allan@didsgn.uucp (didsgn) (10/14/89)
MARWK@levels.sait.edu.au writes: >In article <Oct5.1989.5868@didsgn.uucp>, allan@didsgn.uucp (didsgn) writes: >> I forward the details to anyone interested. >Please post it. >Ray I posted this once, but our system seems to be having some problems. I hope this post reaches you (in other words, those not here please call out you name :-). If this is a duplicate at your site, then consider this a fault-tolerant posting. Below is a verbal description of the algorithm. -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!allan