Просмотр исходного текста страницы Различные способы параметризации прямых


Как уже отмечалось, практические вычислительные методы, основанные на
преобразовании Хафа, работают не в непрерывном пространстве параметров, а на
ячейках аккумулятора. Однако и изображения в цифровых системах определены на
дискретной прямоугольной сетке, которая, очевидно, допускает лишь некоторую
соответствующую дискретную параметризацию семейства прямых. Такая
естественная параметризация прямых для дискретных массивов и связанное с ней
преобразование Хафа предложены в статье.

Рассмотрим естественное множество прямых линий, порождаемое целочисленной
решеткой $N\times N$ точек, содержащей $N^{2}$ элементов. Считая, что любые
две различные точки решетки определяют прямую, мы увидим, что размер этого
множества составит $N^{2} (N^{2}-1)$, т. е. $O(N^{4})$ линий. Однако многие
линии будут определены несколько раз своими различными отрезками, если на
них лежит более двух точек исходной решетки. Таким образом, представление
натурального множества прямых в виде четырехпараметрического массива
$[(x_{1},y_{1}),(x_{2},y_{2})]$ концевых точек размерности $O[N^{4}]$
является явно избыточным.

Естественное множество прямых порождает также и естественное множество
углов ($\theta _{a})$, которое можно описать как $\textrm{tg} \theta _{a}=i/j$,
где $\{i,j\}\in\{0,1,{\ldots} ,N-1\}$.

Учитывая симметрию, $0 < \rm tg   \theta _{ a} \le 1$, причем эти углы
повторяются во всех четырех квадрантах:

$$
\textrm{tg}   \theta  =[\textrm{tg}  (90&deg; -\theta )]^{-1}=-[\textrm{tg} (90&deg;+\theta )]^{-1}=-[\rm   \textrm{tg} (180&deg; -\theta )].
$$

Все возможные углы $0 \le   \theta _{a}  \le 1$ могут быть получены
геометрически с использованием $N(N-1)/2$ линий, так что число уникальных
углов $N_{a}$ должно быть $2N(N-1)$ (в четырех квадрантах). Однако и здесь мы
увидим избыточность; некоторые отношения $i/j$ являются кратными (например,
$3/12=2/8=1/4$). Вероятность того, что два целых числа соотносятся заданным
образом, равна $6/\pi ^{2}$. Это означает, что размер неизбыточного
множества углов на решетке равен

$$
N_{a}=(6/\pi ^{2})2N(N-1)=1{,}216 N (N-1).
$$

Аналогично, для множества прямых

$$
N_{L}\cong 0{,}23N^{2}(N^{2}-1).
$$

Перейдем к параметризации преобразования Хафа. Хотелось бы ввести такие
параметры, которые бы не только обеспечивали вычислительные выгоды, но и
имели бы простую и интуитивно понятную интерпретацию. Кроме того, существует
проблема "запрещенных областей", т. е. таких областей решетки параметров,
которые никогда не будут заполнены при "голосовании" точек исходного
пространства. В традиционном ($\rho  , \theta )$-пространстве такие области
занимают до $10${\%} общей площади для изображений на квадратных дискретных
решетках $N\times N$. Эта память неизбежно пропадает при программной реализации.
Кроме того, тратится лишнее время на опрос этих заведомо пустых областей при
определении пиков аккумуляторной функции. Еще одним важным соображением при
выборе параметров является конечность их значений. Например, параметр $k$ в
уравнении $Y=kX+b$, как известно, является неограниченным (при $\theta =90&deg; $, $k=+\infty )$. Исходя из выше изложенного, можно предложить следующие
варианты параметризации.

==Точки периметра($m,n$).==

Будем описывать прямые парой концевых точек, лежащих на периметре решетки
$N\times N$. Очевидно, это составляет $4N$ точек или ( с учетом симметрии)
1$/2(4N\times 4N)=8N^{2}$ линий. Так как четверть из этих точек лежит на одной
прямой ( стороне квадрата), окончательный размер массива параметров составит
$6N^{2}$. Это лишь небольшое подмножество натурального множества с $0$
$[N^{4}$] элементов.

Преимуществом параметризации $(m,n)$ является то, что будучи примененной в
случае изображения, разбитого на области меньшего размера, она позволяет
легко соединять линии, проходящие через несколько таких областей, так как
они смыкаются по периметру. Недостаток заключается в том, что информация об
угловом положении прямых не содержится здесь в явном виде.

==Точка периметра и угол $(a,n)$.==

Здесь мы используем одну точку пересечения данной пряиой с периметром
$n$ $(0 \leqslant \vert n\vert < N)$ и угол, определяемый прямой, проходящей
через центр решетки и точку периметра $a$ $(-N+1 \leqslant a \leqslant N-1)$. Массив
аккумулятора содержит здесь, очевидно, $4N^{2}$ элементов. Эта
параметризация не создает "запрещенных областей". Многие свойства
пространства $(a,n)$ можно рассмотреть на примере описываемого ниже
пространства $(a,d)$.

==Наклон и смещение ($a,d)$.==

