allan@didsgn.uucp (didsgn) (10/10/89)
Back in 1982 I wrote an algorithm which computed the area of a region
in image memory. Side benefits included returning the length of the
perimeter. Below is a description of the algorithm. If more details
are needed, please call me.
-Allan G. Schrum
Allan G. Schrum | Sign it? Without reading the fine print?
Digital Design, Inc. |-----------------------------------------
3060 Business Park Drive | (404) 447-0274
Norcross, GA 30071 | ...!gatech!rebel!didsgn!allan
This document describes the basic idea behind a routine to determine
the area and/or perimeter of any object in an image array. The outputs
are such that you can determine if the object being examined is a hole
or the actual object. The length of time for the calculation of area or
perimeter depends upon the perimeter of the object.
The basic idea is to first treat a pixel as a four sided square with
each side being of unit length. Thus a single pixel on has an area of 1
and a perimeter of 4; two pixels side-by-side have an area of two and a
perimeter of 6; two pixels connected diagonally (8-connected) have an
area of two and a perimeter of 8, etc. From this point, the idea is to
trace the perimeter of the object and from this perimeter determine the
internal area encompassed by this perimeter.
Since we are treating each side of a pixel as a unique object, the
algorithm that performs the trace will do the same. To start the
algorithm, one must find an edge of the object to start the trace from.
Pick one of the exterior sides of the pixel as an arbitrary starting
point. This is our (0,0) location. The calculations are quite simple.
We trace the perimeter of the object by looking for the next edge that
makes up the perimeter. There are three conditions: either a right turn
is needed, or no turn (straight ahead), or a left turn.
Let's start back at the point which we marked as our arbitrary starting
location of (0,0). Let's assume that the edge of the pixel found is a
horizontal edge. We need to keep track of how far away, horizontally,
from the (0,0) position we have traveled while following the perimeter.
Each time we move horizontally, we add one to the variable keeping
track of our horizontal distance. If we move to the "right", we add
one; if we move to the "left", we subtract one. Each time we move
vertically we add our distance variable to the current area count. Each
time we move "up", we add our distance variable to the area count; each
time we move "down", we subtract our distance variable to the area
count. This process continues until you return back to the original
starting location.
If the resulting area is negative, then the algorithm traced a hole and
the area is the negative of what the hole encapsulates; if the area is
positive, you have traced an object whose area is that number.
The perimeter is a side benefit and is easily counted during this
process.
If the object has any "holes" within it, these are not seen by the
algorithm. Thus the area of a donut will be the same as the area of a
circle of the same exterior size (assuming we are calculating the area
of the donut from the outside and not from the donut's hole).
One trick to keeping things sane is to treat the left-hand side of a
pixel's edge as the "anchor" or (0,0) location of the object. This
assumes that the algorithm is "standing" on the outside looking at the
object.
Another side benefit is that if you keep track of horizontal and
vertical moves seperately, you can scale the perimeter to give
arbitrary scaling of the results.
If you are interested in determining the lengths of lines, this same
algorithm works. However, keep track of when a diagonal move took place
(i.e. a left-hand or right-hand turn was made) as well as seperate
horizontal and vertical movements. The length is just the sum of the
horizontal, vertical and the adjusted diagonal moves all divided by two
(remember that you went up one side and down the other). The adjustment
to the diagonal moves is typically multiplying by the square-root of 2.
Line length calculation lends itself for scaling very easily as all
three aspects of a line are known (horizontal, vertical and diagonal
displacements). Area scaling is trivial since the area is in terms of
the basic units: determine the scaling factor from a basic unit to a
unit area in the scaled space and multiply.
The implementation is much simpler that the description. It is usually
2 "peeks" into the image plane followed by a small case statement to do
the calculations. If I am energetic enough (or there is sufficient
demand) I can make and then provide a C code example.
--
Allan G. Schrum | Sign it? Without reading the fine print?
Digital Design, Inc. |-----------------------------------------
3060 Business Park Drive | (404) 447-0274
Norcross, GA 30071 | ...!gatech!rebel!didsgn!allaningoldsb@ctycal.UUCP (Terry Ingoldsby) (10/19/89)
Thanks to all who posted/mailed suggestions. They were most
helpful, and I can see where each technique proposed would be
useful in a given circumstance.
The method we are using is Newell's formula (suggested by many)
to calculate the area of the straight sided polygon. To handle
the arcs, we use Ken Shiriff's suggestion of determining
whether to add or subtract a chorded arc area
based on the sign of the vector cross product. Once the chorded
areas are added or subtracted, the absolute value of the total is
the correct area in all cases.
By the way, the reason we got into this is because some 3rd party
software we purchased was getting the wrong answer. Not only
does the technique outlined above give the right answer, it is
20 times faster than the 3rd party stuff. Moral of the story:
if you want it done right, do it yourself!
--
Terry Ingoldsby ctycal!ingoldsb@calgary.UUCP
Land Information Systems or
The City of Calgary ...{alberta,ubc-cs,utai}!calgary!ctycal!ingoldsb