Выделение контуров на малоконтрастных и размытых изображениях с помощью фрактальной фильтрации

Алиев М.В.

Кандидат физико-математических наук, доцент, зав. кафедрой прикладной математики и информационных технологий факультета математики и компьютерных наук Адыгейского государственного университета, тел. (8772) 59-39-04, e-mail: alievmarat@mail.ru

Панеш А.Х.

Кандидат технических наук, доцент кафедры прикладной математики и информационных технологий факультета математики и компьютерных наук Адыгейского государственного университета, тел. (8772) 59-39-04

Каспарьян М.С.

Студент 5 курса факультета математики и компьютерных наук Адыгейского государственного университета, тел. 89604787363

Источник: Вестник государственного унтверситета. Серия 4: Естественно-математические и технические науки

Аннотация

В статье описан способ быстрого вычисления фрактальной размерности (размерность Минковского). Предложен алгоритм выделения контура на малоконтрастных и размытых изображениях с помощью фрактальной фильтрации.

Ключевые слова: фрактальная фильтрация, распознавание образов.

1. Фракталы и фрактальная размерность

Выделение контура объекта на изображении является одной из актуальных задач в цифровой обработке сигнала [1-4]. Существуют различные подходы для решения данной задачи, но ни один из них не дает стабильного результата на малоконтрастных и размытых изображениях. В своих работах Потапов А.А.[1] предложил интерпрети- ровать такие объекты, как фрактальные.

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

В более широком смысле под фракталами понимают множество точек в евклидовом пространстве, имеющее дробную метрическую размерность (в смысле Минковско- го или Хаусдорфа), либо метрическую размерность, строго большую топологической.

Рассмотрим компактное множество A ? Rn . Покроем A объединением n-мерных шаров и просуммируем их объем (см. рис. 1).

Пусть N(? ) – минимальное количество шаров радиуса ? , необходимое для покрытия множества A.

Рис. 1. Покрытие множества A объединением шаров

Для подсчета размерности будем использовать размерность Минковского [2, 5, 6] в силу простоты вычислений.

Определение 2 [2]. Размерность Минковского или грубая (дробная) размерность ограниченного множества в метрическом пространстве равна

Если предел не существует, то можно рассматривать верхний или нижний предел и говорить соответственно о верхней и нижней размерности Минковского.

Для итеративного подсчета удобней использовать не формулу 1, а следующее соотношение:

log N(E) = log c - d logE,

где c – константа. Заметим, что log N(E) линейно зависит от log c , поэтому для определения c и d необходимо оценить N(E) для нескольких значений E

Не нарушая общности, заменим n-мерные шары n-мерными кубами со стороной E, так куб более естественен при обработке изображений.

2. Алгоритм вычисления фрактальной размерности и его оптимизация

Под изображением будем понимать дискретную функцию f (x, y) , заданную на матрице размером n*m [3], то есть

Тогда определение размерности Минковского состоит в следующем. Разобьем область, содержащую A, на квадратные клетки нескольких размеров. Затем посчита- ем количество клеток, необходимых для покрытия в каждом случае, и подставим в соотношение (2).

Рассмотрим монохромное изображение, тогда если точка изображения принадлежит фракталу A , то f (x, y) =1, в противном случае f (x, y) = 0. Таким образом, у нас имеется изображение фрактала, размерность которого необходимо найти. Следующий алгоритм вычисляет размерность фрактала.

Алгоритм 1 [2]. Размерность Минковского

Вход:

f – бинарная квадратная матрица фрактала, n, m – размер f , b – количество квадратов.

Выход:

d – оценка размерности Минковского.

Инициализация:

L/10 max L = p – максимальный размер клетки.

Шаги:

for L =1 to max L

N(L) = 0

B = p/L

for i =1 to B

for j =1 to B

Воспользуемся методом наименьших квадратов для построение прямой по точкам, при этом d (искомая размерность) – модуль углового коэффициента данной прямой.

Сложность данного алгоритма при n=m равна O(n4). Ее можно улучшить до O(n3) следующим образом.

Таким образом, для подсчета количества пикселей в прямоугольнике (рис. 2) получаем следующую формулу:

Рис. 2. Массив dp

Если изображение не является монохромным, а функция f (x, y) принимает значения на интервале [0, 255], то в алгоритме 1 необходимо рассматривать не клетки, а кубы. Соотношение (2) остается прежним, а вот формула (3) обобщается на трехмерный случай.

Данный алгоритм выделяет объекты на малоконтрастных и размытых изображениях. Стандартные алгоритмы [9] не способны выделить объекты на таких изображениях.

Рис. 3. Варианты объединения пикселей

На основе алгоритма 3 был разработан программный продукт (на языке Java [7,8]), результат работы которого проиллюстрирован на рисунке 4.

Заключение

В работе предложен алгоритм выделение контуров на малоконтрастных и размытых изображениях на основе фрактальной фильтрации. А также метод более быстрого подсчета размерностиМинковского по сравнению с алгоритмом, предложенным в работе [2].

По результатам исследований было установлено, что фрактальные методы более наглядно выделяют контуры, чем, например, оператор Собеля и другие стандартные алгоритмы. Это дает больше возможностей для дальнейшего анализа изображения.

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

1. Петров, В. О. Алгоритм текстурной сегментации растровых изображений при решении прикладных задач медико-биологического анализа / В. О. Петров, В. А. Ка- маев, С. В. Поройский // Современные проблемы науки и образования. – 2009. – № 6. – C. 106–110.

2. Bradski G., Kaebler A. OReilly-LearningOpenCV, 2008. – 577 с.

3. Кудряшов П. П. Гибридный алгоритм обнаружения человеческих лиц / П. П. Кудряшов, С. А. Фоменков //Информационные технологии. – 2007. – №10. – С. 20–23.

4. Стокман Д., Шапиро Л. Компьютерное зрение. – Бином. Лаборатория знаний, 2006 г. – 752 с.

5. Дзвид А. Компьютерное зрение. Современный подход. 2004. – 928 с.

6. Малинин В. В. Распознавание образов на ЭВМ. М: Учеба, 2005. – 573 с.

7. Буткарев А. И. Полировка. «АБ Универсал». Технологии, материалы, оборудование, инструменты, 2002.

8. Гаршин А. П. Абразивные материалы. Л., 1983.

9. ГОСТ 3647–80. Материалы шлифовальные. Классификация. Зернистость и зерновой состав. Методы контроля. – М, 1982.