О свойствах эмпирической решеточной фрактальной размерности изображений

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

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

ОФР обычно применяются в задачах распознавания полутоновых изображений, хорошо моделируемых некоторыми специальными видами поверхностей, - например, фрактальной Броуновской поверхностью (fBs) [4], [3], или само-подобными/само-аффинными поверхностями [3]. Подобные модели изображений определяют основное направление исследований ОФР, вычисленных различными способами, а именно, - нахождение точности, с которой конкретный алгоритм вычисляет известную фрактальную размерность fBs или само-подобной поверхности по ее изображению, и выяснение влияния на точность дискретизации, квантования и разрешения [2], [3], [4]. Инвариантность ОФР к группе преобразований не подвергается сомнению и остается за рамками рассмотрения.

В предлагаемой статье представлены некоторые результаты исследований свойств ОФР, проведенных в рамках другого подхода. По определению “фрактал” - просто ком- пактное множество [1]. Следовательно, фрактальная размерность существует для любого компактного множества. Считая произвольное полутоновое изображение подмножеством участка некоторой поверхности в R3, можно вычислить по нему какую-либо ОФР. При этом возникают следующие вопросы:

• 1.    Каково множество значений ОФР произвольного полутонового изображения?

• 2.    Является ли ОФР произвольного полутонового изображения информативным признаком?

• 3.    Сохраняет ли ОФР произвольного полутонового изображения инвариантные свойства теоретической фрактльной размерноти множества?

2.    АЛГОРИТМ ВЫЧИСЛЕНИЯ ЭРФР

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

Пусть задана матрица полутонового изображения 1т с элементами imy. Изображение 1т будем считать подмножеством поверхности Дх,у), совпадающей с изображением в точках im^ и удовлетворяющей неравенству пш^ (‘^mi+kj+i) ⁵ Л^У) ⁵ /^] ^^mi*kJ⁺^ ^в 0<х+1, /<у<у+1). Расстояние между двумя соседними пикселами по осям х и у в плоскости изображения будем считать равным единице (так же, как и расстояние между соседними уровнями интенсивности по оси z).

Чтобы вычислить ЭРФР полутонового изображения, нужно сначала найти мощности покрытий изображения решетками G^h) с шагами 1/2^А, А=О,...,г единиц расстояния (как в быстром алгоритме “box counting” [5]). Поскольку разрешение изображения ограничено, можно начать вычисление с решетки G^t) с минимальным шагом. Направляющие решетки в области, занимаемой изображением, определяются уравнениями GG) (x=i, y=j), ^i, Z^k\ (y=j, £=kV i=0, .....m-1,/=0,...,и-1, *=!,...,Г-1, Г=2', где 7",- количество уровней интенсивности. Очевидно, что покрытие изображения решеткой (7(0 единственно. Для А>0 существует не одно покрытие изображения решеткой GVt-h\ Чтобы исключить неоднозначность, введем начало координат,- точку (z₀, j^ на плоскости (х,у), через которую проходят вертикальные направляющие решеток G^t-h^ для всех рассматриваемых И. Можно показать, что для каждого фиксированного положения решетки с шагом /-А+1 существует только четыре различающиеся решетки G и следовательно, четыре различных покрытия исходного изображения решеткой с шагом t-h.

Алгоритм вычисляет множество (МО,—. МО)) мощностей покрытия изображения решетками с соответствующими шагами. Затем по некоторому подмножеству точек ((A-f)log2, (A-/) log/V) с использованием метода наименьших квадратов находится прямая, угол наклона которой к оси х и является значением ЭРФР изображения для интервала масштабов, определяемого заданным подмножеством точек. Выбрать интервал масштабов можно нс единственным образом, и, в принципе, можно использовать для этой цели любой подынтервал интервала [О,г]. Путем прямых вычислений можно вывести следующую формулу для £ In NUHi - (m2 +m, )/2)

