Методы сопоставления изображений

Введение

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

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

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

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

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

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

Постановка задачи

В задаче совмещения дано два изображения:

 и , (1)

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

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

 и . (2)

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

. (3)

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

, (4)

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

 (5)

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

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

Пространство поиска

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

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

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

, (6)

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

. (7)

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

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

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

, . (8)

Оптический поток может использоваться, как в явном виде (в виде зависимости ), так и в некоторой параметризации. Такой параметризацией могут служить, например, ряды Фурье:

, (9)

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

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

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

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

Характерные признаки изображения

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

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

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

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

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

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