Optimization of information signs recognition methods for the problem of indoor navigation

Lebedev Leonid Ivanovich PhD in Physics and Mathematics Leading Researcher, Lobachevsky National Research Nizhny Novgorod State University 603950, Russia, Nizhegorodskaya oblast', g. Nizhnii Novgorod, pr. Gagarina, 23 lebedev@pmk.unn.ru

Osipov Mikhail Pavlovich PhD in Technical Science Leading Researcher, Lobachevsky National Research Nizhny Novgorod State University 603950, Russia, Nizhegorodskaya oblast', g. Nizhnii Novgorod, pr. Gagarina, 23 virtulab@mail.ru

Введение

Внутренняя структура современных общественных зданий представляет собой сложный комплекс из этажей, коридоров и комнат, в которых довольно сложно ориентироваться. В последнее время для решения проблемы навигации внутри зданий было предложено множество технологических решений, основанных на использовании сетей передачи данных (Bluetooth, Wi-Fi, UWB, FM-радиоволны), микромеханических инерциальных датчиков (акселерометры, датчики угловой скорости), магнитного поля земли, QR-кодов, RFID-меток и т.п. ^{[1, p. 9-10]}. Однако все они имеют существенные ограничения по точности, стоимости и сложности реализации.

Традиционно для навигации внутри помещений использовалась так называемая визуальная навигация, представляющая собой систему именных табличек и указателей, размещенных на стенах и дверях зданий и являющиеся путеводителем по ним. Для автоматизации этого процесса, а также снижения информационной нагрузки на человека могут использоваться методы машинного зрения ^[2-4] для распознавания информационных знаков помещения и локализации пользователя. Но частота появления информационных знаков помещения и их не уникальность не позволяют определять местоположение пользователя в любой момент времени. Поэтому в работе ^[5] описывается комбинированный подход, где результаты распознавания информационных знаков помещения используются в качестве уточнения (корректировки) положения пользователя, вычисленного по результатам микромеханических инерциальных датчиков ^[6].

Постановка задачи

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

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

Методы и алгоритмы оптимизации

Окантовка информационных знаков представляет собой область однородного цвета. Поэтому для ускорения поиска информационных знаков помещения на изображении необходимо определить области однородного цвета. Для решения этой задачи наиболее подходит представление изображения в цветовой модели HSV. Процесс выделения областей однородных по цвету происходит следующим образом. Кадр анализируется построчно. В каждой строке происходит формирование групп пикселей попавших в заданный диапазон цвета. Расстояние между соседними пикселями в сформированных группах не должно превышать заданного порога. Таким образом, формируются отрезки пикселей заданного цвета. Далее происходит включение этих отрезков в близлежащие области распознавания заданного цвета. Расстояние между границами отрезка и областей распознавания данного цвета не должно превышать заданного порога. Если таких областей нет, отрезок формирует новую область распознавания заданного цвета. Области распознавания, не включившие отрезки текущей строки, считаются сформированными и для следующих строк не рассматриваются. На заключительном этапе происходит объединение областей распознавания, имеющих примыкание, включение или пересечение друг с другом. Данный алгоритм позволяет за один проход выделить однородные по цвету области для любого заданного количества цветов. Трудоемкость такого алгоритма O(N).

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

Рис.1 Сегментация изображения кадра по наборам заданных цветов

Выделение в одном кадре нескольких областей однородного цвета позволяет запустить задачи анализа и распознавания в каждой области в отдельном потоке параллельно и независимо друг от друга. Тем самым распараллелить весь процесс на многопроцессорных архитектурах ^{[7, с. 98]}. Для реализации предложенных алгоритмов в задаче распознавания информационных знаков в кадре из видеопотока разработано программное обеспечение, реализованное для различных платформ (в том числе на мобильных устройствах). На рисунке 1 приведен снимок экрана программы, выделившей на кадре из видеопотока шесть областей определенного цвета, представляющих различные информационные знаки. На рисунке 2 изображены полученные области, содержащие соответствующие информационные знаки и построенная контурная модель для этих фрагментов. Для решения задачи построения контурной модели, на основе которой будет осуществляться распознавание объектов изображения, полученное разделение всего кадра на области с малым количеством цветов позволяет точнее найти порог бинаризации и, как следствие, получить более качественную контурную модель описания фрагмента. В перспективе это приводит к более качественному распознаванию объектов.

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

а)

б)

в)

г)

Рис.2 Изображение выделенной области и контурная модель объектов распознавания

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

а) изображение информационного знака б) эталонное изображение

Рис. 3 Изображения информационного знака и его эталонный образ

Решение задачи распознавания объектов изображений выделенных областей реализовано на базе корреляционно-экстремального контурного метода с использованием оценки сходства, инвариантной к аффинным преобразованиям ^{[8, с. 84-89]}. В работе ^{[9, с. 35-42]} было доказано, что любое аффинное преобразование может быть представлено совокупностью операций, включающих проецирование контура на плоскость, полученную последовательным вращением плоскости XOY вокруг осей OX и OY на β и γ соответственно, ортогональное преобразование, и масштабирование проецированного контура. Для обеспечения инвариантности относительно аффинных преобразований вначале формируются описания проекций контура по формулам:

(1)

,

а затем решается оптимизационная задача вида:

(2)

где оценка сходства (близости) ε_m(β,γ) для заданных значений углов β и γ находится с помощью КЭКМ в соответствии с формулами:

(3)

где Dw^e, Dw(β,γ) - дисперсии контуров эталона и фрагмента изображения соответственно, а R(β,γ) - величина, вычисленная по значениям смешанных корреляционных моментов:

(4)

.

.

Решение оптимизационной задачи (2) осуществляется с использованием метода сеток. Определитель матрицы проецированного преобразования (1) равен , и отличается от определителя аффинного преобразования на величину . Поэтому, чтобы аффинное преобразование было преобразованием первого рода, необходимо выполнение условия . Отсюда, с учетом k_m>0, области изменения параметров β и γ изначально задаются в пределах (-90, 90). Анализ выражения из формулы преобразования проецирования (1) показывает для реализации значений z(β,γ) достаточно области . Следует иметь ввиду, что искажения формы контуров при погрешностях в 2.5° для параметров β и γ не критичны и допустимы по величине ошибок, вносимых в значения оценок близости. Поэтому в методе сеток размер ячейки был выбран равным 5. Отсюда, для нахождения число итераций будет равно 18×35=630. То есть, сложность метода распознавания на базе оценки близости, инвариантной относительно аффинных преобразований приближенно в 630 раз выше, чем при распознавании на основе базовой оценки близости (3). Для уменьшения времени распознавания был реализован алгоритм, основанный на распараллеливании потоков данных по параметрам β и γ. Так как для каждой итерации значение вычисляется независимо от других, то количество потоков можно было бы сформировать по числу заданных ячеек. Однако, учитывая возможности мобильных устройств распараллеливание было реализовано только по параметру γ (то есть предусматривает организацию 18 потоков).

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

(5)

(6)

.

.

.

(7)

Это позволяет реализовать следующую технологию распознавания информационных знаков на основе новой структуры описания эталонного изображения. Суть предлагаемой технологии заключается в уменьшении области D⁰(β,γ) изменения параметров β и γ, также целенаправленном отборе для распознавания объектов информационного знака соответствующих по местоположению данному эталону. Для реализации этих положений в описании эталонного изображения выделяются базовые эталоны, которым присваивается метка приоритета. Базовые эталоны должны обладать свойством эксклюзивности для данного информационного знака. Метрические описания всех эталонов должны быть заданы в системе координат изображения, на базе которого они формируются. Кроме того, обязательно задается габаритное описание эталона. Тогда быстродействие алгоритма распознавания объектов на изображении информационного знака будет определяться следующей последовательностью операций.

Шаг 1. Выбирается текущий базовый эталон E^b,j.

Шаг 2. Для каждого преобразования с параметрами из области D⁰(β,γ) формируется множество проецированных описаний эталонов E^b,j(β,γ) в соответствии с формулой (5).

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

(8)

а также средняя точка объекта и формируется область изменения параметров .

Шаг 4. Выполнять Шаг 3 до исчерпания объектов.

Шаг 5. Если не нашлось объекта сходного с базовым эталоном, то переходим к выполнению пункта Шаг 1 до их исчерпания, иначе переходим к выполнению следующего пункта.

Шаг 6. Если не сформировалось ни одной области , процедура распознавания завершает свою работу с сообщением «Информационный знак не опознан».

Шаг 7. Для каждого следующего эталона определяется местоположение объекта на изображении информационого знака по формулам:

(9)

где матрица определяется по формулам:

(10)

.

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

Шаг 8. На основании анализа меток эталонов решается вопрос о соответствии распознаваемого информационного знака эталонному изображению.

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

На рисунке 4 показаны результаты восстановления объектов боковой фронтальной перспективы с использование параметров распознавания на базе эталонов буквы «щ» и рукописной буквы «Л» ^[10]. Обратное преобразование используется здесь для большей наглядности.

а) восстановление на базе эталона «щ» б) восстановление на базе эталона «Л»

Рис.4 Фрагменты изображений центральной фронтальной перспективы и восстановленной боковой фронтальной перспективы по различным эталонам

Как следует из анализа рисунка 4, если цифра «2» будет заявлена как эталон, то область поиска объектов для него на изображении боковой фронтальной перспективы следует определять по параметрам распознанной рукописной буквы «Л», а не эталона буквы «щ», даже в случае если он является базовым. Отсюда также можно сделать вывод, что большие по габаритам контуры использовать в качестве эталонов нежелательно, так как область поиска объектов на распознаваемом изображении, локализованная полученным аффинным преобразованием может по местоположению отличаться от истинного. Это в свою очередь может привести к неудовлетворительному распознаванию из-за выбора объектов, несоответствующих эталону.

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

Заключение

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

На рисунке 1 приведен снимок экрана программы с результатами распознавания информационных знаков в кадре из видеопотока, полученном камерой на мобильном устройстве. Экспериментально установлено, что в целом использование разработанных алгоритмов распознавания позволяет на порядок увеличить их быстродействие и решать задачи идентификации информационных знаков в реальном масштабе времени.