Институт прикладной математики ДВО РАН, Владивосток
Выделение и распознавание текстовой информации на топографическом плане
А.П. Кудряшов, канд. техн. наук,
И.В. Соловьев
В статье предлагается метод выделения и распознавания информации на топографическом плане. Метод используется для распознавания текста внутри контуров зданий и других условных обозначений. Предлагаемый метод распознавания текста основан на волновом алгоритме Ли. В работе показана универсальность данного алгоритма для задач выделения контуров объектов на черно-белом изображении даже с учетом его зашумленности. Предлагается подход к распознаванию текстовых условных обозначений на топографическом плане, используя анализ последовательности символов.
Ключевые слова: трехмерная реконструкция, топографический план, распознавание текста, городская обстановка, волновой алгоритм.
распознавание текстовый топографический
Компьютерное моделирование реальных объектов окружающего мира на основе их трехмерной реконструкции является важной и актуальной задачей компьютерной графики и машинного зрения. Полученные таким образом объекты и сцены широко используются в научных, служебных и развлекательных целях. Одна из практических задач - реконструкция сцен городского пространства, которые позволяют ориентироваться на местности, помогают учитывать существующую композицию объектов при проектировании новых архитектурных сооружений, а также для туристической и развлекательной сфер деятельности.
Трехмерная модель городского пространства может состоять из множества классов объектов. Некоторые из них являются его обязательными составляющими, другие дополняют его, для придания сцене большей реалистичности. В зависимости от вида прикладной задачи состав может варьироваться, однако к общему списку классов объектов относятся здания, рельеф, деревья, кусты, светофоры, уличные фонари, автомобили, люди и др.
Уровень детализации сцены и отдельных ее объектов меняется от одной прикладной задачи к другой. Так, например, здания могут быть смоделированы вплоть до воссоздания своей точной трехмерной формы или же представлять из себя некоторый геометрический примитив. Текстуры зданий могут являться частью фотоизображения реального объекта или иметь некий условный вид для определенного типа строения. Во всех этих случаях требуется соблюдать баланс между детализацией сцены и временем ее реконструкции.
Ручное моделирование трехмерной сцены городского пространства с высокой степенью детализации требует огромных затрат времени и сил. Автоматизация реконструкции позволяет значительно сократить время, но имеет ряд тех или иных недостатков.
Авторы предлагают выполнить реконструкцию протяженной городской сцены с использованием ее топографического плана (рис. 1).
Рис. 1. Топографический план с отмеченными зданиями.
Основная информационная ценность топографического плана - это расположение зданий с информацией о них, а также других объектов, таких как электросети, фонари, светофоры, дороги, деревья и т.д. Поэтому важно выделить искомые объекты на сцене и определить их тип.
Один из этапов реконструкции сцены - определение информации о зданиях и других объектах. Внутри контура каждого здания находится текст с условными обозначениями, которые необходимо выделить и идентифицировать.
Способ выделения текста - специфическая задача, которая решается в зависимости от особенностей источника данных. Например, детектор границ Канни [1] позволяет выделить все контуры на изображении, но при этом будет отсутствовать привязка внутренней информации к контурам здания. Поэтому авторами предлагается использовать волновой алгоритм Ли [2], который, как будет показано, в рамках данной задачи универсален.
К текущему моменту разработаны методы [2, 4], направленные на решение задач распознавания символов. В качестве исходных данных некоторые из них используют цветные или черно-белые изображения, на которых алгоритмы производят распознавание текста.
Например, шаблонный метод [5] выполняет сравнение входного изображения с некоторым количеством шаблонных изображений (эталоны). При каждом сравнении рассчитывается коэффициент корреляции. Символ идентифицируется в том случае, если коэффициент корреляции достаточно высок. Алгоритм прост в реализации, но имеет жесткую привязку к шрифту эталонных символов.
Признаковый метод [6] осуществляет анализ признаков символов. Например, количество замкнутых областей, процент заполненности и т.д. Метод позволяет игнорировать начертание символов, однако он чувствителен к дефектам изображения.
Структурный метод [7] преобразует текст в виде графика, который затем анализируется. Достоинства и недостатки данного метода аналогичны признаковому методу.
Нейронные сети [8] позволяют распознавать текст без жестко заданного алгоритма. Распознавание осуществляется на основании обучающей выборки. Метод имеет высокую эффективность и производительность, однако требует большой обучающей выборки и настройки под конкретную задачу.
Авторами был предложен подход, при котором необходимо внутри задний на топографическом плане распознать условные обозначения с помощью волнового алгоритма Ли. Эта информация может быть использована для преобразования в трехмерную модель сцены (на основании количества этажей здания) и ее текстурирования (на основании типа здания). Предлагаемый метод является развитием более ранних работ авторов [9 - 11].
В качестве основного инструмента для выделения информации на топографическом плане будет служить волновой алгоритм [2]. Данный алгоритм изначально предназначен для поиска кратчайшего пути в дискретном лабиринте, однако принцип его работы может быть использован и для того, чтобы выделить контуры объектов на бинарном изображении. После предложенной модификации алгоритм может быть использован для поиска контуров на изображении.
Каждый объект на бинарном изображении является совокупностью черных и белых точек. Такие последовательности будут называться контурами. Волновой алгоритм позволяет обработать изображение таким образом, что в результате будут получены все внешние и внутренние точки, опоясывающие все объекты.
Принцип работы волнового алгоритма заключается в распространении волны в дискретной области из некоторой точки и выделении всех точек, с которыми эта волна столкнулась.
Основные понятия, использующиеся в работе волнового алгоритма:
карта - дискретная область, содержащая числовые значения в каждой своей ячейке;
ячейка - элемент карты с числовым значением, которое ее характеризует;
волна - совокупность действий по переходу от одной ячейки к другой;
пустая ячейка - в которой значение равно 0, а по пустым ячейкам происходит распространение «волны»;
ячейка шага - которая была пустой, но изменила свое значение при распространении волны;
стена - ячейка, в которой содержится значение 1, такие ячейки не участвуют в распространении волны, а являются барьером для нее;
точка контура - ячейка стены, с которой столкнулась волна. При этом значение в ячейке стены будет меняться на 2. Эти точки являются составляющей того множества, которое необходимо определить на этапе выделения контуров объектов;
исходная ячейка - для начала распространения волны ее значение равно 3;
текущее значение волны - максимальное значение среди всех ячеек.
Выполнение волнового алгоритма состоит из последовательности шагов.
Шаг 1. Работа волнового алгоритма начинается с подготовки карты. Карта должна содержать только пустые ячейки и стены. Карту необходимо окружить стенами, чтобы волна не распространялась за ее пределы.
Шаг 2. На карте необходимо указать исходную ячейку, от которой будет распространяться волна. Исходная ячейка должна быть изначально пустой. Текущее значение волны становится равным значению исходной ячейки, т.е. 3 (рис. 2).
Рис. 2. Фрагмент карты со значениями в ячейках.
Шаг 3. Осуществляется поиск всех ячеек на карте, значение которых равно текущему значению волны.
Шаг 4. Выбираются соседние ячейки вокруг тех, которые были найдены на шаге 3. Волна может распространяться двумя способами - по четырем направлениям или по восьми. В первом случае в качестве соседних ячеек выбираются те, которые расположены ближе всего к найденным на шаге 3 по горизонтали и вертикали. Во втором случае в качестве соседних берутся еще и диагональные ячейки.
Осуществляется проверка соседних ячеек относительно исходной. Если соседняя ячейка пустая, то в нее записывается значение, равное значению пустой ячейки + 1. Если соседняя ячейка является стеной, то она становится точкой контура и в нее записывается значение 2.
Шаг 5. Текущее значение волны увеличивается на 1.
Шаг 6. Если на шаге 4 была найдена хотя бы одна пустая ячейка, то алгоритм повторяется с шага 3. Таким образом будут обработаны все пустые ячейки в контуре, внутри которого находится исходная точка.
Шаг 7. Волна не сможет распространяться дальше, если на ее пути нет пустых точек. Результатом будет карта, на которой присутствуют ячейки контуров (рис. 3).
Рис. 3. Результат распространения волны на карте.
Выделенные таким образом ячейки могут образовывать несколько разделенных групп ячеек контуров. Две группы будут считаться разделенными, если никакая ячейка одной группы не является соседней для любой ячейки другой группы. При этом каждая группа ячеек в итоге является контуром. Один из таких контуров всегда будет объединяющим для остальных.
Все выделенные ячейки контуров представляются последовательностью точек, по которым можно восстановить форму объекта на топоплане.
Выделение символов
Следующим этапом необходимо выделить внутреннюю информацию. В ячейках внешнего контура (значения равны 2) устанавливаются значения 0. Это нужно для того, чтобы разделить значения контура и значения внутренней информации. После этого в области контура всем значениям, отличным от 2, устанавливается значение 0. В результате останутся только ячейки контуров внутренней информации.
Далее необходимо надпись разделить на отдельные символы. Для этого снова использовать волновой алгоритм. В этот раз он будет распространяться по точкам внутренней информации (со значением 2). Распространяться он будет по ортогонально-диагональному правилу, т.е. волна будет двигаться не в четырех направлениях, а в восьми. Каждая ячейка волны будет добавляться в отдельный список точек с запоминанием ее координат на карте. После того как волновой алгоритм обработает все точки символа, в них будет установлено значение 0. После этого выбирается следующая ячейка со значением 2, и процесс выделения символа повторяется. Это происходит до тех пор, пока не останется ячеек с внутренней информацией.
Далее из каждого списка точек нужно восстановить изображение символа. Каждая точка из списка помещается на некоторую промежуточную карту, размеры которой соответствуют размеру выделенного символа. После этого внутри образованного контура запускается волновой алгоритм для заполнения пространства внутри символа.
Каждый контур здания обязательно внутри себя содержит служебную информацию о количестве этажей в здании, а также дополнительные данные о его структуре (жилое, нежилое, кирпичное и т.д.). Информация о количестве этажей является необходимой для последующей трехмерной реконструкции. При наличии данных об этажности здания, а также масштабе то- поплана могут быть установлены высота городского объекта и его тип.
Угол наклона надписи вычисляем следующим образом. На топоплане текст внутри зданий всегда имеет ту же ориентацию, что и одна из его стен
Размеры символов могут варьироваться. Исходя из этих положений, в качестве способа распознавания текста выбран метод корреляции пикселей. Далее будет описан алгоритм распознавания такого текста.
Топоплан содержит ограниченное количество возможных символов (рис. 4). Все возможные текстовые символы внутренней информации здания представлены на рисунке ниже:
Рис. 4. Служебные символы, встречающиеся на топопланах.
Каждый эталонный символ представляет матрицу, заполненную нулями и единицами (ноль соответствует белому цвету на изображении, а единица - черному).
Определение угла наклона надписи
Угол наклона надписи определяется ее положением относительно горизонтальной линии изображения. Надпись может содержать один или несколько символов. Если надпись содержит несколько символов, то направление надписи будет определяться по прямой, которая проходит между двумя наиболее удаленными друг от друга центрами описанных вокруг символов прямоугольниками.
Если надпись состоит из одного символа, то им может быть или буква «К», или буква «Н». Поэтому распознавание символа будет происходить только для двух эталонов.
Для каждого из эталонных символов предполагается, что высота символа больше, чем его ширина, а описанный вокруг символа прямоугольник, имеющий наименьшую площадь, практически точно совпадает с описанным вокруг символа прямоугольником, стороны которого параллельны сторонам изображения. Данные предположения позволят точно определить угол наклона каждого символа. Направление надписи будет совпадать с отрезком меньшей длины соединяющего середины противолежащих сторон описанного вокруг символа прямоугольника (рис. 5).