Need Help -> Векторизация

From

Victor A. Pavlov (2:5025/81)

To

Evgen Kondratyuk

Date

2002-07-23T18:54:26Z

Area

RU.ALGORITHMS

Доброго здоровья, Evgen!

 Как то раз (Пон Июл 22 2002 20:54) Evgen Kondratyuk написал письмо All:

 EK>   Такая задачка.___________________________________________
 EK>   Входные данные: БМП файл с фигурами(триугольник, квадрат и т.д.).
 EK>   Требуется: Векторизировать файл, тоесть определить линии (начало и конец
 EK> линии) и сложить из линий объекты. Вывести в текстовый файл названия
 EK> объектов и координаты составляющих их линий.

  Обработка производится в несколько этапов:
  1. Бинеаризация.
  Здесь мы приводим полутоновое изображение к двууровневому виду (двум цветам). Если необходима векторизация разноцветных фигур по-отдельности, делаем многоуровневую сегментацию - приведение к ограниченному числу цветов, а далее для каждого цвета (кроме цвета фона) формируем отдельное двухцветное изображение, сводя задачу к предыдущей.
  Алгоритмы бинеаризации довольно хорошо проработаны и выбрать подходящий для конкретного случая не составляет труда.
  2. Выделение границ (edge detect).
  Если изображение представлено, в основном, сплошными закрашенными фигурами, необходим этап выделения границ. Он состоит в обходе всех границ раздела цветов и создании результирующего изображения, в котором закрашены только пикселы, соответствующие границам.
  Если же изображение состоит из тонких линий (вроде чертежа), данный этап не требуется.
  3. Скелетизация (thinning).
  На данном этапе все линии на изображении приводятся к толщине в 1 пиксел. Имеется несколько алгоритмов скелетизации, например, Zhang-Suen. Если нужен пример в исходниках - могу выслать.
  4. Трассировка однопиксельных линий.
  Отслеживаем полученные в результате скелетизации однопиксельные линии, идя вдоль них и записывая подряд каждую точку. Анализируем разветвления, либо зацикливания линий. Получаем "сырое" векторное описание.
  Можно просто тупо соединить любые две закрашенные соседние точки векторами, а затем в несколько проходов разрывать по определенным правилам циклы (треугольники), размером в 1 пиксел, пока подобных циклов-артефактов не останется. Можно также восстанавливать разрывы линий в 1-2 пиксела, для коррекции ошибок сканирования/бинеаризации.
  5. Сглаживание линий.
  Сглаживаем полученные на предыдущем этапе попиксельные ломаные любыми нравящимися нам кривыми (отрезки прямых, дуги окружностей, сплайны и т.п.) и получаем результирующее векторное описание.

Всего хорошего - Victor

--- GoldED/W32 3.0.1
 * Origin: Red Station, Voronezh, Russia (2:5025/81)