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

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

Иллюстрации

Показать все

Реферат

ОБЛАСТЬ ТЕХНИКИ

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

УРОВЕНЬ ТЕХНИКИ

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

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

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

РАСКРЫТИЕ ИЗОБРЕТЕНИЯ

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

КРАТКОЕ ОПИСАНИЕ ЧЕРТЕЖЕЙ

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

На Фиг. 2A-D показаны два типа переносных устройств, предназначенных для получения изображений.

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

На Фиг. 4 показано типовое изображение с цифровым кодированием.

На Фиг. 5 показан один вариант цветовой модели RGB.

На Фиг. 6 показана другая цветовая модель «Оттенок-насыщенность-светлота» (HSL).

На Фиг. 7 показано формирование полутонового или бинаризованного изображения из цветного изображения.

На Фиг. 8A-N показаны модели, которые описывают преобразования первого изображения документа во второе изображение документа и способ выбора конкретной модели из множества моделей-кандидатов для описания конкретного преобразования для двух соответствующих изображений документа.

На Фиг. 9А-В показаны два документа, используемые в качестве примеров при обсуждении раскрываемых в настоящем описании способов и подсистем.

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

На Фиг. 11A-F показан один подход к установлению соответствия между точками в глобальной системе координат и соответствующими точками в плоскости изображения камеры.

На Фиг. 12 показано выявление признаков методом SIFT.

Фиг. 13-18 содержат справочную информацию по различным концепциям, используемым методом SIFT для выявления признаков в изображениях.

На Фиг. 19A-D показан выбор кандидатов на ключевые точки в изображении.

На Фиг. 19Е показана фильтрация кандидатов на ключевые точки, или признаков, в пирамиде разностей гауссианов, полученных методом SIFT.

На Фиг. 19F показано, как назначается величина и ориентация признака из значений в пирамиде разностей гауссианов.

На Фиг. 19G показано вычисление дескриптора признака.

На Фиг. 19H-I показано простое приложение преобразования Хафа с одним параметром.

На Фиг. 19J-K показано использование точек SIFT для распознавания объектов в изображениях.

На Фиг. 20A-N представлен обзор способов и систем, к которым относится настоящий документ, а также подробное описание создания модели документа в соответствии со способами и системами настоящего изобретения.

На Фиг. 21A-D показаны блок-схемы процедуры «найти документы» (find documents), которая выявляет содержащие документ фрагменты в исходном изображении, как уже обсуждалось ранее со ссылкой на Фиг. 20А.

ОПИСАНИЕ ПРЕДПОЧТИТЕЛЬНЫХ ВАРИАНТОВ РЕАЛИЗАЦИИ

Настоящий документ относится к способам и подсистемам, которые выявляют и характеризуют содержащие документ фрагменты изображений в содержащем документ изображении. Приведенное ниже обсуждение разбито на несколько подразделов, в том числе: (1) Обзор архитектуры вычислительных систем и цифровых изображений; (2) Пример способа выбора с использованием модели, похожей на RANSAC; (3) Область рассматриваемых проблем и несколько примеров типов документов; (4) Преобразования перспективы; (5) Детекторы признаков; и (6) заключительный подраздел, в котором обсуждаются способы и подсистемы, рассматриваемые в настоящем документе.

Обзор архитектуры вычислительных систем и цифровых изображений

На Фиг. 1 представлена схема архитектуры вычислительной системы верхнего уровня, подобной той вычислительной системе, в которой реализована раскрываемая в этом документе подсистема распознавания содержащих документ фрагментов изображения. Мобильные устройства получения изображений, включая смартфоны и цифровые камеры, могут быть изображены на диаграмме аналогичным образом, а также могут содержать процессоры, память и внутренние шины. Тем, кто знаком с современной наукой и технологиями, будет понятно, что программа управления или подпрограмма управления, включающая машинные команды, которые хранятся в физической памяти устройства с процессорным управлением, представляют собой компонент управления данным устройством и являются столь же физическими, реальными и важными, как и любой другой компонент электромеханического устройства, включая устройства формирования изображений. Компьютерная система содержит один или более центральных процессоров (ЦП) 102-105, один или более электронных модулей памяти 108, взаимосвязанных с ЦП через шину подсистемы ЦП/память 110 или несколько шин, первый мост 112, который соединяет шину подсистемы ЦП/память 110 с дополнительными шинами 114 и 116, либо другие виды средств высокоскоростного соединения, в том числе несколько высокоскоростных последовательных соединений. Эти шины или последовательные межсоединения в свою очередь соединяют ЦП и память со специализированными процессорами, такими как графический процессор 118, и с одним или более мостами 120, которые соединены по высокоскоростным последовательным каналам или несколькими контроллерами 122-127, такими как контроллер 127, которые предоставляют доступ к различным типам запоминающих устройств большой емкости 128, электронных дисплеев, устройств ввода и прочих подобных компонентов, подкомпонентов и вычислительных ресурсов.

На Фиг. 2A-D показаны два типа переносных устройств, предназначенных для получения изображений. На Фиг. 2А-С показана цифровая камера 202. Цифровая камера содержит объектив 204, кнопку спуска затвора 205, нажатие которой пользователем приводит к получению цифрового изображения, которое соответствует отраженному свету, попадающему в объектив 204 цифровой камеры. В задней части цифровой камеры, которая видна пользователю, когда он держит камеру при съемке цифровых изображений, имеются видоискатель 206 и жидкокристаллический дисплей видоискателя 208. С помощью видоискателя 206 пользователь может напрямую просматривать создаваемое объективом 204 камеры изображение, а с помощью жидкокристаллического (ЖК) дисплея 208 - просматривать электронное отображение создаваемого в настоящей момент объективом изображения. Обычно пользователь камеры настраивает фокус камеры с помощью кольца фокусировки 210, смотря при этом через видоискатель 206 или на жидкокристаллический экран видоискателя 208, чтобы выбрать требуемое изображение перед тем, как нажать на кнопку 205 спуска затвора для получения цифрового снимка изображения и его сохранения в электронной памяти цифровой камеры.

На Фиг. 2D показан типичный смартфон с передней стороны 220 и задней стороны 222. На задней стороне 222 имеется объектив 224 цифровой камеры и датчик приближения и (или) цифровой экспонометр 226. На передней стороне смартфона 220 может отображаться получаемое изображение 226 (под управлением приложения), аналогично работе жидкокристаллического дисплея 208 видоискателя цифровой камеры, а также может находиться сенсорная кнопка 228 спуска затвора, при прикосновении к которой происходит получение цифрового изображения и сохранение его в памяти смартфона.

На Фиг. 3 показаны обычный настольный сканер и персональный компьютер, которые используются совместно для преобразования печатных документов в электронные документы, которые можно хранить в запоминающих устройствах большой емкости и (или) в электронной памяти. В настольном сканере 302 имеется прозрачное стекло планшета 304, на которое помещен документ 306 лицевой стороной вниз. Запуск сканирования приводит к получению оцифрованного изображения отсканированного документа, которое можно передать на персональный компьютер (ПК) 308 для хранения на запоминающем устройстве большой емкости. Программа визуализации изображения сканируемого документа может отобразить оцифрованное отсканированное изображение документа для отображения на экране 310 устройства отображения 312 ПК. Настольный сканер обеспечивает более стабильную и точную платформу для получения изображения документа, чем переносное устройство, но он также может формировать изображения документа, в которых имеются проблемы контраста, искажения и другие дефекты.

На Фиг. 4 показано типовое изображение с цифровым кодированием. Кодированное изображение включает двухмерный массив пикселей 402. На Фиг. 4 каждый небольшой квадрат, например, квадрат 404, является пикселем, который обычно определяется как наименьшая часть детализации изображения, для которой предусматривается цифровая кодировка. Каждый пиксель представляет собой место, обычно представленное как пара цифровых значений, соответствующих значениям на осях прямоугольных координат x и y (406 и 408, соответственно). Таким образом, например, пиксель 404 имеет координаты x, y (39,0), а пиксель 412 имеет координаты (0,0). В цифровой кодировке пиксель представлен числовыми значениями, указывающими на то, как область изображения, соответствующая пикселю, представляется при печати, отображается на экране компьютера или ином дисплее. Обычно для черно-белых изображений для представления каждого пикселя используется единичное значение в интервале от 0 до 255 с числовым значением, соответствующим уровню серого, с которым отображается этот пиксель. Согласно общепринятому правилу значение «0» соответствует черному цвету, а значение «255» - белому. Для цветных изображений может применяться множество различных наборов числовых значений, указывающих на цвет. В одной широко используемой цветовой модели, показанной на Фиг. 4, каждый пиксель связан с тремя значениями, или координатами (r, g, b), которые указывают на яркость красного, зеленого и синего компонента цвета, отображаемого в соответствующей пикселю области.

На Фиг. 5 показан один вариант цветовой модели RGB. Тремя координатами основных цветов (r,g,b) представлен весь спектр цветов, как было показано выше со ссылкой на Фиг. 4. Цветовая модель может считаться соответствующей точкам в пределах единичного куба 502, в котором трехмерное цветовое пространство определяется тремя осями координат: (1) r 504; (2) g 506; и (3) b 508. Таким образом, координаты отдельного цвета находятся в диапазоне от 0 до 1 по каждой из трех цветовых осей. Например, чистый синий цвет максимально возможной яркости соответствует точке 510 по оси b с координатами (0,0,1). Белый цвет соответствует точке 512 с координатами (1,1,1,), а черный цвет - точке 514, началу системы координат с координатами (0,0,0).

На Фиг. 6 показана другая цветовая модель «Оттенок-насыщенность-светлота» (HSL). В этой цветовой модели цвета содержатся в трехмерной бипирамидальной призме 600, имеющей шестигранное сечение. Оттенок (h) связан с доминантной длиной волны излучения света, воспринимаемого наблюдателем. Значение оттенка изменяется от 0° до 360°, начиная с красного 602 при 0°, проходит через зеленый 604 при 120°, синий 606 при 240°, и заканчивается красным 602 при 360°. Насыщенность (s), изменяющаяся в интервале от 0 до 1, обратно связана с количеством белого и черного цвета, смешанного при определенной длине волны или оттенке. Например, чистый красный цвет 602 полностью насыщен при насыщенности s=1,0, в то время как розовый цвет имеет значение насыщенности меньше 1,0, но больше 0,0, белый цвет 608 является полностью ненасыщенным, для него s=0,0, а черный цвет 610 также является полностью ненасыщенным, для него s=0,0. Полностью насыщенные цвета располагаются по периметру среднего шестигранника, содержащего точки 602, 604 и 606. Шкала оттенков серого проходит от черного 610 до белого 608 по центральной вертикальной оси 612, представляющей полностью ненасыщенные цвета без оттенка, но с различными пропорциональными сочетаниями черного и белого. Например, черный цвет 610 содержит 100% черного цвета и совсем не содержит белый цвет, белый цвет 608 содержит 100% белого цвета и совсем не содержит черный цвет, а точка начала координат 613 содержит 50% черного цвета и 50% белого цвета. Светлота (l) представлена центральной вертикальной осью 612, она указывает на уровень освещенности, который изменяется от 0 для черного цвета 610 (l=0,0), до 1 для белого цвета 608 (l=1,0). Для произвольного цвета, представленного точкой 614 на Фиг. 6, оттенок определяется как угол θ 616 между первым вектором из исходной точки 613 к точке 602 и вторым вектором из исходной точки 613 к точке 620, в которой вертикальная линия 622, проходящая через точку 614, пересекает плоскость 624, включающую исходную точку 613 и точки 602, 604 и 606. Насыщенность представлена отношением расстояния представленной точки 614 от вертикальной оси 612 d' к длине горизонтальной линии, проходящей через точку 620 от исходной точки 613, к поверхности бипирамидальной призмы 600, d. Светлота представлена вертикальным расстоянием от репрезентативной точки 614 до вертикального уровня точки, представляющей черный цвет 610. Координаты конкретного цвета в цветовой модели (h, s, l), могут быть получены на основе координат цвета в цветовой модели RGB (r, g ,b) следующим образом:

