МЕСТНАЯ ЛОКАЛИЗАЦИЯ С ИСПОЛЬЗОВАНИЕМ БЫСТРОГО СОГЛАСОВАНИЯ ИЗОБРАЖЕНИЙ
ON-SITE LOCATION USING FAST IMAGE MATCHING

Область техники, к которой относится изобретение
Изобретение относится к определению местоположения части документа, захваченной в изображении. Различные аспекты настоящего изобретения применимы, в частности, для идентификации местоположения меток на документе путем захвата изображений документа.
Предшествующий уровень техники
Хотя электронные документы, хранящиеся в компьютерах, обеспечивают ряд преимуществ над рукописными документами, многие пользователи продолжают решать некоторые задачи, пользуясь печатными версиями электронных документов. Эти задачи включают в себя, например, чтение и аннотирование документов. В связи с этими аннотациями следует отметить, что бумажная версия документа имеет вполне конкретное значение, потому пользователь, как правило, записывает аннотации непосредственно на отпечатанный документ. Вместе с тем, одна из проблем, связанных с непосредственным аннотированием печатной версии документа, является затруднение при последующем преобразовании аннотаций в электронную форму. В идеальном случае, аннотации, хранимые в электронной форме, должны соответствовать электронной версии документа таким же образом, как аннотации, написанные от руки, соответствуют бумажной версии документа.
Это соответствие обычно требует, чтобы первоначальный или другой пользователь разобрался в аннотациях и лично ввел их в компьютер. В некоторых случаях, пользователь может провести электронное сканирование аннотаций, написанных на бумажном документе, и таким образом создать новый электронный документ. Эти несколько этапов требуют согласованности между печатной версией документа и электронной версией этого документа, причем эту согласованность трудно поддерживать при повторении упомянутых этапов. Кроме того, сканированные изображения зачастую не допускают редактирования. Таким образом, может оказаться невозможным отделить аннотации от первоначального текста документа. Это затрудняет использование аннотаций.
Для решения этой проблемы были разработаны перья, предназначенные для захвата аннотаций, записанных на печатные документы пером. Перо этого типа включает в себя камеру, которая захватывает изображения печатного документа, когда пользователь пишет аннотации. Однако при реализации некоторых примеров пера этого типа, перо может использовать чернила, которые невидимы для съемочной камеры. Перо может использовать, например, неуглеродистые чернила и инфракрасное освещение для съемочной камеры, что не дает съемочной камере «увидеть» аннотацию, написанную этими чернилами. Для пера этого типа, перо определяет движение кончика пера, формируя аннотации на документе из изображений, захватываемых пером во время написания аннотаций. Вместе с тем, чтобы связать изображения с первоначальным электронным документом, нужно определять положение изображений относительно документа. Соответственно, перо этого типа часто используется вместе с бумагой, которая включает в себя узор, однозначно идентифицирующий местоположения на бумаге. Анализируя этот узор, компьютер, принимающий изображение, может определить, какая часть бумаги (и таким образом, какая часть печатного документа) была захвачена в этом изображении.
Хотя использование такой узорной бумаги или других носителей позволяет преобразовывать рукописные аннотации на бумажном документе в электронную форму и надлежащим образом связывать с электронной версией документа, этот способ не всегда надежен. Например, документ, содержащий текст на бумаге, может скрывать области узора. Если перо захватывает изображение одной из этих областей, компьютер может оказаться неспособным использовать узор для точного определения местоположения части документа, захваченной этим изображением. Вместо этого, компьютеру придется использовать другой способ идентификации местоположения части документа, захваченной в изображении. Например, компьютер может осуществлять попиксельное сравнение захваченного изображения с электронным документом.
Попиксельное сравнение будет обычно идентифицировать часть документа в захваченном изображении, но для этого способа характерен высокий уровень непроизводительных издержек при обработке. Чтобы осуществить этот способ, например, преобразование, такое как поворот и масштабирование, между захваченным изображением и изображением документа в типичном случае сначала должно быть оценено, так чтобы захваченное изображение может быть деформировано и согласовано с изображением документа на попиксельной основе. Если преобразование неизвестно, нужно рассматривать все возможные повороты и масштабы. Кроме того, в изображении выбирают опорный пиксел. Каждый пиксел в деформированном изображении затем сравнивают с соответствующим пикселом в электронном документе, так что опорный пиксел изображения сравнивается с первым местоположением в электронном документе. Затем это сравнение нужно повторить так, чтобы в перспективе сравнить опорный пиксел изображения с каждым местоположением в электронном документе. Сравнение, сопровождаемое наибольшим соответствием пикселов изображения и электронного документа, идентифицирует положение опорного пиксела относительно электронного документа, а значит и часть документа, захваченную в изображении. Поэтому было бы желательно разработать способ, который позволит компьютеру определять местоположение части документа в захваченном изображении без проведения попиксельного сравнения изображения со всем документом в целом.
Краткое изложение сущности изобретения
В различных вариантах осуществления изобретения преимущественно предложен эффективный способ определения части документа, соответствующей захваченному изображению. В соответствии с различными вариантами осуществления изобретения, когда пользователь пользуется пером, чтобы создать росчерк в документе, камера, установленная на пере, захватывает ряд изображений. Положение некоторых из изображений будет определяться, например, в результате анализа узора документа, который захвачен изображением, или в результате попиксельного сравнения изображения с документом. Однако положение других изображений придется определять с помощью других способов.
Чтобы эффективно определить положение этих нелокализованных (с неизвестным положением) изображений, всю последовательность изображений сегментируют на группы, которые соответствуют форме росчерка. Таким образом, изображения, которые соответствуют относительно линейной части росчерка, будут сгруппированы вместе. Кроме того, поскольку все изображения в сегменте будут в типичном случае близкими, информацию, касающуюся локализованных (с известным положением) изображений, можно будет использовать для определения положения тех изображений в сегменте, которые не локализованы. Например, можно установить для нелокализованного изображения некоторую область поиска в документе на основе положения ранее локализованного изображения и максимальной или фактической скорости пера. Кроме того, поворот и масштаб (т.е. аффинное преобразование, которое впоследствии можно уточнить как перспективное преобразование) локализованного изображения можно использовать в качестве оценки поворота и масштаба нелокализованного изображения, потому что не ожидается значительного изменения положения пера за короткий промежуток времени. Эти оцененные поворот и масштаб можно использовать для деформирования нелокализованного изображения с целью согласования с ориентацией и масштабом изображения в документе. Затем можно провести попиксельное сравнение деформированного нелокализованного изображения и области поиска в документе.
Перечень фигур чертежей
Фиг.1 - общее описание компьютера, который может быть использован совместно с вариантами осуществления настоящего изобретения.
Фиг.2А - иллюстрация примера пера, соответствующего различным вариантам осуществления изобретения, а на фиг.2В - иллюстрация разрешения изображения, которое можно получить с помощью конкретных вариантов осуществления изобретения.
Фиг.3А-3I - различные примеры кодовых систем в соответствии с вариантами осуществления настоящего изобретения.
Фиг.4 - графическая иллюстрация того, как можно использовать кодирующий узор для определения поворота изображения, захваченного из части документа.
Фиг.5 - формула, которую можно использовать для определения поворота изображения, захваченного из части документа.
Фиг.6 - иллюстрация росчерка, выполненного в документе.
Фиг.7 - иллюстрация захваченных изображений по мере выполнения того росчерка в документе, который показан на фиг.6.
Фиг.8 - иллюстрация опорных точек для каждого захваченного изображения, показанного на фиг.7.
Фиг.9 - иллюстрация инструментального средства, которое можно использовать для согласования захваченного изображения с частью документа в соответствии с различными вариантами осуществления изобретения.
Фиг.10А-10С - схемы последовательности операций, описывающие способ согласования захваченного изображения с частью документа в соответствии с различными вариантами осуществления изобретения.
Фиг.11 и 12 - иллюстрации определения опорных точек поворота для росчерка, показанного на фиг.6.
Фиг.13 и 14 - иллюстрации примера того, как можно деформировать захваченное изображение.
Подробное описание изобретения
Рабочая среда
На фиг.1 показана функциональная блок-схема примера обычной цифровой вычислительной среды общего назначения, которую можно использовать для реализации различных аспектов настоящего изобретения. На фиг.1 показано, что компьютер 100 включает в себя процессор 110, системную память 120 и системную шину 130, которая соединяет различные системные компоненты, включая системную память, с процессором 110. Системная шина 130 может представлять собой любую из нескольких типов шинных структур, включая шину памяти или контроллер памяти, периферийную шину и локальную шину, с использованием множества архитектур шин. Системная память 120 включает в себя постоянную память (ROM) 140 и оперативную память (RAM) 150.
В ROM 140 хранится базовая система 160 ввода-вывода (BIOS), содержащая базовые процедуры, которые способствуют передаче информации между элементами внутри компьютера 100, например, во время запуска. Компьютер 100 также включает в себя накопитель 170 на жестких дисках для считывания с жесткого диска (не показан) и записи на него, магнитный дисковод 180 для считывания со сменного магнитного диска 190 и записи на него, и оптический дисковод 191 для считывания со сменного оптического диска 192, такого, как CD ROM или другой оптический носитель, и записи на него. Накопитель 170 на жестких дисках, магнитный дисковод 180 и оптический дисковод 191 подключены к системной шине 130 посредством интерфейса 189 накопителя на жестких дисках, интерфейса 193 магнитного дисковода и интерфейса 194 оптического дисковода, соответственно. Накопители и дисководы и связанные с ними машиночитаемые носители информации обеспечивают энергонезависимое хранение машиночитаемых команд, структур данных, программных модулей и других данных для персонального компьютера 100. Специалисты в данной области техники поймут, что в возможной операционной среде можно также использовать машиночитаемые носители информации других типов, выполненные с возможностью хранения данных, к которым компьютер может осуществить доступ, например, кассеты с магнитной лентой, платы флэш-памяти, цифровые видеодиски, картриджи Бернулли, блоки оперативной памяти (RAMs), блоки постоянной памяти (ROMs) и т.п.
В накопителе 170 на жестких дисках, на магнитном диске 190, оптическом диске 192, в ROM 140 или RAM 150 можно хранить некоторое количество программных модулей, включая операционную систему 195, одну или более прикладных программ 196, другие программные модули 197 и данные 198 программ. Пользователь может вводить команды и информацию в компьютер 100 посредством таких устройств ввода, как клавиатура 101 и указательное устройство 102. Другие устройства ввода (не показаны) могут включать в себя микрофон, джойстик, игровую приставку, спутниковую тарелку, сканер и т.п. Эти и другие устройства ввода часто подключены к процессору 110 через интерфейс 106 последовательного порта, который подсоединен к системной шине, но их можно подключать через другие интерфейсы, например, параллельный порт, игровой порт или универсальную последовательную шину (USB). Кроме того, эти устройства также можно подсоединять непосредственно к системной шине 130 через подходящий интерфейс (не показан). К системной шине 130 через такой интерфейс, как видеоадаптер 108, также подключен монитор 107 или отображающее устройство другого типа. Помимо монитора, персональные компьютеры обычно включают в себя другие периферийные устройства вывода (не показаны), такие как громкоговорители и принтеры. В предпочтительном варианте осуществления, предусматривается наличие цифрового преобразователя 165 пера и связанного с ним пера или пишущего элемента 166 для цифрового захвата рукописного ввода. Хотя показано непосредственное соединение между цифровым преобразователем 165 и последовательным портом, на практике цифровой преобразователь 165 может быть соединен с процессором непосредственно, через интерфейс параллельного порта или другой интерфейс и системную шину 130, как известно в данной области техники. Кроме того, хотя цифровой преобразователь 165 показан отдельно от монитора 107 предпочтительно, чтобы полезная область ввода цифрового преобразователя 165 была продолжением области отображения монитора 107. Помимо этого, цифровой преобразователь 165 может быть встроен в монитор 107 или может существовать в качестве отдельного устройства, наложенного на монитор 108 или подсоединенного к этому монитору иным образом.
Компьютер 100 может работать в сетевой среде с помощью логических соединений с одним или более удаленными компьютерами, таким, как удаленный компьютер 109. Удаленный компьютер 109 может быть сервером, маршрутизатором, сетевым персональным компьютером, одноранговым устройством или другим обычным узлом сети, и в типичном случае включает в себя многие или все элементы, описанные выше применительно к компьютеру 100, хотя на фиг.1 проиллюстрировано только запоминающее устройство 111. Логические соединения, изображенные на фиг.1, включают в себя локальную сеть (LAN) 112 и глобальную сеть (WAN) 113. Такие сетевые среды широко распространены в офисах, компьютерных сетях масштаба предприятия, корпоративных локальных сетях и Internet.
При использовании в сетевой среде LAN, компьютер 100 подключен к локальной сети 112 через сетевой интерфейс или адаптер 114. При использовании в сетевой среде WAN персональный компьютер 100 в типичном случае включает в себя модем 115 или другие средства для установления связи через глобальную сеть 113, такую как Internet. Модем 115, который может быть внутренним или внешним, может быть подключен к системной шине 113 через интерфейс 106 последовательного порта. В сетевой среде программные модули, предназначенные для персонального компьютера 100, или их части, могут храниться в удаленном запоминающем устройстве.
Следует понять, что показанные сетевые соединения носят иллюстративный характер, и можно использовать другие методики установления линии связи между компьютерами. Предполагается наличие любых из многочисленных и широко известных протоколов, таких как TCP/IP (протокол управления передачей/протокол Internet), Ethernet, FTP (протокол передачи файлов), HTTP (протокол передачи гипертекста), Bluetooth, IEEE 802.11x и т.п., а система может работать в конфигурации «клиент - сервер», чтобы предоставить пользователю возможность извлекать web-страницы из сервера, работающего на основе web-технологии. Для отображения данных на web-страницах и манипулирования этими данными можно использовать любой из различных обычных web-браузеров.
Устройство для захвата изображения
Различные варианты осуществления можно использовать для определения местоположений частей документа, захваченных серией изображений. Как отмечалось выше, определение местоположения части документа, захваченной в изображении, можно использовать для выяснения местоположения взаимодействия пользователя с бумагой, экраном отображающего устройства или другим носителем, отображающим документ. В соответствии с некоторыми вариантами осуществления изобретения, изображения можно получать с помощью чернильного пера, используемого для письма чернилами на бумаге. В соответствии с другими вариантами осуществления изобретения, перо может быть пишущим элементом, используемым для «письма» электронными чернилами на поверхности цифрового преобразователя, отображающего документ.
На фиг.2А и 2В показан иллюстративный пример пера 201, которое можно применять в соответствии с различными вариантами осуществления изобретения. Перо 201 включает в себя кончик 202 и камеру 203. Кончик 202 может включать или не включать в себя резервуар с чернилами. Камера 203 захватывает изображение 204 с поверхности 207. Перо 201 может также включать в себя дополнительные датчики и/или процессоры, отображенные пунктирным прямоугольником 206. Эти датчики и/или процессоры 206 могут также предусматривать способность передавать информацию в еще одно перо 201 или в еще один персональный компьютер (например, посредством протокола Bluetooth или других протоколов беспроводной связи).
На фиг.2В представлено изображение, как его «видит» камера 203. В одном иллюстративном примере, разрешение изображения, захваченного съемочной камерой 203, составляет NxN пикселов (где N=32). Соответственно, на фиг.2В показано иллюстративное изображение, имеющее 32 пиксела в длину и 32 пиксела в ширину. Размер N является регулируемым, причем большее значение N будет обеспечивать большее разрешение изображения. Кроме того, хотя изображение, захваченное камерой 203, показано здесь в целях иллюстрации в виде квадрата, поле зрения камеры может предусматривать другие формы, как известно в данной области техники.
i
i
i
Изображения, захваченные камерой 203, можно охарактеризовать как последовательность кадров {I} изображения, где I захватывается пером 201 за время t выборки. Скорость выборки может быть большой или малой, в зависимости от конфигурации системы и требования эффективности. Размер кадра захваченного изображения может быть большим или малым, в зависимости от конфигурации системы и требования эффективности. Кроме того, должно быть ясно, что изображение, захваченное камерой 203, может прямо или косвенно использоваться обрабатывающей системой или может подвергаться предварительной фильтрации. Эта предварительная фильтрация может осуществляться в пере 201 или может осуществляться вне пера 201 (например, в персональном компьютере).
На фиг.2А также показана плоскость 209 изображения, в которой формируется изображение 210 узора из местоположения 204. Свет, принимаемый от узора в предметной плоскости 207, фокусируется линзой 208. В соответствии с различными вариантами осуществления изобретения, линза 208 может представлять собой одиночную линзу или многоэлементную линзовую систему, но в данном случае для простоты представлена в виде одиночной линзы. Датчик 211 захвата изображения захватывает изображение 210.
Датчик 211 изображения может быть достаточно большим, чтобы захватить изображение 210. В альтернативном варианте, датчик 211 изображения может быть достаточно большим, чтобы захватить изображение кончика 202 пера в местоположении 212. Для справки отметим, что изображение в местоположении 212 будет считаться виртуальным кончиком пера. Следует заметить, что местоположение виртуального кончика пера относительно датчика 211 изображения является фиксированным ввиду неизменной взаимосвязи между кончиком пера, линзой 208 и датчиком 211 изображения.
S→P
Как отмечалось ранее, перо 201 в типичном случае будет использоваться совместно с носителем, таким как документ, отпечатанный на бумаге, с отображениями узора для идентификации положений на этом носителе. Этот узор преимущественно можно использовать для преобразования изображения 210, захваченного камерой 203, в форму, соответствующую внешнему виду носителя. Например, нижеследующее преобразование F преобразует изображение 210, захваченное камерой 203, в реальное изображение на листе бумаги:
бумаги
S→P
датчика
L=F(L).
S→P
Во время письма, кончик пера и бумага находятся в одной и той же плоскости. Соответственно, преобразование из виртуального кончика пера в реальный кончик пера также будет преобразованием F:
кончика пера
S→P
виртуального кончика пера
L=F(L).
S→P
Преобразование F можно оценить как аффинное преобразование. Оно представляется в упрощенной форме как
S→P
x
y
x
y
S→P
S→P
S→P
т.е. как оценка преобразования F, где θ, θ, s и s представляют собой поворот и масштаб двух ориентаций узора, захваченного в местоположении 204. Кроме того, можно получить уточнение F' путем согласования захваченного изображения с соответствующим реальным изображением на бумаге. «Получить уточнение» означает получить более точную оценку преобразования F с помощью некой разновидности алгоритма оптимизации, называемой рекурсивным методом. Рекурсивный метод рассматривает матрицу F' в качестве начального значения. Уточненная оценка точнее описывает преобразование между S и P.
кончика пера
S→P
виртуального кончика пера
Местоположение виртуального кончика пера можно определить с еще большей точностью путем калибровки. Чтобы калибровать местоположение виртуального кончика пера, пользователь располагает кончик 202 пера в фиксированном местоположении L на бумаге. Затем пользователь наклоняет перо, давая камере 203 возможность захватить ряд изображений при разных положениях пера. Для каждого захваченного изображения получается преобразование F. Из этого преобразования можно получить местоположение виртуального кончика пера, L:
виртуального кончика пера
P→S
кончика пера
(L)=F(L),
кончика пера
где L инициализируется как (0, 0) и
P→S
S→P
-1
F=(F).
виртуального кончика пера
виртуального кончика пера
виртуального кончика пера
кончика пера
виртуального кончика пера
Усредняя L, полученное из каждого изображения, можно определить местоположение виртуального кончика пера, L. С помощью L можно дать более точную оценку L. После нескольких итераций можно получить точное местоположение виртуального кончика пера, L.
Узор для идентификации положений на носителе
Как отмечалось ранее, применяются различные конкретные варианты осуществления изобретения для определения части документа, соответствующей захваченному изображению, причем носитель, отображающий документ, также включает в себя узор для идентификации различных положений на носителе. Таким образом, узор можно считать кодированным потоком данных в отображенной форме. Носитель, отображающий узор, может быть отпечатанной бумагой (или другим физическим носителем) или, в альтернативном варианте - может быть дисплеем, проецирующим поток кодированных данных в связи с еще одним изображением или набором изображений. Например, кодированный поток данных может быть представлен в виде физического изображения на бумаге или изображения, накладываемого на отображенное изображение, или может быть физическим кодированным узором (т.е. неизменяемым узором), объединенным с экраном дисплея или накладываемым поверх него (так что любая часть изображения, захватываемая пером, размещается на экране дисплея).
На фиг.3А показан один пример способов кодирования, предназначенных для кодирования первого бита и второго бита с получением узора для идентификации положений на носителе. Первый бит 301 (например, со значением «1») представлен столбцом темных чернил. Второй бит 302 (например, со значением «0») представлен строкой темных чернил. Вместе с тем, следует понимать, что для представления различных битов можно использовать чернила любого цвета. Единственное требование к выбираемому цвету чернил состоит в том, чтобы он обеспечивал значительный контраст с фоном носителя, различаемый системой захвата изображения. В этом примере, биты на фиг.3А представлены имеющей размер 3×3 матрицей точек. Размер матрицы можно изменить с получением любого желаемого размера на основании размера и разрешения системы захвата изображения, используемой для захвата изображений носителя.
Альтернативные представления битов значениями 0 и 1 показаны на фиг.3С-3Е. Следует понимать, что представление нуля или единицы для кодирования выборок, показанное на фиг.3А-3Е, можно менять одно на другое без эффекта. На фиг.3С показаны представления битов, занимающие две строки или два столбца в перемежающемся расположении. На фиг.3D показано альтернативное расположение элементов изображения в строках и столбцах в пунктирных линиях. И, наконец, на фиг.3Е показаны представления элементов изображения в столбцах и строках в формате с неодинаковыми промежутками (например, в виде двух темных точек с последующей неокрашенной точкой).
Следует отметить, что возможны альтернативные ориентации сетки, включая поворот нижележащей сетки в негоризонтальное и невертикальное расположение (например, когда правильная ориентация узора составляет 45°). Используя негоризонтальное и невертикальное расположение, можно обеспечить вероятное преимущество исключения визуальных особенностей, отвлекающих внимание, создаваемых пользователем, поскольку пользователи могут быть склонны предпочитать горизонтальные и вертикальные узоры другим. Вместе с тем, в целях упрощения, ориентацию сетки (горизонтальную, вертикальную, а также соответствующую любому другому желаемому повороту нижележащей сетки) собирательно называют предварительно определенной ориентацией сетки.
Возвращаясь к фиг.3А, отмечаем, что если некоторый бит представлен имеющей размер 3×3 матрицей элементов, а система получения изображения обнаруживает темную строку и две светлых строки в области 3×3, то это означает, что обнаружена область со значением «нуль» (или, в альтернативном варианте, со значением «единица»). Если обнаружена область 3×3 с темным столбцом и двумя светлыми столбцами, то это означает, что обнаружена область со значением «единица» (или, в альтернативном варианте, со значением «нуль»). Соответственно, если размер изображения 210 на фиг.2В составляет 32×32 пиксела, а размер каждого кодирующего блока составляет 3×3 пиксела, то количество захваченных кодированных блоков должно составлять приблизительно 100 блоков. Если размер кодированного блока составляет 5×5, то количество захваченных кодированных блоков должно составлять приблизительно 36.
Как показано на фиг.3А, можно использовать более одного пиксела или одной точки для представления бита. Использование единственного пиксела (или единственной точки) для представления бита ненадежно. Пыль, сгибы на бумаге, неплоские поверхности и т.п. создают затруднения при чтении одноэлементных представлений единиц данных. Однако даже при использовании нескольких элементов для представления битов, другой текст, отображаемый на носителе с узором, такой как отпечатанный текст в документе, может по-прежнему скрывать один или более битов в узоре.
Для создания графического узора 303, изображенного на фиг.3В, используют поток битов. Графический узор 303 включает в себя 12 строк и 18 столбцов. Более конкретно, строки и столбцы сформированы потоком битов, преобразуемым в графический узор 303 с помощью представлений 301 и 302 битов. Таким образом, узор 303, изображенный на фиг.3В, можно рассматривать как имеющий следующее представление битов:
Для создания изображения 303, показанного на фиг.3В, можно использовать различные потоки битов. Например, можно использовать случайную или псевдослучайную последовательность единиц и нулей. Последовательность битов можно располагать в строках, в столбцах, по диагоналям или с соблюдением любого другого стереотипного порядка. Например, вышеупомянутую матрицу можно сформировать с помощью следующего потока битов, если пробегать строки слева направо с последующим переходом к нижней строке:
0100 0111 0110 0100 1000 1110 0111 0100 1100.
Вышеупомянутую матрицу можно сформировать с помощью следующего потока битов, если пробегать столбцы сверху вниз с последующим переходом к правому столбцу:
0101 1100 0011 0010 0110 1001 1001 1110 0010.
Вышеупомянутую матрицу можно сформировать с помощью следующего потока битов, если пробегать матрицу по одной диагонали с последующим переходом на другую:
0110 0000 0101 0101 1000 0011 1111 1010 1010.
На фиг.3В также показаны укрупненные виды блоков элементов изображения из изображения 303. Укрупненные виды 304-311 иллюстрируют имеющие размер 5×5 блоки пикселов. Блок 304 пикселов иллюстрирует темную строку между светлыми строками. Блок 305 пикселов иллюстрирует темный столбец между светлыми столбцами. Блок 306 пикселов иллюстрирует нижний левый угол. Блок 307 пикселов иллюстрирует верхний правый угол. Блок 308 пикселов иллюстрирует темный столбец с половиной темной строки слева. Блок 309 пикселов иллюстрирует темную строку с половиной темного столбца над этой строкой. Блок 310 пикселов иллюстрирует половину темной строки. Блок 311 пикселов иллюстрирует половину темного столбца. Анализируя комбинацию блоков пикселов, следует понимать, что все комбинации пикселов можно сформировать с помощью сегментов изображения, обнаруживаемых в блоках 304-311 пикселов. Узор того типа, который показан на фиг.3В, можно назвать «лабиринтным» узором, поскольку линейные сегменты явно образуют лабиринт при отсутствии области, со всех четырех сторон полностью окруженной этим лабиринтом.
Без преувеличения, следует ожидать, что каждую из четырех «угловых» комбинаций пикселов, показанных на фиг.3Е-3I, можно будет найти в лабиринтном узоре, показанном в изображении 303. Вместе с тем, как видно на фиг.3В, в восьми блоках 304-311 пикселов фактически присутствуют только три типа углов. В этом примере нет угловой комбинации пикселов, показанной на фиг.3F. Выбирая сегменты 301 и 302 изображения, чтобы исключить некоторый тип угла таким образом, можно определить ориентацию захваченного изображения на основе пропущенного типа угла.
Например, как показано на фиг.4, можно проанализировать изображение 401, как оно захвачено камерой 203, и определить его ориентацию таким образом, чтобы обеспечить его интерпретацию применительно к положению, фактически представляемому изображением 401. Во-первых, просматривают изображение 401, чтобы определить, какие пикселы изображения 401 образуют лабиринтный узор, и угол θ, необходимый для поворота изображения таким образом, чтобы пикселы узора были выровнены по горизонтали и вертикали. Следует отметить, что, как обсуждалось выше, возможны альтернативные варианты выравнивания сетки согласно другим вариантам осуществления изобретения, включая поворот нижележащей сетки в негоризонтальное и невертикальное расположение (например, когда правильная ориентация узора составляет 45°).
Далее, изображение 401 анализируют, чтобы определить, какой угол пропущен. Величина «о» поворота, необходимая для поворота изображения 401 с тем, чтобы получить изображение 403, готовое к декодированию, показана как о=(θ плюс величина поворота {определяемая тем, какой угол пропущен}). Величина поворота показана уравнением на фиг.5. Возвращаясь к фиг.4, отмечаем, что сначала определяют угол θ по компоновке пикселов, необходимой для достижения вертикального и горизонтального (или соответствующего другой предварительно определенной ориентации сетки) расположения пикселов, и поворачивают изображение так, как обозначено позицией 402. Затем проводят анализ, чтобы определить пропущенный угол, и поворачивают изображение 402, получая изображение 403, чтобы задать изображение для декодирования. В данном случае изображение поворачивают на 90° против часовой стрелки, так что изображение 403 имеет правильную ориентацию и может быть использовано для декодирования.
Следует понимать, что поворот на угол θ может быть осуществлен перед поворотом изображения 401, или после такого поворота, для учета пропущенного угла. Следует также понимать, что, принимая во внимание шум в захваченном изображении, могут присутствовать все четыре типа углов. Соответственно, при различных вариантах осуществления изобретения можно подсчитывать количество углов каждого типа, а тип, которому соответствует наименьшее количество углов, можно определить как тип угла, который пропущен.
И, наконец, считывают код в изображении 403 и выполняют его корреляцию с первоначальным потоком битов, использованным для создания изображения 303. Корреляцию можно проводить многими способами. Например, ее можно проводить с помощью рекурсивного подхода, при котором восстановленный поток битов сравнивают со всеми остальными фрагментами потока битов в пределах первоначального потока битов. Во-вторых, можно провести статистический анализ для сопоставления восстановленного потока битов и первоначального потока битов, например, посредством использования расстояния Хэмминга между этими двумя потоками битов. Следует признать, что можно применять множество подходов к определению местоположения восстановленного потока битов в пределах первоначального потока битов.
Из вышеизложенного ясно, что можно использовать вышеописанный лабиринтный узор, чтобы закодировать информацию на поверхность носителя, например, на лист бумаги или дисплей цифрового преобразователя. Эту информацию затем можно захватывать в одном или более изображениях с помощью камеры 203 пера 201 и декодировать. Одним исключительно полезным типом информации, которую можно кодировать на поверхность носителя, является информация о положении. Если части потока битов не повторяются на носителе, то компьютер 100 сможет определить часть документа, содержащую конкретный поток битов.
Если в изображении захватывается законченная часть узора, то компьютер 100 окажется способным определить часть документа, захваченную в изображении, как описано выше. Однако при некоторых обстоятельствах часть изображения может быть скрыта. Например, если носитель представляет собой документ, содержащий, например, отпечатанный текст, то этот текст может частично скрывать один или более битов в узоре. В вышеупомянутом примере (когда каждый бит построен на имеющей размер 3×3 матрице пикселов, а разрешение камеры 203 составляет 32×32 пиксела), компьютер 100 с очень большой вероятностью окажется способным определить часть документа, захваченную в изображении, если из этого изображения удастся идентифицировать 60 или более битов. Вмести с тем, если удасться идентифицировать лишь от 36-ти до 60-ти битов, то компьютер 100 по-прежнему окажется способным определить положение части документа, захваченной в изображении. А вот если удасться идентифицировать лишь 35 или менее битов из изображения, то компьютер 100 окажется неспособным определить положение части документа, захваченной в изображении.
Изображения, захватываемые с помощью росчерка
В иллюстрируемом варианте осуществления изобретения, чернила, формирующие росчерк на документе, невидимы для камеры 203, как подробно описано выше. Вместо этого, камера 203 захватывает изображения документа по мере того, как перо движется, формируя росчерк. Вывод о положении реального кончика пера, а значит и о положении росчерка, делают на основе смещения положения центра изображений с помощью параметра калибровки. Соответственно, на фиг.6 приведен пример траектории 601 росчерка, соответствующей росчерку, который можно сформировать на документе, пользуясь пером 201. Траектория 601 росчерка следует форме росчерка, но имеет смещение от этого росчерка. Когда пользователь движет перо 201, формируя росчерк, камера 203 периодически захватывает изображение документа вдоль траектории 601 росчерка. Соответственно, как показано на фиг.7, камера 203 будет захватывать серию изображений 701А-701Х документа, причем центр каждого изображения будет находиться на траектории 601 росчерка. Таким образом, центр каждого изображения 701А-701Х находится на реальной траектории 601 росчерка. Поэтому на фиг.8 проиллюстрирована серия точек 801А-801Х, которые являются центрами изображений 701А-701Х, соответственно. Вместе с тем, следует понять, что в других вариантах осуществления изобретения можно применять другое расположение. Например, в альтернативных вариантах осуществления изобретения, центр захваченного изображения может соответствовать реальному кончику 202 пера 201.
Как отмечалось ранее, документ будет включать в себя узор, содержащий битовую информацию, идентифицирующую различные местоположения документа. Соответственно, каждое изображение 701А-701Х может включать в себя часть этого узора. В некоторых случаях, захваченное изображение будет включать в себя такую часть узора, которая будет достаточна для того, чтобы компьютер, такой как компьютер 100, смог определить местоположение изображения (т.е. положение части документа, захваченной в изображении). В альтернативном варианте, можно получить одно или более изображений, например, путем попиксельного сравнения изображения с документом или выбранными областями документа.
С другой стороны, как отмечалось выше, если из изображения идентифицировано недостаточное количество битов, то компьютер 100 не сможет определить, какая часть документа захвачена в изображении. Вместо этого компьютер 100 должен применить альтернативный способ, чтобы определить, какая часть документа захвачена в изображении. Следовательно, если документ хранится в электронной форме, то компьютер 100 сможет провести попиксельное сравнение пиксела изображения в повернутом и масштабированном изображении с каждым местоположением в электронном документе. Этот способ может потребовать большого количества процессов сравнения. Например, одна страница в электронном документе может содержать 1410×2019 пикселов, так что понадобятся 2889090 (1410×2019) сравнений. Кроме того, каждый процесс сравнения предусматривает сравнение большого количества пикселов. Например, захваченное изображение может содержать 32×32 пиксела, следовательно, при каждом сравнении сравниваются 1024 (32×32) пиксела. Кроме того, если нельзя оценить поворот и масштаб захваченного изображения, то придется рассматривать все возможные повороты и масштабы. Этот способ также предусматривает большой объем непроизводительных затрат при обработке и требует больших затрат времени. Вместо этого, как будет подробнее описано ниже, компьютер 100 может эффективнее и быстрее определять местоположение, где находится изображение, осуществляя быстрое согласование изображений в соответствии с различными вариантами осуществления изобретения.
На фиг.9 проиллюстрировано инструментальное средство 901, которое можно использовать для осуществления быстрого согласования захваченного изображения с частью документа в соответствии с различными вариантами осуществления изобретения. Инструментальное средство 901 включает в себя модуль 903 приема изображений, модуль 905 сегментации, модуль 907 завершения сегментов и модуль 909 удаления результатов. Как будет подробнее описано ниже, модуль 903 приема изображений принимает изображения части документа, отображенного на физическом носителе, при этом центр каждого изображения находится на траектории 601 росчерка, располагающейся со смещением относительно реального росчерка, сделанного чернилами. Затем модуль 905 сегментации анализирует каждое изображение, чтобы сегментировать последовательность изображений, соответствующую форме росчерка. Сразу же после определения сегментов, модуль 907 завершения сегментов «завершает» каждый сегмент путем определения местоположения каждого изображения в сегменте. Затем модуль 909 удаления результатов удаляет результаты, которые были ошибочно определены модулем 907 завершения сегментов. Один способ определения нелокализованных частей документа, соответствующих изображениям, описан в схеме последовательности операций, показанной на фиг.10А-10С, которые также будут подробнее описаны ниже.
Сегментация изображений
При анализе изображений, захваченных вдоль траектории росчерка, компьютер 100 сначала попытается определить положение каждого изображения с помощью узора, предусмотренного в документе, например, лабиринтного узора, подробно описанного выше. Если посредством декодирования узора не удалось успешно определить положение изображения, то проводят попиксельное сравнение между первым изображением и документом (или, если можно идентифицировать вероятные соответствующие области документа, - сравнение с этими вероятными соответствующими областями). Если можно успешно локализовать первое изображение посредством такого сравнения, то остальные кадры анализируют с помощью местного процесса локализации, подробнее рассматриваемого ниже. Если успешно локализовать первое изображение нельзя, то анализируют следующий кадр с использованием попиксельного сравнения. Этот процесс продолжается до тех пор, пока изображение не будет успешно локализовано, или до тех пор, пока не будет определено, что нельзя локализовать ни одно изображение. Если нельзя локализовать ни одно изображение, то росчерк теряется (т.е. положение росчерка определить нельзя). После этого центры нелокализованных изображений будут называться «начальными» точками, поскольку эти точки будут использоваться в качестве базиса для определения положения тех изображений, которые еще не локализованы, вдоль траектории 601 росчерка. Таким образом, центр каждого кадра, успешно локализованного с использованием узора или попиксельного сравнения, оказывается начальной точкой.
Возвращаясь к фиг.8, отмечаем, что на этом графике показаны различные точки 801А-801Х, каждая из которых является центром изображения 701А-701Х, соответственно. На этом чертеже точки, обозначенные кружочками, являются начальными точками. Таким образом, точки 801А, 801С, 801F, 801I, 801K, 801O, 801Q, 801T и 801Х являются начальными точками. Точки, обозначенные звездочкой, являются центрами изображений, которые еще не локализованы (т.е. изображений, которые захватили некоторую не идентифицированную часть документа). Таким образом, точки 801B, 801D, 801E, 801G, 801H, 801J, 801L, 801M, 801N, 801P, 801R, 801S, 801U, 801V и 801W являются нелокализованными точками.
Обращаясь теперь к фиг.10А, отмечаем, что на этапе 1001 сегментируют последовательность изображений (или кадров). Более конкретно, последовательность кадров делят на группы таким образом, что каждая группа соответствует относительно линейной части траектории 601 росчерка. Эта сегментация обеспечивает точную интерполяцию положения нелокализованных изображений в сегменте на основании положения локализованных изображений в этом сегменте, как будет подробнее рассмотрено ниже. Чтобы определить сегменты для некоторого росчерка, модуль 905 сегментации идентифицирует начальные точки поворота для этого росчерка. Начальные точки поворота - это точки, которые находятся в местоположениях, где росчерк изменяет направление, или около таких местоположений. Кроме того, первая и последняя начальные точки в росчерке тоже будут считаться начальными точками поворота.
1
Один процесс сегментации последовательности изображений 701А-701Х для траектории 601 росчерка графически проиллюстрирован на фиг.11 и 12. Как первая начальная точка 801А, так и последняя начальная точка 801Х считаются начальными точками поворота, как отмечалось ранее. Таким образом, начальные точки 801А и 801Х поворота определяют между собой один сегмент траектории 601 росчерка. Чтобы определить дополнительные начальные точки поворота для траектории 601 росчерка, модуль 905 сегментации генерирует линию 1101 между первой начальной точкой 801А поворота и последней начальной точкой 801Х поворота, как показано на фиг.11. Затем начальную точку 801О, наиболее удаленную от линии 1101 (на расстояние, превышающее пороговую величину, такую как 0,5 пиксела, как будет описано ниже), идентифицируют как начальную точку поворота. Таким образом, модуль 905 сегментации обозначает начальную точку 801О, находящуюся на расстоянии d от линии 1101, как начальную точку поворота. Такое определение начальной точки 810О приводит к делению последовательности изображений 710А-710Х на два сегмента. Первый сегмент, СЕГ1, соответствует части траектории 601 росчерка между начальной точкой 801А поворота и начальной точкой 801О поворота, а второй сегмент, СЕГ2, соответствует части траектории 601 росчерка между начальной точкой 801О поворота и начальной точкой 801Х поворота.
2
Модуль 905 сегментации продолжает делить каждый сегмент на меньшие сегменты до тех пор, пока каждый сегмент не станет соответствовать части росчерка, которая является относительно прямолинейной. Например, в случае траектории 601 росчерка, модуль 905 сегментации будет делить первый сегмент СЕГ1 на меньшие сегменты. Более конкретно, модуль сегментации будет генерировать линию 1201 между концевыми точками сегмента СЕГ1 (т.е. между начальной точкой 801А поворота и начальной точкой 810О поворота). Затем модуль 905 сегментации идентифицирует начальную точку, наиболее удаленную от линии 1201. Таким образом, модуль 905 сегментации обозначает начальную точку 801F, находящуюся на расстоянии d от линии 1201, как начальную точку поворота. Такое определение начальной точки 810F приводит к делению последовательности изображений 710А-710О на два сегмента. Первый сегмент, СЕГ1А, соответствует части траектории 601 росчерка между начальной точкой 801А поворота и начальной точкой 801F поворота, а второй сегмент, СЕГ1В, соответствует части траектории 601 росчерка между начальной точкой 801F поворота и начальной точкой 801О поворота.
Модуль 905 сегментации продолжает делить каждый сегмент изображений до тех пор, пока каждый сегмент изображений не станет соответствовать части росчерка, которая является, по существу, линейной. Например, если модуль 905 сегментации генерирует линию между двумя начальными точками поворота, образующими сегмент, и нет начальных точек, отстоящих от упомянутой линии дальше, чем на некоторое пороговое расстояние, то модуль сегментации больше не будет делить сегмент. В некоторых вариантах осуществления изобретения пороговое значение может представлять собой, например, расстояние 0,5 элемента (например, пиксела), используемое для определения отдельных местоположений в документе (например, с помощью декартовой системы координат). Конечно, можно использовать и большее пороговое значение, обеспечивая тем самым соответствие сегментов изображений частям росчерка, которые менее линейны. Можно также использовать меньшее пороговое значение, тем самым обуславливая соответствие сегментов изображений частям росчерка, которые более линейны.
После того, как модуль 905 сегментации идентифицировал все начальные точки поворота в росчерке, этот модуль уточняет положение и перспективное преобразование начальных точек поворота. Более конкретно, модуль 905 сегментации сравнивает каждое изображение 701, соответствующее начальной точке 801 поворота, с электронной версией документа, чтобы точнее определить местоположение и перспективное преобразование начальной точки 801 поворота. Этот процесс сравнения можно воплотить с использованием любого желаемого известного способа, например, такого как способ, описанный в Техническом отчете MSR-TR-97-23 об исследованиях фирмы Microsoft под названием “Panoramic Image Mosaics”, авторами которого являются Heung-Yeung Shum и Richard Szeliski и который опубликован 1 сентября 1997 г. и обновлен в октябре 2001 г. Уточнение начальных точек поворота завершает процесс деления последовательности изображений на сегменты.
Помимо более точного определения положения начальных точек 801 поворота (и связанных с ними изображений 701), уточнение начальных точек 801 поворота позволяет модулю 905 сегментации повысить точность параметров преобразования, используемых для согласования изображений с соответствующими им частями документа. Как подробно рассмотрено выше, наклон и поворот пера 201 вызывает поворот и масштабирование изображений, захватываемых съемочной камерой, по отношению к фактическому внешнему виду документа. Чтобы точнее сравнить изображение с частью документа, нужно деформировать изображение для компенсации изменения в повороте и масштабе, вносимого посредством наклона и поворота пера 201. Например, на фиг.13 показано первоначальное изображение 1301. При этом на фиг.14 показано то же самое изображение после деформирования в соответствии с параметрами деформационного преобразования.
За счет более точного сравнения начальных точек поворота с электронной версией документа, модуль 905 сегментации может изменять параметры преобразования, чтобы точнее деформировать изображение для согласования с документом. В различных вариантах осуществления изобретения модуль 905 сегментации может изменять единственный набор параметров преобразования, применимый ко всем захваченным изображениям в последовательности. Однако в еще одних вариантах осуществления изобретения модуль 905 сегментации создает специальный набор параметров преобразования для каждой начальной точки поворота. Как будет подробнее рассмотрено ниже, наличие специального набора параметров преобразования для каждой начальной точки поворота обеспечивает более точное интерполирование соседних нелокализованных точек. Хотя наклон и поворот пера 201 можно изменять в широких пределах на протяжении всего росчерка в целом, наклон и поворот пера 201 в типичном случае не будут значительно изменяться на коротком расстоянии одного сегмента росчерка. Соответственно, параметры преобразования для каждой начальной точки поворота можно изменять для более точного деформирования изображений, захваченных непосредственно перед изображением, соответствующим начальной точке поворота, или непосредственно после такого изображения.
После того, как модуль 905 сегментации сегментирует изображения 701А-701Х, модуль 907 завершения сегментов обрабатывает каждый сегмент изображений, чтобы определить положение нелокализованных изображений в каждом сегменте. Так, на этапе 1003 модуль 907 завершения сегментов принимает изображения в первом сегменте. Затем, на этапе 1005, модуль 907 завершения сегментов определяет, завершен ли сегмент. Модуль 907 завершения сегментов определит, что сегмент завершен, если этот сегмент включает в себя, по меньшей мере, одну начальную точку, которая является начальной точкой поворота. То есть, если положение, по меньшей мере, одной точки в сегменте, не являющейся начальной точкой поворота, было ранее определено из узора, захваченного в изображении, или иным способом, то сегмент завершен. При этом обстоятельстве, сегмент является достаточно линейным, чтобы можно было определить местоположения всех изображений в сегменте посредством линейной интерполяции. Кроме того, модуль 907 будет определять, что сегмент завершен, после того, как каждое нелокализованное изображение в этом сегменте окажется согласованным с соответствующей частью документа.
Если сегмент не завершен, то на этапе 1007 модуль 907 завершения сегментов принимает первое необработанное (т.е. нелокализованное) изображение в сегменте. (Первое изображение в каждом сегменте будет начальной точкой поворота с известным положением.) На этапе 1008 модуль завершения сегментов деформирует изображение для сравнения с документом, как будет подробно рассмотрено ниже. Затем, на этапе 1009, модуль 907 завершения сегментов определяет область поиска необработанного изображения. Область поиска необработанного изображения в сегменте определяется на основании максимальной оцененной скорости пера 201. Как будет очевидно для специалиста в данной области техники, пользователь, пишущий пером 201, сможет лишь перемещать перо 201 на максимальной скорости в соответствии с физическим носителем, отображающим документ. Максимальную скорость и физический носитель для пера 201 конкретного типа можно определить, например, посредством эксперимента.
Таким образом, центр области поиска первого необработанного изображения может быть первой начальной точкой поворота в сегменте, при этом радиус области поиска ограничен максимальной скоростью пера 201, умноженной на интервал времени между захватом изображения, соответствующего первой начальной точке поворота в сегменте, и захватом первого необработанного изображения в сегменте. В различных вариантах осуществления изобретения, необработанное изображение будет деформироваться для сравнения с использованием параметров преобразования первой начальной точки поворота в сегменте, как отмечалось ранее. Однако в еще одних вариантах осуществления изобретения необработанное изображение можно деформировать с использованием параметров преобразования ранее локализованного изображения в сегменте независимо от того, было ли предыдущее изображение начальной точкой поворота. После деформирования необработанного изображения, модуль 907 завершения сегментов может провести попиксельное сравнение деформированного первого необработанного изображения с областью поиска в документе, чтобы определить часть документа, захваченную в первом необработанном изображении. Посредством попиксельного сравнения можно, например, определить значения корреляции между первым необработанным изображением и каждой частью документа в области поиска.
Модуль 907 завершения сегментов определит, что необработанное изображение соответствует части документа, дающей наибольшее значение корреляции. Точно локализуя необработанное изображение таким образом, модуль 907 завершения сегментов также определит местоположение точки, соответствующей необработанному изображению. Расстояние между локализованной точкой первого необработанного изображения и первой начальной точкой поворота укажет скорость, с которой на самом деле двигалось перо 201. На основании определенного местоположения необработанного изображения, модуль 907 завершения сегментов также может обновлять параметры преобразования, уточняя захваченные изображения (т.е. согласовывая захваченное изображение с изображением в документе для получения перспективного преобразования) с целью использования при деформировании следующего необработанного изображения, как отмечалось выше. Сразу же после определения фактической скорости движения пера 201 и обновления параметров преобразования, необработанное изображение будет считаться обработанным.
На этапе 1015 модуль 907 завершения сегментов определяет, имеются ли еще необработанные изображения в сегменте. Если имеются, то модуль 907 завершения сегментов повторяет этап 1007, принимая текущее необработанное изображение. Затем, на этапе 1009, модуль 907 завершения сегментов определяет область поиска для текущего необработанного изображения. Применительно ко второму и каждому последующему необработанному изображению в сегменте, область поиска будет определяться на основании фактической скорости пера 201, определенной в результате локализации предыдущего необработанного изображения. Например, центр области поиска может находиться в точке, соответствующей предыдущему необработанному изображению. Тогда модуль 907 завершения сегментов сможет определять радиус области поиска на основании фактической скорости пера, вычисленной в результате нахождения местоположения точки для предыдущего необработанного изображения. Более конкретно, радиус области поиска можно определить путем умножения фактической скорости пера, вычисленной, исходя из положения предыдущего необработанного изображения, на интервал времени между двумя захваченными изображениями.
Как будет очевидно для специалистов в данной области техники, пользователь, пишущий пером 201, сможет лишь изменять скорость пера 201 посредством использования максимального значения ускорения. Это максимальное значение ускорения можно вычислить, например, с помощью эксперимента или на основании фактического ускорения между ранее локализованными изображениями. Соответственно, в некоторых вариантах осуществления изобретения радиус области поиска для второго и последующих необработанных изображений можно изменять посредством использования максимального значения ускорения. Например, в росчерке возможны три изображения f1, f2, f3, которые захватываются в моменты t1, t2 и t3 и имеют центры в точках р1, р1 и р3. Если место точек р1 и р2 можно определить, то скорость V пера между захватами этих изображений составляет V=(p2-p1)/(t2-t1). Если значение ускорения оказывается между -А и А, то область поиска для точки р3 будет отцентрирована вокруг места Р=р2+V·(t3-t2), при этом площадь области поиска будет иметь пределы
[P-A·(t3-t2)·(t3-t2)/2; P+A·(t3-t2)·(t3-t2)/2.
После того, как модуль 905 завершения сегментов определил область поиска для текущего необработанного изображения, этот модуль 905 завершения сегментов деформирует необработанное изображение и проводит попиксельное сравнение деформированного необработанного изображения с областью поиска в документе на этапе 1011. И опять же, часть документа, которая дает наибольшее значение корреляции, выбирают в качестве местоположения для текущего необработанного изображения. Затем модуль 905 завершения сегментов вычисляет новую скорость для пера 201 на основании расстояния между точкой текущего необработанного изображения и точкой предыдущего необработанного изображения. Этот модуль также обновляет параметры преобразования на основе идентифицированного местоположения текущего необработанного изображения, тем самым обрабатывая это изображение. Затем модуль 905 завершения сегментов повторяет этап 1015, чтобы определить, остаются ли еще какие-либо нелокализованные изображения в текущем сегменте.
Модуль 905 завершения сегментов повторяет этапы 1007 и 1015 до тех пор, пока в текущем сегменте больше не останется нелокализованных изображений. Затем, на этапе 1017, модуль 905 завершения сегментов определяет, есть ли еще сегменты в последовательности изображений. Если сегменты еще есть, то модуль 905 завершения сегментов повторяет этапы 1013-1015 до тех пор, пока не будут завершены все сегменты в последовательности изображений.
После того, как все сегменты будут завершены, каждое изображение в росчерке будет локализовано в документе. Некоторые факторы, например, такие как неправильные начальные параметры преобразования и смазанные контуры при перемещении, могут привести к ошибочным результатам локализации для одного или более локализованных изображений. Поэтому в различных вариантах осуществления изобретения используется модуль 909 удаления результатов, предназначенный для удаления ошибочных местоположений из результатов на этапе 1019.
Модуль 909 удаления результатов может, например, поддерживать местоположение каждой из начальных точек для последовательности изображений. Далее, модуль 909 удаления результатов может пройти по каждой точке вдоль всей траектории росчерка, анализируя каждую точку, при этом будет соблюдаться порядок следования от первой точки к последней точке. Более конкретно, вычисляется скорость от предыдущей точки до текущей точки и от текущей точки до следующей точки. Исходя из этих двух значений скорости, также вычисляется ускорение. Если либо скорость, либо ускорение превышает максимум, то местоположение текущей точки считается ошибочным и удаляется из результатов.
В различных вариантах осуществления изобретения, модуль 909 удаления результатов может повторять анализ каждой точки, но, в отличие от вышеизложенного, проводить анализ каждой точки в обратном порядке - от последней точки к первой точке. Таким образом, вычисляется скорость от следующей точки до текущей точки и от текущей точки до предыдущей точки. Исходя из этих двух значений скорости, также вычисляется ускорение. Если либо скорость, либо ускорение превышает максимум, то местоположение текущей точки считается ошибочным и удаляется из результатов. После удаления всех ошибочных точек, местоположения удаленных точек можно определять посредством интерполирования.
Заключение
Хотя изобретение описано применительно к конкретным примерам, включая предпочтительные в настоящее время режимы осуществления изобретения, для специалистов в данной области техники будет очевидно, что возможны многочисленные изменения и перестановки вышеописанных систем и способов, находящиеся в рамках объема изобретения, охарактеризованного в прилагаемой формуле изобретения.