Определение пространственной ориентации объекта, маркированного QR кодом

Определение пространственной ориентации объекта, маркированного QR кодом

Санкт-Петербургский ГосУдарственный политехнический университет

ИНСТИТУТ МЕТАЛУРГИИ, МАШИНОСТРОЕНИЯ И ТРАНСПОРТА

ОТДЕЛЕНИЕ ТЕХНОЛОГИЙ МАШИНОСТРОЕНИЯ

Кафедра «Мехатроника и роботостроение» (при ЦНИИ РТК)

ВЫПУСКНАЯ РАБОТА БАКАЛАВРА

Тема: Определение пространственной ориентации объекта, маркированного QR кодом

Направление: 220200.62.01 «Автоматизация и управление»

Санкт-Петербург, 2013

Реферат

КОД, КАМЕРА, ОБНАРУЖЕНИЕ И РАСПОЗНАВАНИЕ МЕТКИ, ПРОСТРАНСТВЕННАЯ ОРИЕНТАЦИЯ QR КОДА, РАЗРАБОТКА АЛГОРИТМОВ

Целью этой работы является разработка приложения для обнаружения, расшифровки и определения положения QR кода в пространстве.

С помощью библиотеки OpenCV реализовано обнаружение и обработка QR кода. На основе спецификации ISO/IEC 18004 Information technology - Automatic identification and data capture techniques - Bar code symbology - QR Code (Информационная технология - Автоматическая идентификация и сбор данных - Символика штрихового кода - QR Код) изучен и программно реализован алгоритм расшифровки QR кода. Разработан алгоритм определения положения QR кода в системе координат, связанной с камерой.

Данное приложение может быть использования для нахождения определенного объекта среди объектов, на которых нанесен QR код и позиционирования манипулятора с использованием данных об ориентации плоскости QR кода.

Содержание

Введение

. Алгоритмы распознавания графического маркера

.1 Алгоритм обнаружения QR кода

.2 Алгоритм расшифровки QR кода

. Методы 3D реконструкции

.1 Метод триангуляции

.2 Стереозрение

.3 Определение ориентации плоскости QR кода относительно камеры

. Программное обеспечение для распознавания QR кода и определения его ориентации

.1 Описание программы

.2 Тестирование программы

. Применение разработанного программного обеспечения

Заключение

Список использованных источников

Перечень условных обозначений, терминов и сокращений

Введение

код плоскость программный обеспечение

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

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

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

Отметим, что QR-коды могут быть выполнены с использованием бинарных сочетаний цветов, отличных от сочетания «черный-белый». Главное, чтобы между темными и светлыми участками был четко выраженный контраст.

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

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

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

В первом разделе описаны разработанные алгоритмы обнаружения и расшифровки QR кода.

Во втором разделе приведен обзор методов нахождения координат объекта и описан разработанный алгоритм определения ориентации объекта по графическому маркеру.

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

1. Алгоритмы распознавания графического маркера

.1 Алгоритм обнаружения QR кода

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

Рисунок 1 - Изначальное изображение

Ниже приведен алгоритм обнаружения QR кода, реализованный с помощью библиотек VideoInput и OpenCV. Идея данного алгоритма описывается в [1]. Данный алгоритм был нами модифицирован и дополнен деталями необходимыми для его практического использования.

В качестве технического средства была использована веб-камера Ritmix RVC-006M с матрицей 0,3 мегапикс, разрешением видео 640*480, подключенная через USB 2.0. А в качестве среды разработки была выбрана среда Visual Studio 2010, а в качестве языка программирования - C++ . такой выбор обусловлен тем, что на этом языке написана мощная профессиональная библиотека для реализации задач компьютерного зрения OpenCV. Также для осуществления захвата видео была использована библиотека videoInput.- Библиотека компьютерного зрения с открытым исходным кодом(Open Source Computer Vision Library), содержащая более 500 функций. До первой версии разработкой занималась русская команда Intel в Нижнем Новгороде. Библиотека содержит алгоритмы для обработки, реконструкции и очистки изображений, распознания образов, захвата видео, слежения за объектами, калибровки камер и др. [2].

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

