“Структурный подход к классификации изображений на основе нечетких групп

Введение

Классификация изображений требует обработки огромного количества информации. В этом процессе важно самого начала выделить информативную часть изображения, а ненужный шум отбросить. Это необходимо сделать, так как все алгоритмы классификаций работают с набором ключевых признаков, описывающих изображение. В данной статье предлагаются следующие методы для классификации текстурных изображений:

Выделение границ с последующим применением трансформации Хаффа, для выделения структуры изображения.

Построение нечетких групп – преобразований как описание взаимного расположения структурных элементов

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

Выделение структуры изображения

Как уже отмечалось выше в качестве информативной, то есть пригодной для классификации, части изображения будет использоваться его структурные элементы. В качестве структурной единицы будет использоваться отрезок. Но перед тем как начать выделение отрезков составляющих структуру изображения, его необходимо предобработать. В предобработку входит: подавление шумов, контрастирование, и выделение границ особенностей – перепады яркости. Для выделения границ использован метод Sobel. После выделения границ имеем изображение, в котором выделены особенности. На основе этих границ будет строиться структурное представление изображения, которое строиться с помощью трансформации Хаффа. В данной работе используется модификация алгоритма трансформации для выделения отрезков на изображении, описанная в работе[3]. Рассмотрим основные моменты алгоритма трансформации.

Суть алгоритма состоит в подсчете значимых пикселей лежащих на одной прямой, если их количество превысит порог, то считается, что они задают линию. Каждая линия задается в полярной системе координат в виде:

r = x cos(th)+y sin(th)

где x, y – координаты пикселя, r – расстояние до начала координат – по перпендикуляру, th – угол наклона нормали к линии.

Для получения отрезков, а не бесконечных линий использует метод скользящего окна, при этом окно сканирования должно быть малым по отношению к особенностям изображения. Окна сканирования плотно накладываются друг на друга, то есть каждый пиксель берется за центр окна при трансформации. Это позволяет управлять точностью выделения граничных точек отрезка с помощью различных порогов. С помощью порогов можно так же влиять на детализацию – от длинных прямых, до мелких отрезков, учитывающих каждый поворот линий. Для учета отрезков больших, чем окно сканирования весь процесс разбивается на два этапа. На первом этапе формируется локальный список отрезков, а потом они добавляются в глобальный список отрезков для всего изображения. При формировании глобального списка проверяется коллинеарность отрезков и их наложение, если они накладываются с заданной точностью, то формируется один длинный отрезок. Алгоритм вычисления локальных отрезков является независимым, что позволяет вести обсчет параллельно для нескольких окон. Примеры изображений после трансформации представлены на рисунках ниже.

Рис 1. Исходное изображение с выделенными границами.

Рис.2. Изображение после выделение отрезков.

Использование отрезков в качестве структурного элемента позволяют на порядок уменьшить объем обрабатываемой информации практически без потери качества изображения. Такое уменьшение используемой информации позволяет использовать целую картинку для формирования классификационного признака – нечетких групп-преобразований. Использование целого изображения исключает потери качества на стыках окна сканирования.

Построение классификационного признака

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

Классы сопряженных групп-преобразований описывают закономерности расположения структурных элементов изображения, а также их повторяющуюся фрактальную природу.

Единицей построения классов сопряженности берется отрезок и функция преобразования – импульс. В качестве функции берутся аффинные преобразования – сдвиг, масштаб, поворот.

Афинное преобразование - это композиция линейного оператора и трансляции (сдвига). Если линейный оператор представлен матрицей 3´3:

A = ,

то афинное преобразование "A + трансляция" можно представить матрицей 4´4, определяющей линейный оператор B:

B =

При этом трансляция определяется вектором (b1,b2). При применении B к точкам 2-х мерного пространства, последние представляют векторами (1,x,y)^T. Пусть (1,y₁,y₂)^T= B (1,x₁,x₂)^T, тогда y_i = b_i + a_i1_ּx₁ + a_i2_ּx₂. Афинное преобразование однозначно определяется двумя четверками точек, дающих 9 линейных уравнений с 9 неизвестными - параметрами преобразования. Подмножество взаимно-однозначных афинных преобразований является группой афинных преобразований.

