Pull to refresh

Оригами и расширенная реальность (продолжение)

Algorithms *
У всего, что написано ниже есть маленькая предыстория. Здесь мы решили сосредоточится на технических подробностях. Итак, перед нашим пытливым умом поставили следующую задачу:
  • есть лист бумаги, который необходимо сложить определенным образом;
  • для подсказок складывающему желательно воспользоваться технологией расширенной реальности и накладывать информацию о подсказках поверх получаемых изображений.
Было решено в качестве маркеров на листе расставить специальные баркоды и модулю отрисовки возвращать информацию об их содержании и положении на изображении, в то время как в самом модуле будет хранится информация о том, когда и как этой информацией воспользоваться.

Одним из неназванных, но предполагаемых, условий было использование «своего» модуля распознания и «своих» баркодов (нет, не обязательно изобретать велосипед, можно было собрать его из уже имеющихся деталей — главное, чтобы он в итоге поехал). Разработанные баркоды основываются на шифровании алгоритмом Рида-Соломона и им, пожалуй, стоит посвятить отдельную статью.

Сейчас же поведем рассказ о модуле распознания этих таинственных знаков.

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

 

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

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

 

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

максимальная разность из попарно окружающих значений

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

 

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

 

Теперь изображение содержит только черные и белые пиксели, поэтому можно приступать к поиску объектов.

Алгоритмов выделения границ очень много. Мы же воспользуемся одним из самых простых — «алгоритмом последовательного сканирования». Построчно рассмотрим изображение, пропуская пиксели фона, но объединяя идущие подряд «значимые» пиксели (для каждого пикселя в момент анализа важны левый, левый-верхний, верхний и правый-верхний пиксели). После переиндексации, объединения границ и прочих необходимых манипуляций, о которых подробнее можно почитать в соответствующих статьях, мы получим наконец список связанных областей. Осталась самая малость — выбрать из них те, что являются баркодами.

Для этого проведем несколько проверок (работать будем снова с изображением в оттенках серого):
  1. Отбросим те из найденных объектов, которые меньше указанного нами размера: т. к. баркоды у нас содержат 8×8 клеток с информацией, то примем минимальный размер изображения с ними, к примеру, 16 на 16 пикселей.
  2. Проанализируем границы каждого из объектов. Заменив их набором отрезков оставим только те, границы которых состоят из 4 отрезков (баркоды квадратные, однако за счет того, что лист не перпендикулярен камере, они могут искажаться, но 4 стороны сохранят все равно)
  3. Одной из особенностей наших баркодов является непрерывная черная граница, поэтому оставляем только те объекты, внутренняя граница которых темнее внешней.
  4. Восстановим квадратную форму оставшихся объектов. Для этого строим матрицу отображения исходного (искаженного) изображения на квадратную картинку, а конфликты (недостаток или избыток пикселей) разрешаем интерполяцией данных. Для изображений из примера получаем такие снимки баркодов:

  5. К полученным снимкам снова применим фильтр Оцу:

  6. Бинаризуем полученные изображения и преобразуем их в числовую матрицу. Баркоды состоят из 64 клеток (8×8), поэтому делим снимки на 64 квадратные области. Для каждой клетки вычисляем ее «точное» значение: черная она или белая (если «точности» оказывается недостаточно, например, 40% пикселей одного цвета и 60% — другого, то снимок признается непригодным для дальнейшего анализа). По результатам строим матрицу 8×8, заполненную 1 и 0.
  7. Анализируем полученные матрицы: ищем угловые маркеры, поворачиваем матрицу в соответствии с нашими понятиями о верхе и низе (снимки баркодов, приведеные выше уже повернуты установленным образом), извлекаем из нее полезную информацию, декодируем (информация закодирована с помощью алгоритма Рида-Соломона). На этом этапе, как уже можно было догадаться, также отсеиваются области, которые прошли все прошлые проверки, на баркодами не являются. Зато полученную информацию уже можно использовать.

______________________
Текст подготовлен в Хабра Редакторе от © SoftCoder.ru
Tags:
Hubs:
Total votes 41: ↑40 and ↓1 +39
Views 1.2K
Comments Comments 13