ВведениеПоиск геометрических примитивов на изображениях широко используются в интеллектуальных системах распознавания изображения как промежуточная стадия получения исходных данных для последующего анализа, либо для уточнения области дальнейшего распознавания [1]. Так, например, для распознавания дорожных знаков в видео потоке более оптимальным является распознавать только изображения, находящиеся внутри объектов, имеющих геометрические формы: круга, треугольника, квадрата и пр. Также следует отметить, что на реальных изображениях данные фигуры могут быть значительно искажены в связи с углом их съемки и проекцией. Так круг будет чрезвычайно редко представлен в данном виде и почти всегда представляется в виде эллипса, границы которого достаточно сильно размыты и имеют неправильную форму.Применение классических методик распознавания изображений, использующих сверточные и рекуррентные нейронные сети [2], а также другие сети для классификации в задачах распознавания простых геометрических примитивов крайне неэффективны и требуют значительных вычислительных ресурсов, особенно при больших размерах изображений или поточного видео. Более правильным подходом является обработка изображения и поиск замкнутых контуров, удовлетворяющих необходимым условиям.Поиск примитивов в изображении предлагаемым методом можно разбить на четыре основных этапа: обработка изображения и приведение его к бинарной карте, поиск контуров по бинарной карте, поиск примитивов в массиве контуров, фильтрация набора найденных примитивов. 1. Определение контуровТак как анализ цветов изображений не производится, для ускорения работы и упрощения алгоритмов изображение переводится в оттенки серого. Далее используется уже ставший классическим алгоритм Джона Кенни (John Canny) [3]. Данный алгоритм сначала сглаживает изображение, чтобы устранить шум и находит градиент изображения, чтобы подсветить области с высокими пространственными производными. После чего алгоритм проходит по этим областям и подавляет все пиксели, которые не в максимуме (не максимальное подавление). После чего градиентный массив уменьшается гистерезисом, который используется, чтобы отследить оставшиеся пиксели, которые не были подавлены. Гистерезис использует два порога и если величина ниже первого порога, то она устанавливается в ноль (делается не краевой). Если величина выше высокого порога, она делается краевой. В том случае если нет пути от текущего пиксела к пикселю с градиентом выше второго порога, и если величина яркости пикселя находится между двумя порогами, то она устанавливается в ноль. В результате преобразований получаем бинарную карты изображений.Далее осуществляется поиск контуров границ и при этом используется алгоритм Судзуки (Suzuki, S.) [4]. При анализе используется небольшая модификация оригинального алгоритма, использующая аппроксимацию линий для замыкания контуров. Далее выбирались только замкнутые контуры, имеющие более семи линий с заданной пропорцией общей площади контура по отношению ко всему изображению. 2. Определение эллиптических объектовОсновным этапом обработки изображения является непосредственно определение является ли замкнутый контур относительно правильным эллипсом. Для этого создается массив уникальных точек P = áX, Yñ, образующих контур. В данном массиве находятся минимальные и максимальные координаты точек по обеим осям: Таким образом, находится прямоугольник, описывающий предполагаемый эллипс (рис. 1). Стороны прямоугольника, разделенные пополам a = (Xmax - Xmin) / 2 и b = (Ymax - Ymin) / 2, являются также полуосями искомого эллипса. Данное утверждение правомерно, так как началом координат всегда является верхний левый угол изображения, следовательно, все координаты положительны. Центр данного прямоугольника, при этом является центром предполагаемого эллипса.Далее, используя стандартную формулу эллипса в декартовых координатах, и выражая большую и малую полуось через имеющиеся координаты, получаем следующую зависимость для определения любой точки эллипса: Однако данная зависимость является уравнением, что требует жесткого выполнения условия равенства. Так как на практике контур практически никогда не может быть рассчитан по битовой карте точно, то необходимо расширить зависимость. Предлагается сделать это двумя различными способами в зависимости от требуемой скорости алгоритма и его точности. Если требуется обеспечить наивысшую скорость работы, пожертвовав точностью (как показывает практика не значительной), то наиболее простым является создание системы неравенств, при удовлетворении которой точка, могла бы быть признана принадлежащей эллипсу.Введем допуск на искажение формы эллипса D = max (a, b,) / 12 , характеризующий расстояние до математической границы Описанная система неравенств определяет принадлежит ли точка p = {x, y} массива P эллипсу с границами в крайних точках и толщиной контура D в 12 раз меньшей, чем наибольшая ось эллипса.Проверяем все точки исследуемого контура на выполнение системы неравенств. В случае если каждая точка, образующая контур удовлетворяет системе неравенств, считаем контур эллипсом с полуосями a и b и центром в точке {Xmin + a, Ymin + b}. В случае, если a = b ± D/2, эллипс считаем окружностью с радиусом r = (a + b) / 2 и с центром в той же точке.Определение условий съемки и реконструкция возможной окружности по эллипсу являются отдельной задачей и данной статье не рассматриваются, но для ее решения исходными данными могут быть как изменение найденного эллипса в последовательности кадров (съемка в движении), так и по статическим изображениям ориентируясь на других искажениях и артефактах изображения.В случае если необходимо обеспечить большую точность определения, то для этого можно использовать обыкновенный полносвязный многослойный персептрон всего с тремя входами и двумя выходами. На вход можно подавать количество вершин в анализируемом контуре, средневзвешенное отклонение от центра между эллипсами минимума и максимума и дельту между размерами полуосей |a - b|, так как практика показывает, что размер вылета за норму найденных точек контура зависит от пропорций эллипса.ЗаключениеПредлагаемый метод хорошо себя зарекомендовал при решении различных практических задач, таких как поиск знаков на фотографиях [5], обнаружение окружностей на диаграммах и схемах [6], поиск границ овалов лиц и др. Основным достоинством метода является его чрезвычайная простота реализации, а также высокая скорость работы, что позволяет применять его не только на современных стационарных компьютерах, но и мобильных устройствах с низкой вычислительной мощностью. При корректном использовании для изображений имеющих четкие контрастные границы эллиптических объектов и имеющие незначительный угол наклона к границам изображения, метод имеет приемлемо низкое количество ошибок и может эффективно применяться на предварительных стадиях распознавания изображений.