отображение между камерой и кончиком пера и калибровка

Формула изобретения

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

генерируют калибровочный параметр на основе множества изображений, захваченных камерой цифрового пера, посредством установки пера в множество различных ориентаций при удержании кончика пера в, по существу, фиксированном местоположении L_{кончика пера} на поверхности с кодированием позиций, при этом калибровочный параметр генерируют на основе множества итеративно сгенерированных оценок калибровочного параметра; и

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

2. Способ по п.1, дополнительно содержащий этапы, на которых рассчитывают преобразование F_{S P} и обратное преобразование F_{P S}=F^-1F_{S P}, путем декодирования m-массива и согласования изображений для каждого изображения из упомянутого множества захваченных изображений и затем рассчитывают:

Lⁱ _{кончика пера}=Fⁱ _{S Р}·L_{виртуального кончика пера,} i=1, 2 , N и

Lⁱ _{виртуального кончика пера}=Fⁱ _{P S}·(L_{кончика пера}+ L_i), i=1, 2 , N,

где N - количество захваченных изображений, используемых для генерирования калибровочного параметра, и L_i - смещение между действительным местоположением кончика пера в i-м кадре и L_{кончика пера}.

3. Способ по п.2, дополнительно содержащий этап, на котором инициализируют

_{виртуального кончика пера} как (0, 0), где _{виртуального кончика пера} величина оценки

_{виртуального кончика пера}.

4. Способ по п.3, дополнительно содержащий этапы, на которых в уравнении L ⁱ _{кончика пера}=Fⁱ _{S P}·L_{виртуального кончика пера}, i=1, 2 , N, устанавливают L_{виртуального кончика пера} как _{виртуального кончика пера} для получения L ⁱ _{кончика пера}, i=1, 2, N, и путем усреднения Lⁱ _{кончика пера} оценивают L_{кончика пера} как:

.

5. Способ по п.4, дополнительно содержащий этапы, на которых в уравнении

Lⁱ _{виртуального кончика пера}=Fⁱ _{Р S}·(L_{кончика пера}+ L_i), i=1, 2, , N, устанавливают L_{кончика пера} как _{кончика пера} для получения Lⁱ _{виртуального кончика пера}, i=1, 2, , N, и путем усреднения Lⁱ _{виртуального кончика пера} оценивают L_{виртуального кончика пера} как:

.

6. Способ по п.5, дополнительно содержащий повторение этапов, где в уравнении Lⁱ _{кончика пера}=F_{S P}·L_{виртуального кончика пера}, i=1, 2 , N, устанавливают L_{виртуального кончика пера} как _{виртуального кончика пера} для получения L ⁱ _{кончика пера}, i=1, 2, N, и путем усреднения Lⁱ _{кончика пера} оценивают L_{кончика пера} как

,

и в уравнении Lⁱ _{виртуального кончика пера}=Fⁱ _{S P}·(L_{кончика пера}+ L_i), i=1, 2 , N, устанавливают L _{кончика пера} как _{кончика пера} для получения Lⁱ _{виртуального кончика пера}, i=1, 2, ... N, и путем усреднения Lⁱ _{виртуального кончика пера} оценивают L_{виртуального кончика пера} как

,

множество раз, так чтобы оценка L_{виртуального кончика пера} сошлась, по существу, к более точному результату L^точное _{виртуального кончика пера} и оценка L_{кончика пера} сошлась, по существу, к более точному результату L ^точное _{кончика пера}.

7. Способ по п.6, дополнительно содержащий этап, на котором используют L^точное _{виртуального кончика пера} в качестве калибровочного параметра для отображения местоположения центра изображения, захваченного камерой, на местоположение кончика пера.

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

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

10. Машиночитаемый носитель информации по п.9, дополнительно содержащий машиноисполняемые команды, которые рассчитывают преобразование F_{S P} и обратное преобразование F_{P S}=F^-1 _{S P} путем согласования изображений для каждого изображения из упомянутого множества захваченных изображений и рассчитывают

