Алгоритм последовательного сканирования

⇐ ПредыдущаяСтр 5 из 6Следующая ⇒

1. если пиксель (x, y) помечен единицей на исходном бинарном изображении:

2. если пиксели (x − 1, y), (x, y − 1) не отнесены ни к одной из

3. найденных областей:

4. прибавить счетчик областей n = n + 1;

5. приписать пиксель (x, y) к области n;

6. если только один из пикселей (x − 1, y), (x, y − 1) отнесен к одной из

7. областей i:

8. приписать пиксель (x, y) к области i;

9. если оба пикселя (x − 1, y), (x, y − 1) отнесены к найденной

10. области i:

11. приписать пиксель (x, y) к области i;

12. если оба пикселя (x − 1, y), (x, y − 1) отнесены к разным

13. областям i, j: i = j:

14. приписать пиксель (x, y) к области i;

15. зафиксировать эквивалентность областей i и j;

16. перейти к следующему пикселю.

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

Псевдокод:

if A = O

do nothing

else if (not B labeled) and (not C labeled)

increment label numbering and label A else if B xor C labeled

copy label to A

else if B and C labeled

if B label = C label

copy label to A

else

copy either B label or C label to A

record equivalence of labels

0 – фон; 1 – цвет объекта.

Вычисление признаков

Геометрические признаки

Каждый физический объект обладает набором некоторых свойств, которые позволяют отличить его от других объектов (рис. 2.1).

Рис. 2.1. Различные объекты

Совокупность свойств, описывающих конкретный объект, называется образом данного объекта. Под классом объектов понимается некоторая совокупность образов, называемых элементами класса, обладающая рядом близких свойств. Измеряемые или вычисляемые свойства объектов, позволяющие отличить классы друг от друга, называются признаками.

Так на изображении объекты (области) можно отличить, используя следующие признаки:

1. Текстурные признаки;

2. Геометрические признаки;

3. Фотометрические признаки и др.

Для каждой области можно подсчитать некий набор простейших числовых характеристик:

· Площадь;

· Центр масс;

· Периметр;

· Компактность;

· Ориентацию главной оси инерции;

· Удлиненность (эксцентриситет).

На основе этих характеристик можно классифицировать получаемые объекты (области).

· Площадь – количество пикселей в области (рис. 2.2).

Рис. 2.2. Площадь объекта

. (2.1)

· Центр масс

, . (2.2)

· Периметр – количество пикселей, принадлежащих границе области (рис. 2.3).

Рис. 2.3. Периметр объекта

Периметр зависит от того, какую связность (4-х или 8-ми) используют при определении соседей. Также отличают внутреннюю и внешнюю границу объекта (рис. 2.4).

1. Пиксель лежит на границе области, если он сам принадлежит области, а хотя бы один из его соседей области не принадлежит (внутренняя граница).

2. Пиксель лежит на границе области, если он сам не принадлежит области, а хотя бы один из его соседей области принадлежит (внешняя граница).

Рис. 2.4. Граница объекта

Для распознавания, как правило, интересуют признаки, инвариантные к изменениям масштаба, переносу и повороту. Такими признаками являются удлиненность и компактность.

· Компактность – отношение квадрата периметра к площади (рис. 2.5):

. (2.3)

Наиболее компактная фигура – круг: π.

Рис. 2.5. Компактность фигуры

Дискретный центральный момент области определяется следующим образом:

, (2.4)

где – центр масс области.

· Удлиненность, нецентрированность (компактность) (рис. 2.6):

. (2.5)

Рис. 2.6. Удлиненность фигуры

· Ориентация главной оси инерции не является инвариантной к повороту, но в ряде случаев предоставляет полезную информацию об ориентации объекта (рис. 2.7):

. (2.6)

Рис. 2.7. Ориентация главной оси инерции объекта

Фотометрические признаки

Для каждой области можно подсчитать некий набор простейших числовых характеристик:

· Средняя яркость;

· Средний цвет (для цветного изображения);

· Гистограмма распределения яркостей (или для цветного изображения три гистограммы R, G, B);

· Дисперсия (разброс) яркости или цвета.

Кластерный анализ

Пусть число признаков равно n, тогда каждый образ можно представить в виде некоторого набора значений признаков или вектора признаков вида:

, (2.7)

где – значение i-го признака данного образа.

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

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

x₁₁	x₁₂	…	…	x_1m
…	…	…	…	…	(2.8)
x_n₁	x_n₂	…	…	x_nm

тогда

m=(µ₁, µ₂, …, µ_n): µ_i . (2.9)

(2.10)

где i, j =1, …, n – индексы номеров компонент вектора признаков; m – число образов, составляющих данный класс; – значение i-го признака k-го образа; µ_i- математическое ожидание i-ой компоненты вектора признаков; – дисперсия i-го признака; - коэффициент ковариации i-го и j-го признаков; m – вектор математических ожиданий; Cov – ковариационная матрица.

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

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

Под распознаванием образа понимается отнесение его к тому классу, расстояние до которого от данного образа в пространстве признаков минимально. Для определения расстояния между точками в метрическом пространстве признаков ранее было введено понятие метрики.

Методы распознавания можно разделить на две группы. К первой группе относятся методы, основанные на последовательном вычислении расстояний между распознаваемым образом и центрами кластеров в пространстве признаков с той или иной метрикой, например Евклидово расстояние. Образ считается принадлежащим классу, расстояние до которого минимально.

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

Выбор конкретного метода зависит от решаемой задачи. Существует около 100 разных алгоритмов кластеризации, однако чаще используется иерархический кластерный анализ и кластеризация методом k-средних (k-means).

⇐ Предыдущая 1 2 3 456 Следующая ⇒