способ формирования составного изображения

Формула изобретения

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

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

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

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

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

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

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

3. Способ по п.1, отличающийся тем, что дескрипторы точек совмещения являются инвариантными к масштабу и вращению.

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

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

Описание изобретения к патенту

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

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

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

Из уровня техники известны различные способы получения изображения, в которых процесс выравнивания основан на совмещении особых (характерных) точек. Среди них есть способы, основанные на перекрестной корреляции участков со сходной яркостью. Эти способы не являются инвариантными по отношению к масштабированию и вращению исходных (входящих) изображений. Помимо этого предлагалось использование различных типов инвариантов, например инвариант Нu и инвариант Flusser (см. J.Flusser and В.Zitová, "Combined invariants to linear filtering and rotation," Intl. J. Pattern Recognition Art. Intell., Vol.13, pp.1123-1136, 1999) [1]. Однако самым надежным способом, основанным на инвариантных характеристиках, является метод Lowe (см. Lowe, David G. (1999). "Object recognition from local scale-invariant features". Proceedings of the International Conference on Computer Vision 2: 1150-1157 [2]). Описанные в данном способе преобразования являются геометрически инвариантными как в случае преобразования подобия, так и в случае аффинных преобразований по яркости.

Изобретение, описанное в патенте США № 6097418 [3], устраняет артефакты в изображении, скомпонованном из множества исходных элементов. Различимые швы в изображении удаляются путем рандомизации точки стыка между строками сканирования, порожденными каждым из источников изображения. Рандомизация может быть оптимизирована путем применения способа перемещения случайной точки сшивки, основанного на содержании строки сканирования, смежных строк сканирования, и на других критериях. В этом изобретении решена также проблема компенсации ошибок сканирования, вызванных термальными факторами, десинхронизацией барабана, механическим смещением и другими факторами, связанными с использованием нескольких систем формирования изображения. Система фотодатчиков, включающая маску с парой отверстий треугольной формы, позволяет замерять ошибки внутри сканера.

В патенте США № 7271822 [4] описаны системы и способы для сшивки множества изображений в принтере для формирования единого, бесшовного составного изображения. Использование нескольких лазерных источников и нескольких сканирующих линз с одним или более сканирующих устройств и различными методами сшивки изображений позволяет добиться значительно более качественного составного изображения, чем при использовании принтеров с одним источником лазерного излучения и одной линзой сканирования. Такие преимущества состоят, например, в более широком формате изображения, меньшей зернистости, низкой стоимости и уменьшенном общем размере принтера.

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

В патентах США № 6754379 [6] и № 6359617 [7] и в докладе Y.Xiong и К.Turkowski. "Registration, Calibration, and Blending in Creating High Quality Panoramas". 4th IEEE Workshop on Applications of Computer Vision. October, 1998 [8] предлагается способ выравнивания прямолинейных изображений в трехмерные посредством проекционной записи и калибровки. Сначала изображения записывают проекционным методом с использованием оптимизации на градиентной основе и линейного поиска на основе корреляции. На втором этапе калибруют внутренние и внешние параметры каждого изображения, используя глобальную оптимизацию. Это значительно уменьшает общие несоответствия изображения на всех участках наложения (перекрытия). На третьем этапе изображения объединяются с применением метода построения пирамид Лапласа и с использованием маски объединения, сформированной с помощью преобразования расстояний (distance transform). Таким образом, обеспечивается плавный переход (стык) между изображениями и устраняются незначительные последствия неправильного выравнивания, вызванного явлениями параллакса или некорректным парным совмещением. Этот подход наиболее близок к заявляемому изобретению.

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

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

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

- Анализируют входные изображения, выявляют точки совмещения (особые точки) и определяют дескрипторы точек совмещения;

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

- Выбирают опорное изображение;

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

- Объединяют один за другим изображения в составное (мозаичное) изображение, используя восстановленные параметры вращения/смещения.

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

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

Далее сущность заявляемого изобретения поясняется в деталях с привлечением графических материалов.

Фиг.1. Схема основных компонентов системы.

Фиг.2. Основные этапы формирования мозаики изображения.

Фиг.3. Иллюстрация процесса совмещения дескрипторов с выходным изображением и восстановления параметров вращения/смещения (этап 203).

Фиг.4. Пример таблиц, поясняющий процесс выбора следующего изображения для процедуры объединения.

Фиг.5. Иллюстрация процесса поочередного объединения изображений с использованием восстановленных параметров вращения/смещения (этап 204).

Фиг.6. Примеры, а именно вид 6.1 - Маска объединения, сформированная на этапе 405; вид 6.2 - Обновленная маска объединения, рассчитанная на этапе 407; вид 6.3 - Изображение различий пикселей в пределах перекрывающегося участка с оптимальным швом (помечен светлой кривой линией).

Фиг.1 показывает схему основных компонентов системы, реализующей заявляемый способ. Процесс функционирования устройства управляется процессором 101, который выполняет программный код, хранящийся в памяти 102. В памяти 102 хранятся исходные черно-белые или цветные фотографии. Изображение обрабатывается и поступает на дисплей 104. Обмен данными осуществляется через шину 106.

Фиг.2 иллюстрирует процесс формирования мозаики из набора частично перекрывающихся изображений. На этапе 201 изображения подвергаются анализу, переформатируются к предопределенному размеру, а также выявляются особые точки, т.е. точки совмещения. Для каждой такой точки рассчитывают дескриптор. Это можно выполнить различными методами, описанными в литературе. Например, можно использовать Scale-Invariant Feature Transform (SIFT) (см. [2]). Затем на этапе 202 совмещают особые точки для каждой пары изображений из исходного (входящего) набора. Число правильно подобранных точек сохраняется в таблице. На этапе 203 особые точки каждого изображения сопоставляют с выходным изображением (подробности этого этапа поясняются далее), при этом получающиеся аффинные модели преобразования изображения (параметры вращения/смещения) сохраняют в памяти. После этого изображения одно за другим присоединяют к заключительному изображению (подробности этого этапа приведены далее). Это является заключительным этапом заявляемого способа.

На этапе 202 особые точки совмещают в каждой паре изображений из исходного (входного) набора. Степень соответствия между двумя совместимыми точками определяется суммой квадратов разностей компонентов соответствующих дескрипторов. Формируется квадратная матрица со всеми возможными разностями дескрипторных пар. Для каждой строки определяют минимальное значение и отмечают его. Для каждой колонки определяют минимальное значение и отмечают его. Пары, в которых такие отметки совпадают, рассматриваются как совместимые пары. Затем параметры вращения/смещения между парами восстанавливают и с помощью метода RANdom SAmple Consensus (RANSAC) удаляются выбросы (outliers), т.е. те точки, которые не удовлетворяют найденным параметрам вращения/смещения.

RANSAC - это алгоритм для оценки параметров математической модели по ряду наблюдаемых данных, в котором содержатся излишние пары, или выбросы (см. [1]). RANSAC многократно выбирает случайное подмножество точек исходных данных. Модель адаптирована к тому, чтобы для тех точек, которые являются гипотетическими «адекватными точками» (inliers), генерировать, так называемые, «предсказанные» данные. Эти «предсказанные» данные затем сравнивают с «взвешенными» данными. Если точка хорошо подходит, ее рассматривают как гипотетическую «адекватную точку» (inlier). Если достаточно много точек классифицированы как гипотетический inliers по отношению к предполагаемой модели, то эта модель является относительно приемлемой. Тогда такую процедуру повторяют фиксированное число раз, каждый раз получая либо модель, которая отклоняется потому, что слишком малое число точек были классифицированы как inliers, либо получая улучшенную модель вместе с соответствующими данными (весом) о погрешности. В последнем случае сохраняют улучшенную модель, если присущая ей погрешность меньше, чем у ранее сохраненной модели.

Фиг.3 иллюстрирует этап 203, на котором подбирается модель соответствия выходному (конечному) изображению. На этапе 301 выбирают первое (опорное) изображение (детали такого выбора приведены далее), которое без изменений копируется в выходное изображение. Затем выполняют очередную процедуру до тех пор, пока не останется ни одного необработанного изображения. Выбирают следующее изображение для объединения (этап 302). Процесс отбора очередного изображения иллюстрирован далее. На этапе 303 вычисляют ограничивающий прямоугольник для приблизительного размещения очередного изображения на выходном изображении. Затем в целях повышения точности совмещения отбирают лишь те точки, которые лежат в пределах вычисленного ограничивающего прямоугольника. На этапе 304 метод RANSAC используется для вычисления параметров вращения/смещения очередного изображения относительно выходного (конечного) изображения. На этапе 305 параметры вращения/смещения сохраняют в памяти. Корректируют размер выходного изображения с тем, чтобы он был равен ограничивающему прямоугольнику конечного изображения с только что подсоединенным изображением. Особые точки выходного изображения дополняют особыми точками только что подсоединенного изображения, к которым предварительно применяют найденную модель вращения/смещения. Выполнение метода завершают, когда не остается никаких необработанных изображений (условие 306).