Lⁱ _{кончика пера}=Fⁱ _{S P}·L_{виртуального кончика пера}, i=1, 2 , N и

Lⁱ _{виртуального кончика пера}=Fⁱ _{P S}·(L_{кончика пера}+ L_i), i=1, 2 , N,

где N - количество захваченных изображений, используемых для генерирования калибровочного параметра, и L_i - смещение между действительным местоположением кончика пера в i-м кадре и L_{кончика пера}.

11. Машиночитаемый носитель информации по п.10, дополнительно содержащий машиноисполняемые команды, которые инициализируют _{виртуального кончика пера} как (0, 0), где _{виртуального кончика пера} - оценка значения L_{виртуального кончика пера}.

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

Lⁱ _{кончика пера}=Fⁱ _{S P}·L_{виртуального кончика пера}, i=1, 2 , N, установить L_{виртуального кончика пера} как _{виртуального кончика пера} для получения L ⁱ _{кончика пера}, i=1, 2, N, и путем усреднения

Lⁱ _{кончика пера} оценить L_{кончика пера} как

.

13. Машиночитаемый носитель информации по п.12, дополнительно содержащий машиноисполняемые команды для того, чтобы в уравнении Lⁱ _{виртуального кончика пера}=Fⁱ _{P S}·(L_{кончикa пера}+ L_i), i=1, 2, , N, установить L_{кончика пера} как _{кончика пера} для получения Lⁱ _{виртуального кончика пера}, i=1, 2, , N, и путем усреднения Lⁱ _{виртуального кончика пера} оценить L_{виртуального кончика пера} как

.

14. Машиночитаемый носитель информации по п.13, дополнительно содержащий машиночитаемые команды для повторения расчетов так, чтобы в уравнении Lⁱ _{кончика пера}=Fⁱ _{S P}·L_{виртуального кончика пера}, i=1, 2 , N, установить L_{виртуального кончика пера} как _{виртуального кончика пера} для получения L ⁱ _{кончика пера}, i=1, 2 , N, и путем усреднения Lⁱ _{кончика пера} оценить L_{кончика пера} как

,

и в уравнении Lⁱ _{виртуального кончика пера}=Fⁱ _{P S}·(L_{кончика пера}+ L_i), i=1, 2 , N, установить L_{кончика пера} как _{кончика пера} для получения Lⁱ _{виртуального кончика пера}, i=1, 2 , N, и путем усреднения Lⁱ _{виртуального кончика пера} оценить L_{виртуального кончика пера} как



множество раз, так чтобы оценка L_{виртуального кончика пера} сошлась, по существу, к более точному результату L^точное _{виртуального кончика пера} и оценка L_{кончика пера} сошлась, по существу, к более точному результату L ^точное _{кончика пера}.

15. Машиночитаемый носитель информации по п.14, дополнительно содержащий машиноисполняемые команды для использования L^точное _{виртуального кончика пера} в качестве калибровочного параметра L_{виртуального кончика пера} для отображения местоположения центра изображения на местоположение кончика пера.

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

генерирование калибровочного параметра на основе множества изображений, захваченных камерой цифрового пера, путем установки пера в множество различных ориентаций при удержании кончика пера в, по существу, фиксированном местоположении L_{кончика пера} на поверхности с кодированием позиций, при этом калибровочный параметр генерируется на основе множества итеративно сгенерированных оценок калибровочного параметра; и

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

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

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

калибровочный модуль, выполненный с возможностью генерации калибровочного параметра на основе множества изображений, захваченных камерой цифрового пера, когда перо находится в множестве различных ориентаций, в то время как кончик пера расположен, по существу, в фиксированном местоположении L _{кончика пера} на поверхности с кодированием позиций, при этом калибровочный параметр генерируется на основе множества итеративно сгенерированных оценок калибровочного параметра; и

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

