Метод вейвлетной сегментации цветных текстурных изображений
УДК 621.397.132
МЕТОД ВЕЙВЛЕТНОЙ СЕГМЕНТАЦИИ ЦВЕТНЫХ ТЕКСТУРНЫХ ИЗОБРАЖЕНИЙ
© 2012 г. В. Т. Фисенко, канд. техн. наук; Т. Ю. Фисенко, канд. техн. наук Филиал ФГУП “ЦНИИ “Комета” “НПЦ ОЭКН”, Санкт-Петербург E-mail: valery@eoss.ru
Исследованы методы сегментации сложных текстурных изображений. Разработан метод вейвлетной многомасштабной сегментации цветных текстур на основе их характерных признаков и характеристик цветности. Для формирования признаков текстур использован кратномасштабный анализ изображений. Метод позволяет объединять оценки текстурных характеристик на основе дискретного вейвлетного преобразования и цветовых характеристик текстуры. Получены оценки эффективности сегментации от числа итераций вейвлетного преобразования, типа вейвлет-базиса, вида цветового координатного пространства и размера окна фильтрации оценки признаков сегментации.
Ключевые слова: текстура, цвет, сегментация, вейвлетный анализ.
Коды OCIS: 100.2960, 100.7410, 100.2000, 330.6110
Поступила в редакцию 29.05.2012
Введение
Текстура является важной характеристикой изображения. Можно выделить три подхода к описанию текстур [1]: статистический, фрактальный и структурный. Статистический подход основан на следующем определении текстуры: “Под текстурами понимают такие типы изображений, класс которых обладает свойством эргодичности, то есть любое изображение данной текстуры является типовым и полностью характеризует все другие изображения, относящиеся к этому классу” [2]. Из определения следует, что при распознавании текстуры можно выявить статистические характеристики образца текстуры и считать их соответствующими любым другим образцам этой текстуры.
Получили распространение различные методы формирования признаков текстур, cреди которых отметим следующие. Метод описания текстур моментами функции распределения яркости. Производится оценка гистограммы изображения текстуры и определяются моменты функции распределения яркости изображения. Метод локального двоичного разбиения (local binary partition, LBP), основанный на сравнении значения интенсивности каждого элемента изображения и восьми его соседей. Метод формирования энергетических характеристик Лавса, при котором выполняется свертка изо-
бражения с 15-импульсными характеристиками в пространственной области, позволяющая выделить высокочастотную (ВЧ) информацию изображения, на основании которой формируются энергетические карты, составляющие пространство признаков. Метод формирования гистограммных признаков второго порядка [3] описывает пространственные связи пар яркостей элементов в цифровом изображении текстуры. Для этого формируется матрица смежности (сooccurrence matrix) и производится ее нормировка. По нормированной матрице вычисляют признаки, среди которых наибольшее применение получили: момент инерции (контраст), энергия, однородность и корреляция. Для анализа текстур на основании теории статистического кодирования и данных физиологии зрения используют распределение отрезков контуров и интервалов между контурными элементами. Для анализа анизотропных текстур предложены алгоритмы, учитывающие зависимости распределения интервалов между контурами и отрезков контуров вдоль направлений сканирования текстуры. Для повышения эффективности сегментации цветных текстур наряду с пространственными характеристиками яркости учитывают и характеристики цветности. Возникновение трудностей при сегментации текстур состоит в том, что эффективность сегментации зависит от размера окна, в котором оцениваются признаки текстуры.
“Оптический журнал”, 79, 11, 2012
21
При этом для оценки признаков текстуры предпочтительно выбирать окно большего размера, а для формирования более точных границ областей – меньшего размера.
В статье рассмотрена проблема сегментации цветных текстурных изображений на основе дискретного вейвлетного преобразования (ДВП). Предложен метод многомасштабной вейвлетной сегментации цветных текстурных изображений и выполнена оценка его эффективности.
Применение ДВП для сегментации текстурных изображений
Характеристики текстуры можно выявить при рассмотрении ее в некотором диапазоне масштабов. В связи с этим большой интерес вызывает применение ДВП изображений при сегментации текстур. Основополагающей в вейвлет-анализе является идея о выделении информации при различных уровнях детализации. Такое преобразование обеспечивает получение высокого пространственного разрешения при низком частотном, и, наоборот, высокого разрешения по частоте при низком разрешении по пространству [4]. При вейвлетной схеме преобразования производится разложение сигнала по набору базисных функций. ДВП является разделимым преобразованием и сводится к двум независимо выполняемым одномерным преобразованиям.
В одномерном случае функция f Î L2(R) может быть представлена в виде
f(t)= å cjj(t)+ å ådkjkj(t), jÎ Z kÎ Z+ jÎ Z
(1)
где j(t) = (t – j) – масштабирующая функция (отцовский вейвлет), kj(t) = 2k/2(2kt – j) – материнский вейвлет, j – смещение по оси времени, k – параметр масштаба, Z+ – множество целых положительных чисел, {cj} – аппроксимирующие коэффициенты, {dkj} – детализирующие коэффициенты. Все базисные функции
получают из одного прототипа материнского вейвлета путем его растяжения (или сжа-
тия) и смещения. В классической схеме ДВП
масштабирование базисных функций не про-
изводят. Применяют одни и те же базисные
функции на сетке масштабов, а масштабиру-
ют изображение и полученные коэффициенты
вейвлетного преобразования. Поскольку ча-
стотный диапазон изображения уменьшается
в два раза после фильтрации, то без потери ин-
формации отбрасывают каждый второй отсчет
преобразования, то есть выполняют децима-
цию. В случае двумерного ДВП, четырем отсче-
там высокого разрешения соответствует один
отсчет более грубого разрешения. Это означает,
что сегментация, выполненная на основании
признаков, сформированных на k + 1-й итера-
ции, может быть сопоставлена с сегментацией,
выполненной на k-й итерации с точностью до
окрестности ±2 элемента. Необходимо учиты-
вать, что не обязательно все эти отсчеты соот-
ветствуют одной и той же текстуре. Неопреде-
ленность определения границы сегментиро-
ванной области увеличивается при увеличении
числа масштабов K.
Классическая схема ДВП, пригодная для
сжатия изображений, имеет существенное
ограничение при решении задач анализа изо-
бражений. Для уменьшения ошибок сегмен-
тации и устранения неопределенности, свя-
занной с кратномасштабным представлением
текстур, предлагается формировать полнораз-
мерное “изображение” коэффициентов ДВП.
Это позволит сохранить точную привязку
к координатам коэффициентов ДВП на всех
K масштабах. Схема формирования субполос
на основе ДВП для одной итерации имеет вид,
представленный на рис. 1. Штрих-пунктирная
линия разделяет прямое ДВП и обратное ДВП
(ОДВП). На схеме использованы следующие
обозначения: h – НЧ фильтр анализа, g – ВЧ фильтр анализа, h~, g~ – фильтры восстановле-
ния НЧ и ВЧ соответственно, “стр” указывает
на фильтрацию по строкам, “ст” – по столбцам,
индексы h, , d означают горизонтальные, вер-
тикальные и диагональные детализирующие
коэффициенты соответственно. L соответствует
отклику НЧ фильтра, H соответствует отклику
ВЧ фильтра. Восстановленные аппроксимиру-
ющие коэффициенты ДВП субполосы LL с по-
мощью фильтров восстановления путем ОДВП
обозначены Vk(y, x) и восстановленные детализирующие коэффициенты субполос B (B {HL,
LH, HH}) обозначены WB, k(y, x). Восстановление коэффициентов ДВП выполняется в обрат-
ной последовательности. Для восстановления
детализирующих коэффициентов сначала при-
меним следующие фильтры восстановления:
g~, h~ для получения горизонтальных детализи-
рующих кальных
кWоэ,фg~ф,иg~ци–ендлтоявдWиаhг,оh~н,алg~ь–ныдхляWвdе.рПтио--
скольку детализирующие коэффициенты на
каждой итерации получаются только из НЧ
субполосы LL, необходимо выполнить восста-
22 “Оптический журнал”, 79, 11, 2012
cтр {ckj} cт h2 h
2 LL
cт g 2 LH
LL
cтр {dkj} cт g2h
cт
g
2 HL 2 HH
1
cт cтр
2 h~
2 h~
1
1V
2
cт g~ 2
h~ cтр
1
1
Wh
2
h~ cт 2
cтр g~
1
1
W
cт cтр
2 g~
2 g~
1 1 Wd
Рис. 1. Схема формирования субполос для k-го масштаба на основе ДВП для одной итерации (пояснение в тексте).
новление с помощью НЧ фильтров по столбцам
и по строкам. Это преобразование выделено
штриховой линией на рис. 1, а соответствую-
щий блок обозначен как блок 1. При восстанов-
лении коэффициентов k-й итерации преобразо-
вание, соответствующее блоку 1, выполняется
k – 1 раз.
Информация о текстуре содержится в ВЧ
субполосах. Поэтому пространство признаков
формируется из ВЧ субполос следующим об-
разом. Для каждой субполосы B формируется
два изображения. Первое представляет среднее
значение квадратов коэффициентов преобразо-
вания в скользящем окне S = (2m + 1)(2n + 1)
å åm
EB,k (y,x)=1 S
n (WB,k (y + i,x + j))2. (2)
i=-m j=-n
Второе изображение представляет среднее зна-
чение модулей коэффициентов преобразования
в скользящем окне S:
å åm n
MB,k (y,x)=1 S
WB,k (y + i,x + j). (3)
i=-m j=-n
Изображения {EB, k(y, x)} и {MB, k(y, x)} являются полномасштабными. При выполнении каждой итерации алгоритма формируется q = 6 “изображений” признаков для B субполос для полутонового изображения или q = 18 “изображений” признаков для цветного изображения.
Анализируемое изображение представляет собой конечное множество элементов A = {a1, a2, …, an}, составляющих множество объектов кластеризации, где n – количество объектов кластеризации. Каждый объект характеризуется q-мерным вектором признаков: P = {p1, p2, …, pq}. Каждый компонент вектора
Вероятность сегментации
0,98
0,97
1 0,96 2
3
0,95
0,94 9
13 17 21 25 29 33 Размер окна
Рис. 2. Зависимость вероятности правильной сегментации от размера окна. Вейвлет-фильтры: 1.bior3.5, 2.db3, 3.coif5.
признаков имеет оценку в виде действительного числа
{ }xi = x1i,x2i ,...,xqi , i Î[1,n].
При такой интерпретации каждому элементу изображения соответствует вектор из q текстурных признаков. Эти текстурные признаки используют для кластеризации изображения в области с одинаковой текстурой.
Выбор базиса вейвлетов для разложения изображения влияет на эффективность сегментации. На рис. 2 показан график зависимости вероятности правильной сегментации от размера окна (выбрано квадратное окно) при разных видах вейвлет базисов. На рис. 2 цифрами обозначены следующие вейвлет фильтры: 1-bior3.5, 2-db3, 3-coif5. Выполнение ДВП на нескольких масштабах повышает эффективность сегментации, что показано в табл. 1 на примере 5 стадий ДВП при использовании дискретного фильтра “coif5”.
“Оптический журнал”, 79, 11, 2012
23
Таблица 1. Зависимость вероятности правильной сегментации от размера окна при разном числе масштабов
Размер фильтра
1
Число итераций 234
5
9 0,922 0,928 0,933 0,932 0,928 13 0,971 0,972 0,972 0,972 0,972 17 0,976 0,977 0,977 0,976 0,977 21 0,969 0,970 0,970 0,969 0,969 25 0,953 0,955 0,956 0,956 0,955 29 0,943 0,945 0,945 0,945 0,945 33 0,932 0,934 0,935 0,935 0,935
Применение алгоритма нечетких k-средних
При выполнении сегментации приходится решать задачу отнесения элемента изображения к той или иной текстуре в условиях, когда различия между текстурами размыты, то есть когда можно скорее ответить на вопрос, в какой степени тот или иной элемент принадлежит данной текстуре. Это, прежде всего, относится к элементам на границах текстур. Поэтому мы используем метод нечетких k-средних (FCM – Fuzzy C – Means) [5]. Задача нечеткой кластеризации состоит в нахождении нечеткого разбиения элементов исследуемой совокупности элементов на T нечетких кластеров и формирование соответствующих им значений функций принадлежности. Функция принадлежности указывает на степень уверенности в том, что элементы некоторого множества принадлежат заданному нечеткому множеству и должна удовлетворять условию
Aj(ai )³ 0, "j Î[1, T], "ai Î A.
Из векторов значения признаков формируется матрица данных
D
=
êêêêéëêêêê
x11 x12 ...
x1n
x21 x22 ...
x2n
... ... ... ...
xq1 xq2 ...
xqn
úúúùûúúúúú
.
Задача нечеткого кластерного анализа формулируется таким образом: на основе исходных данных D определить такое нечеткое разбиение множества A на заданное число нечетких кластеров, при котором достигается экстремум некоторой целевой функции среди всех нечетких разбиений.
На функции принадлежности накладывают-
ся дополнительные условия:
– нормировки
åT
Aj(ai )=1, "ai Î A,
j=1
(4)
где T N – число кластеров, T > 1, – отсутствие пустых кластеров
åT
Aj (ai )> 0,
"j Î[1,T].
i=1
Для каждого нечеткого кластера вво-
дится q-мерный вектор центра кластеров cj = [c1j, c2j, …, cqj], j [1, T], каждый компонент которого определяется в соответствии
с уравнением
å åclj = ëéê Aj (ai )ùûúm xli
êéë Aj (ai )ùúûm ,
ii
для "j Î{1,,T}, "pl Î P,
где m – экспоненциальный вес, равный не-
которому действительному значению больше
единицы.
Целевая функция – сумма квадратов взве-
шенных отклонений координат объектов кла-
стеризации от центров искомых нечетких кла-
стеров:
( ) åå å( )n
Aj, clj =
T éêë Aj (ai )ùûúm q
xli - clj 2.
i=1 j=1
l=1
(5)
Задача нечеткой кластеризации – найти матрицу U значений функции принадлежности объектов кластеризации нечетким кластерам, обеспечивающую получение минимума целевой функции (5).
Алгоритм FCM является итеративным, на каждой итерации последовательно улучшается некоторое исходное нечеткое разбиение пространства признаков, заданного первоначально пользователем. На каждой итерации рекуррентно пересчитываются значения функций принадлежности и центры тяжести нечетких кластеров. Алгоритм FCM прекращает работу при выполнении заданного априорно максимального числа итераций, либо при достижении априорно заданного параметра сходимости. Алгоритм FCM относится к приближенным алгоритмам поиска экстремума целевой функции, поэтому в результате выполнения данного алгоритма достигается локально – оптимальное нечеткое разбиение, которое описывается совокупностью функций принадлеж-
24 “Оптический журнал”, 79, 11, 2012
ности, а также центрами тяжести каждого из нечетких кластеров.
При кластеризации необходимо представить результаты нечеткой кластеризации в форме обычного не нечеткого разбиения. Для этого используется метод дефаззификации. Поскольку все функции принадлежности искомого нечеткого разбиения нормированы, используем метод максимального значения функции принадлежности.
Выбор цветового координатного пространства
Эффективность выбора признаков зависит от выбора цветового координатного пространства. Анализ цветных изображений показал, что наиболее информативным из цветовых признаков представляется компонент тона [6]. Исследователи при сегментации текстур используют разные цветовые модели. Приведем краткое описание наиболее часто используемых моделей.
Цветовая модель RGB. В цветовом координатном пространстве RGB любой цвет получается как сумма (смешение) красного, зеленого и синего компонентов.
Цветовая модель YСrCb. Компонент Y несет информацию о яркости элементов, а компоненты Сb и Сr содержат информацию о цвете и насыщенности. Переход от цветового координатного пространства RGB к пространству YCrCb соответствует рекомендациям Международного телекоммуникационного союза (ITU – International Telecommunication Union) ITU – T с идентификатором BT.601. Пространство YCrCb используется в ТВ системах PAL и SECAM, а также при кодировании неподвижных изображений и видеопоследовательностей.
Цветовая модель L*a*b* МКО 1976. Эта система координат обеспечивает относительно точное представление цветов в соответствии с системой цветов, разработанной в 1905 г. художником Манселлом, и представляет собой “равноконтрастную” цветовую систему. Координата L* определяет яркость цвета, a* – соотношение красного и зеленого цветов, b* – соотношение синего и зеленого [2].
Цветовая модель HMMD. Эта модель использована в стандарте MPEG-7, она применяется для описания структуры цвета (color structure descriptor – CSD) [7]. Модель названа по 4 компонентам: тон (hue), минимум (min), мак-
250 200 150
100 50 0
200 100
0 –100 –200
255 яркость
тон 0
255 насыщенность
0 –200 –100 0
100 200
Рис. 3. Геометрическая модель расположения цветов в пространстве HMMD в соответствии с цветовым тоном, насыщенностью и яркостью.
симум (max) и разность (difference). Цветовое пространство, называемое по 4 компонентам, имеет 3 независимых компонента: тон, сумму минимального и максимального значений (яркость), разность максимального и минимального значений (насыщенность). Цветовое пространство HMMD представлено на рис. 3. Преобразование из RGB пространства в пространство HMMD выполняется в соответствии с кодом:
maxVal = max(R, G, B);
minVal = min(R, G, B);
diff = maxVal – minVal;
hmmd(1) = diff;
hmmd(2) = (maxVal + minVal)/2;
if (diff = 0) hue = 0; elseif (r = maxVal ) hue = 60*(g – b)/diff; elseif (g = maxVal) hue = 60*(2. + (b – r)/diff); elseif (b = maxVal) hue = 60*(4. + (r – g)/diff);
end;
if hue < 0 hue = hue + 360; end;
hmmd(3) = hue.
Обратное преобразование из пространства HMMD в пространство RGB выполняется в соответствии с условным кодом:
diff = hmmd(1); Sum = hmmd(2);
Hue = hmmd(3); Val = diff/2 + Sum;
“Оптический журнал”, 79, 11, 2012
25
Вероятность сегментации
minVal = Sum – diff/2; Saturation = diff/Val; if (Val = minVal), r = Val; g = Val; b = Val; % –achromatic (grey), Saturation = 0 else hue_index = floor(Hue/60); % целая часть вещественного числа hue_factorial = Hue/60 – hue_index; p = Val*(1-Saturation); q = Val*(1-Saturation*hue_factorial); t = Val*(1-Saturation*(1-hue_factorial)); if (hue_index = 0)||(hue_index = 6) r = Val; g = t; b = p; elseif (hue_index = 1) r = q; g = Val; b = p; elseif (hue_index = 2) r = p; g = Val; b = t; elseif (hue_index = 3) r = p; g = q; b = Val; elseif (hue_index = 4) r = t; g = p; b = Val; else r = Val; g = p; b = q; end end; R = uint8(r); G = uint8(g); B = uint8(b).
На рис. 4 приведен пример повышения эффективности сегментации текстур при включении в пространство признаков характеристик цветности и введены следующие обозначения:
0,98
0,97 1
2
0,96
3
0,95
0,94
9 13 17 21 25 29 33 Размер окна
Рис. 4. Зависимость вероятности правильной сегментации с учетом признаков характеристик цветности (пояснение в тексте).
Таблица 2. Зависимость вероятности правильной сегментации от размера окна и вида цветовой модели
Размер окна
RGB
Цветовая модель YCrCb L*a*b* МКО HMMD
9
0,643 0,621
0,573
0,950
13 0,643 0,621 0,573 0,955
17 0,644 0,624 0,573 0,962
21 0,643 0,623 0,573 0,965
25 0,643 0,625 0,573 0,968
29 0,644 0,626 0,571 0,969
1. – соответствует сегментации в цветовом пространстве L*a*b* МКО, 2. –LSH, 3. – только по компоненту яркости Y.
В табл. 2 приведена зависимость вероятности правильной сегментации от размера окна и цветовой модели.
Экспериментальные исследования сегментации цветных текстур
Выполнены экспериментальные исследования по оценке эффективности алгоритмов сегментации цветных текстурных изображений. Использованы реальные текстуры из альбома Бродатца [8] и текстуры баз данных [9, 10]. Исследованы методы сегментации сложных текстурных изображений при известном числе кластеров. Тестовые изображения получены наложением текстур по маске. Вероятность правильной сегментации определялась как отношение числа элементов текстур, верно сегментированных, к общему числу элементов изображения, покрытого этими текстурами.
На рис. 5 приведен пример вейвлетной сегментации для первой стадии ДВП при применении биортогонального фильтра анализа “bior3.5”. На рис. 5г представлена маска, по которой на изображение фона: текстуры “Brick0004”, наложено изображение объекта – текстуры “Flowers0002” [9], в результате синтезировано тестовое изображение (рис. 5а). Выполнено преобразование тестового изображения в цветовое координатное пространство L*a*b* МКО. Произведено ДВП, сформировано пространство признаков, составляющее 18-компонентное пространство признаков. Произведена НЧ линейная фильтрация признаков при заданном размере окна. Выполнена
26 “Оптический журнал”, 79, 11, 2012
(а) (б) (в)
ментированная, при увеличении размера окна отсутствует. Однако дальнейшее увеличение окна приводит к расширению области объекта, вследствие чего ухудшается точность выявления его границ.
(г) (д) (е)
Рис. 5. Пример вейвлетной сегментации (пояснение в тексте).
нечеткая классификация и дефаззификация. Пример вейвлетной сегментации представлен на рис. 5.
На рис. 5б и 5в показана маска объекта, полученная при размерах окна 13 и 17 соответственно. На рис. 5д и 5е показаны ошибки сегментации, полученные вычитанием из маски сегментированной области маски 5г, соответствующей идеальной маске сегментации. Из рис. 5 видно, что при увеличении размера окна эффективность сегментации повысилась, малая область изображения, ошибочно сег-
Выводы
Разработан метод многомасштабной сегментации цветных текстур на основе текстурных признаков и характеристик цветности. Для формирования признаков текстур использован кратномасштабный анализ изображений. Инвариантность к переносу достигается исключением процесса децимации из ДВП. Для сокращения пространства признаков можно выбирать субполосы с большей энергией (2).
Выполнено сравнение методов сегментации текстур, основанных на оценке энергии коэффициентов ДВП, при использовании разных вейвлет-базисов.
Проведено исследование сегментации цветных текстур на основании объединения цветовых и пространственных характеристик текстур при их описании в разных цветовых координатных пространствах. Показано, что использование характеристик цветности позволяет повысить эффективность сегментации.
*****
ЛИТЕРАТУРА
1. Фисенко В.Т., Фисенко Т.Ю. Сегментация цветных текстурных изображений // Международная конференция. Прикладная оптика: Сборник трудов. СПб., 2008. Т. 3. С. 359–363.
2. Фисенко В.Т., Фисенко Т.Ю. Компьютерная обработка и распознавание изображений: учеб. пособие. СПб: СПбГУ ИТМО, 2008. 192 c.
3. Харалик Р.М. Статистический и структурный подходы к описанию текстур // ТИИЭР. 1979. Т. 67. № 56. С. 98.
4. Малла С. Вэйвлеты в обработке сигналов: Пер. с англ. М.: Мир, 2005. 671 с.
5. Леоненков А.В. Нечеткое моделирование в среде MATLAB и fuzzyTECH. СПб.: БХВ-Петербург, 2005. 736 с.
6. Фисенко В.Т., Фисенко Т.Ю. Метод автоматического анализа цветных изображений // Оптический журнал. 2003. Т. 70. № 9. C. 18–23.
7. Manjunath B., Ohm J.-R., Vasudevan V., Yamada A. Color and Texture Descriptors // IEEE Trans. Circuits and Systems for Video Technology. 2001. V. 11. № 6. P. 703–715.
8. Brodatz P. A Photographic Album for Artists and Designers. New York, Dover, 1966.
9. Vision Texture [Электронный ресурс]. Режим доступа: http://vismod.media.mit.edu/vismod/imagery/ VisionTexture/vistex.html, 2012.
10. University of Oulu texture database [Электронный ресурс]. Режим доступа: http://www.outex.oulu.fi, 2012.
“Оптический журнал”, 79, 11, 2012
27
МЕТОД ВЕЙВЛЕТНОЙ СЕГМЕНТАЦИИ ЦВЕТНЫХ ТЕКСТУРНЫХ ИЗОБРАЖЕНИЙ
© 2012 г. В. Т. Фисенко, канд. техн. наук; Т. Ю. Фисенко, канд. техн. наук Филиал ФГУП “ЦНИИ “Комета” “НПЦ ОЭКН”, Санкт-Петербург E-mail: valery@eoss.ru
Исследованы методы сегментации сложных текстурных изображений. Разработан метод вейвлетной многомасштабной сегментации цветных текстур на основе их характерных признаков и характеристик цветности. Для формирования признаков текстур использован кратномасштабный анализ изображений. Метод позволяет объединять оценки текстурных характеристик на основе дискретного вейвлетного преобразования и цветовых характеристик текстуры. Получены оценки эффективности сегментации от числа итераций вейвлетного преобразования, типа вейвлет-базиса, вида цветового координатного пространства и размера окна фильтрации оценки признаков сегментации.
Ключевые слова: текстура, цвет, сегментация, вейвлетный анализ.
Коды OCIS: 100.2960, 100.7410, 100.2000, 330.6110
Поступила в редакцию 29.05.2012
Введение
Текстура является важной характеристикой изображения. Можно выделить три подхода к описанию текстур [1]: статистический, фрактальный и структурный. Статистический подход основан на следующем определении текстуры: “Под текстурами понимают такие типы изображений, класс которых обладает свойством эргодичности, то есть любое изображение данной текстуры является типовым и полностью характеризует все другие изображения, относящиеся к этому классу” [2]. Из определения следует, что при распознавании текстуры можно выявить статистические характеристики образца текстуры и считать их соответствующими любым другим образцам этой текстуры.
Получили распространение различные методы формирования признаков текстур, cреди которых отметим следующие. Метод описания текстур моментами функции распределения яркости. Производится оценка гистограммы изображения текстуры и определяются моменты функции распределения яркости изображения. Метод локального двоичного разбиения (local binary partition, LBP), основанный на сравнении значения интенсивности каждого элемента изображения и восьми его соседей. Метод формирования энергетических характеристик Лавса, при котором выполняется свертка изо-
бражения с 15-импульсными характеристиками в пространственной области, позволяющая выделить высокочастотную (ВЧ) информацию изображения, на основании которой формируются энергетические карты, составляющие пространство признаков. Метод формирования гистограммных признаков второго порядка [3] описывает пространственные связи пар яркостей элементов в цифровом изображении текстуры. Для этого формируется матрица смежности (сooccurrence matrix) и производится ее нормировка. По нормированной матрице вычисляют признаки, среди которых наибольшее применение получили: момент инерции (контраст), энергия, однородность и корреляция. Для анализа текстур на основании теории статистического кодирования и данных физиологии зрения используют распределение отрезков контуров и интервалов между контурными элементами. Для анализа анизотропных текстур предложены алгоритмы, учитывающие зависимости распределения интервалов между контурами и отрезков контуров вдоль направлений сканирования текстуры. Для повышения эффективности сегментации цветных текстур наряду с пространственными характеристиками яркости учитывают и характеристики цветности. Возникновение трудностей при сегментации текстур состоит в том, что эффективность сегментации зависит от размера окна, в котором оцениваются признаки текстуры.
“Оптический журнал”, 79, 11, 2012
21
При этом для оценки признаков текстуры предпочтительно выбирать окно большего размера, а для формирования более точных границ областей – меньшего размера.
В статье рассмотрена проблема сегментации цветных текстурных изображений на основе дискретного вейвлетного преобразования (ДВП). Предложен метод многомасштабной вейвлетной сегментации цветных текстурных изображений и выполнена оценка его эффективности.
Применение ДВП для сегментации текстурных изображений
Характеристики текстуры можно выявить при рассмотрении ее в некотором диапазоне масштабов. В связи с этим большой интерес вызывает применение ДВП изображений при сегментации текстур. Основополагающей в вейвлет-анализе является идея о выделении информации при различных уровнях детализации. Такое преобразование обеспечивает получение высокого пространственного разрешения при низком частотном, и, наоборот, высокого разрешения по частоте при низком разрешении по пространству [4]. При вейвлетной схеме преобразования производится разложение сигнала по набору базисных функций. ДВП является разделимым преобразованием и сводится к двум независимо выполняемым одномерным преобразованиям.
В одномерном случае функция f Î L2(R) может быть представлена в виде
f(t)= å cjj(t)+ å ådkjkj(t), jÎ Z kÎ Z+ jÎ Z
(1)
где j(t) = (t – j) – масштабирующая функция (отцовский вейвлет), kj(t) = 2k/2(2kt – j) – материнский вейвлет, j – смещение по оси времени, k – параметр масштаба, Z+ – множество целых положительных чисел, {cj} – аппроксимирующие коэффициенты, {dkj} – детализирующие коэффициенты. Все базисные функции
получают из одного прототипа материнского вейвлета путем его растяжения (или сжа-
тия) и смещения. В классической схеме ДВП
масштабирование базисных функций не про-
изводят. Применяют одни и те же базисные
функции на сетке масштабов, а масштабиру-
ют изображение и полученные коэффициенты
вейвлетного преобразования. Поскольку ча-
стотный диапазон изображения уменьшается
в два раза после фильтрации, то без потери ин-
формации отбрасывают каждый второй отсчет
преобразования, то есть выполняют децима-
цию. В случае двумерного ДВП, четырем отсче-
там высокого разрешения соответствует один
отсчет более грубого разрешения. Это означает,
что сегментация, выполненная на основании
признаков, сформированных на k + 1-й итера-
ции, может быть сопоставлена с сегментацией,
выполненной на k-й итерации с точностью до
окрестности ±2 элемента. Необходимо учиты-
вать, что не обязательно все эти отсчеты соот-
ветствуют одной и той же текстуре. Неопреде-
ленность определения границы сегментиро-
ванной области увеличивается при увеличении
числа масштабов K.
Классическая схема ДВП, пригодная для
сжатия изображений, имеет существенное
ограничение при решении задач анализа изо-
бражений. Для уменьшения ошибок сегмен-
тации и устранения неопределенности, свя-
занной с кратномасштабным представлением
текстур, предлагается формировать полнораз-
мерное “изображение” коэффициентов ДВП.
Это позволит сохранить точную привязку
к координатам коэффициентов ДВП на всех
K масштабах. Схема формирования субполос
на основе ДВП для одной итерации имеет вид,
представленный на рис. 1. Штрих-пунктирная
линия разделяет прямое ДВП и обратное ДВП
(ОДВП). На схеме использованы следующие
обозначения: h – НЧ фильтр анализа, g – ВЧ фильтр анализа, h~, g~ – фильтры восстановле-
ния НЧ и ВЧ соответственно, “стр” указывает
на фильтрацию по строкам, “ст” – по столбцам,
индексы h, , d означают горизонтальные, вер-
тикальные и диагональные детализирующие
коэффициенты соответственно. L соответствует
отклику НЧ фильтра, H соответствует отклику
ВЧ фильтра. Восстановленные аппроксимиру-
ющие коэффициенты ДВП субполосы LL с по-
мощью фильтров восстановления путем ОДВП
обозначены Vk(y, x) и восстановленные детализирующие коэффициенты субполос B (B {HL,
LH, HH}) обозначены WB, k(y, x). Восстановление коэффициентов ДВП выполняется в обрат-
ной последовательности. Для восстановления
детализирующих коэффициентов сначала при-
меним следующие фильтры восстановления:
g~, h~ для получения горизонтальных детализи-
рующих кальных
кWоэ,фg~ф,иg~ци–ендлтоявдWиаhг,оh~н,алg~ь–ныдхляWвdе.рПтио--
скольку детализирующие коэффициенты на
каждой итерации получаются только из НЧ
субполосы LL, необходимо выполнить восста-
22 “Оптический журнал”, 79, 11, 2012
cтр {ckj} cт h2 h
2 LL
cт g 2 LH
LL
cтр {dkj} cт g2h
cт
g
2 HL 2 HH
1
cт cтр
2 h~
2 h~
1
1V
2
cт g~ 2
h~ cтр
1
1
Wh
2
h~ cт 2
cтр g~
1
1
W
cт cтр
2 g~
2 g~
1 1 Wd
Рис. 1. Схема формирования субполос для k-го масштаба на основе ДВП для одной итерации (пояснение в тексте).
новление с помощью НЧ фильтров по столбцам
и по строкам. Это преобразование выделено
штриховой линией на рис. 1, а соответствую-
щий блок обозначен как блок 1. При восстанов-
лении коэффициентов k-й итерации преобразо-
вание, соответствующее блоку 1, выполняется
k – 1 раз.
Информация о текстуре содержится в ВЧ
субполосах. Поэтому пространство признаков
формируется из ВЧ субполос следующим об-
разом. Для каждой субполосы B формируется
два изображения. Первое представляет среднее
значение квадратов коэффициентов преобразо-
вания в скользящем окне S = (2m + 1)(2n + 1)
å åm
EB,k (y,x)=1 S
n (WB,k (y + i,x + j))2. (2)
i=-m j=-n
Второе изображение представляет среднее зна-
чение модулей коэффициентов преобразования
в скользящем окне S:
å åm n
MB,k (y,x)=1 S
WB,k (y + i,x + j). (3)
i=-m j=-n
Изображения {EB, k(y, x)} и {MB, k(y, x)} являются полномасштабными. При выполнении каждой итерации алгоритма формируется q = 6 “изображений” признаков для B субполос для полутонового изображения или q = 18 “изображений” признаков для цветного изображения.
Анализируемое изображение представляет собой конечное множество элементов A = {a1, a2, …, an}, составляющих множество объектов кластеризации, где n – количество объектов кластеризации. Каждый объект характеризуется q-мерным вектором признаков: P = {p1, p2, …, pq}. Каждый компонент вектора
Вероятность сегментации
0,98
0,97
1 0,96 2
3
0,95
0,94 9
13 17 21 25 29 33 Размер окна
Рис. 2. Зависимость вероятности правильной сегментации от размера окна. Вейвлет-фильтры: 1.bior3.5, 2.db3, 3.coif5.
признаков имеет оценку в виде действительного числа
{ }xi = x1i,x2i ,...,xqi , i Î[1,n].
При такой интерпретации каждому элементу изображения соответствует вектор из q текстурных признаков. Эти текстурные признаки используют для кластеризации изображения в области с одинаковой текстурой.
Выбор базиса вейвлетов для разложения изображения влияет на эффективность сегментации. На рис. 2 показан график зависимости вероятности правильной сегментации от размера окна (выбрано квадратное окно) при разных видах вейвлет базисов. На рис. 2 цифрами обозначены следующие вейвлет фильтры: 1-bior3.5, 2-db3, 3-coif5. Выполнение ДВП на нескольких масштабах повышает эффективность сегментации, что показано в табл. 1 на примере 5 стадий ДВП при использовании дискретного фильтра “coif5”.
“Оптический журнал”, 79, 11, 2012
23
Таблица 1. Зависимость вероятности правильной сегментации от размера окна при разном числе масштабов
Размер фильтра
1
Число итераций 234
5
9 0,922 0,928 0,933 0,932 0,928 13 0,971 0,972 0,972 0,972 0,972 17 0,976 0,977 0,977 0,976 0,977 21 0,969 0,970 0,970 0,969 0,969 25 0,953 0,955 0,956 0,956 0,955 29 0,943 0,945 0,945 0,945 0,945 33 0,932 0,934 0,935 0,935 0,935
Применение алгоритма нечетких k-средних
При выполнении сегментации приходится решать задачу отнесения элемента изображения к той или иной текстуре в условиях, когда различия между текстурами размыты, то есть когда можно скорее ответить на вопрос, в какой степени тот или иной элемент принадлежит данной текстуре. Это, прежде всего, относится к элементам на границах текстур. Поэтому мы используем метод нечетких k-средних (FCM – Fuzzy C – Means) [5]. Задача нечеткой кластеризации состоит в нахождении нечеткого разбиения элементов исследуемой совокупности элементов на T нечетких кластеров и формирование соответствующих им значений функций принадлежности. Функция принадлежности указывает на степень уверенности в том, что элементы некоторого множества принадлежат заданному нечеткому множеству и должна удовлетворять условию
Aj(ai )³ 0, "j Î[1, T], "ai Î A.
Из векторов значения признаков формируется матрица данных
D
=
êêêêéëêêêê
x11 x12 ...
x1n
x21 x22 ...
x2n
... ... ... ...
xq1 xq2 ...
xqn
úúúùûúúúúú
.
Задача нечеткого кластерного анализа формулируется таким образом: на основе исходных данных D определить такое нечеткое разбиение множества A на заданное число нечетких кластеров, при котором достигается экстремум некоторой целевой функции среди всех нечетких разбиений.
На функции принадлежности накладывают-
ся дополнительные условия:
– нормировки
åT
Aj(ai )=1, "ai Î A,
j=1
(4)
где T N – число кластеров, T > 1, – отсутствие пустых кластеров
åT
Aj (ai )> 0,
"j Î[1,T].
i=1
Для каждого нечеткого кластера вво-
дится q-мерный вектор центра кластеров cj = [c1j, c2j, …, cqj], j [1, T], каждый компонент которого определяется в соответствии
с уравнением
å åclj = ëéê Aj (ai )ùûúm xli
êéë Aj (ai )ùúûm ,
ii
для "j Î{1,,T}, "pl Î P,
где m – экспоненциальный вес, равный не-
которому действительному значению больше
единицы.
Целевая функция – сумма квадратов взве-
шенных отклонений координат объектов кла-
стеризации от центров искомых нечетких кла-
стеров:
( ) åå å( )n
Aj, clj =
T éêë Aj (ai )ùûúm q
xli - clj 2.
i=1 j=1
l=1
(5)
Задача нечеткой кластеризации – найти матрицу U значений функции принадлежности объектов кластеризации нечетким кластерам, обеспечивающую получение минимума целевой функции (5).
Алгоритм FCM является итеративным, на каждой итерации последовательно улучшается некоторое исходное нечеткое разбиение пространства признаков, заданного первоначально пользователем. На каждой итерации рекуррентно пересчитываются значения функций принадлежности и центры тяжести нечетких кластеров. Алгоритм FCM прекращает работу при выполнении заданного априорно максимального числа итераций, либо при достижении априорно заданного параметра сходимости. Алгоритм FCM относится к приближенным алгоритмам поиска экстремума целевой функции, поэтому в результате выполнения данного алгоритма достигается локально – оптимальное нечеткое разбиение, которое описывается совокупностью функций принадлеж-
24 “Оптический журнал”, 79, 11, 2012
ности, а также центрами тяжести каждого из нечетких кластеров.
При кластеризации необходимо представить результаты нечеткой кластеризации в форме обычного не нечеткого разбиения. Для этого используется метод дефаззификации. Поскольку все функции принадлежности искомого нечеткого разбиения нормированы, используем метод максимального значения функции принадлежности.
Выбор цветового координатного пространства
Эффективность выбора признаков зависит от выбора цветового координатного пространства. Анализ цветных изображений показал, что наиболее информативным из цветовых признаков представляется компонент тона [6]. Исследователи при сегментации текстур используют разные цветовые модели. Приведем краткое описание наиболее часто используемых моделей.
Цветовая модель RGB. В цветовом координатном пространстве RGB любой цвет получается как сумма (смешение) красного, зеленого и синего компонентов.
Цветовая модель YСrCb. Компонент Y несет информацию о яркости элементов, а компоненты Сb и Сr содержат информацию о цвете и насыщенности. Переход от цветового координатного пространства RGB к пространству YCrCb соответствует рекомендациям Международного телекоммуникационного союза (ITU – International Telecommunication Union) ITU – T с идентификатором BT.601. Пространство YCrCb используется в ТВ системах PAL и SECAM, а также при кодировании неподвижных изображений и видеопоследовательностей.
Цветовая модель L*a*b* МКО 1976. Эта система координат обеспечивает относительно точное представление цветов в соответствии с системой цветов, разработанной в 1905 г. художником Манселлом, и представляет собой “равноконтрастную” цветовую систему. Координата L* определяет яркость цвета, a* – соотношение красного и зеленого цветов, b* – соотношение синего и зеленого [2].
Цветовая модель HMMD. Эта модель использована в стандарте MPEG-7, она применяется для описания структуры цвета (color structure descriptor – CSD) [7]. Модель названа по 4 компонентам: тон (hue), минимум (min), мак-
250 200 150
100 50 0
200 100
0 –100 –200
255 яркость
тон 0
255 насыщенность
0 –200 –100 0
100 200
Рис. 3. Геометрическая модель расположения цветов в пространстве HMMD в соответствии с цветовым тоном, насыщенностью и яркостью.
симум (max) и разность (difference). Цветовое пространство, называемое по 4 компонентам, имеет 3 независимых компонента: тон, сумму минимального и максимального значений (яркость), разность максимального и минимального значений (насыщенность). Цветовое пространство HMMD представлено на рис. 3. Преобразование из RGB пространства в пространство HMMD выполняется в соответствии с кодом:
maxVal = max(R, G, B);
minVal = min(R, G, B);
diff = maxVal – minVal;
hmmd(1) = diff;
hmmd(2) = (maxVal + minVal)/2;
if (diff = 0) hue = 0; elseif (r = maxVal ) hue = 60*(g – b)/diff; elseif (g = maxVal) hue = 60*(2. + (b – r)/diff); elseif (b = maxVal) hue = 60*(4. + (r – g)/diff);
end;
if hue < 0 hue = hue + 360; end;
hmmd(3) = hue.
Обратное преобразование из пространства HMMD в пространство RGB выполняется в соответствии с условным кодом:
diff = hmmd(1); Sum = hmmd(2);
Hue = hmmd(3); Val = diff/2 + Sum;
“Оптический журнал”, 79, 11, 2012
25
Вероятность сегментации
minVal = Sum – diff/2; Saturation = diff/Val; if (Val = minVal), r = Val; g = Val; b = Val; % –achromatic (grey), Saturation = 0 else hue_index = floor(Hue/60); % целая часть вещественного числа hue_factorial = Hue/60 – hue_index; p = Val*(1-Saturation); q = Val*(1-Saturation*hue_factorial); t = Val*(1-Saturation*(1-hue_factorial)); if (hue_index = 0)||(hue_index = 6) r = Val; g = t; b = p; elseif (hue_index = 1) r = q; g = Val; b = p; elseif (hue_index = 2) r = p; g = Val; b = t; elseif (hue_index = 3) r = p; g = q; b = Val; elseif (hue_index = 4) r = t; g = p; b = Val; else r = Val; g = p; b = q; end end; R = uint8(r); G = uint8(g); B = uint8(b).
На рис. 4 приведен пример повышения эффективности сегментации текстур при включении в пространство признаков характеристик цветности и введены следующие обозначения:
0,98
0,97 1
2
0,96
3
0,95
0,94
9 13 17 21 25 29 33 Размер окна
Рис. 4. Зависимость вероятности правильной сегментации с учетом признаков характеристик цветности (пояснение в тексте).
Таблица 2. Зависимость вероятности правильной сегментации от размера окна и вида цветовой модели
Размер окна
RGB
Цветовая модель YCrCb L*a*b* МКО HMMD
9
0,643 0,621
0,573
0,950
13 0,643 0,621 0,573 0,955
17 0,644 0,624 0,573 0,962
21 0,643 0,623 0,573 0,965
25 0,643 0,625 0,573 0,968
29 0,644 0,626 0,571 0,969
1. – соответствует сегментации в цветовом пространстве L*a*b* МКО, 2. –LSH, 3. – только по компоненту яркости Y.
В табл. 2 приведена зависимость вероятности правильной сегментации от размера окна и цветовой модели.
Экспериментальные исследования сегментации цветных текстур
Выполнены экспериментальные исследования по оценке эффективности алгоритмов сегментации цветных текстурных изображений. Использованы реальные текстуры из альбома Бродатца [8] и текстуры баз данных [9, 10]. Исследованы методы сегментации сложных текстурных изображений при известном числе кластеров. Тестовые изображения получены наложением текстур по маске. Вероятность правильной сегментации определялась как отношение числа элементов текстур, верно сегментированных, к общему числу элементов изображения, покрытого этими текстурами.
На рис. 5 приведен пример вейвлетной сегментации для первой стадии ДВП при применении биортогонального фильтра анализа “bior3.5”. На рис. 5г представлена маска, по которой на изображение фона: текстуры “Brick0004”, наложено изображение объекта – текстуры “Flowers0002” [9], в результате синтезировано тестовое изображение (рис. 5а). Выполнено преобразование тестового изображения в цветовое координатное пространство L*a*b* МКО. Произведено ДВП, сформировано пространство признаков, составляющее 18-компонентное пространство признаков. Произведена НЧ линейная фильтрация признаков при заданном размере окна. Выполнена
26 “Оптический журнал”, 79, 11, 2012
(а) (б) (в)
ментированная, при увеличении размера окна отсутствует. Однако дальнейшее увеличение окна приводит к расширению области объекта, вследствие чего ухудшается точность выявления его границ.
(г) (д) (е)
Рис. 5. Пример вейвлетной сегментации (пояснение в тексте).
нечеткая классификация и дефаззификация. Пример вейвлетной сегментации представлен на рис. 5.
На рис. 5б и 5в показана маска объекта, полученная при размерах окна 13 и 17 соответственно. На рис. 5д и 5е показаны ошибки сегментации, полученные вычитанием из маски сегментированной области маски 5г, соответствующей идеальной маске сегментации. Из рис. 5 видно, что при увеличении размера окна эффективность сегментации повысилась, малая область изображения, ошибочно сег-
Выводы
Разработан метод многомасштабной сегментации цветных текстур на основе текстурных признаков и характеристик цветности. Для формирования признаков текстур использован кратномасштабный анализ изображений. Инвариантность к переносу достигается исключением процесса децимации из ДВП. Для сокращения пространства признаков можно выбирать субполосы с большей энергией (2).
Выполнено сравнение методов сегментации текстур, основанных на оценке энергии коэффициентов ДВП, при использовании разных вейвлет-базисов.
Проведено исследование сегментации цветных текстур на основании объединения цветовых и пространственных характеристик текстур при их описании в разных цветовых координатных пространствах. Показано, что использование характеристик цветности позволяет повысить эффективность сегментации.
*****
ЛИТЕРАТУРА
1. Фисенко В.Т., Фисенко Т.Ю. Сегментация цветных текстурных изображений // Международная конференция. Прикладная оптика: Сборник трудов. СПб., 2008. Т. 3. С. 359–363.
2. Фисенко В.Т., Фисенко Т.Ю. Компьютерная обработка и распознавание изображений: учеб. пособие. СПб: СПбГУ ИТМО, 2008. 192 c.
3. Харалик Р.М. Статистический и структурный подходы к описанию текстур // ТИИЭР. 1979. Т. 67. № 56. С. 98.
4. Малла С. Вэйвлеты в обработке сигналов: Пер. с англ. М.: Мир, 2005. 671 с.
5. Леоненков А.В. Нечеткое моделирование в среде MATLAB и fuzzyTECH. СПб.: БХВ-Петербург, 2005. 736 с.
6. Фисенко В.Т., Фисенко Т.Ю. Метод автоматического анализа цветных изображений // Оптический журнал. 2003. Т. 70. № 9. C. 18–23.
7. Manjunath B., Ohm J.-R., Vasudevan V., Yamada A. Color and Texture Descriptors // IEEE Trans. Circuits and Systems for Video Technology. 2001. V. 11. № 6. P. 703–715.
8. Brodatz P. A Photographic Album for Artists and Designers. New York, Dover, 1966.
9. Vision Texture [Электронный ресурс]. Режим доступа: http://vismod.media.mit.edu/vismod/imagery/ VisionTexture/vistex.html, 2012.
10. University of Oulu texture database [Электронный ресурс]. Режим доступа: http://www.outex.oulu.fi, 2012.
“Оптический журнал”, 79, 11, 2012
27