Для построения скелета изображения на объекте (отрезке) выбирается начальная (затравочная) точка, от которой начинается распространяться волна, путем добавления пикселей сначала к затравочной точке потом к уже добавленным. Волна генерируется по определенным законам, использующих четырех или восьмисвязанность пикселей.
При 4-х связном растре распространение идет в форме ромба (рис. 5.2, а), при 8-связном – в виде квадрата (рис. 5.2, б). Если попеременно использовать 4-ч и 8-и связанное распространение то форма волны будет близка к кругу (рис. 5.2, в).
При распространении сферической волны на отрезке прямой наблюдаются следующие эффекты: не более чем через 2N шагов распространение волны приобретает устойчивый характер вне зависимости от начальной точки распространения волны (Рисунок 5). Причем N – ширина линии в пикселях.
| а) | б) | в) |
Рис. 5.2. Формы распространения волн на растровом изображении
| а) | б) |
Рис. 5.3. Распространение волны на отрезке
При отличии формы отрезка от прямой, распространение волны также предсказуемо, причем необходимо отметить хорошие огибающие свойства сферической волны.
Узловые точки определяются на каждой генерации волны или через определенное количество генераций волн. В качестве узловой точки берется центр отрезка, образуемого крайними точками необходимой генерации волны.
При достижении волной места соединения двух или более отрезков наблюдается разделение волны на несколько дочерних волн, сохраняющих поведение материнской волны (рис. 5.4). Момент разделения довольно просто отслеживается путем анализа “ширины” волн, т.е. количества точек образующих очередную генерацию волны: перед разделением наблюдается увеличение “ширины” волны с дальнейшим разделением волны на две (иногда более) дочерние волны.
| а) | б) |
Рис. 5.4. Распространение волны на соединении и пересечении отрезков
Выявление мест увеличения “ширины” волны и разделения волны на дочерние позволяет установить точку предполагаемого соединения двух отрезков. Определение увеличения “ширины” волны производится путем сравнения “ширины” очередной генерации волны и ее среднего значения за N предыдущих генераций (N задается заранее). Причем мы получаем две крайние точки (A, B) трассируемого отрезка. После разделения волны на две полуволны, мы получаем еще две пары точек (C, D) и (E, F) (например, рис. 5.5).
Рис. 5.5. Пример определения точки соединения
С помощью анализа этих отрезков (AB, CD, EF) можно оценить положение точки соединения отрезков. Первоначально установим место соединения как центр масс этого многоугольника.