19. Система по п.18, в которой калибровочный модуль выполнен с возможностью расчета преобразования F_{S P} и обратного преобразования F_{P S}=F^-1 _{S P} путем согласования изображений для каждого изображения из упомянутого множества захваченных изображений и последующего расчета:

Lⁱ _{кончика пера}=Fⁱ _{S Р}·L_{виртуального кончика пера}, i=1, 2 , N и

Lⁱ _{виртуального кончика пера}=Fⁱ _{P S}·(L_{кончика пера}+ L_i), i=1, 2 , N,

где N - количество захваченных изображений, используемых для генерирования калибровочного параметра, и L_i - смещение между действительным местоположением кончика пера в i-м кадре и L_{кончика пера}.

20. Система по п.19, в которой калибровочный модуль выполнен с возможностью инициирования _{виртуального кончика пера} как (0, 0), где L _{виртуального кончика пера} - оценка значения L_{виртуального кончика пера}.

21. Система по п.20, в которой в уравнении

Lⁱ _{кончика пера}=Fⁱ _{S P}·L_{виртуального кончика пера}, i=1, 2 , N, L_{виртуального кончика пера} установлено как _{виртуального кончика пера} для получения L ⁱ _{кончика пера}, i=1, 2, N, и L_{кончика пера} оценивается путем усреднения Lⁱ _{кончика пера}, как

.

22. Система по п.21, в которой в уравнении

Lⁱ _{виртуального кончика пера}=Fⁱ _{P S}·(L_{кончика пера}+ L_i), i=1, 2, , N, L_{кончика пера} установлено как _{кончика пера} для получения Lⁱ _{виртуального кончика пера}, i=1, 2, , N, и L_{виртуального кончика пера} оценивается путем усреднения Lⁱ _{виртуального кончика пера} как

.

23. Система по п.22, в которой калибровочный модуль выполнен с возможностью повтора упомянутых расчетов так, чтобы в упомянутом уравнении Lⁱ _{кончика пера}=Fⁱ _{S Р}·L_{виртуального кончика пера}, i=1, 2 , N, L_{виртуального кончика пера} установлено как _{виртуального кончика пера} для получения L ⁱ _{кончика пера}, i=1, 2, N, и L_{кончика пера} оценивается путем усреднения Lⁱ _{кончика пера} как

,

и в уравнении Lⁱ _{виртуального кончика пера}=Fⁱ _{Р S}·(L_{кончика пера}+ L_i), i=1, 2 , N,

L_{кончика пера} установлено как _{кончика пера} для получения Lⁱ _{виртуального кончика пера}, i=1, 2, , N, и L_{виртуального кончика пера} оценивается путем усреднения Lⁱ _{виртуального кончика пера} как



множество раз, так чтобы оценка L_{виртуального кончика пера} сошлась, по существу, к более точному результату L^точное _{виртуального кончика пера} и оценка L_{кончика пера} сошлась, по существу, к более точному результату L ^точное _{кончика пера}.

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

L^точное _{виртуального кончика пера} как калибровочный параметр, предназначенный для использования в модуле отображения для отображения восстановленного штриха центра изображения на восстановленный штрих кончика пера.

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

Описание изобретения к патенту

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Подробное описание изобретения

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

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

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

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

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

III. Перо с возможностью захвата изображений

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

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

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

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

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

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

Размер изображения, показанного на фиг.2B, составляет 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}, где _х, _у, s_x и s_y - поворот и масштаб двух ориентаций узора, захваченного в местоположении 204. Кроме того, можно уточнить F' _{S P} путем согласования введенного изображения с соответствующим действительным изображением на бумаге. "Уточнить" означает получить более точную оценку преобразования F _{S P} с использованием определенного типа алгоритма оптимизации, который называется рекурсивным методом. В рекурсивном методе матрица F'_{S P} используется в качестве начального значения. Уточненная оценка более точно описывает преобразование между S и P.

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

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

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

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

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

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

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

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

