Диссертация (Разработка и исследование алгоритмов совмещения изображений от бортовых видеодатчиков с виртуальной моделью местности), страница 4

Вычисление функциивзаимной корреляции было исторически первым методом, использовавшимся для19корреляционной обработки изображений. Второй причиной широко примененияэтогоалгоритмаявляетсяотносительнаяпростотаеготехническойреализации» [15].1 N 1 M 1F x, y    I РИ i, j  I ВИ i  x, j  y ,MN i 0 j 0(1.1)где 0  x  K  N  , 0  y  L  M  , KL – размер ВИ, NM – размер РИ, x, y –смещение фрагмента IРИ относительно IВИ. В системах обработки изображений x иy обычно отсчитываются от верхнего левого угла, для которого x=0, y=0.Чтобыминимизироватьчислоложныхмаксимумов,корреляционнаякритериальная функция нормируется.

Кроме того, по значению нормированнойкорреляционной функции в глобальном экстремуме (ГЭ) возможно судить о том,является он истинным или ложным (значение истинного глобального экстремумадолжно быть близко к единице). Функцию F(x,y) можно представить в виде:2 N 1 M 1   I РИ i, j  I ВИ i  x, j  y  i 0 j 0F 2  x, y   N 1 M 1 2  N 1 M 1 2Ii,j   РИ     I ВИ i  x, j  y  i 0 j 0  i 0 j 0(1.2)1.2.3 Разностные критериальные функцииКак сказано в [15]: «Разностные алгоритмы основаны на поэлементномвычислении разностей интенсивности изображений».Общее выражение F x, y  для разностных функций имеет следующий вид:N 1 M 1nF  x, y     I РИ i, j   I ВИ i  x, j  y  ,(1.3)i 0 j 0где n=0,1,2,...N.В технике получили распространение следующие разностные критериальныефункции:функция среднего модуля разности (определяется как сумма модулейразностей интенсивностей совмещаемых изображений):20F1x, y  1 N 1 M 1  I РИ i, j   I ВИ i  x, j  y ,NM i 0 j 0(1.4)функция среднего квадрата разности (определяется как сумма квадратовразностей интенсивностей совмещаемых изображений):21 N 1 M 1F2  x, y    I РИ i, j   I ВИ i  x, j  y .NM i 0 j 0Вслучаееслиизображениясовмещеныкачественно(1.5)(яркостисоответствующих пикселей совпадают), значение разностной критериальнойфункции будет стремиться к нулю.

И, наоборот, при рассогласовании яркостейсоответствующих пикселей значение функции будет возрастать. В условияхсильного различия в средней яркости совмещаемых изображений возможновозникновение ложных экстремумов разностной критериальной функции. В этомслучае применяется центрированная разностная функция, в которой вводитсяпоправка на среднюю яркость РИ и ВИ:F x, y  1 N 1 M 1  I РИ i, j   I РИ  I ВИ i  x, j  y   I ВИ ,NM i 0 j 0(1.6)где I РИ , I ВИ – средние яркости изображений.Отсутствие в разностных функциях операции умножения является ихпреимуществом перед корреляционными функциями, позволяющим сократитьвычислительных затраты в среднем в 6 раз [16].1.2.4 Парные критериальные функцииПри числе уровней квантования яркости исследуемого изображения два иболее может быть использовано совмещение ВИ и РИ на основе парных функций.Сравнение изображений производится последовательно по всем элементам.Согласно [15]: «Если каждый элемент РИ при относительном сдвиге (x,y)относительно ВИ имеет уровень квантования яркости i, а каждый элемент ВИимеет уровень j, то парная функция Fij(x,y) 0≤i, j≤2n-1, увеличивается на единицу.Здесь 2n – число уровней квантования.

Следовательно, при i=j функция Fij(x,y)равна числу элементов, уровни интенсивности которых совпадают, а при i=j21функция Fij(x,y) – числу элементов уровни интенсивности которых несовпадают».Виртуальноеизображениеявляетсябинарным,поэтомуиреальноеизображение, чтобы привести его к виду, сравнимому с виртуальным, необходимосделатьбинарным.Дляэтогореальноеизображениеподвергаетсяпредварительной обработке и выделению границ, цель которой – выделить наизображениинаиболеезначимыеобъекты.Присовмещениибинарныхизображенийлучшие результаты дают парные критериальные функции.Применение корреляционных и разностных функций для бинарных изображенийне представляется возможным, так как не обеспечивает требуемого качествасовмещения.Для более подробного описания парных критериальных функций введемследующие обозначения:F11(ax)=a;F01(ax)=b;F10(ax)=c;F00(ax)=e;dр и dв –число элементов с единичной интенсивностью в РИ и ВИ;fр и fв – число элементов с нулевой интенсивностью в РИ и ВИ.По своей сути данные обозначения сводятся к следующему.

Значение асоответствует совпадению черных пикселей на сравниваемых изображениях.Значение е соответствует совпадению белых пикселей на сравниваемыхизображениях. Значения b и c – пиксели на изображениях имеют различнуюяркость: белую и черную, черную и белую соответственно.Известны следующие парные функции [15]:1)функция Рао:K2)a,abce(1.7)функция совпадения нулей:K=a,(1.8)223)функция Джекарда:a,abc(1.9)a,2a  b  c(1.10)K4)функция Дейка:K5)функция Соукала и Снита:K6)a,a  2(b  c)функция Кулзинского:K7)a,d э  dT  aaе,a  e  2(b  c)(1.14)aе,abce(1.15)ae  bc,ae  bc(1.16)a ebc.abce(1.17)функция Юла:K11)(1.13)функция Соукала и Мишнера:K10)(1.12)функция Роджерса и Танимото (II):K9)a,bcфункция Роджерса и Танимото (I):K8)(1.11)функция Хаммана:KКак отмечается в [15]: «Выбор конкретной парной критериальной функцииопределяется относительной важностью единичных и нулевых элементов, атакже относительной важностью событий, заключающихся в совпадении илинесовпадении интенсивностей элементов в решаемой задаче».23Методы1.4поискаглобальногоэкстремумавзадачахмногоэкстремальной оптимизацииОднойизважнейшихсоставляющихкорреляционно-экстремальныхметодов совмещения изображений является метод поиска глобальногоэкстремума,спомощьюкоторогопроизводитсямногоэкстремальнаяоптимизация в пространстве параметров и ограничений решаемой задачи.Для решения задач оптимизации создано весьма большое количествометодов и алгоритмов, однако, универсального подхода, дающего хорошиерезультаты для различных практических задач, на настоящий момент несуществует.В наиболее общем виде задачу глобальной максимизации можноопределить следующим образом [17, 18]:f ( x, y )  max ,( x , y )Pгдеf ( x, y )–многоэкстремальнаякритериальнаяфункция,P  ( x, y)  2 | xmin  x  xmax , ymin  y  ymax – допустимое множество задачи,2 – 2-мерное Евклидово пространство.Спецификазадачиглобальнойоптимизациизаключаетсявмногоэкстремальности целевой функции и неразрешимости в общем случае (вслучае непрерывной области определения аргумента и значения функции).

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

Таким образом, основная идея методов глобальной24оптимизации – оценить значения целевой функцииf ( x, y ) на некотороммножестве точек из допустимого множества ( x, y), а различие всех методовзаключается в способах выбора этих точек.По причине того, что заранее неизвестно, где именно во множестведопустимых значений можно найти глобальный экстремум, то необходимонекоторым образом распределить эти точки по множеству ( x, y). Возможно, чтов окрестности выбранной точки ( xn , yn ) существует лучшее значение целевойфункции f ( x, y ) , чем f ( xn , yn ) . К полученной точке ( xn , yn ) обычно применяюталгоритм локального спуска.

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

Это связанос тем, что большое число алгоритмов глобального поиска состоит из двухэтапов — глобального и локального. Подавляющее большинство методовглобальной оптимизации используют методы локальной оптимизации, какминимум для уточнения значения уже найденного глобального оптимума [19].На глобальном этапе целевая функция вычисляется в точках, более илименее равномерно расположенных в допустимом множестве (используетсянекоторая модель покрытия).

