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

Хромосома особисоответствует понятию генотип, возможное решение – понятию фенотип.В приложении к задаче совмещения изображений популяция – это множествовзаимных расположений РИ и ВИ. Каждая особь в популяции являетсязакодированной координатой взаимного расположения РИ и ВИ.В начале работы алгоритма случайным образом формируется популяция(блок «Инициализация популяции решений – кандидатов»). Применительно ксовмещению изображений это соответствует генерации случайного набора точекпространства поиска.34С целью оценки качества закодированных решений, используется функцияприспособленности, которая необходима для вычисления приспособленностикаждой отдельной особи (блок «Оценивание особей»). Для совмещенияизображений это будет выражено в вычислении значения целевой функции длякаждой координаты возможного положения виртуального изображения (точки вмногомерном пространстве поиска).По результатам оценивания особей наиболее приспособленные из нихвыбираются (блок «Селекция») для скрещивания.

Это соответствует отборукоординат в пространстве поиска, которым соответствуют наилучшие значенияЦФ.В результате скрещивания выбранных особей посредством применениягенетическогоинформацияоператоракоторогокроссовераформируетсясоздаетсявпотомство,результатеобменагенетическаяхромосомнойинформацией между родительскими особями (блок «Кроссовер»). Созданныепотомки формируют новую популяцию, при этом некоторая их часть мутирует(применяется генетический оператор мутации), что выражается в изменении ихгенотипов (блок «Мутация»). В случае совмещения изображений в многомерномпространстве поиска координат это выражается во внесении изменений вкоординатыточек,вкоторыхпроисходиловычислениезначенийЦФ.Измененные гены дают особи новые свойства. Если эти новые свойства полезны,они сохранятся в данной популяции – при этом произойдет скачкообразноеповышение приспособленности.

Поколением называется последовательностьопераций «Оценивание популяции» – «Селекция» – «Скрещивание» – «Мутация».Последовательность некоторого количества таких поколений представляет собойэволюцию популяции. [26].Длительность эволюции может определяться следующими факторами:нахождение удовлетворительного решения задачи;ограниченность количества поколений;вырождение популяции, когда степень разнородности хромосом впопуляции становится меньше допустимого значения [27].35В качестве наиболее перспективных корреляционно-экстремальных методовсовмещения изображений для дальнейшей реализации и анализа выбраны методымультистарта, метод покрытий (сеток), в частности один из его подвидов – поискс некоторым шагом, а также генетические алгоритмы. Названные методыобладают необходимыми параметрами для решаемой задачи: дают решение,совпадающее или близкое к глобальному экстремуму за приемлемое время.Позволяют существенно сократить временные затраты в сравнении с методомполного перебора вариантов решения.

Туннельный алгоритм и поиск с запретамиисключены из дальнейшего рассмотрения по причине сложности их применениядля решаемой задачи, а также недопустимо больших временных затрат за счетитерационных составляющих данных алгоритмов.Экспериментальные результаты исследования корреляционных алгоритмов иих анализ приведены в 4 главе настоящего диссертационного исследования.1.5 Некорреляционные методы совмещения изображенийОсновное отличие некорреляционных методов совмещения изображений откорреляционных состоит в отсутствии необходимости вычислять некоторую меру«похожести» (корреляционную функцию) между совмещаемыми изображениями.Основныеотличиянекорреляционныхметодовоткорреляционныхприменительно к области совмещения изображений в системах улучшенного икомбинированного видения, следующие:1)большинство некорреляционных методов работают не с растровымиизображениями, а с контурным представлением изображений, либо с некоторымкомплексным описанием отдельных областей изображений.2)меньшая трудоемкость необходимых вычислений;3)большая «интеллектуальность», зачастую некорреляционные методысовмещения строятся исходя из эмпирических соображений;4)меньшая точность и робастность некорреляционных алгоритмов, чтоявляется неизбежной потерей при увеличении быстродействия.Одними из наиболее перспективных для решения задач совмещенияизображений являются методы комплексного контурного анализа [28].36Другая широко применяемая группа методов заключается в поиске наизображении особых точек и сопоставлении этих точек друг с другом на разныхизображениях.

Данный подход является одним из наиболее распространённых врешении разнообразных задач по созданию систем технического зрения.На сегодняшний день существует значительное количество разнообразныхалгоритмов, позволяющих выявить на изображении те или иные особенности. Вкачестве выходных данных алгоритмов детектирования выступают некотороеспецифицированное описание геометрических объектов, принятых в качествеособенностей, подлежащих описанию. Такие описания (обычно используетсятермин«дескриптор»)представляютвекторыхарактеристик,однозначноидентифицирующие геометрические объекты на изображении: их размер,ориентацию, взаимное расположение.Следуетособенностей.различатьдетекторыОператорыивыделенияоператорывыделенияхарактерныххарактерныхособенностейдолжнывыделить при обработке изображений требуемые особенности, определеннымобразом увеличить степень их различимости.

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

«Хорошие» признаки должны обладатьрядом свойств:371. Повторяемость. На изображениях одного и того же объекта или сцены,сделанных с разных точек зрения и при разных условиях освещенности,большинство признаков должно быть установлено.2. Локальность. Признаки должны быть максимально локальными, чтобыснизить вероятность перекрытий.3. Репрезентативность. Количество признаков должно быть достаточным,чтобы разумное число признаков детектировалось даже на небольшомизображении объекта.4.

Точность. Признаки должны быть точно продетектированными поотношению к масштабу и форме объекта.5. Эффективность. Для быстродействующих приложений критично важно,чтобыпроцедуравычисленияпризнаковнетребовалазначительныхвычислительных затрат [29].1.6.1 Дескриптор SURFДескриптор SURF (Speeded up Robust Features) относится к числудескрипторов, которые одновременно выполняют поиск особых точек и строят ихописание, инвариантное к изменению масштаба и вращения.

Кроме того, сампоиск ключевых точек обладает инвариантностью в том смысле, что повернутыйобъект сцены имеет тот же набор особых точек, что и образец.Метод SURF можно условно разделить на два этапа. На первом этапе ищутсяключевые точки. Для этого используются значения гессианаdetH   2 I  2 I   2 I .22  xy x y(1.18)Здесь I x, y  – функция яркости изображения. Для оценки частныхпроизводныхвторогопорядкавсоответствующие шаблоны (маски):производной2Ix 2составеD xxгессиана(1.18)используютсядля получения оценки частной380011D xx   11100001111100001111100002222200002222200матрица D yy для оценки частной производнойтранспонированиемпоследней( D yy  DTxx ).0022222002Iy200111110000111 ;1100001111100получается из матрицы D xxОценкасмешаннойчастной2Iпроизводнойнаходится в результате свертки исходного изображения сxyматрицей00 0 000 00 011 0 1 1 1 00 10 111 0 1 1 1 011 0 1 1 1 00 1D xy   0 000 0 000 0 .0 1 1 1 0 111 00111011100 1 1 1 0 111 0000000000В рабочем варианте метода SURF оценка гессиана производится не поформуле(1.18),апоформуле  detH   D xx  I   D yy  I  0.9 D xy  I ,где I – интенсивность (яркость) изображения,  - знак свертки.Неинвариантность метода к масштабу вынуждает получать оценки гессиана сфильтрами (масками), размер которых изменяется в некотором диапазоне (от 9 до99).

Для уменьшения числа фильтров вводятся октавы. Всего от 4 до 6 октав. Вкаждой октаве размер фильтра изменяется с определенным шагом. Например, в39первой октаве с шагом 6 (9, 15, 21, 27 – размеры фильтров), во второй с шагом 12(15, 27, 39, 51) и т.д. Размеры фильтров в соседних октавах перекрываются.Точка (i 0 , j 0 )признается ключевой, если значение гессиана в нейоказывается максимальным или минимальным по сравнению с соседними в окне3 3 в данной октаве и в соседних с ней нижней и верхней октавах того жеразмера.На втором этапе осуществляется построение дескрипторов ключевых точек.Дескриптор каждой ключевой точки в методе SURF содержит 64 (в другихвариантах 128) чисел. Основная задача дескриптора – определить направление, вкотором модуль градиента Iфункции яркости принимает максимальноезначение.