Усовершенствованный подход к декодированию m-массива и исправлению ошибок

Усовершенствованный подход к декодированию m-массива и исправлению ошибок

Иллюстрации

Показать все

Реферат

Область изобретения

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

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

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

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

Сущность изобретения

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

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

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

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

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

фиг.2А и 2Б изображают систему захвата изображения и соответствующее захваченное изображение согласно вариантам воплощения настоящего изобретения,

фиг.3А-3Е изображают различные последовательности и способы свертывания согласно вариантам воплощения настоящего изобретения,

фиг.4А-4Д изображают различные системы кодирования согласно вариантам воплощения настоящего изобретения,

фиг.5А-5Г изображают четыре возможных результирующих угла, ассоциированных с системами кодирования согласно фиг.4А и 4Б,

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

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

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

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

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

фиг.11 изображает представление пространства кодирования в документе согласно уровню техники,

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

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

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

Подробное описание предпочтительных вариантов воплощения

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

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

Термины

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

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

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

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

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

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

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

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

Должно быть понятно, что показанные сетевые соединения являются иллюстративными, и могут использоваться другие способы для установления линии связи между компьютерами. Допускается существование любого из различных хорошо известных сетевых протоколов, таких как TCP/IP, Ethernet, FTP, HTTP, Bluetooth, IEEE 802.11x и т.д., и система может работать в конфигурации клиент-сервер, чтобы позволить пользователю осуществлять поиск web страниц из www-сервера. Для отображения и управления данными на web страницах могут использоваться любые из различных известных web браузеров.

Перо захвата изображения

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

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

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

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

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

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

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

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

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

в качестве оценки F_S→P, в которой θx, θy, sx и sy являются вращениями и масштабными множителями двух ориентаций образца, захваченного в местоположении 204. Далее, можно уточнить F'_S→P путем согласования захваченного изображения с соответствующим реальным изображением на бумаге. 'Уточнить' означает получить более точную оценку преобразования F_S→P посредством, например, алгоритма оптимизации, называемого как рекурсивный метод. Рекурсивный метод трактует матрицу F'_S→P как исходное значение. Уточненная оценка описывает преобразование между S и P более точно.

Затем можно определить местоположение виртуального наконечника пера посредством калибровки.

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

где L_pentip инициализируется как (0,0) и

Усредняя L_{virtual-pentip}, полученные из каждого изображения, можно определить местоположение виртуального наконечника пера L_{virtual-pentip}. С известным L_{virtual-pentip} можно получить более точную оценку L_pentip. После нескольких итераций можно определить точное местоположение виртуального наконечника пера L_{virtual-pentip}.

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

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

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

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

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

где Pn(x) является примитивным многочленом степени n в поле Fq[x] (имеющим qn элементов). Rl(x) является ненулевым многочленом степени l (где l<n) в поле Fq[x]. Последовательность может быть создана с использованием итеративной процедуры с двумя шагами: первый, деление двух полиномов (приводящее к элементу поля Fq), и второй, умножение остатка на x. Вычисление останавливается, когда выходное значение начинает повторяться. Данный процесс может быть выполнен, используя регистр сдвига с линейной обратной связью, описанный в статье Douglas W. Clark и 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-последовательности. Пусть A является массивом с периодом (m₁, m₂), а именно Когда окно n₁×n₂ сдвигается на период A, все ненулевые матрицы n₁×n₂ по Fq появляются только один раз. Указанное свойство также называется "свойством окна", при котором каждое окно является уникальным. Затем окно может быть выражено как массив с периодом (m₁, m₂) (где m₁ и m₂ являются горизонтальным и вертикальным числами битов, присутствующих в массиве) и порядком (n₁, n₂).

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

L≥m₁×m₂, где L=2ⁿ-1.

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

Для создания способа свертывания, как показано на фиг.3Г, создают последовательность {a_i} с длиной L и порядком n. Далее создается массив {b_kl} размером m₁×m₂, где наибольший общий делитель gcd(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А показывает способы кодирования, которые могут быть использованы для кодирования массива фиг.3Г. Понятно, что можно использовать другие способы кодирования. Например, альтернативный способ кодирования показан на фиг.11.

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

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

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

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

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

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

Что касается определения ориентации захваченного изображения относительно полной закодированной площади, следует отметить, что не все четыре возможных угла, показанных на фиг.5А-5Г, могут быть представлены на графическом образце 403. В действительности при правильной ориентации тип угла, показанного на фиг.5А, не может существовать на графическом образце 403. Следовательно, ориентация, в которой отсутствует тип угла, показанный на фиг.5А, является правильной ориентацией.

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

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

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

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

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

Допустим, последовательность (или m-последовательность) I соответствует степенному ряду I(x)=1/Pn(x), где n - порядок m-последовательности, и захваченное изображение содержит K битов последовательности I b=(b₀ b₁ b₂ ••• b_K-1)^t, где K≥n, а показатель степени t представляет транспонирование матрицы или вектора. Местоположение s из K битов как раз является числом циклических сдвигов последовательности I, так что b_о сдвигается к началу последовательности. Эта сдвинутая последовательность R соответствует степенному ряду x^s/P_n(x), или R=T^s(I), где T представляет собой оператор циклического сдвига. Авторы нашли s косвенно. Полиномы по модулю P_n(x) формируют поле. Гарантируется, что x ^s ≡r ₀ +r ₁ x+…r _n-1 x ^n-1 mod(P _n (x)). Следовательно, находим (r₀, r₁, …, r_n-1) и затем находим решение для s.

Соотношение x ^s ≡r ₀ +r ₁ x+…r _n-1 x ^n-1 mod(P _n (x)) подразумевает, что R=r ₀ +r ₁ T(I)+…+r _n-1 T ^n-1(I). Записанное в виде бинарного линейного уравнения, выражение становится:

R=r^tA (2)

где r=(r₀, r₁, …, r_n-1)^t, и A=(I T(I)…T ^n-1(I))^t, которое состоит из циклических сдвигов последовательности I от 0-сдвига до (n-l)-сдвига. Теперь в последовательности R доступны только разбросанные K битов для решения r. Допустим, разность показателей между b_t и b₀ в последовательности R составляет k_i, где i=1, 2, …, k-1, тогда 1-ый и (k _i+1) элементы последовательности R, где i=1, 2, …, k-1, равны в точности b ₀ , b ₁ , …, b _k-1. Выбирая 1-ый и (k _i+1) столбцы матрицы A, где i=1, 2, …, k-1, получается следующее бинарное линейное уравнение:

b^t=r^tM (3)

где M является подматрицей размерностью n×K матрицы A.

Если b не содержит ошибок, то решение для r может быть записано в виде:

где представляет собой невырожденную подматрицу матрицы М размерностью n×n, а представляет собой соответствующий субвектор b.