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

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

. (15)

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

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

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

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

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

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

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

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

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

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

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

Классификация по типу задачи

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

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

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

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

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

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

Третья (последняя) категория включает обнаружение существенных различий, где основная сложность возникает из-за того, что сами объекты изображения могут существенно меняться вместе с изменениями в направлении съемки и освещения. Эта категория является наиболее общей и может включать все сложности, свойственные первым двум категориям. Дополнительная проблема здесь появляется из-за того, что в процессе совмещения производится попытка сопоставить данные, которые могут содержать сильные отличия. Учет таких отличий приводит к построению робастных методов совмещения, использующих внутреннюю оценку качества, инвариантную к выбросам.

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

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

Заключение

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

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

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

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

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

Литература

G.Christensen, “Consistent linear-elastic transformation for image matching”. In 16^{th Conference on Information Processing in Medical Imaging, pages 224-247, June 1999}

I.J.Dowman, “Automating image registration and absolute orientation: solutions and problems”, Photogrammetric Record, 16(91): pp. 5-18, 1998.

M.Gabrani and O.J.Tretiak, “Surface-based matching using elastic transformation”. Pattern Recognition, 32:87-97, 1999.

D.Lagunovsky and S.Ablameyko, “Straight-line-primitive extraction in grey-scale object recognition”, Pattern Recognition Letters 20, pp. 1005-1014, 1999.

A.A.Mustafa, “Optimum template selection for image registration using ICMM”, 9th British Machine Vision Conference, 1998.

C.V.Stewart, “Robust parameter estimation in computer vision”, SIAM Reviews, September 1999.

P.Thevenaz, U.E.Ruttimann, and M.Unser, “A pyramid approach to subpixel registration based on intensity”, IEEE Transactions on image processing, vol. 7, no. 1, 1998.

^{Иллюстрации}

Рис. 1. Пример вычисления стереодиспаратности для контурных точек пары ректифицированных изображений.

Рис. 2. Разделение существенно трехмерной сцены на поверхности, для каждой из которых необходимо определять собственное проективное преобразование.

Рис. 3. Совмещение инфракрасного и радиолокационного (SAR) изображений. Из-за отсутствия однородного преобразования яркости для изображений, полученных с разных сенсоров, и наличия спекл-шума на SAR-изображении, методы, основанные на первоначальных значениях интенсивностей неприменимы, совмещение производится на основе структурных описаний.

Рис. 4. Пример совмещения оптического изображения с векторными данными (CAD-моделью карты местности).

34. Критерии сходства изображений.

http://www.sernam.ru/book_kir.php?id=49