ФОРМИРОВАНИЕ, ФИКСАЦИЯ И ИСПОЛЬЗОВАНИЕ МЕТОК ВИЗУАЛЬНОЙ ИДЕНТИФИКАЦИИ ДЛЯ ДВИЖУЩИХСЯ ОБЪЕКТОВ Российский патент 2016 года по МПК G06K19/06 

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

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

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

Наиболее близким к настоящему изобретению является матричный код "MaxiCode", используемый UPS Ref. 1), в нем используются черно-белые шестиугольники, и цветной штрих-код большой емкости компании Microsoft Ref. 2), в котором используются цветные треугольники в качестве модулей оптического кодирования. Фиксация известных 2D матричных кодов с помощью цифровой камеры с низким разрешением будет неудачной при изменяющихся условиях освещения, или когда цель расположена слишком далеко. Ни один из этих кодов нельзя надежно идентифицировать для переменного количества меток, присутствующих одновременно в поле обзора движущейся камеры.

На фиг.1 иллюстрируются два обычно используемых 2D матричных кода. Data Matrix слева и QR Ref. 3) на правом коде представлены имя и адрес Правообладателя, как указано на первой странице данной заявки. Следует обратить внимание на типичные элементы привязки, в данном случае квадраты, которые используются для совмещения (перемещения в первое стандартное положение, или получения) меток. Элементы привязки находят с использованием сопоставления с шаблонами.

На фиг.2 иллюстрируется "MaxiCode" UPS для той же строки, которая показана на фиг.1. Использование черно-белых шестиугольников позволяет более экономично использовать пространство. Элемент привязки типа "мишени" используется для определения местоположения и совмещения метки. Следует отметить, белый промежуток между двумя соседними черными шестиугольниками используется для сегментации.

На фиг.3 иллюстрируются цветные метки высокой плотности компании Microsoft в {черном, желтом, голубом, пурпурном} пространстве (2 бита на треугольник). Белые промежутки между последовательными рядами используются для устранения перекоса и выравнивания, и представляют собой неотъемлемую часть данного изобретения. Метки могут быть сгенерированы и сохранены на специализированном веб-сервере Microsoft. Детали инструкции по съемке см. в Ref. 4).

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

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

Рассмотрим собрание, на котором участники носят метки со своими именами. Метки с именами и визитные карты трудно надежно считывать с помощью мобильных устройств, отчасти потому, что оптическое распознавание образов (OCR) в значительной степени использует вычислительные ресурсы. Использование RFID, смарт-карт и аналогичных электронных устройств требует дополнительного оборудования и может рассматриваться, как нарушение прав личности. Ношение визуальных опорных меток, таких, как раскрыты в данном изобретении, однако, позволяет легко и надежно распознавать участников, позволяет выполнять автоматические услуги конференции и много чего еще. Визуальные идентификационные метки могут обеспечить информацию по требованию на художественных и промышленных выставках, обслуживать официальные и частные собрания, автоматизировать идентификацию обслуживающего персонала, используя одну и ту же шкалу взвешивания, копировальные устройства кассовой регистрации и т.п. в области мелкорозничной торговли и обслуживания, улучшить системы наблюдения и/или отслеживания роботов и т.д.

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

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

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

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

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

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

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

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

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

На приложенных чертежах:

На фиг.1 иллюстрируются два обычно используемых 2D матричных кода.

На фиг.2 иллюстрируется UPS "MaxiCode" для той же строки, что и на фиг.1.

На фиг.3 иллюстрируются цветные метки высокой плотности Microsoft.

На ИЗОБРАЖЕНИИ 1 представлен вариант осуществления визуальной опорной метки А.

На фиг.4 показана карта США с каждым федеральным штатом, раскрашенным так, чтобы ни у какого из двух соседних штатов не был одинаковый цвет. Использовались только четыре цвета.

На фиг.5 иллюстрируется, как плотная упаковка плоскости кругами заданного радиуса (справа) хорошо аппроксимируется сотовой решеткой, показанной с левой стороны.

На фиг.6 иллюстрируется основная визуальная опорная метка. Реальные цвета могут использоваться только один раз, центр закрашен черным или белым цветом.

На фиг.7 показана альтернативная основная визуальная опорная метка. Черный шестиугольник также представляет начальную точку при считывании метки.

На фиг.8 иллюстрируются трехслойная визуальная опорная метка. Второй и третий слои соответствуют правилам раскрашивания карты.

На фиг.9 иллюстрируется кластер, полученный путем повторения основной метки.

Таблица 1 - список значений емкости информации визуальных опорных меток, в битах.

В таблице 2 отображается переменное количество цифр вдоль пути кодирования по фиг.10а и множество возможных других раскрасок.

На фиг.10а показан стандартный путь кодирования ЕР.

На фиг.10b показана окраска, соответствующая десятичному числу 127.

На фиг.10с показан эффект эстетического сдвига.

В таблице 3 содержатся детальные вычисления для генерирования цветов на фиг.10b.

На фиг.11 показан геометрический способ расчета для подсчета гистограмм на основе пикселя.

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

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

На фиг.14 показан процесс аннотации реального объекта.

На фиг.15 иллюстрируется пример чтения аннотаций объекта.

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

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

Как показано на фиг.10b, опорная метка 2 (REF Tag 2), содержит центральный шестиугольник, окруженный двумя слоями идентичных шестиугольников. Эта метка имеет емкость вплоть до 39 битов, в случае, когда кодирование является инвариантным при повороте. При сравнении, полная пара координат широты - долготы требует только 21 бит. Шестиугольники являются правильными: если сторона шестиугольника равна А, тогда его высота составляет А√3. Используемые цвета представляют собой Черный, Красный, Желтый, Зеленый, Голубой, Синий, Пурпурный и белый, в указанном порядке.

На ИЗОБРАЖЕНИИ 1 иллюстрируется несколько необычный физический вариант осуществления визуальной опорной метки А. Здесь представлена фотография из реальной жизни, представляющая проекцию дихроичных фильтрованных цветов с помощью галогеновой лампы "Doice Vita" Oligo, Reg. 5), в квартире автора изобретения. Следует отметить, что голубой фильтр отсутствует. Фильтры могут быть заменены вручную для разделения одного из, например, 5!=120 секретных сообщений.

На фиг.5 иллюстрируется, как охват плоскости кругами заданного радиуса (справа) хорошо аппроксимируется сотовой решеткой, показанной с левой стороны. Точка принадлежит синему шестиугольнику, обозначенному, как X, если она попадает между линиями (1, 2), (3, 4) и (5, 6).

На фиг.6 иллюстрируется основная метка Tag А. Фигура имеет приблизительно реальный размер именной карточки, схематично показанной справа. Рекомендуется нейтральный серый фон. Если черный/белый центр перемещается вверх, инвариантная при повороте метка может содержать вплоть до 10 битов. Такие асимметричные метки обозначены, как основные метки "core В". Оба типа меток имеют идеальную сигнатуру тональности, отражающую отображаемые шесть эквидистантных цветов.

На фиг.7 иллюстрируется основная метка Tag В: внешний белый шестиугольник используется, как для компенсации белого, так и как исходная точка при использовании инвариантного при повороте кодирования. Ее емкость составляет 10 битов.

На фиг.8 иллюстрируется метка REF Tag 3 с 2 дополнительными слоями, окружающими основу метки, также при выполнении правил раскрашивания карты.

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

На фиг.10b иллюстрируется метка REF Tag 2. Внешние шестиугольники оболочки раскрашены в соответствии с правилами раскрашивания карты: они должны отличаться (по цвету) от своих соседей.

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

Таблица 1 Метка REF   А В 2 3 Кластер⁽¹⁾ Основная метка А 8 - 37 66 137 В - 10 39 68 139

