Меню
Главная
Авторизация/Регистрация
 
Главная arrow Информатика arrow Информатика 2015

3.7. QR-коды

Современные информационные технологии стремительно внедряются в нашу повседневную жизнь. Удивительные возможности помехоустойчивого кодирования можно рассмотреть на примере QR-кодов.

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

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

QR-код (англ, quick response — быстрый отклик) — матричный код, разработанный японской компанией «Denso-Wave» в 1994 году.

Вместимость одной кодовой матрицы не является безграничной. Максимальное количество символов, которые можно поместить в одну матрицу, зависит от вида кодируемой информации (цифры, буквы, двоичный код, иероглифы), уровня коррекции ошибок и версии используемого QR-кода. Для версии 40 в одной матрице при минимальном уровне коррекции ошибок можно разместить 7089 десятичных цифр, либо 4296 букв и цифр, либо 2953 двоичных данных, либо 1817 иероглифов.

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

С помощью QR-кодов удобно делать визитки и размещать их на майках, фуражках, значках. Коды открывают большие возможности для рекламы. За счёт размещения QR-кода на рекламном щите, плакате (постере) или объявлении можно привлечь большое число клиентов.

Для того чтобы сделать туристические маршру ты более информативными, на улицах г. Львова (Украина) размещено более 80 изображений QR- кодов. Ими оснащены коммерческие и культурные объекты, в том числе памятники, архитектурные сооружения.

QR-коды используются для маркировки ответственных деталей. Гравировка металлической поверхности позволяет наносить код на детали, подвергающиеся воздействиям высоких температур, давлений или агрессивных химических веществ. Данный код имеет высокую помехоустойчивость. Даже при наличии повреждений (искажений) изображения на площади 30% всё еще есть возможность безошибочно считать информацию.

QR-код не является единственным вариантом двухмерного штрихкода. Известны и другие форматы: DataMatrix, ScanLife EZcode и Microsoft Tag (Tag).

Три квадрата в углах изображения QR-кода позволяют устройству правильно определять его пространственную ориентацию. Черные и белые точки изображения преобразуются считывающим устройством в двоичные числа. Затем производится обработка цифровой информации. На матрице размещается системная информация, информационные биты, корректирующие биты. При обработке считанного изображения используется алгоритм Рида-Соломона, который позволяет устранить греть возможных искажений матрицы.

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

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

Уровень коррекции ошибок

Код

Допустимые

искажения

L

01

7%

М

00

15%

Q

11

25%

Н

10

30%

Уровни L и М рекомендуется использовать для печати кодов на пригласительных билетах, объявлениях, визитках, плакатах, рекламных щитах и г.д. Уровни Q и Н применяют для маркировки промышленных деталей, когда существует высокая вероятность повреждения изображения кода.

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

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

Информационные биты, контрольные биты и системная информация располагаются в определённых местах матрицы. Порядок размещения всех элементов матрицы определены правилами, которые описаны в спецификации [23].

7%

15%

25%

30%

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

В настоящее время создано 40 версий QR-кодов. На матрицах QR- кодов, начиная с версии 2, имеются метки центровки 4. В версии 1 такой метки нет, но в старших версиях QR- кода можно насчитать 46 таких меток.

В областях 5 для версий старше шестой размещается информация о версии кода. В четырех модулях 6 содержится код, которые определяет, какой вид данных содержится в матрице. Системная информация размещается в областях 7 и 8.

Информация об уровне коррекции ошибок и виде использованной маски располагается в системной строке (см. рисунок слева). Разряды 14 и 13 содержат сведения об используемом уровне коррекции ошибок. Разряды 12, 11 и 10 показывают, какая маска использована для наложения на информационные и корректирующие биты. Три бита позволяют сформировать коды для восьми разных масок.

Системная информация дублируется. Один раз 15 системных битов размещают в столбце 8 (счет элементов ведется, начиная с 0 из левого верхнего угла матрицы).

Второй раз системную информацию размещают в строке 8.

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

Существует 40 версий QR-кода. С увеличением номера версии кода объем помещаемых в матрицу данных увеличивается. Определить, к какой версии относится данная матрица, можно тремя способами:

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

В таблице приведена информация о числе модулей (пикселей) для различных версий QR-кодов.

Версия

Число модулей

1

21x21

2

25x25

3

29x29

40

177x177

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

Версия

Строки

Версия

Строки

2

6

18

8

6

24

42

3

6

22

9

6

26

46

4

6

26

10

6

28

50

5

6

30

11

6

30

54

6

6

34

12

6

32

58

7

6

22

38

13

6

34

62

В таблице приведены сведения о координатах меток центровки для версий 2... 13 ____

На следующем рисунке для примера показано изображение матрицы QR-кода версии 7.

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

На матрицах, начиная с версии 7, имеются две области, где содержится закодированная информация об использованной версии. Эти области отмечены на рисунке, цифрами 1 и 2. В таблице приведены коды некоторых версий QR-кода.

Версия

Код

7

001010010011111000

8

000111101101000100

9

100110010101100100

10

011001011001010100

11

011011111101110100

12

001000110111001100

13

111000100001101100

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

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

0

3

6

9

12

15

1

4

7

10

13

16

2

5

СО

11

14

17

Рассмотрим, как определить уровень коррекции ошибок. Так как системная информация дублируется, то сведения о имеющейся корректирующей способности кода можно отыскать в двух местах матрицы. Один раз 15 бит системной информации помещаются в строке 1 (отсчет слева направо), а второй раз - в столбце 2 (отсчёт снизу-вверх). Есгесэвенно, что эти два значения одинаковые. Сведения об уровне коррекции ошибок содержатся в первых двух битах системной информации. Эти два бита расположены в 14 и 13 разрядах системной строки.

Па следующем рисунке первые два бита в системной строке равны 1.

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

В результате сложения получим:

11010 = 01.

Код 01 соответствует уровню коррекции ошибок L (7%).

На следующем рисунке показана матрица, в которой использован иной уровень коррекции ошибок. Первые два бита во взором случае равны 10. Суммирование с маской 10 дает результат 00. Это говорит о том, что в этой матрице использован код с уровнем коррекции ошибок М (15%).

Аналогично производятся вычисления для матриц с уровнями коррекции ошибок Q и Н. На этих матрицах системная информация начинается битами 01 и 00 соответственно. Суммирование с маской 10 даст двоичные коды 11 и 10 соответственно.

Для повышения надёжности сканирования матрицы подвергают дополнительной обработке. Целью этой обработки является формирование такого рисунка (конфигурации) матрицы, на котором было бы как можно меньше смежных модулей одинакового цвета. Простыми словами это требование можно сформулировать гак: «Матрица должна быть пёстрой и на ней должно быть минимум однотонных сплошных протяжённых участков». Этим облегчается работа сканирующей аппаратуры, например, мобильных телефонов.

Цель достигается следующим образом: формируют 8 матриц с одинаковым информационным содержанием, но разного вида (разной формы). Для этого используют 8 заранее подготовленных масок, которые суммируют с исходной матрицей по правилу Исключающее ИЛИ. Полученные матрицы поочередно подвергают математической обработке, в результате которой выбирают одну матрицу. Отбор матриц осуществляют путем вычисления штрафных баллов. Для оптимальной (наиболее «пёстрой») матрицы число штрафных баллов будет минимальным среди восьми чисел.

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

Код маски

Соотношение

000

(/ + j)mod2 = 0

001

i mod 2 = 0

010

jmod3 = 0

011

(z + j) mod3 = 0

100

((i div 2) + (j div3))mod2 = 0

101

(/• j)mod2 + (z- j)mod3=0

110

((z • j) mod2 + (z- j) mod3) mod2 = 0

111

((/• j')mod3+(z- j) mod 2) mod 2 = 0

В таблице использованы обозначения: j - номер строки матрицы; i - номер столбца; mod - операция поиска остатка от целочисленного деления; div- операция деления.

Порядок определения координат модулей иллюстрирует рисунок.

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

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

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

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

Порядок нумерации битов показан на рисунке, причём старший разряд кода формата находится в клетке, отмеченной цифрой 1.

Рассмотрим порядок ручного декодирования матрицы, показанной на рисунке.

Вначале нужно определить, какой вид маски использован при её кодировании. В разрядах 12, И и 10 системной отроки записано двоичное слово 111. Сложение со статической маской 101 дает двоичное число 010. По таблице кодов маски легко определить формулу, использованную для формирования маски:

jmod3 = 0.

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

Анализируя рисунок в), можно заметить, что от изменения защищены

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

Процесс наложения фактической маски на декодируемую матрицу показан на рисунке слева.

Наибольший интерес для декодирования представляет область матрицы, расположенная в её правом нижнем углу. Здесь находятся информационные биты. Рассмотрим детально эту зону. Рисунок а) показывает фрагмент исходной матрицы, который должен быть подвержен обработке. На рисунке 6) выделены модули, которые должны быть проинвертированы. Следует обратить внимание, что верхняя граница рисунка совпадает с системной строкой. Результат наложения маски и декодируемой матрицы показан на рисунке в).

Из рисунка в) видно, что модули третьего и шестого столбца справа были проинвертированы.

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

Порядок считывания декодируемой информации показан на рисунке.

В соответствии с двоичным форматом данных следующие 8 бит (клетки 5... 12) указывают, сколько символов содержится в сообщении. Двоичное число 00000101 говорит о том, что данное сообщение содержит пять символов.

В очередных восьми клетках 13... 20 (см. рисунок а) размещено двоичное слово 01010000. Перевод этого байта в десятичную систему счисления даёт число 80. По таблице СР-1251 легко определить, что данному коду соответствует латинская буква «Р».

Следует обратить внимание на порядок нумерации модулей. Номера располагаются друг за другом в виде змейки.

Результаты декодирования сообщения приведены в таблице.

Номера модулей

Биты

Десятичное число

Символ

13... 20

01010000

80

Р

21... 28

01110000

114

г

29... 36

01101111

111

0

37... 44

01100010

98

b

45... 52

01100001

97

а

Таким образом, в результате ручного декодирования было определено, что матрица содержит слово «РгоЬа».

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

Согласно первому правилу штраф назначается за каждую группу из пяти или более одноцветных пикселей в одной строке. Штрафные функции но столбцам вычисляются аналогично. Второе правило дает штраф за каждый одноцветный квадрат размером 2x2 пикселя. Третье правило определяет штраф, если на матрице есть области, которые похожи на указатели определения ориентации. Четвёртое правило начисляет штраф, если более половины пикселей одного цвета.

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

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

Расчет ведется следующим образом. Если в строке имеется группа из пяти смежных одноцветных пикселей, то начисляется три штрафных балла. За каждый последующий пиксель, который примыкает к группе, начисляется дополнительно по одному баллу. Таким образом, первая группа черных пикселей дает вклад 3 + 1 + 1 = 5 баллов. Вторая группа из семи черных пикселей также дает 5 штрафных баллов. В общей сложности первая строка дала 10 штрафных баллов.

Вторая сверху строка матрицы показана на следующем рисунке.

В этой строке есть две группы но пять белых пикселей. Эти две группы в сумме дают 6 штрафных баллов.

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

На следующем рисунке показаны штрафные баллы гго всем строкам и столбцам матрицы.

Затем рассчитываются суммарные значения штрафных баллов гго строкам и гго столбцам. Для рассматриваемого г гримера суммарное число штрафных баллов по строкам равно 88, а гго столбцам 102. Общее число штрафных балов, вычисленное по ггервому правилу для данной маски, даёт число 190.

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

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ ОРИГИНАЛ   След >
 

Популярные страницы