автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Нейросетевые алгоритмы для решения задач кодирования изображений с использованием технологии CUDA

005043529

На правах рукописи

Нгуен Виет Хунг

^ 2_

НЕЙРОСЕТЕВЫЕ АЛГОРИТМЫ ДЛЯ РЕШЕНИЯ ЗАДАЧ КОДИРОВАНИЯ ИЗОБРАЖЕНИЙ С ИСПОЛЬЗОВАНИЕМ ТЕХНОЛОГИИ США

Специальность 05.13.01 - системный анализ, управление и обработка информации (в информационно-телекоммуникационных системах)

Автореферат диссертации на соискание учёной степени кандидата технических наук

1 7 МАЙ 2012

Москва-2012

»Л

Л \

005043529

Работа выполнена на кафедре «Интеллектуальных информационных систем и технологий» ФГБОУ ВПО «Московский физико-технический институт (государственный университет)».

Научный руководитель:

Заслуженный деятель науки РФ, доктор технических наук, профессор Галушкин Александр Иванович

Официальные оппоненты:

доктор технических наук, профессор Чобану Михаил Константинович

доктор технических наук, профессор Назаров Лев Евгеньевич

Ведущая организация:

Московский государственный институт электроники и математики

Защита состоится « 31 » мая 2012 г. в 14.00 на заседании совета по защите докторских и кандидатских диссертаций Д.445.001.01 при Центре информационных технологий и систем органов исполнительной власти по адресу: 123557, Москва, Пресненский Вал, 19, стр. 1.

С диссертацией можно ознакомиться в библиотеке Московского физико-технического института (государственного университета) по адресу: 141700, Московская область, г. Долгопрудный, Институтский переулок, 9.

Автореферат разослан «28» апреля 2012 г.

Ученый секретарь совета по защите докторских и кандидатских диссертаций

кандидат технических наук

А. В. Бочаров

Общая характеристика работы

Актуальность темы:

В настоящее время пропускная способность каналов сетей передачи данных продолжает расти, и дает возможность передачи информации все быстрее и быстрее, однако актуальность проблемы сжатия изображений и видео при их передаче по проводным и беспроводным линиям связи (передача телевизионных изображений, передача изображений по линии Internet и др.) сохраняется. Действенным методом снижения технических требований к пропускной способности используемых каналов передачи данных, определяемой вероятностно-энергетическими характеристиками и скоростью передачи, является кодирование (сжатие) изображений и видеопоследовательностей при их передаче и декодирование в приемном устройстве. Появляются многие виды услуг, которые требуют передачи в реальном времени, например такие как видеотелефония, мобильная и стационарная телеконференцсвязь, многопрограммное интерактивное телевидение, телевидение высокой четкости, многопрограммное звуковое вещание и др. Алгоритмы сжатия изображений и видеоданных постоянно совершенствуются, создаются новые стандарты.

Проблема сжатия изображений и видеопоследовательностей актуальна также при создании центров хранения, архивов и каталогов (баз данных) изображений и видеопоследовательностей в цифровом виде (медицинские изображения, космические изображения, получаемые при помощи датчиков дистанционного зондирования, фотоизображения и др.). Решение этой проблемы позволит уменьшить объем информации, хранимой на носителях.

Разработка алгоритмов цифрового сжатия различных видов информации для их передачи по каналам связи как альтернативы аналоговым системам проводится уже более 20 лет во всем в мире. Был получен ряд важных результатов в плане разработки алгоритмов сжатия, включая стандарты JPEG (JPEG-2000), MPEG-1, MPEG-2, MPEG-4 (видео), H.261, H.263, H.264 (AVC) и др. для статических и динамических изображений различного разрешения.

К настоящему времени исследованы разные алгоритмы сжатия изображений. Самыми популярными в практике алгоритмами сжатия изображений являются алгоритмы поблочного кодирования с преобразованием, основанные на дискретных ортогональных преобразованиях. Среди алгоритмов с преобразованием фактическим стандартом являются алгоритмы Joint Photographic Experts Group - JPEG и JPEG2000. Однако эти алгоритмы имеют низкую скорость работы и сложны в аппаратной реализации. В последние годы в связи с широким распространением нейросетевых методов были разработаны нейросетевые алгоритмы сжатия изображений. Исследовались разные типы нейронных сетей как обучаемые с учителем, так и самообучаемые нейронные сети. Нейронные сети могут быть легко распараллелены, что позволяет сократить время вычисления и дает возможность сжимать изображения в реальном времени.

В современных стандартах сжатия видео процесс компенсации движения играет очень важную роль. Использование алгоритмов компенсации движения при одинаковом качестве передаваемого изображения может увеличить степень

сжатия информации. Эффективность и время выполнения процесса компенсации движения сильно зависит от алгоритмов поиска векторов движения. Однако поиск векторов движения является одним из наиболее вычислительно затратных этапов цифрового кодирования, требующего большого числа арифметических операций. В стандартах сжатия видео алгоритмы поиска векторов движения обычно не фиксированы и их можно свободно оптимизировать в рамках стандарта сжатия. Программа сжатия с эффективным алгоритмом поиска векторов движения может достигать значительного преимущества над другими программами, реализующими тот же стандарт сжатия. Поэтому разработка алгоритмов поиска векторов движения является актуальной задачей.

Целью диссертационной работы является разработка эффективных нейросетевых алгоритмов сжатия статических и динамических изображений, обеспечивающих повышение эффективности процесса кодирования с применением технологии CUDA на графических процессорах NVIDIA.

Для достижения поставленной цели были решены следующие задачи:

1. выполнен анализ существующих алгоритмов сжатия статических и видео изображений;

2. разработаны и исследованы нейросетевые алгоритмы сжатия изображения, которые также реализованы на графических процессорах NVIDIA;

3. выполнен анализ существующих алгоритмов поиска векторов движения;

4. разработан и реализован более эффективный по сравнению с аналогами алгоритм поиска векторов движения на графических процессорах NVIDIA;

5. проведены экспериментальные исследования разработанных алгоритмов на реальной информации.

Научная новизна:

1. Предложен новый нейросетевой алгоритм для сжатия изображения на основе самоорганизующейся карты Кохонена в преобразованном пространстве.

2. Предложен алгоритм распараллеливания процесса обучения и эксплуатации сети Кохонена на графическом процессоре.

3. Предложен алгоритм поиска векторов движения, отличающийся от известных использованием нового нейросетевого подхода для построения набора кандидатов вектора движения.

4. Реализация на графических процессорах NVIDIA алгоритмов поиска вектора движения: предложенного алгоритма, алгоритма полного перебора и нового трехшагового алгоритма

Практическая ценность:

1. Разработана программа реализующая процесс обучения сети Кохонена на CUDA. Программа помогает ускорить процесс обучения сети Кохонена в 9-10 раз по сравнению с CPU.

2. Разработан программный комплекс для сжатия изображений с использованием нейронной сети на CUDA.

3. Разработана программа для быстрого нахождения векторов движения на С1ЮА, которая может быть применена в программном комплексе реализующем стандарт сжатия видео.

4. Проведен комплекс экспериментальных исследований разработанных алгоритмов.

Основные положения, выносимые на защиту: На защиту выносятся следующие положения, разработанные и исследованные в данной работе:

1. Новый нейросетевой алгоритм сжатия статического изображения, использующего коэффициенты вейвлетного дискретного преобразования как входы самоорганизующейся карты Кохонена, что позволяет увеличить качество сжатого изображения при высоком коэффициенте сжатия.

2. Реализация процесса обучения сети Кохонена на США, что позволяет увеличить скорость процесса обучения в 9-10 раз. Реализация алгоритма сжатия с использованием сети Кохонена на США, что позволяет увеличить скорость сжатия, и дает возможность сжатия изображений в реальном масштабе времени.

