Правительство Российской Федерации
Федеральное государственное бюджетное образовательное
учреждение высшего образования
«Санкт-Петербургский государственный университет»
Кафедра информатики
Виденеева Мария
Разработка алгоритмов анализа и классификации изображений с
применением вейвлет-преобразований
Выпускная квалификационная работа
Научный руководитель:
К.ф.-м.н., доцент
Соловьев И.П.
Рецензент:
К.ф.-м.н.,
Терентьев С.В.
Санкт-Петербург
2016
SAINT-PETERSBURG STATE UNIVERSITY
Mathematics and Mechanics Faculty
Department of Informatics
Videneeva Mariia
The design of image analysis and classification algorithms with the use of
wavelet transforms
Graduation Qualification Paper
Scientific supervisor:
PhD, associate professor
Soloviev I.P.
Reviewer:
PhD,
Terentev S.V.
Saint-Petersburg
2016
Оглавлени
Введение.......................................................................................................4
1. Основные понятия................................................................................ 7
1.1 Понятие фрактальной размерности..................................................8
1.2.Метод фрактальной сигнатуры......................................................... 9
1.3. Вейвлет-преобразование................................................................10
2. Численные эксперименты.....................................................................14
Заключение................................................................................................ 19
Литература................................................................................................. 20
Введение
Одной из наиболее актуальных задач современности и на текущий
момент остается цифровая обработка изображений. Спектр
применения очень широк: обработка документов, распознавание
текстов и штриховых кодов, видеонаблюдение и системы
безопасности, цифровая фотограмметрия и бесконтактные измерения,
биометрия, зрение роботов и многое другое. В отдельное направление
можно выделить автоматизированную обработку изображений в таких
областях как биология и медицина. Обработка изображений с целью
их распознавания является одной из центральных и практически
важных задач при создании систем искусственного интеллекта.
Работа с цифровыми изображениями предполагает необходимость не
только получение практических данных, которые несет в себе
изображение, но и обработку целых множеств образцов
и их
разбиение на классы, выделение структуры. Задача анализа и
к л а с с и ф и ка ц и и ц и ф р о в ы х изо б р а же ний пр ивод ит на с к
необходимости выбора подходящего метода исследования из целого
ряда таких методов, ориентированных на специфические области
применения и опирающихся на различные математические и
компьютерные модели: морфологические методы, частотная и
линейная фильтрация, нейронные сети, текстурный анализ, вейвлетпреобразования и вычисление фрактальных характеристик
изображения. Так, для анализа текстовых изображений, часто
применяют морфологические методы, для анализа изображений
биомедицинских препаратов — статистические текстурные [4,7].
В литературе нет единого определения, дающего понятия «текстуры».
Формулировка Пикетта: «текстура используется для описания
двумерных массивов изменений яркости», Претта – «текстура –
оп и с ан и е п ро ст ран ственной упорядоченно сти элементов
изображения», Харалика – «текстура – организованный участок
поверхности», Тамуры – «текстура – нечто составляющее
макроскопическую область», Ричарда – «текстура определена для
наших целей как атрибут поля, не имеющего никаких компонентов
(составляющих), которые выступают счетными (перечислимыми)»
[15,16,17].
Среди свойств, позволяющих определить текстуру можно выделить
распределение значений серого в пространстве. Именно оно лежит в
основе большинства применяемых методов. Текстура в данном случае
будет определяться как некоторая двумерная функция задающая
з н а ч е н и я с е р о г о . Э то с в о й с т в о т е кс ту р ы п о з в ол я е т е е
классифицировать, а именно выделять типы однородных областей
сопоставимых определенному классу. Позволяет также определять
границы текстуры — это задача сегментации текстур.
Другое важное свойство для текстуры это повторяющийся характер
расположения текстурных элементов в изображении. Здесь свое
применение находят методы, позволяющие вычислять фрактальные
характеристик изображения.
Таким образом текстурные методы охватывают достаточно широкий
класс задач в т.ч. таких как вычисление фрактальных характеристик и
сегментация изображений.
На практике в медицине наиболее часто применимыми являются
текстурные методы. Примеры такого применения этого можно найти в
[17]. Наряду с изображениями, представляющими снимки
макроструктур (органы и ткани), несомненный интерес представляют
снимки, полученные с помощью микроскопа. Здесь хорошо
зарекомендовали себя мультифрактальные методы, позволяющие
получать характеристику изображения в виде спектра (вектора)
значений [7, 18].
С другой стороны вейвлеты зарекомендавали себя при решении задач
сжатия и увеличения исходного изображения с минимальными
потерями информации. Вейвлет-преобразования также позволяют
проводить операции размытия и наведения резкости, выделения
областей перепадов яркости.
В рамках данного исследования мы рассматриваем несколько
подходов к анализу и классификации изображений. Основной фокус
направлен на вычисление их фрактальных характеристик. В методах
используется фрактальная сигнатура цветного изображения,
приведенного в палитру grayscale (G) или представленного в
компоненте H палитры HSV. Изображение рассматривается как
целочисленная функция F, т.е. двумерная поверхность [10].
Можно выделить два основных исследуемых метода. В первом методе
используется фрактальная сигнатура исследуемого изображения, где
фрактальная сигнатура вычисляется согласно [11] (метод фрактальной
сигнатуры). Второй метод основан на вычислении фрактальных
характеристик вейвлет-преобразования изображения с помощью
метода, описанного в [1]. Метод фрактальной сигнатуры заключается
в вычислении площади поверхности A δ
так называемого δ-
параллельного тела для поверхности графика функции F. Под δпараллельным телом понимают множество точек, находящихся на
расстоянии не более чем δ от поверхности графика функции F.
Отношение log2 A δ /
log2 δ
называется фрактальной сигнатурой.
Путем последовательного изменения δ в некотором диапазоне [1,N]
вычисляется вектор фрактальных сигнатур, используемый нами в
качестве характеристики изображения [6,7].
Для того чтобы выполнить вейвлет-преобразование, мы использовали
функцию Гаусса и ее вторую частную производную, что обусловлено
ее хорошими локальными свойствами [5].
Мы применяем такое преобразование к рассматриваемому цифровому
изображению и затем вычисляем фрактальную сигнатуру полученного
вейвлет-преобразования, которое мы рассматриваем как новое
и з о б р а ж е н и е . И з м е н я я з н ач е н и я м а с ш т а б а в п р е д е л а х
экспериментально установленного диапазона мы получаем
последовательность вейвлет-образов и вектор из соответствующих им
фрактальных сигнатур. При этом фрактальная сигнатура вычисляется
для δ = 1, 2.
Таким образом, каждому исследуемому изображению сопоставляется
два вектора фрактальных сигнатур. В обоих методах полученные
вектора используются для того, чтобы определить принадлежность
различных изображений к одному классу: чем меньше расстояние
между векторами сравниваемых изображений A и B, тем больше
вероятность того, что A
иB
принадлежать к одному классу.
Проведенные эксперименты позволяют нам выбрать метод,
показавший лучшее разделение для входного множества изображений,
заранее разделенного на классы.
Постановка задачи
Цель: исследование применимости описанных выше алгоритмов для
классификации сложных текстурных изображений. Реализация
программной системы, которая основана на фрактальных и
мультифрактальных методах обработки изображений.
Были выделены следующие подзадачи:
1. Исследование и апробация метода модифицированной
фрактальной сигнатуры.
2. Исследование и апробация метода модифицированной
фрактальной сигнатуры основанного на вейвлет-преобразовании.
В качестве анализируемых образцов были выбраны изображения
биомедицинских препаратов.
1. Основные понятия
Исходное
исследуемое изображение представляется
дискретной
функцией F в grayscale или HSV (компонента H) палитре:
F = {Хij, i=0,1,…,K, j=0,1,…,L}, где Хij —интенсивность пикселя, K, L
– задают размер изображения. В точках с вещественными
координат ами F доопределим значением на левом конце
целочисленного отрезка. Это позволит нам говорить о поверхности
графика функции F и вычислять ее площадь.
1.1.
Понятие фрактальной размерности
В настоящее время одной из наиболее часто используемых
размерностей является емкостная из-за простоты ее вычисления [6].
Емкостная размерность относится к классу так называемых boxcounting размерностей и обозначается dim B .
Рассмотрим F – непустое ограниченное множество в Rn, Ω
={ωi:i=1,2,3..} – его покрытие. Обозначим Nδ(F) число множеств ωi с
диаметром меньше δ.
Предположим, что:
Nδ(F)=δ-D.
(1.1.1)
Определим нижнюю и верхнюю границу емкостной размерности для
F:
dim B F = lim
δ →0
(1.1.2)
log2 N δ ( F)
−log2 δ
lim ¿
δ →0
dim´ B F=¿
log2 N δ ( F)
−log2 δ
Если верхняя и нижняя границы существуют и совпадают, то их общее
значение называется емкостной размерностью:
dimBF= lim
δ →0
log 2 N δ (F)
−log 2 δ
(1.1.3)
Тогда:
D=dimBF
1.2.
(1.1.4)
Метод фрактальной сигнатуры
Метод основан на идее Б. Мандельброта о приближенном вычислении
длины береговой линии, которая имеет сложную фрактальную
структуру [2]. Рассматривается полоса шириной 2δ, окружающая
линию. Длина определяется как площадь полосы, деленная на 2δ.
Проведенные измерения показали, что существует диапазон значений
по δ, в котором результат стабилизируется. Авторы [9] применили эту
идею к вычислению приближенного значения площади поверхности
графика функции, представляющей цифровое изображение. Для этого
нужно построить специальную окрестность полученной поверхности
(так называемое δ-параллельное тело), вычислить ее объем и поделить
его на высоту тела. Меняя значение δ, мы получаем несколько
приближений к искомой площади.
Следуя [11] определим δ-параллельное тело как множество точек,
находящихся на расстоянии не более чем δ от поверхности графика
функции F. Они образуют «покрывало» толщиной 2δ (Рис. 1), которое
имеет верхнюю (uδ ) и нижнюю (bδ ) границы, которые вычисляются в
каждой точке изображения с использованием значения интенсивности
пикселя, соответствующего этой точке и интенсивности его соседей из
выбранной окрестности.
Рис. 1. Поверхность и покрывало
Верхняя и нижняя граница δ-параллельного тела вычисляются по
следующим формулам:
uδ ( i , j )=max {uδ−1 ( i , j ) +1,
max
|( m ,n )−( i , j )|≤1
b δ ( i, j )=min {b δ−1 ( i , j )−1,
uδ−1(m ,n)}
min
|( m, n ) −( i , j )|≤ 1
uδ−1 (m , n)}
(1.2.1)
Объем полученного тела определяется как
Volδ=∑i,j(uδ(i,j)-bδ(i,j))
(1.2.2)
Для вычисления площади поверхности можно использовать два
варианта формул
A δ=Vol δ /2 δ ,
(1.2.3)
или
A δ=
(1.2.4)
Vol δ −Vol δ−1
2
Оказывается, что для фрактальных поверхностей формула (1.2.4)
более предпочтительна и мы будем использовать ее в дальнейшем.
Фрактальная сигнатура Sδ определяется как
Sδ =
log A δ
log δ
.
(1.2.5)
Д л я δ ∈[1, N ]
вычисляется последовательнорсть значений Sδ .
Приближенное значение фрактальной сигнатуры Sδ
определяется
методом наименьших квадратов и задает коэффициент угла наклона
прямой (в двойной логарифмической шкале), наилучшим образом
аппроксимирующей три точки: (log(δ-1), log(Aδ-1)), (log(δ) , log(Aδ)) и
(log(δ+1), log(Aδ+1)).
Путем последовательного изменения δ в пределах экспериментально
определенного диапазона, для каждого конкретного изображения
вычисляется вектор фрактальных сигнатур, который и является
фрактальной характеристикой изображения. Для сравнения
изображений (оценки степени их близости) вычисляется декартово
расстояние между соответствующими векторами.
1.3. Вейвлет-преобразование
О с н о в н ы м отл и ч и е м д а н н о го м е тод а я вл я е т с я ве й вл е т преобразование, применяемое непосредственно к дискретной
функции, представляющей исследуемое изображение [4,8].
Вейвлетные преобразования применяются при обработке цифровых
изображений в следующем порядке:
• Вычисляется двумерное вейвлет-преобразование
изображения;
• Вносятся изменения в коэффициенты преобразования;
• Вычисляется обратное преобразование.
Так как нас в нашем исследовании не интересует конечный внешний
вид обработанного изображения, обратное преобразование мы к нему
не применяем.
Вейвлетное преобразование позволяет изучить изображение с
различных точек зрения в силу того, что сам вейвлет возможно
подобрать с учетом особенностей того или иного изучаемого класса
изображений. Кроме того, вейвлетное изображение позволяет
проводить масштабирование изображения.
Вейвлеты – это функции типа маленькой волны (всплески), которые
порождают базисы пространства L2(R), удобные для обработки
сигналов. Кроме того, это обобщённое название математических
функций локальных во времени и по частоте и в которых все функции
получаются из одной базовой, изменяя её.
Вейвлет-преобразование непрерывной функции производится по
следующей формуле:
∞
( )
1
t −b
T ( a , b )=
x ( t ) φ¿
dt
∫
a
√ a −∞
(1.3.1)
Гдe параметр b ϵ R соответствует временному сдвигу, параметр a>0
задает масштабирование.
Так как мы применяем такое преобразование к изображению,
представленному в дискретной форме двумерной функцией grayscale,
нам необходимо рассмотреть дискретизацию вейвлет-преобразования.
Пусть Δt – некоторый достаточно малый промежуток времени.
Рассмотрим последовательность точек t n = nΔt и соответствующую
последовательность: x n = f(nΔt), n ∈ Z значений сигнала f(t).
По определению интеграла, при малых Δt мы будем иметь
приближенное равенство:
∞
( )
∞
(
)
t −b
n ∆ t−b
f ( ω )= ∫ f ( t ) φ
dt ≈ ∑ f ( n ∆ t ) φ¿
dt
a
a
n=−∞
−∞
¿
'
(1.3.2)
Тогда дискретное двумерное вейвлет-преобразование примет вид:
φ m, n =a−m/2
φ
0
(
t−n b0
m
a0
)
(1.3.3)
∞
(1.3.4)
T m .n = ∫ x ( t ) φ¿m ,n ( t ) dt
−∞
Величины T m ,n также известны как вейвлет-коэффициенты.
∞
x ( t )= K φ
∞
∑ ∑
m=−∞ n=−∞
(1.3.5)
T m, n φm ,n (t)
где Kψ – постоянная нормировки. K ψ −постоянная нормировки
В отличие от преобразования Фурье, вейвлетное преобразование
обозначает целый класс преобразований, которые различаются не
только используемыми функциями разложения, но и самой природой
этих функций, а также тем способом, как их следует применять
(например, сколько различных разрешений следует применять).
В наших экспериментах вейвлет-преобразование выполняется по
формуле (1.2.2):
1
W ( a ,b1 , b2 ) =¿
a
K −1 L−1
∑
∑φ
x =0 y=0
( x−ba , y−ba ) F ( x , y )
1
2
(1.3.6)
где a – параметр масштаба, b1, b2 — смещения по осям координат, φ –
вейвлет. В нашем случае:
φ ( x , y )=¿ exp
(
2
2
)
−x y
2
2
− ∗(x + y +2 xy−2)
2
2
(1.3.7)
В формуле (1.3.7) вейвлет конструируется с использованием частных
производных второго порядка функции Гаусса (1.3.8):
2
G ( x , y ) =exp(
2
−x y
− )
2
2
(1.3.8)
Такой вейвлет был выбран, так как имеет узкий энергетический
спектр, что дает ему определенные преимущества при анализе
особенностей высокого порядка [5]. Мы применяем к исходному
изображению вейвлет-преобразование, построенное с помощью
второй производной функции Гаусса. Вторая производная была
выбрана по нескольким причинам: производные высших порядков
позволяют получить более точные результаты (что подтверждается
проведенными экспериментами),
производные выше второй
усложняют вычисления и не показывают достаточной весомой
разницы в точности результатов.
Для функции, представляющей изображение, выполняется вейвлетпреобразование, где а – фиксировано, b1, b2 изменяются от 1 до K, L
соответственно (K, L задают размер изображения). Полученный
результат будем трактовать как
новое «изображение» такого же
размера, как исходное, каждой точке которого соответствует значение,
полученное путем преобразования функции F для соответствующих
b1, b2.
Последовательно изменяя значение параметра масштаба в диапазоне,
сопоставимом с диапазоном предыдущего метода, для каждого
изображения, получаем набор связанных с ним образов. К каждому
образу применяем МФС. Набор фрактальных сигнатур, вычисленный
таким способом, определяет характеристический вектор исходного
изображения.
2. Численные эксперименты
Для проведения эксперимента были выбраны изображения двух
классов: снимки здоровой печени и снимки печени с жировой
дистрофией (FLD) (Рис. 2 и Рис. 3). Все рассматриваемые снимки
имеют одинаковый размер: 300х300. Для наглядности проведенного
эксперимента было выбрано по 5 представителей каждого класса.
Рис. 2. Снимки здоровой печени.
Рис. 3. Снимки печени с жировой дистрофией.
Все исследуемые изображения были предварительно разделены на
классы с помощью эксперта.
В результате метода МФС к изображениям в палитре HSV видимого
разделения входного множества изображений на классы после
преобразования не произошло (Рис. 4.).
Рис. 4. Результат применения метода МФС к исследуемым
изображениям в палитре HSV: вектора смешаны.
Отметим, что величина вектора (число 30) была определена
эмпирическим путем, далее с увеличением δ изменение значения
фрактальной сигнатуры незначительно. А для результатов,
полученных с помощью второго метода, достаточно и первых 10
итераций, далее все результаты стабилизируются.
Результаты применения второго метода к изображениям в палитре
HSV, напротив, позволили говорить о четком разделении результатов
на два класса.
На приведенном ниже графике (Рис. 5) представлена зависимость
значений фрактальной сигнатуры от изменения параметра масштаба,
штриховой линией обозначены вектора, полученные для снимков
здоровой печени, сплошной – для снимков печени с жировой
дистрофией. Полученный график позволяет говорить о разделении
входного множества изображений на два класса, а также о том, что
вейвлет-преобразования позволило улучшить степень разделения
изображений по сравнению с результатами первого метода.
Р и с . 5. Ре зул ьт ат п ри м е н е н и я м е тод а с в е й вл е т
преобразованием к исследуемым изображениям в палитре
HSV: вектора разделились на 2 класса.
Аналогично, как и для результатов изображений в палитре HSV,
результаты применения первого
метода к изображениям в палитре
grayscale не позволили сделать однозначный вывод
о разделении
входного множества изображений на два класса, ввиду чего были
рассмотрены графики усредненных значений векторов, значений
максимумов и значений минимумов. Наиболее показательным
оказался график максимумов значений векторов фрактальной
сигнатуры (Рис. 6)
Результаты, отраженные на графике ниже, говорят о слабой
различимости данных классов изображений в палитре grayscale при
применении первого метода.
Рис. 6. Результат (максимумы) применения метода МФС к
исследуемым изображениям в палитре gray scale: значения
векторов близки.
Применение второго метода к этим же изображениям не привело к
существенным улучшениям в решении задачи разделения входного
множества на классы (Рис. 7).
Р и с . 7. Ре зул ьт ат п ри м е н е н и я м е тод а с в е й вл е т
преобразованием к исследуемым изображениям в палитре
gray scale: вектора неотличимы друг от друга.
Аналогичные вычисления были проведены для снимков печени с
полнокровием (Рис. 8 и рис. 9). Полученные результаты были
сравнены с результатами для снимков здоровой печени и печени с
жировой дистрофией. Как и ранее, наиболее точное разделение на
классы было получено в результате применения второго метода к
изображениям в палитре HSV (компонента H).
На рис. 8 представлены вектора, полученные для снимков здоровой
печени (пунктирная линия) и снимков печени с полнокровием. Из
представленного графика видно, что в среднем значения векторов,
получаемые для снимков здоровой печени лежат выше чем вектора
второго класса изображений.
Р и с . 8. Ре зул ьт ат п ри м е н е н и я м е тод а с в е й вл е т
преобразованием к исследуемым изображениям в палитре
HSV: вектора разделились на 2 класса.
На рис. 9 представлены вектора полученные для снимков печени с
полнокровием и снимков печени с жировой дистрофией (пунктирная
линия). В данном случае мы видим ситуацию, аналогичную
представленной на предыдущем графике: в среднем значения векторов
сравниваемых между собой классов изображений различимы друг от
друга.
Р и с . 9. Ре зул ьт ат п ри м е н е н и я м е тод а с в е й вл е т
преобразованием к исследуемым изображениям в палитре
HSV: вектора разделились на 2 класса.
В таблице ниже приведены варианты сочетаний методов и палитры
представления изображений, знаком «+» отмечен наилучший
результат.
HSV
grayscale
method 1
-
method 2
+
-
Заключение
В ходе проведенных экспериментов были получены результаты для
обоих методов: после применения к изображениям в градациях серого
и в шкале HSV (компонента H). Во всех случаях результаты оказались
более точными, когда методы применялись к изображениям в шкале
HSV (компонента H).
Также можно говорить о том, что в некоторых случаях применение
вейвлет-преобразования к изображениям позволяет более точно
разделить входное множество изображений на классы. Эксперименты
показывают, что второй метод может быть применен для разделения
множества цифровых изображений биомедицинских препаратов,
имеющих ярко выраженные текстурные особенности.
Литература
[1] A. N. Pavlov, V. S. Anishchenko. Multifractal analysis of complex
signals. International Research Institute of Nonlinear Dynamics,
N. G. Chernyshevskii Saratov State University, 2007.
[2] B. B. Mandelbrot, The Fractal Geometry of Nature San Francisco, CA:
Freeman, 1982
[3] C.K.Chui. An Introduction to wavelets. M. Mir (2001).
[4] I. Soloviev, N. Ampilova, E. Gurevich. On implementation of a neural
network classifier for some classes of biological and medical
preparation images. Proc. 7 Int. Conf. CEMA12, 8-10 Nov. 2012,
Athens, Greece. P. 94-97.
[5] K. A. A l e k s e e v .
Around
http://matlab.exponenta.ru/wavelet/book3/4.php
the
C W T.
[6] K.J.Falconer. Fractal Geometry. Mathematical Foundations and
Applications. — John Wiley & Sons, 1990.
[7] N. Ampilova, E. Gurevich, I. Soloviev. Application of Modified Fractal
Signature & Regny Spectrum Methods to the Analysis of Biomedical
Preparations Images. Proc. 6 Int. Conf. CEMA11, 6-8 Oct. 2011, Sofia,
Bulgaria. p. 96-100.
[8] N.M.Astaf'eva. Wavelet Analysis: Theoretical Backgrounds and
Application Examples, Usp. Fiz. Nauk 166 (11), 1145–1170 (1996).
[9] Peleg Shmuel, Naor Joseph, Hartley Ralph, Avnir David. Multiple
Resolution Texture Analysis and Classification. IEEE Transactions on
pattern analysis and machine intelligence, vol. PAMI-6, NO. 4, July
1984
[10] R.
Gonzalez, R. Woods. Digital Image Processing. Tekhnosfera, (2006)
[11] Y. Y. Tang, Hong Ma, Dihua Xi, Xiaogang Mao, C. Y. Suen.
Modified Fractal Signature (MFS): A New Approach to Document
Analysis for Automatic Knowledge Acquisition. — IEEE Trans.
Knowledge and Data Eng., vol.9. no. 5, 1997, pp. 742-762.
[12] Н.К. Смоленцев: Основы теории вейвлетов, Москва 2005
[13] В.Т. Фисенко, Т.Ю. Фисенко: Компьютерная обработка и
распознавание изображений – учебное пособие, Санкт-Петербург
2008
[14]
Wiki – Техническое зрение: Преобразование Фурье. Линейная
фильтрация
в
частотной
о б л а с т и .URL:
http://wiki.technicalvision.ru/index.php/Заглавная_страница
[15] Coggins J.M. A Framework for Texture Analysis Based on Spatial
Filtering Ph. D. // Computer Science Department. – Michigan:
Michigan State University, 1982. 3.
[16] Tamura H., Mori S., Yamawaki Y. Textural Features Corresponding to
Visual Perception // IEEE Transactions on Systems, Man and
Cybernetics. – 1978. – № 8. – P. 460-473.
[17] Haralick R.M. Statistical and Structural Approaches to Texture // Proc.
of the IEEE, 67. – 1979. – P. 786-804.
[18]
Yong Xu, Hui Ji, Cornelia Fermüller.Viewpoint Invariant Texture
Description Using Fractal Analysis - Springer Science+Business
Media, LLC 2009
Отзывы:
Авторизуйтесь, чтобы оставить отзыв