ЭРФР в интервале масштабов [m ,mj: ЭРФР=———--------------—.

In 2^(z² - (m₂ + mJ² / 4) "4

Если определить элементарную ЭРФРДт^!) как ЭРФР, вычисленную для интервала масштабов единичной длины с началом т,, Дт,+l^logo^ffl^^ , можно для вычисления

6 У /(т, + Мт, - иц - i + 1) ЭРФР воспользоваться формулой ЭРФР=---^—---------^-------—.

(т₂ - пц Кт₂ - ггц + 1 Д/тг, - т, + 2)

Формулы позволяют быстро вычислить значение ЭРФР, однако для изучения ее свойств их недостаточно.

3.    ФРАКТАЛЬНОЕ ПИРАМИДАЛЬНОЕ ПРЕДСТАВЛЕНИЕ ИЗОБРАЖЕНИЯ

Определим 3-мерное бинарное изображение Jm размера тп-^ как матрицу того же размера с элементами ут,^е{0,1}. Объектом 3-мерного бинарного изображения ОЬЦт') назовем подмножество единичных элементов Jm. Преобразуем исходное полутоновое изображение 1т в 3-мерное бинарное изображение Jm(J), пользуясь следующим правилом: утДГ)=1, если min(z/n и^<к < max(zm_{1D м}). На рис. 1(a) изображен одномерный профиль ^J                 Ospsl                   OspsI

Os/sl                   Oskl

Z=f{x,[) функции ?.-Дх,у) для некоторого /, и решетка G(/). Соответсвующее сечение Jm^f) показано на рис.1(6). Черные квадратики соответствуют "1", а белые - "О". (Для простоты предположим, что все профили изображения одинаковы).

Jm(f) - 3-мерное бинарное изображение размера (т-1)(л-1)(Т-1). Индексы i, j элемента jm^/) являются минимальными индексами элементов исходного изображения, принимающих участие в его образовании, а к - номер нижнего из двух соседних уровней интенсивности, формирующих элемент. Очевидно, что покрытие исходного изображения решеткой G(.f) совпадает с Ob(Jm(t)) (множество черных квадратов на рис. 1(6)).

Зафиксируем начало координат S и перенумеруем пикселы исходного изображения так, чтобы пиксел, расположенный в начале координат имел четные индексы / и j. (В результате минимальные индексы Z, у в Jm(f) могут быть равны 0 или 1. Если минимальный индекс по какой-либо оси координат равен 1, можно расширить Jm(,f) в соответствующем направлении, приписывая значение 0 появляющимся дополнительным элементам. Построим Jm(r-l) по правилу ym.JM)= тах(/№,.,„.,2>.,(/)), /6{/т10, i^JeV^.W, где но-z»oj Г-оз вые индексы согласованы с началом координат.

Рис.1.

На рис. 1(в) показаны сечения двух различных

Jm(t-\Y соответствующих двум различным положениям решетки относительно изображения. Всего будет 4 возможных различных 3-мерных бинарных изображения этого уровня, соответствующих четырем различным началам координат. Аналогично Jm(t-h-V) строится по Jm(t-hY Очевидно, что покрытие изображения решеткой б(/-А) совпадает с Ob^t-hY и N(t-h)= I Jm(t-h) I = I Ob(t-h) I. На рис.1, представлены сечения возможных 3-мерных бинарных изображений в плоскости (x,z).

4.    СВОЙСТВА ПРЕДСТАВЛЕНИЯ ИЗОБРАЖЕНИЯ ПИРАМИДОЙ 3-МЕРНЫХ БИНАРНЫХ ИЗОБРАЖЕНИЙ

Построенное представление полутонового изображения пирамидой 3-мерных бинарных изображений обладает некоторыми свойствами, которые позволяют оценить свойства ЭРФР.

Определим для каждого jm^t-h) индексы u,v, l/-«|sl, Ij-vkl тех его соседей, с которыми он объединятеся при образовании одного элемента Jm(t-h-\Y Направления на этих соседей образуют множество направлений, согласованных с началом координат, для данного элемента. Дилатацией 3-мерного бинарного изображения Jm(t-hY согласованной с началом координат, назовем преобразование Jm(t-h) в 3-мерное бинарное изображение D^Jm^t-h^Y D^mjj^t-h^max^d^'mj^Y jm,_)kY ^r^^e для каждого jn^t-h) d_s является его множеством направлений, согласованных с началом координат. Результат дилатации, согласованной с началом координат 5,, показан на рис.1 (б) (множество черных и серых квадратиков). 3-мерное бинарное изображение может быть продолжено вдоль осей х , у и £ приписыванием значения “0” дополнительным элементам.. Определим расширенную дилатацию ZX_s(/m(/-A)) как дилатацию 3-мерного бинарного изображения Jm(t-hY вычисленную также и для дополнительных элементов, имеющих соседей в Jm(t-hY

Определим функцию разреженности 3-мерного бинарного изображения, согласован-м l^^(Z-A))!

ную с началом координат S, как gj(Z-A)= '

Можно показать, что для любого 5 при фиксированных Z-A, А, т, п, l%^t-h) с учетом того, что для любого А и любого Jm(t-hY построенного по полутоновому изображению с использованием описанного выше алгоритма, Ob(t-hi) представляет собой связное множество без дыр.

Следующим параметром 3-мсрного бинарного изображения, использующимся в оцен ках свойств ЭРФР, является плотность Jm(t-h) при некотором начале координат:

P^JmU-h^-m^t.h^t-h>

где m^t-h\ n^t-h) - размеры изображения после дилатации, проведенной для вычисления g^Z-A)). В терминах функции разреженности и плотности связь между \Ob(t-h)\ и |O6(z-A-l)l задается неравенством 2

