Методы распознавания в наше время используются в автоматизированных системах, связанных с такими отраслями как криминалистика, медицина, военное дело, астрономия (смещение объектов, звезд, планет), и т.д. Такие применения теории распознавания, как кластерный анализ, выявление закономерностей во множестве экспериментальных данных, прогнозирование различных процессов или явлений широко используются в научных исследованиях. Большую роль методы распознавания играют в активно развивающихся геоинформационных системах. Принципы распознавания образов можно также применять и при разработке некоторых тестирующих систем [3].
Однако обеспечить удовлетворительный результат в некоторых задачах (распознавание быстродвижущихся подобных объектов, рукописного текста) все еще не удается [1]. Таким образом, разработка новых алгоритмов распознавания объектов и их улучшение связана с необходимостью совершенствования существующих методов распознавания, использующихся при идентификации объектов на изображениях.
Теория распознавания образов изначально развивалась по двум направлениям: детерминистскому и статистическому, причем чаще всего строго различить их не удается. Детерминистский подход [5] включает различные методы: эмпирические, эвристические, в основе которых лежат здравый смысл, более или менее удачное моделирование действий, осуществляемых мозгом человека; математически формализованные, например, основанные на модели порождения объектов того или иного образа. При этом используется различный математический аппарат (математическая логика, теория графов, топология, математическая лингвистика, математическое программирование и др.) [4].
Статистический подход опирается на фундаментальные результаты математической статистики (теория оценок, последовательный анализ, стохастическая аппроксимация, теория информации).
В процессе развития теории распознавания различные подходы и применяемый математический аппарат переплелись таким образом, что классификация различных алгоритмов по используемым методам является условной и неоднозначной [6].
В представленной статье для распознавания образов используется метод, связанный с определением центра масс исходного образа в совокупности с анализом отдельных признаков, свойственных геометрическим фигурам. Рассмотрим суть предлагаемого метода распознавания.
Пусть имеется изображение некоторого размера, в самом простом случае — битовое. В случае цветного изображения его всегда можно преобразовать в изображение в оттенках серого.
Для удобства работы с точками изображения внесем их в отдельный массив сразу после открытия файла с изображением. В этом массиве будут содержаться элементы, равные нулю или единице. Единица будет соответствовать точке изображения, цвет которой отличен от белого.
Выделение контура образа будет проходить в два этапа. На первом этапе необходимо пройти по массиву и выделить в нем граничные точки. Граничной является такая точка, которая имеет хотя бы одну точку белого цвета в качестве соседней. Такие граничные точки в массиве будем обозначать ʺдвойкамиʺ. Таким образом, в конце первого этапа наш массив будет содержать еще и границы отдельных областей (фигур). Однако на этом этапе еще не понятно, какие граничные точки относятся к одной области, а какие — к другой.
На втором этапе необходимо идентифицировать граничные точки каждой области и выделить их в отдельные группы (контуры). Контур будет храниться в отдельном массиве. Для выделения контура организуем просмотр массива, и как только встретим двойку, вновь заменим ее на единицу (сохранив ее предварительно как первую точку нового контура). Далее будем искать соседние с ней двойки, добавлять их в контур и заменять на единицы. Как только с текущей ʺдвойкойʺ не оказывается соседних ʺдвоекʺ, завершаем процесс — контур определен. Таким образом выделяем все контуры на изображении.
После выделения всех контуров можно начинать их анализ. При этом сначала проанализируем принадлежность контуров к простейшим геометрическим фигурам, таким как: треугольник, равносторонний треугольник, прямоугольник, квадрат, окружность, эллипс.
Очевидно, что у всех вышеперечисленных фигур можно найти по крайней мере две особые точки, расстояние между которыми максимально. Для треугольника и прямоугольника такие точки будут являться двумя вершинами. Для окружности — это диаметрально противоположные точки. Для эллипса они являются концами его большой оси.
Рассмотрим, например, как происходит идентификация треугольника. Очевидно, что для треугольника остается найти еще одну вершину. Ее найдем на основе того, что сумма расстояний до нее от первых двух вершин должна быть максимальной. После этого оставшиеся точки контура нужно проверить на принадлежность отрезкам, концами которых являются вершины треугольника. Такую проверку выполним на основе следующего рассуждения.
Некоторая точка лежит на отрезке, если сумма расстояний от нее до концов отрезка равна длине этого отрезка. Если все точки контура удовлетворяют отмеченному рассуждению, то фигура, определяемая контуром, является треугольником. Если при этом расстояния между вершинами равны, то треугольник является равносторонним.
При проверке расположения точек контура нужно учесть, что координаты точек дискретны. Поэтому точного равенства расстояний требовать нельзя (точка может не располагаться точно на отрезке).
Опишем теперь алгоритм распознавания формы произвольной фигуры. Очевидно, что уникальной точкой фигуры выступает центр масс. Будем его использовать для сравнения реальных размеров фигур при приведении их к одному масштабу. В качестве второй точки, определяющей характерный размер фигуры, возьмем точку, наиболее удаленную от центра масс. Алгоритм сравнения и распознавания в этом случае будет сравнивать две фигуры, одна из которых является эталонной.
В зависимости от формы фигур определяющее значение при распознавании может иметь или длина контура, или площадь фигуры, ограниченной контуром. Однако часто использование в качестве признака величины площади может давать неверный результат при распознавании. Поэтому нужно предусмотреть оба варианта распознавания как совместно, так и по отдельности.
Отметим также, что для распознавания формы контуров можно использовать способ совмещения контуров. Однако при этом необходимо совместить контуры поворотом, т.е. нужно знать угол, на который необходимо повернуть сравниваемый контур для его совмещения с эталонным образом. Здесь также может помочь центр масс и наиболее удаленная от него точка контура. Определение угла поворота изображено на рисунке 1 (Точки О и О1 — центры масс контуров фигур, А и А1 — наиболее удаленные точки от центра масс).
Однако применение такого метода для фигур, обладающих осью (осями) симметрии может не дать ожидаемого результата. Поэтому в таком случае нужно использовать дополнительные признаки или способы, которые позволят в итоге найти верное расположение фигуры. Один из таких способов — это подсчет расстояний от точек фигуры до линии, проходящей через центр масс фигуры и условную точку подвеса фигуры (линия в таком случае будет вертикальной).
Можно также вращать фигуру на некоторый угол и проверять, совместились ли фигуры. При этом, однако, на распознавание придется потратить достаточно много времени, или существенно оптимизировать алгоритм. Некоторые возможности оптимизации отдельных алгоритмов (не относящиеся напрямую к распознаванию образов) рассмотрены в работе [2].
Программная реализация описанного алгоритма распознавания форм двумерных объектов продемонстрировал на практике хорошие результаты распознавания. Тем не менее, необходима доработка и усовершенствование алгоритма с целью дальнейшего повышения качества распознавания и добавления новых функций, поскольку практическая значимость рассматриваемой области высока.