В задаче аппроксимации многоугольниками применяются методы объединения, основанные на ошибке или других крите­риях. Один из подходов состоит в соединении точек границы линией по методу наименьших квадратов. Линия проводится до тех пор, пока ошибка аппроксимации не превысит ранее задан­ный порог. Когда порог превышается, параметры линии зано­сятся в память, ошибка полагается равной нулю и процедура повторяется; новые точки границы соединяются до тех пор, пока ошибка снова не превысит порог. В конце процедуры образу­ются вершины многоугольника в результате пересечения сосед­них линий. Одна из основных трудностей, связанная с этим под­ходом, состоит в том, что эти вершины обычно не соответствуют изгибам границы (таким, как углы), поскольку новая линия начинается только тогда, когда ошибка превысит порог. Если, например, длинная прямая линия пересекает угол, то числом (зависящим от порога) точек, построенных после пересечения, можно пренебречь ранее, чем будет превышено значение поро­гового уровня. Однако для устранения этой трудности наряду с методами объединения можно использовать методы разбиения.

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

3.2.Дескрипторы области

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

3.2.1.Некоторые простые дескрипторы.

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

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

Большая и малая оси области полезны для определения ориентации объекта. Отношение длин этих осей, называемое эксцентриситетом области, также является важным дескриптором для описания формы области.

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

Связной называется область, в которой любая пара точек может быть соединена кривой, полностью лежащей в этой об­ласти. Для множества связных областей (некоторые из них имеют отверстия) в качестве дескриптора полезно использовать число Эйлера, которое определяется как разность между числом связных областей и числом отверстий. Например, числа Эйлера для букв А и В соответственно равны 0 и —1. Другие дескрип­торы области рассматриваются ниже.

3.2.2.Текстура.

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

3.2.3.Скелет области.

Важным подходом для описания вида струк­туры плоской области является ее представление в виде графа. Во многих случаях для этого определяется схема (скелет) об­ласти с помощью так называемых прореживающих (или же сокращающих) алгоритмов. Прореживающие процедуры иг­рают основную роль в широком диапазоне задач компьютерного зрения — от автоматической проверки печатных плат до под­счета асбестовых волокон в воздушных фильтрах. Скелет об­ласти можно определить через преобразование средних осей (ПСО), предложенное в работе. ПСО области R с грани­цей В определяется следующим образом. Для каждой точки р из R мы определяем ближайшую к ней точку, лежащую на В. Если р имеет больше одной такой точки, тогда о ней говорится, что она располагается на средней оси (скелете) области R. Важно отметить, что понятие «ближайшая точка» зависит от определения расстояния, и поэтому на результаты операции ПСО будет влиять выбор метрики. Хотя ПСО дает довольно удовлетворительный скелет обла­сти, его прямое применение затруднительно с вычислительной точки зрения, поскольку требуется определение расстояния между каждой точкой области и границы. Был предложен ряд алгоритмов построения средних осей, обладающих большей вычислительной эффективностью. Обычно это алгоритмы про­реживания, которые итеративно устраняют из рассмотрения точки контура области так, чтобы выполнялись следующие ограничения:

1) не устранять крайние точки;

2) не приводить к нарушению связности;

3) не вызывать чрезмерного размывания области.

4.СЕГМЕНТАЦИЯ И ОПИСАНИЕ ТРЕХМЕРНЫХ СТРУКТУР

В предыдущих двух разделах основное внимание уделялось методам сегментации и описания двумерных структур. В этом разделе мы рассмотрим эти задачи применительно к трехмер­ным данным сцены.

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

Возможны три основные формы представления информа­ции о трехмерной сцене. Если применяются датчики, измеряю­щие расстояние, то мы получаем координаты (х, у, z) точек поверхностей объектов. Применение устройств, создающих сте­реоизображение, дает трехмерные координаты, а также инфор­мацию об освещенности в каждой точке. В этом случае каждая точка представляется функцией f (х, у, z), где значения послед­ней в точке с координатами (х, у, z) дают значения интенсив­ности в этой точке (для обозначения точки в трехмерном про­странстве и ее интенсивности часто применяется термин вок сел). Наконец, можно установить трехмерные связи на основе одного двумерного образа сцены, т. е. можно выводить связи между объектами, такие, как «над», «за», «перед». Поскольку точное трехмерное расположение точек сцены обычно не может быть вычислено на основе одного изображения, связи, полу­ченные с помощью этого вида анализа, иногда относятся к так называемой 2,5-мерной информации.