9.2.3.1.    Преобразование точек в кривые

Предположим, как обычно, что нам дано множество из п точек объекта {(xit Уі)}, і=1, . . . , п, которое мы хотим аппроксимировать некоторым еще нуждающимся в определении числом прямых линий. Один класс методов связан с переводом каждой точки (xt, yt) в некоторую кривую в новом пространстве параметров таким образом, чтобы коллинеарные точки превращались в пересекающиеся кривые. Если несколько кривых пересекаются, их общая точка определяет в некоторой системе параметров уравнение прямой линии на плоскости (X,Y), содержащей коллинеарные точки.

Конкретный пример методов этого класса будет задан, если мы введем систему параметров для семейства прямых линий. По некоторым причинам, объясняемым ниже, мы выберем так называемую нормальную систему параметров прямой линии. Как показано на рис. 9.5, такая система параметров задает прямую линию углом наклона Ѳ ее нормали и ее расстоянием р от начала координат. Нетрудно убедиться, что уравнение прямой линии при таком пред

ставлении выглядит следующим образом;

В соответствии с этим мы переводим каждую точку (хі, уі) в кривую на плоскости (Ѳ, р), определяемую уравнением

Заметим, что это преобразование сводится всего лишь к тому, что мы иначе интерпретируем те же величины: мы считаем величины

(Хі, Уі) фиксированными, а величины (Ѳ, р) — переменными. Если у нас есть нес- колькоточек {хиУі) на плоскости {X, Y), лежащих на прямой X cos Ѳ„+г/ sin Ѳо = =Ро, то соответствующие им кривые на плоскости (Ѳ, р) должны проходить через точку (Ѳо, ро). Выражаясь формальным языком, для нашего преобразования образ точки {Хі, уі) есть кривая

или, поскольку точка (х:і, г/г) лежит на линии, определяемой параметрами

(Ѳо, Ро),

Но последнее равенство справедливо при Ѳ=Ѳо и р=Ро, поэтому образы всех коллинеарных точек (л:,, уд проходят через точку (Ѳо, Ро)-

В принципе описанный метод решает проблему аппроксимации множества заданных точек набором прямых линий. На практике, однако, возникают две трудности. Во-первых, если мы начинаем обработку п точек, то должны решить приблизительно /гѴ2 уравнений, чтобы найти все пересечения. Во-вторых, можно предвидеть заранее, что из-за шумов точки подмножеств будут коллинеарны лишь с некоторым приближением, и, следовательно, их образы будут пересекаться в одной точке лишь приближенно. Можно уменьшить обе эти трудности, если квантовать параметры Ѳ и р и провести обработку с помощью двумерного массива счетчиков на плоскости (Ѳ, р). Для каждой точки исходного объекта соответствующая (кван-

тованная) кривая заносится в массив посредством увеличения содержимого счетчиков в каждой клетке вдоль кривой. Коллинеар- ные точки создадут в результате большие числа в некоторых счетчиках. Приближенно коллинеарные точки создадут моды в двумерной гистограмме, отображаемой массивом. Заметим, кстати, что нам нужно рассматривать значения Ѳ только от 0 до 2я, а значения р от 0 до величины максимального диаметра сетчатки. Более того, метод изотропен в том смысле, что он не чувствителен к ориентации координатных осей. Эти качества представляют собой важное свойство нормальной системы параметров прямой линии, и они делают такую систему более удобной, чем, скажем, известный способ представления прямой через наклон и точку пересечения с осью координат. Другие сведения о нормальной форме прямой линии мы получим позже, когда будем обсуждать интегральные геометрические методы.