How to Calculate area of partial pixels in a square image cut off by a circle ?

I have a square 11x11cm image, and a circle of diameter 10cm inscribed inside the square, resulting in partial pixels at the boundary of the circle. The values contained in each pixels need to be normalized by area, which would be 1cm2 for the complete pixels, however the area of edge pixels will be lower than 1.

How do I calculate the area of each of these partial pixels ?

Answer 1

[Amos]

You could randomly define a large number of points inside each pixel and then check for each of the points, if it is inside the circle or not. The fraction of the area inside the circle can then be approximated by the fraction of points iside the circle compared to the total number of points in the pixel.

If a certain pixel is specified by the edge points [x1,x2], [y1,y2] and your circle is specified by the center [xm,ym] and radius r, the code could looke like

N=1000;
xi = rand(N,1)*(x2-x1)+x1;
yi = rand(N,1)*(y2-y1)+y1;
distance2 = (xi-xm).^2 + (yi-ym).^2;
area_fraction_estimate = sum(distance2<r^2)/N

[Jainil]

That is exactly what I had in mind. Except I was thinking to sub-pixelize each 1x1cm pixel into 100s of pixels and then count the ones that lie within the circle. Which is essentially the same thing, except yours is simpler ! Thanks a lot !

[Image Analyst]

That's not what you told me. You said that each 1-by-1 region was one single pixel, not hundreds of them. So, which is is? Also note that Amos's code does not give you "the area of each of these partial pixels" which you asked for - it gives you the area fraction of the entire circle (area of circle divided by area of bounding box) which is quite a different thing.

[Mohammad Abouali]

I would play a bit with N (increasing it) to make sure that I am getting proper answer. In these sort of approach (Monte Carlo) The accuracy depends on how many random points you generate.

[Amos]

Jainil: yes, subdividing the pixel into a regular grid would be the alternative. I don't know what are the pros and cons of regular vs. random. In either case, I would agree to Mahammad that one should make sure the discretization/number of random points is sufficient.

Answer 2

[Image Analyst]

You would have to model your space as a grid of "tiles" or squares of some finite size. Then you have to place your circle over it. For example, does the center of your circle lie in the middle of a square pixel, on the edge between two pixels, or somewhere between the edge and the center. It makes a difference and you'll get different answers depending on how the tiles lie on top of your circle. How big are the pixels in your model? One cm by one cm? 0.01 cm by 0.01 cm? Something else?

[Jainil]

The center of the circle is in the middle of the pixel.. Specifically pixel (6,6). Yes, the pixels are 1x1cm. I already got to the the placing the circle on a grid of 11x11 squares part. I'm having difficulty now estimating the cut off pixels. There's no direct / simple way to do it.

Answer 3

[John D'Errico]

This is easier than you are making it out to be. You need to know the fractional area of a square that lies inside of a circle. From what you have said, you don't need it to be perfect, accurate to within machine epsilon. And a nice thing is, the square is small with respect to the radius of the circle. So we don't need to worry about too many strange things happening.

To a large extent, a circle cuts one of these pixels if one or more of the vertices is inside the circle, AND if one or more vertices is outside. Since you have told us the center of the circle lies at the center of one pixel, there may be either zero or four additional squares that are cut by the circle, where only an edge of the circle was cut, but no vertices of the square were inside the circle.

I'd just look for pixels that are crossed by the circular arc. Within these square pixels, approximate the arc by many small linear segments, and create a polygon that defines the region that lies inside both the square AND the circle. Then use POLYAREA to evaluate the area of the transected pixel. Essentially, this is a trapezoidal rule approximation for the area. It will be quite efficient, and quite accurate if you use enough points. And you can use a sufficient number of points for it to be as accurate as you need it to be.

If you were an extreme perfectionist (me!) compute the area using the above scheme, then cut each segment of the circular arc passing through the square into two pieces. This will give you two estimates of the area. Then use Richardson extrapolation to give you a higher order approximation to that area. This will be quite accurate. In fact, we could have doubled the number of arc segments through the square a second or even a time, giving us a multi-level Richardson extrapolant.

Done correctly, that tiered Richardson extrapolant could easily be done in a way that would in fact give you an estimate of the area that was in fact accurate to within nearly machine epsilon.

[Image Analyst]

Here is a general example of what I'm envisioning that he's asking:

and for each square (pixel) that gets crossed by the blue perimeter line, he wants to know the area that is inside the blue circle .

He says "The center of the circle is in the middle of the pixel." so that would mean he has this situation:

Can't this be solved analytically just using geometric equations?

[John D'Errico]

Actually, I interpreted the words which stated that the center of the circle would be in the middle of a pixel to say the circle was centered at the center of one of those square pixels. So I had a different interpretation than did you.

The reason I chose my interpretation, is each pixel is being viewed as a square, that then has its area computed. So when he says "The center of the circle is in the middle of the pixel", to me, that means the circle is not centered at one of the corner vertices of that grid of pixels, but at the center of one of them.

As for your question, can this be solved analytically, I am quite sure that it can. HOWEVER, any such solution must depend on how many edges, and which edges, are cut by the circle!

For example, I could with some effort, probably come up with an analytical solution to the area contained inside a "triangle", one arc of which is actually a circular arc. But that is only one case of many here. That circular arc can cut through a square in many ways, and each possible set of intersections would require a distinct analytical solution.

This is why I suggested use of polyarea to solve the problem, which is equivalent to trapezoidal rule. Then, by layering several tiers of trapezoidal rules, we could use Richardson extrapolation to compute the area to within machine precision, if done with proper care. And who cares how you get a result that is accurate to within machine precision?

[Image Analyst]

You're right - I wrote the code wrong and believe as you do, like below: