Vectorization using Bresenham llines

Abstract

We study vectorization algorithms which vectorize raster into vector files consisting of lines with the restriction that pixels corresponding to a line can be fully recovered by applying the Bresenham line drawing algorithm on the endpoints of the line. We also study the problem of finding a minimum number of line segments which is needed to represent a given raster. We prove that this problem is NP-complete and present an efficient approximation algorithm which produces near optimal results.