,

, и

,

где значения r, g и b соответствуют яркости красного, зеленого и синего первичных цветов, нормализованных на интервале [0, 1]; C_max представляет нормализованное значение яркости, равное максимальному значению из r, g и b; C_min представляет собой нормализованное значение яркости, равное минимальному значению из r, g и b; а Δ определяется как C_max-C_min.

На Фиг. 7 показано формирование полутонового или бинаризованного изображения из цветного изображения. В цветном изображении каждый пиксель обычно описывается тремя значениями: а, b и с 702. В разных цветовых моделях для представления конкретного цвета используются разные значения a, b и с. Полутоновое изображение содержит для каждого пикселя только одно значение яркости 704. Бинаризованное изображение является частным случаем полутонового изображения, которое имеет только два значения яркости «0» и «1». Обычно полутоновые изображения могут иметь 256 или 65 536 разных значений яркости для каждого пикселя, представленного байтом или 16-битным словом соответственно. Таким образом, чтобы преобразовать цветное изображение в полутоновое, три значения а, b и с цветных пикселей необходимо преобразовать в одно значение яркости для полутонового или бинаризованного изображения. На первом этапе три цветовых значения а, b и с преобразуются в значение яркости L, обычно находящееся в диапазоне [0,0, 1,0] 706. В некоторых цветовых моделях к каждому из цветовых значений 708 применяется функция, а результаты суммируются 710 для получения значения яркости. В других цветовых моделях каждое цветовое значение умножается на коэффициент, и полученные результаты суммируются 712, давая значение яркости. В других цветовых системах одно из трех значений цвета фактически является значением яркости 714. Наконец, в общем случае к трем цветовым значениям 716 применяется функция, которая дает значение яркости. Затем значение яркости квантуется 718, позволяя получить значение яркости оттенков серого в требуемом интервале, обычно [0, 255] для полутоновых изображений и (0,1) для бинаризованных изображений.

Пример выбора модели для способа типа RANSAC

На Фиг. 8A-N показаны модели, которые описывают преобразования первого изображения документа во второе изображение документа и способ выбора конкретной модели из множества моделей-кандидатов для описания конкретного преобразования для двух соответствующих изображений документа. Преобразования могут отражать различные типы физического или связанного с получением изображения искажения или изменения документа по отношению к нормализованному документу такого же типа. Например, нормализованный документ может представлять собой точное изображение сертификата или удостоверения определенного типа. При получении изображения такого сертификата или удостоверения в неидеальных условиях могут возникнуть различные типы искажения изображения вследствие нестандартного расположения и ориентации устройства формирования изображения по отношению к документу, отсутствия фокусировки и других подобных условий, вызывающих искажения. В другом примере сертификат или удостоверение, для которых получают изображение, могут быть физически искажены из-за того, что этот документ смяли, сложили, испачкали, либо в результате других таких физических событий, вызывающих искажения. В обсуждаемых ниже способах и системах для выявления конкретных типов фрагментов изображений документов из изображений выбирается преобразование для описания любых искажений или других различий между нормированным документом или эталонным документом, и соответствующим фрагментом изображения документа внутри изображения. Во многих случаях определение преобразования включает определение не только модели, но также одного или нескольких параметров модели, которые наилучшим образом соответствуют наблюдаемым искажениям и различиям нормализованного изображения и соответствующего фрагмента изображения. Один из способов определения параметров математической модели из множества наблюдаемых данных называется способом оценки параметров на основе случайных выборок (random sample consensus или RANSAC). В обсуждаемом ниже примере со ссылкой на Фиг. 8A-N используется похожий на RANSAC метод оценки параметров для определения параметра модели, который наилучшим образом согласует модель с наблюдаемыми данными. Цель этого примера - для общего случая проиллюстрировать похожие на RANSAC методы выбора модели параметров. В раскрываемых в настоящем описании способах и подсистемах используются различные похожие на RANSAC методы для нескольких более сложных типов подгонки параметров и построения модели.

