Например, Бобцов

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

ПРОСТРАНСТВЕННЫЕ АЛГОРИТМЫ КОДИРОВАНИЯ ИЗОБРАЖЕНИЙ
УДК 621.397.13:519.95
ПРОСТРАНСТВЕННЫЕ АЛГОРИТМЫ КОДИРОВАНИЯ ИЗОБРАЖЕНИЙ
Е.И. Колесников, Е.В. Костикова
Рассмотрен подход к решению задач представления и обработки изображений на основе рекурсивного поиска опорных точек при сжатии и использовании двумерной интерполяции при восстановлении изображений. Приведен пример алгоритма поиска опорных точек. Ключевые слова: рекурсия, опорные точки, полигон, полигональная сетка.
Введение Дефицит пропускной способности каналов связи всегда имеет место, и развитие техники связи показывает, что это «вечная» проблема всей техники связи, и, особенно, телевизионной техники. В связи с этим во всех системах обработки изображений применяются устройства сжатия, реализующие максимально возможные способы распараллеливания алгоритмов кодирования. Одним из многочисленных методов сжатия, реализующим кодирование изображения без перехода в спектральную область, является полигонально-рекурсивный метод (ПРМ) кодирования, основанный на пространственно-рекурсивном разбиении исходного изображения [1−4]. Сегодня активно развиваются подходы по способам представления видеоинформации на основе пирамидально-рекурсивных структур данных [2]. Такие структуры обеспечивают возможность эффективной обработки видеоданных с поэтапной выборкой и передачей нужной в данное время информации. Также, благодаря высокой степени компрессии данных этого метода, в таком представлении могут храниться очень большие базы видеоданных. Основные достоинства данного подхода заключаются в следующем:  в процессе кодирования изображений решается задача компактного представления исходных данных с помощью набора опорных точек (ОТ), где каждая точка максимально характеризует свою локальную область (задача сжатия);  полигонально-рекурсивный метод разбиения исходного изображения на полигоны позволяет максимально распараллеливать процесс поиска ОТ, что является важным при сжатии нестационарных изображений.
88 Научно-технический вестник Санкт-Петербургского государственного университета
информационных технологий, механики и оптики, 2011, № 3 (73)

Е.И. Колесников, Е.В. Костикова
Основной идеей этого метода является аппроксимация сигнала изображения набором областей с интенсивностью, изменяющейся внутри каждой области по известному закону (с применением сплайнов различного порядка, обычно – от нулевого до третьего) [3, 4]. В отличие от простейшего способа интерполяции изображения по набору регулярно расположенных отсчетов, полигональный метод использует нерегулярный массив отсчетов, связанных с некоторыми «особыми» точками исходного изображения, которые становятся опорными при его восстановлении. Выделение на реальных изображениях, содержащих, кроме полезного сигнала, различные помехи, «особых» точек характеризует ПРМ как попытку выделения полезной информации из шумовой, а сам алгоритм регулярной триангуляции может быть охарактеризован как оптимальный инструмент восстановления изображений по опорным точкам [5−7].
Целью работы является исследование алгоритмов ПРМ разбиения на полигоны при поиске ОТ на этапе кодирования изображений и применении интерполяционных алгоритмов на этапе декодирования. При этом решается задача определения оптимальных параметров системы кодирования на основе предложенного метода (число полигонов, число опорных точек, число бит на отсчет и т.д.) и выбора наилучшей структуры представления ОТ.
Описание метода кодирования
Процесс кодирования и декодирования сигналов изображений на основе ПРМ заключается в следующем (рис. 1). На этапе кодирования, изображение рассматривается как единая область (полигон), и на ней проверяется критерий однородности (наличие или отсутствие каких-либо объектов или опорных точек). На этапе кодирования задается порог отклонения значений отсчетов от дисперсии сигнала, далее сравниваются отсчеты исходного полигона с порогом для разбиения и дальнейшего поиска ОТ. В пределах каждого из полученных полигонов осуществляется поиск оптимальной точки, максимально характеризующей двумерную поверхность полигона. В результате анализа всего изображения получаем полигональную двумерную сетку, содержащую как пустые полигоны (однородные), так и полигоны, содержащие ОТ.
На этапе декодирования (восстановления) каждая ОТ соединяется с ближайшими соседними точками, и в итоге все точки будут соединены сеткой, вершины которой в результате двумерной интерполяции позволяют построить регулярную триангуляцию.

