Пользователь
0,0
рейтинг
28 августа 2011 в 01:19

Читаем QR код tutorial



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


В статье рассмотрены базовые особенности QR кодов и методика дешифрирования информации без использования вычислительных машин.


Иллюстраций: 14, символов: 8 510.




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


Решение задачи непосредственного чтения информации с QR-картинки рассмотрим на примере двух кодов. Информация была закодирована в online генераторе QR Coder.ru.




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


На случай некорректного чтения данных в QR применяются специальные коды, которые способны исправить недочёты при чтении. Это так называемые коды Рида-Соломона. Принцип вычисления кодов, а также исправление ошибок в блоках информации рассматривать не будем, это тема отдельной статьи. Корректирующие ошибки коды Рида-Соломона (RS) записываются после всех информационных данных. Это очень упрощает задачу непосредственного чтения информации: можно просто считать данные, не трогая коды. Как показывает практика, обычно бОльшую часть QR -матрицы занимают корректирующие RS-коды.

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


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




Здесь зелёным фломастером подчёркнуты пункты, которые нужно будет реализовать при непосредственном чтении кода. Остальные пункты можно опустить в виду того, что считывание производит человек.


Шаг 0. QR код




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



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


Размещение системной информации показано на рисунке:




Системная информация дублируется, что позволяет значительно понизить вероятность возникновения ошибок при детектировании кода и считывании. Системная информация – это 15 бит данных, среди которых первые 5 — это полезная информация, а остальные 10 – это BCH(15,5) код, который позволяет исправлять ошибки в системных данных. К классу BCH кодов относят и RS коды. Обратите внимание, что на рисунке две полоски по 15 бит не пересекаются.


Шаг 1. Чтение 5 бит системной информации


Как уже говорилось, интерес представляют только первые 5 бит. Из которых 2 бита показывают уровень коррекции ошибок, а остальные 3 бита показывают какая маска из доступных 8 применяется к данным. В рассматриваемых QR кодах системная информация содержит:




Шаг 2. Маска для системной информации


Кроме уже озвученных схем зашиты системной информации, в добавок, используется статическая маска, которая применяется к любой системной информации. Она имеет вид: 101010000010010. Так как имеет интерес только первые 5 бит, то маску можно сократить и легко запомнить: 10101 (десять-сто один). После применения операции «исключающего или» (xor) получаем информацию.


Возможные уровни коррекции ошибок:


L 01
M 00
Q 11
H 10


Возможные маски:


000 (i + j) mod 2 = 0
001 i mod 2 = 0
010 j mod 3 = 0
011 (i + j) mod 3 = 0
100 ((i div 2) + (j div 3)) mod 2 = 0
101 (i j) mod 2 + (i j) mod 3 = 0
110 ((i j) mod 2 + (i j) mod 3) mod 2 = 0
111 ((i+j) mod 2 + (i j) mod 3) mod 2 = 0




Шаг 3. Чтение заголовка данных


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




Список возможных режимов:


ECI 0111
Числовые 0001
Буквенно-числовые 0010
8-битный (байтный) 0100
Kanji 1000
Структурированное дополнение 0011
FNC1 0101 (1-я позиция)
1001 (2-я позиция)


Шаг 4. Применение маски к заголовку


После извлечения 4-х бит, описывающих режим, необходимо к ним применить маску.
В нашем случае для двух кодов используются разные маски. Маска определяется выражением, приведённым в таблице выше. Если данное выражение сводится к TRUE (верное) для бита с координатами (i,j), то бит инвертируется, иначе всё остаётся без изменений. Начало координат в левом верхнем углу (0,0). Взглянув на выражения, можно заметить в них закономерности. Для рассматриваемых QR кодов, маски будут выглядеть так:






Получим режимы:




Шаг 5. Чтение данных


После получения данных о режиме можно приступать к чтению информации. Надо оговорить, что наиболее интересно считывать числовые и буквенно-числовые данные, так как они легко интерпретируются. Но также не стоит бояться 8-битных. Это может быть также легко интерпретируемая информация. Например, многие онлайн генераторы QR текст кодируют в этом режиме, используя ASCII. Ещё одна причина, почему следует изначально прочитать режим это то, что от него зависит количество пакетов данных. Которая также зависит и от версии кода. Для версий с первой по девятую длины блоков для более читабельных режимов:


Числовые 10 бит / 4 бита
Буквенно-числовые 9 бит
8-битный (байтный) 8 бит


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




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




