Введение

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

Использовать мы будем python вместе с opencv и numpy. Учитывая, что opencv - кросс-язычная библиотека, а также то, что работа с изображением/текстурой в разных решениях выглядят примерно одинаково, то я думаю, что вы без труда сможете перевести алгоритм, который будет здесь написан, на любой нужный вам язык

В первую очередь мы будем рассматривать полноразмерный qr-код, Micro-qr возможно будет рассмотрен после завершения работы над полноразмерным qr

Также, хочу отметить, что готовый класс QrCodeDetector уже имеется внутри opencv. Возможно, вам не нужно изобретать велосипед :-)

Обнаружение

Очевидно, что прежде, чем дешифровать qr-код, нужно для начала его обнаружить на картинке. Как же это делают наши смартфоны? Всё очень просто, специально для этого на Qr-коде есть вот эти три квадратика:

Пишем код

Как уже было сказано выше, использовать мы будем opencv и numpy. Импортируем эти библиотеки:

import cv2 as cv
import numpy as np

В первую очередь нам нужно найти первый чёрный пиксель на изображении, которое является трёхмерным массивом вида:

img[y, x, 1]

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

class QrHandler():
    def detect(self, img):
        for y in range(0, len(img)):
            for x in range(0, len(img[0])):
                if (img[y, x] < [50, 50, 50]).all():
                  print('black')

Кстати, ради дебага я использую режим чтения cv.IMREAD_COLOR, по существу он здесь совершенно не нужен, так что я советую заменить его на cv.IMREAD_GRAYSCALE

Мы нашли черный пиксель, теперь нам нужно проверить, что он является частью квадрата:

import cv2 as cv
import numpy as np


class QrHandler():
    def detect(self, img):
        for y in range(0, len(img)):
            for x in range(0, len(img[0])):
                if (img[y, x] < [50, 50, 50]).all():
                    square_length = self._get_square_length(img, y, x)
                    if square_length != -5:
                      prtint('square')

    # не забываем про помехи на изображении, поэтому при проверке какой-либо точки нужно проверять небольшой регион вокруг этой точки
    def _is_black_point(self, img, y, x, inaccuracy):
        y_2 = y + inaccuracy
        if y_2 >= len(img):
            y_2 = len(img) - 1
        x_2 = x + inaccuracy
        if x_2 >= len(img[0]):
            x_2 = len(img[0]) - 1
        for y in range(y - inaccuracy, y_2):
            for x in range(x - inaccuracy, x_2):
                if (img[y, x] < [50, 50, 50]).all():
                    return True
        return False

    def _get_square_length(self, img, y, x):
        square_length = 0
        # идём вправо по x и ищем конец квадрата, находим его примерную длину
        for x_i in range(x, len(img[0])):
            if (img[y, x_i] > [50, 50, 50]).all():
                break
            square_length += 1
        # слишком маленькая длина явно говорит нам о том, что это неподходящий квадратик, поэтому проверяем
        if square_length >= 6:
            #проверяем две точки: по y и по диагонали
            if self._is_black_point(img, y + square_length, x + square_length, 3) and self._is_black_point(img, y + square_length, x, 3):
                return square_length
        return -5

Здесь в функции get_square_length мы сначала ищем длину квадрата, проходя по нему до сюда:

А затем при помощи функции _is_black_point проверяем два региона:

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

Также, стоит проверить наличие вот этого маленького квадратика внутри:

Для этого в наш класс пишем еще одну функцию:

class QrHandler():
    def detect(self, img):
        for y in range(0, len(img)):
            for x in range(0, len(img[0])):
                if (img[y, x] < [50, 50, 50]).all():
                    square_length = self._get_square_length(img, y, x)
                    #добавляем нашу новую функцию в проверку квадратика
                    if square_length != -5 and self._is_has_lil_square(img, y, x, square_length):
                        print('square')
                        
    def _is_has_lil_square(self, img, y, x, square_length):
        lil_square_length = 0
        #находим центр найденного нами квадрата
        y = y + square_length // 2
        x = x + square_length // 2
        have_white = False
        #идем от центра, пока не найдем границу квадратика
        #запоминаем расстояние от центра до границы
        for x_lil in range(x, x + square_length):
            if (img[y, x_lil] > [50, 50, 50]).all():
                have_white = True
                break
            lil_square_length += 1
        if have_white:
            have_white = False
            lil_square_length_y = 0
            #если мы нашли границу по x, то потвторяем то же самое по y
            for y_lil in range(y, y + square_length):
                if (img[y_lil, x] > [50, 50, 50]).all():
                    have_white = True
                    break
                lil_square_length_y += 1
            #если нашли границу по y, то нужно проверить расстояние до нее от центра
            #расстояние по x и по y должно быть примерно равно друг другу
            if have_white and (lil_square_length_y in range(lil_square_length - 3, lil_square_length + 3)):
                #также нужно проверить нижнюю правую точку квадратика
                if self._is_black_point(img, y + lil_square_length, x + lil_square_length, 3):
                    return True
        return False

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

