КОМПЛЕКСНЫЙ РАСЧЕТ ХАРАКТЕРИСТИК ЛАНДШАФТНЫХ ИЗОБРАЖЕНИЙ
УДК 004.932
КОМПЛЕКСНЫЙ РАСЧЕТ ХАРАКТЕРИСТИК ЛАНДШАФТНЫХ ИЗОБРАЖЕНИЙ
© 2010 г. М. Н. Фаворская, канд. техн. наук; Н. Ю. Петухов
Сибирский государственный аэрокосмический университет им. академика М.Ф. Решетнева, Красноярск
Е-mail: favorskaya@sibsau.ru, n_petukhov@sibsau.ru
Разработаны алгоритмы вычисления фрактальных размерностей текстурных изображений методом покрытия эталонами и методом покрытия двумерными поверхностями, показавшим лучшие результаты. Проведен расчет основных фрактальных характеристик (фрактальная размерность и лакунарность) ландшафтных изображений, которые являются естественными фрактальными образованиями. В качестве дополнительных характеристик привлекались статистические показатели, такие как средняя яркость, дисперсия, третий момент, однородность, энтропия и некоторые другие характеристики. Разработан программный комплекс оценки фрактальной размерности текстур при распознавании ландшафтных изображений. Для исследований использовались две базы естественных текстур “Textures Library Forrest” (400 изображений) и “Brodatz” (110 изображений).
Ключевые слова: текстура, фрактальная размерность, статистические показатели.
Коды OCIS: 100.2960, 100.3008
Поступила в редакцию 01.02.2010
Введение
Комплексная оценка состояния различных природных структур по их изображениям требует привлечения не только классических методов моделирования и прогнозирования тенденций изменения свойств природных объектов, но и применения современных физических, математических, компьютерных знаний и технологий. Фрактальный анализ может быть применен к изображениям природных объектов, демонстрирующим свойства самоподобия в относительно широком диапазоне характерных масштабов (в частности, для описания и распознавания ландшафтных изображений) [1]. Фрактальные методы используют дробную топологическую размерность пространства сигналов и изображений, математический аппарат дробных интегралов и производных (дробных операторов), а также свойства самоподобия (скейлинга).
Как известно, анализ и распознавание текстурных изображений опирается на три основных подхода: статистический, структурный и спектральный методы. Получаемые при ста-
тистическом методе признаки основаны на значениях автокорреляционных функций, первых и вторых моментах и некоторых других показателях. Структурные подходы интерпретируют текстурное изображение как множество непроизводных элементов и изучают правила их упорядочивания. Наиболее универсален метод анализа текстурных изображений с помощью ансамбля из 28 признаков, определяемых по матрице распределения градиентов в пространственной области [2]. Известна также система из 28 текстурных признаков в области пространственных частот [3]. Спектральные методы основаны на свойствах преобразования Фурье и используются для обнаружения глобальной периодичности в изображении по узким выбросам спектральной характеристики. Однако в последние годы для анализа природных объектов все чаще используются методы фрактальной геометрии. Алгоритмы фрактального распознавания образов основаны на использовании парадигмы “топология объекта – ее фрактальная размерность”. Методы фрактальной топологии позволяют расширить информативность пространства признаков за счет таких фрактальных
54 “Оптический журнал”, 77, 8, 2010
характеристик, как фрактальная размерность D, фрактальная сигнатура, дробные показатели фрактального спектра и др. Повышение размерности вектора измерений позволяет более четко выделить классы естественных и антропогенных объектов при фрактальной кластеризации данных дистанционного зондирования, анализе ландшафтных изображений и при решении других задач [4, 5].
Фрактальный метод оценки текстурных изображений
Статистическая модель броуновского фрактального процесса представляет основу для анализа и описания масштабно инвариантных текстур. Фрактальный броуновский процесс описывается функцией дисперсии приращений [6]
V (x, y) − V (x + Δx, y + Δy) 2 = Δx2 + Δy2 H, (1)
где V(x, y) – обобщенное броуновское движение точки с координатами (x, y) (введено Мандельбротом), Δx и Δy – приращения координат (x, y), 0 < H < 1 – показатель Херста. При H = 1 поверхность рассеяния является гладкой, а при H = 0 она соответствует очень неровной текстуре. Энергетический спектр G(fpr) процесса, характеризуемого функцией fpr, имеет вид
〈G(fpr)〉 ∼ fp–rβ,
где β – степенной показатель. При этом величины D, H и β связаны между собой соотношениями
β = 2H + D0, D = 3 – H,
где D0 – топологическая размерность. Таким образом, по известным параметрам H и β можно вычислить фрактальную размерность случайного процесса.
В работе [7] показано, что большинство естественных поверхностей являются пространственно изотропными фракталами и что двумерные функции изображений таких поверхностей также являются фракталами. Представим связную область А в топологическом n-пространстве. Говорят, что область A самоподобна, когда она является объединением N отдельных неперекрывающихся самоподобных копий, каждая из которых уменьшена в r раз по всем осям координат. Фрактальная размерность области A задается соотношением
D = logN/log(1/r).
(2)
Естественные фрактальные поверхности обычно не обладают самоподобием: они проявляют статистическое самоподобие, т. е. состоят из N отдельных подобластей, каждая из которых является уменьшенной в r раз копией и идентична по всем статистическим характеристикам оригинальной поверхности. Фрактальная размерность таких поверхностей также задается выражением (2). Однако не всегда возможно определить размерность фрактального изображения с помощью характеристики самоподобия. Целесообразней вычислять меру области A на множестве Rn. Предположим, что область A можно покрыть n-мерным кубом размером Lmax. Если область A является копией с коэффициентом уменьшения r, то существует N = r–D подобластей. Поэтому число кубов размером L = rLmax, необходимых для покрытия всей области, задается выражением
N(L) = 1/rD = [Lmax/L]D.
(3)
Простым способом определения величины D из соотношения (3) является покрытие пространства размерностью n сеткой из кубов с длиной стороны L и подсчет количества непустых кубов K. Вычисление параметра N(L) для нескольких значений L позволяет определить размерность D по наклону линии, проходящей через последовательность заполненных ячеек наименьшего размера, расположенных вдоль линии {logL; –logN(L)}.
Существует и другой способ определения фрактальной размерности изображения на основе вероятностного подхода. Пусть P(m, L) – вероятность того, что m точек внутри куба с длиной стороны L сосредоточено вокруг произвольной точки поверхности изображения A. Пусть общее число точек изображения равно M. Если нанести на изображение сетку из кубов с длиной стороны L, то число кубов, содержащих m точек внутри куба, равно (M/m)P(m, L) и будет пропорционально степенной зависимости L–D.
Однако различные фрактальные образования с одинаковой размерностью могут иметь резко различающуюся текстуру. Мандельброт ввел специальный термин “заполнение”, или “лакунарность” (lacunarity), для описания характеристик фракталов, имеющих одинаковые фрактальные размерности, но различный внешний вид или текстурные показатели [8]. Было предложено несколько альтернативных способов определения заполнения Λ, самый известный из которых имеет вид
“Оптический журнал”, 77, 8, 2010
55
Λ = (M/ M −1)2 ,
(4)
где M – масса фрактального образования, 〈M〉 – ожидаемая масса. Заполнение, показывающее разницу между фрактальной массой и ожидаемой массой, относится к статистическим характеристикам второго порядка и изменяется следующим образом: заполнение мало для плотной текстуры и велико для крупнозернистой текстуры. В работе [8] показано, что
M(L) = KLD,
т. е. заполнение является функцией параметра
L. Вероятность P(m, L) содержит усредненную
информацию распределения массы по фрак-
тальному образованию. В работе [9] лакунар-
ность предлагается вычислять по следующей
формуле:
( )Λ(L) = M2 (L) − M(L) 2 / M(L) 2,
(5)
где
∑ ∑N N
M(L) = m P(m, L), M2(L) = m2P(m, L) .
m=1
m=1
Однако признак заполнения, вычисляемый по формуле (4), хорошо работает для больших по площади текстур, но не обеспечивает адекватного различения для небольших сегментов изображения. Проведенные эксперименты показали, что для измерения заполнения можно использовать упрощенную функцию, также учитывающую вероятность P(m, L), а именно, функцию C(L) вида
C(L) = [M(L) − N(L)]/[M(L) + N(L)],
где M(L) – усредненная плотность массы внутри куба со стороной L, N(L) – число, равное частному от деления количества кубов со стороной L, необходимых для полного покрытия фрактального образования, на количество точек в данном фрактальном образовании. В случае если наименьший элемент текстуры меньше выбранного размера куба, масса фрактального образования равномерно распределена в каждом кубе. Следовательно, значения M(L) и N(L) приблизительно равны, а отношение C(L) будет приближаться к нулю. Если наименьший элемент текстуры велик по сравнению с кубом, то плотность массы будет большая, а количество кубов, необходимых для покрытия, мало и, следовательно, C(L) → 1. С ростом величины L значение C(L) → 1 для всех фрактальных образований. Поэтому значения C(L) в обоих случаях будут содержать информацию о текстурных элементах.
Алгоритмическая реализация фрактальных методов оценки текстур
На практике для измерения фрактальной размерности обычно используют три алгоритма: метод покрытия поверхности эталонами, дисперсионное масштабирование, основанное на оценке закона функции распределения средних квадратов по формуле (1), оценка фрактальной размерности D по степени аппроксимирующего полинома для спектра мощности процесса. Наибольшее распространение получил первый способ измерения фрактальной размерности текстурных изображений.
Сущность метода покрытий заключается в покрытии фрактального изображения квадратной сеткой с шагом ε → 0, но при этом значение ε не должно быть слишком малым [10]. Входным изображением является одиночное текстурное изображение, например, изображения дерева, листвы, воды, облаков и проч. На этапе инициализации ε присваиваются минимальное и максимальное значения. Также устанавливается размер шага уменьшения значения ε. На этапе обработки осуществляется вычисление фрактальной размерности и вывод результатов. Приведем описание алгоритма расчета фрактальной размерности методом покрытия эталонами:
1. Начало работы алгоритма. 2. Задаем максимальный εmax и минимальный εmin размеры клетки, по которой высчитывается размерность. 3. Подсчитываем количество клеток, в которые попадает фрактал. 4. Вычисляем значение
lim[log N(ε)/log(ε)].
ε→0
5. Если размер клетки ε > εmin, то возвращаемся к шагу 2, иначе – шаг 6.
6. Конец работы алгоритма. Другой метод покрытия фрактального образования двумерной поверхностью состоит в том, что квантованные значения интенсивности двумерного сигнала должны располагаться между двумя функциями, называемыми верхней и нижней поверхностями [4]. Верхняя поверхность U(x, y, ε) содержит множество точек, значения интенсивностей которых всегда, по крайней мере, на один шаг квантования превышают интенсивность входного сигнала. Нижняя поверхность W(x, y, ε) включает множество точек, значения интенсивностей которых всегда, по крайней мере, на один шаг квантования, меньше
56 “Оптический журнал”, 77, 8, 2010
интенсивности входного изображения f(x, y). В общем случае
U(i,
j,
ε
+1)
=
max⎪⎪⎩⎧⎪⎨U(i,
j,
ε)
+1,
max [U(k,
k, m∈η
m,
ε)]⎪⎪⎬⎭⎪⎫,
W
(i,
j,
ε −1)
= min⎧⎩⎪⎪⎪⎨
W(i,
j,
ε) −1,
min [W(k,
k, m∈η
m,
ε)]⎪⎬⎪⎫⎪⎭,
(6)
где η – локальная область сконструированной “поверхности” размерами k × m точек.
Две функции из выражения (6) формируют покрытие толщиной 2ε. Для двумерного сигнала площадь “поверхности” есть объем, занятый покрытием, деленный на 2ε. Площадь “поверхности” интенсивности A(ε) в пределах скользящего окна R рассчитывается вычитанием точки за точкой нижней “поверхности” из верхней “поверхности” с дальнейшим суммированием по всему окну R
A(ε) = ∑ [U(i, j, ε) −W(i, j, ε)]/[2ε = Vs (ε)/2ε]. (7) i, j∈R
Из работы [8] известно, что объем Vs(ε), занятый покрытием, определяется как
Vs(ε)=2K′exp(3 – D),
(8)
где K′ – постоянная величина. Линейный наклон графика зависимости
logA(ε) от logε говорит о фрактальности процесса. Фрактальная размерность определяется по наклону данного графика. Значение D, полученное из выражения (7), находится в ожидаемом диапазоне от 2 до 3, при котором D = 2 соответствует плоской поверхности. Приведем алгоритм расчета фрактальной размерности методом покрытия двумерной поверхностью:
1. Начало работы алгоритма. 2. Задаем значение ε – толщину покрытия. 3. Строим поверхность по формуле (6). 4. Вычисляем площадь поверхности A(ε) по формуле (7). 5. Строим график зависимости logA(ε) от logε. 6. Определяем фрактальную размерность по наклону графика. 7. Конец алгоритма.
Алгоритмическая реализация расчета статистических показателей текстуры
Статистические характеристики определяются по гистограмме яркости всего изображения или его локальной области. Вычисление стати-
стических характеристик позволяет охаракте-
ризовать текстуру области как гладкую, грубую,
зернистую. Пусть z – случайная величина, соот-
ветствующая яркости элементов изображения,
а p(zi), i = 0, 1, 2, …, Q – 1 – ее гистограмма, где Q – число уровней яркости. Центральный мо-
мент порядка n случайной величины z равен
∑ ∑μn
(z)
=
Qi=−01⎜⎜⎜⎛⎝⎜zi
−
Q−1
zi
i=0
p(zi
)⎟⎟⎠⎟⎟⎞n
p(zi
).
Для описания текстуры особенно важен второй момент, т. е. дисперсия σ2(z) = μ2(z). Она является мерой яркостного контраста и может
быть использована для построения дескрипторов
относительной гладкости. Так, величина
R =1−1/[1+ σ2(z)]
равна 0 для областей постоянной яркости и приближается к 1 для больших значений σ2(z). Поскольку для полутоновых изображений с уровнями яркости от 0 до 255 значения дисперсии оказываются большими, дисперсию целесообразно нормировать до интервала изменения [0, 1]. Для этого необходимо разделить дисперсию σ2(z) на (Q – 1)2. Эмпирическим путем выяснено, что статистики второго порядка и выше являются более важными показателями. Имеются дополнительные характеристики текстуры. Так, “однородность” текстуры находится по формуле
∑S = Q−1 p2(zi ), i=0
а средняя энтропия определяется как
∑Q−1
E = p(zi )log2 p(zi ). i=0
Поскольку все значения p(zi) находятся в интервале [0, 1] и их сумма равна 1, то максимальное значение величины S достигается для изображения, все элементы которого имеют одинаковую яркость (максимально однородное изображение), и оно снижается по мере роста яркостных различий. Энтропия характеризует
“Оптический журнал”, 77, 8, 2010
57
изменчивость яркости изображения: она, наоборот, равна 0 для области постоянной яркости и максимальна в случае равновероятных значений.
Однако текстурные характеристики, вычисляемые только на основании гистограммы, имеют определенную ограниченность, поскольку не несут никакой информации о взаимном расположении элементов изображения. Один из способов учесть подобную информацию при анализе текстуры состоит в том, чтобы рассматривать не только распределение яркостей, но и местоположение пикселов с равными или близкими значениями яркости.
Приведем алгоритм расчета статистических характеристик, считая входное изображение текстурой одного вида:
1. Начало работы алгоритма. 2. Строим гистограмму яркости изображения. 3. Вычисляем статистические характеристики: среднюю яркость, дисперсию, параметр относительной гладкости R, третий момент, определяющий степень симметрии гистограммы и показывающий, наблюдается ли на ней перекос влево (при отрицательном значении момента) или вправо (при положительном значении), однородность, характеризующую равномерность
распределения яркости, энтропию, показывающую изменчивость яркости изображения.
4. Вывод и сохранение полученных статистических характеристик.
5. Строим матрицу смежности пикселов для нахождения связанных областей с равными или близкими значениями яркости. Вывод матрицы смежности.
6. Конец алгоритма.
Реализация алгоритмов и результаты экспериментальных исследований
Разработка программного комплекса “TextureFeatures v.1.0” проводилась в среде программирования Code Gear C++ Builder 2007. Программный комплекс включает четыре модуля: главный модуль Main.cpp, модуль расчета статистических характеристик Stat.cpp, модуль расчета фрактальных показателей Fract.cpp, модуль вспомогательных функций ImageCol.cpp.
Общая структура модулей программного комплекса представлена на рис. 1. В главном модуле Main.cpp реализованы графический интерфейс и структура меню программы. Модуль расчета статистических характеристик Stat.cpp содержит функцию расчета статистических показателей для описания изображения. Модуль
Главный модуль Main.cpp
Модуль расчета статистических характеристик
Stat.cpp
Модуль расчета фрактальных показателей
Fract.cpp
Модуль вспомогательных функций
ImageCol.cpp
Функция расчета статистических характеристик
Get_Stat
Функция покрытия изображения эталонами
Draw_Grid
Функция покрытия изображения поверхностями
Draw_Suf
Функция расчета фрактальной размерности
Get_Fract_Dim
Функция расчета лакунарности
Get_Lac
Рис. 1. Общая структура модулей программного комплекса.
58
Функция перевода в полутоновое изображение
rgb2gray Функция бинаризации изображения
rgb2bw Функция построения гистограммы
Hist
“Оптический журнал”, 77, 8, 2010
Stat.cpp использует гистограмму яркости изображения, которая рассчитывается вспомогательным модулем и передается в функцию Get_Stat(int*gist). Функция возвращает шесть значений характеристик с плавающей запятой. Модуль расчета фрактальных показателейFract.cpp выполняет четыре основные функции: покрытие изображения эталонами, покрытие изображения поверхностями, вычисление фрактальной размерности и вычисление показателя лакунарности. Модуль вспомогательных функций ImageCol.cpp содержит функции перевода входного изображения в бинарное и полутоновое изображения, а также функции расчета гистограммы изображения по яркости. Все модули непосредственно связаны с главным модулем и функционируют по командам из главного меню.
На рис. 2 представлена экранная форма “Главное окно программы”. В верхнюю левую часть загружается исходное изображение, в верхней правой части строится его гистограмма яркости. В нижней части экранной формы отображаются статистические показатели. В центре экранной
формы задаются параметры для расчета и отображаются результирующие фрактальные показатели.
Тестирование проводилось на персональном компьютере, имеющем следующую конфигурацию: процессор Intel Corel 2 DUO 2.26 GHz, ОЗУ 2024 Mb, видеокарта Ati Radeon HD 3470 512 Mb. Для тестирования использовались две базы с естественными текстурами: “Textures Library Forrest” (400 изображений) и “Brodatz” (110 изображений). Также был задействован m-файл в программном обеспечении “MatLab 2008b”, вычисляющий фрактальную размерность методом покрытий квадратной сеткой, и файл для расчета статистических характеристик. Данные по расчетам фрактальных показателей с помощью программного продукта “TextureFeatures v.1.0” и с использованием среды “MatLab 2008b” представлены в таблице.
Экспериментальные исследования, проведенные с помощью разработанного программного комплекса “TextureFeatures v.1.0” и полученные с применением пакета “MatLab 2008b”, показали, что расхождения при расчете фрак-
Рис. 2. Экранная форма “Главное окно программы”. “Оптический журнал”, 77, 8, 2010
59
Результаты расчета фрактальных показателей текстурных изображений с помощью программного комплекса “TextureFeatures v.1.0” и среды программирования “MatLab 2008b”
Текстура
Фрактальная размерность “TextureFeatures v.1.0”
Фрактальная размерность “MatLab 2008b”
Показатель лакунарности “TextureFeatures v.1.0”
Трава Облако Вода Кора дерева Дерево Куст
2,6271 2,6439 2,603681 2,721743 2,697814 2,658424
2,6256 2,6421 2,6001 2,7198 2,69584 2,65438
0,25412 0,67368 0,72711 0,58230 0,53705 0,26732
тальных показателей составляют около 2–4%, что существенно не влияет на полученные результаты.
В ходе экспериментов было обнаружено, что некоторые фрактальные образования имеют почти одинаковую размерность, для чего рассчитывались показатели лакунарности (таблица) и статистические характеристики. Статистические характеристики позволяют определить характер текстуры (гладкая, грубая, периодическая). К грубой текстуре относятся изображения – “Дерево” и “Куст”, к периодической текстуре – изображения “Кора дерева” и “Трава”, к гладкой текстуре – изображение “Вода”. Основной статистической характеристикой, по которой определяется характер текстуры, является дисперсия. Ее среднее значение для текстуры типа “Дерево” равно 46,33, для типа “Кора дерева” – 46,61, для типа “Облако” – 44,76, для типа “Трава” – 46,83, для типа “Вода” – 30,33, для типа “Куст” – 49,22.
Заключение
В статье представлены модели и разработанные на их основе алгоритмы нахождения фрактальных и статистических признаков с целью дальнейшей комплексной оценки текстурных изображений, являющихся естественными фрактальными структурами. Разработанный программный комплекс “TextureFeatures v.1.0” позволяет оценивать основные фрактальные и статистические показатели ландшафтных изображений. Экспериментально показано, что некоторые тестовые изображения имеют одинаковую фрактальную размерность, и требуется расчет дополнительных показателей (в частности, показателя лакунарности). В дальнейшем планируется разработка модуля распознавания текстур с использованием различных методов
нахождения меры сходства с эталонными текстурными изображениями в пространстве признаков.
ЛИТЕРАТУРА
1. Потапов А.А., Пахомов А.А., Никитин С.А., Гуляев Ю.В. Новейшие методы обработки изображений. М.: Физматлит, 2008. 496 c.
2. Haralick R.M., Shanmugam K., Dinstein I. Textural Features for Image Classification // IEEE Trans. 1973. V. SMC–3. № 6. P. 610–621.
3. Song-Sheng L., Jernigan M.E. Texture Analysis and Discrimination in Additive Noise // Comput. Vision, Graph., Image Process. 1990. V. 49. № 1. P. 52–67.
4. Потапов А.А. Фракталы в радиофизике и радиолокации: Топология выборки. М.: Университетская книга, 2005. 848 с.
5. Фаворская М.Н. Сегментация ландшафтных изображений на основе фрактального подхода // Тез. докл. 10-й междунар. конф. и выст. “Цифровая обработка сигналов и ее применение”. М., 2008. Ч. 2. С. 498–501.
6. Stewart C.V., Moghaddam B., Hintz K.J., Novak L.M. Fractional Brownian Motion Models for Synthetic Aperture Radar Imagery Scene Segmentation // Proc. IEEE. 1993. V. 81. № 10. P. 1511–1522.
7. Pentland A.P. Fractal-Based Description of Natural Scenes // IEEE Trans. 1984. V. PAMI-6. № 6. P. 661–674.
8. Mandelbrot B.B. The Fractal Geometry of Nature. N.Y.: Freeman, 1982. 468 p.
9. Keller J.M., Chen S., Grownover R.M. Texture Description and Segmentation through Fractal Geometry // Comput. Vision, Graph., Image Process. 1989. V. 45. № 2. P. 150–166.
10. Петухов Н.Ю. Реализация метода покрытий для расчета фрактальной размерности ландшафтных изображений // Тез. докл. 11-й междунар. конф. и выст. “Цифровая обработка сигналов и ее применение”. М., 2009. Ч. 2. С. 393–396.
60 “Оптический журнал”, 77, 8, 2010
КОМПЛЕКСНЫЙ РАСЧЕТ ХАРАКТЕРИСТИК ЛАНДШАФТНЫХ ИЗОБРАЖЕНИЙ
© 2010 г. М. Н. Фаворская, канд. техн. наук; Н. Ю. Петухов
Сибирский государственный аэрокосмический университет им. академика М.Ф. Решетнева, Красноярск
Е-mail: favorskaya@sibsau.ru, n_petukhov@sibsau.ru
Разработаны алгоритмы вычисления фрактальных размерностей текстурных изображений методом покрытия эталонами и методом покрытия двумерными поверхностями, показавшим лучшие результаты. Проведен расчет основных фрактальных характеристик (фрактальная размерность и лакунарность) ландшафтных изображений, которые являются естественными фрактальными образованиями. В качестве дополнительных характеристик привлекались статистические показатели, такие как средняя яркость, дисперсия, третий момент, однородность, энтропия и некоторые другие характеристики. Разработан программный комплекс оценки фрактальной размерности текстур при распознавании ландшафтных изображений. Для исследований использовались две базы естественных текстур “Textures Library Forrest” (400 изображений) и “Brodatz” (110 изображений).
Ключевые слова: текстура, фрактальная размерность, статистические показатели.
Коды OCIS: 100.2960, 100.3008
Поступила в редакцию 01.02.2010
Введение
Комплексная оценка состояния различных природных структур по их изображениям требует привлечения не только классических методов моделирования и прогнозирования тенденций изменения свойств природных объектов, но и применения современных физических, математических, компьютерных знаний и технологий. Фрактальный анализ может быть применен к изображениям природных объектов, демонстрирующим свойства самоподобия в относительно широком диапазоне характерных масштабов (в частности, для описания и распознавания ландшафтных изображений) [1]. Фрактальные методы используют дробную топологическую размерность пространства сигналов и изображений, математический аппарат дробных интегралов и производных (дробных операторов), а также свойства самоподобия (скейлинга).
Как известно, анализ и распознавание текстурных изображений опирается на три основных подхода: статистический, структурный и спектральный методы. Получаемые при ста-
тистическом методе признаки основаны на значениях автокорреляционных функций, первых и вторых моментах и некоторых других показателях. Структурные подходы интерпретируют текстурное изображение как множество непроизводных элементов и изучают правила их упорядочивания. Наиболее универсален метод анализа текстурных изображений с помощью ансамбля из 28 признаков, определяемых по матрице распределения градиентов в пространственной области [2]. Известна также система из 28 текстурных признаков в области пространственных частот [3]. Спектральные методы основаны на свойствах преобразования Фурье и используются для обнаружения глобальной периодичности в изображении по узким выбросам спектральной характеристики. Однако в последние годы для анализа природных объектов все чаще используются методы фрактальной геометрии. Алгоритмы фрактального распознавания образов основаны на использовании парадигмы “топология объекта – ее фрактальная размерность”. Методы фрактальной топологии позволяют расширить информативность пространства признаков за счет таких фрактальных
54 “Оптический журнал”, 77, 8, 2010
характеристик, как фрактальная размерность D, фрактальная сигнатура, дробные показатели фрактального спектра и др. Повышение размерности вектора измерений позволяет более четко выделить классы естественных и антропогенных объектов при фрактальной кластеризации данных дистанционного зондирования, анализе ландшафтных изображений и при решении других задач [4, 5].
Фрактальный метод оценки текстурных изображений
Статистическая модель броуновского фрактального процесса представляет основу для анализа и описания масштабно инвариантных текстур. Фрактальный броуновский процесс описывается функцией дисперсии приращений [6]
V (x, y) − V (x + Δx, y + Δy) 2 = Δx2 + Δy2 H, (1)
где V(x, y) – обобщенное броуновское движение точки с координатами (x, y) (введено Мандельбротом), Δx и Δy – приращения координат (x, y), 0 < H < 1 – показатель Херста. При H = 1 поверхность рассеяния является гладкой, а при H = 0 она соответствует очень неровной текстуре. Энергетический спектр G(fpr) процесса, характеризуемого функцией fpr, имеет вид
〈G(fpr)〉 ∼ fp–rβ,
где β – степенной показатель. При этом величины D, H и β связаны между собой соотношениями
β = 2H + D0, D = 3 – H,
где D0 – топологическая размерность. Таким образом, по известным параметрам H и β можно вычислить фрактальную размерность случайного процесса.
В работе [7] показано, что большинство естественных поверхностей являются пространственно изотропными фракталами и что двумерные функции изображений таких поверхностей также являются фракталами. Представим связную область А в топологическом n-пространстве. Говорят, что область A самоподобна, когда она является объединением N отдельных неперекрывающихся самоподобных копий, каждая из которых уменьшена в r раз по всем осям координат. Фрактальная размерность области A задается соотношением
D = logN/log(1/r).
(2)
Естественные фрактальные поверхности обычно не обладают самоподобием: они проявляют статистическое самоподобие, т. е. состоят из N отдельных подобластей, каждая из которых является уменьшенной в r раз копией и идентична по всем статистическим характеристикам оригинальной поверхности. Фрактальная размерность таких поверхностей также задается выражением (2). Однако не всегда возможно определить размерность фрактального изображения с помощью характеристики самоподобия. Целесообразней вычислять меру области A на множестве Rn. Предположим, что область A можно покрыть n-мерным кубом размером Lmax. Если область A является копией с коэффициентом уменьшения r, то существует N = r–D подобластей. Поэтому число кубов размером L = rLmax, необходимых для покрытия всей области, задается выражением
N(L) = 1/rD = [Lmax/L]D.
(3)
Простым способом определения величины D из соотношения (3) является покрытие пространства размерностью n сеткой из кубов с длиной стороны L и подсчет количества непустых кубов K. Вычисление параметра N(L) для нескольких значений L позволяет определить размерность D по наклону линии, проходящей через последовательность заполненных ячеек наименьшего размера, расположенных вдоль линии {logL; –logN(L)}.
Существует и другой способ определения фрактальной размерности изображения на основе вероятностного подхода. Пусть P(m, L) – вероятность того, что m точек внутри куба с длиной стороны L сосредоточено вокруг произвольной точки поверхности изображения A. Пусть общее число точек изображения равно M. Если нанести на изображение сетку из кубов с длиной стороны L, то число кубов, содержащих m точек внутри куба, равно (M/m)P(m, L) и будет пропорционально степенной зависимости L–D.
Однако различные фрактальные образования с одинаковой размерностью могут иметь резко различающуюся текстуру. Мандельброт ввел специальный термин “заполнение”, или “лакунарность” (lacunarity), для описания характеристик фракталов, имеющих одинаковые фрактальные размерности, но различный внешний вид или текстурные показатели [8]. Было предложено несколько альтернативных способов определения заполнения Λ, самый известный из которых имеет вид
“Оптический журнал”, 77, 8, 2010
55
Λ = (M/ M −1)2 ,
(4)
где M – масса фрактального образования, 〈M〉 – ожидаемая масса. Заполнение, показывающее разницу между фрактальной массой и ожидаемой массой, относится к статистическим характеристикам второго порядка и изменяется следующим образом: заполнение мало для плотной текстуры и велико для крупнозернистой текстуры. В работе [8] показано, что
M(L) = KLD,
т. е. заполнение является функцией параметра
L. Вероятность P(m, L) содержит усредненную
информацию распределения массы по фрак-
тальному образованию. В работе [9] лакунар-
ность предлагается вычислять по следующей
формуле:
( )Λ(L) = M2 (L) − M(L) 2 / M(L) 2,
(5)
где
∑ ∑N N
M(L) = m P(m, L), M2(L) = m2P(m, L) .
m=1
m=1
Однако признак заполнения, вычисляемый по формуле (4), хорошо работает для больших по площади текстур, но не обеспечивает адекватного различения для небольших сегментов изображения. Проведенные эксперименты показали, что для измерения заполнения можно использовать упрощенную функцию, также учитывающую вероятность P(m, L), а именно, функцию C(L) вида
C(L) = [M(L) − N(L)]/[M(L) + N(L)],
где M(L) – усредненная плотность массы внутри куба со стороной L, N(L) – число, равное частному от деления количества кубов со стороной L, необходимых для полного покрытия фрактального образования, на количество точек в данном фрактальном образовании. В случае если наименьший элемент текстуры меньше выбранного размера куба, масса фрактального образования равномерно распределена в каждом кубе. Следовательно, значения M(L) и N(L) приблизительно равны, а отношение C(L) будет приближаться к нулю. Если наименьший элемент текстуры велик по сравнению с кубом, то плотность массы будет большая, а количество кубов, необходимых для покрытия, мало и, следовательно, C(L) → 1. С ростом величины L значение C(L) → 1 для всех фрактальных образований. Поэтому значения C(L) в обоих случаях будут содержать информацию о текстурных элементах.
Алгоритмическая реализация фрактальных методов оценки текстур
На практике для измерения фрактальной размерности обычно используют три алгоритма: метод покрытия поверхности эталонами, дисперсионное масштабирование, основанное на оценке закона функции распределения средних квадратов по формуле (1), оценка фрактальной размерности D по степени аппроксимирующего полинома для спектра мощности процесса. Наибольшее распространение получил первый способ измерения фрактальной размерности текстурных изображений.
Сущность метода покрытий заключается в покрытии фрактального изображения квадратной сеткой с шагом ε → 0, но при этом значение ε не должно быть слишком малым [10]. Входным изображением является одиночное текстурное изображение, например, изображения дерева, листвы, воды, облаков и проч. На этапе инициализации ε присваиваются минимальное и максимальное значения. Также устанавливается размер шага уменьшения значения ε. На этапе обработки осуществляется вычисление фрактальной размерности и вывод результатов. Приведем описание алгоритма расчета фрактальной размерности методом покрытия эталонами:
1. Начало работы алгоритма. 2. Задаем максимальный εmax и минимальный εmin размеры клетки, по которой высчитывается размерность. 3. Подсчитываем количество клеток, в которые попадает фрактал. 4. Вычисляем значение
lim[log N(ε)/log(ε)].
ε→0
5. Если размер клетки ε > εmin, то возвращаемся к шагу 2, иначе – шаг 6.
6. Конец работы алгоритма. Другой метод покрытия фрактального образования двумерной поверхностью состоит в том, что квантованные значения интенсивности двумерного сигнала должны располагаться между двумя функциями, называемыми верхней и нижней поверхностями [4]. Верхняя поверхность U(x, y, ε) содержит множество точек, значения интенсивностей которых всегда, по крайней мере, на один шаг квантования превышают интенсивность входного сигнала. Нижняя поверхность W(x, y, ε) включает множество точек, значения интенсивностей которых всегда, по крайней мере, на один шаг квантования, меньше
56 “Оптический журнал”, 77, 8, 2010
интенсивности входного изображения f(x, y). В общем случае
U(i,
j,
ε
+1)
=
max⎪⎪⎩⎧⎪⎨U(i,
j,
ε)
+1,
max [U(k,
k, m∈η
m,
ε)]⎪⎪⎬⎭⎪⎫,
W
(i,
j,
ε −1)
= min⎧⎩⎪⎪⎪⎨
W(i,
j,
ε) −1,
min [W(k,
k, m∈η
m,
ε)]⎪⎬⎪⎫⎪⎭,
(6)
где η – локальная область сконструированной “поверхности” размерами k × m точек.
Две функции из выражения (6) формируют покрытие толщиной 2ε. Для двумерного сигнала площадь “поверхности” есть объем, занятый покрытием, деленный на 2ε. Площадь “поверхности” интенсивности A(ε) в пределах скользящего окна R рассчитывается вычитанием точки за точкой нижней “поверхности” из верхней “поверхности” с дальнейшим суммированием по всему окну R
A(ε) = ∑ [U(i, j, ε) −W(i, j, ε)]/[2ε = Vs (ε)/2ε]. (7) i, j∈R
Из работы [8] известно, что объем Vs(ε), занятый покрытием, определяется как
Vs(ε)=2K′exp(3 – D),
(8)
где K′ – постоянная величина. Линейный наклон графика зависимости
logA(ε) от logε говорит о фрактальности процесса. Фрактальная размерность определяется по наклону данного графика. Значение D, полученное из выражения (7), находится в ожидаемом диапазоне от 2 до 3, при котором D = 2 соответствует плоской поверхности. Приведем алгоритм расчета фрактальной размерности методом покрытия двумерной поверхностью:
1. Начало работы алгоритма. 2. Задаем значение ε – толщину покрытия. 3. Строим поверхность по формуле (6). 4. Вычисляем площадь поверхности A(ε) по формуле (7). 5. Строим график зависимости logA(ε) от logε. 6. Определяем фрактальную размерность по наклону графика. 7. Конец алгоритма.
Алгоритмическая реализация расчета статистических показателей текстуры
Статистические характеристики определяются по гистограмме яркости всего изображения или его локальной области. Вычисление стати-
стических характеристик позволяет охаракте-
ризовать текстуру области как гладкую, грубую,
зернистую. Пусть z – случайная величина, соот-
ветствующая яркости элементов изображения,
а p(zi), i = 0, 1, 2, …, Q – 1 – ее гистограмма, где Q – число уровней яркости. Центральный мо-
мент порядка n случайной величины z равен
∑ ∑μn
(z)
=
Qi=−01⎜⎜⎜⎛⎝⎜zi
−
Q−1
zi
i=0
p(zi
)⎟⎟⎠⎟⎟⎞n
p(zi
).
Для описания текстуры особенно важен второй момент, т. е. дисперсия σ2(z) = μ2(z). Она является мерой яркостного контраста и может
быть использована для построения дескрипторов
относительной гладкости. Так, величина
R =1−1/[1+ σ2(z)]
равна 0 для областей постоянной яркости и приближается к 1 для больших значений σ2(z). Поскольку для полутоновых изображений с уровнями яркости от 0 до 255 значения дисперсии оказываются большими, дисперсию целесообразно нормировать до интервала изменения [0, 1]. Для этого необходимо разделить дисперсию σ2(z) на (Q – 1)2. Эмпирическим путем выяснено, что статистики второго порядка и выше являются более важными показателями. Имеются дополнительные характеристики текстуры. Так, “однородность” текстуры находится по формуле
∑S = Q−1 p2(zi ), i=0
а средняя энтропия определяется как
∑Q−1
E = p(zi )log2 p(zi ). i=0
Поскольку все значения p(zi) находятся в интервале [0, 1] и их сумма равна 1, то максимальное значение величины S достигается для изображения, все элементы которого имеют одинаковую яркость (максимально однородное изображение), и оно снижается по мере роста яркостных различий. Энтропия характеризует
“Оптический журнал”, 77, 8, 2010
57
изменчивость яркости изображения: она, наоборот, равна 0 для области постоянной яркости и максимальна в случае равновероятных значений.
Однако текстурные характеристики, вычисляемые только на основании гистограммы, имеют определенную ограниченность, поскольку не несут никакой информации о взаимном расположении элементов изображения. Один из способов учесть подобную информацию при анализе текстуры состоит в том, чтобы рассматривать не только распределение яркостей, но и местоположение пикселов с равными или близкими значениями яркости.
Приведем алгоритм расчета статистических характеристик, считая входное изображение текстурой одного вида:
1. Начало работы алгоритма. 2. Строим гистограмму яркости изображения. 3. Вычисляем статистические характеристики: среднюю яркость, дисперсию, параметр относительной гладкости R, третий момент, определяющий степень симметрии гистограммы и показывающий, наблюдается ли на ней перекос влево (при отрицательном значении момента) или вправо (при положительном значении), однородность, характеризующую равномерность
распределения яркости, энтропию, показывающую изменчивость яркости изображения.
4. Вывод и сохранение полученных статистических характеристик.
5. Строим матрицу смежности пикселов для нахождения связанных областей с равными или близкими значениями яркости. Вывод матрицы смежности.
6. Конец алгоритма.
Реализация алгоритмов и результаты экспериментальных исследований
Разработка программного комплекса “TextureFeatures v.1.0” проводилась в среде программирования Code Gear C++ Builder 2007. Программный комплекс включает четыре модуля: главный модуль Main.cpp, модуль расчета статистических характеристик Stat.cpp, модуль расчета фрактальных показателей Fract.cpp, модуль вспомогательных функций ImageCol.cpp.
Общая структура модулей программного комплекса представлена на рис. 1. В главном модуле Main.cpp реализованы графический интерфейс и структура меню программы. Модуль расчета статистических характеристик Stat.cpp содержит функцию расчета статистических показателей для описания изображения. Модуль
Главный модуль Main.cpp
Модуль расчета статистических характеристик
Stat.cpp
Модуль расчета фрактальных показателей
Fract.cpp
Модуль вспомогательных функций
ImageCol.cpp
Функция расчета статистических характеристик
Get_Stat
Функция покрытия изображения эталонами
Draw_Grid
Функция покрытия изображения поверхностями
Draw_Suf
Функция расчета фрактальной размерности
Get_Fract_Dim
Функция расчета лакунарности
Get_Lac
Рис. 1. Общая структура модулей программного комплекса.
58
Функция перевода в полутоновое изображение
rgb2gray Функция бинаризации изображения
rgb2bw Функция построения гистограммы
Hist
“Оптический журнал”, 77, 8, 2010
Stat.cpp использует гистограмму яркости изображения, которая рассчитывается вспомогательным модулем и передается в функцию Get_Stat(int*gist). Функция возвращает шесть значений характеристик с плавающей запятой. Модуль расчета фрактальных показателейFract.cpp выполняет четыре основные функции: покрытие изображения эталонами, покрытие изображения поверхностями, вычисление фрактальной размерности и вычисление показателя лакунарности. Модуль вспомогательных функций ImageCol.cpp содержит функции перевода входного изображения в бинарное и полутоновое изображения, а также функции расчета гистограммы изображения по яркости. Все модули непосредственно связаны с главным модулем и функционируют по командам из главного меню.
На рис. 2 представлена экранная форма “Главное окно программы”. В верхнюю левую часть загружается исходное изображение, в верхней правой части строится его гистограмма яркости. В нижней части экранной формы отображаются статистические показатели. В центре экранной
формы задаются параметры для расчета и отображаются результирующие фрактальные показатели.
Тестирование проводилось на персональном компьютере, имеющем следующую конфигурацию: процессор Intel Corel 2 DUO 2.26 GHz, ОЗУ 2024 Mb, видеокарта Ati Radeon HD 3470 512 Mb. Для тестирования использовались две базы с естественными текстурами: “Textures Library Forrest” (400 изображений) и “Brodatz” (110 изображений). Также был задействован m-файл в программном обеспечении “MatLab 2008b”, вычисляющий фрактальную размерность методом покрытий квадратной сеткой, и файл для расчета статистических характеристик. Данные по расчетам фрактальных показателей с помощью программного продукта “TextureFeatures v.1.0” и с использованием среды “MatLab 2008b” представлены в таблице.
Экспериментальные исследования, проведенные с помощью разработанного программного комплекса “TextureFeatures v.1.0” и полученные с применением пакета “MatLab 2008b”, показали, что расхождения при расчете фрак-
Рис. 2. Экранная форма “Главное окно программы”. “Оптический журнал”, 77, 8, 2010
59
Результаты расчета фрактальных показателей текстурных изображений с помощью программного комплекса “TextureFeatures v.1.0” и среды программирования “MatLab 2008b”
Текстура
Фрактальная размерность “TextureFeatures v.1.0”
Фрактальная размерность “MatLab 2008b”
Показатель лакунарности “TextureFeatures v.1.0”
Трава Облако Вода Кора дерева Дерево Куст
2,6271 2,6439 2,603681 2,721743 2,697814 2,658424
2,6256 2,6421 2,6001 2,7198 2,69584 2,65438
0,25412 0,67368 0,72711 0,58230 0,53705 0,26732
тальных показателей составляют около 2–4%, что существенно не влияет на полученные результаты.
В ходе экспериментов было обнаружено, что некоторые фрактальные образования имеют почти одинаковую размерность, для чего рассчитывались показатели лакунарности (таблица) и статистические характеристики. Статистические характеристики позволяют определить характер текстуры (гладкая, грубая, периодическая). К грубой текстуре относятся изображения – “Дерево” и “Куст”, к периодической текстуре – изображения “Кора дерева” и “Трава”, к гладкой текстуре – изображение “Вода”. Основной статистической характеристикой, по которой определяется характер текстуры, является дисперсия. Ее среднее значение для текстуры типа “Дерево” равно 46,33, для типа “Кора дерева” – 46,61, для типа “Облако” – 44,76, для типа “Трава” – 46,83, для типа “Вода” – 30,33, для типа “Куст” – 49,22.
Заключение
В статье представлены модели и разработанные на их основе алгоритмы нахождения фрактальных и статистических признаков с целью дальнейшей комплексной оценки текстурных изображений, являющихся естественными фрактальными структурами. Разработанный программный комплекс “TextureFeatures v.1.0” позволяет оценивать основные фрактальные и статистические показатели ландшафтных изображений. Экспериментально показано, что некоторые тестовые изображения имеют одинаковую фрактальную размерность, и требуется расчет дополнительных показателей (в частности, показателя лакунарности). В дальнейшем планируется разработка модуля распознавания текстур с использованием различных методов
нахождения меры сходства с эталонными текстурными изображениями в пространстве признаков.
ЛИТЕРАТУРА
1. Потапов А.А., Пахомов А.А., Никитин С.А., Гуляев Ю.В. Новейшие методы обработки изображений. М.: Физматлит, 2008. 496 c.
2. Haralick R.M., Shanmugam K., Dinstein I. Textural Features for Image Classification // IEEE Trans. 1973. V. SMC–3. № 6. P. 610–621.
3. Song-Sheng L., Jernigan M.E. Texture Analysis and Discrimination in Additive Noise // Comput. Vision, Graph., Image Process. 1990. V. 49. № 1. P. 52–67.
4. Потапов А.А. Фракталы в радиофизике и радиолокации: Топология выборки. М.: Университетская книга, 2005. 848 с.
5. Фаворская М.Н. Сегментация ландшафтных изображений на основе фрактального подхода // Тез. докл. 10-й междунар. конф. и выст. “Цифровая обработка сигналов и ее применение”. М., 2008. Ч. 2. С. 498–501.
6. Stewart C.V., Moghaddam B., Hintz K.J., Novak L.M. Fractional Brownian Motion Models for Synthetic Aperture Radar Imagery Scene Segmentation // Proc. IEEE. 1993. V. 81. № 10. P. 1511–1522.
7. Pentland A.P. Fractal-Based Description of Natural Scenes // IEEE Trans. 1984. V. PAMI-6. № 6. P. 661–674.
8. Mandelbrot B.B. The Fractal Geometry of Nature. N.Y.: Freeman, 1982. 468 p.
9. Keller J.M., Chen S., Grownover R.M. Texture Description and Segmentation through Fractal Geometry // Comput. Vision, Graph., Image Process. 1989. V. 45. № 2. P. 150–166.
10. Петухов Н.Ю. Реализация метода покрытий для расчета фрактальной размерности ландшафтных изображений // Тез. докл. 11-й междунар. конф. и выст. “Цифровая обработка сигналов и ее применение”. М., 2009. Ч. 2. С. 393–396.
60 “Оптический журнал”, 77, 8, 2010