СПОСОБ ВЫРАВНИВАНИЯ ДЛЯ ПОЛУЧЕНИЯ ИЗОБРАЖЕНИЙ С РАСШИРЕННЫМ ДИНАМИЧЕСКИМ ДИАПАЗОНОМ
ALIGNMENT METHOD FOR OBTAINING IMAGES WITH EXTENDED DYNAMIC RANGE

ПРЕДПОСЫЛКИ НАСТОЯЩЕГО ИЗОБРЕТЕНИЯ
Область настоящего изобретения
Настоящее изобретение относится к получению цифровых изображений. Конкретнее, в настоящем изобретении описан способ точного выравнивания и коррекции изображений при обработке видео и изображений с расширенным динамическим диапазоном.
Описание известного уровня техники
Получение изображений с расширенным динамическим диапазоном используется для воспроизведения большего динамического диапазона яркости при получении изображений и в фотографии. Традиционная техника получения изображений с расширенным динамическим диапазоном включает использование специальных датчиков изображения для передискретизации. Другая техника включает в себя слияние нескольких изображений.
Тем не менее, специальные датчики изображения зачастую сталкиваются с трудностями при использовании в условиях с низким освещением, что создает неоптимальное конечное изображение. Кроме того, кодирование цифровых изображений не всегда предлагает достаточно большой диапазон значений для обеспечения тонких переходов, что вызывает нежелательные эффекты из-за сжатия с потерями.
Следовательно, существует необходимость в эффективном способе выравнивания для точного выравнивания и коррекции изображений при обработке видео с расширенным динамическим диапазоном, который создает высококачественное видео с расширенным динамическим диапазоном с высокой частотой кадров.
СУЩНОСТЬ НАСТОЯЩЕГО ИЗОБРЕТЕНИЯ
Для получения этих и других преимуществ и с целью устранения недостатков традиционного способа в соответствии с целью настоящего изобретения, как реализовано и подробно описано в данном документе, настоящее изобретение предлагает эффективный способ точного выравнивания и коррекции изображений при обработке видео и изображений с расширенным динамическим диапазоном.
Когда изображение с расширенным динамическим диапазоном (HDR) создают посредством слияния ряда изображений с узким динамическим диапазоном (LDR), изображения LDR как правило снимают с разным временем экспозиции (с использованием экспобрекетинга, чтобы охватить некоторый необходимый динамический диапазон) или значениями ISO. Это требует получения снимков с различной длительностью экспонирования, что может вызвать отклонение от заданного положения изображений LDR при перемещении или колебаниях камеры во время съемки (т.е. в камерах без штатива). В такой ситуации для выравнивания и коррекции изображений перед слиянием в изображение HDR требуются особые алгоритмы.
Далее представлено описание способа выравнивания, который основан на обнаружении и анализе отдельных объектов.
Способ включает этап поиска признаков (характерных элементов) в изображении, этап параметризации этих признаков и этап сравнения изображений с различным экспонированием путем сравнения признаков.
Для обнаружения объектов используется канал яркости. Кроме того, другие каналы цветности изображения могут использоваться как источник дополнительных параметров для распознавания объектов.
Канал яркости представлен на логарифмической шкале как его распределение в дискретном пространстве координат пикселей. Предполагается, что канал яркости является непрерывным (в дискретном пространстве) на всем изображении, и его первая и вторая пространственные численные производные (определенные в дискретном пространстве) существуют и имеют конечные значения в любой точке (x,y) канала сигнала яркости.
Поскольку каналы яркости анализируется на логарифмической шкале по основанию «2» (шкала EV), ограничения для уровней черного и белого представлены для всех пикселей в изображении путем следующих ограничений:
- Уровень черного ограничен значением -32 EV;
- Уровень белого ограничен максимально возможным значением в представлении данных исходного изображения, и на шкале EV равен 0,0 EV.
Это значит, что выше 0,0 EV не будет никаких значений, но все значения ниже -32 EV должны быть приведены к -32 EV.
Для данного алгоритма предполагается, что объекты на изображении должны быть построены из своих наименьших обнаруживаемых частей – деталей. Для параметрического представления объектов используются понятия траектория, поток и компонент. Траектории являются тривиальными признаками, характеризующими изображение. Они составляют потоки, а потоки составляют компоненты. Сравнение деталей между двумя изображениями осуществляется посредством сравнения их релевантных параметров компонентов.
Предполагается, что каждый компонент имеет только одну точку отсчета (центр), которая отражает одну точку экстремума канала яркости.
Любой компонент содержит достаточный набор параметров, который характеризует его релевантную деталь:
– форму (включая характеристики распределения яркости);
– размер;
– положение;
– ориентацию; и
– распределение яркости его пикселей и т.д.
Для лучшей точности и для более широких возможностей распознавания, здесь вводятся некоторые меньшие градиентоподобные составляющие компонентов – потоки. Таким образом, предполагается, что компоненты представляют собой нетривиальные части параметризации изображения, и они могут быть разделены на свои более мелкие тривиальные части. Любой поток содержит достаточный набор параметров, который характеризует его релевантную часть тривиальной детали. Параметры потоков составляют параметры их компонента. Поток может принадлежать нескольким соседним компонентам (объединяя центры компонентов).
Изображение также может быть представлено как набор объектов, и любая параметризация объекта характеризуется как уникальная комбинация (группирование) соответствующих компонентов, и эти компоненты – как уникальные комбинации их составляющих элементов.
Поскольку детали на изображении могут иметь различные размеры и значимость, а некоторые из них могут создавать объекты с различными формами и размерами, для улучшенной работы и распознавания обнаружение объектов и параметризация осуществляются посредством пирамиды масштабирования. Пирамида состоит из уровней масштабирования. Каждый уровень характеризует разделение объектов на их наименьшие (для текущего уровня) нетривиальные части. Такие маленькие части, в свою очередь, могут быть разделены на свои меньшие нетривиальные части на нижнем уровне пирамиды, и т.д.
Группирование компонентов данного уровня в компоненты следующего уровня определяется посредством соединения элементов соседних компонентов.
Эти и другие цели настоящего изобретения станут очевидными специалисту в данной области после прочтения следующего подробного описания предпочтительных вариантов осуществления.
Следует понимать, что как вышеуказанное общее описание, так и следующее подробное описание являются примерными и предназначены для предоставления дополнительного пояснения заявленного изобретения.
КРАТКОЕ ОПИСАНИЕ ГРАФИЧЕСКИХ МАТЕРИАЛОВ
Приложенные графические материалы представлены для обеспечения лучшего понимания настоящего изобретения, включены в данное описание и составляют его часть. Графические материалы изображают варианты осуществления настоящего изобретения и, вместе с описанием, служат для объяснения принципов настоящего изобретения. На графических материалах:
фиг.1A представляет собой блок-схему, изображающую способ обработки видео и изображений с высоким динамическим разрешением согласно одному варианту осуществления настоящего изобретения;
фиг.1 В представляет собой блок-схему, изображающую способ обработки видео и изображений с высоким динамическим разрешением согласно одному варианту осуществления настоящего изобретения; и
фиг.2 представляет собой блок-схему, изображающую способ выравнивания сравнения компонентов согласно одному варианту осуществления настоящего изобретения.
ОПИСАНИЕ ПРЕДПОЧТИТЕЛЬНЫХ ВАРИАНТОВ ОСУЩЕСТВЛЕНИЯ
Далее будет приведено подробное описание предпочтительных вариантов осуществления настоящего изобретения, примеры которых изображены в прилагаемых графических материалах. Где это возможно, одинаковые ссылочные позиции используются в графических материалах и описании для отсылки на такие же или подобные части.
Рассмотрим фиг.1A, которая представляет собой блок-схему, изображающую способ выравнивания для получения изображений с расширенным динамическим диапазоном согласно одному варианту осуществления настоящего изобретения.
Способ 10 начинается с этапа 11 путем поиска признаков (характерных элементов) в изображении. Далее, на этапе 12 способ продолжается этапом параметризации этих признаков. И этап 12 включает этап сравнения изображений с различным экспонированием путем сравнения признаков.
Рассмотрим фиг.1B, которая является блок-схемой, изображающей способ выравнивания для получения изображений с расширенным динамическим диапазоном согласно одному варианту осуществления настоящего изобретения.
Способ 50 начинается с этапа 100 путем обнаружения признаков в изображении.
С целью обнаружения деталей в изображении и получения некоторого параметрического представления о них (компонентов), к изображению применяются некоторые процедуры пространственной фильтрации. Фильтрация позволяет обнаруживать как можно больше полезной информации, и в то же время отбросить пространственно некоррелированные данные (такие как, например, шум). Параметры компонентов находят как отклики фильтров характеристик на детали изображения.
Во время фильтрации можно избежать классической фильтрации изображения с квадратным ядром, из-за хорошо известных проблем таких постоянно распределенных FIR фильтров с симметричной формой:
- Фильтр должен быть пространственно симметричным, так что он всегда имеет круговую симметрию для распределения своих элементов. Таким образом, этот фильтр может давать отклик только на размер деталей, и не всегда он осведомлен о форме. Поэтому для анализа деталей с произвольной формой должны использоваться фильтры различных размеров.
- Применение фильтра с фиксированной схемой обычно требует множество операций свертки, поэтому, чем больше апертура фильтра, тем больше количество перемножений требуется для каждого положения пикселя перед интегрированием. Поскольку для различных размеров деталей также требуется весь набор сверток с различными размерами апертур (чтобы проанализировать весь спектр размеров), количество вычислений вырастает в значительной мере.
- Потери данных возникают, поскольку любые формы и размеры подходящих апертур характеризуемых деталей не используются.
На этапе 200 осуществляется адаптивная фильтрация по форме с использованием пирамид масштабирования. Для данного алгоритма обнаружения элементов представляют фильтрацию с произвольной формой, который обнаруживает элементы путем подгонки заметных деталей с использованием фильтров с адаптируемой формой, чьи формы (и характерные размеры), в свою очередь, определяются самими деталями.
В настоящем изобретении канал яркости изображения рассматривается как квазистатическое потенциальное фазовое поле. Каждая деталь изображения имеет свое собственное уникальное локальное распределение потенциала как части поля.
На этапе 300 определяют траектории. С целью обнаружения и параметризации деталей первое потенциальное фазовое поле анализируют посредством квазидинамического поведения мнимой «заряженной пробной частицы», помещенной в любую точку (x,y) этого поля. Поведение частицы описывается здесь посредством одной уникальной траектории, образованной путем движения этой частицы вдоль мгновенного локального градиента в текущем положении (x,y) частицы в поле.
Анализ осуществляется как для положительных, так и для отрицательных зарядов частицы. Более темные области поля имеют отрицательные пространственные заряды, которые притягивают положительно заряженные частицы, и наоборот, яркие области поля имеют положительные пространственные заряды, которые притягивают отрицательно заряженные частицы. Более темные и более яркие области притяжения имеют свои соответствующие точки притяжения (или циклы), где усредненный градиент равен нулю. Анализируют любую траекторию посредством как положительных, так и отрицательных пробных частиц, помещенных последовательно в тех же исходных координатах (x,y) на фазовом поле и затем перемещенных вдоль мгновенного локального градиента поля. Для положительно заряженной частицы ее точка притяжения будет указана как точка (-) (темная точка), а для отрицательно заряженной частицы ее точка притяжения будет указана как точка (+) (яркая точка). Поскольку движение положительной и отрицательной частиц начинается с того же исходного положения (x,y), это движение создает траекторию, которая подобна «каналу электрического тока» между точками (+) и (-). Вот почему точки (+) и (-) траектории, соответственно, называются начальной и конечной точками. Начальная и конечная точки считаются значениями потенциала, и разница яркости между ними считается разностью потенциалов.
Для пространственной фильтрации анализируют только геометрию этого движения частицы. Ее скорость или ускорение могут использоваться в дальнейшем анализе как дополнительные параметры распознавания.
Как было описано выше, канал яркости (как потенциальное поле) является непрерывным на изображении, и его пространственные производные имеют конечные значения в любой точке, поэтому любая траектория является определяемой на поле и, если канал яркости имеет какую-то область с ненулевыми значениями градиента (которые могут рассматриваться как «деталь»), существует по меньшей мере одна траектория ненулевого размера, которая имеет свои устойчивые точки притяжения (включая точки на бесконечном расстоянии).
В вариантах осуществления настоящего изобретения существует несколько способов вычисления локального градиента, и некоторые из них обеспечивают траектории с устойчивым циклом. Для устойчивых циклов их центральные точки могут рассматриваться как устойчивые точки (т.е. окончания траекторий).
Для некоторых других способов может иметь место ситуация неопределенности, когда есть более чем одно возможное направление для перемещения частицы из текущего положения. В этом случае траектория может разветвляться с образованием нескольких новых траекторий, которые имеют несколько общих пикселей, при этом имеют различные начальную и/или конечную точки.
Абсолютное значение градиента не равняется нулю в любой из точек траектории, за исключением ее начальной и конечной точек, поэтому траектория всегда непрерывна на дискретном пространстве канала яркости.
Каждая конечная траектория, которая имеет обе устойчивые точки ((+) и (-)) внутри границ изображения и имеет длину больше чем некоторое значение минимальной длины, может использоваться для параметризации детали.
Под термином «траектория» используется уникальный непрерывный канал с двумя конечными точками ((+) и (-)) для перемещения «заряженной пробной частицы».
Траектории получают посредством поточечного перемещения в направлении наивысшего локального градиента. Локальный градиент может вычисляться для центрального пикселя в апертуре пикселей 3×3 (или в общем n×n).
На этапе 400 вычисляют диапазон характеристик для каждого компонента в изображении. Предположим, что все возможные траектории были построены для данного канала B (канал яркости некоторого изображения). Начальная и конечная точки этих траекторий становятся центрами компонентов. Если есть два компонента, которые имеют одну или более общих траекторий, тогда набор всех этих общих траекторий называется потоком. Потоки являются элементами, которые создают параметризацию компонента. Поток имеет свою начальную точку и конечную точку, полученные от составляющих его траекторий.
Таким образом, адаптивная фильтрация изображения по форме (SAIF) создается как процедура, где элементы определяются как потоки, образованные траекториями.
Компонент представляет собой область изображения, которая состоит из центрального пикселя, в котором функция B(x,y) яркости достигает экстремума, и из всех потоков изображения, которые имеют свои начальную или конечную точку в этом пикселе. Компоненты, которые соответствуют локальным минимумам функции B, называются темными компонентами. Иначе они называются светлыми компонентами.
Для каждого компонента в изображении вычисляется диапазон характеристик. В одном варианте осуществления настоящего изобретения реализация алгоритма содержит следующие характеристики:
· является ли компонент темным или светлым;
c
c
· яркость центра компонентов B (x, y);
· количество потоков;
· световой контраст между начальными и конечными точками потоков;
· площадь компонентов пикселях;
· для каждой траектории компонента: ее длина вычисляется, например, как сумма расстояний между каждыми двумя соседними пикселями траектории, так что для пикселей с одинаковыми координатами x или y расстояние равно 1, а в других случаях оно равняется √(2);
· для каждого потока: его длина вычисляется, например, как среднеквадратичное значение содержащихся траекторий;
· для каждого потока: его «вектор» как направленный отрезок линии со своими начальной и конечной точками, соответственно, совпадающими с начальной и конечной точками потока;
· для каждого потока: его извилистость как отношение, полученное, когда его длина поделена на длину его вектора; и
· для каждых двух соседних потоков компонента: угол между их векторами.
В других вариантах осуществления также используются и другие характеристики.
Описанный набор характеристик может служить для сравнения компонентов между изображениями с различным экспонированием для нахождения соответствующих элементов изображений. Особое свойство характеристик заключается в том, что они являются инвариантными для любого смещения и вращения одного изображения относительно другого, что делает возможным их использование для выравнивания изображений с целью устранения недостатков при создании HDR изображения. Если найдено по меньшей мере две пары компонентов, легко можно вычислить угол и смещение для выравнивания.
Пример пирамиды на основе классического фильтра с ядром Гаусса представляет собой так называемую пирамиду Гаусса. Канал B взят как ее нулевой уровень. При заданном уровне k уровень k+1 формируют следующим образом: фильтр Гаусса с постоянным радиусом r применяют к пикселям изображения k-уровня с шагом r+1. Например, фильтр 3×3 применяют к каждому второму пикселю. Ядро Гаусса задается функцией:
(1)
В данной реализации параметры задают как σ=1, μ=0.
Результирующие значения образуют изображение с , , которое становится уровнем с номером k+1.
min
min
Создание новых уровней продолжается, пока ширина и высота наивысших уровней больше, чем некоторые установленные значения ширина, высота.
В другом варианте осуществления настоящего изобретения в другой версии реализации алгоритма используется тип пирамиды, в которой элементы нижнего уровня (компоненты, потоки, траектории) берут как основание для создания элементов более высоких уровней.
В таком варианте осуществления пиксель считается тривиальным компонентом, который состоит только из своей центральной точки и не содержит потоков ненулевой длины, и канал B оригинального изображения берут как нулевой уровень пирамиды.
Алгоритм создания траекторий, описанный выше, используется для создания элементов первого уровня. Следовательно, согласно определенным терминам, мнимая частица, которая чертит траектории 1-го уровня, движется от одного компонента нулевого уровня к другому последовательно по закону, полученному из относительной яркости соседних компонентов. Траектории уровней k=2...N следует создавать аналогично. Каждая из траекторий (k+1)-уровня содержит компоненты k-го уровня, как их соединения, а также их начальные и конечные точки.
Компоненты, которые имеют общие потоки, называются соседними компонентами.
Процесс создания траекторий на более высоких уровнях требует способа определения направления движения мнимых частиц, аналогично оценке градиента на нулевом уровне.
o
1
K
s
1
K
o
s
o
B
D
D
B
D
D
B
B
B
Например, можно использовать следующий способ: предположить, что отрицательно заряженная частица задана как светлый компонент U, который очевидно имеет только темные соседние компоненты U... U. Тогда компонент, к которому частица движется на следующем этапе, является самым светлым компонентом U, среди всех светлых компонентов, соседствующих с U…U компонентами, кроме U, и только в случае, если U светлее U (относительно средней яркости). Чтобы найти такой компонент, требуется функция оценки средней яркости компонентов.
s
l
s
B
D
B
Такая функция, например, может вычислять среднюю яркость компонента как среднее значение всех пикселей, которые составляют компонент, или как среднее значение средней яркости всех потоков. Таким образом, частица переносится на U, а темный компонент U,l ∈1…K, соседствующий с U, добавляется к текущей траектории как соединение.
s
l
B
D
В случае наличия более одного возможного выбора U и/или U, траектория будет разветвляться.
Положительно заряженная частица будет перемещаться от светлого компонент к самому темному из своих соседних компонентов.
В случае, когда начальный компонент является темным, выбор направления перемещения частиц осуществляется симметрично.
Как только траектория остановится на одном из компонентов k-1 уровней, центр этого компонента становится центром нового компонента k уровней. Поскольку новая траектория уровня k состоит из нескольких траекторий k-1 уровня, связанных вместе, его длина может быть вычислена как сумма длин этих траекторий. Характеристики других элементов также могут быть вычислены аналогично предыдущему уровню.
Каждый уровень компонентов пирамиды может создаваться и использоваться для сравнения соответствующих уровней различных изображений. Таким образом, на каждом уровне можно найти угол и смещение для выравнивания.
Чем выше показатель уровня, тем более грубой является эта оценка. С другой стороны, основной уровень зачастую имеет шумы, что пагубно может отразиться на точности. Поэтому следует учитывать все уровни, чтобы выполнить выравнивание с наилучшей возможной точностью.
1
2
Любая пара компонентов сама по себе предоставляет свои значения угла и смещения одного изображения относительно другого. Предположим компоненты U и U соединены. Затем расстояние между их центрами задает смещение, а угол между их соответствующими потоками задает угол вращения. Когда все возможные пары компонентов найдены на текущем уровне, требуется специальный алгоритм для усреднения углов и смещений, задаваемых ими.
k
k
k
k
k
k
Предположим алгоритм выдал значения (dx, dy) смещения и α для угла вращения после процесса усреднения на уровне k. Затем после перехода вниз на уровень k-1, для каждых двух компонентов, которые, как предполагается, связаны, значения смещения и угла вращения, который они задают, не должны сильно отличаться от значений (dx, dy) и α. Иначе пара должна быть исключена.
На этапе 500 характеристики спаренных компонентов сравниваются для выбора или исключения пары. Эффективный алгоритм сравнения компонентов определяет одну из ключевых проблем для выравнивания.
Способ выравнивания сравнения компонентов согласно настоящему изобретению включает следующие этапы, изображенные на фиг.2.
Этап 1. Первичный выбор пар
На этапе 1 зачастую образуется большое количество пар, большинство из которых может быть исключено на дальнейших этапах.
Сравнение на данном этапе основано на оценке разницы основных характеристик компонентов. Каждая характеристика может иметь свою отдельную функцию для оценки разницы.
1
2
1i
1
2j
2
1i
2j
Предположим, сравниваются изображения I и I. Каждый компонент u изображения I сравнивается с каждым компонентом u изображения I, если оба компонента u и u являются темными или оба являются светлыми.
Первая проверка использует такие параметры как квадратура и количество потоков. Если параметры отличаются на большую величину, то пара исключается.
11
1 N1
1i
21…
2 N2
2j
Предположим S…S все являются потоками, которые принадлежат u и SS - являются потоками u.
1i
2j
1 n1
2 n2
knk
n
kn
Для каждого u и u выбирается «характеризующий» поток, чтобы начать сравнение с него. Например, могут быть взяты потоки S, S с максимальной извилистостью: E(S)=max E(S).
2
j
1 i
Центры компонентов совмещают, и u вращают относительно u, пока выбранные потоки не совпадут.
kn
kn
Для каждого потока S угол α представлен между ним и характеризующим потоком компонента при вращении по часовой стрелке.
Наиболее интересные параметры выбирают для сравнения потоков. В варианте осуществления настоящего изобретения используют извилистость потоков, длину и длину векторов.
1
1
2
2
1n
2m|
∈
Затем осуществляется итерация над потоками, по часовой стрелке или против часовой стрелки. Начиная с первых совпадающих потоков Sn и Sn, каждая пара потоков, между которыми имеется угол │(α−α)│ меньший, чем предопределенный α, значения, характеризующие совпадение выбранных параметров, вычисляют и сохраняют в памяти. Такие значения могут представлять собой отношение таких параметров, при условии, что знаменатель отличается от 0.
∈
Если α – окрестность потока одного из компонентов не содержит какого-либо потока другого компонента, тогда сохраняют значение, соответствующее минимальному возможному сходству по каждому из параметров. После окончания всех итераций над потоками сохраненные значения усредняют, и результат отражает сходство компонентов.
1
n1
2
n2
1
n1
2
n2
Могут быть различные способы выбора первых характеризующих потоков S, S для сравнения. Описанный алгоритм согласно настоящему изобретению может повторяться несколько раз с различным выбором S, S, и вариант с максимальным результирующим значением сходства может быть использован для определения того, стоит ли соединять компоненты или нет.
1
i
2
j
Каждая пара u, u, которая прошла этапы, описанные выше, может затем проверяться с помощью некоторых дополнительных параметров, например, разницы яркости между окончаниями совпадающих потоков не должны сильно расходиться.
Этап 2. Выбор на основе статистического подхода.
1…
N
i
i
i
i
Второй этап работает с набором пар pp, собранных на этапе 1, и учитывает случайные переменные: угол α и смещения dx и dy вдоль двух осей изображения. Их средние значения соответствуют целевым параметрам выравнивания. α, dx и dy, предоставленные парой p, могут быть рассмотрены как i-е измерение этих переменных.
Следовательно, доступно N измерений. На практике N зачастую является достаточно большим для оценки целевых переменных. Посредством N измерений можно создать графики распределения случайных переменных. Этот график может быть построен в виде гистограммы со значениями случайных переменных на оси абсцисс и количеством измерений, которые попадают в каждый из интервалов, на оси ординат. Если гистограмма достигает отличительного максимума в некоторой точке, то этот максимум отражает среднее значение соответствующей случайной переменной. Таким образом на данном этапе все пары, которые попадают далеко от этого максимума, исключаются.
В общем случае, наборы пар, задаваемые каждой из трех гистограмм, различны; таким образом, пересечение этих наборов может быть взято как результирующий набор пар. На практике этот набор обычно не пустой и достаточно большой для осуществления выравнивания, при условии, что значительное количество пар было получено на этапе 1.
Этап 3. Кластерный анализ
В случаях, когда количество пар компонентов, образованное на этапе 1, невелико (например, приблизительно 30 или меньше), вместо статистического анализа (или наряду с ним) может быть выполнен кластерный анализ. Компоненты попарно упорядочены (первый – это компонент ключевого изображения, а второй – это изображение, которое необходимо выровнять). Процесс выравнивания, когда центры компонентов второго изображения устанавливают в центры компонентов первого изображения, можно представить как перемещение. Цель заключается в нахождении максимального поднабора в наборе всех пар, так что все компоненты этого поднабора, которые идут вторыми в своей паре, перемещаются вместе как твердое тело. Все пары за пределами этого поднабора исключаются из процесса выравнивания. С целью поиска описанного поднабора могут быть использованы различные подходы. Например, все центры потенциального поднабора можно связать отрезками прямых. Следовательно, можно увидеть, не изменяются ли длины этих отрезков и углы между ними во время перемещения (или изменения являются минимальными). С использованием этих критериев пары могут быть исключены по одной, и можно оценить, на сколько изменяются длины и углы в процессе перемещения оставшихся пар. Таким образом, пара, исключение которой ведет к наилучшему результату, может быть найдена и исключена, а затем процедура может повторяться с оставшимися парами.
Этап 4. Вычисление параметров выравнивания (угол вращения и смещение).
Пары, выбранные на предыдущих этапах, используют для аппроксимации угла и смещения.
Углы между соответствующими потоками соединенных компонентов больше не используются для оценки целевого угла. Интерес представляют координаты (x,y) центров компонентов, и используется алгоритм, который вычисляет такой угол и смещение выравнивания изображения (не принимая в расчет возможные оптические искажения), которые обеспечивают наименьшее среднеквадратичное изменение всех соединенных координат центров компонентов.
Таким образом получают первую аппроксимацию параметров выравнивания.
Этап 5. Дополнительная коррекция оценки параметров.
Зачастую требуется некоторая дополнительная коррекция значений угла и смещения. Для этой цели пары компонентов, которые были исключены на этапе 2, снова принимают к рассмотрению. Затем те пары, которые задают угол и смещение достаточно близкие к парам полученным позднее, добавляют к конечному набору пар для выравнивания. Затем вычисления повторяют с участием центров полученных пар.
Специалисту в данной области будет понятно, что различные модификации и изменения могут быть внесены в настоящее изобретение без отступления от объема или сущности настоящего изобретения. В виду вышеуказанного предполагается, что настоящее изобретение охватывает модификации и изменения настоящего изобретения, которые подпадают под объем настоящего изобретения и его эквивалентов.