5.4. Вычисление квадратичного критерия близости
В гл. 3 было показано, что классификация участка сигнала Р(х,у), накрытого апертурой, производится на основе результатов вычисления квадра-тичного критерия близости
(516)
п
где к- порядковый номер гистограммы, являющейся эталонной для к- го класса; П - яростный интервал, на котором выполняется анализ значений гис-тограммы.
Как показывает эксперимент, в случае тепловизионных изображений возможна ситуация, когда фон и «цель» описываются не одной парой эталонных гистограмм, а парой множеств гистограмм и Нг>э, где
, /г = {#,7'} для фона и «цели» соот
ветственно. Каждый элемент множеств Нд<э и Нг э представляет собой эталонную гистограмму, которая построена по участку сигнала, относящегося к «цели» или фону.
В этом случае для идентификации состояния регистрируемой сцены не-обходимо выполнить вычисление критериев близости Фk(hp),
к
к = ,э)-1. Для построения гистограммы hp(Pj) выборки сигнала,
к
ограниченной апертурой, которая содержит М(Л) пикселей, необходимо выполнить N(/1) операций сложения. Для вычисления каждого значения критерия близости при использовании гистограмм, имеющих N (О) уровней кванто- вания, требуется выполнить N(0) операций умножения (возведение в квадрат) и A'(/l) + 2-;V(6>) операций сложения (вычисление Л/>(//), разности fy и выполнение суммирования значений по уровням квантования). С учетом общего количества вычисляемых величин Ф к (hp), можно сделать вывод о том, что для идентификации участка сигнала, накрытого апертурой, требуется выполнение опеРа1*ий умножения и
к
М(Л) + 2операций сложения. После сдвига апертуры требу-
к
ется повторное вычисление совокупности из X^(^v) величин Фк(Ьр)* что
к
требует выполнения такого же количества арифметических операций.
Для увеличения эффективности идентификации состояния отдельных элементов изображения в множества НВэ и Ну, добавляются новые элементы.
С добавлением в них новых элементов линейно возрастает объем вычислений, необходимых для вычисления совокупности значений квадратичных критериев близости.Таким образом, возникает задача ускорения выполнения алгоритма вычисления совокупности величин Фfc(hp). При сдвиге апертуры в одном из направлений по полю изображений на одну строку (столбец) Х(Л) (К(л)) пикселей исключается из области, ограниченной апертурой и столько же новых пикселей попадает в ее пределы.
t:
п( А) пикхелей,
уходящих из апертуры
V
Положение апертуры после сдвига, величины Ф'А (hr) Рис. 5.18. Сдвиг апертуры по полю изображения с изменением значений
//(Л) пикселей
В дальнейших рассуждениях обозначим «(/1) количество пикселей, изменяющих свое значение при сдвиге апертуры на один пиксель независимо от направления сдвига апертуры. При движении апертуры по изображению значение Фа С'/') образуется следующим образом.
Допустим, что до сдвига аперту ры были известны все значения Ф* (/'/>). необходимые для идентификации состояния сиены. При сдвиге апертуры в ее пределах остается Л'(А)-п(А) пикселей, участвовавших в формировании значений Ф{((hp), поэтому целесообразно использовать значения Ф^.(hp) для вычисления на их основе множества значений Ф\(hp), получающихся после сдвига апертуры. Величины Ф'к (hp) можно представить как сумму
(5.17)
где ДФk(hp) поправка, связанная с попаданием в пределы апертуры новых пикселей.
Выразим Ф'к (hp) с помощью (5.16):
П
где h'p(Pj) - гистограмма участка сигнала Р(х,у), накрытого апертурой после сдвига. Учтем, что
т.е. при сдвиге гистограммы нет необходимости производить ее повторное вычисление, а достаточно найти значения Ahp(Pj) приращений отдельных элементов гистограммы й/> (//¦). Выражения (5.17) и (5.19) показывает рекуррентность разработанного алгоритма вычисления значения Ф'^ (hp) для
идентификации состояния наблюдаемой сцены.
Можно предложить следующую процедуру для вычисления массива значений Ahp(Pj). Изначально все значения Дhp(Pj) полагаются равными нулю.
На первом шаге процедуры выполняется последовательный обход «(>4) пикселей, выбывающих из апертуры, с уменьшением на 1 значения Ahp(Pj), для которого Pj соответствует значению рассматриваемого пикселя из совокупности объемом п(а). На следующем этапе рассматривается последовательность попадающих в апертуру п(А) пикселей. При этом, по аналогии с первым шагом величина Ahp(Pj) для соответствующих значений Р{ увеличивается на 1. Вычислительная трудоемкость этой процедуры составит 2 -п(А) операций сложения.
Подставим (5.19) в (5.18):
Фк(^) = !(>'/>(Pi) + *hp(Pi)~КэИ)f • (5-2°)
П
Применяя формулу разложения квадрата суммы с последующей перегруппировкой слагаемых, получим:
П (5.21)
+l[ ДМ ) ¦ (2 • (А/> (Pi) ¦' >Ъ (Pi)) + Abp (Pi ))]¦
С учетом (5.16) и (5.17) получим
ЛФ* (hp) = Z[Ahp (I)).(2. (hp (/})- hk 3 (/})) + Ahp (Pf))]. (5.22)
Таким образом, для вычисления массива из величин ф'к(Ьр) п0
к
(5.17) необходимым условием является вычисление массива приращений АФ^ (/»/») такого же размера. Как было сказано выше, вычисление величин
Ahp(Pj) требует 2-п(А) операций сложения. Поэтому с учетом (5.22) для вычисления АФд.(hp) потребуется 3-N(0) + 2-n(A) операций сложения. Что касается умножений при вычислении по формуле (5.22), то количество нетривиальных операций умножения будет максимально равно 2-п(А). Это связано с
тем, что в массиве Ahp(Pj) нулевыми будут N(0)-2/i(/ На приведенных ниже графиках изображены по две кривые: вычислительная трудоемкость расчета критерия близости гистограмм по прямой формуле ((2.32), кривые (1)) и по рекуррентной формуле ((5.22), кривые (2)). а) ч-ООСОКЮЮтГ г т- tN n t Ю Ю О О СО Г"-, to U") Г Г N (О ^F К) (D Рис. 5.19. Зависимость количества сложений от размера апертуры
Графики на рис. 5.19 показывают зависимость количества сложений N(.S') ОТ размеров стороны квадратной апертуры п(А). Графики на рис. 5.19, а, рис. 5.20, а и рис. 5.21, а построены для = а графики на рис. 5.19, б, к рис. 5.20, б и рис. 5.21, б - для = 6 (рис. 5.19, б). к Выше показано, что для вычисления массива ZMVo) величин потребуется выполнение (5.23) операций сложения. Для вычисления Фi(A/>) напрямую количество сложений составит W, (S) = ? N (Л,,,) {2 • N (е) + и2 (Л)]. (5.24)
Рис. 5.20. Зависимость количества умножений от размера апертуры Найдем точку, в которой происходит пересечение графиков (1) и (2) (см. рис. 5.19). Для этого решим уравнение, составленное из правых частей (5.23) и (5.24), относительно л (Л).Решение такого квадратного уравнения дает результат n(A) = \ + yjN(Q). Таким образом, если jV(6>) = 256, то при /г(Л)>17 использование формулы (5.22) приводит к выигрышу в Л', (.сложений. График зависимости количества операций умножения, требуемых для вычисления значений ФЦй/»), показан на рис. 5.20. При вычислении по рекур-рентному алгоритму количество умножений составит к При вычислении напрямую: к Точка пересечения графиков имеет абсциссу«(>4) = Л^((2)/4. Т.о., если Лг(0) = 256, то при и(л)<64 выигрыш по количеству операций умножения составит Рис. 5.21. Зависимость количества арифметических операций от размера = (5.28) к апертуры Рис. 5.21 демонстрирует графики зависимости полного количества ариф-метических операций N(0)=N(S) + N(M). (5.29) от размеров апертуры. Рис. 5.22. Зависимость времени выполнения алгоритма анализа изображений от размера апертуры На рис. 5.22 показана зависимость времени выполнения процедуры гистограммного анализа от размеров апертуры, полученные при реализации рекуррентного алгоритма вычисления критерия близости гистограмм (кривые (2)) в сравнении с прямым вычислением критерия (кривые (1)). С учетом соотношений (5.25), (5.28) и (5.29) полный выигрыш в количестве арифметических операций составит W, (О) - ,V2 (О) = ? Л'(/Ь) • [п2(Л)-4-и(Л)]. (5.30) Полученная величина принимает положительные значения при п> 4, что означает, что в случае, когда размер стороны апертуры превышает значение в 4 пикселя использование рекуррентного способа (5.22) вычисления критерия квадратичной близости является более выгодным по сравнению с вычислением напрямую (2.32) с точки зрения вычислительной трудоемкости. Значения времени выполнения алгоритма анализа изображений показывают, что при размере стороны апертуры, соответствующему 2-25 пикселей выигрыш по сравнению с прямым вычислением критерия близости гистограмм составляет 50%. При увеличении размера апертуры преимущество рекуррентного метода вычисления критерия близости увеличивается до 75% в случае, когда размер стороны апертуры принимает значения порядка 60-70 пикселей. Реализация рекуррентного алгоритма вычисления квадратичного критерия близости предполагает использование целочисленной арифметики. Это связано с тем, что при вычислении величины А/>(//) (формула (5.19)) используется значение hp(Pj)- которое соответствует количеству пикселей ярко стью Рг В случае, когда в качестве элементов гистограммы используются нор- - N (Р-) мнрованные величины hP(Pj)= д^'^ , для получения значений hp(Pj) необходимо выполнить умножение hp(Pj)' NA(Pt). При вычислении нормированных значений элементов гистограммы hf,(Pj) на этапе её формирования по предъявленному изображению происходит частичная потеря точности за счёт ограниченного числа двоичных разрядов, Таким образом, целесообразно все эталонные гистограммы и мгновенную гистограмму строить по выборкам из апертур одинаковых размеров. Это позволит избежать необходимости нормирования значения отсчетов гистограмм.