Далее будем рассматривать группу преобразований вида:

это трансляция (a1,a2) + изменение масштабов по осям координат, определяемые масштабными коэффициентами k1,k2, y_i = a_i + kiּxi, i = 1,2. Такое преобразование однозначно определяется двумя парами точек (p1,p2) |® (p3,p4).

Пусть p_i = (x_i,y_i), тогда

k1 = ( x4 - x3 ) / ( x2 - x1 ),

a1 = x3 - k1 ּx1,

k2 = ( y4 - y3 ) / ( y2 - y1 ),

a2 = y3 - k2 ּ y1.

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

Множество импульсов формируют элементарную нечеткую группу. На множестве сопряженных элементарных нечетких групп, строятся их произведения - нечеткие группы более высокого порядка. Все полученные нечеткие группы распределяются по классам сопряженности и формируют так называемый "лес" классов сопряженности. Анализ его характеристик позволяет решать задачи классификации и идентификации текстур. Для такого анализа рассматривается мощность классов сопряженности, порядок и другие характеристики входящих в него нечетких групп. Совокупность значимых классов сопряженности нечетких групп образуют спектр, идентифицирующий текстуры, как структурные элементы изображения. В качестве инструментария для анализа и сравнения классов сопряженности может использоваться аппарат мат. статистики, нейронных сетей, нечетких множеств. Вышеописанный метод формирования классификатора (признака) текстур впоследствии используется для решения задач идентификации, классификации, сегментации текстур.

Реализация классификатора

На основе построенного множества классов сопряженности нечетких групп извлекались классифицирующие признаки согласно методике представленной ниже.

Строилась гистограмма, мощности классов сопряженности произведений элементарных групп. Далее значения гистограммы интерпретировались, как функция принадлежности нечеткого множества, что позволяло использовать различные индексы сравнения для классификации изображения. На гистограмме выделяется особенность характерная для заданного класса изображения таким образом, чтобы значение особенности было максимальным для текущего изображения и минимальным для всех остальных.

Метод тестировался на текстурах из альбома Brodatz. Алгоритм обучался на каждом рассматриваемом образце, то есть строилась гистограмма, и запоминались текущие классы сопряженности. По мере добавления образцов расширялась и гистограмма. Таким образом, формировалось единое пространство для сравнения текстур. При проведении эксперимента количество классов сопряженности достигало нескольких тысяч, учитывая что, отбрасывались маломощные классы (с малым числом элементов). Алгоритм классификатора был опробован для шести классов по первым образцам рядов D1,D10,D11,D20,D35,D82 альбома Brodatz, при этом достигнута 90% точность классификации( всего было проведено 100 запусков после проведения обучения). Программа также была опробована на сложных текстурах, включающие в себя не однородности. Пример таких текстур представлен на рис.3.

Рис3. Неоднородные текстуры.

При работе с неоднородными текстурами алгоритм не показал ухудшения качества классификации. Это объясняется введением единого пространства классификационного признака. В дальнейшем предполагается улучшить метод классификации через иерархический подход к рассмотрению объектов: с начало берутся только ярко выраженные особенности (“большие”), а потом более детальные. Такой подход позволит снизить время классификации и улучшить ее качество.

Литература

1. Муравьев Е.А. “Моделирование текстур и фракталов на основе нечетких групп и вейвлет-преобразования”., В. сб. трудов 4-й междунар. конф. по морским интеллектуальным технологиям МОРИНТЕХ-2001, СПб, с.304 - 307.

2. Высицкий К. А., Савенко В. В., Муравьев Е. А. “Текстурный анализ морского дна по данным гидролокатора” В. сб. трудов 4-й междунар. конф. по морским интеллектуальным технологиям МОРИНТЕХ-2001, СПб,

3. Yuefeng Zhang, Robert Webber. “A windowing approach to detecting line segments using Hough transform” . Pattern Recognition Vol 29 No 2, pp255-265 1996.