Приложения должны быть переносимыми, оптимизированными, код которых не обязательно должен быть открытым. Приложения также могут создаваться в коммерческих целях. OpenCV поддерживает компиляторы Visual C++, Borland C++, Intel Compiler, MinGW, GCC, Intel Compiler, Carbon. В начале мы подключаемся к web камере с помощью библиотеки VideoInput и делаем снимок QR кода и далее начинаем обработку снимка (рисунок 5). Преобразуем полученное изображение в градации серого, делаем изображение двоичным с помощью порогового преобразования. Всем пикселям, значение которых меньше порога, присваиваем значение 255 - белый цвет, всем пикселям, значение которых выше порога присваиваем 0 - черный цвет. Для получения корректного результата нужно, чтобы снимок был достаточно контрастным. Таким образом, мы получаем черно-белое изображение.

Далее находим все контуры, которые присутствуют на черно-белой картинке. Теперь среди найденных контуров нам необходимо найти 3 мишени. Мишень - область QR кода образованная тремя вложенными квадратами с отношением сторон 7:5:3 (рисунок 2).

Рисунок 2 - Мишень QR кода

Считаем мишенью квадрат, имеющий внутри себя два вложенных квадрата (рисунок 3).

Рисунок 3 - Изображение с найденными мишенями

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

В цикле обходим все контуры и ищем квадраты. Чтобы определить, что контур является квадратом, используем два критерия поиска: 1) мы найдем размеры минимального прямоугольника, охватывающего текущий контур и, перемножив размеры, получим площадь этого прямоугольника. Напрямую с помощью специальной функции OpenCV найдем площадь контура. Если площади контура и прямоугольника, ограничивающего контур, примерно совпадают, то можно считать этот контур прямоугольником;

) сравниваем высоту и ширину прямоугольника, ограничивающего контур. Если они примерно равны, то считаем это прямоугольник квадратом.

Определяем точки-вершины каждой мишени. Мы имеем все вершины QR кода кроме правой нижней. Для того, чтобы ее определить проведем прямые линии через правую сторону правой верхней мишени и нижнюю сторону левой нижней мишени. Точка пересечения данных прямых (точка А на рисунке 4) будет искомой нижней правой вершиной QR кода.

Рисунок 4 - Нахождение правой нижней вершины QR кода

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

.2 Алгоритм расшифровки QR кода

Полученный методами компьютерного зрения массив нулей и единиц будет расшифрован с помощью алгоритма, описанного в спецификации ISO/IEC 18004 Информационная технология - Автоматическая идентификация и сбор данных - Символика штрихового кода - QR Код [3]. Опишем данный алгоритм:

) получение массива "0" и "1" бит;

) считывание информации о формате QR кода. Извлечение информации о маске (рисунок 5);

Рисунок 5 - Состав QR кода

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

(i + j) mod 2 = 0, (1)

(i)mod 2 = 0, (2)

(j)mod 3 = 0, (3)

(i + j) mod 3 = 0, (4)

((i div 2) + (j div 3)) mod 2 = 0, (5)

(i j) mod 2 + (i j) mod 3 = 0, (6)

((i j) mod 2 + (i j) mod 3) mod 2 = 0, (7)

((i j) mod 3 + (i+j) mod 2) mod 2 = 0, (8)

где i и j - номера ячеек.

Рисунок 6 - Виды масок

Применяем маску к полученному нами массиву посредством операции XOR (рисунок 7);

Рисунок 7 - Применение маски

5) определение режима кодирования и считывание кода в соответствии с правилами размещения и восстановление данных и кодовых слов в сообщении.

Узнаем индикатор режима по четырем битам в правом нижнем углу и соответствующий ему режим по таблице 1.

