Определение расположения штрихов посредством декодирования m-массива и быстрого сравнения изображений

Определение расположения штрихов посредством декодирования m-массива и быстрого сравнения изображений

Иллюстрации

Показать все

Реферат

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

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

Уровень техники

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

Одним методом захвата рукописной информации является использование пера, расположение которого может определяться во время записи. Одним пером, которое обеспечивает такую возможность, является перо Anoto компании Anoto Inc. Это перо действует с использованием камеры для захвата изображения бумаги, кодируемого по предопределенной структуре. Пример структуры изображения приведен на фиг.11. Данная структура используется пером Anoto (компании Anoto Inc.) для определения расположения пера на участке бумаги. Однако неясно, насколько эффективно определение расположения при помощи системы, используемой пером Anoto. Чтобы получить эффективное определение расположения захваченного изображения, необходима система, которая обеспечивает эффективное декодирование захваченного изображения.

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

Раскрытие изобретения

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

Согласно другому аспекту изобретения последовательность изображений захватывается камерой, которая расположена в пере. Траектория кончика пера определяется посредством декодирования связанной лабиринтной структуры (m-массива) и сравнения захваченных изображений с изображениями документа.

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

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

Краткое описание чертежей

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

Фиг.1 - общее описание компьютера, который может использоваться вместе с вариантами выполнения настоящего изобретения.

Фиг.2А и 2В - система захвата изображений и соответствующее захваченное изображение согласно вариантам выполнения настоящего изобретения.

Фиг.3А-3F - различные последовательности и методы свертки согласно вариантам выполнения настоящего изобретения.

Фиг.4А-4Е - различные системы кодирования согласно вариантам выполнения настоящего изобретения.

Фиг.5А-5D - четыре возможных результирующих уголка, связанных с системой кодирования по фиг.4А и 4В.

Фиг.6 - поворот части захваченного изображения согласно вариантам выполнения настоящего изобретения.

Фиг.7 - различные углы поворота, используемые вместе с системой кодирования по фиг.4А-4Е.

Фиг.8 - процесс определения расположения захваченного массива согласно вариантам выполнения настоящего изобретения.

Фиг.9 - способ определения расположения захваченного изображения согласно вариантам выполнения настоящего изобретения.

Фиг.10 - другой способ определения расположения захваченного изображения согласно вариантам выполнения настоящего изобретения.

Фиг.11 - представление пространства кодирования в документе согласно известному уровню техники.

Фиг.12 - блок-схема последовательности операций для декодирования извлеченных битов из захваченного изображения согласно вариантам выполнения настоящего изобретения.

Фиг.13 - выбор битов из извлеченных битов из захваченного изображения согласно вариантам выполнения настоящего изобретения.

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

Фиг.15 - способ определения траектории кончика пера из последовательности захваченных кадров согласно варианту выполнения настоящего изобретения.

Фиг.16 - устройство для определения траектории кончика пера из последовательности захваченных кадров согласно варианту выполнения настоящего изобретения.

Фиг.17 - пример захваченного изображения согласно варианту выполнения изобретения.

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

Фиг.19 - анализ лабиринтной структуры захваченного изображения согласно варианту выполнения изобретения.

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

Фиг.21 - результат анализа изображения документа согласно варианту выполнения изобретения.

Фиг.22 - результат глобального определения расположения для примерного штриха согласно варианту выполнения изобретения.

Фиг.23 - результат локального определения расположения для примерного штриха согласно варианту выполнения изобретения.

Фиг.24 - восстановленный штрих кончика пера и траектория соответствующих центров захваченных изображений согласно варианту выполнения изобретения.

Фиг.25 - фактический штрих, который соответствует восстановленному штриху, как показано на фиг.24.

Осуществление изобретения

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

Нижеследующее разделяется подзаголовками для удобства читателя. Подзаголовки включают в себя: Термины, Компьютер общего назначения, Захватывающее изображение перо, Кодирование массива, Декодирование, Коррекция ошибок, Определение расположения, Декодирование m-массива и Архитектура для определения траектории пера.

Термины

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

Камера - система захвата изображения, которая может захватывать изображение с бумаги или любой другой среды.

Компьютер общего назначения