В таблице 2 показано переменное количество "цветовых цифр" вдоль пути, пронумерованного на фиг.10а. m=0 соответствует исходной точке (SP) и $$Q_m={П}_{k=0}^{m-1}{q}_k,m>0;Q_0=1$$ представляет собой число, которое умножает "цветовую цифру a_m∈[0,…,q_m-1]: как описано в Приложении. Значения, записанные в таблице, отражают описанные здесь "аппроксимации одного пути".

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

На фиг.10b показан код, соответствующий числу 127=Q₀+3Q₁+2Q₃. {черный, красный} цвета часто повторяются сами собой, поскольку они находятся в верхней части списка доступных цветов (в порядке RGB). См. таблицу 3, в которой представлены подробные расчеты.

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

В таблице 3 представлены примеры того, как кодируют число 127 в цветах по фиг.10b. Вначале рассмотрим таблицу 2 и введем в столбец ПРОПУСК соответствующие "цветные цифры". Следуя по пути кодирования запишем в следующей строке таблицы уже существующие цвета, влияющие на фактический выбор. Для первых 7 шестиугольников каждый цвет может быть выбран только один раз (правило цвета). На втором уровне только уже расцвеченные ближайшие соседи должны быть исключены из доступного списка цветов. Столбцы с исключенными цветами затенены.

Для шестиугольника SP=0 на фиг.10а выбирают либо черный, или белый цвет. Поскольку Qi=2 и 127 является нечетным, его цветная цифра для а₀=1, поэтому черный пропускают (">"), и выбирают белый цвет. После этого черный и белый исключены из основания В, поэтому эти столбцы затенены. Далее кодируют цветную цифру "3" (для 3×2=6), что после трех пропусков ">" приводит к голубому. До сих пор кодировали 1+6=7 из 127. Все еще необходимо кодировать 2 перед Qi=60, для того, чтобы закончить 127. Этот цвет представляет собой Синий. Для каждой следующей записи вводят "цветную цифру" 0 (ноль). Ноль означает выбор первой записи из списка доступных цветов.

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

При работе с последним рядом можно отметить, что два соседа 17 и 7 для ячейки 18, оба являются черными. Это разрешено, поскольку они не являются ближайшими соседями. Это оставляет фактически 5 свободных цветов для выбора для ячейки 18, а не 4, которые можно найти в таблице 2. Поэтому, дополнительный промежуток обозначается меткой "?". Возможно ли такое также в других рядах таблицы 3 при кодировании некоторых других чисел?

Фактически, таблица 2 и таблица 3 не содержат полную истину, но простую и точную аппроксимацию. Можно рассмотреть случаи, в которых таблица 3 обеспечивает больше возможностей, чем таблица 2, и никогда меньше. Следовательно, описанный способ кодирования всегда работает, за исключением потери некоторой дополнительной емкости кодирования. Математический фундамент этого процесса раскрыт в правиле прямой итерации (Ур. 14) в Приложении. В соответствии с этим, для использования полной информационной емкости меток, записи Q_m в таблице 2 должны быть актуализированы после каждого этапа кодирования, в зависимости от фактической конфигурации цветов вплоть до этого этапа. Обычно процесс кодирования и декодирования выполняется автоматически с помощью программных средств, в которых внедрены этапы, описанные выше.

Сильное коммерчески привлекательное качество меток REF состоит в их эстетическом внешнем виде. При кодировании малых чисел большая часть цветных цифр (или ПРОПУСКОВ (SKIPS)) будет равна нулю. Из примера, представленного выше, следует, что правило кодирования быстро приводит к кодированию нуля. Следовательно, только первые два или три цвета будут изменяться вдоль пути кодирования. Для улучшения этой ситуации, можно изменить правила, требуя, чтобы на каждом этапе был выполнен пропуск на принятые по умолчанию m шагов, где m представляет собой номер ячейки на пути кодирования. При достижении конца списка свободных цветов, подсчет продолжается с начала списка. Эта процедура приводит к метке, показанной на фиг.10 с, на которой представлено более сбалансированное распределение цветов.

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

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

На фиг.12 иллюстрируется предшествующее (ожидаемое) распределение цветовых тонов для основной сигнатуры, независимо от фактической кодированной информации. Она представляет собой сумму нормальных распределений, с центром в {R, Y, G, С, В, М} на углу тональности цветов. Такое распределение может быть изменено плохо откалиброванными принтерами и камерами. Однако, присутствие больше чем 5-6 хорошо разделенных, примерно равных пиков в пределах меньшей, компактной области, является очень редким в естественных изображениях. Это обеспечивает сильный по уровню сигнал для идентификации основных меток.

На фиг.13 показаны некоторые примеры распознанных меток - следует отметить разные и иногда трудные фоновые изображения. Размеры изображения составляют 640×640 пикселей, за исключением верхнего левого, которое представляет собой видеокадр размером 240×240.

На фиг.14 иллюстрируется пример процесса аннотации реального объекта:

визуальная метка содержит вставку ID уникальной базы данных. В базе данных содержатся свойства объекта, метка и уникальное хеш-значение метки.

На фиг.15 иллюстрируется пример считывания аннотаций объекта: после съемки изображения (или получения видеокадра) с цифровой камерой, приложение находит метку, калибрует изображение и декодирует информацию о метке. Декодирование информации 2D визуальной метки используется, в качестве ключа для базы данных устройства или других аналогичных вариантов применения, для специализированного сервера, провайдера телефонных услуг или для веб-услуги. По запросу приложения передают часть данных, полученных из базы данных, обратно в исходное устройство (в защищенной форме, если это применимо) и, в случае необходимости, проецируют в отображаемое изображение/видеопоток или передают как текст SMS.

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

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

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

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

Физические варианты осуществления меток REF могут быть либо распечатаны, или раскрашены на наклейке, пластиковой этикетке, кусочке жести или керамической пластине и т.д., или могут быть закреплены, как светящийся или подсвеченный объект. На ИЗОБРАЖЕНИИ 1 иллюстрируется интересный пример. Метки REF могут обеспечить помощь при навигации мобильных устройств, при определении мест без доступа к спутнику (подземные станции метро или супермаркеты), могут обеспечить помощь при автоматическом определении маршрута роботов, улучшить системы наблюдения, позволяют аутентифицировать разные объекты, и выполнять услуги всех видов. Они могут быть размещены в виде массивов или могут изменять цвета с течением времени, обеспечивая непрерывный источник сигналов. Метки REF могут даже быть напечатаны позади считываемого человеком текста, таким образом, что это позволяет обеспечить автоматическое восстановление гиперссылок из бумажных печатных изданий.

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

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

ОПРЕДЕЛЕНИЕ МЕСТОПОЛОЖЕНИЯ (Определение цели): система должна надежно находить сигнатуру одной или больше этикетов в снятом изображении. Все существующие матричные коды основаны при выполнении этой операции на определенных формах элементов привязки, которые представляют собой линии, круги или квадраты заданной формы и структуры, как можно видеть на фиг.1-фиг.2. Вместо этого, в данном изобретении используется центральная часть метки для генерирования гистограммы с определенным цветом, которая детектируется вероятностным способом.

КАЛИБРОВАТЬ: В реальных ситуациях части снятого изображения будут иметь низкое качество (тени и т.д.). Поскольку метки содержат много шестиугольников белого и черного цветов, их можно использовать для уравновешивания цветов RGB, расположенных непосредственно рядом с ними.

