Исследование QR-кода

Таблицы 4.4.4 и 4.4.5 показывают, в каком порядке размещаются  биты восемнадцатиразрядного кода в  отмеченных областях.

Табл. 4.4.4

0	3	6	9	12	15
1	4	7	10	13	16
2	5	8	11	14	17

Табл. 4.4.5

0	1	2
3	4	5
6	7	8
9	10	11
12	13	14
15	16	17

4.5. Методические  указания к заданию 3.5

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

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

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

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

Рис. 4.5.1. Уровень коррекции  ошибок 01

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

Рис. 4.5.1. Уровень коррекции  ошибок 00

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

4.6. Методические  указания к заданию 3.6

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

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

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

 

Табл. 4.6.1

Код маски	Соотношение
000
001
010
011
100
101
110
111

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

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

Рис. 4.6.1. Система координат

Формулы используются следующим  образом: если координаты рассматриваемого модуля матрицы удовлетворяют данному  соотношению, то этот модуль инвертируется. Рассчитанные по формулам таблицы 4.6.1 «узоры» приведены в Приложении 1.

В данном задании требуется  лишь определить, какая из восьми масок применена для преобразования исследуемой матрицы. Чтобы выполнить задание, нужно считать три бита, расположенных в разрядах 12, 11 и 10 (см. рис. 4.4). Считанные три бита нужно сложить по правилу Исключающее ИЛИ с числом 101. Полученный результат определяет вид использованной маски  в данной матрице (табл. 4.6.1).

4.7. Методические  указания к заданию 3.7

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

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

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

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

Рис. 4.7.1. Порядок считывания битов

Названия форматов при  различных значениях кода указаны  в табл. 4.7.1.

Табл. 4.7.1

Код	Формат
0001	Цифровой
0010	Символьный
0100	Двоичный
1000	Японский

4.8. Методические  указания к заданию 3.8

Предположим, что требуется  вручную декодировать матрицу QR-кода, показанную на рис. 4.8.1.

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

.    (4.6.1)

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

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

Рис. 4.8.1. Матрица

Процесс наложения фактической  маски на матрицу (рис. 4.8.1) показан  на рис. 4.8.4.

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

Рис. 4.8.2. Расчетная маска

Рис. 4.8.3. Фактическая маска

 

Рис. 4.8.4. Совмещение матрицы  и фактической маски

а)          б)            в)

Рис. 4.8.5. Инвертирование выделенных модулей

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

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

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

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

а)          б)            в)

Рис. 4.8.6. Нумерация информационных модулей

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

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

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

Табл. 4.8.1

Номера модулей	Биты	Десятичное число	Символ
13…20	01010000	80	P
21…28	01110000	114	r
29…36	01101111	111	o
37…44	01100010	98	b
45…52	01100001	97	a

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

 
4.9. Методические указания  к заданию 3.9

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

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

Второе правило дает штраф  за каждый одноцветный квадрат размером 2x2 пикселя.

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

Четвертое правило начисляет  штраф, если более половины пикселей одного цвета.

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

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

Для примера используем матрицу, показанную на рис. 4.8.1. Вычислим штрафные баллы построчно.

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

Рис. 4.9.1. Первая строка матрицы

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

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

Рис. 4.9.2. Вторая строка матрицы

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

Рис. 4.9.3. Третья строка матрицы

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

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

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