3. Новый алгоритм поиска вектора движения с использованием нейронной сети для определения множества кандидатов, что позволяет уменьшить количество вычислений оценочной функции и увеличить степень компрессии.

4. Реализация предложенного алгоритма поиска вектора движения на С1ША, что позволяет увеличить скорость нахождения вектора движения.

5. Результаты экспериментальных исследований разработанных алгоритмов.

Апробация работы. Основные положения работы докладывались на

следующих семинарах и конференциях:

1. Научно-практическая конференция «Вычисления с использованием графических процессоров в молекулярной биологии и биоинформатике» - Москва -2010.

2. IX Всероссийская конференция «Нейрокомпьютеры и их применение». Москва - 2011

3.54-ая научная конференция МФТИ «Проблемы фундаментальных и прикладных естественных и технических наук в современном информационном обществе» - Долгопрудный - 2011.

4. XIV Всероссийская научно-техническая конференция «Нейроинформатика-2012» - Москва - 2012

5. X Всероссийская конференция «Нейрокомпьютеры и их применение». Москва -2012.

Публикации. По теме диссертации автором опубликовано 9 работ, из них 3 статьи в научно-технических журналах из перечня ВАК [4][5][9].

Структура и объем диссертации: Диссертационная работа состоит из введения, четырех глав, заключения и трех приложений. Содержит 152 страницы, 9 таблиц, 43 рисунков и 3 приложения. Список цитируемой литературы содержит 80 наименований.

Содержание работы

Во введении обоснована актуальность темы диссертации, определены цель и задачи исследования, научная новизна и практическая ценность результатов диссертации, сформулированы основные положения, выносимые на защиту.

В первой главе рассмотрены вопросы сжатия статических и динамических изображений.

Представлена постановка задачи сжатия изображений, классификация методов сжатия, их основные характеристики и описаны основные классические и современные алгоритмы сжатия изображений без потерь и с потерями. Показано, что используя один из алгоритмов сжатия без потерь, можно обеспечить архивацию изображения примерно в 2 раза. В то же время сжатия с потерями, например JPEG и JPEG2000, оперируют с коэффициентами 10-200 раз. Помимо возможности модификации изображения, одна из основных причин подобной разницы заключается в том, что традиционные алгоритмы ориентированы на работу с цепочкой и не учитывают так называемую когерентность областей в изображениях. Идея когерентности областей заключается в малом изменении цвета и структуры на небольшом участке изображения. Алгоритм JPEG имеет в своей основе дискретное косинусное преобразование (ДКП), которое применяется к неперекрывающимся блокам изображения размером 8x8 пикселей. К основным недостаткам можно отнести: распад кодируемого изображения на отдельные блоки по 8x8 пикселей при больших коэффициентах сжатия; появление ложных контуров; плохое описание нестационарного во времени сигнала коэффициентами Фурье-преобразования. Для преодоления указанных недостатков был предложен новый стандарт сжатия изображений JPEG20G0, основу которого составляет вейвлег-преобразование. В этом случае все изображение раскладывается по базисным вейвлет-функциям, локализованным как во временной, так и в частотной областях. Благодаря такому подходу в вейвлет-коэффициентах образуются длинные цепочки идущих подряд нулей, которые эффективно сжимаются энтропийными кодерами.

В этой главе представлена история развития стандартов сжатия видеоданных, используемых в современных видеокомпрессорах. Особенностью последовательности видеоизображений является большая временная избыточность, обусловленная корреляцией соседних кадров, а также пространственная избыточность, содержащаяся в передаваемом изображении и обусловленная корреляцией соседних пикселей изображения. Технология сжатия видео обычно распадается на две части: уменьшение избыточности видеоинформации во временном измерении, и сжатие отдельных изображений. Процесс устранения временной избыточности называется компенсацией движения {motion compensation). На практике широко используется метод компенсации движения, который компенсирует перемещение прямоугольных областей текущего кадра. При этом для каждого фиксированного блока, состоящего из M*N пикселей обрабатываемого кадра, выполняется следующая процедура:

1. Поиск на ссылочном кадре, предыдущем или следующем, ранее закодированном и переданном декодеру, «подходящего» блока из М*1М пикселей. Это делается путем сравнения фиксированного -блока с некоторыми или со всеми блоками области поиска. Область поиска обычно представляет собой некий регион с центром в середине этого выбранного блока. Популярным критерием схожести блоков является энергия остатка, получаемая вычитанием блока-кандидата из фиксированного М*Ы блока, то есть выбирается блок-кандидат, минимизирующий энергию остатка. Этот процесс поиска подходящего блока называется оценкой движения.

2. Выбранный кандидат становится прогнозом текущего М*]\' -блока, и его необходимо вычитать из этого блока для получения остаточного М*Н -блока.

3. Остаточный блок кодируется и передается декодеру, и декодер получает координаты вектора смещения текущего блока по отношению к позиции блока-кандидата - вектора движения. Декодер использует вектор движения для нахождения блока-прогноза, декодирует остаточный блок, и складывает его прогнозом для реконструкции версии исходного блока.

Эффективность компенсации движения полностью зависит от алгоритма нахождения вектора движения.

Во второй главе описаны нейросетевые алгоритмы для решения задачи сжатия статического изображения.

На рис.1 приведена блок-схема двухслойной нейронной сети, составляющей основу рассматриваемых алгоритмов сжатия изображений. Первый слой сети состоит из п1 нейронов, каждый нейрон содержит п (п>п,) входов с весовыми коэффициентами где р = 1,2,...,я, - номер нейрона первого слоя,

» = 1,2,...,« - номер весового коэффициента нейрона этого слоя. Второй слой сети состоит из п нейронов, каждый нейрон содержит пу входов с весовыми коэффициентами и'™ = {и*"1}, где р = 1,2,...,« - номер нейрона второго слоя,

г = 1,2,...,и, - номер весового коэффициента нейрона этого слоя. Параметры п и п, определяются размером обрабатываемых фрагментов изображения и требуемым коэффициентом сжатия.

При кодировании изображение А(х,у) представляется в виде совокупности непересекающихся фрагментов (блоков) /¿(.Х>У) размером n = bxb,

fi? = 1,2,...,—-j^- - номер фрагмента. Нейронная сеть обрабатывает каждый b

фрагмент fd(x,y), для этого на основе отсчетов fd(x,y) формируется

(0) / (0) (0) (0)ч :!

реализация ху = (xu,x\J ,...,xj) длительностью n = b , поступающая на вход сети.

Роль кодера выполняет первый слой сети, для каждого фрагмента fd(x,y) вычисляется ns коэффициентов кодирования x(J' = (х^

г0) _ V И/(1) ■ Г(0) „11 и /14

xpd~2-,wip xid , P = «I (l)

Результатом сжатия изображения А(х,у) является множество квантованных коэффициентов {х^}, к которым можно применить энтропийное кодирование.

