АНАЛИЗ ВИДЕОИНФОРМАЦИИ НА ОСНОВЕ ФРАКТАЛЬНОЙ КЛАСТЕРИЗАЦИИ
УДК 621.397 АНАЛИЗ ВИДЕОИНФОРМАЦИИ НА ОСНОВЕ ФРАКТАЛЬНОЙ КЛАСТЕРИЗАЦИИ
© 2010 г. И. К. Коханенко, доктор техн. наук Ростовский военный институт ракетных войск, Ростов-на-Дону E-mail: kik112@yandex.ru
Обосновывается алгоритм анализа изображения для его автоматического распознавания, который рассматривается в статье с точки зрения формализации выделения кластеров либо постоянной, либо подобной интенсивности сигнала, их количества и размеров, двухуровневого принятия решений. Такой подход базируется на гипотезе фрактальности, которая состоит в предположении о степенной зависимости числа пикселов постоянной интенсивности в кластере от его ранга и фрактальном пространственном распределении пикселов в самом кластере. Обоснование гипотезы связывается с гармонией разнообразия и устойчивости изображения как системы. Рассмотрены особенности двухуровневого алгоритма автоматического распознавания сравнением с эталоном. Приведен пример распознавания изображения по наблюдаемой оптической картине. Изучены особенности подобного подхода при анализе видеоинформации на основе карт Кохонена.
Ключевые слова: фрактал, распознавание, видеоинформация, кластер, инвариант, интенсивность, нейросеть, морфологический анализ, аномальная диффузия.
Коды OCIS: 100.4996, 100.5010
Поступила в редакцию 11.02.2010
Введение
В экспериментальной психологии показано, что наиболее информативными при распознавании изображений являются не значения яркостей объектов, а характеристики их границ – контуров. Это положение используется во многих алгоритмах анализа видеоинформации, в морфологическом анализе, в автоматической сегментации текстурированных изображений, в самоорганизующихся кластерных картах Кохонена. При этом в измерительной информации находятся симметрии, выражающиеся в инвариантности формы объекта к множеству преобразований, типичных для условий измерений, и приводящие к кластерам инвариантов – однородным по характерным признакам областям. Это основные внешние черты объекта, они связаны с неизменными свойствами и определяют его форму. Типичными в множестве преобразований являются изменения оптических свойств (цвет, текстура) и освещения. В ситуациях, когда оптические свойства и освещение являются локально однородными, кластеры постоянной яркости можно считать инвариантами относительно указанных изменений и базой для распознавания.
Полагая, что получаемые изображения имеют подобные инварианты, можно представить модель изображения в виде двумерной матрицы R = Nx × Ny пикселов, каждая строка которой задается последовательностью пар чисел: интенсивностью принимаемого сигнала I и числом элементов строки матрицы n, имеющих интенсивность I = [(I1, n1), (I2, n2),…,(Im, nm)], ∑ni = Nx. Такая модель измеренного изображения совпадает со следующим его кусочно-постоянным описанием:
f(x, y) = ∑Iiχi(x, y), i=1, 2, … m,
(1)
(x, y) ∈ Аi → χi(x, y) = 1, (x, y) ∉ Аi → χi(x, y)=0,
где m – количество кластеров Аi с постоянной интенсивностью; в том числе, один из кластеров есть фон – Imχm(x, y). Подобное описание модели достаточно полно обосновано в работах [1, 2].
Далее, если следовать морфологическому подходу, строится форма объекта в виде проектора Pfg – проекции изображения g на множество форм V(f) или правило, по которому изображению g из гильбертова функционального пространства L2(X) ставится в соответствие некоторое изображение ϕ = Pfg. В соответствии с работами [1, 2] под формой изображения понимается
“Оптический журнал”, 77, 8, 2010
47
множество изображений с упорядоченной интенсивностью
V(f) = [f(x, y) = ∑Iiχi(x, y) + Imχm, (2) (x, y) ∈ X, –∞ < Im ≤ Ii < ∞, i = 1, 2, …, (m – 1)].
Содержательно искомое правило распознавания должно выявить то изображение из множества V(f), которое было бы наиболее близким к изображению g. При этом, если
ϕ= Pfg= g,
(3)
то считается, что объект распознан, т. е. можно подобрать условия регистрации, при которых объект породит изображение g. Множество V(f) полагается выпуклым и замкнутым, т. е. проектор Pf определяется из условия минимума расстояния от изображения до формы, что приводит к процедуре построения Pf как усреднения изображения в каждом кластере постоянной интенсивности [1]. Итак, в каждом кластере находится средняя интенсивность, которая принимается в нем постоянной. Но при этом в контексте задачи распознавания изображения немаловажно знать, как распределяется эта постоянная интенсивность в каждом кластере, сколько пикселов располагается в различных его подобластях. Очевидно, что такое распределение пикселов в кластере является характеристикой изображения. Поэтому, не изучая такие характеристики, устройство узнавания теряет информацию.
В таком алгоритме есть еще одна неопределенность: неясно как определять кластеры постоянной интенсивности Ai, сколько их должно быть и каковы их размеры. Обычно рекомендуется отвечать на подобный вопрос так: полагая, что области изображения одинаковой интенсивности сформированы модулями объекта с идентичными физическими (оптическими, акустическими и др.) и геометрическими свойствами, задавать кластеры Ai по расположению однородно отражающих граней или границ относительно наблюдателя. Однако физически такое решение не всегда выполнимо, и, кроме того, часто постоянство интенсивности достаточно условно, как правило, желаемое постоянство приближенно представляет некоторое множество значений интенсивности в сравнительно небольшом диапазоне.
Аналогичные вопросы характерны и для алгоритмов, реализуемых в нейросетях, в частности, в картах, в слоях нейронов Кохонена. Там кластеры – это не области постоянной интенсивности,
а области с подобным (близким) пространственным распределением интенсивностей (признаков). И при этом в задаче распознавания остаются вопросы первоначального выделения на изображении кластеров – на каких основаниях и сколько. Необходимы основания для назначения приблизительного числа кластеров, без которых структуру слоя Кохонена синтезировать нельзя. При распознавании немаловажно знать и фрактальную размерность пространств “интенсивность – ранг интенсивности” или “число входных векторов – ранг кластера” для каждого кластера. Без такой оценки нейросетевое устройство распознавания теряет информацию.
1. Гипотеза фрактальности и форма изображения
Для преодоления отмеченных выше противоречий целесообразно дополнить зависимость I(x, y) связью интенсивности с количеством пикселов в области Ai. Действительно, для многих реальных объектов каждый кластер Ai будет иметь характерное для него число ni пикселов постоянной интенсивности Ii. Итак, надо найти зависимость ni(Ii). Учитывая, что с ней связана форма изображения, естественно искать такие зависимости в среде систем, которые обладают свойствами разнообразия и устойчивости, так как разнообразие формы является необходимым условием полноты адекватной проверки по правилу (3), а устойчивость – необходимым условием сохранения ее характеристик и наблюдаемости. Понятие разнообразия обычно связывается с энтропией и информацией. В состоянии равновесия (экстремум энтропии) при единственном ресурсе (усилии) задача на условный экстремум приводит в зависимости от характера ограничений формы ресурсами к различным ранговым распределениям: Гиббса, Ципфа–Парето, “разломанного стержня” Макартура [3]. В статье приведен пример только распределения Ципфа–Парето pI = μI–1/d–1, где полагается, что потребности кластеров в ресурсe пропорциональны lnI. Например, в соответствии с физиологическим законом Фехнера потребность усилий по воспроизведению слова ранга I в тексте пропорциональна lnI, и поэтому частота появления в тексте слова ранга I фрактально связана с рангом. Здесь μ = р1, p1 > p2 >…> pm, m – число кластеров (видов) в системе (сообществе), d – в термостатике трактуется как величина, обратная температуре, а в законе Ципфа–Парето d есть фрактальная размерность.
48 “Оптический журнал”, 77, 8, 2010
Как правило, считается, что разнообразие системы тем больше, чем больше в ней кластеров и выше выравненность E = (mpi/lnpi)/i – отношение наблюдаемого разнообразия к максимальному, т. е. равномерность распределения кластеров в системе (E = 1 при равном распределении кластеров). Здесь величина mpi/lnpi известна как индекс Шеннона, типичный диапазон его изменения [1,5–4,5].
Оценка свойств этих законов (плотности, энтропии, выравненности, индекса Шеннона) показывает, что наибольшим разнообразием, а следовательно, совершенством и стабильностью, обладают системы, структура которых связана с распределениями Ципфа–Парето и Макартура. Причем, наибольшее разнообразие у систем, для которых характерно последнее распределение. Если первый закон имеет известное прямое отношение к фрактальным структурам, то относительно закона Макартура это не очевидно. Изучая механизм формирования распределения Макартура, можно показать, что оно сводится к ранговому распределению Ципфа–Парето x(r) ~ r–β, β = 1/(d–1), т. е. закон Макартура тоже относится к классу фрактальных распределений.
Полученные решения по разнообразию подтверждаются и при использовании идей теории информации. Очевидно, характер восприятия системой сигналов внешней среды зависит от ширины полосы частот сигналов, к которым чувствительна система и ее элементы. При этом, чем шире полоса частот, тем больше не только разнообразие, но и ошибок в восприятии сигналов внешней среды и больше вероятность неустойчивости системы. Таким образом, как разнообразие системы, т. е. количество кластеров и элементов в них, так и неадекватность ее поведения, а следовательно, и вероятность ее деградации зависят от ширины полосы частот сигналов, воспринимаемых ею и ее кластерами и элементами. В контексте изучаемого интересно сопоставить ширину полос пропускания систем “ранг кластера – число пикселов одинаковой интенсивности в нем” с различными законами распределения. Для этого следует пояснить понятие ширины полосы пропускания применительно к изучаемой кластерной модели изображения. Ранговому распределению Ципфа–Парето соответствует частота, связанная с фрактальной размерностью d и рангом r кластера следующим соотношением [3]: ωr = = С[exp(1/d–1)]–lnr, C = const. При этом полагается линейная зависимость числа пикселов
в кластере и частоты. Отсюда ранговое распределение Ципфа–Парето может быть записано в виде n(r) = n(1)r–1/d – 1, 1/d – 1 = lnν, ν = = (ωr/ωr + 1)–ln(r + 1). Отношение Δ2 частот кластеров i и (i + 1) для закона Ципфа–Парето равно Δ2 = νln(r + 1), ν = exp(1/d–1). Аналогично для законов Гиббса (отношение Δ1) и Макартура (отношение Δ3): Δ1 = ν, Δ3 = ln(r + 1). Из приведенных зависимостей следует, что для рангов r ≥ 2 наибольшая ширина полосы частот у закона Ципфа–Парето и наименьшая у закона Макартура. Это согласуется с характером разнообразия систем, для которых характерны изучаемые законы распределения: фрактальность системы способствует ее устойчивости за счет обеспечения высокой степени разнообразия и приемлемой зашумленности при рациональной ширине пропускания.
Итак, системы, подчиняющиеся закону Ципфа–Парето, имеют второй ранг по разнообразию при наибольшей полосе пропускания. Системы, подчиняющиеся закону Макартура, имеют первый ранг по полосе пропускания и наибольшее разнообразие. Системы, подчиняющиеся закону Гиббса, имеют среднюю полосу частот и наименьшее разнообразие. Выше показано, что системы, подчиняющиеся законам Макартура и Ципфа–Парето, относятся к классу фрактальных. Следовательно, фрактальность системы способствует ее устойчивости за счет обеспечения высокой степени разнообразия и приемлемой зашумленности при рациональной ширине пропускания. Поэтому для устойчиво развивающейся системы ее фрактальная структура является естественной. Следовательно, рационально выбрать в качестве зависимости между размерами кластеров Aj (количеством пикселов nj постоянной интенсивности) и величинами соответствующих постоянных интенсивностей Ij фрактал, т. е.
nj(Ij) = αAα/Ijd, d = α + 1,
(4)
где параметры определяются по соотношениям [4]: для размерности d это
d1 = ln(G/A),
(5)
G − среднее геометрическое наблюдений интенсивностей, исключая фон, для A это A1 = = min{I1, I2, …, Im – 1}.
Таков смысл гипотезы фрактальности, делаю-
щей определенными выбор числа кластеров и их
размеры. Теперь выражение (2) для множества
форм изображения приобретает вид
“Оптический журнал”, 77, 8, 2010
49
V(f) = {f(x, y)=∑[αAα/nj]–d + Imχm,
(6)
(x, y) ∈ X, d > 0, j = 1, 2, …, (m – 1)},
α = d – 1. Опять получаем форму кусочно-постоянного изображения только в виде фрактала. Следовательно, для определения проекции Pfg необходимо усреднять наблюдаемое изображение g(x, y) в каждом из кластеров Ai постоянной интенсивности изображения f [1, 2]. Из выражений (5) и (6) видно, что множество форм изображения имеет один параметр – фрактальную размерность d. Необходимо оценить d для полученной проекции Pfg, т. е. оценить фрактальную размерность системы: “средняя интенсивность – число соответствующих ей пикселов в кластере”. Равенство полученной фрактальной размерности этому параметру формы будет эквивалентно выполнению правила (3), т. е. совпадению наблюдаемого изображения с эталоном. Действительно, I1 ≈ I1(A, d, n1), I2 ≈ I2(A, d, n2), …, Im – 1 ≈ Im – 1(A, d, nm – 1) – – (m – 1) есть уравнения при двух (A, d) неизвестных, а если учесть, что A = min{I1, I2, …, Im – 1}, то (m – 1) уравнение при одной (d) неизвестной. Очевидно, при одинаковых интенсивностях у кластеров эталонного и наблюдаемого изображений равенство их фрактальных размерностей возможно лишь при равном числе пикселов ni.
2. Алгоритмические особенности процедур кластеризации
Следуя фрактальной гипотезе, задачу распознавания удобнее решать в следующей последовательности. В случае, когда изображение представлено матрицей с элементами в градациях серого, из шкалы выделяются интервалы (кластеры) значений интенсивностей в диапазоне 1–256, на которых интенсивность принимается равной соответствующему среднему значению, например, в интервале 180–256 среднее значение интенсивности равно 218. Развивая гипотезу фрактальности, можно определить регулярную процедуру назначения диапазонов указанных кластеров. Действительно, при изучении зависимости наибольшей интенсивности в кластере Im от ранга кластера r использование сказанного в разделе 1 относительно ширины полосы пропускания систем с разными законами распределения с позиций наибольшей информативности приводит к целесообразности применения гиперболической зависимости, т. е. закона Ципфа–Парето. При использовании шкалы “оттенки серого”
эта зависимость имеет вид Im = 256/rd, т. е., чем больше интенсивность, тем значительнее размеры кластера. Кластеры постоянной интенсивности, например, при d = 1, могут иметь границы 256–128, 128–85, 85–64, 64–51. Фрактальная размерность d определяется, исходя из физически обоснованных значений интенсивности сигнала для фона If и количества кластеров m, т. е. d = (ln256 – lnIf)/lnm. Далее рассчитывается фрактальная размерность системы кластеров с соответствующими постоянными интенсивностями. Как показано ранее, совпадение кластеров и фрактальных размерностей формы и проекции свидетельствует о выполнении правила (3), т. е. совпадении наблюдаемого изображения с эталоном. Но модель (6) на основе гипотезы фрактальности может быть расширена детализацией анализа. Действительно, связь I(n) интенсивности с числом пикселов в кластере, которая описывается выражением (6), целесообразно структурировать для учета естественной неравномерности расположения пикселов постоянной интенсивности в каждом кластере, что было отмечено во введении. Если выделить в кластере отдельные непересекающиеся подобласти, то число пикселов постоянной интенсивности в каждой из них ранжируется, т. е. n(r). После чего выражение (6) трансформируется в более подробную модель – модель второго уровня, включающую (m – 1) моделей (форм) кластеров
nj(Ij) = {nj(Ij(x, y)) = ∑rjk–1/dj – 1(A/dj – 1)1/dj – 1,
(x, y) ∈ X, j=1, 2, …, (m – 1),
(7)
k = 1, 2, …, mj},
где mj – количество подобластей в кластере. Для уточнения общего результата узнава-
ния определяются проекторы Pfgj для каждого из (m – 1) кластеров и оцениваются их фрактальные размерности dj. Нахождение проекторов кластеров проводится следующим образом. В кластере выделяются по осям x и y интервалы Δx и Δy. В каждом интервале j-го кластера (j = 1, 2, …, m – 1) находится число оказавшихся в нем пикселов интенсивностей njk, k = 1, 2, …, mj, здесь mj – число подобластей в кластере j. Подобласти ранжируются в порядке убывания в них числа пикселов интенсивности. Далее оценивается фрактальная размерность кластера из известного рангового соотношения для закона Ципфа
50 “Оптический журнал”, 77, 8, 2010
n(r) = B/r1/d – 1, B= (A/d–1)1/d – 1,
в соответствии с которым несложно найти d = dj, построив прямую
lnn=lnB – (1/d – 1)lnr.
(8)
Здесь r – ранг подобласти в кластере, А – наименьшее значение интенсивности.
При найденных фрактальных размерностях d и dj (j = 1, 2, …, (m – 1)) решение принимается на основе теоретических результатов динамической фрактальной геометрии [4, 5]. Смысл, который вкладывается в определение “динамической”, состоит в следующем. В теории фракталов полагается, что фрактальные объекты обнаруживают пространственное самоподобие, а динамические фракталы (фрактальные временные ряды) имеют статистическое самоподобие во времени. В основе обобщенного изучения самоподобия лежит замена временной динамики на пространственную, в кинетических уравнениях которой производные по времени заменяются производными по пространственным координатам. В работе [5] показано, что модифицированные заменой времени на координату x уравнения аномальной диффузии субдиффузионного и супердиффузионного типов в дивергентной форме имеют соответствующее максимуму энтропии изокоординатное (∂f/∂x = 0) решение вида f ~ h–d, где d – фрактальная размерность, h – характеристика поверхности (изображения). Теперь, следуя работе [4], можно записать последовательность уравнений вида ∂f1/∂x = af1, ∂f2/∂x = bf2, из которых получается фрактал f1 ~ f2–d, где f2 = h, d = a1/a2. Нельзя не заметить подобную последовательность в изучаемом случае, когда число ni в i-м кластере постоянной яркости Ii равно ni ∼ Ii–d, а с другой стороны, число пикселов есть сумма ni∼∑Bj/rj1/di – 1 (суммирование по индексу j ведется от j = 1 до j = k, где k – число интервалов в кластере). Поэтому справедливо соотношение
Ii–d ∼ ∑Bi/r1j /di – 1,
(9)
где i = 1, …, m – 1, rj – ранг в j-м интервале i-го кластера.
Равенство фрактальных размерностей кластеров эталона и наблюдаемого изображения свидетельствует о подтверждении выполнения правила (3), т. е. совпадении наблюдаемого изображения с эталоном. Отличия некоторых из них или всех требуют дополнительного содержательного анализа. Эти отличия могут быть полезны при узнавании, визуализации аномалий, дефектов в микроэлектронике, охранных системах и дру-
гих приложениях. Соотношение (9) свидетельствует о функциональной зависимости фрактальных размерностей d-изображения и di-кластеров постоянной интенсивности. Это указывает на недостаточность вывода о совпадении эталонного и наблюдаемого изображений только по их фрактальной размерности (3). Для получения более достоверного решения необходимо оценивать фрактальные размерности кластеров.
Таким образом, морфологический анализ изображения на основе гипотезы фрактальности включает два уровня. Первый основывается на базовом соотношении (6) и сравнении фрактальных размерностей формы и наблюдаемого изображения и, наконец, второй уровень предполагает сравнение ранговых фрактальных размерностей кластеров постоянной интенсивности (7). На каждом уровне можно принимать решение о распознавании; очевидно, достоверность решения возрастает при увеличении уровня.
Как показано выше, число кластеров зависит от интенсивности фона If и фрактальной размерности. В диапазоне d = 1–3 и If = 10–50 число кластеров изменяется примерно от 2 до 25. Количественное изучение множества изображений показывает, что для отражения специфики изображения достаточно 1–2 кластеров, как правило, не более 5. Пятый кластер в градациях серого соответствует постоянной интенсивности, равной примерно 20. Если воспользоваться классической формулой Шеннона, то получается, что в трех кластерах содержится 0,75, в одном – 0,15 долей информации об изображении, содержащейся в 5 кластерах. Это свидетельствует о наличии ядра изображения – одно-, двух-, пятияркостного ядра. Относительно вариаций оптических свойств ядро есть инвариант, описывающий видимую картину. Указанный инвариант – это главное, наиболее существенное в изображении, это сжатая форма изображения. Такое утверждение наиболее адекватно для однородных изображений, т. е. изображений, имеющих мало существенных элементов (например, лица – нос, глаза, уши). Подтверждением тому является рис. 1, где для сравнения приведены два варианта изображения одного объекта. Если существенных элементов в изображении несколько, то при уменьшении числа кластеров информация теряется значимо.
3. Особенности нейросетевого анализа
Интерпретация видеоинформации, когда затруднено использование эталонов, часто осуще-
“Оптический журнал”, 77, 8, 2010
51
ствляется с использованием различных алгоритмов кластеризации. Задача нейросетевого анализа видеоинформации рассматривается здесь применительно к слоям Кохонена [6], где кластеры – это не области постоянной интенсивности, а области с подобным (близким) пространственным распределением интенсивностей (признаков). При этом в анализе изображений остаются прежние вопросы первоначального выделения на изображении кластеров. Опять-таки, в контексте распознавания изображения немаловажно знать фрактальную размерность пространства “интенсивность – ранг интенсивности” в каждом кластере. Не оценивая указанную фрактальную размерность, нейросетевое устройство распознавания теряет информацию.
Наличие ядра изображения, отмеченное в разделе 2, приводит к возможности сжатия информации путем фрактальной кластеризации. Поэтому целесообразно перед формированием структуры слоя Кохонена провести фрактальную кластеризацию изображения по методике морфологического анализа, описанной в разделе 1. В этом случае в связи со сжатием информации, характерной для фрактальной кластеризации, в дальнейшем входные векторы слоя Кохонена будут содержать меньшее число градаций интенсивностей, что упрощает последующую за фрактальной процедуру нейрокластеризации, уменьшая количество циклов обучения.
Синтезированная в соответствии с обучающими векторами и фрактальной кластеризацией архитектура сети Кохонена содержит некоторое количество кластеров, в каждом из которых после нейроанализа нейронами-победителями окажутся нейроны из подмножества входных векторов изображения. На этом в традиционных алгоритмах заканчивается задача. Но очевидно, что при автоматическом распознавании изображения такое окончание из-за отсутствия учителя в сетях Кохонена, как правило, не приводит к результату. Для распознавания изображения учитель–эталон необходим. Поэтому полученную топологию карты Кохонена в задаче распознавания изображения необходимо проанализировать. Для этого в каждом кластере проводится оценка фрактальной размерности dni пространства “число входных векторов – ранг кластера”. При этом с точностью до обозначений используется выражение (8). Такая же задача решается для эталона и совпадение фрактальных размерностей эталона и изображения свидетельствует о распознавании.
4. Пример Анализируемая видеоинформация представлена в форме статических цифровых полутоновых изображений (наблюдаемого – рис. 1 и эталонного – рис. 2) размером 300×110 элементов (пикселов) и с N = 256 градациями интенсивности (градациями серого). Изображения трансформируются в соответствующие матрицы. Сравнение эталонного изображения в трехкластерном варианте с натурным изображением объекта на рис. 2 не приводится, но оно во многом подобно рис. 1. Фрактальная размерность эталонного изображения в трехкластерном варианте, рассчитанная по соотношению (8), равна 3,1. Аналогично определенная для распознаваемого изображения (рис. 1) фрактальная размерность равна 2,4. Отсюда следует, что указанные изображения не идентичны. Подтверждением этого является результат второго уровня анализа – оценки фрактальных размерностей кластеров двух сравниваемых изображений. Для эталона они получились равными 2,5, 1,5, 1,2, а для распознаваемого изображения соответственно 2,0, 1,7, 1,6. Несовпадение очевидно. Пример иллюстрирует работоспособность алгоритма и высокую информативность фрактальной размерности пространств генерируемых кластеров инвариантов как критерия распознавания. Он не позволяет получить представление о такой важной характеристике алгоритма, как вероятность правильного распознавания на выборках изображений. Аналитических соотношений для оценки такой вероятности автор не получал. Но опыт компьютерного распозна-
(а) (б)
Рис. 1. Изображение (а) и его копия (б) при трех кластерах.
Рис. 2. Эталонное изображение в трехкластерном варианте.
52 “Оптический журнал”, 77, 8, 2010
вания разнообразных изображений с использованием предложенного алгоритма накапливается. Он показывает, что достоверность решения в одноуровневом анализе примерно равна 60–80%. Эксперименты по распознаванию не проводились для условий сильных искажений, будь то неудачный ракурс или плохое освещение. При переходе к двухуровневому анализу достоверность возрастает примерно на 15–20% в зависимости от количества кластеров и пикселов в них. Кроме того, 10% отличий в значениях фрактальных размерностей двух изображений приводят к относительному расстоянию 45–15% между изображениями в характерной для гильбертова функционального пространства метрике при изменении числа пикселов от 3 до 100. Эти результаты получены по 30 экспериментам для каждого типа изображений (местности, объектов техники, людей).
Заключение
Предлагаемые процедуры для автоматического двухуровневого кластерного анализа изображений базируются на обоснованной гипотезе о степенной зависимости количества пикселов постоянной интенсивности в кластерах инвариантов от ранга и фрактальном пространственном распределении пикселов в каждом кластере. При этом в отличие от традиционных подходов появляется возможность формализации оценки как количества кластеров, так и их размеров, а изучение пространственного распределения постоянной интенсивности в кластере и оценка фрактальной размерности такого распределения повышают информативность анализа. В критерии распознавания при анализе используется один параметр – фрактальная частотная или
ранговая размерности (в зависимости от имеющихся данных).
Поскольку предлагаемые процедуры применяются не только в морфологическом анализе, но и в нейросетевом распознавании изображений, обсуждаются их особенности в самоорганизующихся картах Кохонена. Здесь также используется возможность формализации оценки как количества кластеров, так и их размеров, и по сравнению с морфологическим анализом изменяется содержание анализируемых фрактальных пространств.
Таким образом, разработанные процедуры позволяют применять кластеры инвариантов для автоматического распознавания изображений с использованием в качестве меры близости соответствующих фрактальных размерностей.
ЛИТЕРАТУРА
1. Пытьев Ю.П. Морфологический анализ изображений // Докл. АН СССР. 1983. Т. 269. № 5. С. 1061–1064.
2. Пытьев Ю.П., Чуличко А.И. Морфологический анализ изображений: сравнение по форме, узнавание, классификация, оценка параметров // ВЦ РАН. Доклады 11-й Всероссийской конф. “Математические методы распознавания образов”. 2003. С. 415–418.
3. География и мониторинг биоразнообразия. М.: изд-во научного и учебно-методического центра МГУ, 2002. 432 с.
4. Коханенко И.К. Фракталы в оценке эволюции сложных систем // АиТ. 2002. № 8. С. 54–62.
5. Коханенко И.К. К фрактальному непараметрическому распознаванию / Обозрение прикладной и промышленной математики. 2008. Т. 15. В. 4. С. 704–705.
6. Уоссермен Ф. Нейрокомпьютерная техника: Теория и практика. М.: Мир, 1992. 184 с.
“Оптический журнал”, 77, 8, 2010
53
© 2010 г. И. К. Коханенко, доктор техн. наук Ростовский военный институт ракетных войск, Ростов-на-Дону E-mail: kik112@yandex.ru
Обосновывается алгоритм анализа изображения для его автоматического распознавания, который рассматривается в статье с точки зрения формализации выделения кластеров либо постоянной, либо подобной интенсивности сигнала, их количества и размеров, двухуровневого принятия решений. Такой подход базируется на гипотезе фрактальности, которая состоит в предположении о степенной зависимости числа пикселов постоянной интенсивности в кластере от его ранга и фрактальном пространственном распределении пикселов в самом кластере. Обоснование гипотезы связывается с гармонией разнообразия и устойчивости изображения как системы. Рассмотрены особенности двухуровневого алгоритма автоматического распознавания сравнением с эталоном. Приведен пример распознавания изображения по наблюдаемой оптической картине. Изучены особенности подобного подхода при анализе видеоинформации на основе карт Кохонена.
Ключевые слова: фрактал, распознавание, видеоинформация, кластер, инвариант, интенсивность, нейросеть, морфологический анализ, аномальная диффузия.
Коды OCIS: 100.4996, 100.5010
Поступила в редакцию 11.02.2010
Введение
В экспериментальной психологии показано, что наиболее информативными при распознавании изображений являются не значения яркостей объектов, а характеристики их границ – контуров. Это положение используется во многих алгоритмах анализа видеоинформации, в морфологическом анализе, в автоматической сегментации текстурированных изображений, в самоорганизующихся кластерных картах Кохонена. При этом в измерительной информации находятся симметрии, выражающиеся в инвариантности формы объекта к множеству преобразований, типичных для условий измерений, и приводящие к кластерам инвариантов – однородным по характерным признакам областям. Это основные внешние черты объекта, они связаны с неизменными свойствами и определяют его форму. Типичными в множестве преобразований являются изменения оптических свойств (цвет, текстура) и освещения. В ситуациях, когда оптические свойства и освещение являются локально однородными, кластеры постоянной яркости можно считать инвариантами относительно указанных изменений и базой для распознавания.
Полагая, что получаемые изображения имеют подобные инварианты, можно представить модель изображения в виде двумерной матрицы R = Nx × Ny пикселов, каждая строка которой задается последовательностью пар чисел: интенсивностью принимаемого сигнала I и числом элементов строки матрицы n, имеющих интенсивность I = [(I1, n1), (I2, n2),…,(Im, nm)], ∑ni = Nx. Такая модель измеренного изображения совпадает со следующим его кусочно-постоянным описанием:
f(x, y) = ∑Iiχi(x, y), i=1, 2, … m,
(1)
(x, y) ∈ Аi → χi(x, y) = 1, (x, y) ∉ Аi → χi(x, y)=0,
где m – количество кластеров Аi с постоянной интенсивностью; в том числе, один из кластеров есть фон – Imχm(x, y). Подобное описание модели достаточно полно обосновано в работах [1, 2].
Далее, если следовать морфологическому подходу, строится форма объекта в виде проектора Pfg – проекции изображения g на множество форм V(f) или правило, по которому изображению g из гильбертова функционального пространства L2(X) ставится в соответствие некоторое изображение ϕ = Pfg. В соответствии с работами [1, 2] под формой изображения понимается
“Оптический журнал”, 77, 8, 2010
47
множество изображений с упорядоченной интенсивностью
V(f) = [f(x, y) = ∑Iiχi(x, y) + Imχm, (2) (x, y) ∈ X, –∞ < Im ≤ Ii < ∞, i = 1, 2, …, (m – 1)].
Содержательно искомое правило распознавания должно выявить то изображение из множества V(f), которое было бы наиболее близким к изображению g. При этом, если
ϕ= Pfg= g,
(3)
то считается, что объект распознан, т. е. можно подобрать условия регистрации, при которых объект породит изображение g. Множество V(f) полагается выпуклым и замкнутым, т. е. проектор Pf определяется из условия минимума расстояния от изображения до формы, что приводит к процедуре построения Pf как усреднения изображения в каждом кластере постоянной интенсивности [1]. Итак, в каждом кластере находится средняя интенсивность, которая принимается в нем постоянной. Но при этом в контексте задачи распознавания изображения немаловажно знать, как распределяется эта постоянная интенсивность в каждом кластере, сколько пикселов располагается в различных его подобластях. Очевидно, что такое распределение пикселов в кластере является характеристикой изображения. Поэтому, не изучая такие характеристики, устройство узнавания теряет информацию.
В таком алгоритме есть еще одна неопределенность: неясно как определять кластеры постоянной интенсивности Ai, сколько их должно быть и каковы их размеры. Обычно рекомендуется отвечать на подобный вопрос так: полагая, что области изображения одинаковой интенсивности сформированы модулями объекта с идентичными физическими (оптическими, акустическими и др.) и геометрическими свойствами, задавать кластеры Ai по расположению однородно отражающих граней или границ относительно наблюдателя. Однако физически такое решение не всегда выполнимо, и, кроме того, часто постоянство интенсивности достаточно условно, как правило, желаемое постоянство приближенно представляет некоторое множество значений интенсивности в сравнительно небольшом диапазоне.
Аналогичные вопросы характерны и для алгоритмов, реализуемых в нейросетях, в частности, в картах, в слоях нейронов Кохонена. Там кластеры – это не области постоянной интенсивности,
а области с подобным (близким) пространственным распределением интенсивностей (признаков). И при этом в задаче распознавания остаются вопросы первоначального выделения на изображении кластеров – на каких основаниях и сколько. Необходимы основания для назначения приблизительного числа кластеров, без которых структуру слоя Кохонена синтезировать нельзя. При распознавании немаловажно знать и фрактальную размерность пространств “интенсивность – ранг интенсивности” или “число входных векторов – ранг кластера” для каждого кластера. Без такой оценки нейросетевое устройство распознавания теряет информацию.
1. Гипотеза фрактальности и форма изображения
Для преодоления отмеченных выше противоречий целесообразно дополнить зависимость I(x, y) связью интенсивности с количеством пикселов в области Ai. Действительно, для многих реальных объектов каждый кластер Ai будет иметь характерное для него число ni пикселов постоянной интенсивности Ii. Итак, надо найти зависимость ni(Ii). Учитывая, что с ней связана форма изображения, естественно искать такие зависимости в среде систем, которые обладают свойствами разнообразия и устойчивости, так как разнообразие формы является необходимым условием полноты адекватной проверки по правилу (3), а устойчивость – необходимым условием сохранения ее характеристик и наблюдаемости. Понятие разнообразия обычно связывается с энтропией и информацией. В состоянии равновесия (экстремум энтропии) при единственном ресурсе (усилии) задача на условный экстремум приводит в зависимости от характера ограничений формы ресурсами к различным ранговым распределениям: Гиббса, Ципфа–Парето, “разломанного стержня” Макартура [3]. В статье приведен пример только распределения Ципфа–Парето pI = μI–1/d–1, где полагается, что потребности кластеров в ресурсe пропорциональны lnI. Например, в соответствии с физиологическим законом Фехнера потребность усилий по воспроизведению слова ранга I в тексте пропорциональна lnI, и поэтому частота появления в тексте слова ранга I фрактально связана с рангом. Здесь μ = р1, p1 > p2 >…> pm, m – число кластеров (видов) в системе (сообществе), d – в термостатике трактуется как величина, обратная температуре, а в законе Ципфа–Парето d есть фрактальная размерность.
48 “Оптический журнал”, 77, 8, 2010
Как правило, считается, что разнообразие системы тем больше, чем больше в ней кластеров и выше выравненность E = (mpi/lnpi)/i – отношение наблюдаемого разнообразия к максимальному, т. е. равномерность распределения кластеров в системе (E = 1 при равном распределении кластеров). Здесь величина mpi/lnpi известна как индекс Шеннона, типичный диапазон его изменения [1,5–4,5].
Оценка свойств этих законов (плотности, энтропии, выравненности, индекса Шеннона) показывает, что наибольшим разнообразием, а следовательно, совершенством и стабильностью, обладают системы, структура которых связана с распределениями Ципфа–Парето и Макартура. Причем, наибольшее разнообразие у систем, для которых характерно последнее распределение. Если первый закон имеет известное прямое отношение к фрактальным структурам, то относительно закона Макартура это не очевидно. Изучая механизм формирования распределения Макартура, можно показать, что оно сводится к ранговому распределению Ципфа–Парето x(r) ~ r–β, β = 1/(d–1), т. е. закон Макартура тоже относится к классу фрактальных распределений.
Полученные решения по разнообразию подтверждаются и при использовании идей теории информации. Очевидно, характер восприятия системой сигналов внешней среды зависит от ширины полосы частот сигналов, к которым чувствительна система и ее элементы. При этом, чем шире полоса частот, тем больше не только разнообразие, но и ошибок в восприятии сигналов внешней среды и больше вероятность неустойчивости системы. Таким образом, как разнообразие системы, т. е. количество кластеров и элементов в них, так и неадекватность ее поведения, а следовательно, и вероятность ее деградации зависят от ширины полосы частот сигналов, воспринимаемых ею и ее кластерами и элементами. В контексте изучаемого интересно сопоставить ширину полос пропускания систем “ранг кластера – число пикселов одинаковой интенсивности в нем” с различными законами распределения. Для этого следует пояснить понятие ширины полосы пропускания применительно к изучаемой кластерной модели изображения. Ранговому распределению Ципфа–Парето соответствует частота, связанная с фрактальной размерностью d и рангом r кластера следующим соотношением [3]: ωr = = С[exp(1/d–1)]–lnr, C = const. При этом полагается линейная зависимость числа пикселов
в кластере и частоты. Отсюда ранговое распределение Ципфа–Парето может быть записано в виде n(r) = n(1)r–1/d – 1, 1/d – 1 = lnν, ν = = (ωr/ωr + 1)–ln(r + 1). Отношение Δ2 частот кластеров i и (i + 1) для закона Ципфа–Парето равно Δ2 = νln(r + 1), ν = exp(1/d–1). Аналогично для законов Гиббса (отношение Δ1) и Макартура (отношение Δ3): Δ1 = ν, Δ3 = ln(r + 1). Из приведенных зависимостей следует, что для рангов r ≥ 2 наибольшая ширина полосы частот у закона Ципфа–Парето и наименьшая у закона Макартура. Это согласуется с характером разнообразия систем, для которых характерны изучаемые законы распределения: фрактальность системы способствует ее устойчивости за счет обеспечения высокой степени разнообразия и приемлемой зашумленности при рациональной ширине пропускания.
Итак, системы, подчиняющиеся закону Ципфа–Парето, имеют второй ранг по разнообразию при наибольшей полосе пропускания. Системы, подчиняющиеся закону Макартура, имеют первый ранг по полосе пропускания и наибольшее разнообразие. Системы, подчиняющиеся закону Гиббса, имеют среднюю полосу частот и наименьшее разнообразие. Выше показано, что системы, подчиняющиеся законам Макартура и Ципфа–Парето, относятся к классу фрактальных. Следовательно, фрактальность системы способствует ее устойчивости за счет обеспечения высокой степени разнообразия и приемлемой зашумленности при рациональной ширине пропускания. Поэтому для устойчиво развивающейся системы ее фрактальная структура является естественной. Следовательно, рационально выбрать в качестве зависимости между размерами кластеров Aj (количеством пикселов nj постоянной интенсивности) и величинами соответствующих постоянных интенсивностей Ij фрактал, т. е.
nj(Ij) = αAα/Ijd, d = α + 1,
(4)
где параметры определяются по соотношениям [4]: для размерности d это
d1 = ln(G/A),
(5)
G − среднее геометрическое наблюдений интенсивностей, исключая фон, для A это A1 = = min{I1, I2, …, Im – 1}.
Таков смысл гипотезы фрактальности, делаю-
щей определенными выбор числа кластеров и их
размеры. Теперь выражение (2) для множества
форм изображения приобретает вид
“Оптический журнал”, 77, 8, 2010
49
V(f) = {f(x, y)=∑[αAα/nj]–d + Imχm,
(6)
(x, y) ∈ X, d > 0, j = 1, 2, …, (m – 1)},
α = d – 1. Опять получаем форму кусочно-постоянного изображения только в виде фрактала. Следовательно, для определения проекции Pfg необходимо усреднять наблюдаемое изображение g(x, y) в каждом из кластеров Ai постоянной интенсивности изображения f [1, 2]. Из выражений (5) и (6) видно, что множество форм изображения имеет один параметр – фрактальную размерность d. Необходимо оценить d для полученной проекции Pfg, т. е. оценить фрактальную размерность системы: “средняя интенсивность – число соответствующих ей пикселов в кластере”. Равенство полученной фрактальной размерности этому параметру формы будет эквивалентно выполнению правила (3), т. е. совпадению наблюдаемого изображения с эталоном. Действительно, I1 ≈ I1(A, d, n1), I2 ≈ I2(A, d, n2), …, Im – 1 ≈ Im – 1(A, d, nm – 1) – – (m – 1) есть уравнения при двух (A, d) неизвестных, а если учесть, что A = min{I1, I2, …, Im – 1}, то (m – 1) уравнение при одной (d) неизвестной. Очевидно, при одинаковых интенсивностях у кластеров эталонного и наблюдаемого изображений равенство их фрактальных размерностей возможно лишь при равном числе пикселов ni.
2. Алгоритмические особенности процедур кластеризации
Следуя фрактальной гипотезе, задачу распознавания удобнее решать в следующей последовательности. В случае, когда изображение представлено матрицей с элементами в градациях серого, из шкалы выделяются интервалы (кластеры) значений интенсивностей в диапазоне 1–256, на которых интенсивность принимается равной соответствующему среднему значению, например, в интервале 180–256 среднее значение интенсивности равно 218. Развивая гипотезу фрактальности, можно определить регулярную процедуру назначения диапазонов указанных кластеров. Действительно, при изучении зависимости наибольшей интенсивности в кластере Im от ранга кластера r использование сказанного в разделе 1 относительно ширины полосы пропускания систем с разными законами распределения с позиций наибольшей информативности приводит к целесообразности применения гиперболической зависимости, т. е. закона Ципфа–Парето. При использовании шкалы “оттенки серого”
эта зависимость имеет вид Im = 256/rd, т. е., чем больше интенсивность, тем значительнее размеры кластера. Кластеры постоянной интенсивности, например, при d = 1, могут иметь границы 256–128, 128–85, 85–64, 64–51. Фрактальная размерность d определяется, исходя из физически обоснованных значений интенсивности сигнала для фона If и количества кластеров m, т. е. d = (ln256 – lnIf)/lnm. Далее рассчитывается фрактальная размерность системы кластеров с соответствующими постоянными интенсивностями. Как показано ранее, совпадение кластеров и фрактальных размерностей формы и проекции свидетельствует о выполнении правила (3), т. е. совпадении наблюдаемого изображения с эталоном. Но модель (6) на основе гипотезы фрактальности может быть расширена детализацией анализа. Действительно, связь I(n) интенсивности с числом пикселов в кластере, которая описывается выражением (6), целесообразно структурировать для учета естественной неравномерности расположения пикселов постоянной интенсивности в каждом кластере, что было отмечено во введении. Если выделить в кластере отдельные непересекающиеся подобласти, то число пикселов постоянной интенсивности в каждой из них ранжируется, т. е. n(r). После чего выражение (6) трансформируется в более подробную модель – модель второго уровня, включающую (m – 1) моделей (форм) кластеров
nj(Ij) = {nj(Ij(x, y)) = ∑rjk–1/dj – 1(A/dj – 1)1/dj – 1,
(x, y) ∈ X, j=1, 2, …, (m – 1),
(7)
k = 1, 2, …, mj},
где mj – количество подобластей в кластере. Для уточнения общего результата узнава-
ния определяются проекторы Pfgj для каждого из (m – 1) кластеров и оцениваются их фрактальные размерности dj. Нахождение проекторов кластеров проводится следующим образом. В кластере выделяются по осям x и y интервалы Δx и Δy. В каждом интервале j-го кластера (j = 1, 2, …, m – 1) находится число оказавшихся в нем пикселов интенсивностей njk, k = 1, 2, …, mj, здесь mj – число подобластей в кластере j. Подобласти ранжируются в порядке убывания в них числа пикселов интенсивности. Далее оценивается фрактальная размерность кластера из известного рангового соотношения для закона Ципфа
50 “Оптический журнал”, 77, 8, 2010
n(r) = B/r1/d – 1, B= (A/d–1)1/d – 1,
в соответствии с которым несложно найти d = dj, построив прямую
lnn=lnB – (1/d – 1)lnr.
(8)
Здесь r – ранг подобласти в кластере, А – наименьшее значение интенсивности.
При найденных фрактальных размерностях d и dj (j = 1, 2, …, (m – 1)) решение принимается на основе теоретических результатов динамической фрактальной геометрии [4, 5]. Смысл, который вкладывается в определение “динамической”, состоит в следующем. В теории фракталов полагается, что фрактальные объекты обнаруживают пространственное самоподобие, а динамические фракталы (фрактальные временные ряды) имеют статистическое самоподобие во времени. В основе обобщенного изучения самоподобия лежит замена временной динамики на пространственную, в кинетических уравнениях которой производные по времени заменяются производными по пространственным координатам. В работе [5] показано, что модифицированные заменой времени на координату x уравнения аномальной диффузии субдиффузионного и супердиффузионного типов в дивергентной форме имеют соответствующее максимуму энтропии изокоординатное (∂f/∂x = 0) решение вида f ~ h–d, где d – фрактальная размерность, h – характеристика поверхности (изображения). Теперь, следуя работе [4], можно записать последовательность уравнений вида ∂f1/∂x = af1, ∂f2/∂x = bf2, из которых получается фрактал f1 ~ f2–d, где f2 = h, d = a1/a2. Нельзя не заметить подобную последовательность в изучаемом случае, когда число ni в i-м кластере постоянной яркости Ii равно ni ∼ Ii–d, а с другой стороны, число пикселов есть сумма ni∼∑Bj/rj1/di – 1 (суммирование по индексу j ведется от j = 1 до j = k, где k – число интервалов в кластере). Поэтому справедливо соотношение
Ii–d ∼ ∑Bi/r1j /di – 1,
(9)
где i = 1, …, m – 1, rj – ранг в j-м интервале i-го кластера.
Равенство фрактальных размерностей кластеров эталона и наблюдаемого изображения свидетельствует о подтверждении выполнения правила (3), т. е. совпадении наблюдаемого изображения с эталоном. Отличия некоторых из них или всех требуют дополнительного содержательного анализа. Эти отличия могут быть полезны при узнавании, визуализации аномалий, дефектов в микроэлектронике, охранных системах и дру-
гих приложениях. Соотношение (9) свидетельствует о функциональной зависимости фрактальных размерностей d-изображения и di-кластеров постоянной интенсивности. Это указывает на недостаточность вывода о совпадении эталонного и наблюдаемого изображений только по их фрактальной размерности (3). Для получения более достоверного решения необходимо оценивать фрактальные размерности кластеров.
Таким образом, морфологический анализ изображения на основе гипотезы фрактальности включает два уровня. Первый основывается на базовом соотношении (6) и сравнении фрактальных размерностей формы и наблюдаемого изображения и, наконец, второй уровень предполагает сравнение ранговых фрактальных размерностей кластеров постоянной интенсивности (7). На каждом уровне можно принимать решение о распознавании; очевидно, достоверность решения возрастает при увеличении уровня.
Как показано выше, число кластеров зависит от интенсивности фона If и фрактальной размерности. В диапазоне d = 1–3 и If = 10–50 число кластеров изменяется примерно от 2 до 25. Количественное изучение множества изображений показывает, что для отражения специфики изображения достаточно 1–2 кластеров, как правило, не более 5. Пятый кластер в градациях серого соответствует постоянной интенсивности, равной примерно 20. Если воспользоваться классической формулой Шеннона, то получается, что в трех кластерах содержится 0,75, в одном – 0,15 долей информации об изображении, содержащейся в 5 кластерах. Это свидетельствует о наличии ядра изображения – одно-, двух-, пятияркостного ядра. Относительно вариаций оптических свойств ядро есть инвариант, описывающий видимую картину. Указанный инвариант – это главное, наиболее существенное в изображении, это сжатая форма изображения. Такое утверждение наиболее адекватно для однородных изображений, т. е. изображений, имеющих мало существенных элементов (например, лица – нос, глаза, уши). Подтверждением тому является рис. 1, где для сравнения приведены два варианта изображения одного объекта. Если существенных элементов в изображении несколько, то при уменьшении числа кластеров информация теряется значимо.
3. Особенности нейросетевого анализа
Интерпретация видеоинформации, когда затруднено использование эталонов, часто осуще-
“Оптический журнал”, 77, 8, 2010
51
ствляется с использованием различных алгоритмов кластеризации. Задача нейросетевого анализа видеоинформации рассматривается здесь применительно к слоям Кохонена [6], где кластеры – это не области постоянной интенсивности, а области с подобным (близким) пространственным распределением интенсивностей (признаков). При этом в анализе изображений остаются прежние вопросы первоначального выделения на изображении кластеров. Опять-таки, в контексте распознавания изображения немаловажно знать фрактальную размерность пространства “интенсивность – ранг интенсивности” в каждом кластере. Не оценивая указанную фрактальную размерность, нейросетевое устройство распознавания теряет информацию.
Наличие ядра изображения, отмеченное в разделе 2, приводит к возможности сжатия информации путем фрактальной кластеризации. Поэтому целесообразно перед формированием структуры слоя Кохонена провести фрактальную кластеризацию изображения по методике морфологического анализа, описанной в разделе 1. В этом случае в связи со сжатием информации, характерной для фрактальной кластеризации, в дальнейшем входные векторы слоя Кохонена будут содержать меньшее число градаций интенсивностей, что упрощает последующую за фрактальной процедуру нейрокластеризации, уменьшая количество циклов обучения.
Синтезированная в соответствии с обучающими векторами и фрактальной кластеризацией архитектура сети Кохонена содержит некоторое количество кластеров, в каждом из которых после нейроанализа нейронами-победителями окажутся нейроны из подмножества входных векторов изображения. На этом в традиционных алгоритмах заканчивается задача. Но очевидно, что при автоматическом распознавании изображения такое окончание из-за отсутствия учителя в сетях Кохонена, как правило, не приводит к результату. Для распознавания изображения учитель–эталон необходим. Поэтому полученную топологию карты Кохонена в задаче распознавания изображения необходимо проанализировать. Для этого в каждом кластере проводится оценка фрактальной размерности dni пространства “число входных векторов – ранг кластера”. При этом с точностью до обозначений используется выражение (8). Такая же задача решается для эталона и совпадение фрактальных размерностей эталона и изображения свидетельствует о распознавании.
4. Пример Анализируемая видеоинформация представлена в форме статических цифровых полутоновых изображений (наблюдаемого – рис. 1 и эталонного – рис. 2) размером 300×110 элементов (пикселов) и с N = 256 градациями интенсивности (градациями серого). Изображения трансформируются в соответствующие матрицы. Сравнение эталонного изображения в трехкластерном варианте с натурным изображением объекта на рис. 2 не приводится, но оно во многом подобно рис. 1. Фрактальная размерность эталонного изображения в трехкластерном варианте, рассчитанная по соотношению (8), равна 3,1. Аналогично определенная для распознаваемого изображения (рис. 1) фрактальная размерность равна 2,4. Отсюда следует, что указанные изображения не идентичны. Подтверждением этого является результат второго уровня анализа – оценки фрактальных размерностей кластеров двух сравниваемых изображений. Для эталона они получились равными 2,5, 1,5, 1,2, а для распознаваемого изображения соответственно 2,0, 1,7, 1,6. Несовпадение очевидно. Пример иллюстрирует работоспособность алгоритма и высокую информативность фрактальной размерности пространств генерируемых кластеров инвариантов как критерия распознавания. Он не позволяет получить представление о такой важной характеристике алгоритма, как вероятность правильного распознавания на выборках изображений. Аналитических соотношений для оценки такой вероятности автор не получал. Но опыт компьютерного распозна-
(а) (б)
Рис. 1. Изображение (а) и его копия (б) при трех кластерах.
Рис. 2. Эталонное изображение в трехкластерном варианте.
52 “Оптический журнал”, 77, 8, 2010
вания разнообразных изображений с использованием предложенного алгоритма накапливается. Он показывает, что достоверность решения в одноуровневом анализе примерно равна 60–80%. Эксперименты по распознаванию не проводились для условий сильных искажений, будь то неудачный ракурс или плохое освещение. При переходе к двухуровневому анализу достоверность возрастает примерно на 15–20% в зависимости от количества кластеров и пикселов в них. Кроме того, 10% отличий в значениях фрактальных размерностей двух изображений приводят к относительному расстоянию 45–15% между изображениями в характерной для гильбертова функционального пространства метрике при изменении числа пикселов от 3 до 100. Эти результаты получены по 30 экспериментам для каждого типа изображений (местности, объектов техники, людей).
Заключение
Предлагаемые процедуры для автоматического двухуровневого кластерного анализа изображений базируются на обоснованной гипотезе о степенной зависимости количества пикселов постоянной интенсивности в кластерах инвариантов от ранга и фрактальном пространственном распределении пикселов в каждом кластере. При этом в отличие от традиционных подходов появляется возможность формализации оценки как количества кластеров, так и их размеров, а изучение пространственного распределения постоянной интенсивности в кластере и оценка фрактальной размерности такого распределения повышают информативность анализа. В критерии распознавания при анализе используется один параметр – фрактальная частотная или
ранговая размерности (в зависимости от имеющихся данных).
Поскольку предлагаемые процедуры применяются не только в морфологическом анализе, но и в нейросетевом распознавании изображений, обсуждаются их особенности в самоорганизующихся картах Кохонена. Здесь также используется возможность формализации оценки как количества кластеров, так и их размеров, и по сравнению с морфологическим анализом изменяется содержание анализируемых фрактальных пространств.
Таким образом, разработанные процедуры позволяют применять кластеры инвариантов для автоматического распознавания изображений с использованием в качестве меры близости соответствующих фрактальных размерностей.
ЛИТЕРАТУРА
1. Пытьев Ю.П. Морфологический анализ изображений // Докл. АН СССР. 1983. Т. 269. № 5. С. 1061–1064.
2. Пытьев Ю.П., Чуличко А.И. Морфологический анализ изображений: сравнение по форме, узнавание, классификация, оценка параметров // ВЦ РАН. Доклады 11-й Всероссийской конф. “Математические методы распознавания образов”. 2003. С. 415–418.
3. География и мониторинг биоразнообразия. М.: изд-во научного и учебно-методического центра МГУ, 2002. 432 с.
4. Коханенко И.К. Фракталы в оценке эволюции сложных систем // АиТ. 2002. № 8. С. 54–62.
5. Коханенко И.К. К фрактальному непараметрическому распознаванию / Обозрение прикладной и промышленной математики. 2008. Т. 15. В. 4. С. 704–705.
6. Уоссермен Ф. Нейрокомпьютерная техника: Теория и практика. М.: Мир, 1992. 184 с.
“Оптический журнал”, 77, 8, 2010
53