Векторизация с помощью волнового алгоритма

Векторизация – преобразование изображения из растрового представления в векторное. Векторизация - процесс, обратный растеризации. Векторизация проводится, как правило, в случае, если результат векторизации подлежит дальнейшей обработке исключительно в программах векторной графики, с целью повышения качества изображения, для создания изображения, пригодного для масштабирования без потери качества, если дальнейшая обработка изображения будет осуществляться на специфическом оборудовании (плоттеры, станки с ЧПУ).

Различают следующие виды векторизации:

§ Автоматическая векторизация — перевод растровых изображений чертежей (сканированных копий, фотографий) в электронный вид с помощью специального программного обеспечения.

§ Ручная векторизация — перевод бумажных чертежей в электронный вид перечерчиванием каждого документа вручную в системах автоматизированного проектирования.

Одним из алгоритмов для нахождения векторного представления из растрового изображения (отсканированного чертежа) является волновой алгоритм. На вход алгоритма поступает бинарное растровое изображение, которое может быть получено из исходного путем пороговой фильтрации. Под бинарным растровым изображением понимается двумерная матрица из черных и белых пикселей, в которой объект задается черными пикселями, а фон – белыми пикселями.

На растровом изображении могут присутствовать отрезки, соединения и пересечения отрезков (рис. 5.1). Включение дуг в изображение в данном пособии не рассматривается.

а)

б)

в)

Рис. 5.1. Объекты растрового изображения

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

Под соединением отрезков будем понимать два отрезка такие, что одна из вершин одного отрезка лежит на другом отрезке. В этом случае они будут иметь одну общую точку и один из отрезков будет разделен на два (рис. 5.1, б).

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

Задачей алгоритма является построение нагруженного графа, у которого нагрузка вершин – пары координат x, y соответствующих узловым точкам изображения.

За узловые точки будем принимать точки соединения изображения линий в растровом изображении. Толщиной линии будем считать ее ширину в пикселях.

Алгоритм реализуется в два этапа:

§ Построение скелета изображения с помощью сферической волны;

§ Оптимизация полученного скелета.

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