In December I wrote several blogs about the algorithm underlying the poly2mask function. Basically, the algorithm uses a 5-by-5 subpixel grid and lays out the polygon along the edges of the grid, like this:
The algorithm then makes a binary decision (inside or outside) for each pixel. A given pixel is inside the polygon if and only if the center subpixel square is inside the polygon.
A very similar procedure could be used to compute an approximate fractional coverage for each pixel. In other words, approximately what fraction of each pixel is inside the polygon? It might look like this:
For each pixel, you just divide the number of gray squares by 25 to get the approximate fractional coverage. This computation could be used to do antialiased polygon scan conversion. For example, compare the left and right images below. The left image is a binary image containing the output of poly2mask. You can see the "jaggies" along the edges. The right image is a grayscale image containing the fractional coverage of each pixel. The edges in this image appear smoother.
Readers: Would you like to see this functionality in the Image Processing Toolbox? If so, what do you think you might use it for?
Published with MATLAB® 7.3
Hi, it’s funny & tasty …
I was implemented some algorithm like this (2 years ago)…
I faced some problem in some polygon that have obtuse angles ((like more than 140 … i think ))
I couldn’t solve this problem and developed algorithm until now!!
those days i thought((spiked in my mind!!)) to other algorithm that :
we find or estimated Center of object for example center in circle or circumcenter or incircle in triangle …
now we have 2 thing 1)1 dot in shape 2)other dot((edge of shape))
now we make function that coordination of edge’s dot are independent variable and DISTANCE from enter of shape to edge’s shape is dependent variable …
if we plot this function, peak of this function ((local maximum)) are cornet of polygon ..
it’s raw but beauty i think …
what’s your idea?
Steve,
Thanks for the info on the poly2mask/roipoly functions. Now I understand why pixels at integer (x,y) locations along horizontal and vertical lines are often clipped out.
To solve this problem, I found the “inpoly.m” subroutine in the file exchange. It not only calculates which points are in a polygon, but also identifies points on the borders of a polygon.
I could use a function like this for some interesting image resorting algorithms (CT reconstruction and the like.) Also, I’ve wanted a function like this in past for better ROI selection.
AliReza – I don’t really understand what you mean.
Anthony – What do you mean by “better ROI selection”?
Matt – The MATLAB function inpolygon can also identify points on the polygon borders.
http://www.sharemation.com/naarkhoo/max.jpg?uniq=yut6jo
Steve … i draw my think …
NOW YOU SEE WHAT i MEANT tanx
AliReza – you can use the bwboundaries function (or bwtraceboundary) to generated an ordered list of vertices. Then you can compute the distance between the centroid and each vertex.
Hi Steve,
I stumbled across your blog today and have found the posts about the poly2mask function really helpful.
I too, like Anthony, would benefit from this anti-aliased poly2mask function in constructing “better ROIs” for use in image reconstruction, as some algorithms benefit from being able to assign fractional coverage of pixels.
David – Thanks for your input.
Hi,
I read your blog today and it is very close to what I am looking for.
In your blog you describe a better poly2mask function.
I am looking for a function that “smoothens” a mask using the original image information and returns a mask containing subpixel coordinates.
I am using this information to compare between similar contours of objects, and the granolarity of full pixel location causes errors in the similarity measure.
Thanks,
Ruthy
Ruthy—I’m not sure what you mean by “a mask containing subpixel coordinates.”
Hi Steve,
I am doing a segmentation of an image and I use the boundary information to compare between two curves and decide weather they match.
If I am using the output of the segmentation as a discrete numbers, I will have a very noise edge and the comparison will not be robust.
I want to get the edge of the shape in a sub-pixel resolution to be able to better compare the edges.
Ruthy
Ruthy—Thanks for the suggested application.
I’m using the following combination to obtain the boundary-pixels of the convex hull of some marks in an image:
thresholding
bwboundaries (to get more information for (un)selecting marks)
convhull (gives me a poygon, but I need all the pixels, therefore …)
poly2mask
bwtraceboundary
If I use this procedure objects are always shrinking (although valid convex marks should be an invariant of that procedure). Since I’m using convhull, where I lose information about the boundary, I can not ensure that the marks don’t get deformed slightly, but for keeping up the area it could be useful to have the fractional coverage for selection as parameter (better performance) or at least get it as result.
This would be useful, when having a fast precompiled poly2mask-version – an interpreted one is as good as writing it on my own.
(By the way: Another improvement for my algorithm would be, if bwtraceboundary would give me the outer coords, but not the center-coords of the pixels. Is there some way?)
Regards,
Thomas
Thomas—If you have enough memory to upsample your image by a factor of 3 in both directions, then you could do bwboundaries on the result. Then if you can scale the boundary locations back down you can get boundaries along the pixel edges instead of through the pixel centers.
I’ll think about doing a blog post on this idea.
Hi Steve,
I really enjoyed your last several posts. I would really really find this code useful, esp. in generating stimuli at non grid locations for my simulations. Can you please share this anti-aliased polyscan algorithm ?
Thanks a lot in advance
Rishabh
Hi Steve,
I really enjoyed your last several posts. I would really really find this code useful, esp. in generating stimuli at non grid locations for my simulations. Can you please share the code for the mentioned anti-aliased polyscan algorithm ?
Thanks a lot in advance
Rishabh
Rishabh—I haven’t written it.