Местная локализация с использованием быстрого согласования изображений

Местная локализация с использованием быстрого согласования изображений

Иллюстрации

Показать все

Реферат

Область техники, к которой относится изобретение

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

Предшествующий уровень техники

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

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

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

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

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

Краткое изложение сущности изобретения

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

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

Перечень фигур чертежей

Фиг.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, показано здесь в целях иллюстрации в виде квадрата, поле зрения камеры может предусматривать другие формы, как известно в данной области техники.

Изображения, захваченные камерой 203, можно охарактеризовать как последовательность кадров {I_i} изображения, где I_i захватывается пером 201 за время t_i выборки. Скорость выборки может быть большой или малой, в зависимости от конфигурации системы и требования эффективности. Размер кадра захваченного изображения может быть большим или малым, в зависимости от конфигурации системы и требования эффективности. Кроме того, должно быть ясно, что изображение, захваченное камерой 203, может прямо или косвенно использоваться обрабатывающей системой или может подвергаться предварительной фильтрации. Эта предварительная фильтрация может осуществляться в пере 201 или может осуществляться вне пера 201 (например, в персональном компьютере).

На фиг.2А также показана плоскость 209 изображения, в которой формируется изображение 210 узора из местоположения 204. Свет, принимаемый от узора в предметной плоскости 207, фокусируется линзой 208. В соответствии с различными вариантами осуществления изобретения, линза 208 может представлять собой одиночную линзу или многоэлементную линзовую систему, но в данном случае для простоты представлена в виде одиночной линзы. Датчик 211 захвата изображения захватывает изображение 210.

Датчик 211 изображения может быть достаточно большим, чтобы захватить изображение 210. В альтернативном варианте, датчик 211 изображения может быть достаточно большим, чтобы захватить изображение кончика 202 пера в местоположении 212. Для справки отметим, что изображение в местоположении 212 будет считаться виртуальным кончиком пера. Следует заметить, что местоположение виртуального кончика пера относительно датчика 211 изображения является фиксированным ввиду неизменной взаимосвязи между кончиком пера, линзой 208 и датчиком 211 изображения.

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

L_бумаги=F_S→P(L_{датчика}).

Во время письма, кончик пера и бумага находятся в одной и той же плоскости. Соответственно, преобразование из виртуального кончика пера в реальный кончик пера также будет преобразованием F_S→P:

L_{кончика пера}=F_S→P(L_{виртуального кончика пера}).

Преобразование F_S→P можно оценить как аффинное преобразование. Оно представляется в упрощенной форме как

т.е. как оценка преобразования F_S→P, где θ_x, θ_y, s_x и s_y представляют собой поворот и масштаб двух ориентаций узора, захваченного в местоположении 204. Кроме того, можно получить уточнение F'_S→P путем согласования захваченного изображения с соответствующим реальным изображением на бумаге. «Получить уточнение» означает получить более точную оценку преобразования F_S→P с помощью некой разновидности алгоритма оптимизации, называемой рекурсивным методом. Рекурсивный метод рассматривает матрицу F'_S→P в качестве начального значения. Уточненная оценка точнее описывает преобразование между S и P.

Местоположение виртуального кончика пера можно определить с еще большей точностью путем калибровки. Чтобы калибровать местоположение виртуального кончика пера, пользователь располагает кончик 202 пера в фиксированном местоположении L_{кончика пера} на бумаге. Затем пользователь наклоняет перо, давая камере 203 возможность захватить ряд изображений при разных положениях пера. Для каждого захваченного изображения получается преобразование F_S→P. Из этого преобразования можно получить местоположение виртуального кончика пера, L_{виртуального кончика пера}:

(L_{виртуального кончика пера})=F_P→S(L_{кончика пера}),

где L_{кончика пера} инициализируется как (0, 0) и

F_P→S=(F_S→P)^-1.

Усредняя 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 росчерка. Таким образом, центр ка