Лабораторная работа № 2. Кластерный анализ в распознавании образов

КЛАСТЕРНЫЙ АНАЛИЗ В РАСПОЗНАВАНИИ ОБРАЗОВ

Цель работы: ознакомиться с интерпретацией многомерных образов в виде кластеров. Освоить статистическое описание образов в многомерном пространстве признаков. Исследовать особенности распознавания образов с использованием различных метрик.

Теоретические сведения

Выделение связных областей

Есть два метода выделения связных областей:

· Рекурсивный алгоритм

· Итеративный метод (алгоритм последовательного сканирования)

Допустим, мы имеем черно-белое изображение. Таковым будем называть изображение, состоящее из точек только двух цветов: цвета фона и цвета объектов. Чаще всего обозначают 0 – фоновый цвет, 1 –цвет объекта. В таком случае выделенные области всегда будут одинаковыми при неизменном типе связности (4- или 8- связном).

Рекурсивный алгоритм

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

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