Содержание к диссертации
Введение
Глава 1. Анализ основных подходов к сжатию статических и динамических изображений 13
1.1. Понятия и термины 13
1.1.1. Математическая модель непрерывного изображения 13
1.1.2. Вероятностное описание непрерывных изображений 14
1.1.3. Дискретные и цифровые изображения 16
1.2. Основные идеи методов сжатия изображений 18
1.3. Устранение временной избыточности 19
1.3.1. Блочная компенсация движения 21
1.3.2. Компенсация в области вейвлет-преобразования 24
1.3.3. Глобальная компенсация движения 25
1.4. Устранение пространственной избыточности 29
1.4.1. Кодирование с предсказанием 29
1.4.2. Преобразование изображений 29
1.5. Квантование 36
1.6. Статистическое кодирование 38
1.6.1. Коды переменной длины 38
1.6.2. Арифметическое кодирование 39
1.7. Оценка качества восстановленных изображений 40
1.8. Постановка задачи диссертационного исследования 42
Глава 2. Сжатие изображений на основе контекстного кодирования коэффициентов ДКП 44
2.1. Классическая схема JPEG 44
2.2. Принцип контекстного кодирования 47
2.2.1. Понятие контекста 47
2.2.2. Использование контекста для кодирования символов 47
2.3. Корреляция между коэффициентами ДКП 48
2.4. Построение контекстного прогноза 51
2.5. Алгоритм контекстного кодирования коэффициентов ДКП 53
2.5.1. Выбор модели позначенню контекстного прогноза 53
2.5.2. Кодирование блока ДКП 54
2.6. Анализ эффективности алгоритма сжатия 57
2.7. Выводы 62
Глава 3. Глобальная и локальная компенсация движения 63
3.1. Глобальная компенсация движения на основе векторов перемещения характерных блоков 64
3.1.1. Алгоритм определения сдвига изображения 65
3.1.2. Результаты моделирования алгоритма 66
3.2. Трехслойная схема компенсации движения 71
3.2.1. Модифицированная трехслойная схема 74
3.3. Выводы 75
Глава 4. Алгоритм видеокомпрессии на основе ДВП и блочной компенсации движения для видеосистемы МРК 77
4.1. Использование ДВП для сжатия данных 78
4.2. Алгоритм сжатия динамических изображений 82
4.2.1. Общая схема кодирования 82
4.2.2. Преобразование цветового пространства 83
4.2.3. Компенсация движения и построение прогнозного кадра 83
4.2.4. Кодирование векторов движения 88
4.2.5. Обработка разностного изображения 90
4.3. Некоторые аспекты реализации алгоритма видеокодирования на
вычислительных элементах, используемых в телевизионной системе МРК 93
4.3.1. Эффективная реализация видеокодера на основе ЦСП 93
4.3.2. Распараллеливание основных этапов сжатия 96
4.4. Выводы 99
Глава 5. Компьютерное моделирование и экспериментальное исследование характеристик разработанного алгоритма видеокомпрессии 101
5.1. Формирование выходного битового потока 102
5.2. Оптимизация вычислений 103
5.2.1. Компенсация движения 103
5.2.2. Использование лифтинг-схемы для вычисления ДВП 104
5.2.3. Оптимизация алгоритма SPIHT 105
5.3. Результаты кодирования тестовых видеопоследовательностей 106
5.4. Выводы 116
Заключение 117
Литература
- Математическая модель непрерывного изображения
- Использование контекста для кодирования символов
- Алгоритм определения сдвига изображения
- Алгоритм сжатия динамических изображений
Введение к работе
Перспективным направлением автоматизации в различных областях человеческой деятельности, включая транспортную, промышленную и военную отрасли, является создание мобильных робототехнических комплексов (МРК). Существенным преиму: ществом МРК является их способность функционировать в экстремальных и опасных для жизни человека условиях: они позволяют без риска для человека перевозить радиоактивные и другие вредные вещества, контролировать обстановку в районах экологических катастроф, проводить аварийно-спасательные работы в атомной энергетике, химической, нефтегазовой и горнодобывающих отраслях, операции по борьбе с терроризмом и действия в условиях военных конфликтов.
Ряд программ, проводимых в США, Западной Европе, Израиле, Японии и России, направлен на разработку и внедрение в промышленных масштабах комплексов, которые дистанционно управляются человеком, находящимся на командном пункте и получающим видеоинформацию от бортовых источников МРК по радиоканалам телекодовой связи. Среди российских разработок в этой области можно отметить следующие комплексы [1]:
РТК РД — робототехнический комплекс разведки и дезактивации, предназначенный для проведения первоочередных работ при ликвидации последствий радиационных аварий и включающий мобильное транспортное средство с манипулятором, телевизионное и осветительное оборудование, а также передвижной пункт управления;
КРТ-100М—- робототехнический комплекс, предназначенный для проведения работ при ликвидации последствий аварий преимущественно на открытых площадках и крышах атомных электростанций (АЭС), предприятий ядерного топливного цикла. Мобильный аппарат КРТ-100М снабжен отвалом, осветительным и телевизионным оборудованием, состоящим из двух обзорных полноповоротных видеокамер;
МРК-27МА.00 — робототехнический комплекс для ликвидации последствий аварий преимущественно в помещениях, с помощью которого можно перемещать предметы и проводить осмотр пространства в аварийной зоне. Подвижный аппарат оснащен тремя телевизионными камерами.
Другим видом дистанционно управляемых комплексов являются беспилотные летательные аппараты (БПЛА), активно используемые для оперативного получения разведывательных данных (в том числе в зоне конфликта), а также точечного уничтожения наземных целей. Из современных российских разработок можно отметить БПЛА ZALA 421-06 и ZALA 421-12 компании «Беспилотные системы» [28]. ZALA 421-06— это БПЛА вертолетного типа, позволяющий проводить разведывательные операции в труднодоступных и опасных для человека местах. Его основными преимуществами являются вертикальный взлет и возможность зависания над объектом. БПЛА ZALA 421-12 с увеличенной продолжительностью полета был разработан для решения задач пограничных подразделений. На его борту размещена стабилизированная в двух осях цветная видеокамера с обзором любой точки нижней полусферы.
Дистанционное управление МРК осуществляется с помощью человеко-машинного интерфейса на основе визуальной информации, поступающей от собственной телевизионной системы подвижного аппарата или установленного навесного оборудования. Получаемая видеоинформация используется как для оценки окружающей обстановки, навигации и формирования управляющих команд оператором, так и для автоматической интерпретации видеоданных, полученных от телевизионных камер, с последующей идентификацией или классификацией объектов, наблюдаемых в контролируемом пространстве. Освобождение оператора от выполнения рутинных действий существенно повышает эффективность управления, однако при использовании автоматизированного (а не автономного) комплекса остается возможность вмешательства специалиста в экстренных или неоднозначных ситуациях. Этим объясняются повышенные требования, предъявляемые к качеству видеоизображения: система передачи видеоданных должна обеспечивать максимально достоверную и полную визуальную информацию при минимальных вносимых искажениях.
Ограниченная пропускная способность существующих радиоканалов связи не позволяет передавать без компрессии большие потоки видеоданных от камер наблюдения, установленных на борту аппаратно-программных комплексов. Это объясняет необходимость синтеза новых методов обработки и кодирования динамически меняющихся изображений, позволяющих адаптироваться к изменению радиоэлектронной обстановки и объему передаваемой информации.
При проектировании МРК выбор того или иного метода компрессии определяется не только его характеристиками сжатия, но и вычислительной сложностью реализации. Часто останавливаются на простейших алгоритмах видеокодирования, подразумевающих независимую покадровую обработку поступающей видеоинформации. Очевидно, что добиться высокой степени сжатия в этом случае не представляется возможным, однако подобный метод компрессии не требует больших вычислительных ресурсов и обеспечивает надежность передачи видеоданных: ошибка, возникшая при трансляции одного кадра, не влияет на корректность восстановления последующих кадров, что минимизирует задержку, возникающую в процессе декодирования при наличии помех в радиоканале. Примером такого подхода является метод Motion JPEG, в котором каждый кадр сжимается алгоритмом JPEG [72].
Распространенные стандарты видеокодирования, такие как MPEG-2 [73], MPEG-4 [74] и Н.264 [79], позволяют добиться лучшего соотношения качество/сжатие, используя хмеханизм компенсации движения, но построение прогнозных кадров, как правило, занимает более половины процессорного времени, затрачиваемого на обработку текущего кадра. Кроме того, данные алгорітмьі основаны на дискретном косинусном преобразовании (ДКП), что при малых битовых затратах приводит к появлению на восстановленных видеоизображениях характерных блочных искажений, затрудняющих их визуальное восприятие и, следовательно, не позволяющих человеку-оператору адекватно оценить обстановку. Еще одним недостатком является невозможность изменения битовой скорости закодированного потока в режиме реального вреімени.
Специалисты в области прикладной теории передачи данных уделяют повышенное внимание увеличению эффективности существующих методов компрессии, стандарты которых определяют лишь формат битового потока и способ его декодирования, а не сами вычислительные процедуры. Кроме того, активно разрабатываются новые алгоритмы сжатия видеоинформации на базе вейвлет-преобразования: примерами исследований в этом направлении могут служить работы таких ученых как John W. Woods [141-143], Deepak S. Turaga и Mihaela van der Schaar [131—133]. Очевидно, что использование вейвлет-кодирования является перспективным направлениехм и со временем ляжет в основу новых стандартов видеокомпрессии.
Большинство из многочисленных публикаций по теме сжатия видеоданных, однако, либо содержат лишь общее описание методов кодирования, либо в них, наоборот, рассматривается только некоторая часть алгоритма компрессии (например, компенсация межкадрового движения), либо результаты соответствующих исследований на текущий момент не могут быть использованы на практике из-за слишком большой вычислительной сложности.
В связи с вышесказанным крайне актуальными являются как исследования, позволяющие повысить эффективность известных методов компрессии статических и динамических изображений, так и разработка новых алгоритмов кодирования, обладающих невысокой программной и аппаратной сложностью, которые могут быть успешно использованы в различных системах видеонаблюдения.
Способы кодирования, используемые для сжатия видеопотока в реальном времени, отличаются от тех, которые используются для архивного хранения видеоданных. Во-первых, такие алгоритмы должны обеспечивать возможность их реализации с быстродействием, достаточным для обработки видеокадров с нужной частотой. Также желательно, чтобы при необходимости они могли быть легко адаптированы под конкретную архитектуру вычислительного устройства (в том числе многопроцессорного или многоядерного), которое будет использовано в составе программно-аппаратного комплекса. Во-вторых, алгоритм компрессии должен учитывать особенности передачи видеопотока по каналам с переменной и/или ограниченной пропускной способностью, в частности, иметь возможность быстро и гибко регулировать объем генерируемого битового кода.
Другой актуальной задачей обработки данных, поступающих от телевизионной системы МРК, является компенсация перемещения видеодатчика для подавления нежелательного дрожания и последующего анализа видеоинформации на предмет наличия в кадре различных объектов, например, движущихся целей.
Целью диссертационной работы является разработка методов стабилизации и компрессии изображений, ориентированных на применение в системах видеонаблюдения мобильных робототехнических комплексов при различных характеристиках используемых в них вычислительных элементов и каналов передачи данных.
Основные задачи, решение которых требуется для достижения поставленной цели, следующие:
исследование существующих подходов к сжатию динамических и статических изображений на основе различных декоррелирующих преобразований и анализ методов стабилизации видеоизображений;
разработка JPEG-подобного алгоритма контекстного кодирования изображения на основе межблочных статистических связей между коэффициентами ДКП соседних блоков для использования в системах видеонаблюдения с невысокими вычислительными ресурсами;
синтез алгоритма определения сдвига источника видеосигнала на основе блочного ДКП;
разработка метода масштабируемого кодирования векторов перемещения блоков видеокадра;
разработка алгоритма видеокомпрессии на основе иерархического кодирования коэффициентов ДВП и блочной компенсации движения в пространственной области для систем видеонаблюдения МРК, обладающих высокими вычислительными ресурсами;
реализация предложенных методов и их оптимизация, создание программных средств для тестирования, оценка эффективности разработанных алгоритмов с помощью тестовых изображений и видеопоследовательностей;
выработка рекомендаций по практической реализации разработанного видеокодера с использованием мультимедийных цифровых сигнальных процессоров и многопроцессорных элементов.
В процессе работы над диссертацией в качестве методов исследования использовались методы линейной алгебры, теории вероятностей и математической статистики, теории цифровой обработки и кодирования данных. Экспериментальные исследования проводились с помощью численного моделирования на персональном компьютере в средах разработки Microsoft Visual Studio и MATLAB.
Научная новизна диссертации заключается в:
- создании нового метода контекстного кодирования на базе межблочной корреля
ции между модулями коэффициентов ДКП для использования в JPEG-подобной
схеме компрессии, позволяющего повысить характеристики сжатия за счет несущественного повышения вычислительной сложности;
разработке нового алгоритма определения сдвига видеоизображения, основанного на выделении в кадре характерных блоков с помощью анализа коэффициентов ДКП, который обеспечивает высокую точность даже при небольшом числе рассматриваемых блоков;
разработке нового алгоритма видеокомпрессии на базе ДВП, который включает метод трехслойной обработки векторов движения, повышающий эффективность кодирования на низких битовых скоростях.
Практическая значимость результатов, полученных в диссертационной работе, заключается в том, что разработанные алгоритмы стабилизации и компрессии статических и динамических изображений позволяют повысить эффективность обработки видеоданных как в рамках специализированных систем управления МРК, так и в комплексах впдеонаблюдения более широкого профиля.
Алгоритм видеокомпрессии [2] был разработан в рамках научно-исследовательской работы [5-7]. основанием для проведения которой являлся Государственный контракт от 18 мая 2007 г. № 02.514.11.4024, заключенный Роснаукой с МИЭТ — победителем конкурса на право заключения государственных контрактов на выполнение НИР для государственных нужд в рамках ФЦП «Исследования и разработки по приоритетным направлениям развития научно-технологического комплекса России на 2007-2012 годы» (мероприятие 1.4 Программы, II очередь) по лоту 2.2007-4-1.4-00-03 «Кодирование и передача динамически меняющихся изображений».
Разработанные алгоритмы видеокомпрессии внедрены в макетных образцах систем видеонаблюдения в НИИ ВСиСУ МИЭТ.
Апробация работы. Основные результаты диссертационной работы докладывались и обсуждались на 11-й, 12-й, 13-й и 14-й Всероссийских межвузовских научно-технических конференциях студентов и аспирантов «Микроэлектроника и информатика» (Москва, МИЭТ, 2004, 2005, 2006 и 2007 гг.), а также на 4-й Российско-Баварской конференции по биомедицинской инженерии (Москва, МИЭТ, 2008 г.).
Публикации. По теме диссертации опубликовано девять работ [2, 5-8, 16-20, 41-43, 134] (среди них три статьи в ведущих рецензируемых журналах [2, 20, 43] и одна
статья в трудах международной конференции [134]); результаты исследований отражены также в пяти отчетах о НИР [5—7, 41, 42]. Основные положення, выносимые на защиту:
алгоритм сжатия изображений на основе контекстного кодирования коэффициентов ДКП с учетом межблочной корреляции, использующий многомодельный арифметический кодер;
алгоритм глобальной компенсации движения, использующий векторы перемещения характерных блоков, выбор которых производится на основе анализа коэффициентов ДКП;
метод трехслойного кодирования векторов движения, позволяющий повысить эффективность кодирования при низких битовых скоростях;
алгоритм компрессии видеоизображений на основе двумерного ДВП и блочной компенсации с перекрытием, предназначенный для использования в составе МРК. Структура диссертации. Первая глава диссертации является вводной. В ней
приведены основные понятия теории обработки цифровых сигналов, в частности, статических и динамических изображений. Рассмотрены различные методы устранения пространственной и временной избыточности, применяемые в алгоритмах кодирования видеоданных. Проанализированы недостатки существующих подходов.
Во второй главе детально рассмотрен предлагаемый алгоритм компрессии изображений, основанный на построении контекстного прогноза для модулей коэффициентов ДКП и использовании многомодельного арифметического кодера. Приведены результаты тестирования алгоритма, подтверждающие, что предложенный подход позволяет повысить качество сжатия изображений в JPEG-подобной схеме компрессии.
Третья глава посвящена методам глобальной и локальной компенсации движения. В первой ее части приводится описание разработанного алгоритма определения сдвига видеоисточника, суть которого заключается в использовании векторов движения части блоков, отобранных с помощью критерия, базирующегося на значениях коэффициентов ДКП. Дано экспериментальное обоснование эффективности предложенного метода.
Во второй части третьей главы рассмотрена трехслойная схема кодирования векторов перемещения и ее модификация, предназначенные для использования в рамках видеокодеров с блочной компенсацией движения.
В четвертой главе описан предложенный метод сжатия видеоданных, основанный на блочной компенсации движения с перекрытием, трехслойной схеме кодирования векторов перемещения, рассмотренной в третьей главе, а также алгоритме сжатия статических изображений путем разделения множества коэффициентов по иерархическим деревьям в области дискретного вейвлет-преобразования. Рассматриваются аспекты практического использования предложенного алгоритма видеокодирования в рамках системы видеонаблюдения МРК, в частности, анализируются возможности эффективной реализации алгоритма на основе современных цифровых сигнальных процессоров, а также распараллеливания основных вычислительных процедур.
В пятой главе обсуждаются полученные результаты экспериментального исследования характеристик разработанного алгоритма видеокомпрессии с трехслойной схемой кодирования векторов движения.
В заключении сформулированы основные результаты, полученные в ходе выполнения диссертационной работы; обозначены перспективы и направления дальнейших исследований.
В приложениях приведены стандартные тестовые изображения и кадры из видеопоследовательностей, которые были использованы при проведении экспериментальных исследований, описание алгоритма SPIHT [118], а также копия акта о внедрении результатов диссертационной работы.
Математическая модель непрерывного изображения
Часто бывает удобно рассматривать изображение как реализацию случайного процесса. Рассмотрим порождающую изображение непрерывную случайную функцию F(x,y,i) трех переменных— пространственных координат (х,у) и времени t. Случайный процесс F{x,y,t) может быть полностью описан совместной плотностью вероятности [31] p{Fl,F2,...,FJ;xl)yl,t],x2y2,t2,...,xJyj,tj}, для значений функций F{x ,yj,tj) в точках с координатами \Xj,yj) и временем tj, У = 1,...,./. Как правило, совместные плотности вероятности высокого порядка для изображений неизвестны, и в общем случае их трудно моделировать. Для плотности вероятности первого порядка p{F\x,y,t) иногда удается подобрать удачную модель из физических соображений или на основе измеренных гистограмм. Например, плотность вероятности первого порядка случайного шума в электронных преобразователях изображений хорошо моделируется гауссовой плотностью: p{F\x,y,t}= [27raF (х, y,i)\ ехр [F(x,y,t)-mF(x,y,t)f 2aj(x,y,t) где параметры mF(x,y,t) и aF{x,y,i) — математическое ожидание и дисперсия шума. Кроме того гауссову плотность можно использовать для моделирования с приемлемой точностью плотности вероятности коэффициентов унитарных преобразований изображений [31]. Плотность вероятности яркости должна быть односторонней, т. к. яркость принимает только неотрицательные значения. В качестве моделей плотности яркости применяются плотность распределения вероятностей Рэлея {F;x,yj]= MAexp\ И . )Р Р a" 2a плотность логарифмически нормального распределения Г 1—1/2 p{F;x,y,t}= \2л F2(x,y,t)crF2(x,y,t)\ exp [log[F(x,y,t)]jF(x,y,t)f 2aF(x,y,t) и плотность экспоненциального распределения p{F;x,y,t} = aGxp{-a\F(x,y,t)\}.
Эти плотности определены для F 0, а константа. Двусторонняя экспоненциальная (лапласова) плотность p{F;x,y,t} = —exp{-a\F(x,y,t)\], где а — постоянная, часто используется как модель плотности вероятности разностей отсчетов функции, описывающей изображение.
Для описания случайного процесса можно использовать также условные плотности вероятности. Условная плотность вероятности значения случайной функции F(\,y,i) в точке (xuyx,tx) при заданном значении этой функции в точке (x2,y2,t2) определяется как D\F-X v t\F-x V і У- ; 1,ЗУ1, 2, 2} p{F2;x2,y2,t2\
Случайный процесс, порождающий изображение, называется стационарным в узком смысле, если все его моменты не зависят от переноса начала координат в пространстве или времени. Процесс называется стационарным в широком смысле, если он имеет постоянное математическое ожидание, а его автокорреляционная функция зависит юлько от разностей координат л ! — х2, ух — у2, tx —12, но не от самих их значений. Для стационарного процесса F(x,y,i) математическое ожидание равно E{F(x,y,t)} = rjF и автокорреляционная функция имеет вид (xlylytl;x2y23t2) = R(xl хъУ\ УгА h)-Выражение для автокорреляционной функции можно переписать в виде R(rx,ry,Tt)=E{F(x + rx,y + Ty,t + rt)F(x,y,t)} . Часто моделью изображения служат реализации двумерного марковского процесса первого порядка. Автоковариационная функция такого процесса имеет вид Кх,у(тх Т} )=KQW\- ccWx+oc2yT2y] , где К, а и т — масштабирующие множители. Часто делается упрощающее предположение, что автоковариационная функция марковского процесса может быть представлена в виде Ki,v{Tx Ty) = КеЧ \-ах\тх\ -ССу\ту\}.
Рассмотрим стационарное непрерывное изображение— функцию F(x,y). Пусть Ах и Л — заданные шаги дискретизации по пространственным переменным х и у соответственно. Сделав равномерную выборку из непрерывного сигнала F{x,y) с заданными шагами дискретизации: I = \l(k,n)=F(x,y)\[ х=кАхгУ=пАу } , получим функцию і(к,п) двух дискретных переменных — дискретное изображение.
Оно представляет собой матрицу, размерность которой KxN зависит от размеров исходного изображения и шагов дискретизации.
Для описания матрицы I, как и для непрерывного изображения, часто бывает удобно использовать модель стационарного в широком смысле двумерного дискретного процесса, когда математическое ожидание и дисперсия всех элементов {/ „} матрицы I не зависят от их индексов и равны соответственно т1 и т7 . Для описания статистических зависимостей ограничимся рамками корреляционных связей, пренебрегая моментами более высокого порядка. Будем считать, что коэффициент корреляции элементов Ikn и It может быть представлен в виде: где prow — коэффициент корреляции соседних строк (т. е. коэффициент корреляции соседних в п-м столбце элементов: Prow = f {Ik+i,n -[k,n) O Prow-1) Pcol — коэффициент корреляции соседних столбцов (т. е. коэффициент корреляции соседних в т -й строке элементов: рсоі= г\1кп,1кп+]), 0 рсо! \). Таким образом, модель дискретного изображения (матрицы I) имеет вид [38]: r{lk,n Il,j)= pt wPt A ProwiPcol 1 (1-3) к,1 є {0,1,..., -1), n,je{0,l,...,N-l}. Модель (1.3) определяет дискретный двумерный марковский процесс первого порядка с разделимой межстрочной и межстолбцовой корреляцией [45].
Использование контекста для кодирования символов
Основная идея контекстного кодирования заключается в использовании информации об уже обработанных символах для более эффективного кодирования текущего символа. Применительно к сжатию цифровых изображений, такими символами могут являться как непосредственно пикселы изображения, так и, к примеру, коэффициенты некоторого ортогонального преобразования, выполненного над изображением.
Под контекстом і-го символа s,- будем понимать результат отображения f\s ,Sj ,...,sj J, где r 0 — конечное число, определяющее порядок контекстной модели, Sj ,Sj ,-...,5Jr —некоторые предшествующие st символы, j\,j2,—,jr i [145]. В общем случае отображение f может переводить набор символов s,- ,s, ,....,s, J\ /2 Jr во множество объектов произвольной природы, например, числа, векторы, таблицы частот. В простейшем варианте контекстом символа si является сам набор предшествующих символов Sj ,Sj ,....,Sjr, т.е. используется тождественное преобразование f\SJl SJ2im" SJr / SJl SJ2 " SJr
Контекстное кодирование включает в себя два этапа: контекстное моделирование и эффективное (энтропийное) кодирование [34]. Для эффективного кодирования используется некоторый адаптивный многомодельный энтропийный кодер. Контекстное моделирование заключается в выборе статистической модели для кодирования очередного символа s( по известному контексту C(s() этого символа. Такой подход дает возможность с помощью адаптивной модели оценить по выборке условную вероятность Р С ,)}, т. е. учесть зависимость между символами и, следовательно, более эффективно их закодировать [39].
На качество контекстного кодирования оказывают существенное влияние следующие факторы: - выбор подходящего контекста C(st) и его порядка; - способ определения статистической модели на основе контекста; - алгоритм накопления статистики в адаптивной модели энтропийного кодера; - алгоритм формирования кода символа с помощью выбранной статистической модели.
Метод выбора контекста C(s:) зависит от природы кодируемых данных. Одним из способов определения модели па основе контекста является построение контекстного прогноза. Под контекстным прогнозом (или просто прогнозом) символа St будем понимать случайную величину Pt, представляющую собой функцию от элементов контекста C(Si). Данная величина используется при выборе статистической модели для символа St (прописными буквами обозначаются случайные величины (символы), а строчными — их реализации). Тогда pi = /(С( г)) —значение прогноза. Чем точнее составлен прогноз, тем меньше неопределенность символа S{ и тем более эффективно он может быть закодирован. Очевидно, что задача построения контекстного прогноза тесно связана со способом выбора контекста символа.
Способ накопления и адаптации статистической модели, а также алгоритм формирования кода символа определяются используемым энтропийным кодером.
Введем следующие обозначения: пусть Zy,x = [z% x,zy x,...,z x)— считанные в порядке зигзага и промасштабированные в результате деления без округления, zk =у. Iq.j, коэффициенты ДКП, которые на изображении соответствуют блоку с координатами (у,х), и Ъу,х = Щ Х,2У,Х,...,ЩJ— блок проквантованных коэффици ентов ДКП: fA = round(zk), к = 0,..., 63. Далее там, где координаты блока несущественны, они будут опускаться.
Чтобы построить контекстный прогноз для коэффициентов ДКП, необходимо проанализировать имеющиеся между ними статистические связи. Корреляцию между коэффициентами ДКП можно разделить на два вида: внутриблочную и межблочную. Внугриблочная корреляция— это корреляция между коэффициентами одного блока изображения, тогда как под межблочноіі корреляцией понимается корреляция между коэффициентами из разных блоков изображения, в частности, между коэффициентами с одинаковым номером (внутриполосная корреляция).
Известно, что в силу свойств ДКП внутриблочная корреляция незначительна и коэффициенты корреляции близки к нулю. Однако, как было показано в [34], более сильна корреляция между модулями коэффициентов ДКП. Чтобы подтвердить это предположение, был проведен следующий численный эксперимент. На основе шести стандартных полутоновых изображений— Barbara, Boat, Goldhill, Lena, Mandrill, Peppers (см. приложение 1) — были вычислены наименьшее, наибольшее и среднее значения модулей коэффициентов внутриблочной корреляции, которые представлены в табл. 1. Общее число различных коэффициентов корреляции между элементами спектра без учета постоянных составляющих равно 1953 = 63 62/2 .
Исходя из численных оценок, можно утверждать, что в среднем наиболее сильна корреляция между модулями коэффициентов ДКП. Кроме того, корреляция между модулями всегда выше, чем между самими коэффициентами спектра, т. е. p[\z,\, Zj J \p[zl,zJ), V/ Ф j. Поэтому для составления прогноза имеет смысл использовать корреляцию между абсолютными значениями коэффициентов ДКП Z,, Z2L.. ,Z63 и строить прогноз для абсолютной величины коэффициента ДКП.
Алгоритм определения сдвига изображения
Изображение размером KxN пикселов разбивается на блоки {І„} размером К 8x8 пикселов, к = 0,..., 1, TV п = 0,..., 1. Над каждым блоком вы 8 полняется ДКП: Ykn=DCT[lkn). Шаг 2 Чтобы выделить характерные блоки, для каждого из наборов коэффициентов вычисляется сумма ДКП YM = {y квадратов коэффициентов, отмеченных серым цветом на рис. 14: Ek п = /_,У] Выбор именно этих коэффициентов ДКП обусловлен следующими соображениями. Значения у0 характеризуют среднюю яркость участков изображения и для соседних блоков коэффициенты у0 часто оказываются близкими по величине, поэтому использовать их в качестве «отличительной черты» блока не имеет смысла. Коэффициенты ух и у2 могут иметь большие значения, если блок попал на участок изображения с регулярной структурой, например, с вертикальными или горизонтальными линиями, при этом данные коэффициенты будут коррелированы с соответствующими элементами ДКП-спектра соседних блоков (см. рис. 12 и 13, а также раздел 2.3), следовательно, они гаюке не будут отражать особенности фрагмента кадра. Коэффициенты ДКП у3,...,у9 менее коррелированы с коэффициентами соседних участков изображения, но при этом не так сильно подвержены влиянию шумов, поэтому с их помощью можно оценить «непохожесть» блока на остальные, т. е. его характерность. Шаг З
Из всех блоков {І „} для дальнейшего анализа выделяется часть блоков jl j, к el О,...,- 1L п єІО,..., 1L имеющих наибольшее значение параметра Е. Чем больше значение Е, тем сильнее в блоке проявляются соответствующие коэффициентам Уъ,—,У9 частоты, что делает его более «рельефным» и, следовательно, повышает точность определения его вектора перемещения. Количество выбранных блоков зависит от интенсивности движения в видеосцене: суммарная площадь кадра, покрываемая данными блоками, должна превышать площадь, занимаемую подвижными объектами. Шаг 4
Из полученного множества \\? j исключаются одиночные блоки — блоки, у которых нет соседей слева, справа, сверху и снизу. Таким образом, на данном шаге из рассмотрения убираются изолированные блоки, вероятнее всего располагающиеся на преимущественно однородных участках изображения. Шаг 5
Из блоков jlr \ с предыдущего шага случайным образом выбираются Т блоков.
Такой способ выбора блоков позволяет минимизировать влияние движущихся объектов на точность определения параметров сдвига.
Для каждого из блоков с помощью некоторого алгоритма вычисляется вектор перемещения v, =\Х;,х{ J, і — 0,...,Т — \. Сдвиг кадра определяется с помощью покоординатной медианной фильтрации найденных векторов, т. е. смещение всего изображения принимается равным vi =( ,22). (3.1) где х и х —медианы массивов ov-j- r-i/ и \ о v - r-i/ соответственно.
Предложенный алгоритм определения сдвига изображения тестировался с помощью трех полутоновых видеопоследовательностей, полученных при различных погодных условиях (см. рис. 15, а также прил. 2 рис. 60 и рис. 59). Все
последовательности являются слабоконтрастными, значительную часть видеокадров занимают однородные участки с изображением леса и заснеженной территории, на проезжей части наблюдается движение автомобилей — все это затрудняет выполнение глобальной компенсации. Размер кадров составляет 1024x768 пикселов.
Сдвиг каждого видеокадра относительно предыдущего был получен искусственно и представлял собой случайное целое число пикселов. Максимальное возможное перемещение составляло 32 пиксела в каждом направлении (по вертикали и по горизонтали).
На рис. 15 представлен кадр из тестовой последовательности, на рис. 16 белым отмечены блоки, определенные на шаге 3, на рис. 17— характерные блоки, оставшиеся после шага 4 алгоритма.
На шаге 3 для дальнейшего анализа оставлялись 10 % блоков. Перемещения блоков находились с помощью двух алгоритмов: полного перебора в области ±32 пиксела по вертикали и по горизонтали, а также субоптимального алгоритма поиска в такой же области, на первом этапе которого поиск наиболее похожего блока проводится с шагом в 2 пиксела, а на втором этапе перемещение уточняется до 1 пиксела (см. рис. 18).
Для каждого кадра последовательностей при одинаковых значениях всех параметров перемещение r f{k), = 1,...,10, определялось 10 раз (отличались лишь блоки, которые случайным образом выбирались на шаге 5 алгоритма), после чего полученные значения усреднялись.
В табл. 3-6 приведены результаты моделирования алгоритма, а именно, значения следующих характеристик ошибки, полученной при определе- Р унок 18. Субоптималънъ поиск перемещения блока нии сдвига изображения: довательности, Vy и Vy — реальное и найденное перемещение кадра, такое, что максимальная ошибка Дтя„ = max max f=l,...,F у Vy- - \f J , где F — число кадров в после vf-vf = max \\\v f(k)-vf\\ ); - среднее значение ошибки m - mean\ Wr-vA j, v r = mean[\ f(k)): /=1,...;JPMI J J"E J =1,...,104 /V " - оценка стандартного отклонения ошибки ст., = std I v r — v A ) /=1,...,FV11 У J l
Как видно из табл. 3-5, предложенный алгоритм показывает хорошие результаты на сложных видеопоследовательностях даже при небольшом количестве анализируемых блоков. Таюке можно сделать вывод о том, что помимо выбора характерных блоков важную роль играет способ определения перемещения для каждого блока. Поэтому в данном случае имеет смысл использовать алгоритм полного перебора, но при этом выбирать не так много блоков, как потребовалось бы для субоптимального алгоритма для достижения приемлемой точности.
Для сравнения в табл. 6 представлены результаты, полученные при определении сдвига кадра с использованием алгоритма полного перебора и без определения характерных блоков на шагах 3-4 (случайные блоки на шаге 5 выбираются из всех существующих). Видно, что даже при большом числе анализируемых блоков (200) не удается достичь такой же точности, как при расчете всего по 30 характерным блокам.
Важно отметить, что коэффициенты ДКП, необходимые для классификации блоков, к моменту определения глобального перемещения могут быть уже найдены, если до этого проводилось сжатие видеопотока (т. к. большинство существующих алгоритмов видеокомпрессии основано на использовании блочного ДКП), и повторно их вычислять не будет необходимости. Если же ведется обработка еще не сжатых данных, то вычисленное блочное ДКП можно будет использовать в дальнейшем при компрессии видеопоследовательности.
Алгоритм сжатия динамических изображений
Для кодирования разностного изображения, так же, как и для сжатия ключевого кадра, используется метод SPIHT (set partitioning in hierarchical trees, разложение множества по иерархическим деревьям) [118], который был разработан для оптимальной прогрессивной передачи изображений, а также для их сжатия.
Самая важная особенность этого алгоритма заключается, во-первых, в том, что на любом этапе декодирования качество отображаемого в этот момент кадра близко к наилучшему для текущего объема информации о данном изображении. Во-вторых, метод SPIHT позволяет генерировать вложенный код: если кодер для одного и того же изображения производит два файла, большой объема Р бит и маленький объема р бит, то меньший файл совпадает с первыми р битами большего файла.
Ввиду отсутствия в русскоязычной литературе качественного описания алгоритма SPIHT, он подробно рассматривается в прил. 3.
Для количественного измерения расхождения исходного и реконструированного образов метод SPIHT использует квадрат ошибки или среднеквадратическую ошибку: км \ к м I=0w=0 k=0m=0 где К и М— размеры изображения, С = \скт] — исходные вейвлет коэффициенты, C = \ckmf — коэффициенты, восстановленные декодером. В силу ортогональности ДВП убывание этих значений в области преобразования соответствует убыванию их значений в пространственной области. Таким образом, имеется возможность точно контролировать качество сжатия, не выполняя обратное ДВП, что существенно экономит вычислительные ресурсы. Из v этого также следует, что алгоритм SP1HT может иметь различные критерии остановки работы: по достижении заданного качества сжатия, по достижении заданного размера сжатого файла, а также «смешанные» критерии. Кроме того, кодирование может быть остановлено при превышении лимита времени, отведенного на обработку кадра.
В предложенном алгоритме видсокомпрессии реализована версия SPIHT с возможностью контроля как качества сжатия (по MSE), так и битовых затрат (с точностью до байта). В качестве оценки расхождения между исходным и восстановленным спектрами в нем используется квадрат ошибки (4.3). В начальный момент, когда еще не было закодировано ни одного бита, имеем: К-\ А/-1 Л=0 /и=0
Определим, насколько изменится данная величина при передаче очередного бита коэффициента вейвлет-преобразования. Пусть с — исходный коэффициент, а с{п) — коэффициент, восстановленный декодером на п -м битовом слое. Запишем их двоичное представление: с = ]Гс-.2\ с(л)= 242--1, (4.5) і =0 і=и где /V — количество бит, требуемое для представления амплитуды коэффициента с . После того, как кодер передаст очередной бит, декодированный коэффициент примет вид c(w-l)- C;2 +2"-2, (4.6) /=и-1 при этом ошибка (4.4) уменьшится на следующую величину: АЕ = (c-c(n)f -(c-c(n-l)f. Подставив в это выражение представления (4.5) и (4.6), получим: ( п-\ \ АЕ 2]ГС,.2 -Сп_х2п х -3-2""2 \сп_х2п-х -Г 1). (4.7) V «=о )
Значение АЕ определяет, насколько уменьшается ошибка Е при выводе очередного бита в выходной поток, что позволяет точно контролировать качество восстановленного спектра на любом этапе кодирования.
Следует отметить, что значение (4.7) справедливо для случая, когда п 1 и декодер приписывает к восстановленным битам вейвлет-коэффициента дополнительный единичный бит. При передаче информации с последнего битового слоя будем иметь: д=(С-г(і))Чс-г(о))2=(с„-і)2. V у / =0
Возможность контроля качества сжатия в процессе кодирования позволяет при необходимости использовать в методе SPIHT RD-оптимизацию: функция Лагранжа J = D + A -R (4.8) (здесь D — E — текущее расхождение, R — количество бит, переданное декодеру, Я — константа, определяющая соотношение между качеством и степенью сжатия) может вычисляться как после каждого выведенного в поток бита, так и для упрощения вычислений после кодирования очередного битового слоя. При этом дополнительное ограничение сверху битовых затрат на кодирование I- и Р-кадров конкретными значениями позволит не допустить «скачков» битового потока при работе на каналах связи с малой пропускной способностью.
