Алгоритм векторизации чертежа

Автор: | 31.01.2018

Постановка задачи. Этапы алгоритма
ЭТАП 1. От точек вдоль рядов к скелетным точкам линий
ЭТАП 2. От скелетных точек линий к точкам вдоль линий
ЭТАП 3. Определение вида кривой через аппроксимацию
Программная реализация 1-го этапа на языке VLISP

Постановка задачи. Этапы алгоритма

Векторизация – преобразование растрового  изображения (отсканированной картинки или фото) в векторное представление. Задачу векторизации изображения можно рассматривать как один из этапов решения задачи чтения чертежа:

Ниже описан алгоритм перехода от растра точек до интерпретации линий. В качестве исходной информации принимается отсканированный чертеж (из 2-х цветов).

 

   

 Данные об изображении сохраняются в BMP-файле. Каждая точка идентифицируется координатой X (порядковый номер точки в ряду) и координатой Y (номер ряда).

 

Суть алгоритма векторизации сводится к преобразованию упорядоченной последовательности точек вдоль рядов к упорядоченным последовательностям точек вдоль участков линий и распознавание этих линий. Алгоритм векторизации состоит из 3-х этапов:

  1. Непрерывные последовательности точек в каждом ряду преобразуются в отрезки (штрихи), для каждого из которых определяются срединные (скелетные) точки линий.
  2. Формируются ломанные из отрезков между ближайшими скелетными точками (вдоль линий).
  3. По вершинам ломанных через аппроксимацию определяется вид кривой (окружность, прямая и др.)

Ниже этапы векторизации рассмотрены подробнее

ЭТАП 1. От точек вдоль рядов к скелетным точкам линий

 Точки считываются из BMP-файла вдоль ряда слева направо и по рядам снизу вверх. Непрерывные последовательности точек в каждом ряду преобразуются в отрезки (штрихи).

При этом штрихи запоминаются в списке скелетных точек линий LSP (List of skeleton points) в каждом ряду:

((Y (XP W) … (XP W))… (Y.. (XP W)… (XP W..))),

где Y – номер ряда (начиная от нижнего ряда); XP – координата срединной точки штриха; W — длина штриха (измеряется количеством точек линии по горизонтали).

При формировании списка выполняются 2-а условия:

  • Если разрыв между соседними точками > 2, то начинается новый штрих.
  • В список LSP заносятся только штрихи определённых размеров Wmin< W < Wmax.

Эти условия частично отсекают «шумы». Кроме того, последнее условие не позволяет учитывать штрихи больших размеров. Эти штрихи описывают горизонтальные и близкие к ним участки линий. На таких участках количество скелетных точек вдоль линии получается небольшой, причем, эти точки уже не определяют траекторию линии. К тому же, штрихи горизонтальных участков не отражают истинную толщину линии.

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

((X (YP W) … (YP W))… (X.. (YP W)… (YP W..)))

ЭТАП 2. От скелетных точек линий к точкам вдоль линий

По информации из списка скелетных точек линий LSP формируются списки LPL (List of points on the line) из последовательности точек линий:

(P1 … Pn), где P список ((XP YP) W).

Списки LPL инициализируются по точкам первого ряда LSPR списка LSP и объединяются в списке LCL (list of current lines): ( LPL… LPL). Потом к каждой линии с списка LCL присоединяется точка очередного ряда списка LSP, у которой соответствуют (в границах допуска) координаты YP, XP и ширина линии W тем же параметрам последней точки линии LPL. Если такой точки в ряду нет, линия заканчивается. Данные о линии извлекаются из списка LCL и запоминаются в списке LSL (list of saved lines): ( LPL … LPL). Линия, также, заканчивается в случае неопределенности – на одну и ту же точку очередного ряда претендуют две или больше линий. Последнее условие исключает возможность продолжения линии по-другому направлении, например, при пересечении линий:



