Number of pixels covered by an oval.

Question

I have a raster image with an oval inscribed in a rectangle with a given width and height (in pixels). I need an efficient (ultra-high resolution picture) algorithm to compute the exact number of pixels in the image. Currently I am dividing the rectangle into four parts, iterating over pixels in one of them and multiplying the result by 4, roughly speaking:

pixelCount = 0
frontier = width
newFrontier = frontier
For y in [0 .. height]
  For x in [0 .. frontier]
    If InsideOval(x, y)
      newFrontier = MIN(x, newFrontier)
      pixelCount += height – y
      If x == frontier-1
        frontier = newFrontier
pixelCount *= 4

Is there a more efficient way of doing it? There must be geometric formula... right?

Answer 1

I doubt it exists a geometric formula for that. The number of pixels depends on screen resolution and on the algorithm used for rasterization. As it happen with line rasterization in which Bresenham algorithm gives a different rasterization than DDA algorithm, that would happen with ellipses.

See for instance the different algorithms for rasterizing antialiased ellipses:

http://create.stephan-brumme.com/antialiased-circle/

Also a geometric formula should be rotation invariant while rasterization varies with rotation. Discrete is harder than continuous.

Answer 2

This is not a math question, it is a programming question.

Let's call the pixels to be counted "inside", and the others "outside".

If and all inside pixels are in a single continuous run on each horizontal scan line, then it suffices to calculate the number of continuous outside pixels on each scan line from left and right edges. Perhaps the following illustration helps:

⇨ ⇨ ⇨ ⇨ ⇨ ⇨ ⇨ ⇨ ⇨ X ⇦ ⇦ ⇦ ⇦ ⇦ ⇦ ⇦ ⇦ ⇦
⇨ ⇨ ⇨ ⇨ X X X X X X X ⇦ ⇦ ⇦ ⇦ ⇦ ⇦ ⇦ ⇦
⇨ ⇨ ⇨ X X X X X X X X X X X X ⇦ ⇦ ⇦ ⇦
⇨ ⇨ X X X X X X X X X X X X X X X X ⇦
X X X X X X X X X X X X X X X X X X X
: : : : : : : : : : : : : : : : : : :
X X X X X X X X X X X X X X X X X X X
⇨ X X X X X X X X X X X X X X X X X X
⇨ ⇨ ⇨ X X X X X X X X X X X X X X X ⇦

The function calculates the number of arrows, and returns the total number of pixels in the rectangular area considered, minus the number of arrows, as the number of X's in the image.

In pseudocode:

Function CountInside(IsInside[HEIGHT][WIDTH]):

    # N will be the number of "outside" pixels
    Let N = 0

    For y = 0 to HEIGHT-1:

        # Count the run of outside pixels from left:
        Let xmin = 0
        While (xmin < WIDTH) and (NOT IsInside[y][xmin]):
            xmin++
            N++
        End While

        # Count the run of outside pixels from right:
        If (xmin < WIDTH):
            Let xmax = WIDTH-1
            While (NOT IsInside[y][xmax]):
                xmax--
                N++
            End While
        End If

    End For

    Return WIDTH*HEIGHT - N
End Function

Note that this only accesses N + 2*HEIGHT pixels, so the runtime is dominated by the number of pixels "outside". On typical architectures (like x86 and x86-64), RAM access is the limiting bottleneck.

For cache locality, you'll want to ensure the innermost while loops access data consecutively in memory. If the array is in row-major order like it would be in C, then the above function accesses image pixels consecutively.

If HEIGHT is very large, and you know that the "inside" pixels are in a continuous run both horizontally and vertically (as they are for convex shapes like circles, ovals, squares, and triangles), you can speed the function by skipping the set of horizontal scan lines with all pixels "inside". In pseudocode:

Function CountInside(IsInside[HEIGHT][WIDTH]):

    # N will be the number of "outside" pixels
    Let N = 0
    Let y = 0

    While (y < HEIGHT):

        # Count the run of outside pixels from left:
        Let xmin = 0
        While (xmin < WIDTH) AND (NOT IsInside[y][xmin]):
            xmin++
            N++
        End While

        Let xmax = WIDTH-1
        If (xmin < WIDTH):
            # Count the run of outside pixels from right:
            While (NOT IsInside[y][xmax]):
                xmax--
                N++
            End While
        End If

        If (xmin == 0) AND (xmax == WIDTH-1):
            Break out of While loop
        Else:
            y++
        End If
    End While

    If (y < HEIGHT):
        Let ymin = y
        Let y = HEIGHT - 1

        While (y >= ymin):

            # Count the run of outside pixels from left:
            Let xmin = 0
            While (xmin < WIDTH) AND (NOT IsInside[y][xmin]):
                xmin++
                N++
            End While

            # Count the run of outside pixels from right:
            Let xmax = WIDTH-1
            If (xmin < WIDTH):
                While (NOT IsInside[y][xmax]):
                    xmax--
                    N++
                End While
            End If

            If (xmin == 0) AND (xmax == WIDTH-1):
                Break out of While loop
            Else:
                y--
            End If
        End While

    End If

    Return WIDTH*HEIGHT - N
End Function

The difference between these two versions is that this latter version checks the left and right edges of the pixel array from top down to the first row that starts and ends with X, and from bottom up to the last row that starts and ends with X. The lines marked with : indicate full rows of pixels, and are skipped in this latter version.

Both functions assume that each horizontal scan line has at least one inside pixel. If not, you'll need to add additional checking to the inner while loops, so they won't over/underrun the array.

If you know the shape to be symmetric (regardless of whether the width and height is odd or even), you can simply do the above to the upper left corner, and return WIDTH*HEIGHT - 4*N. I personally would not do this; I consider the extra run time well worth the robustness.