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

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

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

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

Будем в начале работать в системе координат, связанной с точкой пересечения главных осей эллипса. Тогда уравнение эллипса принимает вид:

x=a cos

y=b sin,

где (x,y) – координата точки на эллипсе; a,b – полуоси эллипса;  - угол наклона эллипса относительно осей координат изображений.

Отсюда ориентация нормали описывается условиями

dx/d =-a sin

dy/d = b cos,

и следовательно

dy/dx = a/b ctg.

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

tg 0=(a/b) tg

Поскольку =0- , где tg=y/x=(b/a)tg и tg=tg(0-) / (1+tg0tg), имеем:

tg=sin2(a²-b²)/2ab

² =a²cos²+b² sin²,

откуда следует

⁴-²(a²+b²)+a²b² sec² =0

Для получения функции отклика в голосующей точке границы, поместим теперь в нее начало координат. Обозначим новые координаты через U и V. Получим:

V²=(a²+b²)-U²-a²b²/U².

К сожалению, эта кривая не симметрична относительно начала координат. В случае эллипса с малым эксцентриситетом, она аппраксимируется эллипсом. В случае очень большого эксцентриситета, она аппроксимируется дугами двух кругов:

=a и =a²/b.

Однако, в общем случае, эта кривая всегда будет не симметрична.

Введем два новых параметра:

c=(a+b)/2;

d=(a-b)/2.

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

(U+c+d²/(2c)) ²/d² +V² /(4d² )=1.

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

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

Вычислительная сложность этого алгоритма имеет оценку L_a 6² pcd, где p-число эллипсов, присутствующих на изображении размером N*N пиксел, c и d - параметры эллипсов.