На Фиг. 8А показан пример проблемной области, для которой используется похожий на RANSAC метод подгонки параметра, а также выбор модели для определения преобразования, которое связывает первое изображение image1 со вторым изображением image2. На Фиг. 8А первое изображение 802 и второе изображение 804 показаны в верхней части чертежа. Первое изображение 802 содержит пять темных объектов на светлом фоне, в том числе три темных объекта квадратной формы 806-808 и два объекта неправильной формы 809 и 810. Второе изображение 804 также содержит пять объектов, в том числе три объекта квадратной формы 811-813 и два объекта неправильной формы 814 и 815. Первое изображение представляет собой двумерную матрицу пикселей, индексированных координатами (x, y) 818, а второе изображение 804 представляет собой двумерную матрицу пикселей, индексированных координатами (x', y') 819. Предположение заключается в том, что некоторые объекты или все объекты второго изображении 804 связаны с объектами первого изображения с помощью математически выраженного преобразования. Прямое преобразование 820 включает функцию f(x, y), возвращающую соответствующие координаты (x', y') для точки с координатами (x, y) в первом изображении. Обратное преобразование 821 преобразует координаты пикселя второго изображения в координаты пикселя первого изображения. Третье предположение для конкретного примера проблемы заключается в том, что цвет и (или) яркость пикселя (x, y) в первом изображении равны цвету и (или) яркости соответствующего пикселя (x', y') во втором изображении 822 или что они близки.

На Фиг. 8B-D показаны три различные возможные модели, представленные математическими выражениями, для преобразования объектов первого изображения 802, показанного на Фиг. 8А, в соответствующие объекты второго изображения 804, показанного на Фиг. 8А. Первая возможность, показанная на Фиг. 8В, представляет собой вертикальное перемещение объектов первого изображения в соответствующие позиции, которые, если бы модель была правильной, совпадали бы с позициями соответствующих объектов второго изображения. На Фиг. 8В объекты первого изображения показаны как незаштрихованные объекты, такие как квадратный объект 806, в то время как объекты второго изображения показаны как заштрихованные объекты, имеющие границы в виде пунктирных линией, такие как объект 811. Приемлемое преобразование преобразует пиксели объектов первого изображения в соответствующие пиксели объектов второго изображения. В случае модели вертикального перемещения, показанной на Фиг. 8В, некоторые пиксели, расположенные внутри объектов первого изображения, такие как пиксели 823 и 824, преобразуются согласно показанному преобразованию в соответствующие пиксели 825 и 826, расположенные внутри объектов второго изображения. Однако в других случаях, например, для пикселей 827 и 828, расположенных внутри объектов первого изображения 807 и 809, рассматриваемое преобразование преобразует пиксели в точки 829 и 830, расположенные вне объектов. Таким образом, модель вертикального перемещения по-видимому не является особенно устойчивой и точной моделью преобразования объектов первого изображения в объекты второго изображения. Модель вертикального перемещения вниз показана 831 сбоку от составного изображения 832, приведенного на Фиг. 8В.

