Ключевые слова: нейронные сети; сжатие изображений; машинное обучение; фракталы.

Аннотация

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

1. Введение

Фрактальное кодирование изображений представляет собой подающий надежды подход в приложениях сжатия изображений, таких как веб-сайты Интернет [1]. Однако, потребность во времени для этапа кодирования в этом подходе было сдерживающим препятствием его принятию как практического метода. Процесс кодирования заключается в отображении доменных блоков в ранговые блоки изображения. Для каждого рангового блока алгоритм ищет такой доменный блок и соответствующее преобразование, которые обеспечат наилучшее соответствие ранговому блоку. Классификация доменных блоков может значительно ускорить выполнение кодирования, сокращая количество доменов, среди которых нужно проводить поиск [2, 3]. Использование самоорганизующихся нейронных сетей с целью классификации доменов уже было исследовано [4, 5]. Эти сети дают улучшение, по сравнению с базовыми подходами к классификации, благодаря определению топологии кластеров классов. Вклад данной работы состоит в комбинировании классификации доменов с помощью самоорганизующейся нейронной сети вместе с выделением характеристик с целью обеспечения еще более быстрого кодирования изображений. Небольшой набор характеристик изображения, измеряющих тоновые и текстурные качества, вычисляются для каждого доменного и рангового блока. Таким образом, каждый блок имеет ассоциированный с ним вектор характеристик, размер которого не зависит от размера блока. Выделение характеристик является выгодным по двум причинам. Во-первых, получаемое в результате снижение объема задачи сокращает количество вычислений, необходимых в процессе поиска доменов. Во-вторых, так как характеристики независимы от структуры конкретных доменов, то становится возможным обучать самоорганизующуюся сеть на одном изображении и применять полученную в результате сеть для классификации на других изображениях. Таким образом, время обучения сети не является частью общего времени кодирования. Измерения времени фрактального кодирования изображений обычно выражают в терминах времени выполнения на рабочей станции Sun или Silicon Graphics. Представленный здесь подход обеспечивает сопоставимые измерения при выполнении на ПК Pentium 120 MHz.

2. Фрактальное кодирование изображений

Фрактально кодирование изображений основано на теории систем итерируемых функций (далее сокращенно СИФ, от англ. Iterated Function System — IFS). Теория СИФ имеет в своей основе теорему о сжимающих отображениях (далее сокращенно ТОС, от англ. Contraction Mapping Theorem — CMT) из классического анализа, которая используется для построения фрактальных изображений итеративным образом. Фрактальное изображение является фиксированной точкой в пространстве изображения, что гарантируется ТОС, и это изображение называется аттрактором СИФ. Обратная задача, решаемая фрактальным кодированием изображений, начинается с рассмотрения заданного изображения и вычисления СИФ, представляющей изображение, близкое к заданному, — его аттрактор. Код фрактального изображения обычно (хотя, не всегда) требует меньшего объема для хранения, чем изображение-оригинал, что проявляет этот метод как метод сжатия. Эмпирические результаты показывают, что во многих случаях фрактальный метод настолько же хорош, как и JPEG, который считают стандартом сжатия на сегодня [2].

Фрактальное сжатие изображений использует специальную разновидность СИФ, называемую системой итерируемых кусочно-определенных функций (далее сокращенно СИКФ, от анг. Partitioned Iterated Function System — PIFS). СИКФ состоит из полного метрического пространства X, набора поддоменов D_i ⊂ X, i = 1,...,n, и набора сжимающих преобразований w_i^~: D_i → X, i = 1,...,n. Мы рассматриваем изображения в градациях серого как функции действительные значений f(x, y), определенные на квадратной области I² = I×I. Пусть w_i^~(x, y) — аффинное преобразование I² → I², такое что

(2.1)

для некоторой матрицы A_i размером 2×2 и вектора b_i размером 2×1. Пусть D_i ⊂ I² — некоторый поддомен единичного квадрата I², и пусть R_i — ранг значений преобразования w_i^~, действующего на множестве D_i, так, что w_i^~(D_i)= R_i. Теперь мы можем определить отображение w_i, действующее на изображения следующим образом:

(2.2)

при условии, что w_i^~ — обратимо и (x,y) ∈ R_i. Константа s_i расширяет или сужает диапазон значений функции f и, коль скоро мы говорим об изображениях в градациях серого, то она управляет контрастностью. Аналогично, константа o_i увеличивает или уменьшает значения градаций серого, или управляет яркостью. Преобразование w_i^~ называется пространственной составляющей преобразования w_i.

Базовый алгоритм выполняется следующим образом. Разбиваем изображение на не перекрывающиеся прямоугольные ранговые блоки {R_i}. Блоки R_i могут быть одинакового размера, но чаще используется некоторая разновидность разбиения с переменным размером блоков, что дает возможность плотно заполнять ранговыми блоками маленького размера части изображения, содержащие мелкие детали. Представленные здесь результаты, были получены с использованием схемы разбиения методом квадро-дерева (quadtree partition scheme), описанной в [2]. Покрываем изображение последовательностью доменных блоков, возможно перекрывающихся. Домены могут быть разных размеров и обычно их количество исчисляется сотнями и тысячами. Аффинное преобразование (2.1) является пространственным сжимающим преобразованием, если |det A_i| < 1. Для получения пространственного сжатия ограничим преобразования w_i^~ жестким параллельным переносом и одним из восьми основных поворотов и отражений, как это описано в [2]. Для каждого рангового блока R_i пытаемся найти домен D_i, пространственное преобразование w_i^~, контрастность s_i и яркость o_i такие, чтобы w_i(f) было близко к изображению f в блоке R_i. То есть ищем w_i, такое, чтобы величина

(2.3)

была небольшой. Для оцифрованных изображений интеграл (2.3) заменяется суммированием по пикселям. Если после нахождения наилучшего w_i величина (2.3) оказывается все еще больше некоторой заранее определенной погрешности, то схема разбиения методом квадро-дерева разбивает ранг на четыре более малых прямоугольника, и процесс поиска оптимального преобразования повторяется для этих меньших блоков. Этот процесс продолжается до тех пор, пока величина (2.3) не станет меньше допустимой погрешности или пока не достигается заранее определенная максимальная глубина квадро-дерева. Изображение декодируется итеративным применением преобразования W к изображению f, где

W(f)(x,y) = w_i(f)(x,y) для (x,y) ∈ R_i

Если преобразования {w_i} были выбраны корректно, то итерирование W⁰ⁿ(f) будет близко к исходному изображению при некотором достаточном значении n. Этап кодирования требует значительных вычислений из-за большого количества доменов, среди которых нужно осуществлять поиск для каждого рангового блока, а также из-за вычислений, проводимых при каждом сравнении домена с рангом. В этой работе сокращение вычислительных потребностей этапа кодирования решается в двух направлениях. Во-первых, вводится понятие характеристик изображения, определяемых для каждого доменного и рангового блока. Тогда потенциально подходящие домены могут быть выбраны на основе значений небольшого количества этих характеристик, чем значений самих пикселей. Во-вторых, предлагается организация доменных блоков в кластерную топологию посредством самоорганизующейся нейронной сети. Это еще больше сокращает время кодирования, позволяя сети быстро определять месторасположение в пространстве характеристик тех доменных блоков, которые похожи на ранговые блоки.

3. Выделение характеристик

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

Здесь используются следующие шесть характеристик: 1) стандартное отклонение (standard deviation), σ; 2) асимметрия (skewness), которая представляет собой сумму кубов разностей между значениями пикселей и средним значением блока, нормированных кубом σ; 3) межпиксельная контрастность (neighbor contrast), которая измеряет разность между значениями соседних пикселей; 4) бета (beta), которая показывает насколько сильно отличаются значения пикселей от значения в центре блока; 5) горизонтальный градиент (horizontal gradient), который характеризует изменение значений пикселей блока по горизонтали; 6) вертикальный градиент (vertical gradient), который характеризует изменение значений пикселей блока в направлении сверху вниз. Среднее пиксельное значение не используется в качестве характеристики, поскольку контрастность и яркость меняются в процессе сопоставления доменного и рангового блоков. При сравнении расстояний в пространстве характеристик, вектор характеристик нормализуют для того, чтобы набольшие значения характеристик не доминировали при сравнении.

4. Самоорганизующиеся нейронные сети

Следующее улучшение, которое может быть сделано — это классификация доменов и рангов на основе этих характеристик и сравнение рангов только с доменными похожих классов. Используемая здесь схема классификации доменов основана на самоорганизующейся нейронной сети Кохонена [7]. Этот тип сети состоит из решетки (lattice) узловых позиций (node positions). С каждым узлом решетки связан весовой вектор, который имеет ту же размерность, что и размерность векторов характеристик. Размерность используемых здесь векторов характеристик составляет 6. А используемая здесь решетка узлов состоит из 10 строк и 10 столбцов. Каждый узел представляет класс доменных блоков изображения, поэтому общее количество узлов мы стремимся сохранить довольно малым. Можно рассматривать и другие способы организации узлов, такие как матрицы более высокой размерности.

Процесс обучения происходит независимо, без какого-либо контроля со стороны человека. Сеть весовых векторов инициализируется случайными значениями. Затем в сеть поступает входной вектор характеристик, и мы отыскиваем весовой вектор, самый близкий к входному вектору. То есть, мы находим i’j’, такие что

||v – w_i’j’|| ≤ ||v – w_ij|| для всех i, j