ДЕКОДИРОВАТЬ: размер и положение метки в снятом (цифровом) изображении являются произвольными. Для того, чтобы работать с разными размерами, предлагается использовать однопроходный многомасштабный анализ изображения. Поворот обрабатывают, используя независимые от поворота коды. Информационное содержание, напечатанное на этикетке, может представлять собой результат нескольких операций, включая в себя сжатие данных, кодирование с коррекцией ошибок и шифрование. Декодирование содержит тогда дешифрование, декодирование и расширение, в указанном порядке.

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

Выбор правильной решетки и правильной формы кластера

Штрих-кодами помечают, как правило, разные продукты или документы, используя графический код для целых чисел. В Wikipedia Ref. 3), представлено хорошее представление для штрих-кодов, включая в себя соответствующие патенты). Практически все штрих-коды являются двоичными и, таким образом, напечатаны черным и белым цветами; они эффективно считываются лазерными сканерами. Первым широко использовавшимся матричным кодом был (шестибитный) код Брейля (в 1824 г.), с помощью которого кодировали буквы. Среди матричных (или 2D) кодов наиболее часто коды применяют QR, и Data Matrix (фиг.1). Эти 2D штрих-коды используются на почтовых марках, при распределении билетов в режиме онлайн и в других мобильных вариантах применения. QR-коды также распознают с помощью смартфонов, с хорошей камерой и, например, с операционной системой Android. Однако они не могут быть надежно считаны на расстоянии или в нестабильных условиях.

Самым близким к нашему подходу является MaxiCode, используемый UPS (см. фиг.2). MaxiCode использует шестиугольную решетку. Этот черно-белый код может использоваться в вариантах с низким и высоким уровнем "шумов", и может содержать вплоть до 93 байтов (символов ASCII). Все примеры, показанные на фиг.1-2, содержат полную строку "Rujan Entwicklung und Forschung GmbH, Freiburg, Germany". MaxiCode был стандартизирован в стандарте ISO/IEC 16023 и является общедоступным. Ссылка на оригинальные патенты приведена в Ref. 1).

Другие патенты, относящиеся к нашему изобретению, представляют собой цветной штрих-код большой емкости (НССВ) автора G. Jancke's (Microsoft) Ref. 2), поскольку он представляет собой первый матричный код, в котором используются реальные цвета. Это имеет смысл, поскольку существующие аппаратные средства датчиков имеют отдельные слои цветов RGB и, таким образом, обеспечивают высокую чувствительность к цветовому тону. Код НССВ показан на фиг.3, больше информации можно найти на веб-сайте Microsoft в соответствии с Ref. 4). На фиг.3 представлены ссылки на ту же строку, что и выше. Такие метки генерируют и распознают исключительно с помощью специализированного сервера в <http://tag.miscrosoft.com>.

В настоящем изобретении используются раскрашенные шестиугольники, но здесь обеспечивается несколько новых свойств, что делает его отличным, как от MaxiCode, так и от НССВ. Как на фиг.2, так и на фиг.3 показаны некоторые специально разработанные белые полосы: между соседними шестиугольниками на фиг.2 и между соседними рядами на фиг.3. Эти полосы представляют собой единую часть вариантов осуществления патента и способствуют сегментации решетки для MaxiCode и операции устранения перекоса, после которой следует выделение рядов - кромок для НВВС.

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

Задача упаковки сфер относится к свойствам наиболее самой плотной компоновки сфер и приводит к плотно упакованным решеткам FCC и ВСС в трех - двух изменениях в виде сотовой шестиугольной решетки. Для достижения максимальной плотности информации на единицу области или объема, форма модуля переноса оптической информации или элементарной ячейки должна быть настолько близкой, насколько возможно, к сфере или кругу. В Ref. 11) подробно описаны эти и другие интересные проблемы, относящиеся к упаковке сферы. Наиболее плотная упаковка сфер в двух измерениях соответствует шестиугольной решетке (см. фиг.5), которая позволяет получить плотность $$\frac{\pi }{2{\sqrt{3}}^{!}}$$ , как впервые было рассчитано Гауссом, см. Ref. 12).

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

Кодирование опорных меток

Далее раскрыто, как следует рассчитывать информационную емкость меток REF и как кодировать целые числа в цветные коды. Визуальные опорные метки должны быть относительно большими, по сравнению с обычными матричными кодами, поскольку они должны быть сняты с большего расстояния датчиками с низким разрешением. Кроме того, сам цветной код может быть "достаточно искусственным", для того, чтобы исключить ложные сопоставления с естественным фоновым цветом. Далее описаны только 2D варианты осуществления изобретения, понимая то, что представленные методики могут быть легко обобщены до более высокого уровня измерения.

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

В цветовом пространстве HSV (цвет-насыщенный-значение) часть цвета кодируют, используя цвет (цветовой угол, изменяющийся от 0 до 2π), и насыщенность (интенсивность цвета). В предпочтительном варианте осуществления используется черный, красный, желтый, зеленый, голубой, синий, пурпурный, красный и белый цвета, в указанном порядке. Каждый "реальный" цвет располагается под углом π/3 друг от друга, при высоком значении насыщенности. Одиночная шестиугольная ячейка имеет, таким образом, 8 состояний (3 бита), обозначенных, как {b, R, Y, G, С, В, М, w}, соответственно, или {(0, 0, 0), (1, 0, 0), (1, 1, 0), (0, 1, 0), (0, 1, 1), (0, 0, 1), (1, 0, 1), (1, 1, 1)} при обозначении sRGB, формируя серый код Ref. 16). Малые буквы {b, w} обозначают черный и белый, соответственно. {В} всегда обозначает синий.

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

Основные опорные метки

"ОСНОВНАЯ" опорная метка состоит из центрального шестиугольника и его шести окружающих соседей. Основная опорная метка всегда содержит все шесть реальных цветов (R, Y, G, С, В, М} и одну из {b, w} серых шкал точно один раз. В центре основной метки А отображается черный или белый цвет, в то время как основная метка В расположена во внешнем слое. Метка В является несколько асимметричной, что представляет собой полезное свойство для инвариантного при повороте кодирования.

REF метка А показана на фиг.6 слева. Справа можно видеть графическую иллюстрацию метки, справа, возможно, физическую реализацию, которая здесь называется "этикеткой". Этикетка может быть реализована с помощью разных технологий, из разных материалов, включая в себя отображение на мониторе или может проецироваться на экран или другой фон. Каждый шестиугольник отображает один конкретный цвет из набора {b, R, Y, G, С, В, М, w}. Для графического отображения на этикетке предпочтителен легкий серый фон.

Шесть разных реальных цветов обеспечивают первичную "сигнатуру" метки, которая представляет собой гистограмму тонов на основе пикселей. Вторичная сигнатура обеспечивается описанной окружностью метки, и третья обеспечивается кромками сторон шестиугольника. Если кодирование является инвариантным при повороте, заданный цвет, например, черный или белый для метки В и зеленый для метки А, выбирают в качестве исходной точки (SP).

СТАНДАРТНЫЙ ПУТЬ КОДИРОВАНИЯ состоит в переходе от SP к центру и обратно вправо от начальной точки, затем следует по часовой стрелке по внешнему уровню (см. фиг.10а). Стоимость инвариантного при повороте кодирования составляет шестикратное уменьшение количества конфигураций на метку А. Метка В по своей конструкции является инвариантной при повороте. Выбор пути кодирования позволяет использовать динамические способы программирования, как поясняется в Приложении.

Метка А может принимать одно из Ω=2×6×5×4×3×2×1=1440 состояний, информационная емкость (логарифм Ω по основанию 2) составляет 10 битов, по сравнению с 3×7=21 битов неограниченной емкости. Если код является не инвариантным при повороте, количество состояний Ω=2×5×4×3×2×1=240, что несколько меньше, чем 8 битов. Код состоит из цвета {b, w} в центре и двумерных положений {R, Y, G, С, В, М} цветов. Метка В имеет также 1440 состояний, и она является инвариантной при повороте.

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

