Распознавание маяков типа "Q-Code" — различия между версиями

Материал из roboforum.ru Wiki
Перейти к: навигация, поиск
(Внешний вид визуального маяка)
 
(не показано 37 промежуточных версий этого же участника)
Строка 1: Строка 1:
== Внешний вид визуального маяка ==
+
{{InfoBlock|Реализацию библиотеки для работы с такими маяками можно найти на странице [[Библиотека cvQCodeBeacons]]|        Реализация на С++}}
  
[[Изображение:QCodeBeacon.jpg|thumb|200px|Внешний вид визуального маяка "Q-Code",<br>размещенного на стене комнаты.|right]]
+
== Внешний вид визуального маяка и кодирование информации в нём ==
 +
 
 +
[[Изображение:QCodeBeacon.jpg|thumb|170px|Визуальный маяк "Q-Code",<br>размещенный на стене комнаты.|right]]
 +
 
 +
Структура маяка - черно-белое клетчатое поле размерами 9х9 клеток, в котором внешний квадрат клеток белый, вложенный в него квадрат клеток черный, а в оставшейся середине 5х5 клеток закодированы угловыми клетками правильная ориентация маяка (только одна из них, "маркер поворота", черная) и еще две клетки рядом с "маркером поворота" - одна из них черная, они указывают на то, что это не однократное отражение маяка (двухкратное отражение отличить невозможно).
 +
 
 +
 
 +
Из оставшихся 25-4-2=19 клеток еще 4 мы будем использовать под контрольную сумму, чтобы гарантировать качество распознавания. Итого под информацию у нас остается 15 бит, то есть мы можем изготовить 32768 различных таких маяков. Этого достаточно, чтобы обклеить ими изнутри крупное здание, и скорее всего не одно.
 +
 
 +
Здесь можно взять шаблоны для маяков, подготовленные в формате Microsoft Word:
 +