Роль декодера выполняет второй слой сети - на основе x(J* восстанавливается фрагмент fd(x,y), отсчеты которого вычисляются с использованием

соотношения

W

п

Коэффициент сжатия можно определить соотношением У„ = —

Алгоритм сжатия с использованием многослойных нейронных сетей основан на преобразовании Карунена-Лоэва. Это преобразование разбивает корреляцию входных образцов пикселей. Но корреляции пикселей в блоках изображения обычно сильно отличаются, поэтому эффективность предложенного нейросетевого алгоритма невысокая. Разработан адаптивный алгоритм для улучшения эффективности алгоритма с использованием многослойных нейронных сетей. Исходя из характера статических изображений, когда элементы в одном блоке обычно похожи друг на друга, и они сильно отличаются только в случае, когда этот блок содержит границы каких-то объектов; возникает идея классификации блоков по сложности содержания.

То, как блоки полученные от исходного изображения будут классифицированы, зависит от их «сложности», которая оценивается по определенному критерию. С этой точки зрения для оценки «сложности» блока bxb выбирается формула (3).

Сложность =

Ы1 2

, ij: четны (3)

Т.к. значения пикселей между объектами, или между объектом и фоном обычно сильно отличаются, то по критерию сложности, «сложность» блоков, содержащих границы объектов, будет выше чем «сложность» других блоков. После классификации, блоки изображений сжимаются разными нейронными сетями с разными числами нейронов скрытого слоя.

Результаты экспериментов на рис. 2 показывают, что при использовании адаптивного алгоритма значения PSNR х выше, чем х при использовании обычного нейросетевого алгоритма с примерно одинаковым коэффициентом сжатия.

PSNR Z 35.00

30.00

25.00

20.00

15.00

10,00

5.00

0.00

Lena Camera man clock Pepper

Рис.2. Сравнение значения PSNR х адаптивного и обычного нейросетевых алгоритмов с примерно одиноковым коэффициентом сжатия

Рассмотрены также другие нейросетевые алгоритмы сжатия изображения: алгоритмы на основе самоорганизующейся карты Кохонена. Суть алгоритма сжатия сетью Кохонена на этапе кодирования изображений заключается в сопоставлении фрагментам изображения х(,) таблицы кодирования, тождественной таблице меток для центров результирующих кластеров. При этом полное множество непересекающихся фрагментов х<0 составляет исходное изображение. В результате кодирования совокупности фрагментов {х(0}сопоставляется последовательность номеров кластеров из кодовой таблицы. Сеть Кохонена самообучается, используя информации входных векторов, и группирует «схожие» входные векторы в одну группу. Обычно, изображение сжимается сетью Кохонена следующим образом: входной вектор, подаваемый на входной слой НС - ретину, соответствует блоку изображения, а элементы вектора - пикселям этого блока. Первый входной слой НС не содержит нейронов, он выполняет коммутационные функции, распространяя каждый входной вектор по всем нейронам второго слоя. Число узлов входного слоя равно числу элементов/пикселей входного вектора. Каждый нейрон второго слоя (слой Кохонена) имеет обучаемые весовые коэффициенты своих входов, число входов соответствует числу узлов первого слоя. Внутри второго слоя все нейроны дополнительно могут быть связаны друг с другом латеральными

стимулирующими и тормозящими связями. Слой Кохонена классифицирует входные векторы в группы «схожих». Предполагается, что входные векторы фактически группируются в классы в соответствии с их положением в векторном пространстве. В своей простейшей форме слой Кохонена функционирует в стиле "победитель забирает все". Побеждает в соревновании нейрон, вектор весовых коэффициентов которого окажется наиболее близким к входному вектору.

Коэффициент сжатия данного алгоритма зависит от числа нейронов My слоя Кохонена и размерности к входного вектора. Для восстановления входного вектора X=(xl,x2,x3,...xi<) необходимо сохранить позицию победительного нейрона. Требуется т = log2(M) битов для сохранения одной из М позиций. Поэтому коэффициент сжатия изображения с помощью нейронной сети Кохонена равен:

кх 8

= КkohonenХ ^-entropy ~ Х ^entropy (4)

Где: Кыотп ~ коэффициент сжатия сети Кохонена;

Кемгору - коэффициент сжатия информации от выходов сети Кохонена энтропийным алгоритмом;

В эксперименте были обучены сети Кохонена с размером 16x16, 32x32, 64x64 для сжатия изображения. Размерность входного вектора была выбрана к = 4x4 = 16. Коэффициенты сжатия сети Кохонена Кыопеп при использовании сети с размером 16x16, 32x32 и 64x64 равны 16, 12.8, 10.67. В эксперименте был использован алгоритм Хаффмана для сжатия информации о позиции нейронов победителей. Результаты экспериментов показаны, что коэффициент сжатия энтропийным алгоритмом KEntropy е (1.6 - 2.2). Следовательно, по формуле (4) общий коэффициент сжатия при использовании сети Кохонена с размером 16x16, 32x32 и 64x64 могут достичь значений е (25-35), К^*2" е (20.5-28),

К^4хе(17-23).

На рис.3 показаны значения PSNR при сжатии изображений с размером 512x512 сетями Кохонена размерами 16x16, 32x32 и 64x64.

Рис.3. Значение РБЫЯ при сжатии изображения 512x512 рх нейронными сетями с разными размерами слоя Кохонена

На рис.4 показаны значения PSNR при сжатии разных изображений сетью Кохонена 64x64 и алгоритмом JPEG с коэффициентом сжатия Ксж = 22. На рис.5 показаны изображения после декодирования. Из результатов сравнения следует, что при высоком коэффициенте сжатия, алгоритм с использованием сети Кохонена дает декодированные изображения лучше по качеству, чем алгоритм

(а) (Ь)

Рис. 5. Изображения после декодирования при высоком коэффициенте Ксж~22 (а) алгоритм с использованием сети Кохонена; (Ь) алгоритм JPEG.

Для улучшения алгоритма сжатия сетью Кохонена, разработан новый поход к обучению сети Кохонена в задаче сжатия изображений: обучать сеть не по значениям пикселей изображения, а по значениям их коэффициентов вейвлетного преобразования. Этот подход возникает из характеристики

Рис.

25 ---г-----,---------ч---

Lena Peppers sailboat airplane

4. Сравнение PSNR при использовании нейронного алгоритма алгоритма JPEG при высоком коэффициенте Кс.ж~22.

Сравнение PSNR НС алгоритма и .JPEG при высоком коэффициенте Ксж~22

31

—НС 64x64 —•—JPEG

разбиения корреляции между соседними пикселями вейвлетного преобразования. Для получения коэффициентов вейвлетного преобразования, сначала все изображение делится на части одинакового размера, над каждой из которых независимо от других и будут происходить дальнейшие преобразования. Далее каждый канал проходит фильтрацию низкочастотным и высокочастотным фильтрами отдельно по строкам и по рядам, в результате чего после первого прохода в каждой части формируются четыре более мелких изображения. Все они несут информацию об исходном изображении, но их информативность сильно отличается. Для сжатия этих коэффициентов, используем такую же структуру, как в алгоритме с использованием обычной нейронной сети, только входные значения сейчас не пиксели изображения, а коэффициенты, получающиеся по вейвлетному преобразованию. Для процесса обратного преобразования, по точности восстановленных изображений, чем больше коэффициенты, тем более важную роль они играют. Поэтому, используются разные сети Кохонена с разными размерами входов (т.е. разные коэффициенты сжатия при фиксированных размерах слоя Кохонена 16x16) для разных каналов коэффициентов. Чем меньше значения коэффициентов канала, тем больше коэффициент сжатия. Чем выше степень, тем меньше коэффициенты разложения. Для 3-степени, используем сеть Кохонена с входным вектором размера 4=2x2; для 2-степени - сеть Кохонена с входным вектором размера 16=4x4; и для 1-степени - сеть Кохонена с входным вектором размера 64=8x8. При использовании сети Кохонена, выходом будет только позиция победительного нейрона, поэтому для каждого входного вектора с размером Р (байт), необходимо сохранить только 1 байт при кодировании. Заметим что, у 3-степени есть 4 части (ННЗ, НВЗ, ВИЗ, ВВЗ) с размером 64x64, у 2-степени - 3 части с размером 128x128, у 1-степени - 3 части с размером 256x256. Таким образом, коэффициент сжатия получается: _ Вход(байт)__512x512_

КА>пеп Выход{байт) 4хб4><64х1 + зх128х128х—+3х256х256х —

4 16 64

(5)

= 25,6

Таблица 1: РЭКШ сжатия монохромных изображений при Кк(Аопеп -25,6

разными алгоритмами

Изображение Стандартная сеть Кохонена Предложенный алгоритм

Lena 22,6785 28,5714

Camera man 21,7325 27,1945

Woman 21,2954 27,0256

Pepper 21,6115 27,5327

1+Зх4х —+ 3х16х — _16_64

64

В таблице 1. показаны результаты PSNR сжатия разных изображений данным алгоритмом и стандартной сетью Кохонена при коэффициенте сжатия Kkohonen = 25.6. Значения PSNR предложенного алгоритма при сжатии всех изображений выше, чем значения PSNR стандартного алгоритма с использованием сети Кохонена.

В третьей главе рассматриваются существующие алгоритмы поиска векторов движения.

Формально задача поиска векторов движения представляет собой задачу минимизации оценочной функции. В практике, наиболее распространённой оценочной функцией является сумма абсолютных разниц SAD, которая используется при компенсации движения, рассчитанная для блока размером NxM с координатами (х,у), trго кадра::

SAD (Vr,Vv) = £ ЕИ* + т,У + и,/,) - F{x + Vx + m,y+Vy + и,/2)|, (6)

я=0 /и=0

Где: SAD - сумма абсолютных разниц (Sum of Absolute Differences), F - значение яркости, ti - временной индекс текущего кадра, t2 - временной индекс опорного кадра, (Vx Vy): вектор движения.

Приведены описания следующих алгоритмов поиска векторов движения: алгоритма полного перебора (FS), алгоритма трехшагового поиска (TSS), алгоритма нового трехшагового поиска (NTTS), алгоритма простого и эффективного поиска (SES), алгоритма четырехшагового noncKa(4SS), алгоритма поиска по алмазу (DS), алгоритма поиска по адаптивному шаблону (ARPS).

Разработан новый алгоритм с использованием метода векторного квантования с помощью сети Кохонена. Применяя алгоритм векторного квантования с использованием сети Кохонена, строится набор кандидатов векторов движения, которые часто встречаются в задаче компенсации движения.

Тестовые Векторы

— - Кодовая книга

видео Алгоритм полного движения Нейронные сети

перебора Кохонена

(векторы движения)

Рис. 6. Схема построения множества кандидатов векторов движения сетью

Кохонена

На рис.6 показана схема построения множества векторов движения с помощью нейронной сети. Сначала строятся вектора движения алгоритмом полного перебора для тестированных видеопоследовательностей. Для построения такого множества используются видеопоследовательности по разным тематикам. Затем обучается нейронная сеть Кохонена этими векторами движения, чтобы получить кодовую книгу. Размер слоя Кохонена зависит от размера области поиска. Например, для макроблока 8x8 с расширением области поиска до +7

пикселей, т.е. с размером 15x15 пикселей, выбирается слой Кохонена с размером 8x8, т.е. 64 выхода соответствуют 64 кандидатам вектора движения.

Множество кандидатов векторов движения строится сетью Кохонена на основе общего характера движения, не смотря на характер самой видеопоследовательности. Чтобы улучшить эффективность алгоритма, к множеству кандидатов для каждого блока добавляются отдельно векторы движения окрестности +1 пиксели соседних блоков предыдущего кадра. Основная идея состоит в том, что поле векторов является достаточно гладким как в пространстве, так и во времени, за исключением разрывов, возникающих на границах объектов, движущихся не одинаково, и ситуации смены общего плана. Схема алгоритма показана на рис.7. Кандидаты векторов движения, полностью построены по предложенному алгоритму, определены до процесса поиска каждого кадра, что дает высокую возможность параллелизма при аппаратном ускорении.

Кадр к-1

Средние значения функции PSNR для предсказанных кадров тестовых видеопоследовательностей формата 4CIF (с разрешением 704x576) предложенного алгоритма и описанных выше методов приведены в таблице. 2. В таблице разработанный алгоритм обозначен как «neural». Результаты сравнения показывают, что значения PSNR предложенного алгоритма близко к значениям PSNR алгоритма полного перебора, и выше значения PSNR других алгоритмов на всех видеопоследовательностях.

На рис.8 показаны отношения времени вычислений предложенного алгоритма и описанных алгоритмов к времени вычислений алгоритма полного перебора при нахождении векторов движения тестовых видеопоследовательностей. Из графика следует, что на обычном процесоре время вычиселения предложеного алгоритма значительно больше, чем остальных

алгоритмов. Но предложенный алгоритм имеет высокую возможность параллелизма, а другие алгоритмы требуют большого количества ветвлений, которые могут стать узким местом в реализации на аппаратном ускорении. Это рассмотрено в главе 4.

Табл.2. Сравнение алгоритмы: PSNR кадров разных видеопоследовательностей в

формате 4CIF (в дБ)

Crew Ice City Harbour Soccer

TSS 27.6365 28.544 28.0588 28.0079 23.0375

SES 26.5733 26.8268 27.4864 27.8223 22.1492

4SS 27.4084 27.9266 28.6184 28.1268 22.676

DS 27.3939 27.8933 28.8855 28.3035 22.6332

ADPS 27.7211 28.7142 29.6335 28.2216 23.1677

NTSS 27.7221 28.5951 28.8089 28.3928 23.1007

Neural 28.0573 28.9889 30.2419 28.4975 23.329

FS 28.362 29.2982 30.4542 28.6367 23.6478

Рис.8. Средние значения отношения времени вычислений всех алгоритмов к времени алгоритма полного перебора

В четвертой главе описан подход к реализации рассмотренных алгоритмов сжатия статических и видео изображений при аппаратной поддержке вычислений. Решение задач сжатия изображения и видеоданных связано с необходимостью сбора и обработки огромных объемов информации потокового видео, особенно в режиме реального времени. Для этих целей, одно из перспективных направлений - использование высокопроизводительных вычислительных средств на базе современных и перспективных многоядерных CPU и графических процессоров (GPU) с технологией CUDA.

CUDA (Compute Unified Device Architecture) - это архитектура параллельных вычислений от NVIDIA, позволяющая существенно увеличить вычислительную производительность благодаря использованию GPU (графических процессоров). Типичные графические процессоры состоят из сотни высокопроизводительных

процессорных ядер и могут достичь высокой параллельности вычислений. Сделан обзор модели CUDA программирования и аппаратной архитектуры для получения потенциальной производительности GPU в реализации предложенных алгоритмов.

Высокая параллелизуемость нейронной сети дает возможность того, что нейронный алгоритм сжатия статических изображений с помощью параллельного аппарата является альтернативой по эффективности сжатия известным алгоритмам сжатия. Представлен подход к реализации процесса обучения и вычисления в алгоритме сжатия самоорганизующейся картой Кохонена на графических процессорах с помощью технологии CUDA и приводятся результаты экспериментальных исследований и сравнение с CPU.

При аппаратной реализации процесс обучения сети Кохонена разбивается на 3 основных ядра CUDA:

1) Вычисление расстояния между входным вектором с весовыми векторами нейронов.

2) Нахождение нейрона победителя.