Эта параметризация содержит параметр $a$, т. е. угол, определяемый направлением
из центра к некоторой точке на периметре квадратной решетки, однако
смещение линии по вертикали или горизонтали из центра теперь фиксируется при
помощи расстояния $d$ из центра до пересечения прямой с осью $y$ или $x$. Эта
параметризация на решетке $N\times N$ порождает $3N^{2}$ или $4N^{2}$ элементов
аккумулятора. Легко увидеть, что $(a,d)$-параметризация тесно и
непосредственно связана с ($\rho , \theta )$-параметризацией и наиболее
естественна поэтому для использования в преобразовании Хафа.

Также связана она и с параметрами уравнения $y=ax+b$, где $a$ интерпретируется
не как угол, а как наклон прямой. Для линий с наклоном меньше $45&deg;$ $d$
отсчитывается от центра до пересечения прямой с вертикальной осью y, а для
наклона больше $45&deg;$ $d$ измеряется вдоль горизонтальной оси $x$. Чтобы
сохранить непрерывность отображения необходимо также поменять знак $d$ для
углов $45&deg; <\theta _{ a} \le 90&deg;$.

Отображение $(x,y)$ на $(a,d)$:
$$
d =y - (2ax)(N-1) \mbox{ для } 0 \le \vert a \vert \le  \frac{N-1}{2} ,
$$
$$
d = -\left[ {x-2y+ \frac{2ay}{N-1}}\right] \mbox{ для } \frac{N-1}{2} < a \le N-1 ,
$$
$$
d = \left[{x + \rho y+  \frac{\small\rho\normalsize ay} {N-1}}\right]  \mbox{ для } -N+1 \le a < -\frac{N-1}{2}.
$$
позволяет определить преобразование Хафа с параметрами $(a,d)$.

==Основание нормали.==

Рассмотрим еще один известный способ параметризации прямых, называемый
"снование нормали" (foot-of-normal). Суть этого метода заключается в
следующем. Пусть используется традиционная параметризация ($\rho , \theta
)$ для обнаружения прямых в нормальных координатах. Тогда для вычисления
образа любой точки $(x,y)$ в пространстве ($\rho , \theta )$ необходимо
вычисление арктангенса, чрезвычайно дорогое в плане трудоемкости. Метод
"основания нормали" этого не требует. В этом методе прямая характеризуется
координатами $(x_{0} , y_{0})$ точки основания нормали (перпендикуляра),
опущеной на эту прямую из начала координат или другой выбраной опорной
точки.

Дэвисом было предложено следующее остроумное использование этой
параметризации. Применим к исходному изображению в плоскости $(x,y)$
дифференциальный градиентный оператор Собела для получения в каждой
интересующей нас контурной точке компонент локального градиента
$(g_{x} , g_{y})$. Определим теперь точку $(x_{0} , y_{0})$ как "основание
нормали" прямой $(\rho , \theta )$, проходящей через голосующую точку
$(x,y)$. Тогда справедливы соотношения
$$
\frac {g_{y}}{g_{x}}= \frac {y_{_0}}{x_{_0}},
$$
$$
(x-x_{0})x_{0}+(y-y_{0})y_{0}=0.
$$
Разрешив их относительно $x_{0}$ и $y_{0}$, получим
$$
x_{0}=Vg_{x}, $$ $$y_{0}=Vg_{y},
$$
где $V=(xg_{x} +yg_{y} )/(g^{2}_{x} +g^{2}_{y})$.

Заметим, что эта параметризация требует нескольких умножений, сложений и
лишь одного деления. Интерпретация обратного преобразования (для вычисления
точек, принадлежащих прямой) имеет вид
$$
x = x_{0} +Wg_{y},
$$
$$y = y_{0} -Wg_{x},
$$
где $W=(xg_{y}-yg_{x})/(g^{2}_{x} +g^{2}_{y})$.

Проанализируем возможные ошибки этого метода. Пусть вследствие угловой
ошибки $\epsilon$ в направлении определяемой прямой мы получили значение
($x_{1},y_{1})$ вместо ($x_{0},y_{0})$ для основания нормали. Первое
приближение ошибки дает оценку
$$\delta \rho =\epsilon S,$$ $$\delta S=-\epsilon \rho ,$$
где $S = \sqrt { (x_0-x_1^{2}) +(y_0-y_1^{2})}$.

Как видно, ошибка при одном и том же $\epsilon$ тем больше, чем дальше точка
$(x_{0}, y_{0})$ от начала координат. Так, при помещении начала координат $O$
в центр квадратного изображения размера $N\times N$ пикселов верхняя
граница ошибки составляет $\delta \rho    \epsilon N/\sqrt 2$.

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

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

Вторая проблема связана с падением точности определения направления прямой в
методе "основания нормали" вблизи значения $(x_{0}, y_{0})=(0,0)$. В самом
деле, при нахождении $(x_{0},y_{0})$ в начале координат основание нормали
перестает определять однозначно какую-либо прямую, а определяет все
семейство прямых, проходящих через начало координат. Чаще всего этим
эффектом можно пренебречь, однако в каждом конкретном случае об этом
необходимо помнить и анализировать вероятность ошибок. Корректным способом
решения этой проблемы является перенесение начала координат для точек
$(x_{0},y _{0})$ с малым $\rho $ в какую-либо другую, заранее определенную
точку. Однако это связано с усложнением вычислений.

==Полезные ссылки==

#[[#top| &#9757; К началу ]]
#[[Преобразование Хафа, его обобщения и модификации|&#9756; Преобразование Хафа, его обобщения и модификации]]