Специализированная процедура голосования для поиска эллипсов

Материал из Техническое зрение
Перейти к: навигация, поиск

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

Дэвисом предложена методика решения этой проблемы для случая поиска эллипсов. Эллипс - анизотропная (ориентированная) фигура, и, казалось бы, поиск $n$ возможных ориентаций эллипса требует $n$ листов (слоев, плоскостей) пространства параметров по координате ориентации. Однако можно обойтись одним листом для накопления голосов в пользу всех возможных ориентаций.

Рассмотрим форму функции отклика, которую в пространстве параметров порождает каждая точка границы эллипса, если ориентация его произвольна и неизвестна.

Будем вначале работать в системе координат, связанной с точкой пересечения главных осей эллипса. Тогда уравнение эллипса принимает вид $$ \begin{gather*} x=a \cos \psi, \\ y=b \sin \psi , \end{gather*} $$ где $(x,y)$ - координата точки на эллипсе; $a,b$ - полуоси эллипса; $\psi $ - угол наклона эллипса относительно осей координат изображений.

Отсюда ориентация нормали описывается условиями $$ \frac {dx} {d\psi} =-a \sin \psi, $$ $$ \frac {dy} {d\psi} = b \cos \psi , $$ и, следовательно,

$$ \frac {dy}{dx} = \frac {a}{b} \textrm{ctg} \psi . $$

Таким образом, ориентация нормали к эллипсу в данной точке имеет вид

$$ \textrm{tg} 0= {\frac {a}{b}} \textrm{tg} \psi. $$

Поскольку $\psi =0-\eta $, где $\textrm{tg} \eta =y/x=(b/a) \textrm{tg} \psi $ и $\textrm{tg} \psi = \textrm{tg} (0-\eta ) / (1+ \textrm{tg} 0 \textrm{tg} \eta )$, имеем $$ \textrm{tg} \psi = \sin 2 \psi \frac{a^{2}-b^{2}}{2ab} $$ $$ \nu ^{2 }=a^{2}\cos^{2}\psi +b^{2} \sin ^{2}\psi , $$ откуда следует $$ \nu ^{4}-\nu ^{2}(a^{2}+b^{2})+a^{2}b^{2} \textrm{sec}^{2} \psi =0. $$ Для получения функции отклика в голосующей точке границы поместим теперь в нее начало координат. Обозначим новые координаты через $U$ и $V$. Получим

$$ V^{2}=(a^{2}+b^{2})-U^{2}- \frac{a^{2}b^{2}}{U^{2}}. $$ К сожалению, эта кривая не симметрична относительно начала координат. В случае эллипса с малым эксцентриситетом она аппроксимируется эллипсом. В случае очень большого эксцентриситета она аппроксимируется дугами двух кругов $$\nu =a \quad \mbox {и} \quad \nu =\frac{a^{2}}{b} .$$ Однако, в общем случае, эта кривая всегда будет несимметрична. Введем два новых параметра $$ c=\frac{a+b}{2} , \qquad d=\frac{a-b}{2} . $$

Теперь для малых $d$ наше выражение примет вид

$$ \frac{\left( {U+c+ \frac{d^{2}}{2c}}\right)^{ 2}}{d^{2}} + \frac{V^{2}}{4d^{2}}=1. $$

Пренебрегая членом $d^{2}/2c$, который мало влияет на $U$, мы увидим, что это уравнение эллипса с полуосями $2d$ и $d$ соответственно. Это сильно упрощает вычисления, но справедливо только для эллипсов, для которых $d \le 0,1c$ (т. е. $a \le 1,2b$). Однако если эллипсы невелики, можно потребовать только $a<2b$.

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

Вычислительная сложность этого алгоритма имеет оценку $L_{a} \cong 6\pi ^{2} pcd$, где $p$ - число эллипсов, присутствующих на изображении размером $N\times N$ пикселов, $c$ и $d$ - параметры эллипсов.

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

  1. ☝ К началу
  2. ☜ Преобразование Хафа, его обобщения и модификации
Личные инструменты
Пространства имён

Варианты
Действия
Навигация
Инструменты