18.3. ОПИСАНИЕ ЛИНИЙ

Прямолинейные и криволинейные отрезки образуют основную структуру многих изображений. Для таких изображений математические соотношения между выделенными точками на границе объекта дают символическое описание изображения. В настоящем разделе описываются два подхода к установлению математических соотношений: подбор кривых и преобразование линии в точку.

18.3.1. АППРОКСИМАЦИЯ КРИВЫХ

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

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

абсолютная ошибка

,                    (18.3.1а)

квадратическая ошибка

,              (18.3.1б)

максимальная ошибка

.                                (18.3.1в)

Рис. 18.3.1. Точки, взятые на границе объекта: а - точки объекта: б - точки, находящиеся в функциональной связи.

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

Среди наиболее часто используемых способов аппроксимации кривых для функционально связанных экспериментальных точек следует указать кусочно-полиномиальную аппроксимацию. В этом случае аппроксимирующая функция имеет вид

,                           (18.3.2)

где  - коэффициенты полинома. Подстановка экспериментальных точек в выражение (18.3.2) приводит к соотношению в векторной форме

,          (18.3.3а)

которое можно записать в компактном виде

.                                                             (18.3.3б)

Для ошибки по критерию наименьших квадратов

                               (18.3.4)

оптимальный набор коэффициентов полинома получается из уравнения

.                                                         (18.3.5)

При , т. е. когда число экспериментальных точек превышает число коэффициентов полинома, псевдообратная матрица вычисляется по формуле

                                    (18.3.6)

при условии, что все экспериментальные точки  различны. В случае линейной аппроксимации требуется определить лишь коэффициенты  и . В противоположном крайнем случае, когда функция  представляет собой полином -го порядка, имеет место равенства  и уравнение (18.3.3) справедливо для каждой экспериментальной точки, т. е. аппроксимирующий полином проходит через каждую экспериментальную точку. В этом случае интерполирующий полином единственный, но его можно представить и подсчитать различным образом, например по формулам интерполяции Лагранжа, Ньютона, Эйткена [16].

В работе Дуда и Харта [11] отдается должное Форсену как родоначальнику простого метода кусочно-линейной аппроксимации, названного итеративным подбором концевых точек. На первом этапе работы алгоритма, которая иллюстрируется рис. 18.3.2, концевые экспериментальные точки  и  соединяются прямой линией. Затем исследуется точка с наибольшим отклонением от этой прямой (точка ). Если отклонение достаточно велико, то эта точка берется в качестве точки соединения двух отрезков ( и ). Данная процедура повторяется для каждого отрезка до тех пор, пока экспериментальные точки не будут «хорошо» аппроксимированы отрезками прямых. Основное преимущество этого алгоритма состоит в его простоте, а недостаток - в возникновении ошибок, обусловленных ошибками в исходных экспериментальных данных. Реймер [17] использовал способ, подобный процедуре итеративного подбора концевых точек, для полигональной аппроксимации замкнутых кривых произвольной формы. Павлидис и Хоровиц [18] разработали алгоритм для полигональной аппроксимации кривых.

Рис. 18.3.2. Итеративный подбор концевых точек: а - первый этап; б - второй этап; в - третий этап.