3) Корректирование весов нейронов.

В первом ядре вычисляются расстояния между входом и всеми векторами весов нейронов. Пусть сеть Кохонена имеет height х width нейронов, и каждый нейрон имеет 16 весов. Таким образом, для вычисления расстояния от входа до всех нейронов нужно выполнить (16 х height х width) операций . Верхний уровень вычислений (сетка) является массивом (height/2 х width) блоков нитей (потоков), а каждый блок включает в себя 16x2 нитей. Поэтому 16 нитей одной строки блока вычисляют разницы между координатами входа и веса одного нейрона. Эти 16 значений потом суммируются алгоритмом параллельной редукции чтобы сократить время работы. Пример схемы суммирования множества чисел показан на рис.9. С использованием этого алгоритма количество вычислений суммы уменьшиться в 16/Iog216 = 4 раза. Результаты вычисления расстояний между входом и нейронами сохраняются в глобальной памяти для нахождения нейрона победителя.

1

7 з 3 6 1 4 7 с 1 S А 3 6

Рис.9. Схема суммирования по алгоритму параллельной редукции

16

Процесс нахождения нейрона победителя реализуется параллельно во втором ядре. Требуется найти минимальное значение среди всех расстояний, получившихся в первом ядре. Для распараллеливания этого ядра применяется стандартный прием «разделяй и властвуй». Для начала весь массив расстояний между входом и нейронами разбивается на части и каждой такой части ставится в соответствие один блок сетки, который и будет считать минимум всех элементов данной части массива. Хотя блоки удобно использовать одномерные, но для больших массивов может понадобиться использование двухмерной сетки, поскольку в CUDA существует ограничение на размер сетки по любому измерению, равный 65535.