Рис. 1. Обобщенный полигонально-рекурсивный метод кодирования и декодирования изображений
Простым подходом решения задачи выделения ОТ является использование одного из способов разбиения на основе шаблонов [8]. В этом случае в качестве области для построения первичной сетки выбирают одну из подходящих геометрических форм, для которых разработаны шаблоны (разумеется, эта область должна полностью включать в себя заданную). Рассмотрим вариант построения первичной сетки методом деления на три полигона с использованием полигонально-рекурсивного подхода при поиске опорных точек на этапе кодирования и интерполяции этих точек по полигональной сетке на этапе декодирования изображений. Заметим, что для случая равновероятного распределения ОТ на исходном изображении построенная при разбиении сетка получается близкой к равномерной, т.е. линейные размеры полигонов приблизительно равны. Это обусловлено, во-первых, тем, что поиск ОТ осуществляется по

Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики, 2011, № 3 (73)

89

ПРОСТРАНСТВЕННЫЕ АЛГОРИТМЫ КОДИРОВАНИЯ ИЗОБРАЖЕНИЙ
амплитудным (яркостным) свойствам сигнала, а, во-вторых, тем, что при построении первичной сетки не используется никакой информации о геометрии заданной области, т.е. свойствах конкретной реализации сигнала. При таком представлении изображение разбивается на равные непересекающиеся полигоны (рис. 2, а). Затем процедура повторяется для каждого полигона до тех пор, пока дисперсия значений яркостей отсчетов превышает заданный порог. В результате каждому полигону приписывается численное значение, называемое яркостью или цветом и являющееся его обобщенной характеристикой. Разбиение изображений, не являющихся тривиальными, представляет собой одну из самых сложных задач обработки изображений. Конечный успех анализа изображений во многом определяется точностью разбиения и правильным выбором основных параметров – числа и формы разбиения.
Таким образом, опорные точки − это вершины троичного дерева полученной полигональной сетки (рис. 2, б), с помощью аппроксимации которых можно обеспечить эффективное кодирование при заданном качестве. Опорные точки могут быть найдены двумя способами: а) фиксацией координат по достижении требуемой точности в процессе разбиения; б) поиском ОТ в пределах полигона.
Вопросы, связанные с критериями и алгоритмами поиска ОТ в пределах полигона, в работе не рассматриваются.
Разработка структуры видеоданных
Разработка эффективной структуры данных для хранения и передачи опорных точек осуществлена с использованием динамического одномерного массива, сгруппированного по таким признакам, как число полигонов и уровней разбиений. Данная структура позволяет постепенно воссоздать результирующее изображение по мере приема массива сжатого описания опорных точек. При этом каждая ОТ характеризуется своими абсолютными координатами и яркостью в пределах полигона, что учтено при формировании сжатого описания [9].
Для формирования сжатого описания изображения по ОТ используется динамический одномерный массив (рис. 2, в), сгруппированный в зависимости от числа полигонов после разбиения (при разбиении на два полигона группы содержат два элемента, при разбиении на три полигона группы содержат соответственно три элемента, и т.д.).
В каждой группе 1-й элемент указывает на предыдущий уровень разбиения, остальные элементы содержат следующие признаки: Пр1 – признак того, что полигон подлежит следующему дроблению, т.е. покрывается более одной ОТ. Пр2 – признак того, что полигон далее не подлежит дроблению и покрывает одну ОТ. В этом случае в сжатое описание дополнительно заносятся координаты ОТ в пределах полигона; Пр3 – признак того, что полигон не содержит ни одной ОТ и, следовательно, не подлежит последующему дроблению.
По окончании процесса разбиения и поиска ОТ на этапе кодирования полученный динамический массив преобразуется в двоичный код (массив битов), который далее подвергается энтропийному кодированию для передачи по каналу данных.
Существует множество различных способов создания конечно-элементных сеток. Эти способы классифицируются как по алгоритму полигонального разбиения (различные формы полигонов), так и по способу поиска опорных точек в пределах одного полигона [8]. Для построения дискретной модели двумерной области в основном могут использоваться два семейства элементов: треугольники и четырехугольники. Стороны линейных элементов каждого семейства представляют собой прямые линии. Квадратичные и кубические элементы могут иметь прямолинейные и/или криволинейные стороны. Это означает, что оптимальное разбиение изображения на области требует достаточно большой вычислительной сложности алгоритма, реализующего триангуляционный метод кодирования.
Экспериментальные исследования показали, что при хорошем субъективном качестве восстановленных изображений коэффициент сжатия с использованием различных алгоритмов разбиения и поиска опорных точек на основе ПРМ имеет следующие особенности.  Различные алгоритмы разбиения изображений приводят к различному приближению к энтропии
изображения. Вместе с тем требуемая пропускная способность канала зависит от числа полигонов при разбиении. Результаты моделирования алгоритмов разбиения и восстановления изображений показали, что наиболее близкий к энтропии источника результат достигается при трихотомии, при этом на практике оптимальное основание кода составляет иррациональное число е.  Коэффициент сжатия, который зависит от числа опорных точек, при трихотомии приблизительно в 1,2 раза больше, чем при дихотомии, и в 1,4 раза больше, чем при тетрахотомии.
При равновероятном распределении опорных точек на исходном изображении эффективное сжатие достигается, когда число опорных точек составляет 2030% от общего числа точек, при этом количество бит, необходимое для кодирования ОТ, не превышает 6 бит.
Исследования проводились над изображениями в 256-уровневом представлении яркости в формате 8 бит на пиксель. При этом емкость памяти для хранения цифрового изображения равна 2562 байт. Алгоритмы кодирования и декодирования реализованы на языке высокого уровня С++.
90 Научно-технический вестник Санкт-Петербургского государственного университета
информационных технологий, механики и оптики, 2011, № 3 (73)

