## Image Convex Decomposition!!!

leodeus
Unregistered

Post: #1
Hello Again!!

In my actual field of research"image processing and geometrical algorithms", i have a problem: image convex decomposition.....
I havenÂ´t the location of vertices of a polygon (with holes), but only a simple 2D imagen (black and white), see the picture....

Anyone knows any way or algorithm to deal with this problem?

http://labsim.estig.ipb.pt/image_partition_2.jpg

PS - This division is for a better navigation in a 2D space, yes I Know i have another post with this question but this is a new aproach...

Thanks a Lot
Leo
Sage
Posts: 1,199
Joined: 2004.10
Post: #2
I don't know if the book is still in print -- I bought it back in 2000 or so -- but I learned a lot about decomposing arbitrary polygons into convex parts from this guy's book:

http://home.wxs.nl/~ammeraal/grjava.html

Admittedly, it's all java. But really, that's a good thing. Language neutral.
Moderator
Posts: 455
Joined: 2002.09
Post: #3
This is actually two problems. The first is image segmentation (extracting polygons from an image), a common problem in computer vision. The second is called minimal convex polygon decomposition, a common task in computer graphics and computational geometry.

The first problem is the harder one, although for an image this simple it might not be too bad. In computer vision there are all sorts of hairy techniques for extracting edges or polygons from an arbitrary image. Since this example is so straightforward (the black areas are axis oriented rectangles) you could probably write a custom algorithm for it fairly easily.

This isn't a homework assignment, is it?

Measure twice, cut once, curse three or four times.
Sage
Posts: 1,199
Joined: 2004.10
Post: #4
Whoops -- it didn't occur to me that it was a picture, and not already a vector description.

This is a seriously complex topic, and while I'm sure plenty of folks here would like to help, you should probably be discussing with robotics and AI folk.
leodeus
Unregistered

Post: #5
Is for PhD research....

Yes, my principal problem is the first step (2D image to Polygon with vertices), for the second i have some algorithms to deal with this...
OK, I will see these "hairy techniques for extracting edges".....

Thanks
Moderator
Posts: 455
Joined: 2002.09
Post: #6
If the image you showed is typical (axis-oriented black rectangles with hard edges) then I could suggest a couple of custom algorithms that might do the trick. But as I said, the general problem is difficult. Basic book on computer vision will help you here.

What kind of image are you expecting?

Measure twice, cut once, curse three or four times.
leodeus
Unregistered

Post: #7
I expect to "deal" with more complex images, with circles and others shapes ( but always 2D images with 2 colors (black and White for example)....
To start and do some initial tests, this kind of images (axis-oriented black rectangles with hard edges) is ok... if you could suggest a couple of these custom algorithms, I am thankful ....

Leo
Member
Posts: 245
Joined: 2005.11
Post: #8
I suppose the first step would be to break the image up into areas of the same colour. Do this by selecting a pixel, assigning it an area ID. Expand outwards and assign the same ID to any pixel the same colour. Continue this process until every pixel has been assigned an area ID.
Next you have to transform these areas into vector shapes. This is a more complex process, and you will have to make some decisions about how precise you want to be. Basically you have to scan around the edges of the area and break it into a number of straight lines based on the points where the obvious corners are, but since a raster image has "stepped" edges you will probably have to use bicubic interpolation or something to track the real edges of the shape and avoid lots of false positives.
Once you achieve the above stage (which I have helpfully glossed over!) extracting angles of the corners in your vector shape and reducing to acute angles should be relatively simple.
Member
Posts: 469
Joined: 2002.10
Post: #9
What are the constraints on the input image?

Are all the black regions rectangles?
Are all the faces flat?
What is the range of sizes for a continuous coverage area?
Is it a static image, or will the colored areas move?
etc.
etc.

Also, can the problem be decomposed into the same problem for a smaller area?
Is the solution space reducible to a simpler problem?

---Kelvin--
15.4" MacBook Pro revA
1.83GHz/2GB/250GB
hams_
Unregistered

Post: #10
i'm not sure if you're trying to code everything yourself, but intel has this OpenCV library and associated Image Processing Library (IPL). I has a bunch of corner detectors and edge detectors and such. i don't know if it'll work under macos but does run under linux.

http://www.intel.com/technology/computing/opencv/
Moderator
Posts: 455
Joined: 2002.09
Post: #11
If you want to try more difficult images later then I don't think it's worth spending time on my custom algorithms.

For example, one of them was to walk the rows of the image, looking for where each black rectangle starts and stops. Then you could subtract these from the white rectangle to get the final white polygon.

The time might be better spent studying the larger problem, unless you are desperate to prove feasibility of the rest of your solution, and then return to the feature extraction piece later...

Measure twice, cut once, curse three or four times.
Member
Posts: 469
Joined: 2002.10
Post: #12
I've been digging around with computer vision and I've found some samples in intel's opencv library that I think can do what the GP wants to do. It looks like the "contours" sample finds polygon bounds on an arbitrary image.

OpenCV

---Kelvin--
15.4" MacBook Pro revA
1.83GHz/2GB/250GB
Moderator
Posts: 529
Joined: 2003.03
Post: #13
I hope you posed your question on comp.graphics.algorithms, too. That's probably the best place for these kinds of questions.

"Yes, well, that's the sort of blinkered, Philistine pig-ignorance I've come to expect from you non-creative garbage."