IV.B. Построение массива

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

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

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

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

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

На фиг.4A представлена примерная методика кодирования, которую можно использовать для кодирования массива по фиг.3D. При этом следует понимать, что можно использовать другие методики кодирования. Например, на фиг.11 показана альтернативная методика кодирования.

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

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

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

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

0 1 0 1 0 1 1 1 0

1 1 0 1 1 0 0 1 0

0 0 1 0 1 0 0 1 1

1 0 1 1 0 1 1 0 0

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

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

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

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

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

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

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

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

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

Взаимосвязь x^s r₀ + r_1x +··· r_n-1x^n-1mod(P _n(x)) предполагает, что R = r₀ + r₁T(I)+ ··· + r_n-1 T^n-1(I). При записи в виде бинарного линейного уравнения, она становится:

R = r^tA,(2)

где r = (r_0,r₁ r ₂ ··· r_n-1)^t , и А = (IT(I) ··· T ^n-1(I))^t, который состоит из циклических сдвигов I от 0-го сдвига до (n-1)-го сдвига. Теперь, пусть только разреженные К битов доступны в R для вектора r. Пусть разности индексов между b_i и 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)

где М - подматрица A размером n×K .

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

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

При известном r для определения s можно использовать алгоритм Полига-Геллмана-Силвера (Pohlig-Hellman-Silver), как указано в публикации 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), так что x^s r₀ + r₁x + ···r _n-1 x^n-1 mod(P_n(x)).

Поскольку матрица А (с размерами n на L, где L=2 ⁿ-1) может быть очень большой, следует исключить необходимость записи всей матрицы A. Фактически, как видно из вышеприведенного процесса, при заданных извлеченных битах с разностью k_i индексов для расчетов достаточно использовать только первый и (k_i + 1)-ый столбцы А. Такие варианты выбора k_i в достаточной степени ограничены при заданном размере захваченного изображения. При этом требуется сохранять только те столбцы, которые используются для расчетов. Общее количество таких столбцов намного меньше, чем L (где L=2ⁿ-1 представляют собой длину m- последовательности).

VI. Коррекция ошибок

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

Для этого случая применяется стохастический подход. Если предположить, что количество n_e битов с ошибками в b относительно невелико по сравнению с K, тогда высока вероятность выбора правильных n битов из К битов b и соответствующей подматрицы из матрицы М, которая является невырожденной.

Если все n выбранных битов являются правильными, расстояние Хемминга между b^t и r^tM, или количество битов с ошибкой, ассоциированных с r, должно быть минимальным, при этом r рассчитывают с использованием уравнения (4). При повторении процесса несколько раз, вполне вероятно, что можно будет идентифицировать правильный вектор r, который приводит к минимальному количеству битов с ошибками.

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

Если местоположение s удовлетворяет местному ограничению, получают положения X, Y выделенных битов в массиве. В противном случае процесс декодирования не может быть выполнен.

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

На этапе 803, выполняют случайный выбор n независимых векторов-столбцов из матрицы М и определяют вектор r путем решения уравнения (4). Этот процесс выполняют Q раз (например, 100 раз) на этапе 804. Определение количества циклов описано в разделе Вычисление количества циклов.

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

Система затем определяет на этапе 806, успешно ли была выполнена коррекция ошибок, проверяя, ассоциировано ли множество векторов r с минимальным количеством битов с ошибками. Если это так, на этапе 809 получают результат, свидетельствующий об ошибке, который указывает, что процесс декодирования не был проведен. В противном случае положение s выделенных битов в последовательности (или m-последовательности) рассчитывают на этапе 807, например, с использованием алгоритма Полига-Геллмана-Силвера.

Затем на этапе 808 рассчитывают положение (X, Y) в массиве как: x=s mod m₁ и y=s mod m₂ и выдают результаты.

VII. Определение местоположения

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