Е.И. Колесников, Е.В. Костикова
аб

в
Рис. 2. Структура данных опорных точек: (а) – двумерная пирамида изображения; (б) – соответствующая ей структура данных; (в) – массив сжатого описания исходного изображения
Заключение
Сформулируем основные выводы, которые являются также основными свойствами предлагаемого метода при проектировании систем кодирования и декодирования нестационарных изображений. 1. Структура данных представляется в виде некоторой регулярной, иерархической, не зависящей от
содержания данных структуры. Эта структура содержит множества опорных точек и их взаимосвязь. 2. Разработка алгоритмов производится таким образом, чтобы обеспечить возможность поэтапного
приближения к эпсилон-энтропии исходного сигнала. Для этого на каждом уровне разбиения исходного изображения анализируется результат восстановления по величине ошибки кодирования и при необходимости производится дальнейшее разбиение и уточнение результирующего изображения. 3. Элементы сжатого описания представляют собой не элементы изображения или информационного поля, а опорные точки, имеющие похожие или одинаковые свойства. Таким образом, сложность ПРМ определяется не разрешающей способностью аппаратуры (количеством отсчетов изображения), а количеством опорных точек, т.е. числом элементов самой структуры, которая для конкретного класса может быть значительно меньше числа отсчетов исходного изображения.

Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики, 2011, № 3 (73)

91

ИССЛЕДОВАНИЕ ВАРИАНТОВ РЕАЛИЗАЦИИ ЭТАПА ПРЕДСКАЗАНИЯ ЛИФТИНГОВОЙ …

Литература
1. Твердотельная революция в телевидении / В.В. Березин, А.А. Умбиталиев, Ш.С. Фахми, А.К. Цыцулин, Н.Н. Шипилов. – М.: Радио и связь, 2006. – 300 с.
2. Александров В.В., Горский И.Д. Представление и обработка изображений. Рекурсивный подход.  Л.: Наука, 1985. – 192 с.
3. Demaret L., Iske A. Adaptive image approximation by linear splines over locally optimal Delaunay triangulations // IEEE Signal Processing Letters. – 2006. – № 13 (5). – Р. 281–284.
4. Demaret L., Dyn N. and A. Iske. Image compression by linear splines over adaptive triangulations // Signal Processing. – 2006. – № 86 (7). – Р. 1604–1616.
5. Demaret L., Iske A. Anisotropic triangulation methods in image approximation. In: Approximation Algorithms for Complex Systems. E.H. Georgoulis, A. Iske and J. Levesley (etс). – Berlin: Springer, 2010. – Р. 47–68.
6. Фахми Ш.С. Кодирование и декодирование видеоинформации // Вопросы радиоэлектроники. Сер.
Техника телевидения. – 2007. – Вып. 2. – С. 4351.
7. Прапарата Ф., Шеймос М. Вычислительная геометрия: Введение.  М.: Мир, 1989.  478 с. 8. Фахми Ш.С. Полигональная рекурсивная обработка видеоинформации // Вопросы радиоэлектроники.
Сер. Техника телевидения. – 2008. – Вып. 1. – С. 42–51. 9. Фахми Ш.С. Аналитическая модель оценки степени приближения к эпсилон-энтропии на основе пи-
рамидально-рекурсивного метода кодирования изображений // Вестник ТОГУ. – 2010. – № 1 (16). – С. 32–44.

Колесников Евгений Игоревич Костикова Елена Валентиновна

– Санкт-Петербургский государственный университет информационных технологий, механики и оптики, аспирант, evgeniy777.84@gmail.com
– Санкт-Петербургский государственный университет водных коммуникаций, преподаватель, Kostikovaev@mail.ru

92 Научно-технический вестник Санкт-Петербургского государственного университета
информационных технологий, механики и оптики, 2011, № 3 (73)