class QrHandler():
    def detect(self, img):
        for y in range(0, len(img)):
            for x in range(0, len(img[0])):
                if (img[y, x] < [50, 50, 50]).all():
                    square_length = self._get_square_length(img, y, x)
                    if square_length != -5 and self._is_has_lil_square(img, y, x, square_length):
                        #перебираем точки по y
                        for y_2 in range(y + square_length, len(img)):
                            if (img[y_2, x] < [50, 50, 50]).all():
                                square_length_2 = self._get_square_length(
                                    img, y_2, x)
                                if square_length_2 != -5 and self._is_has_lil_square(img, y_2, x, square_length_2):
                                    #после того как нашли потенциальный квадрат, 
                                    #нужно проверить, что его длина примерно равна длине уже найденного квадрата
                                    if square_length_2 in range(square_length - 3, square_length + 3):
                                        qr_size = y_2 - y
                                        #мы уже знаем расстояние между двумя квадратиками, поэтому нам не нужно проходиться по точкам
                                        #сразу проверяем потенциальную точку
                                        square_length_3 = self._get_square_length(
                                            img, y, x + qr_size)
                                        if square_length_3 != -5 and self._is_has_lil_square(img, y, x + qr_size, square_length_3):
                                            if square_length_3 in range(square_length - 3, square_length + 3):
                                                #проверяем квадратик по аналогии со вторм и возвращаем вырезанный qr
                                                return img[y: y + qr_size + square_length, x: x + qr_size + square_length]

По итогу мы получаем следующий код:

import cv2 as cv
import numpy as np


class QrHandler():
    def detect(self, img):
        for y in range(0, len(img)):
            for x in range(0, len(img[0])):
                if (img[y, x] < [50, 50, 50]).all():
                    square_length = self._get_square_length(img, y, x)
                    if square_length != -5 and self._is_has_lil_square(img, y, x, square_length):
                        for y_2 in range(y + square_length, len(img)):
                            if (img[y_2, x] < [50, 50, 50]).all():
                                square_length_2 = self._get_square_length(
                                    img, y_2, x)
                                if square_length_2 != -5 and self._is_has_lil_square(img, y_2, x, square_length_2):
                                    if square_length_2 in range(square_length - 3, square_length + 3):
                                        qr_size = y_2 - y
                                        square_length_3 = self._get_square_length(
                                            img, y, x + qr_size)
                                        if square_length_3 != -5 and self._is_has_lil_square(img, y, x + qr_size, square_length_3):
                                            if square_length_3 in range(square_length - 3, square_length + 3):
                                                return img[y: y + qr_size + square_length, x: x + qr_size + square_length]

    # не забываем про помехи на изображении, поэтому при проверке какой-либо точки нужно проверять небольшой регион вокруг этой точки
    def _is_black_point(self, img, y, x, inaccuracy):
        y_2 = y + inaccuracy
        if y_2 >= len(img):
            y_2 = len(img) - 1
        x_2 = x + inaccuracy
        if x_2 >= len(img[0]):
            x_2 = len(img[0]) - 1
        for y in range(y - inaccuracy, y_2):
            for x in range(x - inaccuracy, x_2):
                if (img[y, x] < [50, 50, 50]).all():
                    return True
        return False

    def _get_square_length(self, img, y, x):
        square_length = 0
        # идём вправо и ищем конец квадрата, ищем его примерную длину
        for x_i in range(x, len(img[0])):
            if (img[y, x_i] > [50, 50, 50]).all():
                break
            square_length += 1
        # слишком маленькая длина явно говорит нам о том, что это неподходящий квадратик, поэтому проверяем
        if square_length >= 6:
            if self._is_black_point(img, y + square_length, x + square_length, 3) and self._is_black_point(img, y + square_length, x, 3):
                return square_length
        return -5

    def _is_has_lil_square(self, img, y, x, square_length):
        lil_square_length = 0
        y = y + square_length // 2
        x = x + square_length // 2
        have_white = False
        for x_lil in range(x, x + square_length):
            if (img[y, x_lil] > [50, 50, 50]).all():
                have_white = True
                break
            lil_square_length += 1
        if have_white:
            have_white = False
            lil_square_length_y = 0
            for y_lil in range(y, y + square_length):
                if (img[y_lil, x] > [50, 50, 50]).all():
                    have_white = True
                    break
                lil_square_length_y += 1
            if have_white and (lil_square_length_y in range(lil_square_length - 3, lil_square_length + 3)):
                if self._is_black_point(img, y + lil_square_length, x + lil_square_length, 3):
                    return True
        return False

#первый аргумент этой функции - наименование вашего изображения в одной папке с исполняемым файлом
img = cv.imread('qr_wider.jpg', cv.IMREAD_COLOR)
qr_handler = QrHandler()
img = qr_handler.detect(img)
cv.imshow('test', img)
cv.waitKey(0)

Заключение

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

Код всех частей этого цикла можно найти в этом репозитории

Если вам необходимо получить полную информацию о qr-кодах, не ожидая выхода всех частей этого цикла, советую ознакомиться с данной документацией: ISO/IEC JTC 1/SC 31 N (arscreatio.com). Сущность qr-кода не сильно изменилась со времен его создания, поэтому не смотрите на то, что документация 2004 года

*нашел вариант на русском из нашего ГОСТ-а: ГОСТ Р ИСО/МЭК 18004-2015. Информационные технологии. Технологии автоматической идентификации и сбора данных. Спецификация символики штрихового кода QR Code (internet-law.ru)

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