В данной работе мы реализуем два режима: числовой и 8-битный. Цифровой режим кодирует данные из десятичного набора цифр (0 - 9) (ASCII значения 30HEX к 39HEX) при нормальной плотности 3 символа данных на 10 бит. В 8-битный режиме кодируется 8-битный Latin/Kana набор символов в соответствии с JIS X 0201 (символьные значения 00hex к FFhex). В этом режиме плотность данных составляет 8 бит / символ;

) обнаружение ошибок с помощью коррекции ошибок кодовых слов. Если любая ошибка обнаружена, то исправить ее;

Таблица 1 - Режимы кодирования

) разделение кодовых слов данных на сегменты в зависимости от режима и показателями количество символов (рисунок 8).

Считывание происходит змейкой, начиная с правой нижней ячейки (рисунок 9). Старший значащий бит (бит 7) каждого кодового блока находится в первом доступном положении модуля;

Рисунок 8 - Сегменты с данными

Рисунок 9 - Считывание бит

) наконец, декодирование данных в соответствии с режимом.

2. Методы 3D реконструкции

.1 Метод триангуляции

Триангуляция - это способ измерения расстояний и определения положения объектов, часто с использованием лазера. Он использует способность лазерного луча распространяться в хорошо коллимированной форме (т.е. с малой расходимостью) на большие расстояния. Обычно лазерный луч освещает точку, расстояние до которой от лазерного устройства необходимо измерить; по существу, лазер используется в качестве указателя. Рассеянное или зеркальное отражения от этой точки контролируются детектором, который устанавливается на некотором расстоянии от лазерного луча, таком, что источник лазерного излучения, объекта и детектор образуют треугольник. На детекторе линза фокусирует отраженный свет на ПЗС-матрице, и положение яркого пятна на чипе показывает направление входящего света, т. е. угол между лазерным лучом и возвращенным светом, откуда расстояние и может быть рассчитано [4].

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

Принцип триангуляции также может быть реализован с помощью лазерного луча, в направлении которого производится быстрое сканирование в двух измерениях (рисунок 10). Таким образом, можно получить трехмерные (3D) изображения.

В идеале, лазерный источник для триангуляции должен иметь высокое качество пучка, чтобы осветить небольшое пятно на большом расстоянии. Так же требуется определенная оптическая мощность, особенно для целей с рассеянным отражением. Лучше использовать безопасные для глаз длины волны лазерного излучения (например, в 1,5 мкм области), хотя видимый луч помогает убедиться, что подсвечена правильная точка.

Триангуляционный метод измерения - это перспективный и широко применяемый подход к решению важных измерительных задач в разных областях науки. Этот метод в основном использовался в геодезии и картографии, и только с недавних пор стал развиваться в направлении линейно-угловых измерений и контроля точных деталей сложной формы. Связано данное обстоятельство в первую очередь с тем, что электронные компоненты необходимые для создания устройств на базе триангуляционного метода не соответствовали требованиям, предъявляемым к ним, и были невыгодны для внедрения в производство по соотношению цена-качество, но сейчас положение изменилось к лучшему. Метод оптической триангуляции положен в основу современных измерительных устройств, таких как триангуляционные щупы и датчики, лазерные 2D/3D профиломеры, лазерные 3D сканеры и другие.

 <#"722854.files/image011.jpg">

Рисунок 11 - Восстановление точки прообраза

Точку прообраза можно восстановить и с помощью альтернативного, чисто алгебраического подхода: для данных проекционных матриц М и М' и согласованных точек р и р' условия zp = MP и z'p' = MP можно переписать следующим образом: p*MP = 0, p`*M`P = 0.

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