Фиг.4 иллюстрирует повторяющийся процесс выбора очередного изображения для подсоединения. В данном примере число исходных (входящих) изображений равно семи. При попарном сравнении изображений получена таблица размером 7×7 (таблица 1). Эта таблица является симметричной; при этом указанные в ней цифры представляют собой число совмещаемых между изображениями точек. Первая строка (ряд) и первая колонка содержат индексы входных изображений. Первое (опорное) изображение отбирают (этап 301), суммируя цифры в рядах таблицы и выбирая ряд с максимальной суммой. Это изображение копируют на конечное изображение без изменений. Затем выбирают следующее изображение (этап 303). Для этой цели формируют таблицу с цифрами, отражающими количество совмещаемых точек в объединенных/не объединенных изображениях (для иллюстрации см. таблицы 2-7). Первая строка (ряд) в таких таблицах содержит входные индексы необъединенных изображений. Первая колонка в таких таблицах содержит входные индексы уже объединенных изображений. В таблице выбирают максимальное значение, и индекс следующего изображения устанавливают равным номеру колонки, в которой найдено максимальное значение. В качестве иллюстрации здесь приведены четыре таких таблицы, и изображение, где порядок объединения изображений таков: 6, 4, 2, 1, 5, 3.

Фиг.5 иллюстрирует этап 204, где изображения объединены с опорным изображением с использованием аффинных моделей. Сначала формируют конечное (выходное) изображение на основе заранее рассчитанного размера изображения, и опорное изображение копируют в него без изменений. На этапе 402 таким же путем, как и на этапе 302, отбирают очередное изображение. Отобранное изображение деформируют, используя параметры вращения/смещения, сохраненные на этапе 305. Затем вычисляют координаты перекрывающегося участка. Пиксели, которые не принадлежат перекрывающемуся участку, копируют в выходное (конечное) изображение (этап 404). На этапе 405 формируют маску объединения. Эта маска представляет собой изображение, выполненное в трех цветах (оттенках): черном, сером и белом. Черный цвет соответствует пикселям выходного (конечного) изображения, белый цвет соответствует очередному объединенному изображению, а серый цвет соответствует пикселям, назначение которых является пока неопределенным (для иллюстрации см. Фиг.6, панель 6.1). Участок шириной в N пикселей около краев маски объединения имеет черный или белый цвет в зависимости от тех краев изображения, которые соответствуют краям маски объединения: если края выходного (конечного) изображения совпадают с краями маски объединения, то цвет - черный; если края очередного объединяемого изображения совпадают с краями маски объединения, то цвет - белый. На тех участках, где маска перекрытия серого цвета, вычисляют оптимальный шов (этап 406): траектория, проходящая через множество пиксельных разностей, которые в сумме дают минимальную стоимость.

Фиг.6, панель 6.3, иллюстрирует возможный вариант оптимального шва перекрытия (отмечен светлой кривой линией). После этого маску объединения обновляют (этап 407): на одной стороне оптимального шва маска объединения окрашена в белый цвет, на другой стороне она окрашена в черный цвет. После этой процедуры маска объединения имеет только два цвета - черный и белый. Это показано на Фиг.6, панель 6.2. На этапе 408 изображения внутри перекрывающегося участка объединяют каким-либо известным из уровня техники способом, например способом, описанным в [3]. Описанная процедура выполняется для всех изображений, за исключением опорного изображения. На этапе 409 проверяют, есть ли еще необработанные изображения. Если ответ положительный, процедуру повторяют, в ином случае - выполнение способа завершают.

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

Заявляемый способ предназначен для реализации в программном обеспечении для планшетных сканеров, слайд-сканеров, МФУ и других подобных устройств.