Дуда Р., Харт П. - Распознование образов и анализ сцен (1033979), страница 71
Текст из файла (страница 71)
Часто удается минимизировать такой критерий методом поиска, при условии, конечно, что для поиска можно легко найти хорошую начальную точку. Пред- т) Один иа таких критериев устанавливает нулевой штраф, если точка находится иа расстоянии меньше е от аппроксимирующей линии, и единичный штраф — в противном случае. 9.2.
Описаны линии положим в качестве примера, что мы аппроксимируем множество точек посредством простого соединения крайней левой и крайней правой точек множества. Для дискретного Изображения мы можем попробовать перемещать эти концевые точки в пределах небольшой области окрестных элементов с тем, чтобы минимизировать наш критерий. Такие перемещения можно выполнять путем перебора или с помощью какого-либо алгоритма поиска экстремума. Таким образом, основная стратегия минимизации некоторого критерия наилучшего приближения может использоваться даже в том случае, когда аналитическое решение невозможно.
9.2,3. ПОДБОР ЛИНИЙ ПОСРЕДСТВОМ КЛАСТЕРНОГО АНАЛИЗА Ранее мы полагали, что все точки объекта должны аппроксимироваться единственной линией. Обратим теперь наше внимание к более общей задаче описания объекта посредством совокупности линий. А именно это означает, что мы должны уметь разделять объект на такие подмножества, что каждое из них может быть хорошо представлено единственной линией. Существует много методов для выполнения этой операции, В следующих пунктах описываются два метода, основанные на кластерном анализе.
Идея, лежащая в основе каждого из них, заключается в том, чтобы перевести исходный объект в новое пространство, в котором коллинеарные подмножества объекта образуют группы или кластеры. Эти кластеры затем могут быть найдены, например, с помощью методов кластерного анализа, подобных описанным в гл. 6. 9.2.3.1. Преобразование точек в кривые Предположим, как обычно, что иам дано множество из и точек объекта ((хь у;)), 1=1,..., и, которое мы хотим аппроксимировать некоторым еще нуждающимся в определении числом прямых линий. Один класс методов связан с переводом каждой точки (хь у,) в некоторую кривую в новом пространстве параиетров таким образом, чтобы коллинеарные точки превращались в пересекающиеся кривые. Если несколько кривых пересекаются, их общая точка определяет в некоторой системе параметров уравнение прямой линии на плоскости (Х,У), содержащей коллинеарные точки.
Конкретный пример методов этого класса будет задан, если мы введем систему параметров для семейства прямых линий. По некоторым причинам, объясняемым ниже, мы выберем так называемую нормальную систему параиетров прямой линии. Как показано на рис. 9.5, такая система параметров задает прямую линию углом наклона В ее нормали и ее расстоянием р от начала координат. Нетрудно убедиться, что уравнение прямой линии при таком пред- Гя.
9. Описания линии и форин ставлении выглядит следующим образом: х О+у з1п О=р, В соответствии с этим мы переводим каждую точку (хь у,) в кривую на плоскости (О, р), определяемую уравнением р=-х;соз О+урби О. Заметим, что это преобразование сводится всего лишь к тому, что мы иначе интерпретируем те же величины: мы считаем величины (хь у;) фиксированными, а У величины (О, р) — переменными.
Если у нас есть несколькоточек (хьу;) на плоскости (Х, У), лежащих на прямой х соз О,+у з(п О, = =р„то соответствующие им кривые на плоскости (6, р) должны проходить через точку (О„р,). Выражаясь формальным языком, для нашего преобразования образ точки (х;, у,) есть кривая О р=х;соз О+у, з|п 6, х или, поскольку точка (х„у;) Ряс. 9.5. Нормальная система параметров лежит на линии, опрепрямой ляпая. деляемой параметрами (О ра) р =х; соз О+ ~~' "." ' '1 з|п О. мпе, Но последнее равенство справедливо при 6=6, и р=р„поэтому образы всех коллинеарных точек (хь у;) проходят через точку (О, р). В принципе описанный метод решает проблему аппроксимации множества заданных точек набором прямых линий.
На практике, однако, возникают две трудности. Во-первых, если мы начинаем обработку и точек, то должны решить приблизительно иа/2 уравнений, чтобы найти все пересечения. Во-вторых, можно предвидеть заранее, что из-за шумов точки подмножеств будут коллинеарны лишь с некоторым приближением, и, следовательно, их образы будут пересекаться в одной точке лишь приближенно, Можно уменьшить обе эти трудности, если квантовать параметры О и р и провести обработку с помощью двумерного массива счетчиков на плоскости (О, р). Для каждой точки исходного объекта соответствующая (кван- 9.2.
Оиисание линии тованная) кривая заносится в массив посредством увеличения содержимого счетчиков в каждой клетке вдоль кривой. Коллинеарные точки создадут в результате большие числа в некоторых счетчиках. Приближенно коллинеарные точки сбздадут моды в двумерной гистограмме, отображаемой массивом. Заметим, кстати, что нам нужно рассматривать значения 8 только от О до 2н, а значения р от О до величины максимального диаметра сетчатки. Более того, метод изотропен в том смысле, что он не чувствителен к ориентации координатных осей.
Эти качества представляют собой важное свойство нормальной системы параметров прямой линии, и они делают такую систему более удобной, чем, скажем, известный способ представления прямой через наклон и точку пересечения с осью координат. Другие сведения о нормальной форме прямой линии мы получим позже, когда будем обсуждать интегральные геометрические методы. 9.2.3.2. Кластерный анализ сегментов Мы расширим временно основные правила подбора линий с тем, чтобы включить задачу подбора линий для совокупности коротких (как правило) прямых сегментов.
Довод в пользу такой постановки заключается в том, что иногда изображение преобразуется в набор коротких прямых сегментов посредством операции сравнения с эталоном. В таком случае следующий очевидный шаг может состоять в аппроксимации коллинеарных сегментов прямыми линиями. Ключ к тому, как это можно было бы сделать, дает специальный способ представления сегментов, показанный на рис. 9.5. Мы будем представлять данный сегмент в координатах (8, р), где р — длина вектора, проведенного из начала координат по нормали к прямой, содержащей сегмент, а 8 — угол наклона этой нормали относительно оси Х.
Мы сразу же видим, что такой способ представления сегментов неоднозначен. В самом деле, все коллинеарные сегменты дадут одни и те же координаты (8, р). Это наводит на мысль, что почти коллинеарные сегменты могут быть найдены посредством представления каждого из них в виде точки на плоскости (8,р) и выделения кластеров для этих точек. Один из недостатков этого метода состоит в том, что он также чувствителен к выбору координатных осей на плоскости изображения. Если сегмент расположен далеко от начала координат, небольшая ошибка в определении его ориентации приводит к большой ошибке в определении его координаты р.
9.2.4. СЕГМЕНТАЦИЯ ЛИНИИ В некоторых случаях задача разбиения объекта на подмножества может рассматриваться как задача сегментации. Мы, например, имеем основания ожидать, что точки объекта скорее лежат на ка- Гл. р. Описания линии и форма ких-то (возможно, сложных) кривых, чем на случайно расположенных линейных сегментах, В таких случаях естественно поискать методы для разбиения совокупности точек объекта, т. е.
кривой, на некоторое число последовательных линейных сегментов, таких, что каждый из них может быть хорошо аппроксимирован отрезком прямой. В следующих пунктах описываются два весьма простых метода осуществления этой операции. 9.2.4.1. Итеративный подбор концевых точек В своей простейшей форме метод итеративного подбора концевых точек заключается в следующем. Нам дано, как обычно, множество из и точек, и мы проводим первую линию, например линию АВ, соединяя просто концевые точки множества '). Вычисляются рас- О ° ем, м ° мм ° м е мм .у В В Рнс.
9.6. Итеративный подбор концевых точек. стояния от каждой точки до этой линии, и, если все они меньше некоторого установленного заранее порога, процесс закончен. Если это не так, мы находим точку, наиболее удаленную от АВ, например точку С, и заменяем первоначальную линию двумя новыми линиями АС и СВ. Этот процесс затем повторяется отдельно для двух новых линий, возможно, с различными порогами. Рис. 9.6 иллюстрирует этот метод. Исходная линия АВ разбивается на АС и СВ, а затем линия СВ разбивается на С0 и 0В. Конечным результатом является последовательность связанных сегментов АС, С0 и 0В.
Метод имеет два недостатка, причем оба они сводятся к тому, что на результат сильно влияют отдельные точки. Первый, менее существенный недостаток заключается в том, что сегмент, выбираемый в конечном итоге, может оказаться не самой лучшей аппроксимацией точек, находящихся в его непосредственном окружении.
С этим можно бороться с помощью процесса вторичного подбора, в х) Концевыми тачками могут быть крайняя левая и крайняя правая точки множества, крайняя верхняя и крайняя нижняя илн другие уары рааличакнцнхся точек. 9.9. Описание линии котором для уточнения позиций сегментов линии используется более изощренный алгоритм. Другими словами, итеративный алгоритм можно применять для приближенного подбора и приближенного определения точек излома, а затем улучшать аппроксимацию во время второго прохода.
Более серьезный недостаток итеративного процесса заключается в том, что единственная «дикая» точка может резко изменить конечный результат. Хотя с этим также можно бороться, например с помощью процесса предварительного сглаживания, та же самая основная проблема встречается и во многих других алгоритмах обработки изображений. Простота часто достигается ценой принятия решения на основании только локальной информации об изображении.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
