Чтение QR-кода

[bondkim137]

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

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

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

Затем решил попробовать поискать отдельно квадраты-маркеры тем же методом:

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

Затем заметил, что середина каждого квадрата представляет собой симметричную конструкцию по обоим срезам вдоль X/Y, вроде такой:

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

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

Скорости сразу поднялись, ищет опорные квадраты относительно неплохо (картинка кликабельная)



Открытые вопросы, до которых еще не добрался, но которые уже созрели:
- как дешево выполнить нормализацию сигнала (оцифрование в два уровня), особенно с учетом того, что черный (да и белый в принципе) может быть градиентом и перелазить за статичную середину 0x80 (в примере захардкожено 0xC0)
- как развернуть по позициям трех опорных квадратов центральную проекцию квадратного рисунка в общем случае (с учетом искажений перспективы), что б 'на костылях' относительно неплохо работало, или проще поискать четвертый маленький опорный квадрат, на базе позиций трех основных? (он умеет сливаться с данными кода, на глаз я его вообще не сразу заметил)
- опорные квадраты ищутся в своих областях картинки, потому перевернутые исходники и далеко уехавшие не работают. Хотелось попробовать последовательно замалевать каждый квадрат после обнаружения и сканировать всю область, но положение двух квадратов на одной оси все портит.
- непонятно, можно ли что-нибудь сделать с размыванием картинки при ее движении. Специфика многих мобильных камер такова, что яркие пиксели засвечивают темные и при движении и вышеописанный метод плывет. Тут есть идеи как попробовать обойти.

Может быть, кто-нибудь имеет определенный опыт и сразу скажет, куда копать во избежание попыток изобрести велосипед с квадратными колесами?

P.S. Про динамическое программирование и нейронные сети имею представление, но лет на 15 устаревшее. На мой взгляд, и то и другое тут будет слишком медленным.

[arseniiv]

Совершенно дурацкая идея от меня:

bondkim137 в сообщении #1223942 писал(а):

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

Раз такая «градиентность» вызвана в основном разной освещённостью бумаги и подобными причинами, при которых белые и чёрные места осветляются/затемняются вместе, можно размытием попытаться устранить разницу между чёрным и белым, оставив примерно среднюю освещённость, на которую и ориентироваться. Только вот слишком чёрные и белые (по количеству соответствующих пикселей) QR-коды эту идею портят.

[bondkim137]

arseniiv в сообщении #1224685 писал(а):

размытием попытаться устранить разницу между чёрным и белым

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

[arseniiv]

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

-- Вт июн 13, 2017 01:00:15 --

bondkim137 в сообщении #1224810 писал(а):

Возможно, фильтр по гистограмме какой-нибудь поможет.

Да, если набрали гистограмму, это наверняка будет лучше. Но остальной фон тут тоже мешает. Если бы было известно, что QR-код более-менее совпадает с каким-то фиксированой квадратной областью картинки (по положению центра и площади — визуально это в каком-то смысле будет «хорошим наложением»; предложить пользователю всё-таки поднатужиться), можно было бы знать, что уж точно отсекать, и что в центре практически наверняка объект, оценки положения и площади фигуры полезно иметь.

[bondkim137]

arseniiv в сообщении #1224825 писал(а):

Да, если набрали гистограмму, это наверняка будет лучше. Но остальной фон тут тоже мешает

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

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

-- 14.06.2017, 00:44 --

А в идеале что-нибудь такое хочется, конечно, уметь сканировать:

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

[arseniiv]

Интересно, насколько полезно двоично делить гистограмму, смотря на то, какие области занимают пиксели из таких её кусков.

[bondkim137]

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

[bondkim137]

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

Тут функция ошибки (перевернутая) для лучшего найденного паттерна вдоль оси X/Y по краям (отфильтрованная) и сами найденные опорные квадраты выделены.

Выкинул magic-константу 0xC0 в качестве границы. Поехал пока дальше.

[Pavia]

arseniiv
Деление гистограммы на 2 класса хорошо известно как алгоритм Отцу.
Считается что лучше работает локальная бинаризация.
Пробовал применять разные алгоритмы бинаризациии к QR кодам ни один не порадовал.

-- Ср июн 14, 2017 10:28:33 --

Мысли в слух. Мысль ещё не сформировалась, скорее это эскиз мысли.
QR код это не что иное как матрица [1].
Есть алгоритм t-SNE который может восстановить регулярность. Причём ему даже опорные точки не нужны [2].
Осталось понять как подать данные.

Кстати в [1] можно разжиться базой-картинок с QR кодами .
[1] http://www.fit.vutbr.cz/research/groups ... MatrixCode
[2] http://distill.pub/2016/misread-tsne/

[bondkim137]

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

Записал систему уравнений:

$$\left\{ \begin{array}{rcl} (X_1-X_2)^2+(Y_1-Y_2)^2+(Z_1-Z_2)^2&=1& \\ (X_1-X_3)^2+(Y_1-Y_3)^2+(Z_1-Z_3)^2&=1& \\ (X_2-X_3)^2+(Y_2-Y_3)^2+(Z_2-Z_3)^2&=2& \\ \end{array} \right.$$

При этом, центральная проекция должна выглядеть как-то так:

$$\left\{ \begin{array}{rcl} A&=\frac{X}{Z}& \\ B&=\frac{Y}{Z}& \\ \end{array} \right.$$

где {A,B} - двухмерные координаты точки при центральной проекции)

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

$$\left\{ \begin{array}{rcl} Z_1^2{S_1}-2{Z_1}{Z_2}{S_1_2}+Z_2^2{S_2}-1&=0&\\ Z_1^2{S_1}-2{Z_1}{Z_3}{S_1_3}+Z_2^2{S_3}-1&=0&\\ Z_2^2{S_2}-2{Z_2}{Z_3}{S_2_3}+Z_3^2{S_3}-2&=0&\\ \end{array} \right.$$

Где S-это константы:

$$\left\{ \begin{array}{rcl} S_i_j &= {A_i}{A_j}+{B_i}{B_j}+1 &\\ S_i &= {A_i}^2+{B_i}^2+1 &\\ \end{array} \right.$$$

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

На примерах в сферическом вакууме вроде даже заработало, на практике же был озабочен тем, что адекватных решений оказалось несколько, а работает только одно

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


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

[bondkim137]

Давно не писал, был занят основной работой.

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

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

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

Пересекать прямые на листе-проекции просто.

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

Если кому-то интересно, опубликую итоговые формулы.

Картинка снизу кликабельная, можно посмотреть видео. Перевариваются любые наклоны (перспективы).


Аналогичным образом можно заниматься и экстрполяцией. В итоге, имея двухмерную проекцию квадрата (P0, P1, P2, P3), можно однозначно построить биекцию всей плоскости в пространстве, на которой этот квадрат лежит, с ее двухмерной проекцией:


-- 12.09.2017, 03:12 --

Вопрос уточнения позиции матрицы поддался следующим способом:

Зададим параметры - двухмерные смещения четырех точек - границ читаемой матрицы. Я задал в косоугольных координатах относительно базовой позиции матрицы-кода-четырехугольника. Всего 8 степеней свободы.

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

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

[arseniiv]

(Оффтоп)

bondkim137 в сообщении #1247120 писал(а):

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

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

$$(x, y) \mapsto \frac{Ax + By + C}{Dx + Ey + F}$$

[UPD: это бред, в посте ниже исправлено] и решить линейную систему, полученную подстановкой туда четырёх точек, а потом у нас есть формула, в которую знай только подставляй интересующие координаты (я так даже делал одну программу для снятия данных на фотографии или скане какого-то графика, хотя моей преданности хватило только на весьма далёкий от автоматизма инструмент с ужасным UI и почти никакими возможностями; но часть с применением и получением преобразования работала замечательно). Хотя, в принципе, геометрическое построение может быть и не таким долгим, не знаю (а то, что его точность достаточна, видно по скринам ).

bondkim137 в сообщении #1247120 писал(а):

можно однозначно построить биекцию всей плоскости в пространстве, на которой этот квадрат лежит, с ее двухмерной проекцией

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

[bondkim137]

arseniiv в сообщении #1247209 писал(а):

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

$$(x, y) \mapsto \frac{Ax + By + C}{Dx + Ey + F}$$

и решить линейную систему, полученную подстановкой туда четырёх точек

Где же Вы были раньше?
Для большого числа транслируемых точек, в частности - для растровых изображений, однозначно будет быстрее. Здесь точек мало, но тоже, вероятно, будет быстрее - надо будет попробовать.

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

-- 12.09.2017, 16:01 --

bondkim137 в сообщении #1247234 писал(а):

решить линейную систему, полученную подстановкой туда четырёх точек

Четыре двухмерные точки, восемь уравнений. Шесть неизвестных. Чего-то я не понял, вечером матчасть почитаю.

[arseniiv]

bondkim137 в сообщении #1247234 писал(а):

Где же Вы были раньше?

Вроде тут, да как-то, видимо, не до конца вчитывался… Кстати, я тут вам по памяти ерунду написал, это же для одной координаты преобразование, надо так:

$$(x, y) \mapsto \frac{(Ax + By + C, A'x + B'y + C')}{Dx + Ey + 1}.$$

Вот с остальным посоветовать мне до сих пор нечего, увы.

-- Вт сен 12, 2017 18:12:08 --

bondkim137 в сообщении #1247234 писал(а):

Четыре двухмерные точки, восемь уравнений. Шесть неизвестных. Чего-то я не понял, вечером матчасть почитаю.

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

[wrest]

bondkim137
Останется еще подкорректировать "рыбий глаз", как вы говорите (на самом деле скорее "бочку", т.к. "рыбий глаз" это намеренное искажение, а "бочка"\"подушка" - конструктивный дефект объектива).
Если он мешает, его надо корректировать до того как корректируется перспектива.

В первом приближении, получается так (википедия, https://en.wikipedia.org/wiki/Distortion_(optics) ):

$x_u=x_c+\dfrac{x_d-x_c}{1+Kr^2}$
$y_u=y_c+\dfrac{y_d-y_c}{1+Kr^2}$
$r=\sqrt{(x_d-x_c)^2+(y_d-y_c)^2}$
$(x_d,y_d)$ координаты искаженного пикселя
$(x_u,y_u)$ координаты неискаженного пикселя (скорректированные)
$(x_c,y_c)$ центр искажений (обычно -- центр полного изображения, т.е. точка лежащая на оптической оси объектива)
$K$ - коэффициент искажений (плюс для "бочки", минус для "подушки")

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

Но мне кажется, что в обычных смартфонах эти искажения очень невелики.