Steve on Image Processing

February 6th, 2007

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

16:30 UTC | Posted in Uncategorized | Permalink |

You can follow any responses to this entry through the RSS 2.0 feed. You can skip to the end and leave a response. Pinging is currently not allowed.

14 Responses to “Antialiased polygon scan conversion: Are you interested?”

1. AliReza KashaniPour replied on February 9th, 2007 at 18:32 UTC :
   

   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?

2. Matt K. replied on February 12th, 2007 at 17:17 UTC :
   

   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.

3. Anthony Davis replied on February 14th, 2007 at 12:53 UTC :
   

   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.

4. Steve replied on February 15th, 2007 at 16:42 UTC :
   

   AliReza - I don’t really understand what you mean.

5. Steve replied on February 15th, 2007 at 16:55 UTC :
   

   Anthony - What do you mean by “better ROI selection”?

6. Steve replied on February 15th, 2007 at 16:56 UTC :
   

   Matt - The MATLAB function inpolygon can also identify points on the polygon borders.

7. AliReza KashaniPour replied on February 21st, 2007 at 17:26 UTC :
   

   http://www.sharemation.com/naarkhoo/max.jpg?uniq=yut6jo
   Steve … i draw my think …
   NOW YOU SEE WHAT i MEANT tanx

8. Steve replied on February 23rd, 2007 at 08:25 UTC :
   

   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.

9. David Lee replied on April 17th, 2007 at 09:15 UTC :
   

   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.

10. Steve replied on April 18th, 2007 at 17:06 UTC :
    

    David - Thanks for your input.

11. Ruthy replied on September 25th, 2008 at 04:21 UTC :
    

    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

12. Steve replied on September 25th, 2008 at 06:21 UTC :
    

    Ruthy—I’m not sure what you mean by “a mask containing subpixel coordinates.”

13. Ruthy replied on November 11th, 2008 at 13:17 UTC :
    

    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

14. Steve replied on November 11th, 2008 at 16:35 UTC :
    

    Ruthy—Thanks for the suggested application.

Leave a Reply

<pre class="code">
a = magic(3);
sum(a)
</pre>

These postings are the author's and don't necessarily represent the opinions of The MathWorks.