На Фиг. 8С показана модель горизонтального перемещения, при этом для иллюстрации используются те же понятия, что и на Фиг. 8В. Здесь также некоторые пиксели, такие как пиксель 833, преобразуются из объектов первого изображения в объекты второго изображения, в то время как другие пиксели, такие как пиксель 834, преобразуются из объектов первого изображения в места, расположенные вне объектов. Как и на Фиг. 8В, модель горизонтального перемещения влево схематически представлена 835 справа от составного изображения 836, показанного на Фиг. 8С.

Наконец, на Фиг. 8D показана третья модель преобразования объектов изображения image1 в изображение image2, в ней в целях иллюстрации используются те же понятия, которые использовались на Фиг. 8В и 8С. Эта модель представляет собой поворот изображения image1 на 45 градусов вокруг центральной точки изображения image1 в направлении против часовой стрелки, что показано представлением модели 837 справа от составного изображения 838, показанного на Фиг. 8D. В целом каждая точка каждого квадратного объекта первого изображения, например, точки 839-841, преобразуется в соответствующие квадратные объекты второго изображения. Однако объекты неправильной формы первого изображения 809 и 810 не преобразуются в объекты неправильной формы второго изображения 814 и 815. Тем не менее именно эта модель будет считаться наиболее правильной из трех описанных моделей, поскольку фактически второе изображение 804 на Фиг. 8А было получено из первого изображения 802 поворотом квадратных объектов на 45 градусов против часовой стрелки вокруг центральной точки изображения. Объекты неправильной формы намеренно не были преобразованы поворотом на 45 градусов. Этот пример показывает, что может существовать основная модель, которая представляет преобразование положений отдельных объектов, представляющих интерес в первом изображении, в положение этих объектов во втором изображении, и что могут существовать другие признаки изображения, включая шум, оптические искажения и другие признаки, которые не так легко преобразовать. Таким образом, процесс оценки различных возможных моделей, а также выбора наилучшего значения параметра модели может включать сравнение результатов для того, чтобы выбрать лучшую, хотя и не полностью объясняющую модель. Следует обратить внимание на то, что для каждой из моделей, показанных на Фиг. 8B-D, имеется один параметр, значение которого требуется определить. Две модели преобразования имеют параметр «расстояние перемещения», в то время как модель вращения имеет параметр «угол поворота». В общем случае для модели могут потребоваться два или более значений параметров, которые необходимо определить. Похожие на RANSAC методы были разработаны для решения общей задачи определения параметров модели.

На Фиг. 8E-N с помощью таблицы показаны входные и выходные характеристики, а также ряд блок-схем для основанного на методе RANSAC подхода к определению того, какая из моделей, показанных на Фиг. 8B-D, наилучшим образом объясняет преобразование объектов первого изображения 802 (Фиг. 8А) в различные положения на втором изображении 804, показанном на Фиг. 8А, а также определяет оптимальное значение параметров модели для входных данных.

На Фиг. 8Е показана таблица, которая включает характеристики трех моделей. Три строки 842-844 представляют преобразование при вертикальном перемещении вниз, показанное на Фиг. 8В, преобразование при горизонтальном перемещении влево, показанное на Фиг. 8С, и преобразование поворотом против часовой стрелки, показанное на Фиг. 8D. Столбцы таблицы соответствуют представленным рядами полям в записях. Таким образом, каждая модель включает текстовое описание, соответствующее столбцу 845, математическое выражение прямого преобразования, соответствующее столбцу 846, одно или несколько математических выражений обратного преобразования, соответствующие столбцу 847, а также различные неизменяемые параметры, используемые в похожем на RANSAC методе подгонки параметра, которые обсуждаются ниже, соответствующие столбцам 848-849. Каждая модель математически описывается одним переменным параметром: параметром р в первых двух моделях и параметром θ в третьей модели.