На этапе 901 принимают изображение от камеры. Затем принятое изображение может быть, в необязательном порядке, подвергнуто предварительной обработке, на этапе 902 (как показано пунктирным контуром, которым представлен этап 902), для регулировки контраста между светлыми и темными пикселями и т.п.

Затем на этапе 903 выполняют анализ изображения для определения потока битов, содержащегося в нем.

Затем на этапе 904 n битов выбирают случайным образом из потока битов множество раз и определяют местоположение принятого потока битов в исходной последовательности (или m-последовательности).

Наконец, после определения местоположения введенного изображения на этапе 904, на этапе 905 можно определить местоположение кончика пера.

На фиг.10 более подробно представлены этапы 903 и 904 и показан подход, используемый для выделения битового потока в захваченном изображении. Вначале принимают изображение от камеры на этапе 1001. Затем это изображение, в необязательном порядке, может быть предварительно обработано на этапе 1002 (как показано пунктирным контуром, которым представлен этап 1002). Узор выделяют на этапе 1003. Здесь могут быть выделены пиксели на различных линиях для определения ориентации узора и угла .

После этого выполняют анализ принятого изображения на этапе 1004 для определения лежащих в основе линий сетки. Если на этапе 1005 будут найдены линии сетки, на этапе 1006 выделяют код из узора. Код затем декодируют на этапе 1007, и местоположение кончика пера определяют на этапе 1008. Если на этапе 1005 не будут найдены линии сетки, на этапе 1009 формируется сообщение об ошибке.

VIII. Отображение штрихов изображения, захваченного камерой, на соответствующие штрихи кончика пера

В соответствии с различными вариантами выполнения настоящего изобретения положения x-y кончика 202 пера можно определить с использованием калибровочного параметра для отображения положений x-y соответствующих центров изображений, захваченных камерой 210 пера, с соответствующими местоположениями x-y кончика пера.

На фиг.11 показан калибровочный модуль 1102 и модуль 1106 отображения в соответствии с различными вариантами выполнения настоящего изобретения. Калибровочный модуль 1102 принимает входные калибровочные данные 1100, которые могут быть получены посредством помещения пользователем кончика 202 пера в фиксированное местоположение на поверхности 207, которая может представлять собой носитель с кодированием позиций, такой как бумага, и последующего вращения пера и/или перемещения противоположного конца пера в различных направлениях для захвата множества изображений с целью использования при генерировании калибровочного параметра 1104.

Модуль 1106 отображения использует калибровочный параметр 1104 и восстановленную информацию 1110 местоположения, захваченного камерой изображения для генерирования восстановленной информации 1108 местоположения кончика пера.

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

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

На фиг.12 также представлен восстановленный штрих 1201 кончика пера, который был выполнен кончиком 202 пера. Восстановленный штрих 1201 кончика пера может быть получен путем применения калибровочного параметра 1104 к восстановленному штриху 1203 захваченного изображения.

В соответствии с различными вариантами выполнения настоящего изобретения виртуальный кончик 212 пера используют для отображения восстановленного штриха 1203 центра изображения на восстановленный штрих 1201 кончика пера. Местоположение виртуального кончика пера зависит от заранее определенной взаимосвязи между реальным кончиком 202 пера и камерой 203, основывающейся на конфигурации пера. Виртуальный кончик 212 пера представляет собой проецируемую точку кончика 202 пера на плоскость 209 датчика изображения. Местоположение виртуального кончика 212 пера на плоскости 209 датчика изображения является неизвестным, но фиксированным.

Один из способов отображения местоположения центра изображения на местоположение кончика пера состоит в идентификации пространственной взаимосвязи между кончиком пера и корпусом пера, пространственной взаимосвязи между корпусом пера, объективом и датчиком изображения, оптических характеристик, таких как фокусное расстояние объектива, физический размер пикселя датчика изображения, расстояние между центром изображения и оптической осью объектива, и так далее. Для выполнения этих измерений обычно требуется использовать специальное оборудование. Кроме того, каждый раз, когда конфигурация пера изменяется, например, при смене картриджа с чернилами, этот процесс требуется повторять. Благодаря концепции виртуального кончика пера, эти сложные этапы становятся ненужными. К местоположению виртуального кончика пера применяют перспективное преобразование для получения местоположения кончика пера, то есть:

Lкончика пера = F S P(Lвиртуального кончика пера)

(5)

IX. Калибровка

Оценку калибровочного параметра L_{виртуального кончика пера} можно получить в соответствии с различными вариантами выполнения настоящего изобретения, выполняя следующие этапы, (a)-(g):

(a) Пользователь помещает реальный кончик 202 пера в фиксированное местоположение L_{кончика пера} на поверхность 207. На фиг.14 показан участок 1400 поверхности 207 с кодированием позиций, на котором положение L_{кончика пера} показано в точке 1402.

(b) Пользователь удерживает кончик пера в местоположении L_{кончика пера} и захватывает ряд изображений при различной ориентации пера (то есть перо можно поворачивать, и/или конец пера, противоположный кончику 202 пера, можно перемещать в различных направлениях, в то время как кончик 202 пера остается в фиксированном местоположении L _{кончика пера}). Как показано на фиг.14, для L _{кончика пера} 1402 могут быть захвачены изображения, центры которых располагаются вдоль траектории 1404.

(c) Инициализируют _{виртуального кончика пера} как (0, 0), где _{виртуального кончика пера} представляет собой оценку значения L_{виртуального кончика пера.}

(d) Для каждого захваченного изображения рассчитывают преобразование F_{S P} и F_{P S} = F^-1 _{S P} путем декодирования m-массива и согласования изображений, после чего выполняют оценку уравнений 6 и 7:

Liкончика пера = F iS P·Lвиртуального кончика пера, i = 1,2···,N

(6)

Lⁱ _{виртуального кончика пера} = F ⁱ _{P S}·(L_{кончика пера} + L_i), i = 1,2···, N, (7)

где N - количество захваченных изображений, используемых для калибровки, и L_i - смещение между действительным местоположением кончика пера в i-том кадре и L_{кончика пера} .

(e) С помощью уравнения (6) устанавливают как для получения Lⁱ _{кончика пера,} i=1,2, ···, N. С помощью усреднения Lⁱ _{кончика пера} получают оценку L_{кончика пера} в следующем виде:

(f) С помощью уравнения (7) устанавливают как для получения Lⁱ _{виртуального кончика пера}, i = 1,2, ···, N. В результате усреднения Lⁱ _{виртуального кончика пера} получают оценку L_{виртуального кончика пера} в следующем виде:

(g) Переход на этап (e).

После нескольких итераций этапов (e)-(g), значение L _{виртуального кончика пера} и L_{кончика пера} , соответственно, сходятся, по существу, к более точным результатам, которые могут быть обозначены как L^точное _{виртуального кончика пера}и L^точное _{кончика пера.}

Значение L ^точное _{виртуального кончика пера} можно использовать как калибровочный параметр для L_{виртуального кончика пера} в уравнении (5), для отображения восстановленного штриха 1203 центра изображения на восстановленный штрих 1201 кончика пера.

Ниже будет представлен пример, в котором положения L^точное _{виртуального кончика пера} и L_{виртуального кончика пера} рассчитывают на основе помещения кончика пера в фиксированное местоположение L_{кончика пера} и вращения пера, захватывая при этом 47 изображений. Для каждого изображения получают преобразование F_{S P} и F_{P S}= F^-1 _{S P}. Как показано ниже, после 47 итераций, значение L_{виртуального кончикапера} сходится от (0,00, 0,00) в конечный результат (30,80, 7,01), и L _{кончика пера} сходится к конечному результату (978,87, 1618,55). Следует отметить, что значения L_{виртуального кончика пера} находятся в системе координат захваченного изображения с центром изображения, в качестве начала координат, а значения L_{кончика пера} находятся в системе координат соответствующего документа.