На рисунке видно, все 4 пакета представляют собой коды ASCII латинских букв, образующие слово «habr»


Естественно наилучшим способом остаётся достать телефон из кармана и, наведя камеру на QR-картинку, считать всю информацию. Однако в экстренных случаях может пригодиться и описанная методика. Конечно, в голове не удержишь все указатели режимов и типов масок, а также ASCII символы, но популярные комбинации запомнить (хотя бы те, что рассмотрены в статье) под силу.


Спецификация:


BS ISO/IEC 18004:2006. Information technology. Automatic identification and data capture techniques. QR Code 2005 bar code symbology specification. London: BSI. 2007. p. 126. ISBN 978-0-580-67368-9.

P.S. Соблюдайте правила ресурса и условия Creative Commons Attribution 3.0 Unported (CC BY 3.0)

P.P.S. Если ошибся блогом, то подскажите куда — перенесу.
Constantine @tgx
карма
513,0
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое

Комментарии (103)

  • +299
    Оху*ть…

    Простите.
    • +30
      Картинки завораживают! Если делали сами, то преклоняюсь. Даже если просто подбирали, очень круто.
      • +21
        Определенно, сами. Видите, на последней картинке, слово «habr».
        • +15
          Только вот клечатые коды, нарисованные не по клеточкам, выносят мозг %)
          • +5
            Извиняюсь. Дело в том, что пока равнял по одному краю, немного криво стало с другого. В равномерности клеточки я уверен. А вот в QR картинках не совсем. Возможно при масштабирование немного исказились.
            • +1
              *равнял -> ровнял
            • 0
              А в чем рисовали?
              • 0
                писал ниже
  • +2
    Просто супер!
    • +4
      Проводите курс для авторов учебников и пособий по теме «Как нужно подать информацию читателю?». Им это очень помог бы :) А за статью огромное спасибо.
  • –9
    Я распознал текст во втором коде, даже не читая статью и без смартфона :)
    • +11
      Нде… Пожалуй, стоило сразу добавить, что статью я все же прочитал и считаю ее великолепной, просто содержимое «некоторого текста» уж слишком очевидно.
    • +6
      вы контролер из аэроэкспресса? (у меня уже несколько раз проверяли валидность билета методом такого вот гениального взгляда на распечатку с баркодом, без всякой аппаратуры :))
      • +3
        Человеческий мозг способен творить чудеса. После некоторых тренировок можно действительно научиться читать коды. Даже url. В каких-нибудь стандартизированных применениях, например при считывание типового номера, можно процедуру декодирования свести буквально к 2-3 шагам. Причём, с очень большой вероятностью маска будет использоваться одна и та же.
        • +3
          Даже url?! Это и я читать могу.
    • 0
      Вот так?
  • +4
    Красочно, доступно, познавательно. Спасибо.
  • +47
    Мсье — тонкий извращенец! =)
    Читал как триллер.
  • +8
    И сколько времени у Вас занимает распознавание небольшого кода?
    • 0
      Перед тем как писать статью я пробовал декодировать несколько QR кодов. С листочком бумаги получается довольно быстро. Специально не засекал. Пробовал и без бумаги — в голове. Уже сложнее. Часто сбиваюсь — квадратики расплываются.
  • +7
    Статья идеальна для блога Алгоритмы
    • 0
      Мне кажется туда нужны статьи более серьёзного содержания.
      • +24
        Если уж это не серьёзная статья, то я что-то в этом мире не понимаю.
  • +44
    Можно узнать, в какой программе вы делали иллюстрации?
    • +23
      Да, можно. Векторный редактор Adobe Illustrator CS5. Месяц можно пользоваться бесплатно.
      • 0
        Даже CS4 подойдет, так написано в Tutorial Details Create a Marker Text Effect in Illustrator.
        Уроки уроками, а у вас еще и отличный пример использования.
      • 0
        А шрифт? Что-то впервые вижу такой
        • +1
          Цвет: #5F67FF (RGB: 95, 103, 255), Шрифт: Segoe Print (regular).
  • +14
    Реквестирую алгоритм чтения Матрицы
  • +32
    Честно говоря, предмет статьи мне не очень интересен, но подача материала и иллюстрации — на высоте. Извините за комментарий не по делу.
  • +5
    Статья хорошая. Помогает понять как работают декодеры.
    А вот лично руками я буду выяснять зашифрованное только если в 2012 все человечество будет в опасности, а чтобы спасти всех нужно ввести код, зашифрованный в qr коде, а все устройства будут уничтожены вирусом на тот момент.
    • +16
      Неплохой сюжет…

      «До взрыва оставалось пять минут. Он добрался до инструкции по отключению бомбы-которая-взорвёт-всю-солнечную систему. Код отключения был зашифрован в QR-коде… Он достал свой GooglePhone и в этот момент батарея полностью разрядилась. Решалась судьба всей Солнечной Системы… И тут он вспомнил про статью, которую прочёл недавно на одном айтишном сайте...»
      • +3
        Цикл «хабр спасает мир»
      • +6
        xkcd — «я знаю регулярные выражения»?
      • 0
        А теперь добавим немного драмы — треть кода съела собака смазалась. Так что придется курить Рида-Соломона %)
        • +3
          это отдельная история… хотя тем, кто обладает навыками быстро счёта в полях Галуа под силу и эта задача!
          • 0
            А теория Галуа тут при чем?
            • 0
              Коды Рида-Соломона используют особую арифметику: операции определены над конечным полем (поле Галуа).
  • +2
    Я бы даже не осмелился сделать данную операцию =). Спасибо за статью.
  • +1
    Вы гений…
    Я после прочтения статьи до сех пор отойти не могу, а вы это еще и сами писали.

    А вообще спасибо, когда то было интересно как читается qr код, но гуглить лень было.
    • +3
      кто же тогда это?;)
      www.insidepro.com/kk/010/010r.shtml
      • +1
        Это писал человек? :)
        • 0
          Я понимаю что я слегка опоздал с коментирием, но это невероятно.
          • 0
            *комментарием
  • +8
    распечатал и положил в папку. в 2012 пригодится, я уверен
    • +5
      в 2012 очень понадобятся навыки чтения QR-кодов. Уже сейчас можно начинать учить:
      • 0
        Опять же, коды можно делать и человеческими, но имеется достаточно жёсткий лимит по площади, используемой «не по назначению»:
        image
    • 0
      Увы, не пригодилось.
  • +11
    Такой хорошей статьи не видел на хабре очень давно. Картинки завораживают!
    • +4
      да, хабр торт!
  • +7
    ждем тоже самое о шрихкодах
    • +3
      Штрих коды — это проще, намного проще.
      • +2
        тогда ждем от вас
      • +1
        а как насчет Microsoft Tag?
        image
        • 0
          Смартфоном распознал ссылку на википедию.
          • +4
            А с выключенным интернетом слабо? Вот тут-то и обнаруживается…
          • +3
            Да ладно, там и глазами в принципе букву W можно заметить )
  • +9
    Я может-быть не в тему, но меня всё чаще посещает мысль, что блоги и посты не дают рождаться новым книгам, учебникам, трудам. Есть у человека допустим потенциал. Он потратил силы, написал пост или завёл блог. Получил кучу восторженных коментов и… успокоился. В психиатрии это называется положительное закрепление.

    Наверное я всё-таки не в тему… Автор молодец!
    • +2
      Пусть делают учебники по статьям из блогов и платят премию авторам.
      А эта статья просто отличная! Спасибо автору!
      • 0
        Надо выпускать серию книг Хабрахабр. А каждая книга это каждый блог. Например Алгоритмы.
  • +24
    Сейчас гадают судоку, через 10 лет будут разгадывать QR коды.
    • +2
      Попробую маме подсунуть, ей как раз надоели эти судоку)
    • +2
      Google Goggles и судоку может разгадывать :)
  • +2
    И зачем мне теперь qr-сканер в телефоне? =)
    • 0
      Хорошо что у меня есть qr-сканер на телефоне.
  • +3
    Идеал оформления и содержания статьи для хабра.
  • 0
    класс! Давно хотел в этом разобраться
  • +15
    The Sun Gate, Aymara culture, 600 AD, Tiahuanaco, Boliviaне завидую археологам, которым через other 9k лет придётся так же ломать головы над нашими бар-кодами. ;)
    • +3
      ну ладно баркоды, а представьте, что археологам попадутся файлы формата JPEG, а спецификацию они не найдут:)
      • 0
        как будто им будет легче если спецификацию найдут. она тоже будет на тарабарском
        • +8
          Спецификация будет в виде сканов в формате jpeg :)
    • +1
      Можно же вырубить статью на какой-нибудь скале!
      • 0
        Даа… предмет дискуссий в Сколково
    • +2
      image
  • 0
    Увидь матрицу! Познай ее величие!
    вы же видите матрицу?
    • 0
      А она есть )
  • 0
    Интересно было бы ещё прочесть про разбор Aztec Code, который часто используется в банковских документах. Платёжных поручениях например!
  • +4
    Вот чему детей в школах учить нужно! Молодые преподаватели, внимайте! :)
  • 0
    Я в прострации…

    А сколько времени уходит, чтобы прочесть один код вручную?
    • +2
      Я сейчас поэкспериментировал. Взяв ASCII таблицу и листочек с ручкой, я расшифровал код первой версии на странички Wikipedia за 6-7 минут. Самые проблемные места: много времени уходит на переписывание с картинки значений бит (проверяю 2 раза), также уходит время на двоичную арифметику. В итоге получилось слово «Ver1», 8-битный режим, маска i mod 2 ==0, т.е. строки с инверсией и без — чередуются.
    • +3
      Те кто обладают навыками в двоичной арифметике — попробуйте расшифровать, думаю после некоторых тренировок подобные коды можно расшифровывать за 3-4 минуты с листочком, а без неё и того быстрее.
  • +2
    Добавлю пару ссылок:
    Первая по всем почти системам дополнительной реальности базирующейся на QR- кодах:
    www.mindmeister.com/ru/91467151/augmented-reality
    Вот где простор для поиска идей стартапов.

    Вторая на YASN по QR кодам, QR кликам и Трек Глифам:
    daqri.com/

    Третья на цены программного обеспечения:
    www.metaio.com/store/

    Четвёртая на один межброузерный проект:
    www.artags.org/

    Все ссылки получены в пройессе работы над TЗ AI-Аватар.
    Желающие присоедениться к написанию ТЗ пишите в личку.
  • 0
    Картинки завораживают. Спасибо и за них, и за статью.
    Плюс в карму однозначно!
  • +1
    Иногда посещали страшные мысли: а что, если все надписи на улицах заменят на QR-коды?!
    Теперь знаю решение, спасибо автору: запасаемся листочками в клеточку и фломастерами :)
  • 0
    Создается код также, но в обратном порядке?
    • 0
      да, на Хабре где-то был топик-ссылка, где хороший человек в своём блоге рассказывает о QR коде. Надо отметить, что в QR существенные сложности для понимания могут составить коды, корректирующие ошибки.
  • +1
    Я почему-то затосковал за школьными тетрадями в клеточку :(
    • +3
      Рефлекс. На дату посмотрите.
  • 0
    Пока читал статью меня больше всего интересовало как же научить компьютер находить эти QR-коды. Это вам повезло у Вас клеточки тут. А я вот сделал фото недавно и там клеток нет нужно как-то выравнивать QR-код. Расскажите как это можно сделать?!
  • 0
    Да, вот как-то так: demotivation.me/images/20090317/sa7cau2rm8eg.jpg
  • 0
    Спасибо за статью. Все доходчиво и красиво!
  • 0
    Шикарная статья. Огромное спасибо — однозначно в избранное!
  • 0
    Надеюсь что этим придется заниматься just for fun, а не потому что кто-то забыл продублировать код текстом.
  • +1
    Эта статья — одна из немногих, которая заставила мозги пошевелиться после тёплого лета! Спасибо!
    • +2
      отставить панику! У нас завтра ещё целый день лета
  • +3
    image
  • 0
    Если бы каждый так оформлял статьи… В иных статьях все хорошо, кроме иллюстраций…
  • 0
    Автор, похоже, после вопроса «который час?» смотрит на часы, похожие на
    qrtime.com/
    ;)

    Респект!
  • 0
    а вот в белраше даже появилось qrcode.by/
  • 0
    В чем отличие в визуализации маски между серыми и черными квадратами в четвертом шаге?
    • 0
      Серые области — это области, к которым не применяется маска. Почему она не применяется? Потому что эти области несут иное (относительно контекста в 4-ом шаге) функциональное назначение, про них говорилось на 0-ом шаге. Если Вас интересуют детали — взгляните на спецификацию: там есть визуализация всех типов масок, регламентируемых стандартом.
      • 0
        Я правильно понимаю, что маскируется только к индикатору режима и области непосредственно данных? Что и отображено блоком черных пикселей в визуализации?

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