На Фиг. 8F показаны входные и выходные аргументы программы «найти модель» (find model) и подпрограммы «найти параметр» (find parameter). Программа «найти модель» получает в качестве входных данных два изображения 850 и 851, массив моделей 852 и указание количества моделей в массиве моделей 853. Эта программа оценивает каждую модель в отношении исходных изображений. Если выявлена приемлемо точная модель, объясняющая систематические различия между положениями и цветами объектов в двух изображениях, то программа «найти модель» возвращает индекс наилучшей модели, определенной в массиве «Models», а также значение параметра р или θ, используемое в математических выражениях для преобразования, представленного моделью 853. В противном случае программа «найти модель» возвращает индикацию ошибки 854. В подпрограмме «найти параметр» реализован похожий на RANSAC метод, определяющий значение параметра модели р, который наилучшим образом описывает входные данные. Подпрограмма «найти параметр» получает в качестве входных данных 855 два изображения и массив моделей и на выходе определяет долю пикселей первого изображения, которые правильно преобразуются моделью в преобразованные положения во втором изображении 856, наилучшее значение параметра модели р 857, а также общую ошибку приложения, характеризующую применение преобразования к первому изображению 858.

На Фиг. 8G приведена блок-схема программы «найти модель». На шаге 860а программа «найти модель» получает первое и второе изображение, массив «Models» и указание количества моделей или записей в массиве «Models». Изображения могут быть получены в виде ссылок на файлы изображений, в виде ссылок на массивы пикселей или с помощью других стандартных вычислительных методик ввода. На шаге 860b программа «найти модель» инициализирует несколько локальных переменных, включая следующие: (1) bestP - наилучшее значение параметра; (2) bestRatio - наилучшее отношение правильно преобразованных пикселей к общему количеству пикселей в первом изображении; (3) bestError - общая ошибка для наилучшей модели; и (4) bestModel - индекс массива «Models», соответствующий модели, которая лучше всего объясняет различия между изображениями image1 и image2. В цикле for на шагах 860C-860i рассматривается каждая модель в массиве «Models». На шаге 860d вызывается подпрограмма «найти параметр» (find parameter) для определения наилучшего значения параметра модели. Если возвращаемое подпрограммой «найти параметр» отношение превышает значение, хранящегося в локальной переменной best Ratio, которое было определено на шаге 860е, то локальные переменные на шаге 860f обновляются значениями, возвращенными подпрограммой «найти параметр» для рассматриваемой в текущий момент модели. В противном случае, если возвращаемое подпрограммой «найти параметр» отношение равно значению, сохраненному в локальной переменной bestRatio, и общая ошибка, возвращенная подпрограммой «найти параметр», меньше значения, хранящегося в локальной переменной bestError, то на шаге 860f локальные параметры обновляются. В противном случае, если переменная цикла / меньше, чем значение numModels - 1, что определено на шаге 860h, то переменная цикла увеличивается на шаге 860i, и происходит переход к шагу 860d для следующей итерации цикла for. Если после завершения цикла for сохраненный в локальной переменной индекс bestModel превышает значение -1, определенное на шаге 860j, то затем на шаге 860k возвращаются значения, сохраненные в локальных переменных bestP и bestModel. В противном случае на шаге 860l возвращается индикация ошибки. Таким образом, программа «найти модель» оценивает все модели в массиве «Models» и возвращает указание на модель, которая наилучшим образом описывает преобразование признаков между первым и вторым исходными изображениями, а также наилучшее значение параметра для этой модели. Однако если приемлемая модель не найдена, как описано далее ниже, то программа «найти модель» возвращает индикацию ошибки.

На Фиг. 8H-N показана подпрограмма «найти параметр», вызываемая на шаге 860d на Фиг. 8G. Это похожий на RANSAC метод определения наилучшего значения параметра для модели с одним параметром. Эта подпрограмма легко расширяется на определение нескольких значений параметров для моделей, имеющих два или более переменных параметра, однако при использовании простейших подходов объем дополнительных расчетов возрастает в геометри