Ny-W -h ) _sN., „ . J^^^L»

Неравенство (1) следует непосредственно из алгоритма построения пирамидального представления.

5.    СВОЙСТВА ЭРФР

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

5.1.    Величина ЭРФР

• 1 .Для любого полутонового изображения и любого интервала масштабов ЭРФР<3. 2

  • 2.Е сли g.s- (t-h)               V ^/-^ ^в данном интервале масштабов.то ЭРФР>2.

З.Если g5 (Z-A)>2, то jVt-h^l.

^^^-^-^jfchY) ^^>Х‘

Представленные оценки вычислены непосредственно по формуле (1) и определению

Приведенные результаты позволяют сделать вывод, что по крайней мере в терминах элементарных ЭРФР полутоновые изображения могут проявлять свойства простых поверхностей, самоподобных поверхностей и топологически одномерных функций. Последний факт представляется достаточно неожиданным. Приведем пример подобного изобра-жения. Вычислим ЛО Для квадрат ного изображения размера 2^+1, у которого пикселы с координатами (4/+3, 4у+3), /=0,1, ...,/=0,1,...имеют интенсивность (2^+1), а ос тальные - 0. Изображение схематически представлено на рис.2(a), черными кружками от мечены пики интенсивности. Пикселы расположены в узлах решетки. Справа показаны соответствующие уровни интенсивности. На рис,2(6) представлен “вид сверху” соответствующего Jm(t). Столбики справа показывают мощности покрытий в различных областях. Легко подсчитать, что М0=22/"2(3+2*). На рис.2(в) представлен вид сверху изображения Jm(z-l) при начале координат в пикселе (0,0), а на рис.2(г) - при начале координат в пикселе (1,1). Простые вычисления показывают, что в первом случае ^Г-1)=22/'4(3+2А'’1), а во втором -    М/-1)—22/ 22*"| + 1+2/"1.    Следовательно, /S|(t)=    2+log2(2-3/(3+2A’"*)),