При наложении ограничений на выбор цветов, емкость инвариантных при повороте кодов уменьшается от 21-3=18 битов до 10 битов, что соответствует коэффициенту избыточности R=1/2, как используется в большинстве кодов коррекции ошибок. В случае отсутствия одного реального цвета (закрытый или грязный), ограничения позволяют восстановить его. Ошибки могут быть детектированы, если некоторые цвета возникают несколько раз или нарушают ограничение расцвечивания карты. Ошибки, которые не нарушают эти ограничения, не могут быть детектированы такими простыми способами.

Опорные метки 2,3 и кластер⁽¹⁾

Для увеличения информационной емкости метки добавляют один новый внешний слой, окружающий основную метку. Это приводит к получению метки, показанной на фиг.10b-с, называемой Меткой 2. Аналогично, можно добавить третий слой, как показано на фиг.8. Неудивительно, что эта метка называется Меткой 3. Поскольку основная структура уже обеспечивает сигнатуру и инвариантность при повороте, на внешние слои 2 и 3 могут распространяться менее строгие условия, чем на основу.

Для точности печати и простоты детектирования кромки, требуется только, чтобы каждая ячейка принимала другой цвет, чем ее соседи (правило расцвечивания карты). Три шестиугольные ячейки, встречающиеся в углах, все имеют разные цвета. Такая конструкция является хорошей: строгая, пропорциональная площади сигнатура для каждой основной метки и легко детектируемые СЕГМЕНТЫ на кромке (кромки+окончание линий) между любыми соседними шестиугольными ячейками.

Рассмотрим Метку 2 с В-основой на фиг.10а. В ТАБЛИЦЕ 2 отображается плотная нижняя граница для множества возможных конфигураций. Ее значение составляет Ω~144×7×(5×6)⁵×4 или 39 битов, только на один бит меньше, чем теоретическое значение. Такой тип оценки можно назвать "аппроксимацией по одному пути": здесь учитывается только вклад "основного" пути в Ω, и его получают, следуя пути кодирования и подсчитывая на каждом этапе количество доступных цветов, предполагая, что все уже раскрашенные соседи имеют разные цвета.

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

Сохранение GPS координат в градусах, минутах и секундах требует 21 бита. Следовательно, когда используют Метку 2 для сохранения приложения с кодированием GPS, остается достаточно пространства для применения кодов коррекции ошибок: либо турбокода Ref. 15) или кода с проверкой на четность малой плотности Ref. 16): оба близко подходят к оптимальной границе Шеннона. В качестве альтернатив, дополнительная информация может быть сохранена в метке. Другой способ выбора информации состоит в уменьшении координат GPS только до области, представляющей интерес.

REP Метка 3 показана на фиг.8. Ее третий уровень состоит из 12 дополнительных шестиугольников. При выполнении оценки того же типа, как и описано выше, добавляются дополнительные 29 битов к емкости метки - всего теперь 68 битов. Такая метка позволяет надежно кодировать, например, ключи базы данных размером 64 бита.

Другой способ расширения емкости основы состоит в ее итерации. Первая итерация фиг.6 показана на фиг.9 и называется "REF - Кластером первого порядка" (или Кластером⁽¹⁾ метки REF). Следуя по оценке одного пути, как для REF Метки 2 и 3, можно определить, что эта метка позволяет сохранять, по меньшей мере, 139 битов для основания В.

При увеличении размера можно сохранять (как ожидается) больше информации. Однако относительное разрешение для каждой метки ухудшается, и трудность правильного декодирования метки увеличивается. Для быстрого и хорошего распознавания рекомендуется не превышать размер REF - Кластер⁽¹⁾. Однако, по мере того, как увеличивается разрешающая способность, качества изображения и скорости процессора цифровых фотоаппаратов и встроенных систем, варианты осуществления, состоящие из большего количества меток, могут оказаться полезными в будущем. В таблице 1 показан пример информационной емкости при выборе различных меток, в зависимости от основания. Основание В обеспечивает автоматическую инвариантность при повороте.

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

Рассмотрим двух картографов, Элис и Боба, которые желают обменяться определенной информацией ("завтра в 18:00 в баре Кетти") с помощью REF Метки 2. Для простоты, предположим, что они уже договорились в ряде стандартных сообщений, из которых представленное выше соответствует числу 127. Элис пишет и передает сообщение. Боб принимает и читает его. Используя термины безопасной коммуникации, Элис является "кодером", а Боб является "декодером".

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

Прежде, чем рассмотреть, что сделала Элис для кодирования 127, посмотрим, как она могла бы кодировать 0 (ноль). Правило является простым: она движется вдоль пути кодирования. Шестиугольник, называемый SP, при этом является черным (первый доступный цвет). Центр ячейки 1 должен иметь реальный цвет, так, что он представляет собой первый доступный, красный цвет. На каждом шагу Элис записывает список цветов и удаляет цвета, которые уже использовались (в основе), или цвета, уже отображаемые в соседних ячейках (во внешнем слое). Затем она выбирает первый доступный цвет. Следуя такой процедуре для всех шестиугольников, в порядке, предписанном на пути, показанном на фиг.13а, она расцвечивает "0".

Элис кодирует 127 с помощью таблицы 2 и таблицы 3, как уже описано в предыдущих параграфах. Детальный математический вывод для кодирования любого целого числа меньшего, чем хроматическая функция, представлен в Приложении. Единственное различие между одной аппроксимацией пути и точным подсчетом состоит в том, что записи в таблице 2 должны быть сгенерированы на каждом этапе кодирования, в соответствии с формулой итерации вперед (Ур. 14).

Изучение сигнатур, коррекция ошибок, безопасность

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

Новое свойство системы REF состоит в том, что она обеспечивает дополнительный выбор при создании зависимого от случая реалистичного распределения сигнатуры непосредственно из снятых примеров. Никакая другая матричная система кода не обеспечивает такой процедуры изучения. Основные идеи для построения самоорганизующейся системы хорошо раскрыты в книге автора Kohonen Ref. 14).

Два способа изучения сигнатуры

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

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

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

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

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

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

В последние годы были предложены очень быстрые алгоритмы для коррекций стирания, в которых используются древовидные схемы - см. Ref. 18). В кодах CD, DVD и матричных кодах в качестве стандартного кода используют коды коррекции ошибок Рида-Соломона (RS) с перемежением (ЕСС). RS ЕСС представляют собой линейные коды, которые за счет К дополнительных символов позволяют корректировать К/2 ошибок и К стираний, независимо от того, где они возникают. В последнее время были разработаны линейные коды "декодирования списка", они несколько лучше, чем стандартные коды RS. Некоторые нелинейные коды, турбокоды, Ref. 15) и, в частности, коды Галлагера проверки на четность с низкой плотностью, Ref. 16), являются еще лучшими и почти насыщают границу Шеннона. В самом простом варианте осуществления этап кодирования способа ЕСС следует выполнять для опорных данных ПЕРЕД этапом генератора опорной метки и этапом декодирования, ПОСЛЕ восстановления из изображения соответствующего ключа или списка ключей, включающего в себя оценки вероятности ошибки.

Безопасность

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

Однако метки REF можно использовать, как дополнительный канал безопасности. Во время составления настоящего описания, например, в Берлине, банда продавала сфальсифицированные месячные билеты в метрополитен. Решение таких проблем могло состоять в печати дополнительной Метки 2 на каждом билете и сохранение в базе данных, как серийного номера, так и метки, напечатанной на билете. Когда кто-то покупает ежемесячный билет, он делает фотографию метки, передает ее через MMS или (если телефона уже есть необходимое программное обеспечение, через SMS) декодируемую опорную REF по общеизвестному номеру телефону. Сервер возвращает SMS с соответствующим серийным номером или ОК/ФАЛЬШИВЫЙ, затем удаляет пару записей из своей базы данных. С помощью такого приложения достаточно использовать инвариантную при повороте метку 2 REF емкостью 39 бита: в Берлине в любое время находится менее чем 5 миллионов людей, живущих здесь более чем месяц, и число размером 32 бита уже позволяет сохранить приблизительно 3,5 гига-ключей.