* [[http://www.roboforum.ru/download/file.php?id=3749 Скачать шаблон для формата А4]];
 +
* [[http://www.roboforum.ru/download/file.php?id=3748 Скачать шаблон для формата А5]];
  
 
== Кодирование информации в визуальном маяке ==
 
== Кодирование информации в визуальном маяке ==
 +
 +
[[Изображение:QCodeBeaconBits.jpg|thumb|200px|Размещение битов информации<br>и контрольной суммы.|right]]
 +
 +
Корректной принимается ориентация маяка, при которой "маркер поворота" находится в левом нижнем углу, а прилегающая к нему черная клетка справа от него.
 +
 +
 +
В этом случае биты полезной информации (номера маяка) размещается в свободных ячейках слева направо, сверху вниз. В оставшихся четырех битах находится контрольная сумма. Расположение битов информации и контрольной суммы на маяке также приведено на рисунке справа. Биты информации обозначаются I-1 ... I-15, биты контрольной суммы S-1 ... S-4.
 +
 +
'''Внимание!!!''' Младший бит номера маяка располагается в бите I-15, старший - в бите I-1, поэтому маяк с номером 1 будет иметь биты I-1 ... I-14 равными нулю и только последний I-15 равный единице.
 +
 +
 +
Информация с маяка проверяется на корректность по следующему алгоритму:
 +
# К 15 битам информации справа приписать 4 бита контрольной суммы и еще один бит равный 0, получится 20 бит данных;
 +
# Эти 20 бит данных разбиваются на 5 групп по 4 бита;
 +
# Получившиеся группы по 4 бита накладываются друг на друга по XOR;
 +
# Если в результате этого наложения получилось 1101, тогда информация считается корректной, иначе нет.
 +
 +
Порядок рассчета битов контрольной суммы вытекает из уравлений проверки контрольной суммы:
 +
 +
* I-1 XOR I-5 XOR I-9  XOR I-13 XOR S-2 = 1
 +
* I-2 XOR I-6 XOR I-10 XOR I-14 XOR S-3 = 1
 +
* I-3 XOR I-7 XOR I-11 XOR I-15 XOR S-4 = 0
 +
* I-4 XOR I-8 XOR I-12 XOR S-1  XOR 0  = 1
 +
 +
Отсюда следует, что:
 +
 +
* S-1 = I-4 XOR I-8 XOR I-12 XOR 0    XOR 1
 +
* S-2 = I-1 XOR I-5 XOR I-9  XOR I-13 XOR 1
 +
* S-3 = I-2 XOR I-6 XOR I-10 XOR I-14 XOR 1
 +
* S-4 = I-3 XOR I-7 XOR I-11 XOR I-15 XOR 0
  
 
== Распознавание визуального маяка на экране и чтение информации с него ==
 
== Распознавание визуального маяка на экране и чтение информации с него ==
 +
 +
[[Изображение:QCodeBeaconBorder.jpg|thumb|150px|Красным выделен<br>контур, который ищем.|right]]
 +
 +
Распознавание маяков производится по следующему алгоритму:
 +
 +
# Готовим изображение, удаляя с него помехи:
 +
# Строим несколько сечений изображения (сечение - превращение изображения в черно-белое по установленной границе яркости, всё что светлее границы становится белым, остальное черным) и для каждого из сечений:
 +
## Находим на изображении все контуры;
 +
## Аппроксимируем найденные контуры ломаными;
 +
## Среди ломаных находим похожие на квадраты (надеясь, что он является что он является внутренней границей внешнего контура квадратиков визуального маяка);
 +
## Каждый такой похожий на квадрат контур проверяем на то, что он является "Q-Code"-маяком, для этого пытаемся удостоверится в целостности данных им представленных, просто делим его внутренность на квадратики 7х7, и проверяем корректность представленных там битов информации и контрольной суммы;
  
 
== Определение расстояния до визуального маяка ==
 
== Определение расстояния до визуального маяка ==
 +
 +
Если мы готовили маяки известного нам размера, тогда мы можем определять приблизительное расстояние до маяка расположенного к нам под прямым углом в центре кадра просто по стороне квадрата, который был найден при распознавании. То есть если A - сторона этого квадрата, тогда расстояние до маяка - R0=K/A, где K - константа, которую можно определить опытным путем.
 +
 +
В случае, если маяк находится не под прямым углом к камере, тогда необходимо рассчитать его размер по контуру (позже выложу сюда формулы).
 +
 +
Кроме того, если маяк расположен не в центре кадра, необходимо рассчитанное расстояние пересчитать по формуле R=sqrt(R0*R0+D0*D0), где D0 - рассчетное расстояние смещения маяка относительно точки находящейся на расстоянии R0 от камеры отложенном на векторе направления в котором повернута камера.
 +
 +
== Реализация алгоритма ==
 +
[[Библиотека cvQCodeBeacons]]

Текущая версия на 07:04, 16 января 2008

Информация
        Реализация на С++

Реализацию библиотеки для работы с такими маяками можно найти на странице Библиотека cvQCodeBeacons



Внешний вид визуального маяка и кодирование информации в нём

Визуальный маяк "Q-Code",
размещенный на стене комнаты.

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


Из оставшихся 25-4-2=19 клеток еще 4 мы будем использовать под контрольную сумму, чтобы гарантировать качество распознавания. Итого под информацию у нас остается 15 бит, то есть мы можем изготовить 32768 различных таких маяков. Этого достаточно, чтобы обклеить ими изнутри крупное здание, и скорее всего не одно.

Здесь можно взять шаблоны для маяков, подготовленные в формате Microsoft Word:

Кодирование информации в визуальном маяке

Размещение битов информации
и контрольной суммы.

Корректной принимается ориентация маяка, при которой "маркер поворота" находится в левом нижнем углу, а прилегающая к нему черная клетка справа от него.


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

Внимание!!! Младший бит номера маяка располагается в бите I-15, старший - в бите I-1, поэтому маяк с номером 1 будет иметь биты I-1 ... I-14 равными нулю и только последний I-15 равный единице.


Информация с маяка проверяется на корректность по следующему алгоритму:

  1. К 15 битам информации справа приписать 4 бита контрольной суммы и еще один бит равный 0, получится 20 бит данных;
  2. Эти 20 бит данных разбиваются на 5 групп по 4 бита;
  3. Получившиеся группы по 4 бита накладываются друг на друга по XOR;
  4. Если в результате этого наложения получилось 1101, тогда информация считается корректной, иначе нет.

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

  • I-1 XOR I-5 XOR I-9 XOR I-13 XOR S-2 = 1
  • I-2 XOR I-6 XOR I-10 XOR I-14 XOR S-3 = 1
  • I-3 XOR I-7 XOR I-11 XOR I-15 XOR S-4 = 0
  • I-4 XOR I-8 XOR I-12 XOR S-1 XOR 0 = 1

Отсюда следует, что:

  • S-1 = I-4 XOR I-8 XOR I-12 XOR 0 XOR 1
  • S-2 = I-1 XOR I-5 XOR I-9 XOR I-13 XOR 1
  • S-3 = I-2 XOR I-6 XOR I-10 XOR I-14 XOR 1
  • S-4 = I-3 XOR I-7 XOR I-11 XOR I-15 XOR 0

Распознавание визуального маяка на экране и чтение информации с него

Красным выделен
контур, который ищем.

Распознавание маяков производится по следующему алгоритму:

  1. Готовим изображение, удаляя с него помехи:
  2. Строим несколько сечений изображения (сечение - превращение изображения в черно-белое по установленной границе яркости, всё что светлее границы становится белым, остальное черным) и для каждого из сечений:
    1. Находим на изображении все контуры;
    2. Аппроксимируем найденные контуры ломаными;
    3. Среди ломаных находим похожие на квадраты (надеясь, что он является что он является внутренней границей внешнего контура квадратиков визуального маяка);
    4. Каждый такой похожий на квадрат контур проверяем на то, что он является "Q-Code"-маяком, для этого пытаемся удостоверится в целостности данных им представленных, просто делим его внутренность на квадратики 7х7, и проверяем корректность представленных там битов информации и контрольной суммы;

Определение расстояния до визуального маяка

Если мы готовили маяки известного нам размера, тогда мы можем определять приблизительное расстояние до маяка расположенного к нам под прямым углом в центре кадра просто по стороне квадрата, который был найден при распознавании. То есть если A - сторона этого квадрата, тогда расстояние до маяка - R0=K/A, где K - константа, которую можно определить опытным путем.

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

Кроме того, если маяк расположен не в центре кадра, необходимо рассчитанное расстояние пересчитать по формуле R=sqrt(R0*R0+D0*D0), где D0 - рассчетное расстояние смещения маяка относительно точки находящейся на расстоянии R0 от камеры отложенном на векторе направления в котором повернута камера.

Реализация алгоритма

Библиотека cvQCodeBeacons