На фиг.1 представлена функциональная блок-схема примера обычной цифровой вычислительной среды общего назначения, которая может использоваться для осуществления различных аспектов настоящего изобретения. На фиг.1 компьютер 100 включает в себя блок 110 обработки, системную память 120 и системную шину 130, которая соединяет различные компоненты системы, включая системную память с блоком 110 обработки. Системная шина 130 может быть любой из нескольких типов шинных структур, включая шину памяти или контроллер памяти, периферийную шину и локальную шину, используя любую из множества шинных архитектур. Системная память 120 включает в себя постоянное запоминающее устройство (ПЗУ) 140 и оперативное запоминающее устройство (ОЗУ) 150.

Базовая система 160 ввода-вывода (БСВВ), содержащая базовые подпрограммы, которые способствуют переносу информации между элементами внутри компьютера 100, например во время запуска, хранится в ПЗУ 140. Компьютер 100 также включает в себя накопитель 170 на жестких дисках для считывания и записи на жесткий диск (не показан), накопитель 180 на магнитных дисках для считывания или записи на съемный магнитный диск 190 и накопитель 191 на оптических дисках для считывания или записи на съемный оптический диск 192, такой как компакт-диск или другой оптический носитель. Накопитель 170 на жестких дисках, накопитель 180 на магнитных дисках и накопитель 191 на оптических дисках подсоединены к системной шине 130 при помощи интерфейса 192 накопителя на жестких дисках, интерфейса 193 накопителя на магнитных дисках и интерфейса 194 накопителя на оптических дисках, соответственно. Накопители и связанные с ними считываемые компьютером носители обеспечивают энергонезависимое хранение считываемых компьютером инструкций, структур данных, программных модулей и других данных для персонального компьютера 100. Для специалиста в данной области техники понятно, что в примерной операционной среде также могут использоваться другие типы считываемых компьютером носителей, которые могут хранить данные, к которым может обращаться компьютер, такие как магнитные кассеты, карты флэш-памяти, цифровые видеодиски, картриджи Бернулли, оперативные запоминающие устройства (ОЗУ), постоянные запоминающие устройства (ПЗУ) и т. п.

Ряд программных модулей может храниться на накопителе 170 на жестких дисках, магнитном диске 190, оптическом диске 192, в ПЗУ 140 или ОЗУ 150, включая операционную систему 195, одну или несколько программ 196 приложений, другие программные модули 197 и программные данные 198. Пользователь может вводить команды и информацию в компьютер 100 при помощи устройств ввода, таких как клавиатура 101 и указательное устройство 102. Другие устройства ввода (не показаны) могут включать в себя микрофон, джойстик, игровой планшет, антенну спутниковой связи, сканер или т. п. Эти и другие устройства ввода часто подключаются к блоку 110 обработки через интерфейс 106 последовательного порта, который подключается к системной шине, но может подключаться при помощи других интерфейсов, таких как параллельный порт, игровой порт или универсальную последовательную шину (УПШ). Далее, эти устройства могут подключаться непосредственно к системной шине 130 через соответствующий интерфейс (не показан). Монитор 107 или устройство отображения другого типа также подключается к системной шине 130 через интерфейс, такой как видеоадаптер 108. В дополнение к монитору персональные компьютеры обычно включают в себя другие периферийные устройства вывода (не показаны), такие как громкоговорители и принтеры. В предпочтительном варианте выполнения предусмотрены перьевой дигитайзер 165 и сопровождающее перо или стило 166 для захвата изображения цифровым методом ввода, выполненного от руки. Хотя показано непосредственное соединение между перьевым дигитайзером 165 и последовательным портом, на практике перьевой дигитайзер 165 может подключаться к блоку 110 обработки непосредственно, через параллельный порт или другой интерфейс и системную шину 130, что известно в данной области техники. Кроме того, хотя дигитайзер 165 показан отдельно от монитора 107, предпочтительно, чтобы используемая область ввода дигитайзера 165 была совмещена с областью отображения монитора 107. Далее, дигитайзер 165 может быть встроен в монитор 107 или может существовать в качестве отдельного устройства, покрывающего или иным образом присоединенного к монитору 107.

Компьютер 100 может работать в сетевой среде, используя логические подключения к одному или нескольким удаленным компьютерам, таким как удаленный компьютер 109. Удаленным компьютером 109 может быть сервер, маршрутизатор, сетевой персональный компьютер (ПК), одноранговое устройство или другой общий сетевой узел и обычно включает в себя многие или все элементы, описанные выше в отношении компьютера 100, хотя только устройство 111 хранения памяти изображено на фиг.1. Логические подключения, изображенные на фиг.1, включают в себя локальную сеть (ЛС) 112 и глобальную сеть (ГС) 113. Такие сетевые среды общеприняты в офисах, компьютерных сетях масштаба предприятия, интрасетях и Интернете.