На итерации номер 1 ([Этап c]) инициализировать местоположение виртуального кончика пера VirtualPentip значением (x=0,00, y=0,00) для расчета местоположения кончика пера на бумаге для каждого изображения.

[Этап e]:

Изображение 0 кончика пера на бумаге: x=985,57, y=1649,70;

Изображение 1 кончика пера на бумаге: x=985,20, y=1649,25;

...;

Изображение 46 кончика пера на бумаге: x=1006,41, y=1629,30;

Изображение 47 кончика пера на бумаге: x=1006,76, y=1628,79;

Усредненное значение местоположения кончика пера на бумаге: x=993,32, y=1643,28.

[Этап f] - использовать последние усредненные значения местоположения кончика пера на бумаге (x=993,32, y=1643,28) для расчета значения VirtualPentip для каждого изображения:

Изображение 0 виртуального кончика пера: x=2,83, y=11,43;

Изображение 1 виртуального кончика пера: x=2,42, y=11,66;

...;

Изображение 46 виртуального кончика пера: x=9,46, y=-17,72;

Изображение 47 виртуального кончика пера: x=10,55, y=-18,45;

Усредненное значение VirtualPentip: x=3,65, y=0,88;

[Этап g] - переход на этап e.

Итерация номер 2 ([Этап e])- Использовать последнее усредненное значение VirtualPentip (x=3,65, y=0,88) для расчета местоположения кончика пера на бумаге для каждого изображения:

Изображение 0 кончика пера на бумаге: x=984,86, y=1646,07;

Изображение 1 кончика пера на бумаге: x=984,50, y=1645,58;

...;

Изображение 46 кончика пера на бумаге: x=1003,09, y=1628,06;

Изображение 47 кончика пера на бумаге: x=1003,53, y=1627,54;

Усредненное значение местоположения кончика пера на бумаге: x=991,64, y=1640,32.

[Этап f] - Использовать последнее усредненное значение местоположения кончика пера на бумаге (x=991,64, y=1640,32) для расчета значения VirtualPentip для каждого изображения:

Изображение 0 виртуального кончика пера: x=6,25, y=10,93;

Изображение 1 виртуального кончика пера: x=5,79, y=11,12;

...;

Изображение 46 виртуального кончика пера: x=11,93, y=-14,67;

Изображение 47 виртуального кончика пера: x=13,01, y=-15,41;

Усредненное значение VirtualPentip: x=6,87, y=1,64.

[Этап g] - переход на этап e.

Итерация номер 3 ([Этап e] - Использовать последнее усредненное значение VirtualPentip (x=6,87, y=1,64) для расчета местоположения кончика пера на бумаге для каждого изображения:

...

Итерация Номер 43 - Усредненное значение VirtualPentip: x=30,74, y=7,00.

...

Итерация Номер 44 - Усредненное значение VirtualPentip: x=30,76, y=7,01.

...

Итерация Номер 45 - Усредненное значение VirtualPentip: x=30,77, y=7,01.

...

Итерация Номер 46 - Усредненное значение VirtualPentip: x=30,78, y=7,01.

...

Итерация Номер 47 ([Этап f]) - Использовать последнее усредненное значение местоположения кончика пера на бумаге (x=978,87, y=1618,55) для расчета значения VirtualPentip для каждого изображения:

Изображение 0 местоположения виртуального кончика пера: x=31,61, y=6,88;

Изображение 1 местоположения виртуального кончика пера: x=30,74, y=6,73;

...

Изображение 46 местоположения виртуального кончика пера: x=30,47, y=7,74;

Изображение 47 местоположения виртуального кончика пера: x=31,46, y=6,96;

В соответствии с этим, в данном примере конечное усредненное значение VirtualPentip сходится к x=30,80, y=7,01.

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