^/0~2+1оз₂1.571>2.5,^₂(t)= log₂(l y^M-Q'+Y )’ ^(O^+k^l -534<1.7.

5.2.    Влияние поворотов и сдвигов на ЭРФР

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

Вычислениями с использованием неравенства (1) можно показать, что:

• 1.    Если g$_x(t-h) и gs^t-h') - значения функций разреженности для двух начал координат, таких, что Jm_SxU-h>=Jm_sAt-h\ и ^ =е, е >1, то 657

• 2.    Если g_Sx(,t-h) и gs^-h) - значения функций разреженности для двух начал коорди--А), и ⁼е, е >1, то

  нат, таких, что Jm_SxU-hyJm_S1 и N₅₂(/-A)=yN_5|(Z

  
  
6.    ПРИЛОЖЕНИЯ

2                                         2

Полученные результаты являются оценками изменений значений ЭРФР изображения при “физическом” сдвиге всего изображения относительно фиксированного положения решетки. В реальных задачах распознавания изображений под сдвигом понимают другой процесс: смещение одной части изображения (“объекта”) относительно другой части (“фона”). Очевидно, что сдвиг в таком понимании не эквивалентен изменению положения изображения относительно решетки. Однако при реальном сдвиге отношения соседства внутри объекта и фона сохраняются (они меняются только на границах), площади объекта и фона также не меняются. Таким образом, реальный сдвиг примерно соответсвует различному изменению положения частей изображения относительно решетки. Поэтому полученные оценки дают некоторое представление о поведении ЭРФР при сдвиге на изображении. Аналогичная ситуация возникает и в случае поворота. Реально существуют два типа поворота: поворот всего изображения и поворот объекта относительно фона. В первом случае, в результате специфики алгоритмов поворота, размер результирующего изображения больше размера исходного, и значения интенсивностей его элементов являются результатом усреднения по некоторой окрестности прототипа. Во втором случае размеры изображения не меняются, а интенсивность элементов повернутого объекта и появившихся, ранее скрытых, участков фона, также отличаются от интенсивностей элементов исходного изображения. Изменение размеров изображения в первом случае в представленных оценках не учитывается. Остальные изменения аналогичны случаю сдвига, и, следовательно, поскольку отношения ближайшего соседства пикселов сохраняются и в случае поворота, можно считать, что представленные оценки позволяют до некоторой степени оценить влияние поворотов на ЭРФР. Следует также отметить, что повороты всего изображения на 90°, 180° и 270° полностью соответствуют помещению начала координат в пикселы (т-1,0).

(т-1,л-1) и (0,л-1).

В данном разделе кратко представлены результаты экспериментов, направленные на выяснение возможностей применения ЭРФР в качестве признака для описания дактилоскопических отпечатков пальцев (ДОП) в задаче их идентификации [6]. ЭРФР были вычислены для 120 полутоновых изображений ДОП (база данных содержала полные дактилоскопические карты трех человек, по 4 изображения на ДОП с различными искажениями, такими, как сдвиг, поворот, сплющивание и т.д.). Размер изображений 436-416. Изображения состоят частично из изображения гладкой пластины (практически черный фон) и изображения непосредственно ДОП. Эксперименты показали высокую устойчивость ЭРФР к расположению начала координат (разница в значениях ЭРФР, вычисленных при разных началах координат, была порядка 0.001). Значения ЭРФР, представленные в таблицах 1.2,3 получены для начала координат в пикселе с i=j=Q.

Для каждого изображения ДОП метод наименьших квадратов применялся к 6 и 3 точкам из набора ((A-/)log2, (A-r)logM, а также вычислялось множество элементарных ЭРФР. Типичные значения ЭРФР представлены в таблицах 1, 2, 3. В таблицах 2 и 3 приведенные значения ЭРФР относятся к изображениям ДОП одноименных пальцев 3-х человек.

Таблица 1.                   Таблица 2.                   Таблица 3.

Элементарные ЭРФР ЭРФР, вычисленные по 6 ЭРФР, вычисленные по 3 ________________________ _______ точкам                     точкам

N	1	2	3	4
	2.700	2.907	2.807	2.807
fl	2.299	2.222	2.373	2.259
	2.342	2.293	2.350	2.333
	2.409	2.416	2.430	2.422
fs	2.445	2.424	2.386	2.412
	2.330	2.307	2.311	2.289
fl	2.167	2.161	2.164	2.167

N	fd	N	fd	N	fd
11	2.449	21	2.463	31	2.508
	2.455		2.472		2.507
	2.449		2.498		2.508
	2.468		2.469		2.524
av.	2.455	av.	2.476	av.	2.512

N	fd	N	fd	N	fd
11	2.535	2' .	2.539	31	2.591
	2.525		2556		2.584
	2.512		2.602		2.584
	2.538		2.559		2.597
av.	2.528	av.	2.564	av.	2.589

Результаты экспериментов позволяют заключить, что ЭРФР является информативным средством описания изображений ДОП.

ЗАКЛЮЧЕНИЕ

Основной целью работы было выяснение свойств ЭРФР как средства описания произвольных полутоновых изображений в задачах распознавания.

Показано, что множество значений ЭРФР полутоновых изображений шире, чем множество возможных значений фрактальной размерности поверхности. Значения ЭРФР, большие 2, кажутся вполне естественными, так как поверхность может быть достаточно грубой, даже если ее теоретическая фрактальная размерность равна 2. Тот факт, что при данной модели изображения значения ЭРФР могут быть меньше 2, не выглядит очевидным. Но, как явствует из примера в разделе 5.1, изображения с такими значениями ЭРФР существуют, так что можно говорить о классе изображений со свойствами топологически одномерных функций. Представляется, однако, что этот класс очень узок в классе всех по- лутоновых изображений, и что это отклонение может проявляться только для некоторых расположений начал координат, и только при вычислении элементарных ЭРФР с использованием двух последних точек из набора ((A-/)iog2, (A-01og?V). При использовании центральной части графика, или всех точек, подобное отклонение не имеет места ни при каком расположении начала координат. Данное предположение до некоторой степени подтверждается результатами исследований свойств ЭРФР, в настоящее время еще не законченными. Были доказано, что:

• •относительная плотность 3-мерного бинарного изображения, в основном, не уменьшается с увеличением шага решетки (возможное небольшое уменьшение связано только с размерами изображения);

• •после того, как 3-мерное бинарное изображение на некотором уровне пирамидального представления достигает некоторого предельного значения плотности, величины элементарных ЭРФР, вычисленные для соответствующих масштабных интервалов, не меньше 2 при любом расположении начала координат;

•чем больше значение функции рассеяния для некоторого начала координат на уровне t-h, тем существенне увеличивается относительная плотность 3-мерного бинарного изображения на уровне t-H—Y, т.е., чем разреженнее объект Jm(t-h), тем быстрее растет относительная плотность.

Вместе эти факты позволяют предположить, почему при использовании срединных масштабных интервалов при вычислении ЭРФР ее значение >2 для всех расположений решетки: относительная плотность растет достаточено быстро и достаточно быстро достигает критического значения. Следует также отметить, что малые значения ЭРФР для некоторого расположения начала координат имеют место только в том случае, если существует “противоположное” начало координат, при котором значение ЭРФР достаточно высоко, и наоборот (это означает, что при одном расположении решетки изображение ведет себя, как одномерная функция, тогда как при другом, “противоположном”, - как очень “грубый фрактал"). Причиной такого поведения является наличие на изображении регулярно расположенных всплесков интенсивности на однородном фоне. Такие изображения назовем “регулярными анизотропными изображениями”.

Из примера в разделе 5.2. видно, что в результате сдвига множества пиков интенсивности на регулярном анизотропном изображении на два пиксела влево и вперед значение элементарной ЭРФР, вычисленной по двум наиболее мелким масштабным уровням при начале координат в пикселе (0,0) равно значению соответствующей ЭРФР исходного изображения при начале координат в пикселе (1,1) (и абсолютная величина разности между ними > 0.8). Такой сдвиг эквивалентен повороту исходного изображения на 180°. Пример демонстрирует, что ЭРФР изображений этого класса не инвариантна к сдвигам и простым поворотам. Тем не менее, если ЭРФР вычислена по другим масштабным интервалам, она проявляет высокую инвариантность к сдвигам и поворотам для всех изображений. Объяснением этого служат приведенные выше факты и оценки влияния положения решетки на величину ЭРФР.

Алгоритм вычисления ЭРФР, основанный на нахождении I ОА(/-А)| на каждом уровне пирамиды, существенно использует тот факт, что Ob(t-h) - связный и без дыр на каждом уровне пирамидального представления (это позволяет на каждом уровне запоминать индексы к только минимального и максимального элемента для каждого Ob-^t-h^Y Сложность алгоритма - O(m,nY где О«т (nY

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

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