При использовании в сетевой среде ЛС компьютер 100 подключается к локальной сети 112 при помощи сетевого интерфейса или адаптера 114. При использовании в сетевой среде ГС персональный компьютер 100 обычно включает в себя модем 115 или другое средство для установления связи по глобальной сети 113, такой как Интернет. Модем 115, который может быть внутренним или внешним, подключается к системной шине 130 при помощи интерфейса 106 последовательного порта. В сетевой среде программные модули, описанные в отношении персонального компьютера 100 или его частей, могут храниться на удаленном устройстве хранения.

Понятно, что показанные сетевые подключения являются иллюстративными, и могут использоваться другие методы для установления линии связи между компьютерами. Предполагается существование любых из множества общеизвестных протоколов, таких как TCP/IP (протокол управления передачей/протокол Интернета), Ethernet, FTP (протокол передачи файлов), TTP (протокол передачи гипертекста), Bluetooth, IEEE 802.11х и аналогичные, и система может работать в конфигурации клиент-сервер, позволяющей пользователю получать веб-страницы с веб-сервера. Можно использовать любые из многочисленных обычных веб-браузеров для отображения и манипулирования данными на веб-страницах.

Захватывающее изображение перо

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

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

На фиг.2А и 2В приведен иллюстративный пример пера 201 с камерой 203. Перо 201 включает в себя кончик 202, который может включать в себя или может не включать в себя емкость с чернилами. Камера 203 захватывает изображение 204 с поверхности 207. Перо 201 может дополнительно включать в себя дополнительные датчики и/или процессоры, как представлено пунктирным прямоугольником 206. Эти датчики и/или процессоры 206 также могут включать в себя возможность передачи информации на другое перо 201 и/или персональный компьютер (например, по Bluetooth или другим беспроводным протоколам).

На фиг.2В представлено изображение, наблюдаемое камерой 203. В одном иллюстративном примере поле зрения камеры 203 (т.е. разрешение датчика изображения камеры) составляет 32х32 пиксела (где N=32). В одном варианте выполнения захваченное изображение (32 пиксела на 32 пиксела) соответствует области примерно 5 мм на 5 мм плоскости поверхности, захватываемой камерой 203. Следовательно, на фиг.2В показано поле зрения с длиной 32 пиксела и шириной 32 пиксела. Размер N является настраиваемым, так что большие N соответствуют более высокому разрешению изображения. Также, хотя поле зрения камеры 203 показано квадратным для целей иллюстрации в данном случае, поле зрения может включать в себя другие формы, что известно в данной области техники.

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

Изображение, захватываемое камерой 203, может использоваться непосредственно системой обработки или может подвергаться префильтрации. Данная префильтрация может происходить в пере 201 или может происходить вне пера 201 (например, в персональном компьютере).

Размер изображения на фиг.2В составляет 32х32 пиксела. Если размер каждой единицы кодирования составляет 3х3 пиксела, то тогда количество захваченных кодированных единиц составит примерно 100 единиц. Если размер единицы кодирования составляет 5х5 пикселов, то тогда количество захваченных кодированных единиц составляет примерно 36.

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

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

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

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_{виртуальный-кончик пера}.

Теперь известно расположение виртуального кончика пера L_{виртуальный-кончик пера}. Также можно получить преобразование F _S→P из захваченных изображений. Наконец, можно использовать эту информацию для определения расположения реального кончика пера L_{кончик пера}:

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

Кодирование массива

Двумерный массив может быть составлен посредством свертки одномерной последовательности. Любая часть двумерного массива, содержащая достаточно большое количество битов, может использоваться для определения ее расположения в полном двумерном массиве. Однако может быть необходимым определить расположение из захваченного изображения или нескольких захваченных изображений. Чтобы минимизировать возможность сопоставления части захваченного изображения с двумя или более расположениями в двумерном массиве, может использоваться неповторяющаяся последовательность для создания массива. Одним свойством создаваемой последовательности является то, что последовательность не повторяется по длине (или окну) n. Нижеследующее описывает создание одномерной последовательности посредством свертки последовательности в массив.

Составление последовательности

Последовательность чисел может использоваться в качестве начальной точки системы кодирования. Например, последовательность (также упоминаемая как m-последовательность) может быть представлена как q-элемент, установленный в поле F_q. В данном случае q=pⁿ, где n≥1 и p представляет собой простое число. Последовательность или m-последовательность может генерироваться посредством множества различных методов, включая, но не ограничиваясь им, деление многочленов. Используя деления многочленов, последовательность может определяться следующим образом:

где P_n(x) представляет собой примитивный многочлен степени n в поле F_q[x] (имеющем qⁿ элементов). R_l(x) представляет собой ненулевой многочлен степени l (где l<n) в поле F_q[x]. Последовательность может создаваться с использованием итерационной процедуры с двумя этапами: во-первых, деления двух многочленов (получая в результате элемент поля F_q) и, во-вторых, умножения остатка на x. Вычисление останавливается, когда выходной результат начинает повторяться. Этот процесс может быть реализован с использованием линейного регистра сдвига с обратными связями, как описано в статье Douglas W. Clark and Lih-Jyh Weng, "Maximal and Near-Maximal Shift Register Sequences: Efficient Event Counters and Easy Discrete Logarithms," IEEE Transactions on Computers 43.5 (May 1994, pp 560-568). В данном варианте выполнения устанавливается зависимость между циклическим сдвигом последовательности и многочленом R_l(x): изменение R_l(x) только циклически сдвигает последовательность, и каждый циклический сдвиг соответствует многочлену R_l(x). Одним из свойств результирующей последовательности является то, что последовательность имеет период qⁿ-1, и внутри периода, по ширине (или длине) n, любая часть присутствует в последовательности один и только один раз. Это называется «свойством окна». Период qⁿ-1 также упоминается как длина последовательности, и n - как порядок последовательности.

Описанный выше процесс является только одним из множества процессов, который может использоваться для создания последовательности со свойством окна.

Составление массива

Массив (или m-массив), который может использоваться для создания изображения (часть которого может захватываться камерой), представляет собой расширение одномерной последовательности или m-последовательности. Пусть А будет массив с периодом (m₁, m₂), а именно A(k+m₁,l)=A(k,l+m₂)=A(k,l). Когда окно n₁ × n₂ сдвигается на период A, все ненулевые матрицы n₁ × n₂ по F_q появляются один раз и только один раз. Это свойство также упоминается как «свойство окна» в том, что каждое окно является однозначным.

Двоичный массив (или m-массив) может быть составлен посредством свертки последовательности. Одним принципом является получение последовательности, затем свертка ее до размера m₁ × m₂, где длина массива составляет L = m₁ × m₂ = 2ⁿ - 1. Альтернативно, можно начать с предопределенного размера пространства, которое хотят охватить (например, один лист бумаги, 30 листов бумаги или размер монитора компьютера), определить область (m₁ × m₂), затем использовать размер, чтобы получить L ≥ m₁ × m₂, где L = 2ⁿ - 1.

Можно использовать множество различных методов свертки. Например, на фиг.3А-3С показаны три различные последовательности. Каждая из них может быть свернута в массив, показанный на фиг.3D. Показаны три различных способа свертки, наложение на фиг.3D и траектории растра на фиг.3Е и 3F. Авторы принимают способ свертки, показанный на фиг.3D.

Для создания способа свертки, показанного на фиг.3D, создают последовательность {a_i} длиной L и порядка n. Затем создается массив {b_kl} размера m₁ × m₂, где наибольший общий делитель (m₁,m₂) = 1 и L = m₁ × m₂, из последовательности {a_i}, вычисляя каждый бит массива так, как показано в уравнении 1:

b_kl=a_i, где k=i mod(m₁), l=i mod(m₂), i=0,..., L-1(1)

Данный принцип свертки может быть альтернативно выражен как размещение последовательности по диагонали массива, затем продолжая с противоположного края при достижении края.

На фиг.4А показаны методы кодирования выборки, которые могут использоваться для кодирования массива по фиг.3D. Понятно, что могут использоваться другие методы кодирования. Например, альтернативный метод кодирования показан на фиг.11.

Ссылаясь на фиг.4А, первый бит 401 (например, «1») представляется столбцом темных чернил. Второй бит 402 (например, «0») представляется строкой темных чернил. Понятно, что могут использоваться чернила любого цвета, чтобы представлять различные биты. Единственным требованием к цвету выбираемых чернил является то, чтобы они обеспечивали существенный контраст по сравнению с фоном среды, чтобы быть различимыми системой захвата изображения. Биты на фиг.4А представлены матрицей 3х3 ячеек. Размер матрицы может модифицироваться, чтобы он равнялся любому размеру, основанному на размере и разрешении системы захвата изображения. Альтернативное представление битов 0 и 1 показано на фиг.4С-4Е. Понятно, что представление единицы или нуля для кодирования выборки по фиг.4А-4Е может переключаться безрезультатно. На фиг.4С показаны представления битов, занимающих две строки или столбца с чередованием. На фиг.4D показано альтернативное расположение пикселов строками и столбцами в виде пунктира. Наконец, на фиг.4Е показаны представления пикселов столбцами и строками в формате с неравномерными промежутками (например, две темные точки, за которыми следует пустая точка).

