После проведения предварительной обработки изображения с объектом [1] и нахождения его внешнего контура [2] начинается непосредственно процесс поиска вектора.
Базовый алгоритм вычисления вектора расстояний можно описать следующим образом:
1) Находится центр объекта;
2) Рассчитывается длина контура;
3) Контур делится на N равных частей, точки соприкосновения частей выделяются (рис. 6);
4) Центр объекта соединяется с каждой точкой контура, выделенной в предыдущем пункте.
Данный алгоритм имеет основной недостаток — существует вероятность, что в промежутках между будет выпуклость, которую не затронет ни один вектор. Соответственно, в результате эта выпуклость не будет учтена, и форма объекта окажется искаженной(рис. 2). Решением этой
проблемы стала модификация этого алгоритма.
Рисунок 2 — Пример неправильно построенного вектора расстояний
Вместо одного центра объекта, выбираются 2 точки, равноудаленные от него по одной оси(рис. 3).
Рисунок 3 — Пример смещенного центра
|
|
Имея 2 центра для векторов, охватывается большая часть контура, а так же появляется возможность описать объект со второй позиции, что позволяет не упустить различные выпуклости формы объекта.
После нахождения этих центров, строится первая линия, соединяющая один из центров с первым пикселем контура. После чего последующие линии, описывающие форму объекта, строятся по окружности под определенным углом к предыдущей. Для второго центра выполняется аналогичная процедура, но начальной точкой принимается последняя точка контура.
Математически этот алгоритм можно описать следующим способом:
∃ (x;y) Є C, где C – контур объекта.
Пусть точка — первая точка контура, а – центр объекта. Найдем уравнение прямой проходящей через точку p0 и центр объекта с:
, где
Далее берем следующую точку контура , и аналогичным образом находим уравнение прямой, проходящей через и .
Затем находим угол между этими прямыми по формуле:
Если косинус угла φ равен косинусу интересующего нас угла, то учитываем эту прямую, принимаем ее за и берем следующую точку из контура; если нет, то просто переходим к следующей точке.