Можно восстановить точку прообраза, соотнесенную с р и р', как точку Q с образами q и q' минимизировав величину d2(p,q) + d2(p'',q'). В отличие от двух других методов, представленных в этом разделе, данный подход не позволяет аналитически вычислить восстановленную точку.

2.3 Определение ориентации плоскости QR кода относительно камеры

Математическая модель камеры

С точкой О (рисунок 12), в которой находится камера, свяжем систему координат (X,Y,Z). Из этой точки опустим перпендикуляр на картинную плоскость. Точка пересечения перпендикуляра и картинной плоскости называется принципиальной точкой p. С этой точкой свяжем систему отсчета (x,y).

Рисунок 12 - Модель камеры

Системы координат (X,Y,Z) и (x,y) связаны нелинейным преобразованием (формулы (9) и (10)).

 (9)

 (10)

Свяжем систему координат (u,v) с левым верхним углом. Отсчет в этой системе происходит в пикселях (рисунок 13). Принципиальная точка имеет координаты p=(0,0) в системе (x,y); координаты (0,0,Z) в системе (X,Y,Z) и координаты (Cx,Cy) в системе (u,v).

Рисунок 13 - Система координат (u, v)

Системы координат (u,v) и (x,y) связаны аффинными преобразованиями (формулы (11) и (12)).

,

где pix - длина пикселя.

Подставляя формулы (9) и (10) в формулы (11) и (12), получаем выражения, связывающие системы (u,v) и (X,Y,Z).

, (13)

, (14)

где f = 3,85 мм;= 0,0232 мм;= 300 пикселей;= 255 пикселей.

Параметры Cx и Cy были определены в ходе калибровки камеры с разрешением 640*480.

Создание алгоритма для определения ориентации по ключевым точкам QR кода

Нашей задачей является определение углов поворота QR кода вокруг осей x и y. Информацию об этих углах мы получим, сравнивая изображение повернутого QR кода, центр которого расположен на расстоянии Z` от камеры, с QR кодом, находящемся на таком же расстоянии, но в картинной плоскости, то есть с нулевыми углами поворота. В данной работе мы используем факт, что координаты точек QR, лежащих на осях ox и oy, изменяются под влиянием только одного поворота.

Сначала нам нужно узнать координаты центра p` =(CCx,CCy) QR кода на изображении в системе (u,v) (рисунок 14) . Определить их примерно можно по формулам (14) и (15).

Рисунок 14 - Картинная плоскость камеры

 15)

 (16)

где LeftUp, RightUp, LeftDown, RightDown - ключевые точки изображения QR кода.

Для начала рассмотрим случай поворота QR кода только вокруг одной оси x (рисунок 15).

Рисунок 15 - Поворот QR кода вокруг x`

Пусть длина стороны квадрата равна A, тогда в системе (x`,y`) вершины квадрата, лежащего в картинной плоскости имеют координаты (-A/2,-A/2); (A/2,-A/2); (A/2,A/2); (-A/2,A/2). Предположим, QR код повернут вокруг x` на угол a, тогда координаты точек этого квадрата, лежащих на оси ох` не изменятся, а координаты точек Vв и Vн, лежащих на оси oy`, уменьшатся. Используя рисунок, на котором представлен вид сбоку, можно выразить координату точки Vн в системе (X,Y,Z) через a (рисунок 16).

Рисунок 16 - Плоскость QR кода, вид сбоку

 (17)

После поворота по часовой стрелке вокруг оси ox` точка Vн стала находиться ближе к камере, а значит, ее координата Z уменьшилась на sin(a)*A/2.

Используя формулу (13), выразим координату точки Vн в системе (u,v) через a и получим формулу (18):

 , (18)

где Z` - координата центра квадрата.

Значение Vн получаем из анализа изображения. Зная Z` мы находим угол поворота a. Аналогичным образом определим угол поворота b вокруг оси oy.

При повороте вокруг оси oy координаты точек кода, лежащих на оси oy не изменятся, а по изменению координат точек, лежащих на оси ox, можно судить об угле b (рисунок 17).

Рисунок 17 - Поворот вокруг обеих осей x и y

При повороте против часовой стрелки вокруг oy координата Z точки Uп увеличится и станет равна Z`+A/2*sin(b), а координата X уменьшится и станет равна cos(b)*A/2.

 (19)