Ссылаясь обратно на фиг.4А, если бит представлен матрицей 3х3 и система формирования изображения обнаруживает темную строку и две белые строки в зоне 3х3, то тогда обнаруживается нуль (или единица). Если изображение обнаруживается с темным столбцом и двумя белыми столбцами, то тогда обнаруживается единица (или нуль).

В данном случае для представления бита используется более одного пиксела или точки. Использование одного пиксела (или бита) для представления бита является неустойчивым. Пыль, складки на бумаге, неплоские поверхности и т.п. создают трудности при считывании однобитовых представлений блоков данных. Однако понятно, что могут использоваться различные принципы для графического представления массива на поверхности. Такие принципы показаны на фиг.4С-4Е. Понятно, что также могут использоваться другие принципы. Один принцип изображен на фиг.11 с использованием только смещенных на интервал точек.

Поток битов используется для создания графической структуры 403 на фиг.4В. Графическая структура 403 включает в себя 12 строк и 18 столбцов. Строки и столбцы формируются потоком битов, который преобразуется в графическое представление с использованием представлений 401 и 402 битов. Фиг.4В может рассматриваться как имеющая следующее представление битов:

Декодирование

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

Для определения ориентации захваченного изображения относительно всей кодированной области можно заметить, что не все четыре возможные уголка, показанных на фиг.5А-5D, могут присутствовать в графической структуре 403. Фактически, при правильной ориентации тип уголка, показанный на фиг.5А, не может существовать в графической структуре 403. Поэтому ориентация, при которой отсутствует тип уголка, показанный на фиг.5А, является правильной ориентацией.

Продолжая на фиг.6 изображение, захваченное камерой 601, может анализироваться и может определяться его ориентация, чтобы оно было интерпретируемое в отношении положения, фактически представленного изображением 601. Во-первых, изображение 601 просматривается с целью определения угла θ, необходимого для поворота изображения, так чтобы пикселы были выровнены в горизонтальном и вертикальном направлении. Отмечается, что возможны альтернативные выравнивания сетки, включая поворот лежащей в основе сетки в негоризонтальное и невертикальное расположение (например, 45 градусов). Использование негоризонтального и невертикального размещения может обеспечивать возможное преимущество устранения у пользователя визуальной отвлекаемости, так как пользователи могут иметь тенденцию замечать горизонтальные и вертикальные структуры раньше других. С целью упрощения ориентация сетки (горизонтальная и вертикальная и любой другой поворот лежащей в основе сетки) упоминается вместе как предопределенная ориентация сетки.

Затем изображение 601 анализируется с целью определения, какой уголок отсутствует. Величина поворота о, необходимая для поворота изображения 601 в изображение, готовое для декодирования 603, показана как o = (θ плюс величина поворота {определенная тем, какой уголок отсутствует}). Величина поворота показана равенством на фиг.7. Ссылаясь обратно на фиг.6, угол θ сначала определяется раскладкой пикселов, что приводит к горизонтальному и вертикальному (или другой предопределенной ориентации сетки) размещению пикселов, и изображение поворачивается так, как показано в позиции 602. Затем проводится анализ с целью определения отсутствующего уголка, и изображение 602 поворачивается в изображение 603 для установки изображения для декодирования. В данном случае изображение поворачивается на 90 градусов против часовой стрелки, так что изображение 603 имеет правильную ориентацию и может использоваться для декодирования.

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

Наконец, код в изображении 603 считывается и коррелируется с исходным потоков битов, используемым для создания изображения 403. Корреляция может быть выполнена несколькими способами. Например, она может быть выполнена посредством рекуррентного принципа, при котором восстановленный поток битов сравнивается со всеми другими фрагментами потока битов в исходном потоке битов. Во-вторых, может быть выполнен статистический анализ между восстановленным потоком битов и исходным потоком битов, например, посредством использования расстояния Хемминга между двумя потоками битов. Понятно, что может быть использовано множество принципов для определения расположения восстановленного потока битов в исходном потоке битов.

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

Пусть последовательность (или m-последовательность) I соответствует степенному ряду I(x)=1/P_n(x), где n представляет собой порядок m-последовательности, и захваченное изображение содержит K битов из