Итак, каждый блок отвечает за нахождение минимума всех соответствующих ему элементов массива. Таким образом, исходная задача разбивается на набор независимо решаемых подзадач - нахождение минимума для отдельных частей массива. Для распараллеливания данной операции на отдельные нити вновь применяется принцип «разделяй и властвуй» - соответствующие блоку элементы массива разбиваются на пары и элементы каждой пары параллельно сравниваются между собой.

В результате получается вдвое меньше элементов, которые нужно сравнить. Они опять разбиваются на пары и параллельно сравниваются элементы каждой пары. Далее подобный процесс повторяется снова. После каждого повторения число элементов будет уменьшаться вдвое, и при блоке в Elem элементов понадобится log2 Elem шагов для получения требуемого минимума. Например, для сети Кохонена с размером 32x32, надо log2(32x32) = 10 шагов вместо 1024, а для сети с размером 64x64 надо log2 (64x64) = 12 шагов вместо 4096 шагов на CPU. Данный процесс (для примера нарисован процесс только для 16 элементов) показан на рис.10.

Мзсснв расстояний между

После обнаружения нейрона победителя для данного входа, веса победителя и его соседей обновляются. Так как веса нейронов друг от друга не зависят, то параллельный процесс обновления весов реализуется легко. На сетке вычислений CUDA реализуются height х width блоков, каждый из которых содержит 16 нитей для обновления 16 значений весов одного нейрона по формуле корректирования

весов нейронов. В итоге графические процессоры позволяют вычислять формулу корректирования весов параллельно 16х height х width раз.

В эксперименте были использованы 20000 блоков с размером 4x4 пикселей из разных черно-белых изображений для обучения сети. На рис.11 показано отношение времени обучения сети Кохонена с разными размерами слоя Кохонена после 500*20000 = 10000000 шагов на CPU и на CUD А.

Результаты экспериментов показывают, что время обучения сети на CPU значительно больше, чем на GPU. Чем больше размер сети Кохонена, тем выше отношение времени обучения двух процессов.

ГзГ зо

25 20 15 10

16x16 24x24 32x32 48x48 64x64

j

Рис. 11. Отношение времени обучения сети Кохонена на CPU и на CUDA

При увеличении размера сети Кохонена от 16x16 до 64x64 нейронов, время обучения сети на CPU от 4 до 30 раз больше чем на CUDA. Это объясняется тем, что чем больше размер сети, тем больше число операций на каждом шаге обучения, т.е. тем большее число операций можно параллельно вычислять и следовательно эффективнее процесс распараллеливания.

В процессе обучения можно было распараллеливать процесс нахождения нейрона «победителя» только одного входа, а не нескольких входов, т.к. после нахождения победителя необходимо обновляться все веса. Однако, для реализации обучаемой сети на CUDA, можно распараллеливать процессы нахождения нейрона «победителя» сразу всех входов, т.к. эти процессы не зависят друг от друга.

В реализации используется два уровня параллелизма:

1) Первый уровень параллелизма используется на уровне входов сети. Изображение разбивается на блоки с размером 4x4, и каждый блок является входом сети Кохонена как показано выше. Поскольку взаимозависимости между блоками не существует, все блоки могут быть сжаты параллельно. В архитектуре CUDA, один блок в сетке блоков (grid) используется для нахождения нейрона «победителя» для одного блока изображения. Данные о позиции этого нейрона представляются как сжатая информация данного блока изображения.

2) Второй уровень параллелизма - это распараллеливание процесса нахождения нейрона «победителя». Для этого следует параллельно вычислять расстояния между входом и всеми нейронами, и результаты сравнивать между

собой, чтобы получить самое маленькое значение. В идеале, расстояние каждого нейрона до входа вычислялись бы в отдельной нити и все выходы нейронов сразу бы параллельно вычислялись. Но из-за органичности количества нитей в одном блоке (в каждом блоке невозможно более 512 нитей) для сети с большим размером слоя Кохонена, в одной нити должны вычисляться расстояния несколько нейронов. В реализации выбран размер блока нитей равным 16x16 и каждая нить вычисляет расстояния нескольких нейронов, в зависимости от размера сети Кохонена. Например, если используется сеть Кохонена с размером 32x32 нейронов для сжатия статических изображения, то в каждой нити должны вычисляться расстояния (32x32) / (16x16) = 4 нейронов; если размер сети равен 64x64, то (64х64)/(16х16) = 16 нейронов. Результаты вычисления сохраняются в разделяемой памяти для сравнения.

На рисунке 12 показано время в секундах на сжатие изображения с помощью разных сетей Кохонена (размер сети меняется от 16x16 до 64x64 нейронов) на CPU и на GPU.

Рис.12. Время (в секундах) на сжатие изображения сетями Кохонена на CPU и на GPU для изображения с размером 256x256 пикселей (а) и 512x512 пикселей (Ь)

Результаты показывают, что с помощью технологии CUDA, скорость сжатия изображения по нейронному алгоритму значительно увеличивается, от десяти до сотен раз быстрее, в зависимости от размера исходного изображения и размера выбранной нейронной сети.

В результате проведенного сравнительного анализа в главе 3 было принято решение, что наилучшим по эффективности и по времени среди 6 исследованных алгоритмов (TSS, SES, 4SS, DS, ADPS, NTSS) является алгоритм NTSS. Использование этого алгоритма позволяет достичь достаточно высокие значения PSNR при малом времени вычислений. Поэтому для сравнения эффективности алгоритмов на графических процессорах реализованы алгоритм NTSS, алгоритм полного перебора и алгоритм с использованием нейронной сети.

В ядре для всех алгоритмов применяется общий подход: для каждого блока текущего кадра, рассчитать SAD по всем перемещениям кандидатов и выбрать лучшее перемещение, которое сводит к минимуму функции SAD (6). Используются два уровня параллелизма в алгоритмах поиска (рис.13):

1) Первый уровень параллелизма используется на уровне макроблока. Кадр разбивается на сотни или тысячи макроблоков в зависимости от разрешения изображения, и процесс поиска выполняется для каждого макроблока. Поскольку взаимозависимости между макроблоками не существует, алгоритмы могут быть применены для всех макроблоков параллельно.

2) Второй уровень параллелизма - это параллелизм на уровне пикселей. Для вычисления SAD необходимо вычислить абсолютные разницы между всеми пикселями макроблока кандидата и текущего макроблока и просуммировать эти значения. В реализации, абсолютные разницы одного столбца блока вычисляются параллельно в одной итерации, и суммируются по алгоритму параллельной редукции чтобы сократить время вычисления.

Сетка блоков

Глобальная память

Постоянная память

Текстурная память

