У всего, что написано ниже есть маленькая предыстория. Здесь мы решили сосредоточится на технических подробностях. Итак, перед нашим пытливым умом поставили следующую задачу:
Одним из неназванных, но предполагаемых, условий было использование «своего» модуля распознания и «своих» баркодов (нет, не обязательно изобретать велосипед, можно было собрать его из уже имеющихся деталей — главное, чтобы он в итоге поехал). Разработанные баркоды основываются на шифровании алгоритмом Рида-Соломона и им, пожалуй, стоит посвятить отдельную статью.
Сейчас же поведем рассказ о модуле распознания этих таинственных знаков.
Самый первый шаг — получение входных данных. Мы можем получать их из нескольких источников: статическое изображение, видеозапись или видео с веб-камеры. В любом случае работа расширенной реальности сводится к обработке неподвижного изображения (в случае с видео это будет кадр; также добавляется возможность учета данных, собранных с прошлых кадров, введение «инерционности» данных в случае нестабильной картинки и т. д.). Без ограничения общности рассмотрим работу со статическими картинками (сиречь-фотографиями):
Фотографии различаются по яркости (это будет важно на одном из этапов), но объединяет их одно — лист, с расположенными на нем баркодами. Баркоды разрабатывались специально и имеют ряд особенностей, которые так же учтены в алгоритме распознания (речь о них пойдет далее).
Прежде всего необходимо «обесцветить» изображения. Цвет для нас не несет никакой информации, поэтому уберем эту лишнюю информацию:
На полученных изображениях найдем границы объектов. Для этого для каждого пикселя выберем максимальную разность из попарно окружающих его значений:
В результате на «однотонных» участках значение будет близко к нулю (если на изображении присутствует шум, то значение будет незначительно от нуля отличаться), но как только в рассматриваемую область попадет пиксель, контрастирующий с остальными, значение резко увеличится. На полученных после этой операции изображениях хорошо видно, какая информация становится для нас малозначимой (не забываем, что баркоды у нас черно-белые, нанесенные на белую бумагу, а значит они всегда будут иметь высокую контрастность):
На полученных изображениях, казалось бы, уже можно искать границы объектов. Но не стоит забывать, что границы здесь состоят не из одного цвета, а содержат несколько оттенков серого. Поэтому сперва проведем пороговую бинаризацию. Помните, яркость изображений была почему-то для нас важна? Так вот, важна она именно на этом этапе. Если мы зададим строго порог бинаризации, то фильтр сработает неправильно (не так, как нам хотелось бы) на очень светлых и очень темных фотографиях. Поэтому будем использовать алгоритм Оцу (Otsu Tresholding), который определяет порог бинаризации в зависимости от самого изображения. Поэтому теперь важные для нас границы не сотрутся:
Теперь изображение содержит только черные и белые пиксели, поэтому можно приступать к поиску объектов.
Алгоритмов выделения границ очень много. Мы же воспользуемся одним из самых простых — «алгоритмом последовательного сканирования». Построчно рассмотрим изображение, пропуская пиксели фона, но объединяя идущие подряд «значимые» пиксели (для каждого пикселя в момент анализа важны левый, левый-верхний, верхний и правый-верхний пиксели). После переиндексации, объединения границ и прочих необходимых манипуляций, о которых подробнее можно почитать в соответствующих статьях, мы получим наконец список связанных областей. Осталась самая малость — выбрать из них те, что являются баркодами.
Для этого проведем несколько проверок (работать будем снова с изображением в оттенках серого):
______________________
- есть лист бумаги, который необходимо сложить определенным образом;
- для подсказок складывающему желательно воспользоваться технологией расширенной реальности и накладывать информацию о подсказках поверх получаемых изображений.
Одним из неназванных, но предполагаемых, условий было использование «своего» модуля распознания и «своих» баркодов (нет, не обязательно изобретать велосипед, можно было собрать его из уже имеющихся деталей — главное, чтобы он в итоге поехал). Разработанные баркоды основываются на шифровании алгоритмом Рида-Соломона и им, пожалуй, стоит посвятить отдельную статью.
Сейчас же поведем рассказ о модуле распознания этих таинственных знаков.
Самый первый шаг — получение входных данных. Мы можем получать их из нескольких источников: статическое изображение, видеозапись или видео с веб-камеры. В любом случае работа расширенной реальности сводится к обработке неподвижного изображения (в случае с видео это будет кадр; также добавляется возможность учета данных, собранных с прошлых кадров, введение «инерционности» данных в случае нестабильной картинки и т. д.). Без ограничения общности рассмотрим работу со статическими картинками (сиречь-фотографиями):
Фотографии различаются по яркости (это будет важно на одном из этапов), но объединяет их одно — лист, с расположенными на нем баркодами. Баркоды разрабатывались специально и имеют ряд особенностей, которые так же учтены в алгоритме распознания (речь о них пойдет далее).
Прежде всего необходимо «обесцветить» изображения. Цвет для нас не несет никакой информации, поэтому уберем эту лишнюю информацию:
На полученных изображениях найдем границы объектов. Для этого для каждого пикселя выберем максимальную разность из попарно окружающих его значений:
В результате на «однотонных» участках значение будет близко к нулю (если на изображении присутствует шум, то значение будет незначительно от нуля отличаться), но как только в рассматриваемую область попадет пиксель, контрастирующий с остальными, значение резко увеличится. На полученных после этой операции изображениях хорошо видно, какая информация становится для нас малозначимой (не забываем, что баркоды у нас черно-белые, нанесенные на белую бумагу, а значит они всегда будут иметь высокую контрастность):
На полученных изображениях, казалось бы, уже можно искать границы объектов. Но не стоит забывать, что границы здесь состоят не из одного цвета, а содержат несколько оттенков серого. Поэтому сперва проведем пороговую бинаризацию. Помните, яркость изображений была почему-то для нас важна? Так вот, важна она именно на этом этапе. Если мы зададим строго порог бинаризации, то фильтр сработает неправильно (не так, как нам хотелось бы) на очень светлых и очень темных фотографиях. Поэтому будем использовать алгоритм Оцу (Otsu Tresholding), который определяет порог бинаризации в зависимости от самого изображения. Поэтому теперь важные для нас границы не сотрутся:
Теперь изображение содержит только черные и белые пиксели, поэтому можно приступать к поиску объектов.
Алгоритмов выделения границ очень много. Мы же воспользуемся одним из самых простых — «алгоритмом последовательного сканирования». Построчно рассмотрим изображение, пропуская пиксели фона, но объединяя идущие подряд «значимые» пиксели (для каждого пикселя в момент анализа важны левый, левый-верхний, верхний и правый-верхний пиксели). После переиндексации, объединения границ и прочих необходимых манипуляций, о которых подробнее можно почитать в соответствующих статьях, мы получим наконец список связанных областей. Осталась самая малость — выбрать из них те, что являются баркодами.
Для этого проведем несколько проверок (работать будем снова с изображением в оттенках серого):
- Отбросим те из найденных объектов, которые меньше указанного нами размера: т. к. баркоды у нас содержат 8×8 клеток с информацией, то примем минимальный размер изображения с ними, к примеру, 16 на 16 пикселей.
- Проанализируем границы каждого из объектов. Заменив их набором отрезков оставим только те, границы которых состоят из 4 отрезков (баркоды квадратные, однако за счет того, что лист не перпендикулярен камере, они могут искажаться, но 4 стороны сохранят все равно)
- Одной из особенностей наших баркодов является непрерывная черная граница, поэтому оставляем только те объекты, внутренняя граница которых темнее внешней.
- Восстановим квадратную форму оставшихся объектов. Для этого строим матрицу отображения исходного (искаженного) изображения на квадратную картинку, а конфликты (недостаток или избыток пикселей) разрешаем интерполяцией данных. Для изображений из примера получаем такие снимки баркодов:
- К полученным снимкам снова применим фильтр Оцу:
- Бинаризуем полученные изображения и преобразуем их в числовую матрицу. Баркоды состоят из 64 клеток (8×8), поэтому делим снимки на 64 квадратные области. Для каждой клетки вычисляем ее «точное» значение: черная она или белая (если «точности» оказывается недостаточно, например, 40% пикселей одного цвета и 60% — другого, то снимок признается непригодным для дальнейшего анализа). По результатам строим матрицу 8×8, заполненную 1 и 0.
- Анализируем полученные матрицы: ищем угловые маркеры, поворачиваем матрицу в соответствии с нашими понятиями о верхе и низе (снимки баркодов, приведеные выше уже повернуты установленным образом), извлекаем из нее полезную информацию, декодируем (информация закодирована с помощью алгоритма Рида-Соломона). На этом этапе, как уже можно было догадаться, также отсеиваются области, которые прошли все прошлые проверки, на баркодами не являются. Зато полученную информацию уже можно использовать.
______________________