Некоторые области применения

Глобальные метки

Относительно малая информационная емкость метки REF не является проблемой, если ее правильно обрабатывают. У всех нас есть имена, которые в большей или меньшей степени дублированы в мире: но каждый Джон Доу является уникальным в своей деревне. Так же и метки REF в свой среде применения. Если необходимо идентифицировать Джона Доу в большом городе, необходимо добавить к его имени дополнительную информацию, такую, как его номер телефона или адрес. То же применимо к адресу IP каждого компьютера. Метки RFID сталкиваются с аналогичными логистическими проблемами. Использование глобальных меток REF аналогично: услуги сетевого доступа, аналогичные DNS поддерживают RFID, который через коды электронного продукта (EPS) позволяет уникально называть сервер, ответственный за передачу дополнительных данных через услугу наименования объекта (ONS). Конечно, метки с глобальным доступом должны быть зарегистрированы с DNS или другими аналогичными услугами.

Идентификация личности

Здесь представлен вводный пример: использование меток REF на собраниях, вечеринках, на свадьбах, сборах и т.д. Участники надевают REF карты участника или метки REF, напечатанные, как водяные знаки на их именных картах участника. Простая веб-камера или телефонная камера затем позволяют идентифицировать их и предоставить дополнительные услуги. Для сотрудника или надежной идентификации, однако, эти метки не обеспечивают реальной безопасности, поскольку они могут быть легко подделаны. Для таких вариантов применения должны быть построены дополнительные каналы обеспечения безопасности, известные только в системе печати персональных карт. Такие персональные карты могут быть украдены, но не могут быть сфальсифицированы, поскольку подделывающее лицо не знает, какая взаимосвязь существует между разными каналами.

Метка "объекта, представляющего интерес"

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

Визуальный поиск

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

Наблюдение

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

Навигация робота

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

Системы помощи для автомобилей

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

Не требуется OCR

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

Метки GPS, дорожные знаки и дополненная реальность

Координаты GPS имеют формат XXX:YY:YY, где XXX может изменяться от -90° до +90° (или от 0° до 360°), и YY принимает значения от 0 до 60. С одновременным учетом долготы и широты, это составляет приблизительно 21 бит. Следовательно, Метка 2 REF, так же, как метки, показанные на фиг.10b/с, могут легко сохранять их, включая в себя строгую схему ЕСС. Несколько из описанных меток REF имеют большую емкость, поэтому, их можно использовать, как визуальные метки на табличках с названиями улиц, зданиях или в любом месте, в котором требуется отображать их точное положение и, возможно, (через соединение с Интернет) дополнительную информацию, относящуюся к этому объекту. Такие места могут быть также освещенными или могут быть активно проецированными ночью. Навигационные места без доступа к спутникам, такие, как парижское метро, могут стать более простыми для американских или других туристов, которые не говорят по-французски.

Приложения для розничной торговли и персонализированных услуг

Рассмотрим мясную лавку, где различные поставщики используют одинаковую шкалу взвешивания. Всякий раз, когда заданный поставщик использует шкалу, он должен ввести свой собственный идентификационный номер. Эта задача (и множество других аналогичных задач) может выполняться автоматически компьютером, внедренным в весы, если сотрудники носят разные именные карты с REF Меткой А, и весы включают в себя малую цифровую камеру. Существует множество аналогичных ситуаций, когда один центральный ресурс используется несколькими сотрудниками, например, или несколько пользователей предоставляют персонализированные услуги на основе их автоматической визуальной идентификации с помощью меток REF. Другое очевидное использование представляет собой использование одной или больше меток REF для регистрации в компьютере.

Бумажные гипертекстовые ссылки через наложение информации

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

Приложение: емкости, кодеки, алгоритмы

Расчет емкости

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

Рассмотрим карту континента или федеральные штаты, такие как США или ФРГ. Задача расцвечивания карты может быть легко сформулирована: каково минимальное количество цветов, которое картограф должен использовать для расцвечивания произвольной двумерной карты так, чтобы каждая страна (федеральный штат) имела цвет, отличающийся от его соседей. Длительное время предполагалось, что это количество равно четырем. Математики в течение 140 лет добивались получить доказательство, которое было получено только недавно. Оно вовлекает первое использование сгенерированного компьютером цифрового обозначения в математическом доказательстве, Ref. 17).

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

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

$$C=\left[{\log }_2\Omega \left(q\right)\right]\left(Ур.1\right)$$

битов, где [х] представляет собой целую часть от х.

Расчет емкости основных меток является простым, из-за ограничения основания, в соответствии с которым каждый цвет возникает только один раз. Например, метка В имеет один белый или черный цвет на внешнем уровне. Остальные 6 шестиугольников все имеют разные (реальные) цвета. Пусть количество реальных цветов будет равно q. Тогда:

$$\Omega \left(q\right)=2\times q\times \left(q-1\right)\times \left(q-2\right)\times \left(q-3\right)\times \left(q-4\right)\times \left(q-5\right)=\frac{2q!}{\left(q-6\right)!}\left(Ур.2\right)$$

Расчет емкости меток, с исключением ближайшего соседа (правило расцвечивания карты), является более трудным. В теории графов, Ref. 6), функция Ω (g) называется хроматической функцией. Она может быть рассчитана с помощью формулы Биркгофа (1912), как многочлен в q:

$$\Omega \left(q\right)={\sum }_{G\text{'}\in G}{\left(-1\right)}^{b\left(G\text{'}\right)}{q}^{n\left(G\text{'}\right)}\left(Ур.3\right)$$

Сумма перехода по всем подграфам G' метки b (G') представляет собой количество соединений (кромок) в графе и количество n (G') компонентов (кластеров) в подграфе G'. Здесь одиночная (не соединенная) вершина рассчитывается, как один кластер. Такая формула может быть легко выведена из формулы случайного кластера в модели Поттса для состояния q (см. Ref. 7).

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

$$\begin{array}{l}\Omega \left(q\right)\\ ={\displaystyle \sum _{\left\{l_1\right\}}\tilde{\delta }\left(l_1,l_3\right)\tilde{\delta }\left(l_1,l_4\right)\tilde{\delta }\left(l_1,l_5\right)\tilde{\delta }\left(l_1,l_6\right)\tilde{\delta }\left(l_{sp},l_2\right)\tilde{\delta }\left(l_2,l_3\right)\tilde{\delta }\left(l_3,l_4\right)\tilde{\delta }\left(l_4,l_5\right)\tilde{\delta }\left(l_5,l_6\right)\tilde{\delta }\left(l_6,l_{sp}\right)}\left(Ур.4\right)\end{array}$$

Сумма представляет собой короткое обозначение семи сумм по переменным:

l_sp∈{1,2}, l_1-6∈{1,2…,q}. Символ $$\tilde{\delta }\left(l_1,l_2\right)=1-\delta \left(l_1,l_2\right)$$ представляет собой дополнение символа Кронекера δ(l₁,l₂) и равен нулю, если l₁=l₂, и единице в противном случае. Если требуется, конфигурации, в которых две стороны с общей границей имеют одинаковый цвет, не составляют вклад в хроматический многочлен. Аналогичная формула может быть записана для всей метки 2, но она слишком длинная, чтобы ее здесь разместить.

Для оценки представленных выше сумм, необходимы идентичности формы $${\sum }_{l=1}^q\tilde{\delta }\left(l,m\right)=q-1$$ ; $${\sum }_{l=1}^q\tilde{\delta }\left(a,l\right)\tilde{\delta }\left(l,b\right)=q-2+\delta {\left(a,b\right)}_{!}$$ , и т.д. Однако этот расчет может быть довольно трудоемким. Для больших меток этот способ является непрактичным, и при этом не было найдено простое отображение между целыми числами и конфигурациями цветов меток.

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

В качестве примера, рассмотрим снова метку В с правилом расцвечивания карты, как в (Ур. 4). Следует отметить, что в этом случае метка В может быть расцвечена с использованием только трех цветов: один в середине и два разных цвета, чередующихся вокруг центра. Начиная с SP, как показано на фиг.10а: эта ячейка может принимать q разных цветов. Шестиугольник 1 расцвечивания в одном из остающихся q-1 цветов задает коэффициент q-1. Шестиугольник 2 не может принимать тот же цвет, что и SP или 1, таким образом, он имеет q-2 вариантов выбора. Такое же количество ограничений действительно для шестиугольников 3, 4 и 5. Шестиугольник 6 имеет q, по меньшей мере, q-3 вариантов выбора. Следовательно,

$${\Omega }_1\left(q\right)=q\times \left(q-1\right)\times {\left(q-2\right)}^4\times \left(q-3\right)\left(Ур.5\right)$$

Это представляет собой аппроксимацию, поскольку на последнем этапе 6 имеется q-2, а не q-3 вариантов выбора, если 5 имеет тот же цвет, что и SP. Для учета этого случая, цвета SP разделяют на q-1 цвета (отличных от 5) и 1 (идентичный 5). При добавлении соответствующих вкладов получим:

$$\Omega \left(q\right)=\left(q-1\right)\times \left(q-1\right)\times {\left(q-2\right)}^4\times \left(q-3\right)+1\times \left(q-1\right)\times {\left(q-2\right)}^5={\Omega }_1\left(q\right)+1\left(Ур.6\right)$$

Применим теперь эту аппроксимацию к внешнему уровню (шестиугольникам 7-18) метки 2 с основанием В. Первые два и последние шестиугольники обрабатываются по отдельности. Когда Элис находится на нечетном месте, она видит только два расцвеченных ближайших соседа (один из внутреннего основания В, один из ее предыдущего выбора). Следовательно, она может сделать q-2 выбора. Элис не заботится о "пустом" соседе, поскольку она позаботиться о нем на следующем этапе. Следующий четный шестиугольник с нечетным номером имеет три уже расцвеченных соседа, поэтому, его можно раскрасить, по меньшей мере, q-3 способами. Принимая во внимание, что 7 имеет только один, 8 только два, и 18 самое большее четыре разных соседа, простейшая аппроксимация позволяет получить:

$${\Omega }_1\left(q\right)=\left(q-1\right)\left(q-2\right)\times {\left[\left(q-2\right)\left(q-3\right)\right]}^4\times \left(q-3\right)\left(q-4\right)\left(Ур.7\right)$$

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

В шестиугольниках с четными номерами два из трех соседей могут иметь идентичные цвета (шестиугольник 10 может иметь 3=9 соседей). Далее, используя тот же "способ разделения", как и в (Ур. 6), получают аппроксимацию вторичного пути:

$${\Omega }_2\left(q\right)=\left[\left(q-1\right)\left(q-2\right)+1\right]\times {\left[\left(q-2\right)\left(q-3\right)+1\right]}^4\times \left[\left(q-3\right)\left(q-4\right)+1\right]\left(Ур.8\right)$$

Процесс еще не закончился: этот расчет игнорирует то, что шестиугольники 6 и 7 могут иметь одинаковый цвет, обеспечивая для 18 возможность принимать q-3 цвета, вместо q-4. Разделение цветов на 7 приводит к $${\Omega }_3\left(q\right)={\Omega }_2\left(q\right)+1\left(Ур.9\right)$$ , что добавляет еще одно состояние для хроматической функции.

Кодирование и декодирование целых чисел

Перечислим вначале некоторые элементарные факты о выражении чисел по q-нарному основанию. Далее обобщим их для ограниченных геометрий визуальных меток. Типичные примеры для известных q-нарных оснований представляет собой двоичный (q=2), восьмеричный (q=8), шестнадцатеричный (q=16), используемые в информатике и в электротехнике, обычное десятичное (q=10) основание и т.д. Целое число может быть выражено, как многочлен в степенях q:

$$N={\sum }_{n=0}^k{a}_n{q}^n,where{a}_n<q,N<q^{k+1}\left(Ур.10\right)$$

Если известно значение N и требуется рассчитать {a_n}, можно следовать двумя путями. Используя [X], как целочисленную часть от X, получают рекурсии обратной итерации, как следующее (Nk+i=N):

$$a_n=\left[\frac{N_{n+1}}{q^n}\right],N_n=N_{n+1}-a_n{q}^n=N_{n+1}\mathrm{mod}\left(q^n\right)\forall n=k,k-\mathrm{1,}\dots 0\left(Ур.11\right)$$

В другом способе кодирования числа N, вначале рассчитывают α₀=N mod(q), затем вычитают его, как $$N_1=\frac{N-a_0}{q}$$ , и затем повторяют эту процедуру вперед:

$$a_k=N_k\mathrm{mod}\left(q\right),N_{k+1}=\left(N_k-a_k\right)\frac{1}{q^k},N_0=N\left(Ур.12\right)$$

Автор далее обобщает это представление с учетом переменных, которые представляют количество доступных вариантов вдоль пути кодирования. Следовательно, вместо q^k наших коэффициентов будет получено Q_k, где Q представляют собой произведения доступных состояний вдоль пути до k-1-ого элемента. При использовании простой аппроксимации Ω₁(q) в (Ур. 7), можно заранее рассчитать произведение Q_n вдоль пути кодирования и затем использовать форму

$$N={\displaystyle \sum _{n=0}^{n=k}{a}_n{Q}_n},Q_n={\displaystyle \prod _{k=0}^{n-1}{q}_k}forn>\mathrm{0,}{Q}_0=1\left(Ур.13\right)$$

Такое аппроксимированное кодирование показано в Таблицах 2-3. Таблица 2 содержит последовательность выбора цветов, вдоль пути кодирования, в соответствии с аппроксимацией "одного пути". В таблице 3 сведено затем кодирование числа 127 по метке 2 с ядром В. На каждом этапе кодер рассчитывает соответствующее произведение пути на Q_n из таблицы 2 и цифру цвета a_n=N_n-1mod(Q_n).

Как пояснялось в уравнениях (7-9), при учете нескольких путей, количество доступных состояний известно в заданной точке пути кодирования, но любой будущий выбор вдоль пути может зависеть от фактического выбора цветов. Этот факт исключает обратную итерацию (уравнение 7), при которой заранее требуется знать все Q_n. Однако прямой кодер все еще работает.

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

$$a_k=N_k\mathrm{mod}\left(q_k\right);N_{k+1}=\frac{N_k-a_k}{q_k},N_0=N\left(Ур.14\right)$$

На этапе k, соответствующем k-ой точки пути кодирования, Элис просматривает уже все расцвеченные ячейки и считывает фактическое значение Qk, представляющее число доступных цветов, включая в себя специальные случаи, в которых один или больше соседей расцвечены идентично. Nk известно из предыдущего этапа, поэтому она может прийти к расчету a_k и N_k+1.

Например (см. Таблицу 2), если N=127, она рассчитывает вначале а₀=127% 2=1, затем $$N_1=\frac{127-1}{2}=63$$ , a₁=63% 6=3, $$N_2=\frac{63-3}{6}=10$$ , a₂=10% 5=0, $$N_3=\frac{10}{5}=2$$ , a₃=2% 4=2, $$N_4=\frac{0}{4}=0$$ , как описано выше (а % х обозначает a mod(x)). Единственная разность, между апроксимацией одного пути и точной итерацией вперед состоит в том, что таблица 2 не может быть рассчитана заранее, но ее содержание должно быть сгенерировано на каждом этапе кодирования.

При прямой итерации, учитываются все части, которые вносят вклад в хроматическую функцию. Строгое доказательство этого заявления находится за пределами объема данного Приложения, и предполагает (помимо прочих вещей) представление того, что способ прямой итерации эквивалентен алгоритму мета-графа. Декодирование расцвеченного пути следует алгоритму кодирования, выполняемому в обратном порядке: после идентификации чисел цветов a_k и количества фактически доступных цветов Qk, вдоль пути кодирования, число N реконструируют (из уравнения 13).

Обработка в режиме реального времени для поиска всех меток изображения

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

Для специалистов с определенным опытом в области статистики известно, что закон больших чисел применяется после того, как количество выборок составляет М≥12. Следовательно, для достаточного статистического сигнала требуется дополнение больше, чем 12 пикселей на ячейку цвета. Для цветных меток это можно перевести в размер 7×12=84 пикселя и приблизительно с радиусом 21 пиксель для вписанного круга основания. Относительный размер метки/изображения при этом может быть очень малым в изображениях с высоким разрешением и составляет приблизительно 1% видеокадра с размером 240×240 пикселей. И наоборот, это может позволить обеспечить возможность идентификации максимального количества 10-15 объектов на изображение видеокадра. Если в приложении не требуется распознавать расположенные на очень большом расстоянии метки, можно существенно улучшить скорость обработки путем уменьшения разрешения изображения с высокой разрешающей способностью, чтобы меньшее из высоты и ширины изображения имело размер, приблизительно 240 пикселей. Минимальный размер прямоугольного окна будет затем фиксирован, как 24×24 пикселя. Такие числа используются только, как нулевое решение: в конкретном устройстве может потребоваться установка других параметров.

Специалист, имеющий навык в использовании способов обработки изображения, может помнить, как в вычислительной геометрии рассчитывают, находится ли пиксель внутри или за пределами выпуклого многоугольника. Это поясняется для пятиугольника, показанного на фиг.11. Рассчитывают скалярное произведение вектора положения пикселя, $$\overrightarrow{x}=\left(x,y\right)$$ с нормальными векторами сторон пятиугольника, и затем вычитают соответствующее пороговое значение θ_i. Если полученное в результате число является положительным, устанавливают σ_i=1, в противном случае, устанавливают σ_i=0. Для пикселей, расположенных внутри многоугольников, все σ_i должны быть равны 0. В качестве альтернативы, можно рассчитать знак направления Z осевых векторов $${\left(\overrightarrow{x}\times \left({\overrightarrow{r}}_2-\overrightarrow{r}1\right)\right)}_{z_1}$$ , где $${\overrightarrow{r}}_2$$ , $${\overrightarrow{r}}_1$$ представляют собой конечные точки заданной стороны пятиугольника, следуя в направлении по часовой стрелке. Оба способа являются очень эффективными и требуют одинакового количества операций.

При поиске оснований меток требуется рассчитать цветную гистограмму и определить, имеет ли она требуемую сигнатуру. Вначале изображение накрывают круглыми окнами с размером, например, 25, затем с размером 50, 100 и 200. Как показано на фиг.5, предлагается использовать шестиугольники вместо кругов. Учитывая стороны одного шестиугольника, как показано синим шестиугольником, обозначенным X, на фиг.5, и используя способ, представленный на фиг.11, для его воплощения. Шестиугольная решетка разделяется естественным образом на три подрешетки, показанные разными цветами на фиг.5, пиксель принадлежит шестиугольнику синей подрешетки, обозначенному X, если и только если он попадает между линиями, обозначенными (1, 2), (3, 4) и (5, 6).

Для специалиста, имеющего навыки в элементарной геометрии, будет не трудно определить, исходя из точки в плоскости и ее проекции на три основные направления нормальных векторов шестиугольника, что его подрешетка может быть рассчитана с использованием трех операций mod(3) и соответствующих координат шестиугольника тремя делениями на целое число. Каждый шестиугольник может быть описан системами координат трех целых чисел. В системе координат стандартного изображения, где координата у продолжается сверху вниз изображения, нормальные вектора шестиугольников составляют (0, 1), $$\left(\cos \frac{\pi }{3},\sin \frac{\pi }{3}\right)$$ и $$\left(-\cos \frac{\pi }{3},\sin \frac{\pi }{3}\right)$$ . Следует отметить, что система линий, ортогональных каждому нормальному вектору, должна включать в себя, как линии из точек, так и пунктирные линии, показанные на фиг.5. Вместо вещественных чисел, лежащих в интервале [-1, 1], можно использовать целые числа, представляющие их с точностью до трех или четырех знаков.

В соответствии с этим, после инициализации пустой гистограммы для каждого покрывающего шестиугольника, при одном проходе по изображению, обеспечивается возможность одновременного подсчета всех этих гистограмм. Кроме того, путем изменения размера шестиугольной решетки с коэффициентом два (не учитывая каждую вторую линию на фиг.5, можно одновременно подсчитать решетку "двойных размеров", которая покрывает шестиугольные гистограммы, используя только 6 дополнительных операций с целыми числами. Данные могут быть размещены таким образом, что требуется пройти только один раз через пиксели изображения: для каждого пикселя рассчитать его вклад в шестиугольник, покрывающий разные размеры. Кроме того, при оценке гистограммы, после приема большей ее части, можно на раннем этапе удалить части, которые не составляют основание метки.

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

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

Алгоритм декодирования метки

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

А2. Используя набор иерархически организованных шестиугольных окон, как пояснялось выше:

а) Для каждого окна рассчитать гистограмму тональных цветов без черного и белого (отсутствие цветов).

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

c) Если соответствие находится ниже некоторого порогового значения, удалить гистограмму, выйти.

d) Если будет найдено одно или больше соответствий, перейти к "области, представляющей интерес".

A3. Для каждой области, представляющей интерес

e) Найти шестиугольную белую или черную ячейку, проверить действительность метки кандидата. Если ОК, продолжить, если нет, удалить гистограмму, пропустить область, представляющую интерес.

f) В случае необходимости: выполнить баланс белого (найти правильную температуру освещения) на основе данных RGB, определенных по белой или черной области.

g) В случае необходимости: выполнить калибровку цветов: найти (R'G'B')=[Calibration_Matrix] (RGB) элементы матрицы преобразования, например, минимизировать функцию стоимости, (например, наименьшую квадратичную ошибку) между фактической и желательной сигнатурой, при поддержании постоянным значения гамма.

h) Декодировать метку: генерировать список цветов и их 2D положение (положения) (х, У).

i) Выполнить коррекцию ошибок и стирания, если применимо. Реконструировать пиксель цвета, в случае возникновения преграды (стирания). Если два или больше цвета расположены рядом друг с другом (ошибка), система выполнит все возможные случаи. Повернуть метку в стандартное положение,

j) Декодировать цифровой ключ из цветной строки вдоль общеизвестного пути кодирования.

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

А5. Выполнить действия, требуемые приложением. Пример: наложить данные на метки в изображении/видеопотоке.

Этап А2 представляет собой стандартный статистический тест, описанный здесь только с целью полноты. Каждый пиксель сохраняют в формате (R, G, В). Преобразуют его в формат (цвет, насыщенность, значение)=(H, S, V). Отделяют цвета от не цветов: задавая минимальное пороговое значение для насыщенности, все, что выше порога, учитывают как цвет, и все, что ниже порога, как черный или белый. Отделяют черное от белого цвета, учитывая среднее значение по трем цветовым каналам: если это значение велико, это - белый цвет, если низкое, это - черный. Для цветов рассчитывают 6 расстояний цветных пикселей до 6 опорных цветов в координатах RGB: используют Евклидово определение расстояния и учитывают минимум всех 6 расстояний. И снова, в случае, когда расстояние меньше, чем (в зависимости от цвета) пороговое значение, рассматривают пиксель, как принадлежащий соответствующему цветовому карману. Ожидаемое распределение цветовых тонов для основной метки А показано на фиг.12, и представляет собой сумму нормальных распределений, с центрами в {R, Y, G, С, В, М}. Следует отметить, что Этап 2 должен быть выполнен первым, так, что не представляющие интерес пиксели больше не обрабатываются.

