Выделение и распознавание текстовой информации на топографическом плане

Размещено на http://www.allbest.ru/

Институт прикладной математики ДВО РАН, Владивосток

Выделение и распознавание текстовой информации на топографическом плане

А.П. Кудряшов, канд. техн. наук,

И.В. Соловьев

В статье предлагается метод выделения и распознавания информации на топографическом плане. Метод используется для распознавания текста внутри контуров зданий и других условных обозначений. Предлагаемый метод распознавания текста основан на волновом алгоритме Ли. В работе показана универсальность данного алгоритма для задач выделения контуров объектов на черно-белом изображении даже с учетом его зашумленности. Предлагается подход к распознаванию текстовых условных обозначений на топографическом плане, используя анализ последовательности символов.

Ключевые слова: трехмерная реконструкция, топографический план, распознавание текста, городская обстановка, волновой алгоритм.

распознавание текстовый топографический

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

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

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

Ручное моделирование трехмерной сцены городского пространства с высокой степенью детализации требует огромных затрат времени и сил. Автоматизация реконструкции позволяет значительно сократить время, но имеет ряд тех или иных недостатков.

Авторы предлагают выполнить реконструкцию протяженной городской сцены с использованием ее топографического плана (рис. 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).

Рис. 5. У гол поворота по меньшей средней.

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

Распознавание текста

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

Поместим некоторый эталонный символ в начало координат таким образом, чтобы его левый нижний угол совпадал с началом координат. Тогда, чтобы сопоставить любую точку эталона с координатами x и у, с точкой распознаваемого символа, необходимо выполнить следующее преобразование (1):

где Sx, Sy - коэффициенты масштабирования; a - угол поворота символа; Tx и Ty образуют вектор на который смещен символ (2).

где Rmin, Rmax - соответственно длина минимальной и максимальной средней линии описанного около символа прямоугольника минимальной площади; Ew, Eh - соответственно ширина и высота эталонного символа (рис. 6).

Рис. 6. Преобразование перед сопоставновлением изображений.

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

Анализ синтаксиса

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

Целью распознавания текста является определение числа этажей в здании, а также его тип. Будем анализировать найденную надпись по каждому символу, используя следующие критерии:

если число этажей здания равно 1, то единица не наносится на топо- план и далее пишутся буквы. Следовательно, если первый символ является буквой, то число этажей равно 1 ;

если до появления букв не встречается символ «/», то число этажей равно тому числу, что записано перед буквами;

если до появления букв символ «/» встречается, то число этажей равно числу, записанному до этого символа;

если в строке содержится один символ, то им может быть либо «К», либо «Н»; если распознанный символ не является ни одним из перечисленных, то в зависимости от процентного сходства тип здания устанавливается как «К» или «Н»;

если последний символ распознан как «Ж», то может быть два варианта: «КЖ» или «СМЖ». Тогда тип здания выбирается исходя из числа символов в строке, без учета тех, которые определяют число этажей;

если символ «/» распознан как «1» и с двух его сторон находятся числа, то число этажей не вписывается в реальные параметры здания. В таком случает в исходной строке «1» заменяется на «/» и происходит повторный анализ;

когда распознанная надпись не подходит ни под один из описанных критериев, тип здания устанавливается как «КЖ».

Пример обработки служебной информации

Предложенный алгоритм был применен к нескольким контурам на то- поплане (рис. 1). Анализ синтаксиса распознанного текста представлен в таблице.

При таком подходе более 95% текстовой информации распознается верно. Время выделения и распознавания текста на топографическом плане с размерами 7800x7800 пикселей составляет 2 мин.

Заключение

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

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

Литература

Canny J. A computational approach to edge detection // IEEE Transactions on Pattern Analysis and Machine Intelligence. - 1986. - № 8(6). - P. 679-698

Lee C.Y. An Algorithm for Path Connections and Its Applications // IRE Transactions on Electronic Computers. - 1961. - Vol. EC-10, № 2. - P. 346-365.

Моругов А.М., Волков С.В. Методы распознавания символов // Труды международного симпозиума «Надежность и качество». - 2017. - Т. 1. - С.157-160.

Афонасенко А.В., Елизаров А.И. Обзор методов распознавания структурированных символов // Доклады ТУСУР. - 2008. - № 2(18). - Ч. 1. - С. 83-88.

Лапаев О.Н. Современные компьютерные методы распознавания печатного текста // Молодежная наука в развитии регионов. - 2019. - Т. 1. - С.55-58.

Васин Д., Ершов М. Распознавание символов на базе низкоуровневых моделей описания графических изображений // Графикон. Международная конференция по компьютерной графике и зрению. - 2014. - С. 62.

Тимофеева Н.Е., Гераськин А.С. Распознавание рукописных отдельных символов русского алфавита с применением метода выявления «характеристик» символа // Вестник Воронежского государственного университета. Серия «Системный анализ и информационные технологии». - 2016. - С.159-165.

Кулакович А.Ю. Программная реализация однослойной нейронной сети для распознавания цифровых символов // ИВД. - 2018. - №3 (50). - С.58-72.

Кудряшов А.П., Соловьев И.В. Распознавание контуров зданий на топографическом плане для реконструкций городских сцен // Вестник компьютерных и информационных технологий. - 2015. - № 2. - С. 3-8.

Кудряшов А.П., Соловьев И.В. Реконструкция трехмерной модели городского пространства на основе топографического плана // Вестник Амурского государственного университета. - 2016. - № 73. - С. 58-66.

Кудряшов А.П., Соловьев И.В. Реконструкция городской обстановки с учетом рельефа местности, используя топографический план и сервисы Google Maps. // Информационные технологии. - 2017. - Т. 23, №5. - С.382-387.

Размещено на Allbest.ru