Image Convex Decomposition!!!
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
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
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.
http://home.wxs.nl/~ammeraal/grjava.html
Admittedly, it's all java. But really, that's a good thing. Language neutral.
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?
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.
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.
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.
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
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
If the image you showed is typical (axisoriented 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?
What kind of image are you expecting?
Measure twice, cut once, curse three or four times.
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 (axisoriented black rectangles with hard edges) is ok... if you could suggest a couple of these custom algorithms, I am thankful ....
Leo
To start and do some initial tests, this kind of images (axisoriented black rectangles with hard edges) is ok... if you could suggest a couple of these custom algorithms, I am thankful ....
Leo
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.
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.
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?
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
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/
http://www.intel.com/technology/computing/opencv/
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...
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.
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
OpenCV
Kelvin
15.4" MacBook Pro revA
1.83GHz/2GB/250GB
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 pigignorance I've come to expect from you noncreative garbage."
Possibly Related Threads...
Thread:  Author  Replies:  Views:  Last Post  
Breaking down a concave mesh into convex pieces  Willem  5  6,226 
Aug 10, 2008 05:49 AM Last Post: Willem 

Rendering 2D Shadows for Convex Shapes  Nick  16  11,871 
Nov 28, 2006 11:50 AM Last Post: memon 