После первого (грубого) соответствия с ожидаемым распределением выполняют второй тест, итеративно увеличивая размер окна. Записывают только наилучшее соответствие. Этап A3g представляет собой процедуру соответствия данных, которая приводит к малой задаче квадратичного программирования. Этап A3h является необычным в том, что на нем декодируют метку в смысле двумерной структуры, а не одномерной последовательности. Только после оценки ошибки и коррекции результат отображают вдоль стандартного пути кодирования, преобразованного в один или несколько целочисленных ключей. Эти ключи, в конечном итоге, используют для запроса базы данных, в которой содержатся связанные данные. В зависимости от приложений и ограничений по безопасности, данные (или их части) выводят и используют. Для специальных вариантов применение, таких, как отслеживание видеоданных, можно ускорить алгоритм путем оценки движения меток - объектов из нескольких последовательных кадров и, таким образом, анализируя только малую часть изображения, спрогнозированного, как содержащее метку.

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

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

Ссылочные документы

Ref. 1) Chandler, Donald G., Batterman, Eric P., Shah, Govind: Hexagonal, information encoding article, process and system, US Patent, 4874936, Filing date: Apr 8, 1988, Issue date: Oct 17, 1989; Polygonal information encoding article, process and system: Polygonal information encoding article, process and system, US Patent 4896029, Filing date: Mar 31, 1989, Issue date: Jan 23, 1990; US Patent number: 4998010, Filing date: Nov 16, 1989, Issue date: Mar 5, 1991

Ref. 2) Jancke, Gavin: System and method for encoding high density geometric symbol set, US Patent 7,936,901, Issue date. May 3, 2011

Ref. 3) http://en.wikipedia.ore/wiki/Bar codes see also: Burke, Harry E.: Automating

Management Information Systems: Barcode Engineering and Implementation - Thomson Learning, ISBN 0-442-20712-3: Nelson, Benjamin: Punched Cards to Bar Codes - Helmers Publishing, ISBN 0-911261-12-5.434 pages

Ref. 4) http://research.microsoft.com/en-us/proiects/hccb/about.aspx or

http://tag.microsoft.com/consumer/index.aspx

Ref. 5) http://www.oligo.de

Ref. 6) http://en.wikipedia.org/wiki/Graph math see also: Biggs, N.; Lloyd, E.; Wilson, R. (1986), Graph Theory, 1736-1936, Oxford University Press

Ref. 7) Fa-Yueh Wu ('1982): The Potts model. Reviews of Modem Physics. Vo. 54. pp.235-268

Ref. 8) http://en.wikipedia.org/wiki/Machine learning see also Duda, Richard O., Hart, Peter E., Stork, David G. (2001) Pattern classification (2nd edition), Wiley, New York, ISBN 0-471-05669-3. Bishop, C.M. (1995). Neural Networks for Pattern Recognition, Oxford University Press. ISBN 0-19-853864-2.

Ref. 9) http://en.wikipedia. org/wiki/B ar codes

Ref. 10) Conway, J.H. and Sloane, N.J.H. (1998) "Sphere Packings, Lattices and Groups" (Third Edition), TSBN 0-387-98585-9.

Ref. 11) Aste, Т. and Weaire, D. "The Pursuit of Perfect Packing" (Institute Of Physics Publishing London 2000) ISBN 0-7503-0648-3.

Ref. 12) http://en.wikipedia.org/wiki/Voronoi See also Delaunay, В.: Sur la sphere vide, Izvestia Akademii Nauk SSSR, Otdelenie Matematicheskikh i Estestvennykh Nauk, 7: 793- 800, 193; Voronoi, Georgy (1907). Nouvelles applications des parametres continus a la theorie des formes quadratiques. Journal fUr die Reine und Angewandte Mathematik, 133: 97-178, 1907 Aurenhammer, Franz (1991). Voronoi Diagrams - A Survey of a Fundamental Geometric Data Structure. ACM Computing Surveys, 23(3):345-405,1991.

Ref. 13) http://en.wikipedia.org/wiki/Grav Code F. Gray. Pulse code communication, March 17,1953 (filed Nov. 1947). U.S. Patent 2.632.058

Ref. 14) Kohonen, Т., "Self-Organization and Associative Memory", Springer Verlag, 1988, ISBN 0-387-18314-0

Ref. 15) httD://en.wikipedia.org/wiki/Turbo code. BERROU, Claude, ADDE, Patrick Precede de decodage d'un code convolutif a maximum de vraisemblance et ponderation des decisions et decodeur correspondant, Propriete Institut Telecom-Telecom Bretagne. 91 05279,01/04/1992

Ref. 16) http://en.wikipedia.org/wiki/Low-densitv parity-check code and MacKay, David J.C. " Information Theory, Inference, and Learning Algorithms", Cambridge University Press 2005, Chapter 47

Ref. 17) Appel, Kenneth; Haken, Wolfgang (1989), Every Planar Map is Four Colorable, AMS, p.xv, TSBN 0821851039

Ref. 18) Luby, M., Mitzenmacher, M., Shokrollahi A., Spielman. D.: "Efficient Erasure Correction Codes", IEEE Trans, on Information Theory, Special Issue on Codes and Graphs and Iterative Algorithms, Vol.47, No. 2, Feb. 2001.

Изобретение относится к средствам идентификации движущихся объектов. Технический результат заключается в повышении достоверности и простоты идентификации. Визуальную опорную метку формируют из массива ячеек, в котором каждая ячейка визуально отличается от всех других ячеек в заданном соседнем окружении и каждая из упомянутых ячеек содержит одиночный визуальный сигнал, например уникальный цвет, выбранный из конечного числа визуальных сигналов. 3 н. и 11 з.п. ф-лы, 19 ил., 3 табл.

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

2. Материальный носитель по п. 1, в котором упомянутое конечное число больше 4.

3. Материальный носитель по п. 1, в котором упомянутое конечное число равно 8.

4. Материальный носитель по п. 1, в котором цвета находятся в видимом спектре.

5. Материальный носитель по п. 4, в котором упомянутые цвета равномерно распределены по видимому спектру.

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

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

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

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

10. Способ по п. 9, в котором выбор цвета дополнительно определяется пропуском заданного числа цветов для каждого выбора, причем указанное число может быть различным для каждого выбора.

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

12. Способ по п. 11, содержащий этап, на котором проходят по тому же пути кодирования, который определен в п. 9 или 10.

13. Способ по п. 11 или 12, дополнительно содержащий этап, на котором декодируют целые числа с использованием в последовательности пропущенных цветов по п. 10.

14. Способ по п. 13, содержащий этап, на котором проверяют, что декодированные целые числа по п. 11 и 12 согласуются с путем кодирования по п. 9 и пропущенными цветами по п. 10.