Анализ изображения позиционно кодированного документа и нанесение метки

Анализ изображения позиционно кодированного документа и нанесение метки

Иллюстрации

Показать все

Реферат

ОБЛАСТЬ ТЕХНИКИ, К КОТОРОЙ ОТНОСИТСЯ ИЗОБРЕТЕНИЕ

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

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

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

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

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

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

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

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

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

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

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

Дополнительные свойства и преимущества настоящего изобретения будут очевидны при чтении следующего подробного его описания.

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

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

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

На фиг.2А и 2В показана система ввода изображения и соответствующее введенное изображение в соответствии с вариантами выполнения настоящего изобретения.

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

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

На фиг.5A-5D показаны четыре получаемые в результате угла, которые могут быть ассоциированы с системой кодирования в соответствии с фиг.4А и 4В.

На фиг.6 показан поворот участка фиксированного изображения в соответствии с вариантами выполнения настоящего изобретения.

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

На фиг.8 представлен процесс определения местоположения введенной матрицы в соответствии с вариантами выполнения настоящего изобретения.

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

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

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

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

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

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

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

На фиг.16 представлено изображение, вводимое камерой, имеющее ненулевой угол поворота и угол поворота 45 градусов.

На фиг 17 показаны два ядра свертки, которые формируют оператор Собеля (Sobel) выделения краев изображения.

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

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

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

На фиг.21 показано представление пространства кодирования в документе в соответствии с известным уровнем техники.

ОСУЩЕСТВЛЕНИЕ ИЗОБРЕТЕНИЯ

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

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

I. Термины

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

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

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

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

Базовая система 160 ввода/вывода (BIOS), содержащая основные процедуры, которые позволяют передавать информацию между элементами в компьютере 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 процессора непосредственно через параллельный порт или другой интерфейс и системную шину 130, как известно в данной области техники. Кроме того, хотя цифровой преобразователь 165 показан отдельно от монитора 107, предпочтительно, чтобы используемая область ввода цифрового преобразователя 165 имела те же размеры, что и область сопоставления монитора 107. Кроме того, цифровой преобразователь 165 может быть интегрирован в монитор 107, или может быть выполнен как отдельное устройство, наложенное на монитор 107 или присоединенное к нему другим способом.

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

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

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

III. Ручка ввода изображения

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

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

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

На фиг.2В представлено изображение, получаемое с помощью камеры 203. В одном иллюстративном примере поле обзора камеры 203 (то есть разрешающая способность датчика изображения камеры) составляет 32х32 пикселя (где N=32). В варианте выполнения изображение, вводимое камерой 203 (32 пикселя на 32 пикселя) соответствует области поверхности плоскости размером приблизительно 5 мм на 5 мм. В соответствии с этим на фиг.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, в которой θ_х, θ_y, S_x и S_y представляют собой поворот и масштаб двух ориентаций структуры, введенной в местоположении 204. Кроме того, можно уточнить F′_S→_P путем сопоставления введенного изображения с соответствующим действительным изображением на бумаге. "Уточнить" означает получить более точную оценку преобразования F_S→_P с использованием определенного типа алгоритма оптимизации, который называется рекурсивным способом. В рекурсивном способе матрица F′_S→_P используется в качестве исходного значения. Уточненная оценка более точно описывает преобразование между S и Р.

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

Кончик 22 ручки устанавливают в фиксированное местоположение 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_{виртуального кончика ручки}).

IV. Кодирование Матрицы

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

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

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

где Р_n(x) представляет собой примитивный многочлен степени n в поле F_q[x] (содержащем qⁿ элементов). R₁(x) представляет собой ненулевой многочлен степени 1 (где 1<n) в поле F_g[x]. Последовательность может быть создана с использованием итеративной процедуры за два этапа: первый, деление двух многочленов (в результате чего получают элемент поля F_q), и второй, умножение остатка на х. Расчет прекращают, когда выходное значение начинает повторяться. Этот процесс может быть выполнен с помощью линейного сдвигового регистра с обратной связью, как описано в статье 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 (Май 1994 г., стр.560-568). В этой среде между циклическим сдвигом последовательности и многочленом R₁(х) устанавливают взаимозависимость: при изменении R₁(х) происходит только циклический сдвиг последовательности, и каждый циклический сдвиг соответствует многочлену R₁(х). Одно из свойств получаемой в результате последовательности состоит в том, что последовательность имеет период qⁿ-1 и, в пределах периода, по ширине (или длине) n, любой участок присутствует в последовательности один раз и только один раз. Это называется "свойством окна". Период qⁿ-1 также называется длиной последовательности и n называется порядком последовательности.

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

IV. В. Построение матрицы

Матрица (или m-матрица), которую можно использовать для создания изображения (участок которого может быть введен камерой), представляет собой расширение одномерной последовательности или m-последовательности. Пусть А представляет собой матрицу с периодом (m₁, m₂), а именно A (k+m₁, 1)=A (k, 1+m₂)=А (k, 1). Когда окно n₁ × n₂ сдвигается через период А, все ненулевые матрицы n₁ × n₂ F_q появляются один раз и только один раз. Это свойство также называется "свойством окна", при котором каждое окно является уникальным. Окно затем может быть выражено как матрица с периодом (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С показаны три различные последовательности. Каждая из них может быть свернута в виде матрицы, показанной на фиг.3D. Три различных способа свертки показаны в виде наложения на фиг.3D и в виде пути растра на фиг.3Е и 3F. Здесь принят способ свертки, показанный на фиг.3D.

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

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

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

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

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