9.2.4.1. Итеративный подбор концевых точек

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

стояния от каждой точки до этой линии, и, если все они меньше некоторого установленного заранее порога, процесс закончен. Если это не так, мы находим точку, наиболее удаленную от АВ, например точку С, и заменяем первоначальную линию двумя новыми линиями АС и СВ. Этот процесс затем повторяется отдельно для двух новых линий, возможно, с различными порогами. Рис. 9.6 иллюстрирует этот метод. Исходная линия А В разбивается на Л С и СВ, а затем линия СВ разбивается на CD и DB. Конечным результатом является последовательность связанных сегментов АС, CD и DB.

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

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