Методы теории графов и распознавание

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

Сначала дадим несколько простых определений. Граф G = (N, А) представляет собой конечное, непустое множество вершин N вместе с множеством А неупорядоченных пар различных элементов из N. Каждая пара из А называется дугой.

Граф, в котором дуги являются направленными, называется направленным графом. Если дуга выходит из вершины ni, к вершине nj, тогда nj называется преемником вершины ni. В этом случае вершина ni называется предшественником вершины nj. Процесс идентификации преемников каждой вершины называется расширением этой вершины. В каждом графе определяются уровни таким образом, чтобы нулевой уровень состоял из единственной вершины, называемой начальной, а последний уровень-из вершин, называемых целевыми. Каждой дуге (ni nj) приписывается стоимость c(ni nj). Последовательность вершин n1, n2, ., nk, где каждая вершина ni является преемником вершины ri-1, называется путем от ni к nk, а стоимость пути определяется формулой

. (2.4)

Элемент контура мы определим как границу между двумя пикселями р и q. В данном контексте под контуром понимается последовательность элементов контура.

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

Граф (или дерево) распознавания по геометрическим признакам представлен на рис… Цифрами I, II, …, X обозначены возможные решения - номера распознаваемых объектов. Буквы A, B, …, Q в вершинах графа обозначают операторы, выделяющие определенные признаки изображения. Например, оператор А проводит классификацию изображения по длине и высоте описанного прямоугольника, операторы В и С - по площади, DEFG могут быть операторами, проводящими классификацию по числу углов, H и Q - по отстоянию углов друг от друга. Граф может иметь больше или меньше уровней, и содержание операторов может быть различным.

Рисунок 2.1 - Дерево распознавания

Другое по теме:

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

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

©  www.techvarious.ru - 2019