Методы сопоставления изображений (1033991), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

Стратегия поиска

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

Критерий качества отображения

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

В том случае, если в качестве характерных признаков изображения используются точки контуров, критерий оптимальности обычно строится на основе карты расстояний. Карта расстояний представляет собой следующее отображение множества контурных точек в пространство изображения. Пусть - область задания второго изображения (см. уравнение 1) и пусть - множество контурных точек на этом изображении. Тогда карта расстояний будет:

. (10)

Критерий качества преобразования будет выражаться через карту расстояний следующим образом:

, (11)

где , а - множество контурных точек на первом изображении. Уравнение 11 отличается от уравнения 5 лишь тем, что при его вычислении не требуется знать соответствия между характерными признаками изображения, такое соответствие устанавливается автоматически для данного пространственного преобразования. Уравнение 11 может быть обобщено на случай использования ориентированных точек контуров. При этом в качестве угла ориентации используется направление вектора градиента в данной точке. Использование ориентированных точек контуров позволяет гораздо надежнее выделять глобальный максимум, соответствующий истинному пространственному преобразованию.

Критерий наименьших квадратов также широко используется и для методов, основанных на площадях. Однако в этом случае минимизируется среднеквадратичное отклонение соответствующих значений интенсивностей (см. уравнение 3). При наличии некоторых априорных ограничений на пространственное преобразование в функцию, описывающую критерий качества, могут добавляться соответствующие слагаемые. Одним из наиболее широко используемых ограничений в биомедицинских приложениях является ограничение линейной эластичности, изменяющее критерий оптимальности следующим образом:

, (12)

где оператор имеет вид: . Данное ограничение служит для установления предпочтения плавным пространственным преобразованиям, не обладающим разрывами.

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

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

, (13)

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

Одним из важных способов улучшения надежности совмещения является использование симметричной функции качества. В уравнениях 3, 5, 11, 12 и 13 функция качества не является симметричной в том смысле, что ее минимумы в общем случае не совпадает с минимумами функции , где , а . То есть результат совмещения двух изображений зависит от порядка этих изображений. Это связано с неоднозначностями, вызванными большим числом локальных минимумов, количество которых растет при увеличении размерности глобального преобразования. Как показано в ряде работ, использование симметричной функции качества приводит к уменьшению числа локальных минимумов, а значит, к улучшению надежности совмещения. Одним из способов построения симметричной функции является совместное решение прямой и обратной задачи, то есть нахождение такой пары преобразований и , которые дают минимум следующей целевой функции:

(14)

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

Оптимизационный алгоритм

Поскольку функция качества пространственного преобразования имеет множество локальных экстремумов, необходим оптимизационный алгоритм для эффективного поиска глобального экстремума этой функции. Лишь в случае установления соответствия между опорными точками человеком-оператором существует возможность определения пространственного преобразования без поиска в пространстве параметров. Для этого следует продифференцировать уравнение 5 по параметрам преобразования и приравнять эти выражения нулю, а затем решить полученную систему уравнений:

. (15)

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

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

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

В случае привлечения различного рода структурных элементов для оценки качества отображения по формуле 5 возникает необходимость в установлении соответствия между структурными элементами на паре изображений. Здесь возможно два подхода. Первый подходзаключается в просмотре точек в пространстве параметров преобразования. Для каждого рассматриваемого преобразования производится отождествление структурных элементов и оценка функции качества. Здесь могут быть использованы такие же алгоритмы оптимизации, как и в случае методов, основанных на площадях. Предпочтение отдается второму подходу, при котором рассматриваемой гипотезой является соответствие между структурными элементами. Для каждого такого набора соответствий можно найти пространственное преобразование, воспользовавшись системой уравнений 15, и оценить качество найденного преобразования по уравнению 5.

Множество всех возможных комбинаций различных соответствий, образующих дерево перебора, экспоненциально зависит от числа структурных элементов, поэтому исчерпывающий поиск допустим лишь в ограниченном числе случаев. Более популярными являются стохастические методам или методы конечного поиска, такие как динамическое программирование, методы моделируемого отжига и генетические алгоритмы. Во всех этих методах производится то или иное отсечение неперспективных ветвей в дереве перебора, что существенно повышает быстродействие, но может привести к выбору неоптимального преобразования. Сокращение перебора также осуществляется с помощью привлечения дополнительных признаков структурных элементов помимо их пространственных координат (например, для отрезков прямых линий такими признаками могут быть угол ориентации и длина отрезка). Это позволяет накладывать дополнительные ограничения на возможные сопоставления.

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

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

Одним из главных требований к методам совмещения является точность совмещения, то есть среднее (или максимальное) расстояние между соответствующими друг другу точками. Зачастую совмещение требуется выполнять с субпиксельной точностью. Это требование является актуальным для многих задач: выявление изменений, объединение данных, вычисление дальности и фотограмметрические приложения.

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

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

Характеристики

Список файлов реферата