Используя формулу (19) и зная Z`, находим искомый угол b.

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

3. Программное обеспечение для распознавания QR кода и определения его ориентации

3.1 Описание программы

Программа представляет собой приложение для распознавания кода и определения углов поворота плоскости, в которой он лежит, относительно камеры. Для распознавания QR кода нами была использована библиотека для работы с компьютерным зрением OpenCV. С помощью нее кадры, поступающие с камеры, обрабатываются и проверяются на наличие QR кода. Работу части программы, отвечающей за детектирование, описывает блок схема, изображенная на рисунке 18.

Рисунок 18 - Блок-схема алгоритма обнаружения QR кода

Построенный на первом этапе массив нулей и единиц далее расшифровывается на основе алгоритма, приведенного в спецификации [5]. Блок-схема, изображенная на рисунке 19 графически отображает шаги, которые необходимо пройти для расшифровки QR кода.

Рисунок 19 - Блок-схема алгоритма расшифровки QR кода

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

3.2 Тестирование программы

При запуске программы начинается видеозахват с камеры. Все снимки делаются автоматически (рисунок 20).

Рисунок 20 - Снимок QR кода

На камеру поступает картинка каждые 33 мc, автоматически обрабатывается и сканируется на наличие мишеней (рисунок 22).

Рисунок 21 - Снимок после порогового преобразования

Рисунок 22 - Снимок с нарисованными на нем найденными мишенями

Как только поступает изображение, имеющее 3 мишени, запускается код распознавания: находятся вершины QR кода, строится сетка и далее массив нулей и единиц, который выводится в консоль и записывается в файл (рисунок 23).

Рисунок 23 - Снимок с нарисованной на нем построенной сеткой

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

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

Рисунок 24 - Вывод результатов в консоль

4. Применение разработанного программного обеспечения

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

) возможностью выделения существенной информации из множества независимых признаков;

) способностью к обучению на примерах и обобщению этих знаний с целью их применения в новых ситуациях;

) возможностью восстановления событий по неполной информации;

) способностью определять цели и формулировать планы для достижения этих целей.

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

Заключение

В ходе выполнения работы был разработан и программно реализован на языке C++ и с помощью библиотеки OpenCV алгоритм обнаружения QR кода. На основе спецификации ISO/IEC 18004 Information technology - Automatic identification and data capture techniques - Bar code symbology - QR Code изучен и программно реализован алгоритм расшифровки QR кода. Также был разработан алгоритм определения углов смещения QR кода на основе данных о координатах ключевых точек QR кода, полученных при его распознавании. Значения определенных углов являются приблизительными, возможны отклонения от истинных значений в размере 20%, что установлено экспериментальным путем. Разработанное программное обеспечение может быть использовано для позиционирования манипуляторов роботов в случаях, когда не требуется высокая точность.

Список использованных источников

1. Детектирование QR Code с помощью средств OpenCV [Электронный ресурс] - Режим доступа: http://recog.ru/blog/barcode/3.html. - Загл. с экрана. (Дата обращения: 20.05.2013).

. Gary Bradski, Adrian Kaehler. Learning OpenCV.: издательство O'Reilly, 2008. -577с.

. ISO/IEC 18004 Information technology - Automatic identification and data capture techniques - Bar code symbology - QR Code. - 122c.

4. Фрайден Дж. Современные датчики. Справочник. - М.: издательский центр Техносфера, 2006 - 801 с.

. Назаров А.С. Фотограмметрия: учеб. пособие для студентов вузов. - Мн.: ТетраСистемс, 2006. - 368 с.

.        Форсайт Дэвид А. Компьютерное зрение. Современный подход. - М.: издательский дом "Вильямс", 2004.- 928с.