[........ К потоки

(обработка К блоков кадре параллельно)

Векторы движения

Суммирование по столбцу

Текущий и опорный кадры

Рис.13. Реализация алгоритмов поиска векторов движения на CUDA

Среднее значение PSNR и времени нахождения векторов движения для первых 200 кадров трех алгоритмов на CUDA показаны на рис.14. В этом эксперименте размер макроблока был 8x8, и область поиска 15x15 пикселей. Результаты реализации алгоритмов на CUDA показывают, что значения PSNR предложенного алгоритма близки к значениям PSNR алгоритма полного перебора, и значительно выше значений PSNR алгоритма NTSS. Время работы предложенного алгоритма на CUDA почти в 3 раза меньше, чем алгоритма полного перебора. Этот результат объясняется тем, что число вычислений функции SAD в предложенном алгоритме меньше в 3 раза, чем в алгоритме полного перебора, однако, хотя число вычислений функции SAD в алгоритме N'TSS меньше, чем в алгоритме с использованием нейронной сети, но позиции

кандидата вектора движения не определены заранее, и зависят от предыдущих кандидатов, то есть влияет на параллелизм работы и задерживает работу алгоритма. Результаты на рис.15 показывают также, что время выполнения на CUDA гораздо меньше (в тысячи раз) чем на CPU.

Рис.14: (а) Среднее значение РЗИЯ (в дБ) (Ь) Время нахождения векторов движения (в миллисекундах) 200 кадров разных видеопоследовательностей

к Полный перебор I Нейронный метод ÏNTSS

Cre* Ice News Football Foreman Видеопоследовательность

* Полный перебор ■ Нейронный метад SNT5S

Ввдеопоследовцгсзьность

Рис.4.15: Время нахождения векторов движения 200 кадров разных

видеопоследовательностей нейронным алгоритмом на CUDA и на CPU.

В заключении перечислены основные результаты, полученные в диссертационной работе.

1. Проведен анализ эффективности основных нейросетевых алгоритмов сжатия изображений. По результатам экспериментов был сделан вывод о том, что в случаях, когда требуется большой высокий коэффициент сжатия, качество сжатых изображений при использовании нейронных сетей больше, чем при использовании самого популярного алгоритма JPEG.

2. Предложен новый нейросетевой алгоритм для сжатия изображений на основе самоорганизующейся карты Кохонена в преобразованном пространстве. Значение PSNR предложенного алгоритма выше, чем PSNR обычного алгоритма Кохонена, однако, при этом сложность алгоритма увеличивается.

Crew Ice News Fooihall Foreman видеопоследовательность

3. Предложен алгоритм поиска векторов движения, отличающийся от известных использованием нового нейросетевого подхода построения набора кандидатов вектора движения. Проведен сравнительный анализ эффективности предложенного алгоритма и известных алгоритмов поиска векторов движения, для сжатия видеоданных. По результатам экспериментов был сделан вывод о том. что предложенный алгоритм продемонстрировал лучшие результаты PSNR и дал высокую возможность параллелизма при аппаратном ускорении, например на графических процессорах NVIDIA.

4. Предложен алгоритм распараллеливания процесса обучения и эксплуатации сети Кохонена на графических процессорах NVIDIA . Реализация процесса обучения сети Кохонена на CUD А позволяет увеличить скорость процесса в 8-30 раз, при изменении размера Кохонена от 16x16 до 64x64. Сжатие изображения нейронной сетью Кохонена на GPU превосходит по скорости CPU от десяти до сотни раз, в зависимости от размера исходного изображения.

5. Разработан подход к реализации на графических процессорах NVIDIA алгоритмов поиска вектора движения: предложенного алгоритма, алгоритма полного перебора и нового трехшагового алгоритма. Результаты экспериментов показывают, что время работы предложенного алгоритма на CUDA почти в 3 раза меньше, чем алгоритма полного перебора и меньше, чем алгоритма NTSS на 1015%. Результаты показывают также, что время выполнения работы на CUDA гораздо меньше (в тысячи раз) чем на CPU.

В приложениях к диссертационной работе представлен список используемых обозначений и сокращений, исходные коды реализации алгоритмов в среде Matlab и коды реализации алгоритмов на CUDA.

Публикации по основным результатам диссертации:

1. Аляутдинов M .А., Коробкова C.B., Нгуен Виет Хунг. Оптимальные пакеты программ обработки изображений для вычислительных систем на базе процессоров NVIDIA // Тезис докладов научно-практической конференции «Вычисления с использованием графических процессоров в молекулярной биологии и биоинформатике» - Москва 2010. - С. 22-23.

2. Нгуен Виет Хунг. Сжатие изображения с использованием нейронной сети в преобразованном пространстве. // Тезис докладов IX всероссийской конференции «Нейрокомпьютеры и их применение». Москва - 2011 - С.34

3. Нгуен Виет Хунг. Применение нейронных сетей для нахождения вектора движения в задаче кодирования видеопоследовательности со стандартом H.264/AVC// Труды 54-й научной конференции МФТИ «Проблемы фундаментальных и прикладных естественных и технических наук в современном информационном обществе» - Долгопрудный - 2011. - С. 40 - 41.

4. Нгуен Виет Хунг. Нейросетевой алгоритм для решения задачи компенсации движения в видеопоследовательностях со стандартом H264/AVC// Журнал «Информатизация и Связь». -№6, 2005. - С. 77 - 80.

5. Нгуен Виет Хунг. Сжатие изображения с использованием нейронной сети в преобразованном пространстве// Журнал «Нейросетевые технологии» в журнале «Информационные технологии» №1.2012 - Стр. 76 - 78

6. Нгуен Виет Хунг. Применение нейросетевых методов слияния данных в задаче экстраполяции функций с аппаратной поддержкой вычислений // XIV всероссийская научно-техническая конференция «Нейроинформатика-2012», Сборник научных трудов, часть 2 - 2012 - С.82-91.

7. Нгуен Виет Хунг, Муравьев A.B. Реализация нейросетевого алгоритма компенсации движения в видео кодировании с использованием технологии NVIDIA CUDA // Тезис докладов X всероссийской конференции «Нейрокомпьютеры и их применение». Москва - 2012 - С.39.

8. Нгуен Виет Хунг. Сжатие изображения с использованием сети Кохонена при помощи технологии NVIDIA CUDA // Тезис докладов X всероссийской конференции «Нейрокомпьютеры и их применение». Москва - 2012 - С.40.

9. Нгуен Виет Хунг, Муравьев A.B. Применение нейросетевого алгоритма в задаче компенсации движения в видео кодировании при помощи технологии NVIDIA CUDA // Журнал «Нейросетевые технологии» в журнале «Информационные технологии» №5, 2012 - Стр. 74-78.

л

Подписано в печать: 27.04.2012

Заказ № 7314 Тираж - 100 экз. Печать трафаретная. Типография «11-й ФОРМАТ» ИНН 7726330900 115230, Москва, Варшавское ш., 36 (499) 788-78-56 wvvw.autoreferat.ru

61 12-5/2494

Московский физико-технический институт (государственный университет)

КОДИРОВАНИЯ ИЗОБРАЖЕНИЙ С ИСПОЛЬЗОВАНИЕМ

ТЕХНОЛОГИИ США

Специальность 05.13.17 - теоретические основы информатики

Диссертация на соискание ученой степени кандидата технических наук

Научный руководитель: Заслуженный деятель науки РФ, доктор технических наук, профессор Галушкин Александр Иванович

Москва - 2012

ВВЕДЕНИЕ...........................................................................................................5

1. ОБЗОР МЕТОДОВ СЖАТИЯ ИЗОБРАЖЕНИЙ.............................12

1.1 Методы сжатия статических изображений..........................................12

1.1.1 Постановка задачи сжатия изображений. Основные

12

характеристики....................................................................................................

1.1.2 Методы сжатия без потери информации..........................................17

1.1.2.1 Метод группового кодирования (RLE)..........................................17

1.1.2.2 Метод Хаффмана..............................................................................18

1.1.2.3 Адаптивные коды Хаффмана..........................................................19

1.1.2.4 Алгоритм Лемпеля-Зива (LZ-compression)....................................20

1.1.2.5 Алгоритм Лемпеля-Зива-Велча (Lempel-Ziv-Welch -LZW)........21

1.1.2.6 Алгоритм Lossless JPEG..................................................................22

1.1.3 Методы сжатия с потерями................................................................23

1.1.3.1 Алгоритм JPEG.................................................................................23

1.1.3.2 Алгоритм JPEG 2000........................................................................29

1.2 Методы сжатия динамических изображений......................................35

1.2.1 Обзор стандартов.................................................................................36

1.2.2 Описание общего алгоритма компрессии.........................................39

1.2.3 Задача компенсации движения..........................................................43

1.3 Вывод по главе 1.....................................................................................46

2. НЕЙРОСЕТЕВЫЕ АЛГОРИТМЫ В ЗАДАЧЕ СЖАТИЯ СТАТИЧЕСКИХ ИЗОБРАЖЕНИЙ..............................................................48

2.1 Сжатие изображений с использованием многослойных нейронных

сетей49

2.1.2 Многослойные нейронные сети.........................................................49

2.1.2 Многослойный нейросетевой алгоритм сжатия изображения.......53

2.1.3 Результаты экспериментов.................................................................57

2.2 Сжатие изображений с использованием многослойных нейронных сетей: Адаптивный метод................................................................................59

2.3 Алгоритм сжатия на основе самоорганизующейся сети Кохонена.. 62

2.4 Сжатие изображений с использованием нейронной сети в преобразованном пространстве......................................................................72

2.5 Вывод по главе 2.....................................................................................74

3. ИССЛЕДОВАНИЕ И РАЗРАБОТКА АЛГОРИТМА КОМПЕНСАЦИИ ДВИЖЕНИЯ В ЗАДАЧЕ КОДИРОВАНИЯ ВИДЕОПОСЛЕДОВАТЕЛЬНОСТИ............................................................76

3.1 Алгоритм полного перебора..................................................................78

3.1.2 Алгоритм трехшагового поиска.........................................................78

3.1.3 Алгоритм нового трехшагового поиска............................................80

3.1.4 Алгоритм простого и эффективного поиска....................................83

3.1.5 Алгоритм четырехшагового поиска..................................................85

3.1.6 Алгоритм поиска по алмазу...............................................................88

3.1.7 Алгоритм поиска по адаптивному шаблону - Adaptive Rood Pattern Search (ARPS)...................................................................................................89

3.2 Разработка алгоритма компенсации движения с использованием

- 91 нейронной сети.................................................................................................у 1

3.2.1 Обоснование необходимости разработки нового алгоритма.........91

3.2.2 Описание алгоритма............................................................................92

3.2.2.1 Алгоритм векторного квантования................................................92

3.3.2.2 Квантование с использованием сети Кохонена............................93

3.3.2.3 Построение множество кандидатов векторов движения.............94

3.3 Реализация алгоритмов и сравнение их эффективности....................95

3.4 Выводы по главе 3..................................................................................99

4. РЕАЛИЗАЦИЯ АЛГОРИТМОВ НА ГРАФИЧЕСКИХ ПРОЦЕССОРАХ NVIDIA.............................................................................101

4.1 Технология CUD А................................................................................103

4.2 Реализация алгоритма сжатия статического изображения на графической карте с использованием технологией CUDA.......................110

4.2.1 Обучение самоорганизующейся карты сжатия статического изображения с помощью технологии CUDA..............................................111

4.2.2 Реализация алгоритма сжатия изображения..................................116

4.3 Реализация алгоритмов компенсации движения на графических процессорах с использованием технологии CUDA...................................120

4.3.1 Описание подхода к реализации алгоритмов на CUDA................120

4.3.2 Эксперименты и результаты реализации........................................124

4.4 Выводы по главе 4................................................................................126

ЗАКЛЮЧЕНИЕ...............................................................................................128

ЛИТЕРАТУРЫ................................................................................................130

Приложение 1: Исходный код обучения нейронной сети Кохонена на

CUDA.................................................................................................................138

Приложение 2: Исходный код ядра реализации обученной нейронной

сети Кохонена на CUDA.................................................................................147

Приложение 3: Исходный код ядра реализации нейросетевого

алгоритма для поиска векторов движения на CUDA..............................149

Приложение 4: Акты о внедрении результатов диссертации................153

ВВЕДЕНИЕ

Актуальность темы:

В настоящее время пропускная способность каналов сетей передачи данных продолжает расти, и дает возможность передачи информации все быстрее и быстрее, однако актуальность проблемы сжатия изображений и видео при их передаче по проводным и беспроводным линиям связи (передача телевизионных изображений, передача изображений по линии Internet и др.) сохраняется. Действенным методом снижения технических требований к пропускной способности используемых каналов передачи данных, определяемой вероятностно-энергетическими характеристиками и скоростью передачи, является кодирование (сжатие) изображений и видеопоследовательностей при их передаче и декодирование в приемном устройстве. Появляются многие виды услуг, которые требуют передачи в реальном времени, например такие, как видеотелефония, мобильная и стационарная телеконференцсвязь, многопрограммное интерактивное телевидение, телевидение высокой четкости, многопрограммное звуковое вещание и др. Алгоритмы сжатия изображений и видеоданных постоянно совершенствуются, создаются новые стандарты.

Проблема сжатия изображений и видеопоследовательностей актуальна также при создании центров хранения, архивов и каталогов (баз данных) изображений и видеопоследовательностей в цифровом виде (медицинские изображения, космические изображения, получаемые при помощи датчиков дистанционного зондирования, фотоизображения и др.). Решение этой проблемы позволит уменьшить объем информации, хранимой на носителях.

Разработка алгоритмов цифрового сжатия различных видов информации для их передачи по каналам связи как альтернативы аналоговым системам проводится уже более 20 лет во всем в мире. Был получен ряд важных результатов в плане разработки алгоритмов сжатия, включая стандарты JPEG (JPEG-2000)[3-5][18-20][74-76], MPEG-1, MPEG-2,

MPEG-4, H.261, H.263, H.264 (AVC) (видео) [6][8][10][77-80] и др. для статических и динамических изображений различного разрешения.

К настоящему времени исследованы разные алгоритмы сжатия изображений. Самыми популярными в практике алгоритмами сжатия изображений являются алгоритмы поблочного кодирования с преобразованием, основанные на дискретных ортогональных преобразованиях. Среди алгоритмов с преобразованием фактическим стандартом являются алгоритмы Joint Photographic Experts Group - JPEG и JPEG2000. Однако эти алгоритмы имеют низкую скорость работы и сложны в аппаратной реализации. В последние годы в связи с широким распространением нейросетевых методов были разработаны нейросетевые алгоритмы сжатия изображений. Исследовались разные типы нейронных сетей как обучаемые с учителем, так и самообучаемые нейронные сети. Нейронные сети могут быть легко распараллелены, что позволяет сократить время вычисления и дает возможность сжимать изображения в реальном

масштабе времени.

В современных стандартах сжатия видео процесс компенсации движения играет очень важную роль [11][27-28]. Использование алгоритмов компенсации движения при одинаковом качестве передаваемого изображения может увеличить степень сжатия информации. Эффективность и время выполнения процесса компенсации движения сильно зависит от алгоритмов поиска векторов движения. Однако поиск векторов движения является одним из наиболее вычислительно затратных этапов цифрового кодирования, требующего большого числа арифметических операций. В стандартах сжатия видео алгоритмы поиска векторов движения обычно не фиксированы и их можно свободно оптимизировать в рамках стандарта сжатия. Программа сжатия с эффективным алгоритмом поиска векторов движения может достигать значительного преимущества над другими

программами, реализующими тот же стандарт сжатия. Поэтому разработка алгоритмов поиска векторов движения является актуальной задачей.

Целью диссертационной работы является разработка эффективных нейросетевых алгоритмов сжатия статических и динамических изображений, обеспечивающих повышение эффективности процесса кодирования с применением технологии CUDA на графических

процессорах NVIDIA.

Для достижения поставленной цели были решены следующие задачи:

1. выполнен анализ существующих алгоритмов сжатия статических и

видео изображений;

2. разработаны и исследованы нейросетевые алгоритмы сжатия изображения, которые также реализованы на графических процессорах NVIDIA;

3. выполнен анализ существующих алгоритмов поиска векторов движения;

4. разработан и реализован более эффективный по сравнению с аналогами алгоритм поиска векторов движения на графических процессорах NVIDIA;

5. проведены экспериментальные исследования разработанных

алгоритмов на реальной информации. Научная новизна:

1. Предложен новый нейросетевой алгоритм для сжатия изображения на основе самоорганизующейся карты Кохонена в преобразованном пространстве.

2. Предложен алгоритм распараллеливания процесса обучения и эксплуатации сети Кохонена на графическом процессоре.

3. Предложен алгоритм поиска векторов движения, отличающийся от известных использованием нового нейросетевого подхода для построения набора кандидатов вектора движения.

4. Разработан подход к реализации на графических процессорах NVIDIA алгоритмов поиска вектора движения: предложенного алгоритма, алгоритма полного перебора и нового трехшагового алгоритма.

Практическая ценность:

1. Разработана программа реализующая процесс обучения сети Кохонена на CUDA. Программа помогает ускорить процесс обучения сети Кохонена в 9-10 раз по сравнению с CPU.

2. Разработан программный комплекс для сжатия изображений с использованием нейронной сети на CUDA.

3. Разработана программа для быстрого нахождения векторов движения на CUDA, которая может быть применена в программном комплексе реализующем стандарт сжатия видео.

4. Проведен комплекс экспериментальных исследований разработанных алгоритмов.

Основные положения, выносимые на защиту: На защиту выносятся следующие положения, разработанные и исследованные в данной работе:

1. Новый нейросетевой алгоритм сжатия статического изображения, использующего коэффициенты вейвлетного дискретного преобразования как входы самоорганизующейся карты Кохонена, что позволяет увеличить качество сжатого изображения при высоком коэффициенте сжатия.

2. Реализация процесса обучения сети Кохонена на CUDA, что позволяет увеличить скорость процесса обучения в 8-30 раз. Реализация алгоритма сжатия с использованием сети Кохонена на CUDA, что позволяет увеличить скорость сжатия, и дает возможность сжатия изображений в реальном масштабе времени.

3. Алгоритм поиска вектора движения с использованием нейронной сети для определения множества кандидатов, что позволяет уменьшить количество вычислений оценочной функции и увеличить степень компрессии.

4. Реализация предложенного алгоритма поиска вектора движения на CUD А, что позволяет увеличить скорость нахождения вектора движения.

5. Результаты экспериментальных исследований разработанных алгоритмов.

Апробация работы. Основные положения работы докладывались на следующих семинарах и конференциях:

1. Научно-практическая конференция «Вычисления с использованием графических процессоров в молекулярной биологии и биоинформатике» -Москва-2010.

2. IX Всероссийская конференция «Нейрокомпьютеры и их применение». Москва - 2011

3. 54-й научная конференция МФТИ «Проблемы фундаментальных и прикладных естественных и технических наук в современном информационном обществе» - Долгопрудный - 2011.

4. XIV Всероссийская научно-техническая конференция «Нейроинформатика-2012» - Москва - 2012

5. X Всероссийская конференция «Нейрокомпьютеры и их применение». Москва -2012.

Публикации. По теме диссертации автором опубликовано 9 работ [5967], из них 3 статьи в научно-технических журналах из перечня ВАК [62][63][67].

1. Аляутдинов М.А., Коробкова C.B., Нгуен Виет Хунг. Оптимальные пакеты программ обработки изображений для вычислительных систем на базе процессоров NVIDIA // Тезис докладов научно-практической

конференции «Вычисления с использованием графических процессоров в молекулярной биологии и биоинформатике» - Москва 2010. - С. 22 - 23.

2. Нгуен Виет Хунг. Сжатие изображения с использованием нейронной сети в преобразованном пространстве. // Тезис докладов IX всероссийской конференции «Нейрокомпьютеры и их применение». Москва - 2011 - С.34

3. Нгуен Виет Хунг. Применение нейронных сетей для нахождения вектора движения в задаче кодирования видеопоследовательности со стандартом H.264/AVC// Труды 54-й научной конференции МФТИ «Проблемы фундаментальных и прикладных естественных и технических наук в современном информационном обществе» - Долгопрудный - 2011. -С. 40-41.

4. Нгуен Виет Хунг. Нейросетевой алгоритм для решения задачи компенсации движения в видеопоследовательностях со стандартом H264/AVC// Журнал «Информатизация и Связь». -№6, 2005. - С. 77 - 80.

5. Нгуен Виет Хунг. Сжатие изображения с использованием нейронной сети в преобразованном пространстве// Журнал «Нейросетевые технологии» в журнале «Информационные технологии» №1, 2012 - Стр. 76 - 78

6. Нгуен Виет Хунг. Применение нейросетевых методов слияния данных в задаче экстраполяции функций с аппаратной поддержкой вычислений // XIV всероссийская научно-техническая конференция «Нейроинформатика-2012», Сборник научных трудов, часть 2 - 2012 - С.82-91.

7. Нгуен Виет Хунг, Муравьев A.B. Реализация нейросетевого алгоритма компенсации движения в видео кодировании с использованием технологии NVIDIA CUDA // Тезис докладов X всероссийской конференции «Нейрокомпьютеры и их применение». Москва - 2012 - С.39.

8. Нгуен Виет Хунг. Сжатие изображения с использованием сети Кохонена при помощи технологии NVIDIA CUDA // Тезис докладов X

всероссийской конференции «Нейрокомпьютеры и их применение». Москва - 2012 - С.40.

9. Нгуен Виет Хунг, Муравьев A.B. Применение нейросетевого алгоритма в задаче компенсации движения в видео кодировании при помощи технологии NVIDIA CUDA // Журнал «Нейросетевые технологии» в журнале «Информационные технологии» №5, 2012 - Стр. 74 - 78.

Благодарности

Автор выражает глубокую благодарность научному руководителю А.И. Галушкину за общее руководство, обучение и постоянную поддержку в осуществлении работы.

Также автор особенно признателен коллективу кафедры «Интеллектуальные информационные системы и технологии» ФГБОУ ВПО «Московский физико-технический институт (государственный университет)» Аведьяну Э.Д, Пантюхину Д.В, Воронкову И.М. и др. за ценные советы и рекомендации в работе над диссертацией.

1.

ОБЗОР МЕТОДОВ СЖАТИЯ ИЗОБРАЖЕНИЙ

1.1 Методы сжатия статических изображений

1.1.1 Постановка задачи сжатия изображений. Основные характеристики

Проблема сжатия изображений формулируется следующим образом [12]. Изображение в цифровом виде А(х,у),0 < х < Ых ,0 < у < Ыу - это

двумерный массив данных, элементы которого принадлежат дискретному алфавиту {ак} объемом М, к = 1,2,...,М, Рг{ак} - вероятности символов ак. Требуется наиболее экономично представить изображение А(х,у) последовательностью двоичных символов, удовлетворяя дополнительным ограничивающим условиям. Ограничивающие условия заключаются либо в точном восстановлении изображения при декодировании, либо в допустимой мере искажения декодированного изображения А(х,у) по отношению к исходному изображению А(х,у).

Задача сжатия изображения состоит из двух основных частей: кодирование и декодирование. Если декодированное изображение всегда в точности соответствует кодируемому изображению, то такой алгоритм кодирования-декодирования называется алгоритмом сжатия без потерь. Если декодированное изображение отличается от кодированного, то подобный алгоритм назы