18. Задача выделения осевых линий объектов изображения как задача автоматической классификации.

Задача классифика́ции — формализованная задача, в которой имеется множество объектов (ситуаций), разделённых некоторым образом на классы. Задано конечное множествообъектов, для которых известно, к каким классам они относятся. Это множество называется выборкой. Классовая принадлежность остальных объектов неизвестна. Требуется построитьалгоритм, способный классифицировать (см. ниже) произвольный объект из исходного множества.

Классифици́ровать объект — значит, указать номер (или наименование) класса, к которому относится данный объект.

Классифика́ция объекта — номер или наименование класса, выдаваемый алгоритмом классификации в результате его применения к данному конкретному объекту.

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

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

Некоторые алгоритмы для решения задач классификации комбинируют обучение с учителем с обучением без учителя, например, одна из версий нейронных сетей Кохонена — cети векторного квантования, обучаемые с учителем.

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

7

20. Алгоритм классификации типа Форэл.

1.         Управляющий параметр алгоритма

2.         Радиус гиперсферы

3.         Определение значения радиуса

 

При решении практических задач полезно иметь некоторый быстродействующий алгоритм кластерного анализа для получения первых представлений о структуре исследуемого множества исходных допустимых объектов. Одним из таких алгоритмов является Форэль–1 (первоначальное название ФОРЭЛ – формальный элемент).

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

Шаг 1. Задаются исходное множество допустимых объектов S_iÎS, i=1,..., m, радиус R гиперсферы.

Шаг 2. Любой объект S_iÎS назначается центром Z₁(1) (эталоном) этой гиперсферы Q₁ и определяются объекты S_jÎS,.

Шаг 3. Переопределяется центр гиперсферы как усредненный центр

(2.40)

объектов, вошедших на предыдущем шаге в гиперсферу через формулу

, где m₁ – число объектов,

попавших в гиперсферу Q₁ ; S_j – объекты гиперсферы Q₁.

Шаг 4. Вновь определяются объекты S_iÎS, для которых, как и на предыдущем шаге,

r (Z₁ (2), S_j)=||Z₁ (2)-S_j||£ R, j=1, 2,..., m.

 

Шаг 5. Процедуры шагов 3, 4 повторяются до тех пор, пока не перестанут изменяться координаты центра тяжести (усредненного центра). Очевидно, при этом гиперсфера остановится в области локального или главного экстремума плотности объектов исходного множества S. Гиперсфера с центром Z₁(i) представляет собой кластер K₁.

Шаг 6. Из исходного множества S исключаются объекты S_jÎK₁, т.е. входящие в кластер K₁. Объекты, через которые гиперсфера проходила на своем пути к конечному положению, к моменту останова гиперсферы исключающиеся из нее, сохраняются, т.е. после формирования кластера K₁ исходное множество сокращается на число m₁, т.е. S^¢=S \ S(K₁).

Шаг 7. Если итерация не последняя или множество не распределено по кластерам полностью, процедура построения кластера повторяется с шага 2, в качестве первоначального центра выбирается объект S_iÎS^¢.

Таким образом, процедура выделения кластеров K_j повторяется до тех пор, пока все исходное множество S не будет разделено на кластеры K_j, j=1, 2,..., l, представленные центрами гиперсфер радиуса R. Очевидно, что величина l есть некоторая функция от радиуса R, l=f (R), т.е. в зависимости от величины R получается разное число l.

Применение алгоритма Форэль–1 для ряда последовательных значений R позволяет оценить наиболее предпочтительное число классов для данного множества S. При этом основанием для выбора числа классов может служить многократное повторение одного и того же числа классов для нескольких последовательных значений R и его резкое возрастание для следующего шага.

На основе алгоритма Форэль–1 строится целое семейство алгоритмов (разные модификации), целью которых является разбиение S на заданное число классов более сложной формы.