Анисимов Б.В., Курганов В.Д., Злобин В.К. - Распознование и цифровая обработка изображений (1033973), страница 6
Текст из файла (страница 6)
Как видим, на этапе 2 будет най-" 'гден набор следующих пар: (1, 1), (2,2), ' е д в<111 1:(3, р), (4,4), (з, и, г ((.9) гг азо :., вновь не выполняется. т(чгг Ра' э, ° а д. а 3<у,1! .~!:.'ы а з ыр )и, К„и решением вопроса об оптимальном ерадвеиие ' ' объединении его отметок 1, 2 и 3. Соот- е1.! г с)1ЕЕ) :;" ветствующее изменение набора пар, по- г ср 5 с)181) "!! лученного на этапе 2, реализуется с по- г кввеудикпс ЛЕ1,11 с! /<<,1'1 бЩ1 С ебвенссе1 б) 1 4 31111 ! а вевиегс<11,11 г 1 5 .4Я11 Ф' з<л, Рнс. !.7. Объединение отметок соседних Рнс.
!.8. Объединение од- кадров: поименных отметок сосед- а — связи, устаиаалиаасмыс неладу отметками ннх кад))оа с помошью ал4<)( соамсо(синого кадра на этаиа ! оеъслнясния от. РО<(нтма поиска абсолютной маток; б — окоичатслъиыс санин между одно'мг имсинымн отметками мощью второго слагаемого второй суммы в (1.11). Это изменение опретг деляется выбором минимального из приращений (сравнение 3, рис. 1.8, в): а) функции стоимости участника конфликта, появившегося на предыдущем шаге (отметка 3 кадра К„), при условии, что исключены все отметки кадра К„+„оптимально присоединенные на шаге 2 (от:»', метки 1 и 2); б) суммы функций стоимости отметок кадра К„, оптимально объ.' ' единенных на предыдущем шаге (отметок 1 и 2), прй условии, что исключена спорная для данного шага отметка (отметка 2 кадра К»а!). Набор пар, полученный в результате выполнения этапа 3 алгоритма,.имеет следующий вид: (1,1), (2,2), (3,3), (4,4), (5,5) (рис.1.7, б; 1.8, в).
Этот набор удовлетворяет условию (1.9), и, следовательно, соответствующая ему сумма функций стоимости является искомой абсолютной минималью. 23 Таким образом, число операций сравнения посл шага составите„=- 0,5 к (к+ !). Рассмотренный пример, а также дальнейшие пре жения (1.!!), связанные с представлением в основном его членов Г(,а)шп. '=! (! ))шп(о ! ! ппп ч', Еьь и )пш ~ Еп в виде, аналогичном этому выражению позволяют сформулировать следующее правило. Правило разрешения конфликта: временно исключаютс р спорные отметки кадра К„„и сравниваются получаемые ения все с чаются из рассмотпосле этого приращения Л (), !) всех участников конфликп)а. Тот участник, для которого упомянутое приращение максимально (например, отметка с номером ! = 1), получает высший приоритет; к нему, как с номером и ранее, присоединяется ближайшая спорная отметка ! = ага гп!п Ех!.
Для остальных участников конфликта (нап )шйв+ ! нап,о имер д отметок с номерами 2, 3..., )е) находятся соответст-ую теддчУУЮЩИЕ иМ Нсеав значения ппп Е,), ! = 23,..., ! (где Мгы = М '., ' Е ), б в+! = и+!',ага ппп,!), и в+! )едтв+ ! приращений Лт (), !) = ЕΠ— ппп Ег! при условии, иио все спор- )ым„(+)) ные отметки по-прежнему считаются исключенными. Тепе ь д у ик конфликта (например, отметка с номером ! = 2), еперь рудля которого приращение Л! (), !) максимально, объединяется с отметкой !' = агд гп!и Е„., 3»частникам же 3,4,... ! ннов спшвятся ! "!242 , вновь спшаяп)ся в со- )шм 4! ответствие новые значения ппп Е! (где М'"! = М ',( „+! = в.р! !батя пнп Еы, )~мв4! )ш()!в+! ага ппп Ез!)) и приращений Лх! (), !) = Ем — шш ЕО при условии, что Я(2) в+! все спорные отметки исключена и т.
д. )з — ! раз. При вовлечении в конфликт новой отметки (например, отметки с номером ), + !) процесс его разрешения повторяется вновь для отме- ток с номерами ! = 1,2, ..., с, + 1 пока конфликт либо о икт ли не получит нового продолжения, либо его разрешение завершится. Приведенное правило для ситуации, показанной на рис.
!.7, ил- люстрирует рис. 1.9 (где а — г — соответственно этапы алгоритма, символические обозначения соответствуют обозначениям на ис. !.8). Как следует из (! .8), мв+, ш)п Ф (У, !)= пяп Ф (), )1= ш!и ~ч~ ~Е (Ад), !!д, ш))шп (),!)шп (у,!)шп )=! где П вЂ” множество пар (1, !), удовлетворяющее условию не более чем попарного объединения отметок, аналогичному условию (1.9). Другими словами, можно построить алгоритм поиска абсолютной минимали функционала (Т), начинающийся с присоединения к каждой отметке кадра К„! ближайшей отметки кадра К .
в. 24 образом, рассмотренный алто- а! У лрэФлслр! ву)у! ка абсолютной минимали Функ- У " л (лэрл)пх()ус '! Ц Ф при условии не более чем по- Лыйэр э)ах () уд! 2" Р бд л ~ ~ ~~~ д дрд) »Ч "Рл Р Д Урбан д * У Д(д,() М"У "" * РУ,()(» д(у() Е~ У П.Р)) д адд)р Иней полученной величины посредством й! ! ,;,. РазРешения конфликтов.
При этом пары :,'~;;((1,!) переводятся в допустимое множество. :Тч; Следовательно, нахождение абсолютной ми- „р„,„'„,„„у„~„„(( р),, д р д((у( .ею б р* .орд д ! у ((у() '" минимальной деформации, переводящей ; -2-- ° -У (,Л ° Л.У-. -' Д) 4 л()!! '. жество, заключается в разрешении кон', 'фликтов, как правило, между отдельными "ф~,.:: небольшими группами отметок, если А! = Вьуйср ювх Луд! — .Сл Рмр ,Ч" ~ "Р"" У " '"У с ('ду! :"в(-- ЧЕ рддр ~ ~~ а лр !В,Р„„,Д „„б „„„Д,„,„б„л„„~~ Д Д((() Мл У РР .
У~ Д(У,»( ,))( бд ~, ° ° Р~ - ° ° -., У(д,(( ЛФ)! ! РР~.ПД ; еще более увеличиваются при наличии в (Ь— ' "х:;.'! кадрах нелинейных искажений. Все это за- Рнс. ! тй Объеднненне од- , ставляет продолжать поиск более эффек- нонмевных отметок сосед--;! тинных алгоритмов идентификации. ннх кадров пп правнлу разрешения конфликтов Ра», П р н м е ч а н н е. Как будет показано ниже, метод трасс наиболее целе- (, сообразно использовать для вдентнфнкацвн точечных изображений после нх () предварнтельного грубого нлн точного совмещения, й 1.4. КВАЗИКОРРЕЛЯЦИОННЫА МЕТОД ИДЕНТИФИКАЦИИ )у*б, ТОЧЕЧНЫХ ИЗОБРАЖЕНИИ Сущность квазикорреляционного итерационного метода идентифи„" .': кации (совмещения) кадров заключается в том, что взаимной корреля- ционной функции двух соседних идентифицируемых кадров Кв и К„„ ":.„' (или телевизионного и машинного кадров соответственно) в окрест- :: ности ее искомого максимума придается куполообразная форма путем :...";"определенного функционального преобразования одного из кадров ", ' (например, кадра Кв+!).
В результате возникает возможность органи»)д))л зовать направленный поиск упомянутого максимума, используя ту или иную итерационную процедуру. При этом изложить этот алгоритм Ф: ; удобно в следующем виде (см. !8)). й1атематическая модель квазикорреляционного метода. Поставим в соответствие 1-й отметке кадра Кв+! некоторые функции у! (х, у) 2 25 (1 = 1,2,..., М„„), которые будут определены позднее. Используя совокупность этих функций, опишем кадр Кн+! в виде функции м ! ! Р (х,у)= ~чР ~1 (х, у). (1. 12) 1=! Пусть координаты х, у и х, у отметок произвольного объекта, наблюдаемого в кадрах К„„ и К„ соответственно, имеют следующую связь: л=л( х, у), у=-у ( х, у).
(1.13) Тогда Р (л,у)=Р[к(х,у), у(х, у)[=Р (х,у). (1.!4) Вычислим значение Р (х, у) в точках (хг, у!) (! = 1,2,..., М„) и составим выражение для новой функции: мв Р (а, а„., а!) =~чЄР( ху, у!), (!.!6) т=! где а„а„..., а! — независимые параметры, характеризующие связь (1 .13) между системами координат ху и ху. Предположим, что М„= Мц+! = М', т. е.
количества отметок в кадрах К„и К„е! совпадают, и в этих кадрах присутствуют только отметки от идентичных объектов. Обозначим символами аг, аз,..., а! значения упомянутых параметров, при которых координатные описания объектов в идентифицируемых кадрах совпадают. Существенным для дальнейшего изложения является вид функции Р (а„а„..., а,).
Положим, что все определяющие ее компоненты таковы, что допустимые значения а„ а,,..., а, образуют в пространстве этих параметров ограниченную вйпуклую замкнутую область 6, причем указанная функция непрерывна и дифференцируема на множестве точек, соответствующем этой области, имеет единственный максимум в точке (а1, аз,..., а!") Е 6 и монотонно убывает с возрастанием расстояния между точками (а„а,,...,.а,) и (а1, аз, ..., а!'). Тогда необходимыми и достаточными условиями совмещения кадров Кц и Кне являются дР дР— =Рт (ат, а„..., а!)=О, — =Р, (ат, ав, ..., ай= дР =О, ..., — =Р! (аг, ак, ..., а!)=О .
(1,16) да! и, следовательно, величины а!, а3, ..., ат, характеризующие взаимное положение этих кадров, можно найти решением системы (1.16). Рассмотрим получение требуемой формы функции Р (а„а„..., а!), тесно связанное с выбором функций Р! (х,'у), для случая,гкогда формулы связи (1.13) имеют вид х = х — х„у =,'у,' — у„"т. е.' когда имеет место только взаимное плоскопараллельноетьсмещение кадров. Нетрудно заметить, что надлежащий'вид функции Р (аы а,, ..., а,) можно обеспе- 26 ли в качестве упомянутых функций использовать, например, ости вида Рис.
1.!О. Сонмешеиие точечных изображений с помошью кнвзикорреляционного метода: о — первое точечное ваображенве; б— функционально преобразованное второе точечное наображенне: а — вал коррелвцноввой фувкцан ваображеннй Р (х„ у,) =~Ч~', ~ [2дв — ( от(!1 — хе) †(м)у! — уо)~) Х г=! т=! Х т, (А — ) то!".! — х, [) Х (д — ) м;," — у, !!), (1.!9) " где юц = х; — хп ю[уу~ = у! — уу — абсцисса и ордината отметки .',плоскости корреляции, соответствующей г-й отметке кадра К„и ,,' (ьй отметке кадра К„,; х„у, — координаты г-й отметки кадра К„в ' его системе координат х У (! = 1,2, ..., М'); х, = х — х'* У = У вЂ” У. т: 1 (х, у ) =е (" У) +(" а!) =ехр [ — а[(х — л!) +(у — у!) 1);(!.17) --'-'" ' р! (х,у ) = [2йв — ( х — х!) — (у — у!) ] 2(Ь вЂ” ~л — ха[) т (а — [ у — у.[), (!.18) ~ 1прих)0,— '„1:!где Х (х) = хп Уу — кооРдинаты 1-й отметки кадРа Км„, 10 прях(0; '-"в системе координат ху; !х, й — не- лУ '« ' которые действительные константы, ббльшие нуля.
.а (, Зависимости (1.13) обеспечивают ~'меньшие вычислительные затраты и 5 ' большую скорость сходимости итерационного процесса, чем зависимости (1.17). Условимся, что каждая из д) ,в ! кча .4к ".;;Ф, функций 11 (х, у) (1'= 1,..., М') оп(ределена на соответствующей ей об.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
