Need algorithm to detect region/polygon

[trant]

Hello,

I am hoping to find someone who is very knowledgeable in geometric algorithms.

I need to scan a bmp file which has many distinctly colored continuous
regions. The color is the exact same RGB value for each pixel in it's region,
if a pixel has any variation in RGB from another it means it's from a
separate region.

Here is a sample of what it looks like:
http://members.verizon.net/~vze28272/a1.JPG

Upon scanning such a file (this one is converted to JPG for compression
sake, but the real file is bmp and completely solid colors) I want to be able
to make an object which represents each distinct region - so it would have a
polygon which roughly matches the border from the image (though not exact
since it would be far too many vertices if I tried to make a polygon that fit
it precisely by the pixel).

The only thing that I can think of which remotely resembles what this
algorithm needs to do is convex hull, but that algorithm would not be good
because it would create polygons with shortest distance between the points
and thus create bulkier shapes - I need the shapes to roughly "shrink" into
these colored regions

The desired result would be illustrated by this next picture:

http://members.verizon.net/~vze28272/a2.JPG

Imagine the letters represent the objects which would be created for each
colored region detected, and the lines represent the polygon border for them.
Notice those borders do not precisely follow the border pixel by pixel so
that I can save potentially hundreds of Points per polygon. This is
absolutely necessary since the real application would be dealing with
thousands of these regions.

Can you recommend any algorithm or article that may teach me how to
accomplish this goal?

Thanks in advance!

 

[Peter Duniho]

Hello,

I am hoping to find someone who is very knowledgeable in geometric algorithms.

Sorry. Nobody here but us chickens.

[...]
Can you recommend any algorithm or article that may teach me how to
accomplish this goal?

A quick Google search on "border tracing algorithm" turned up a lot of
potential material, including this Powerpoint presentation summarizing a
large number of such algorithms:
http://www.cs.uga.edu/~emani/IMAGE SEGMENTATION1.ppt

One of the simplest algorithms in there to understand and implement
(IMHO) is the one described in detail here:
http://users.utcluj.ro/~tmarita/IPL/L6/PI-L6e.pdf

Pete

 

[Chris Dunaway]

Hello,

I am hoping to find someone who is very knowledgeable in geometric algorithms.

I need to scan a bmp file which has many distinctly colored continuous
regions. The color is the exact same RGB value for each pixel in it's region,
if a pixel has any variation in RGB from another it means it's from a
separate region.

Here is a sample of what it looks like:http://members.verizon.net/~vze28272/a1.JPG

Upon scanning such a file (this one is converted to JPG for compression
sake, but the real file is bmp and completely solid colors) I want to be able
to make an object which represents each distinct region - so it would have a
polygon which roughly matches the border from the image (though not exact
since it would be far too many vertices if I tried to make a polygon that fit
it precisely by the pixel).

The only thing that I can think of which remotely resembles what this
algorithm needs to do is convex hull, but that algorithm would not be good
because it would create polygons with shortest distance between the points
and thus create bulkier shapes - I need the shapes to roughly "shrink" into
these colored regions

The desired result would be illustrated by this next picture:

http://members.verizon.net/~vze28272/a2.JPG

Imagine the letters represent the objects which would be created for each
colored region detected, and the lines represent the polygon border for them.
Notice those borders do not precisely follow the border pixel by pixel so
that I can save potentially hundreds of Points per polygon. This is
absolutely necessary since the real application would be dealing with
thousands of these regions.

Can you recommend any algorithm or article that may teach me how to
accomplish this goal?

Thanks in advance!

Perhaps this will help you:

http://www.bobpowell.net/region_from_bitmap.htm

Chris

 

[not_a_commie]

As a side note, an RLE format (such as PNG) would be significantly
smaller and better looking for compressing those images. As a general
rule, use JPG for photos and PNG for everything else. The Medial Axis
Transform may be helpful for you. The Hough Transform may be worth
looking into as well. A standard point-in-polygon algorithm may be
sufficient for you as well.

 

[trant]

Thank you for the great suggestions!

I will study them and see how I can implement them for my purposes

 

[Jeff Johnson]

As a general rule, use JPG for photos and PNG for everything else.

Amen.

 

[Jeff Johnson]

You forget 1 thing, photo's you make yourself with your digital camera
should always be kept in RAW format.

And only convert to jpeg when done with all the editing, but still keep
the raw file

Well, yes. I'm referring to selecting an image format to use for, say, Web
display. People seem to think that everything displayed on the Web should be
a JPG (or maybe a GIF if it's really small, needs transparency, or needs to
be animated) but for solid colors, PNG is so much better.