Browse Prior Art Database

# Vectorization of line drawing images using B-Rep.

IP.com Disclosure Number: IPCOM000013597D
Original Publication Date: 2000-Aug-01
Included in the Prior Art Database: 2003-Jun-18
Document File: 3 page(s) / 77K

IBM

## Abstract

Disclosed is an algorithm for vectorization of raster images. In this algorithm, vectorized image is presented as B-Rep data structure, such as Half-Edge, Winged-Edge, Quarter-Edge, etc. By using B-Rep to present vector images, topologies of closed loops and branches are presented exactly. This algorithm scans a raster image once and B-Rep data structure is built at the same time. The input is a raster image; it should be a binary image. Usually an image has been thinned before the vectorization. The output is a vector image presented as a B-Rep data structure. The algorithm to vectorize a raster image and to build B-Rep data structure is shown in Fig.1.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 70% of the total text.

Page 1 of 3

Vectorization of line drawing images using B-Rep.

Disclosed is an algorithm for vectorization of raster images. In this algorithm, vectorized image is presented as B-Rep data structure, such as Half-Edge, Winged-Edge, Quarter-Edge, etc. By using B-Rep to present vector images, topologies of closed loops and branches are presented exactly. This algorithm scans a raster image once and B-Rep data structure is built at the same time.

The input is a raster image; it should be a binary image. Usually an image has been thinned before the vectorization.

The output is a vector image presented as a B-Rep data structure.

The algorithm to vectorize a raster image and to build B-Rep data structure is shown in Fig.1.

1

Page 2 of 3

clear prevS canArray

leftV tx=null upleftV tx=null

FA LS E

FA LS E

upleftV tx!=null AND leftV tx==null

prevS canArray

[x+1] != null AND img[y][x]=white

loop for y : y = 0

loop for x : x = 0

img[y][x]

==black

leftV tx==null

prevS canArray[x] ==null

TRUE

TRUE

connect to upper left

FA LS E

TRUE

TRUE

FA LS E

FA LS E

new V tx = create vertex

connect to left

connect to upper right

TRUE

connect to up

leftV tx=new V tx upleftV tx=prevS canA rray[x]

prevS canArray[x] =new V tx

loop for x: x=x+1

loop for y: y=y+1

leftV tx = null

prevS canArray[x]=null

output

2

Page 3 of 3

Fig.1 The vectorization algorithm

Fig.2 shows how vertices can be connected each other.

?

?

?

?

?

?

?

current vertex

m ust be black

?...