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

Размещено на http://www.allbest.ru/

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

В.К. Гулаков, С.Б. Клепинин

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

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

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

Многие годы фрактальное кодирование служило для сжатия изображений, так как фрактальные коды занимают намного меньше места, чем оригинальные изображения. Был создан ряд алгоритмов, успешно реализующих эту технику [1; 7].

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

Фрактальное кодирование изображения. Целью алгоритмов фрактального кодирования изображений является создание последовательности процессов, способных воспроизвести заданное изображение (либо его хорошее приближение).

Преобразование в метрическом пространстве называется сжимающим отображением, если существует константаs , такая, что для выполняется условие

Константа называется коэффициентом сжатия отображения .

Если является полным метрическим пространством и преобразование является сжимающим отображением с коэффициентом , тогда:

1. Существует единственная неподвижная точка , такая, что .

2. .

3. .

Утверждения 1 и 2 известны как теорема о сжимающих отображениях (ТОС), а утверждение 3 называется теоремой Коллажа [2]. Мы рассматриваем изображение как точку в метрическом пространстве. ТОС показывает, как работает фрактальное кодирование: находим такое сжимающее отображение, неподвижной точкой которого является кодируемое изображение (на практике это может быть очень близкое к нему изображение). Теорема Коллажа гарантирует, что расстояние между преобразованной и неподвижной точками меньше, чем расстояние между начальной точкой и неподвижной. Если применять сжимающее отображение последовательно несколько раз к точке, то со временем результат будет приближаться к неподвижной точке.

При фрактальном кодировании изображения код изображения x может быть эффективно представлен как набор аффинных сжимающих отображений W с неподвижной точкой , которая является хорошим приближением к x. Алгоритм фрактального кодирования может быть следующим [3]:

1. Разбиваем изображения на непересекающиеся ранговые блоки , используя квадродерево [6].

2. Покрываем изображения последовательностью доменных блоков , (могут перекрываться).

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

4. Сохраняем как позицию рангового блока и подобранного доменного блока, так и параметры преобразования.

Один из способов разбиения изображения на ранговые блоки - использование квадродерева [6]. Вначале выполняется грубое разбиение, основанное на максимальном размере рангового блока (или разделение целого изображения на четыре прямоугольника). Для каждого рангового блока алгоритм пытается найти домен и соответствующее сжимающее отображение, которое наилучшим образом покрывает ранговый блок. Чтобы обеспечить сжатие, те ранговые блоки, которые оказываются больше самого большого из доменов, разбивают на меньшие ранговые блоки. Если покрытие оказывается в пределах допустимой погрешности, то считается, что этот ранговый блок покрыт, и алгоритм переходит к другому ранговому блоку. Если отклонение не укладывается в пределы допустимой погрешности, то алгоритм проверяет, была ли достигнута максимальная глубина квадродерева. Если максимальная глубина квадродерева не была достигнута, то алгоритм разбивает блок на 4 меньших ранговых блока и поиск оптимальных доменов и преобразований начинается заново для этих новых ранговых блоков. Процесс завершается, когда все ранговые блоки оказываются покрытыми - или с помощью такого подбора домена и преобразования, который обеспечивает отклонение в пределах допустимой погрешности, или путем достижения максимальной глубины квадродерева.

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

Задача фрактального кодирования - найти доменный блок D для каждого рангового блока на одном и том же изображении так, чтобы преобразование W(D) было хорошей аппроксимацией рангового блока. Так как применяются сжимающие отображения, то доменный блок должен быть больше рангового. Число различных допустимых размеров доменных блоков и характер их перекрытия друг друга составляют два важных параметра системы.

Наиболее затратный с точки зрения объема вычислений шаг фрактального кодирования - это отображение доменных блоков в ранговые. Для каждого рангового блока алгоритм выполняет сравнение с преобразованными версиями доменов. Преобразования обычно являются аффинными. Преобразование W состоит из геометрических и цветовых преобразований.

Для изображения в градациях серого обозначим как z интенсивность пикселя (x,y), тогда аффинное преобразование W будет выглядеть следующим образом:

.

распознавание изображение фрактальный кодирование

Коэффициенты a,b,c,d,e,f управляют геометрическим аспектом преобразования, s -контраст, o - яркость. Геометрическое преобразование ограничено уменьшением размера, а также одной из восьми возможных ориентаций. Варианты ориентации включают четыре поворота на 900 и зеркальное отражение в каждой ориентации (рис.1).

Рис. 1. Возможные ориентации доменного блока

Сравнение рангового и доменного блоков происходит в три шага. Сначала к выбранному доменному блоку Dj применяется одна из восьми ориентаций (рис. 1). Затем повернутый домен умень-шается до размеров рангового блока Rk (рис. 2). Ранговый блок должен быть меньше, чем доменный, в связи с использованием сжимающих отображе-ний. В конце вычисляются оптимальные яркость и контраст методом наименьших квадратов. Представление изображения в виде набора преобразованных блоков является не формой копирования, а формой приближения изображения.

Рис. 2. Иллюстрация доменных и ранговых блоков

Минимизировав ошибку между W(Dj) и Rk, мы минимизируем разницу между оригиналом изображения и его фрактальным приближением. Обозна-чим и значения пикселей двух равных по размеру блоков Rk. и Dj (уменьшенного). Ошибку Err определим следующим образом:

.

Минимум Err достигается тогда, когда частные производные по s и o равны 0:

;

; .

Это возможно при

, ,

; , ; .

Фрактальный код изображения может выглядеть так, как показано в таблице.

Таблица

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

Первая колонка таблицы содержит 6 параметров квадродерева, которые указывают геометрическую позицию рангового блока. Следующая колонка - это индекс домена, который уникально идентифицирует положение домена, основываясь на таких параметрах, как размер доменных блоков, количество различных размеров доменных блоков, степень перекрытия. Третья колонка содержит индекс ориентации (число на отрезке [0;7]). В этом типе фрактального кодирования последние 4 колонки (индекс домена, ориентация, яркость и контрастность) используются как фрактальные характеристики (свойства) для распознавания.

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

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

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

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

.

Это условие показывает, что фрактальный код изображения не уникален (мы можем иметь множество пар А,В для одной неподвижной точки ).

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

1. Препроцессинг, нормализация изображения (например, для распознавания лиц на этом этапе локализуется область глаз, лицо).

2. Посредством классического алгоритма вычисляем фрактальный код одного изображения-образца .

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

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

5. Сохраняем параметры кодирования.

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

Рис. 3. Траектории сходимости трех различных изображений, к которым применяется один и тот же фрактальный код (изображение x3 наиболее близко к фиксированной точке (d3<d2<d1))

Например, мы хотим найти в базе данных изображение, близкое к . Евклидово расстояние, основанное на разнице значений пикселей, не является надежным, так как не устойчиво к шумам и помехам в изображении. Поэтому необходимо найти более надежную метрику. Предложение заключается в том, чтобы классифицировать изображения на основе расстояния между двумя успешными итерациями отображений с параметрами, соответствующими (искомое изображение), выполненными над изображениями в базе данных [4].

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

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

Если связь между доменным и ранговым блоками случайна по своей природе, то небольшие изменения в некоторой части изображения приведут к изменениям в системе «ранговый блок - доменный блок». Также это может привести к изменениям во всех ранговых блоках, связанных с тем доменным блоком, в котором произошли изменения. Это показывает, что если распределение доменных блоков по ранговым является случайным, то небольшие изменения в одной части изображения могут повлиять на фрактальные коды другой части изображения.

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

Рассмотрим алгоритм использования подфракталов [5] (на примере базы данных лиц людей) (рис. 4):

1. Локализуем область глаз, нормализуем изображение.

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

3. Покрываем каждую подфрактальную область непересекающимися ранговыми блоками размером rЧr.

4. Покрываем подфрактальные области последовательностью перекрывающихся доменов k различных размеров: 2rЧ2r, 22rЧ22r…, 2krЧ2kr,. Также добавляем в доменный пул версии каждого домена, повернутого на 90, 180, 270 градусов. Добавляем отраженную версию каждого домена в пул.

5. Для каждого рангового блока ищем наилучший доменный блок из пула соответствующей подфрактальной области. Это можно сделать, минимизировав функцию E(R,D):

,

где - R ранговый блок; D - доменный блок.

, , ,

где F {0 - нет отражения, 1 - горизонтальное отражение}.

6. Записываем позиции рангового и доменного блоков, а также параметры L,и,F как геометрическую составляющую преобразования.

7. Вычисляем цветовые параметры o,s (как было описано) и записываем их как часть фрактального кода.

8. Повторяем шаги 5-7 для всех ранговых блоков данной подфрактальной области.

9. Повторяем шаги 3-8 для всех подфрактальных областей изображения.

Таким образом, метод кодирования, основанный на подфракталах, разбивает изображение на ряд подобластей (подфракталов), каждая из которых обладает собственной системой ранговых, доменных блоков и преобразований. Здесь открываются интересные возможности для распознавания образов по отдельным частям, выделения более и менее важных (в прикладном смысле) частей изображения.

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

Рис. 4. Блоки подфракталов: а - ранговые; б - доменные

Алгоритмы разбиения на ранговые и доменные блоки могут варьироваться от системы к системе, так же как и форма блоков.

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

СПИСОК ЛИТЕРАТУРЫ

1. Barnsley, M. Fractal Image Compression / M.Barnsley, L.Hurd. -AK Peters, 1993. - 253p.

2. EbrahimpourKomleh, H. Mathematical basis for use of fractal codes as features / H.EbrahimpourKomleh, V.Chandran, S.Sridharan // Proceedings of Image and Vision Computing. -2002. - Vol.1. - P. 203-228.

3. Jacquin, A. Fractal image coding: review / A.Jacquin // Proceedings of the IEEE. - 1993. - Vol. 81. -№ 10. - P. 1451-1465.

4. Tan, T. Object recognition using fractal neighbor distance: Eventual convergence and recognition rates / T.Tan, H.Yan // Proceedings of 15th International Conference Pattern Recognition. - 2000. - P.781-784.

5. EbrahimpourKomleh, H.An Application of Fractal Image-set Coding in Facial Recognition / H.EbrahimpourKomleh, V.Chandran, S.Sridharan // Lecture Notes in computer science, Biometric Authentication, Springer Ver-lag. - 2004. - Vol. 3072. - P.178-186.

6. Гулаков, В.К. Многомерные структуры данных: монография / В.К. Гулаков, А.О.Трубаков. - Брянск: БГТУ, 2010. - 387 с.

7. Шарабайко, М.П. Быстродействующий алгоритм фрактального сжатия изображений / М.П.Шарабайко, А.Н.Осокин//Изв. Том.политехн.ун-та. -2011. - Т. 318. - № 5. - С. 52-57.

Размещено на Allbest.ru