Авторефераты по всем темам >>
Авторефераты по техническим специальностям
На правах рукописи
Нгуен Виет Хунг
НЕЙРОСЕТЕВЫЕ АЛГОРИТМЫ ДЛЯ РЕШЕНИЯ ЗАДАЧ КОДИРОВАНИЯ ИЗОБРАЖЕНИЙ С ИСПОЛЬЗОВАНИЕМ ТЕХНОЛОГИИ CUDA
Специальность 05.13.01 - системный анализ, управление и обработка информации (в информационно-телекоммуникационных системах)
Автореферат диссертации на соискание учёной степени кандидата технических наук
Москва - 2012
Работа выполнена на кафедре Интеллектуальных информационных систем и технологий ФГБОУ ВПО Московский физико-технический институт (государственный университет).
Научный консультант: Заслуженный деятель науки РФ, доктор технических наук, профессор Галушкин Александр Иванович
Официальные оппоненты: доктор технических наук, профессор Чобану Михаил Константинович доктор технических наук, профессор Назаров Лев Евгеньевич
Ведущая организация: Московский государственный институт электроники и математики
Защита состоится л 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 (видео), Н.261, Н.263, Н.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. Разработана программа для быстрого нахождения векторов движения на CUDA, которая может быть применена в программном комплексе реализующем стандарт сжатия видео.
4. Проведен комплекс экспериментальных исследований разработанных алгоритмов.
Основные положения, выносимые на защиту: На защиту выносятся следующие положения, разработанные и исследованные в данной работе:
1. Новый нейросетевой алгоритм сжатия статического изображения, использующего коэффициенты вейвлетного дискретного преобразования как входы самоорганизующейся карты Кохонена, что позволяет увеличить качество сжатого изображения при высоком коэффициенте сжатия.
2. Реализация процесса обучения сети Кохонена на CUDA, что позволяет увеличить скорость процесса обучения в 9-10 раз. Реализация алгоритма сжатия с использованием сети Кохонена на CUDA, что позволяет увеличить скорость сжатия, и дает возможность сжатия изображений в реальном масштабе времени.
3. Новый алгоритм поиска вектора движения с использованием нейронной сети для определения множества кандидатов, что позволяет уменьшить количество вычислений оценочной функции и увеличить степень компрессии.
4. Реализация предложенного алгоритма поиска вектора движения на CUDA, что позволяет увеличить скорость нахождения вектора движения.
5. Результаты экспериментальных исследований разработанных алгоритмов.
Апробация работы. Основные положения работы докладывались на следующих семинарах и конференциях:
1. Научно-практическая конференция Вычисления с использованием графических процессоров в молекулярной биологии и биоинформатике - Москва - 2010.
2. IX Всероссийская конференция Нейрокомпьютеры и их применение.
Москва - 203. 54-ая научная конференция МФТИ Проблемы фундаментальных и прикладных естественных и технических наук в современном информационном обществе - Долгопрудный - 2011.
4. XIV Всероссийская научно-техническая конференция Нейроинформатика-2012 - Москва - 205. X Всероссийская конференция Нейрокомпьютеры и их применение.
Москва -2012.
Публикации. По теме диссертации автором опубликовано 9 работ, из них статьи в научно-технических журналах из перечня ВАК [4][5][9].
Структура и объем диссертации: Диссертационная работа состоит из введения, четырех глав, заключения и трех приложений. Содержит 152 страницы, 9 таблиц, 43 рисунков и 3 приложения. Список цитируемой литературы содержит 80 наименований.
Содержание работы Во введении обоснована актуальность темы диссертации, определены цель и задачи исследования, научная новизна и практическая ценность результатов диссертации, сформулированы основные положения, выносимые на защиту.
В первой главе рассмотрены вопросы сжатия статических и динамических изображений.
Представлена постановка задачи сжатия изображений, классификация методов сжатия, их основные характеристики и описаны основные классические и современные алгоритмы сжатия изображений без потерь и с потерями.
Показано, что используя один из алгоритмов сжатия без потерь, можно обеспечить архивацию изображения примерно в 2 раза. В то же время сжатия с потерями, например JPEG и JPEG2000, оперируют с коэффициентами 10-200 раз.
Помимо возможности модификации изображения, одна из основных причин подобной разницы заключается в том, что традиционные алгоритмы ориентированы на работу с цепочкой и не учитывают так называемую когерентность областей в изображениях. Идея когерентности областей заключается в малом изменении цвета и структуры на небольшом участке изображения. Алгоритм JPEG имеет в своей основе дискретное косинусное преобразование (ДКП), которое применяется к неперекрывающимся блокам изображения размером 8х8 пикселей. К основным недостаткам можно отнести:
распад кодируемого изображения на отдельные блоки по 8х8 пикселей при больших коэффициентах сжатия; появление ложных контуров; плохое описание нестационарного во времени сигнала коэффициентами Фурье-преобразования.
Для преодоления указанных недостатков был предложен новый стандарт сжатия изображений JPEG2000, основу которого составляет вейвлет-преобразование. В этом случае все изображение раскладывается по базисным вейвлет-функциям, локализованным как во временной, так и в частотной областях. Благодаря такому подходу в вейвлет-коэффициентах образуются длинные цепочки идущих подряд нулей, которые эффективно сжимаются энтропийными кодерами.
В этой главе представлена история развития стандартов сжатия видеоданных, используемых в современных видеокомпрессорах. Особенностью последовательности видеоизображений является большая временная избыточность, обусловленная корреляцией соседних кадров, а также пространственная избыточность, содержащаяся в передаваемом изображении и обусловленная корреляцией соседних пикселей изображения. Технология сжатия видео обычно распадается на две части: уменьшение избыточности видеоинформации во временном измерении, и сжатие отдельных изображений.
Процесс устранения временной избыточности называется компенсацией движения (motion compensation). На практике широко используется метод компенсации движения, который компенсирует перемещение прямоугольных областей текущего кадра. При этом для каждого фиксированного блока, состоящего из M*N пикселей обрабатываемого кадра, выполняется следующая процедура:
1. Поиск на ссылочном кадре, предыдущем или следующем, ранее закодированном и переданном декодеру, подходящего блока из M*N пикселей.
Это делается путем сравнения фиксированного M*N -блока с некоторыми или со всеми блоками M*N области поиска. Область поиска обычно представляет собой некий регион с центром в середине этого выбранного блока. Популярным критерием схожести блоков является энергия остатка, получаемая вычитанием блока-кандидата из фиксированного M*N блока, то есть выбирается блоккандидат, минимизирующий энергию остатка. Этот процесс поиска подходящего блока называется оценкой движения.
2. Выбранный кандидат становится прогнозом текущего M*N -блока, и его необходимо вычитать из этого блока для получения остаточного M*N -блока.
3. Остаточный блок кодируется и передается декодеру, и декодер получает координаты вектора смещения текущего блока по отношению к позиции блокакандидата - вектора движения. Декодер использует вектор движения для нахождения блока-прогноза, декодирует остаточный блок, и складывает его прогнозом для реконструкции версии исходного блока.
Эффективность компенсации движения полностью зависит от алгоритма нахождения вектора движения.
Во второй главе описаны нейросетевые алгоритмы для решения задачи сжатия статического изображения.
На рис.1 приведена блок-схема двухслойной нейронной сети, составляющей основу рассматриваемых алгоритмов сжатия изображений. Первый слой сети состоит из n1 нейронов, каждый нейрон содержит n (n>n1) входов с весовыми (коэффициентами w(1) {wip)} p 1,2,...,n1 - номер нейрона первого слоя,, где p i 1,2,..., n - номер весового коэффициента нейрона этого слоя. Второй слой сети состоит из n нейронов, каждый нейрон содержит n1 входов с весовыми (2) p 1,2,..., n - номер нейрона второго слоя, коэффициентами w(2) {wip }, где p i 1,2,...,n1 - номер весового коэффициента нейрона этого слоя. Параметры n и nопределяются размером обрабатываемых фрагментов изображения и требуемым коэффициентом сжатия.
Рис.1. Блок-схема двухслойной нейронной сети, используемой при сжатии изображений При кодировании изображение A(x, y) представляется в виде совокупности fd (x, y) непересекающихся фрагментов (блоков) размером n bb, NxNy d 1,2,..., - номер фрагмента. Нейронная сеть обрабатывает каждый bfd (x, y) fd (x, y) фрагмент, для этого на основе отсчетов формируется (0) ( (x(0) (x1d, x20),..., xnd) ) реализация длительностью n b2, поступающая на вход d d сети.
fd (x, y) Роль кодера выполняет первый слой сети, для каждого фрагмента ( ( (x(1) (x11), x21),..., xnd) ) вычисляется n1 коэффициентов кодирования d d d n (1) ( x(1) xid0) p 1,2,...,npd wip, (1) iA(x, y) Результатом сжатия изображения является множество квантованных {x(1)} коэффициентов, к которым можно применить энтропийное кодирование.
d Роль декодера выполняет второй слой сети - на основе x(1) восстанавливается d ~ (~ xpd) fd (x, y) фрагмент, отсчеты которого вычисляются с использованием соотношения n(0 (2) (1) ~ xpd) xid, p 1,2,..., n (2) wip in Коэффициент сжатия можно определить соотношением n nАлгоритм сжатия с использованием многослойных нейронных сетей основан на преобразовании Карунена-Лоэва. Это преобразование разбивает корреляцию входных образцов пикселей. Но корреляции пикселей в блоках изображения обычно сильно отличаются, поэтому эффективность предложенного нейросетевого алгоритма невысокая. Разработан адаптивный алгоритм для улучшения эффективности алгоритма с использованием многослойных нейронных сетей. Исходя из характера статических изображений, когда элементы в одном блоке обычно похожи друг на друга, и они сильно отличаются только в случае, когда этот блок содержит границы каких-то объектов; возникает идея классификации блоков по сложности содержания.
То, как блоки полученные от исходного изображения будут классифицированы, зависит от их сложности, которая оценивается по определенному критерию. С этой точки зрения для оценки сложности блока bxb выбирается формула (3).
b b 1 Сложность Ai, Aim, jn, i,j: четны (3) j i2 j2 m1n1 Т.к. значения пикселей между объектами, или между объектом и фоном обычно сильно отличаются, то по критерию сложности, сложность блоков, содержащих границы объектов, будет выше чем сложность других блоков.
После классификации, блоки изображений сжимаются разными нейронными сетями с разными числами нейронов скрытого слоя.
Результаты экспериментов на рис. 2 показывают, что при использовании адаптивного алгоритма значения PSNR выше, чем при использовании обычного нейросетевого алгоритма с примерно одинаковым коэффициентом сжатия.
Рис.2. Сравнение значения PSNR адаптивного и обычного нейросетевых алгоритмов с примерно одиноковым коэффициентом сжатия Рассмотрены также другие нейросетевые алгоритмы сжатия изображения:
алгоритмы на основе самоорганизующейся карты Кохонена. Суть алгоритма сжатия сетью Кохонена на этапе кодирования изображений заключается в сопоставлении фрагментам изображения x(i) таблицы кодирования, тождественной таблице меток для центров результирующих кластеров. При этом x(i) полное множество непересекающихся фрагментов составляет исходное изображение. В результате кодирования совокупности фрагментов {x(i)} сопоставляется последовательность номеров кластеров из кодовой таблицы.
Сеть Кохонена самообучается, используя информации входных векторов, и группирует схожие входные векторы в одну группу. Обычно, изображение сжимается сетью Кохонена следующим образом: входной вектор, подаваемый на входной слой НС - ретину, соответствует блоку изображения, а элементы вектора - пикселям этого блока. Первый входной слой НС не содержит нейронов, он выполняет коммутационные функции, распространяя каждый входной вектор по всем нейронам второго слоя. Число узлов входного слоя равно числу элементов/пикселей входного вектора. Каждый нейрон второго слоя (слой Кохонена) имеет обучаемые весовые коэффициенты своих входов, число входов соответствует числу узлов первого слоя. Внутри второго слоя все нейроны дополнительно могут быть связаны друг с другом латеральными стимулирующими и тормозящими связями. Слой Кохонена классифицирует входные векторы в группы схожих. Предполагается, что входные векторы фактически группируются в классы в соответствии с их положением в векторном пространстве. В своей простейшей форме слой Кохонена функционирует в стиле Упобедитель забирает всеФ. Побеждает в соревновании нейрон, вектор весовых коэффициентов которого окажется наиболее близким к входному вектору.
Коэффициент сжатия данного алгоритма зависит от числа нейронов М у слоя Кохонена и размерности k входного вектора. Для восстановления входного вектора Х=(x1,x2,x3,Еxk) необходимо сохранить позицию победительного нейрона.
Требуется m = log2(M) битов для сохранения одной из М позиций. Поэтому коэффициент сжатия изображения с помощью нейронной сети Кохонена равен:
k Ксж Kkohonen Kentropy Kentropy (4) m Где: Кkohonen - коэффициент сжатия сети Кохонена;
Кentropy - коэффициент сжатия информации от выходов сети Кохонена энтропийным алгоритмом;
В эксперименте были обучены сети Кохонена с размером 16х16, 32х32, 64х64 для сжатия изображения. Размерность входного вектора была выбрана k = 4х4 = 16. Коэффициенты сжатия сети Кохонена Кkohonen при использовании сети с размером 16х16, 32х32 и 64х64 равны 16, 12.8, 10.67. В эксперименте был использован алгоритм Хаффмана для сжатия информации о позиции нейронов победителей. Результаты экспериментов показаны, что коэффициент сжатия КEntropy (1.6 - 2.2) энтропийным алгоритмом. Следовательно, по формуле (4) общий коэффициент сжатия при использовании сети Кохонена с размером 16х16, К16х6х (25 - 35) К32х2х (20.5 - 28) 32х32 и 64х64 могут достичь значений,, сж сж К64х4х (17 - 23).
сж На рис.3 показаны значения PSNR при сжатии изображений с размером 512х512 сетями Кохонена размерами 16х16, 32х32 и 64х64.
Рис.3. Значение PSNR при сжатии изображения 512x512 px нейронными сетями с разными размерами слоя Кохонена На рис.4 показаны значения PSNR при сжатии разных изображений сетью Кохонена 64х64 и алгоритмом JPEG с коэффициентом сжатия Ксж = 22. На рис.показаны изображения после декодирования. Из результатов сравнения следует, что при высоком коэффициенте сжатия, алгоритм с использованием сети Кохонена дает декодированные изображения лучше по качеству, чем алгоритм JPEG.
Рис.4. Сравнение PSNR при использовании нейронного алгоритма и алгоритма JPEG при высоком коэффициенте Ксж~22.
(a) (b) Рис. 5. Изображения после декодирования при высоком коэффициенте Ксж~22 (а) алгоритм с использованием сети Кохонена; (b) алгоритм JPEG.
Для улучшения алгоритма сжатия сетью Кохонена, разработан новый поход к обучению сети Кохонена в задаче сжатия изображений: обучать сеть не по значениям пикселей изображения, а по значениям их коэффициентов вейвлетного преобразования. Этот подход возникает из характеристики разбиения корреляции между соседними пикселями вейвлетного преобразования.
Для получения коэффициентов вейвлетного преобразования, сначала все изображение делится на части одинакового размера, над каждой из которых независимо от других и будут происходить дальнейшие преобразования. Далее каждый канал проходит фильтрацию низкочастотным и высокочастотным фильтрами отдельно по строкам и по рядам, в результате чего после первого прохода в каждой части формируются четыре более мелких изображения. Все они несут информацию об исходном изображении, но их информативность сильно отличается. Для сжатия этих коэффициентов, используем такую же структуру, как в алгоритме с использованием обычной нейронной сети, только входные значения сейчас не пиксели изображения, а коэффициенты, получающиеся по вейвлетному преобразованию. Для процесса обратного преобразования, по точности восстановленных изображений, чем больше коэффициенты, тем более важную роль они играют. Поэтому, используются разные сети Кохонена с разными размерами входов (т.е. разные коэффициенты сжатия при фиксированных размерах слоя Кохонена 16х16) для разных каналов коэффициентов. Чем меньше значения коэффициентов канала, тем больше коэффициент сжатия. Чем выше степень, тем меньше коэффициенты разложения.
Для 3-степени, используем сеть Кохонена с входным вектором размера 4=2x2;
для 2-степени - сеть Кохонена с входным вектором размера 16=4x4; и для 1степени - сеть Кохонена с входным вектором размера 64=8x8. При использовании сети Кохонена, выходом будет только позиция победительного нейрона, поэтому для каждого входного вектора с размером Р (байт), необходимо сохранить только 1 байт при кодировании. Заметим что, у 3-степени есть 4 части (НН3, НВ3, ВН3, ВВ3) с размером 64х64, у 2-степени - 3 части с размером 128х128, у 1-степени - части с размером 256х256. Таким образом, коэффициент сжатия получается:
Вход(байт) 5125КKohonen 1 1 Выход(байт) 4 64 64 3128128 3 256 256 4 16 1 1 3 4 316 (5) 16 25, Таблица 1: PSNR сжатия монохромных изображений при Кkohonen =25,разными алгоритмами Стандартная Предложенный Изображение сеть Кохонена алгоритм Lena 22,6785 28,57Camera man 21,7325 27,19Woman 21,2954 27,02Pepper 21,6115 27,53В таблице 1. показаны результаты PSNR сжатия разных изображений данным алгоритмом и стандартной сетью Кохонена при коэффициенте сжатия Кkohonen = 25,6. Значения PSNR предложенного алгоритма при сжатии всех изображений выше, чем значения PSNR стандартного алгоритма с использованием сети Кохонена.
В третьей главе рассматриваются существующие алгоритмы поиска векторов движения.
Формально задача поиска векторов движения представляет собой задачу минимизации оценочной функции. В практике, наиболее распространённой оценочной функцией является сумма абсолютных разниц SAD, которая используется при компенсации движения, рассчитанная для блока размером NxM с координатами (х,у), t1-го кадра::
N 1 M SAD (Vx,Vy ) F (x m, y n, t1 ) F (x Vx m, y V n, t2 ), (6) y n0 m Где: SAD - сумма абсолютных разниц (Sum of Absolute Differences), F - значение яркости, t1 - временной индекс текущего кадра, t2 - временной индекс опорного кадра, (Vx, Vy): вектор движения.
Приведены описания следующих алгоритмов поиска векторов движения:
алгоритма полного перебора (FS), алгоритма трехшагового поиска (TSS), алгоритма нового трехшагового поиска (NTTS), алгоритма простого и эффективного поиска (SES), алгоритма четырехшагового поиска(4SS), алгоритма поиска по алмазу (DS), алгоритма поиска по адаптивному шаблону (ARPS).
Разработан новый алгоритм с использованием метода векторного квантования с помощью сети Кохонена. Применяя алгоритм векторного квантования с использованием сети Кохонена, строится набор кандидатов векторов движения, которые часто встречаются в задаче компенсации движения.
Тестовые Векторы Кодовая книга видео движения Алгоритм полного Нейронные сети (векторы перебора Кохонена движения) Рис. 6. Схема построения множества кандидатов векторов движения сетью Кохонена На рис.6 показана схема построения множества векторов движения с помощью нейронной сети. Сначала строятся вектора движения алгоритмом полного перебора для тестированных видеопоследовательностей. Для построения такого множества используются видеопоследовательности по разным тематикам.
Затем обучается нейронная сеть Кохонена этими векторами движения, чтобы получить кодовую книгу. Размер слоя Кохонена зависит от размера области поиска. Например, для макроблока 8х8 с расширением области поиска до +пикселей, т.е. с размером 15х15 пикселей, выбирается слой Кохонена с размером 8х8, т.е. 64 выхода соответствуют 64 кандидатам вектора движения.
Множество кандидатов векторов движения строится сетью Кохонена на основе общего характера движения, не смотря на характер самой видеопоследовательности. Чтобы улучшить эффективность алгоритма, к множеству кандидатов для каждого блока добавляются отдельно векторы движения окрестности +1 пиксели соседних блоков предыдущего кадра.
Основная идея состоит в том, что поле векторов является достаточно гладким как в пространстве, так и во времени, за исключением разрывов, возникающих на границах объектов, движущихся не одинаково, и ситуации смены общего плана.
Схема алгоритма показана на рис.7. Кандидаты векторов движения, полностью построены по предложенному алгоритму, определены до процесса поиска каждого кадра, что дает высокую возможность параллелизма при аппаратном ускорении.
Рис.7. Схема построения кандидатов векторов движения Средние значения функции 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.03SES 26.5733 26.8268 27.4864 27.8223 22.144SS 27.4084 27.9266 28.6184 28.1268 22.6DS 27.3939 27.8933 28.8855 28.3035 22.63ADPS 27.7211 28.7142 29.6335 28.2216 23.16NTSS 27.7221 28.5951 28.8089 28.3928 23.10Neural 28.0573 28.9889 30.2419 28.4975 23.3FS 28.362 29.2982 30.4542 28.6367 23.64Рис.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) блоков нитей (потоков), а каждый блок включает в себя 16х2 нитей. Поэтому 16 нитей одной строки блока вычисляют разницы между координатами входа и веса одного нейрона. Эти значений потом суммируются алгоритмом параллельной редукции чтобы сократить время работы. Пример схемы суммирования множества чисел показан на рис.9. С использованием этого алгоритма количество вычислений суммы уменьшиться в 16/log216 = 4 раза. Результаты вычисления расстояний между входом и нейронами сохраняются в глобальной памяти для нахождения нейрона победителя.
Рис.9. Схема суммирования по алгоритму параллельной редукции Процесс нахождения нейрона победителя реализуется параллельно во втором ядре. Требуется найти минимальное значение среди всех расстояний, получившихся в первом ядре. Для распараллеливания этого ядра применяется стандартный прием разделяй и властвуй. Для начала весь массив расстояний между входом и нейронами разбивается на части и каждой такой части ставится в соответствие один блок сетки, который и будет считать минимум всех элементов данной части массива. Хотя блоки удобно использовать одномерные, но для больших массивов может понадобиться использование двухмерной сетки, поскольку в CUDA существует ограничение на размер сетки по любому измерению, равный 65535.
Итак, каждый блок отвечает за нахождение минимума всех соответствующих ему элементов массива. Таким образом, исходная задача разбивается на набор независимо решаемых подзадач - нахождение минимума для отдельных частей массива. Для распараллеливания данной операции на отдельные нити вновь применяется принцип разделяй и властвуй - соответствующие блоку элементы массива разбиваются на пары и элементы каждой пары параллельно сравниваются между собой.
В результате получается вдвое меньше элементов, которые нужно сравнить.
Они опять разбиваются на пары и параллельно сравниваются элементы каждой пары. Далее подобный процесс повторяется снова. После каждого повторения число элементов будет уменьшаться вдвое, и при блоке в Elem элементов понадобится log2 Elem шагов для получения требуемого минимума. Например, для сети Кохонена с размером 32х32, надо log2(32х32) = 10 шагов вместо 1024, а для сети с размером 64х64 надо log2 (64х64) = 12 шагов вместо 4096 шагов на CPU. Данный процесс (для примера нарисован процесс только для 16 элементов) показан на рис.10.
Рис.10. Процесс нахождения минимального расстояния в ядре После обнаружения нейрона победителя для данного входа, веса победителя и его соседей обновляются. Так как веса нейронов друг от друга не зависят, то параллельный процесс обновления весов реализуется легко. На сетке вычислений CUDA реализуются height х width блоков, каждый из которых содержит 16 нитей для обновления 16 значений весов одного нейрона по формуле корректирования весов нейронов. В итоге графические процессоры позволяют вычислять формулу корректирования весов параллельно 16х height х width раз.
В эксперименте были использованы 20000 блоков с размером 4х4 пикселей из разных черно-белых изображений для обучения сети. На рис.11 показано отношение времени обучения сети Кохонена с разными размерами слоя Кохонена после 500*20000 = 10000000 шагов на CPU и на CUDA.
Результаты экспериментов показывают, что время обучения сети на CPU значительно больше, чем на GPU. Чем больше размер сети Кохонена, тем выше отношение времени обучения двух процессов.
Рис.11. Отношение времени обучения сети Кохонена на CPU и на CUDA При увеличении размера сети Кохонена от 16х16 до 64х64 нейронов, время обучения сети на CPU от 4 до 30 раз больше чем на CUDA. Это объясняется тем, что чем больше размер сети, тем больше число операций на каждом шаге обучения, т.е. тем большее число операций можно параллельно вычислять и следовательно эффективнее процесс распараллеливания.
В процессе обучения можно было распараллеливать процесс нахождения нейрона победителя только одного входа, а не нескольких входов, т.к. после нахождения победителя необходимо обновляться все веса. Однако, для реализации обучаемой сети на CUDA, можно распараллеливать процессы нахождения нейрона победителя сразу всех входов, т.к. эти процессы не зависят друг от друга.
В реализации используется два уровня параллелизма:
1) Первый уровень параллелизма используется на уровне входов сети.
Изображение разбивается на блоки с размером 4х4, и каждый блок является входом сети Кохонена как показано выше. Поскольку взаимозависимости между блоками не существует, все блоки могут быть сжаты параллельно. В архитектуре CUDA, один блок в сетке блоков (grid) используется для нахождения нейрона победителя для одного блока изображения. Данные о позиции этого нейрона представляются как сжатая информация данного блока изображения.
2) Второй уровень параллелизма - это распараллеливание процесса нахождения нейрона победителя. Для этого следует параллельно вычислять расстояния между входом и всеми нейронами, и результаты сравнивать между собой, чтобы получить самое маленькое значение. В идеале, расстояние каждого нейрона до входа вычислялись бы в отдельной нити и все выходы нейронов сразу бы параллельно вычислялись. Но из-за органичности количества нитей в одном блоке (в каждом блоке невозможно более 512 нитей) для сети с большим размером слоя Кохонена, в одной нити должны вычисляться расстояния несколько нейронов. В реализации выбран размер блока нитей равным 16х16 и каждая нить вычисляет расстояния нескольких нейронов, в зависимости от размера сети Кохонена. Например, если используется сеть Кохонена с размером 32х32 нейронов для сжатия статических изображения, то в каждой нити должны вычисляться расстояния (32х32) / (16х16) = 4 нейронов; если размер сети равен 64х64, то (64х64)/(16х16) = 16 нейронов. Результаты вычисления сохраняются в разделяемой памяти для сравнения.
На рисунке 12 показано время в секундах на сжатие изображения с помощью разных сетей Кохонена (размер сети меняется от 16х16 до 64х64 нейронов) на CPU и на GPU.
(а) (b) Рис.12. Время (в секундах) на сжатие изображения сетями Кохонена на CPU и на GPU для изображения c размером 256х256 пикселей (а) и 512х512 пикселей (b) Результаты показывают, что с помощью технологии 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. В этом эксперименте размер макроблока был 8х8, и область поиска 15х15 пикселей.
Результаты реализации алгоритмов на CUDA показывают, что значения PSNR предложенного алгоритма близки к значениям PSNR алгоритма полного перебора, и значительно выше значений PSNR алгоритма NTSS. Время работы предложенного алгоритма на CUDA почти в 3 раза меньше, чем алгоритма полного перебора. Этот результат объясняется тем, что число вычислений функции SAD в предложенном алгоритме меньше в 3 раза, чем в алгоритме полного перебора, однако, хотя число вычислений функции SAD в алгоритме NTSS меньше, чем в алгоритме с использованием нейронной сети, но позиции кандидата вектора движения не определены заранее, и зависят от предыдущих кандидатов, то есть влияет на параллелизм работы и задерживает работу алгоритма. Результаты на рис.15 показывают также, что время выполнения на CUDA гораздо меньше (в тысячи раз) чем на CPU.
Рис.14: (a) Среднее значение PSNR (в дБ) (b) Время нахождения векторов движения (в миллисекундах) 200 кадров разных видеопоследовательностей Рис.4.15: Время нахождения векторов движения 200 кадров разных видеопоследовательностей нейронным алгоритмом на CUDA и на CPU.
В заключении перечислены основные результаты, полученные в диссертационной работе.
1. Проведен анализ эффективности основных нейросетевых алгоритмов сжатия изображений. По результатам экспериментов был сделан вывод о том, что в случаях, когда требуется большой высокий коэффициент сжатия, качество сжатых изображений при использовании нейронных сетей больше, чем при использовании самого популярного алгоритма JPEG.
2. Предложен новый нейросетевой алгоритм для сжатия изображений на основе самоорганизующейся карты Кохонена в преобразованном пространстве.
Значение PSNR предложенного алгоритма выше, чем PSNR обычного алгоритма Кохонена, однако, при этом сложность алгоритма увеличивается.
3. Предложен алгоритм поиска векторов движения, отличающийся от известных использованием нового нейросетевого подхода построения набора кандидатов вектора движения. Проведен сравнительный анализ эффективности предложенного алгоритма и известных алгоритмов поиска векторов движения, для сжатия видеоданных. По результатам экспериментов был сделан вывод о том, что предложенный алгоритм продемонстрировал лучшие результаты PSNR и дал высокую возможность параллелизма при аппаратном ускорении, например на графических процессорах NVIDIA.
4. Предложен алгоритм распараллеливания процесса обучения и эксплуатации сети Кохонена на графических процессорах NVIDIA. Реализация процесса обучения сети Кохонена на CUDA позволяет увеличить скорость процесса в 8-30 раз, при изменении размера Кохонена от 16х16 до 64х64. Сжатие изображения нейронной сетью Кохонена на GPU превосходит по скорости CPU от десяти до сотни раз, в зависимости от размера исходного изображения.
5. Разработан подход к реализации на графических процессорах NVIDIA алгоритмов поиска вектора движения: предложенного алгоритма, алгоритма полного перебора и нового трехшагового алгоритма. Результаты экспериментов показывают, что время работы предложенного алгоритма на CUDA почти в 3 раза меньше, чем алгоритма полного перебора и меньше, чем алгоритма NTSS на 1015%. Результаты показывают также, что время выполнения работы на CUDA гораздо меньше (в тысячи раз) чем на CPU.
В приложениях к диссертационной работе представлен список используемых обозначений и сокращений, исходные коды реализации алгоритмов в среде Matlab и коды реализации алгоритмов на CUDA.
Публикации по основным результатам диссертации:
1. Аляутдинов М.А., Коробкова С.В., Нгуен Виет Хунг. Оптимальные пакеты программ обработки изображений для вычислительных систем на базе процессоров NVIDIA // Тезис докладов научно-практической конференции Вычисления с использованием графических процессоров в молекулярной биологии и биоинформатике - Москва 2010. - С. 22 - 23.
2. Нгуен Виет Хунг. Сжатие изображения с использованием нейронной сети в преобразованном пространстве. // Тезис докладов IX всероссийской конференции Нейрокомпьютеры и их применение. Москва - 2011 - С.3. Нгуен Виет Хунг. Применение нейронных сетей для нахождения вектора движения в задаче кодирования видеопоследовательности со стандартом H.264/AVC// Труды 54-й научной конференции МФТИ Проблемы фундаментальных и прикладных естественных и технических наук в современном информационном обществе - Долгопрудный - 2011. - С. 40 - 41.
4. Нгуен Виет Хунг. Нейросетевой алгоритм для решения задачи компенсации движения в видеопоследовательностях со стандартом H264/AVC// Журнал Информатизация и Связь. Ц№6, 2005. - С. 77 - 80.
5. Нгуен Виет Хунг. Сжатие изображения с использованием нейронной сети в преобразованном пространстве// Журнал Нейросетевые технологии в журнале Информационные технологии №1, 2012 - Стр. 76 - 6. Нгуен Виет Хунг. Применение нейросетевых методов слияния данных в задаче экстраполяции функций с аппаратной поддержкой вычислений // XIV всероссийская научно-техническая конференция Нейроинформатика-2012, Сборник научных трудов, часть 2 - 2012 - С.82-91.
7. Нгуен Виет Хунг, Муравьев А.В. Реализация нейросетевого алгоритма компенсации движения в видео кодировании с использованием технологии NVIDIA CUDA // Тезис докладов X всероссийской конференции Нейрокомпьютеры и их применение. Москва - 2012 - С.39.
8. Нгуен Виет Хунг. Сжатие изображения с использованием сети Кохонена при помощи технологии NVIDIA CUDA // Тезис докладов X всероссийской конференции Нейрокомпьютеры и их применение. Москва - 2012 - С.40.
9. Нгуен Виет Хунг, Муравьев А.В. Применение нейросетевого алгоритма в задаче компенсации движения в видео кодировании при помощи технологии NVIDIA CUDA // Журнал Нейросетевые технологии в журнале Информационные технологии №5, 2012 - Стр. 74 - 78.
Авторефераты по всем темам >>
Авторефераты по техническим специальностям