Vectorizing an image

Question

I'm trying to generate a vector graphic from an area in a bitmap image, and while my current algorithm works for most cases it has some problems and it is quite slow.

So I was wondering if you people know of any simple algorithms or code examples of how to do this efficiently.

My situation is simple. I have a bitmap image, with several flat uniform areas. I wish to convert these areas into sets of points that I can use to recreate them later as vector graphics. I will never have overlapping shapes, the shapes are always enclosed and they are always of one color (the same RGB value for all pixels) so it is quite easy to determine the outline, but doing efficiently is harder.

EDIT: I pressed the submit button too soon...

Ideally I would like a solution working in .NET, but pseudo code should also work well. Maybe you folks know of some good resources on image manipulation?

EDIT again: So what I am after is an algorithm or a library that will give me a list of points or vectors that describe each area in the image, not the vectorized image itself.

Answer 1

Since your objects are distinct, you can run an algorithm for connected component labeling. The wikipedia article is just OK as a start, though I won't know why they concentrate on multi-pass algorithms, one pass works easily enough. While you discover the connected components, you'll have to maintain some data structure to represent the outline. If your objects are known to be simple (e.g. rectangles at normal angles from the axes, or circles) then the representation may be very simple. If they are general shapes, then you'll need some more complex curve representation. (Keep in mind tricky objects like 'U' or 'O' shapes.)

Answer 2

I have no experience in this area, so I'm probably going to describe the worst algorithm one can use, and hopefully others who might otherwise pass this question by will be so incensed by my answer that they will give you some of the better available algorithms today.

I'd do a flood fill algorithm to find the edges of each blob, and make polygons with a vector for each edge point of each blob. This will give you polygons with as many corners as there are pixels surrounding the blob.

Then I'd look up polygon simplification routines that will take, for instance, a bunch of vectors that lie on the same line and remove all the middle points.

The flood fill isn't fully necessary either - just search neighboring pixels from the current pixel (there are 8 neighbors) and use right hand edge following to populate the polygons points.

It should be relatively fast, although the polygons will be very complex unless you get a really good simplification routine.

Answer 3

You might also be interested in this genetic algorithm.