Целью этого этапа является нахождение хотя быодной точки в окрестности точки ГЭ целевой функции.Локальный этап может применяться однократно или многократно сцелью: уточнения значения экстремума, грубая оценка которого получена сприменением некоторого метода глобальной оптимизации; отыскания группылокальных экстремумов и выбора среди них наилучшего значения; уточнениязначения целевой функции в некоторой окрестности локального экстремума.25Сложностьрешениязадачиглобальнойоптимизациипородиласущественное количество методов и алгоритмов для ее решения. Классификацияэтих методов и алгоритмов весьма непростая задача по причине их большогоразнообразия.Известные на сегодняшний день методы, исходя из критерия требуемогокачества получения результата, можно отнести к одному из двух классов:методы, которые всегда приводят к нахождению оптимальногорешения, но требуют для этого в наихудшем случае недопустимо большого числаопераций (говоря иначе, решение будет найдено, но, сколько времени потребуетсяна его поиск, заранее сказать невозможно);методы, которые не всегда приводят к нахождению оптимальногорешения, но требуют для получения этого решения приемлемого числа операций(решение будет найдено за требуемое время, однако, в общем случае оно несовпадет с искомым глобальным оптимумом, вопрос заключается в том,насколько серьезно найденное решение будет отличаться от истинного значенияГЭ) [20].Подробная классификация представлена в таблице 1.1.Наиболее общими в теории дискретного программирования являютсяточные методы решения.

К данной группе относятся алгоритмы, в которыхосуществляется либо попытка полного перебора при небольшой размерностизадачи, или максимального сокращения объема перебора в случае, когда задачаимеетбольшуюразмерность.Приэтомимеетместонеизбежностьэкспоненциального времени работы алгоритмов.Часто используемым на практике приемом сокращения перебора являетсяцеленаправленный перебор, основанный на методе «ветвей и границ» или методе«неявного перебора». Он заключается в отыскивании частных решений,представленных в виде дерева поиска, и применении методов построения оценокдля сравнения получаемых решений. Названные оценки должны указать набесперспективные частичные решения, в результате чего от дерева решений сразуотсекаются целые ветви, что сразу существенно сокращает пространство поиска.26Для такого рода алгоритмов необходимо предусматривать процедуру возврата подереву поиска, применяемую в случае, если исследование текущего направленияполностью завершено и необходим просмотр тех ветвей дерева, которые еще неподвергнуты рассмотрению.Таблица 1.1 – Методы и алгоритмы дискретного программированияНаименование алгоритма (метода)1 группа Методыи Полный перебор вариантовалгоритмыМетод ветвей и границ(точные последовательного Методдинамическогометоды) суженияпрограммированиямножестваМетод множителей Лагранжарешений (полный и АлгоритмыАлгоритмыцеленаправленный предварительного отсеченийперебор)расширенияи Алгоритмыпоследующегоконечногосужениярасширения исуженияКомпозитные алгоритмы2 группа Методыи ИтеративныеАлгоритмалгоритмы(локальные)ближайшего(прибли- последовательного алгоритмысоседаженные улучшенияАлгоритмметоды) решенийсредней(эвристическиевеличиныалгоритмы)СтохастическиеСлучайныйалгоритмыпоискНаправленныйслучайныйпоискИмитацияотжигаМетодыпараллельнойобработки данных(методыискусственногоинтеллекта)Локальностохастическиеметоды(эволюционныеметоды)НейронныесетиДостоинстваОптимальноерешениеВысокаяскоростьполучениярезультатаНедостаткиNP полнота.Нереализуемыпри большомчислеисходныхданныхРостпогрешности сувеличениемобъемаисходныхданныхВероятностныйс поискПросмотробластирешениизаданнойвероятностьюРешение,Низкаяблизкоек скоростьоптимальному получениярезультатаВысокаяСложностьскоростьи анализа,точностьпрограммнойполученияи аппаратнойрезультатареализацииЭволюционныевычисленияКо второй группе относятся алгоритмы последовательного улучшениярешений, хорошо развитые в теории математического программирования.