где v — это входной вектор характеристик, а w — весовой вектор в узле ij. Веса, смежные по решетке с выбранным весом w_i’j’ адаптируются, чтобы больше походить на входной вектор. Эта адаптация выражается формулой

w_ij^new = w_ij^old + ε·exp(α·||v–w_ij^old||²)·(v– w_ij^old)

где ij — это индексы узлов, которые находятся в окрестности узла i’j’. Размер этой окрестности сокращается с каждой новой итерацией процесса обучения. Параметр ε — это шаг итерации, и α обратно пропорционально этому шагу. Программная реализация представленных результатов приведена в [8].

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

5. Результаты

В таблице 1 представлены результаты сравнения фрактального сжатия изображений с использованием трех различных методов, применительно к изображениям, показанным на рисунках 1 и 2. «Базовый» («base») метод — это стандартный метод разбиения квадро-деревом, обсуждаемый в [2], без классификации доменов. Величина «уровень квадро-дерева» («quadtree level») обозначает максимально допустимую глубину квадро-дерева. Здесь большое число обуславливает более малые ранговые блоки, что приводит к лучшему качеству декодируемого изображения, но при этом к худшей компрессии. «Порог ошибки» («error threshold») — это параметр, контролирующий условие разбиения ранговых блоков на более малые блоки следующего более высокого уровня квадро-дерева. Значения ошибок вычисляются путем сравнения исходного растрового изображения с изображением, декодированным с использованием 6 итераций (большее количество итераций дало бы немного меньшие ошибки). «Средняя ошибка, %» («average error») — это средняя ошибка, приходящаяся на один пиксель, в то время как «PSNR» — это пиковое отношение сигнал-шум, вычисляемое как в [3]. Метод «FO» (features-only) на основе только характеристик сравнивает доменные и ранговые блоки по шести характеристикам, рассмотренных в разделе 3. Последний метод («SO») классифицирует домены с использованием самоорганизующейся нейронной сети с выделением характеристик, как было рассмотрено выше. В каждом случае всего было использовано 320 доменных блоков. Большее количество доменов привело бы к увеличению времени кодирования и в какой-то степени лучшим коэффициентам сжатия.

Коэффициенты сжатия оцениваются отношением в среднем 4 байт для каждого рангового блока к 66614 байтам исходного растрового изображения. SO-метод работает приблизительно в два раза быстрее FO-метода и в сто раз быстрее базового метода («время на блок» выражает меру времени выполнения, которая не зависит от конечной точности изображения; приведенные здесь значения времени соответствуют ПК Pentium 120MHz). Самоорганизующаяся сеть была обучена отдельно на изображении, отличном от представленных здесь двух изображений, поэтому время обучения не включено в общее время для этого метода. Степень сжатия и качество декодированного изображения, как при ускоренных методах, так и при базовом методе, соизмеримы.

Таблица 1 — Результаты фрактального сжатия изображений при использовании самоорганизующейся классификации доменов («SO»-метод), сравнении доменов на основе только характеристик («FO»), и базовом методе («Base»)

(а)	(б)

Рисунок 1 — (а): Исходное растровое изображении «Rose» (256×256, 256 градаций серого); (б): Декодированное изображение (6 итераций, уровень квадро-дерева равен 7, средняя пиксельная ошибка равна 1.8%, сжатие 2.5:1)

(а)	(б)

Рисунок 2 — (а): Исходное растровое изображение «Leaves» (256×256, 256 градаций серого); (б): Декодированное изображение (6 итераций, уровень квадро-дерева равен 7, средняя пиксельная ошибка равна 3.05%, сжатие 1.6:1). Более высокий уровень детализации в этом изображении приводит к уменьшению быстродействия

6. Выводы

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

Литература

1. E. DeJesus, “Walking, Talking Web”, Byte, January, 1997, 81-84.
2. Y. Fisher, ed., Fractal Image Compression, (New York: Springer-Verlag, 1995).
3. A. Jacquin, “Image coding based on a fractal theory of iterated contractive image transformations”, IEEE Trans. Image Proc. 1, 1992, 18-30.
4. A. Bogdan and H. Meadows, “Kohonen neural network for image coding based on iteration transformation theory”, Proc. SPIE 1766, 1992, 425-436.
5. R. Hamzaoui, “Codebook clustering by self-organizing maps for fractal image compression”, NATO ASI Conf. On Fractal Image Encoding and Analysis, July, 1995.
6. M. Barnsley, Fractals Everywhere, 2nd ed. (Boston: Academic Press, 1993).
7. T. Kohonen, Self-Organization and Associative Memory, (Springer-Verlag, 1989).
8. S. Welstead, Neural Network and Fuzzy Logic Applications in C/C++, (New York: John Wiley and Sons, 1994).