После присоединения к линиям ( LPL … LPL) точек очередного ряда в нем могут остаться невостребованные точки. По этим точкам инициализируются новые линии LPL. Они заносятся в список LCL. После анализа последнего ряда списка LSP все линии LPL из списка LCL заносятся в список LSL.

ЭТАП 3. Определение вида кривой через аппроксимацию

Список LSL содержит подсписки из непрерывных последовательностей точек (координат точек), каждый из которых интерпретирует при помощи ломанной отсеки (дуги) линий.

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

Дуги, которые описываются одинаковыми функциональными зависимостями, относятся к одной линии. Функциональные зависимости для этих дуг уточняются за счет общей математической обработки данных по дугам. Дуги, которые имеют относительно небольшие размеры (по сравнению с шириной линии) и не попадают ни в одну из групп, можно отнести к «шумам». Наличие (или отсутствие) промежутков между дугами определяется по данным из списка LBP. Геометрические признаки (параллельность, перпендикулярность, касание линий и прочие) определяются между элементами чертежа в пределах допуска, а также уточняются за счет общей математической обработки данных по ним. Положение точек пересечения линий определяется из совместного решения уравнений, которые определяют линии.

Программная реализация 1-го этапа на языке VLISP

;Считывание координат черных точек из BMP-файла
(defun C:bmp()
(setq YS nil SP nil) (command "Osnap" "None")
(setq FR (open "D:/Sv/Work/Paz.bmp" "r")) ; (setq FR (open (getstring "File to read?") "r") )
(repeat 18 (b1)) (setq XSIZE (b2) YSIZE (b2)) ( repeat 36 (b1)) ( setq Y 1)
(repeat YSIZE (b3) (setq X 1)
(repeat XSIZE
(if (= ( logand N MASK) 0) (progn ;(command "POINT" (list X Y))
(Y_section)
(X_section)
) )
(setq MASK (lsh MASK -1)) (if (= MASK 0) (b3)) ( setq X (1+ X)))
(setq Y (1+ Y)))
(zap_X_ost) ; отключать при отключении (X_section)
(command "zoom" "e")
)

; **** BMP functions ****
(defun b1() (read-char FR))
(defun b2() (setq N (+ (b1) (lsh (b1) 8) (lsh (b1) 16) ( lsh (b1) 24))))
(defun b3() (setq MASK (lsh 1 31)) (setq N (+ ( lsh (b1) 24) (lsh (b1) 16) (lsh (b1) 8) (b1))))

; Горизонтальные штрихи.
(defun Y_section ()
(if ( = YS nil) (setq XN X XK X))
(cond ((/= Y YS) (init_Y_shtrih) (setq YS Y))
((< (- X XK) 2) (setq XK X))
((>= (- X XK) 2) (init_Y_shtrih))))
(defun init_Y_shtrih () (zap_shtrih) (setq XN X XK X))
(defun zap_shtrih () (if (and (< (- XK XN) 15) (> (- XK XN) 2))
(command "Line" ( list XN YS) (list XK YS) "")))

; Вертикальные штрихи.
(defun X_section ()
(if (= SP nil) (setq SP (list (list X Y Y))))
(setq SP1 (assoc X SP))
(cond ((= SP1 nil) (setq SP (cons (list X Y Y) SP)))
((< (- Y (last SP1)) 2) (setq SP ( subst (list X (cadr SP1) Y) SP1 SP)))
((>= (- Y (last SP1)) 2) (init_X_shtrih))))
(defun init_X_shtrih () (zap_X_shtrih) (setq SP (subst (list X Y Y) SP1 SP)))
(defun zap_X_shtrih () ( setq YN (cadr SP1) YK (last sp1))
(if (and (< ( - YK YN) 15) (> (- YK YN) 2)) ( command "Line" (list X YN) (list X YK) "")))

(defun zap_X_ost () (setq LSP (length SP) N 0)
(repeat LSP (setq SP1 (nth N SP) X (car SP1)) (zap_X_shtrih) (setq N (1+ N))))

Автор: Николай Свирневский

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *