Программные продукты и системы

В настоящее время существует тенденция развития систем технического зрения, связанных с измерением и контролем качества изготовляемой продукции. Актуальным является решение проблемы создания быстродействующих программных продуктов, реализующих сложные математические преобразования. В настоящей статье рассмотрено несколько способов реализации алгоритмов интегрального преобразования по линиям, которое используется для анализа образов линий на растровых изображениях. Частным примером такого интегрального преобразования является преобразование Хоха (Hough P.V.C., Method and means for recognizing complex pattern, U.S. Patent 3069654, December 18, 1962), которое до сих пор широко применяется в области обработки изображений.

Зададим линию вида j(x,y,a)=0, где x, y – переменные; a=(a1,a2,…,am) – параметры.

Под интегральным преобразованием по линии j будем понимать преобразование Hj, ставящее в соответствие изображению f(x,y) его спектр параметров по правилу .

В данном преобразовании используется интеграл по кривой (криволинейный интеграл). Из его свойств следует, что спектральная функция h(a) будет возвращать массу (суммарную яркость) части кривой j(x,y,a)=0. Можно сказать, что каждый спектральный отсчет h(a) в точке a дает меру сходства образа кривой на изображении f(x,y) с заданной линией j(x,a)=0.

Полезным является то, что максимум спектральной функции будет соответствовать параметрам образа линии вида j, содержащегося на изображении f(x,y). Это свойство используется для вычисления признаков образа линии.

Рассмотрим возможность алгоритмической реализации преобразования Hj. Легко заметить, что Hj можно записать через двойной интеграл

.

Вследствие такой формализации алгоритмически данное преобразование можно представить как последовательное рассмотрение каждого значения параметров a и каждой точки изображения (x,y), для которых при соблюдении условия j(x,y,a)=0 происходит рекуррентное увеличение значения функции h(a). При этом полагается, что изначально все значения спектральной функции h(a) равны нулю.

Такую рекуррентную реализацию интегрального преобразования по линии

"(x,y) "al (l=1,…,m)½j(x,y; a1,a2,…,am)=0,

h(a1,a2,…,am)=h(a1,a2,…,am)+f(x, y)dxdy,

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

Алгоритм можно построить таким образом, что в вычислении будут участвовать только точки оцениваемых объектов на изображении (то есть f(x,y)>0):

"(x,y)½f(x,y)>0,

"al (l=1,…,m)½j(x,y; a1,a2,…,am)=0,

h(a1,a2,…,am)=h(a1,a2,…,am)+f(x,y)dxdy.

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

Будем называть такой способ построения алгоритма интегрального преобразования (устранение расчетов с координатами точек фона (x,y), когда f(x,y)=0) способом отсечения фона.

Алгоритм также можно сократить на один цикл и избавиться от проверки условия принадлежности точки кривой j, если выразить из уравнения j(x,y,a)=0 какой-либо из параметров. Например, am=j(x,y; a1,a2,…,am-1).

Алгоритм в таком случае приобретает следующий вид:

"(x,y)½f(x,y)>0,

"al (l=1,…,m-1),

h(a1,a2,…,am)=h(a1,a2,…,am)+f(x, y)dxdy

½am=j(x, y; a1,a2,…,am-1).

Назовем такую реализацию способом с разрешением относительно параметра.

Самый лучший способ для получения быстродействующего алгоритма интегрального преобразования по кривой появляется, когда в пространстве параметров линия задана параметрически в виде системы уравнений (уравнения разрешены не относительно переменных, а относительно параметров в этих уравнениях): ai=ji(x,y;t) (i=1,…,m).

Теперь вместо m циклов остается только один с ранжированным параметром t, а значения параметров a1,a2,…,am вычисляются, исходя из значения t:

"(x,y)½f(x,y)>0,

"t h(a1,a2,…,am)=h(a1,a2,…,am)+f(x,y)dxdy

½al=jl(x,y;t) (l=1,…,m).

Этот способ (выражение всех параметров линии через новый введенный параметр) назовем параметрическим разрешением.

Если изображение f(x,y) сильно насыщено образами линий или линия, по которой выполняется интегрирование, имеет малую длину по сравнению с сигнальной областью, то отсечение фона выполнять нецелесообразно. Воспользуемся свойством, на основании которого криволинейный интеграл можно найти с помощью обычного определенного интеграла. Если линия задана параметрически:  то

,

где .

Вначале начнем перебирать не значения переменных, а значения параметров линии:

"al (l=1,…,m) "t

h(a1,a2,…,am)=h(a1,a2,…,am)+

+f(x,y)×n(a1,a2,…,am; t)dxdy

½x=jx(a1,a2,…,am; t), y=jy(a1,a2,…,am; t).

Назовем такое формирование алгоритма способом разрешения относительно переменных.

Пусть теперь известно направление нормали к предполагаемой кривой в каждой точке изображения (например, направление градиента яркости, если рассматривать контуры в качестве анализируемых линий). Обозначим угол направления как F(x,y) (F:R2 ®[0,2p)).

Модифицируем преобразование Hj так, чтобы угол F(x,y) совпадал с углом наклона нормали к кривой j(x,y,a)=0:

,

где  – оператор градиента; ÐÑ(×) – оператор угла наклона вектора градиента. Назовем данное преобразование градиентным интегральным преобразованием по линии j(x,y,a)=0.

Объединив два уравнения в систему

, можно избавиться от одного параметра уравнения кривой j(x,y,a)=0.

Пусть y(x,y;a1,a2,…,am-1)=0 – результат объединения системы.

Выразим параметры из уравнений

y(x,y;a1,a2,…,am-1)=0Û

Ûam-1 =y(x,y;a1,a2,…,am-2);

F(x,y)–Ð(Ñj(x,y,a))=0Û am=m (x,y;a1,a2,…,am-1).

Исходя из данного, алгоритм преобразования запишется следующим образом:

"(x,y)½f(x,y)>0,

"al (l=1,…,m-2),

h(a1,a2,…,am) = h(a1,a2,…,am)+f(x, y)dxdy

½ am-1=y(x,y;a1,a2,…,am-2),

½ am=m (x,y;a1,a2,…,am-1).

Назовем рассмотренный подход способом построения интегрального преобразования с разрешением двух параметров через градиент.

Видно, что учет информации о направлении позволяет устранить из алгоритма еще один цикл, что существенно сокращает объем вычислений.

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

Обобщим теперь понятие интегрального преобразования на случай, когда известно несколько признаков образа линий на изображении f(x,y). Пусть {Bi(x,y)} – множество функций некоторых k (k

Преобразование, ставящее в соответствиеизображению f(x,y) его спектр параметров по правилу

,

назовем производным интегральным преобразованием по кривой j.

В этом случае мы имеем систему k уравнений

{Bi(x,y)–bi(x,y;a1,a2,…,am) =0},

из которой выразим (если это возможно аналитически) k+1 параметров кривой j:

am-k =y1(x,y;a1,a2,…,am-k-1),

am-k+1 =y2(x,y;a1,a2,…,am-k),

…

am=yk+1(x,y;a1,a2,…,am-1).

Алгоритм преобразования сократится на k+1 циклов:

"(x,y)½f(x,y)>0,

"al (l=1,…,m-k-1),

h(a1,a2,…,am)=h(a1,a2,…,am)+f(x, y)dxdy

½ am-i = yk-i+1(x,y;a1,a2,…,am-k-1) (i=k,…,0).

Назовем такой способ построением интегрального преобразования с разрешением параметров через дополнительные признаки.

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