Робототехника.Фу, Ли, Гонсалес (962794), страница 67
Текст из файла (страница 67)
В качестве иллюстрации описанной выше процедуры рассмотрим образ задней дверцы автомобиля, приведенный на рис. 8.!,а. Цель состоит в определении размеров прямоугольников, с помошью которых можно построить качественное изображение. Построение таких прямоугольников осуществляется в результате определения строго горизонтальных н вертикальных контуров. На рис. 8.!,б и в показаны горизонтальные и вертикальные компоненты операторов Соболя, рассмотренные в равд. 7.6.4.
На рис. 8.!,г показаны результаты соединения точек, которые одновременно имеют градиенты больше 25 и направле- 397 898 ния этих градиентов отличаются не более чем па !5 градусов. Горизонтальные линии построены путем последовательного применения этих критериев к каждой строке изображения (рис 8.1,в), а вертикальные линни — последовательным сканированием изображения (рпс. 8.1,6) по столбцам. Дальнейший Рис.
8.1. Исходный образ (а), горизонтальная составляющая градиента (б), вертикальная составляющая градиента (в) и результат соединения точек контура (е). Предоставлено фирмой Рсгсерг)сз. процесс состоял в соединении сегментов контура, разделенных небольшимп промежутками, и в объединегггггг отдельных коротких сегментов. Глобальный анализ с помощью преобразования Хоуга. Рассмотрим метод соединения граничных точек путем определения их расположения на кривой специального вида. Первоначально предполагая, что на плоскости ху образа дано и точек, тре- буется найти подпоследовательностн точек, лежащих на прямых линиях. Одно из возможных решений состоит в построении всех линий, проходящих через каждую пару точек, а затем в нахождении всех подпослсдовательностей точек, близких к определенным линиям. Задача, связанная с этой процедурой, заключается в нахождении п(п — 1)/2 — па линий и затем в осуществлении п(п(гг — 1)) /2 — пз сравнений каждой точки со всеми лпниямн.
Этот процесс трудоемок с вычислительной точки зрения за исключением самых простых приложений. Данную задачу можно решить по-другому, применяя подход, предло>кенныйт Хоугом и называемый преобразованием Хоуга 1127), Рассмотрим точку (хь у,) н об)цсе уравнение прямой линии у, = ах, + Ь. Имеется бесконечное число линий, проходящих а Ю Рнс. 8.2 Г).тоскость ху (о] н пространство параметров (б), через точку (хо у,), но все онн удовлетворяют уравнению у, = = ах + Ь при различных значениях а и Ь.
Однако, если мы запишем это уравнение в виде Ь = — х,а+ у; и рассмотрим плоскость аЬ (пространство параметров), тогда мы жлеем уравнение одной линии для фиксированной пары чисел (хо у,). Более того, вторая точка (хн у,.) также имеет в пространстве параметров связанную с ней линию, которая пересекает другую линию, связанную с точкой (хо у,) в точке (а', Ь'), где значения а' и Ь' — параметры линии, на которой расположены точки (хо у;) и (хь у,) в плоскости ху. Факт>>чески все точки, расположенные на этой линии, в пространстве параметров будут иметь линни пересечения в точке (а', Ь') (рис. 8.2).
Вычислительная привлекательность преобразования Хоуга заключается в разделении пространства параметров на так называемые собирающие элементы (рцс. 8.3), где (аи кс, анин) и (Ьн.„, Ь„в,) — допустимые величины параметров линий. Собирающий элемент Л(й 1) соответствует плошади, связанной с координатами пространства параметров (ао Ь;). Вначале эти эле- 399 Ь ик амик менты считаются равными нулю.
Тогда для каждой точки (хь, уь) в плоскости образа мы полагаем параметр а равным каждому из допустимых значений на оси а и вычисляем соответствующее Ь, используя уравнение Ь = — х,а+ у,. Полученное значение Ь затем округляется до ближайшего допустимого значения на оси Ь. Если выбор а, приводит к вы шслению Ь„мы полагаем А(р, а) =А(р, а) +1. После завершения этой процедуры значение М в элементе А(й 1) соответствует М точкам в плоскости хч. лежащим на линии у =а,х+ Ьг Точность расположения этих точек на одной прямой зависит от числа разбиений плоскости аЬ.
Отметим, что, если мы разбиваем ось а на К частей, тогда для каждой точки (хмуи) мы получаем К зна. пений Ь, соответствующих К возможным значениям а. Поскольку имеется п точек образа, процесс состоит из пК вычислительных операций. Поэтому приведенная выше процедура,тинейна алики " относительно и и имеет меньшее Рис 8З Разбиение п ое ЧПСЛО ВЫЧИСЛИТЕЛЬНЫХ ОПЕРараметров на элементы е целью ие- ций, чем прпцедура, описанная пользования преобразования хоу- выше, если К ~ ~и.
Проблема, связанная с пред- ставлением прямой линии уравнением у = ах + Ь, состоит в том, что оба параметра а и Ь стремятся к бесконечности, если линия принимает вертикальное положение. Для устранения этой трудности используется нормальное представление прямой линии в виде х сов 0 + у э(п О = О. (8.2-4) Смысит параметров уравнения (8.2-4) ясен пз рис. 8.4, а. Это представление для построения таблицы собирающих элементов используется так же, как метод, изложенный выше, но вместо прямых линий мы имеем синусоидальиые кривые в плоскости Ор. Как и прежде, М точек, лежащих на прямой х сов О, + + уэ1п О, = р,, соответствуют М синусоидальным кривым, которые пересекаются в точке (О., р;) пространства параметров, Если используется метод возрастания 0 н нахождения для него соответствующего О, процедура дает М точек в собирающий элемент А(~',1), связанный с точкой (О„р,).
Разбиение пространства параметров приведено на рис. 8.4,б. Пример. Использование преобразования Хоуга, основанного на уравнении (8.2-4), проиллюстрировано на рис, 8,5. На рис. 8.5,в уровень яркости в плоскости Ор пропорционален числу 400 точек в собирающих элементах. На этом рисунке абсцисса соответствует 0 и ордината р в диапазонах ~90' и ~рмь„, соответственно. В данном случае величина р„„, равна расстоянию от одного угла до другого в исходном образе. Центру рнс. 8.5,в соответствуют 0 = 0' и р = О.
Интересно отметить, что яркие пятна (большое число точек в собирающем элементе) около 0' соответствуют вертикальным линиям и около ~90' соответствуют горизонтальным линиям рис, 8.5, б. На рпс. 8.5,г показаны линии, которые определены этим методом и накладываются на исходный образ. Различие обусловлено ошибкой дискретизации О и р в пространстве параметров. Р Рамии ипитик . ик кики в Ви а б Рнт, 8.4. Нормальное представление линни (а) и разбиение плоскости 0р на элементы (б).
Хотя наше внимание было сосредоточено только на прямых линиях, преобразование Хоуга применимо к любой функции вида д(х, с) =О, где х — вектор координат, а с — вектор коэффициентов. Например, геометрическое место точек, лежащих на окружности (8.2-5) (х — с,)'+ (у — св)' = сз легко может быть определено с помощью подхода, изложенного выше. Основное отличие заключается в том, что теперь мы име. ем три параметра сь с, и сз, которые образуют в трехмерном параметрическом пространстве ячейки в форме кубов н собирающие элементы вида А(й 1, я). Процедура состоит в задании приращений с~ и с,, решении уравнения (8.2-5) относительно с, и в изменении собирающего элемента, соответствующего ячейке, связанной с тройкой (сь сз, са), Очевидно, что сложность преобразования Хоуга существенно зависит от числа координат и коэффициентов в данном функциональном представлении.
В заключение отметим, что определение кривых, не имеющих простого аналитического представления, возможно па основе 40) 0 ° (7) ("( Р) ] ° (5) е Ла а й! Рл ю) с = ~' с(л; „л;). (=3 (8.2-6) дальнейшего обобщения преобразования Хоуга. Более подробно этот вопрос рассмотрен в работе [10]. Гл б обальный анализ с помощью методов теории графов. Из. ложенныс вылив методы основаны па задании послсдователь- Рнс. 85. Об брав детали (а), градиентный образ (б), гра(рик преобразовании Хоуга (в) н обнаруженные линна, наложенные иа исходный образ (г), (]]редоставлено Р.
Оа(е из фнриы Тсхая ]пя]пппеп(я.) ности точек контура, полученных в результате градиентного преобразования. Этот метод редко применяется для предварительной обработки данных в ситуациях, характеризуемых высоким уровнем шума, вследствие того, что градиент является производной и усиливает колебания интенсивности. Рассмотрим глот а бальный подход, основанный на представлении се~ментов онк ура в виде графа и поиске на графе пути наименьшей стоимо- аов сти, который соответствует значимым контурам. Этот подход представляет приближенный метод, эффективный при наличии шума. Как и следует ожидать, эта процедура значительно сложнее и требует больше времени обработки, чем методы, изложенные выше, Сначала дадим несколько простых определений. Граф сг = = ((т', А) представляет собой конечное, пепустое множество вершин М вместе с множеством А неупорядоченных пар различных элементов из М, Каждая пара из А называется дугой.
Рпс. 8.6. Элемент контура, располо- Рис. 8д. Образ разя(ерностью 3 Х 3. женный пежду пикселаып р и д Граф, в котором дуги являются направленными, называется направленных! графом, Если дуга выходит из вершины и; к вершине пн тогда и, называется преемником вершины по В этом случае вершина и, называется пред(иесгвенникон вершины ль Процесс идентификации преемников каждой вершины называется расширением этой вершины. В каждом графе определяются уровни таким образом, чтобы пулевой уровень состоял из единственной вершины, называемой начальной, а последний уровень — из вершин, называемых целевыми.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
