Graphics apparatus and method.

The present invention relates generally to closed contour object characterization, and more particularly to the isolation and classification of closed contour objects using convex-polygon bounding structures.

It is sometimes convenient to isolate and characterize objects in two dimensional and three dimensional space by enclosing them within a defined polygon (or polyhedron in 3D) whose size and shape provide information about the objects they enclose. For example, bounding polygons can be used to distinguish the components of an array of objects and determine rough approximations of their shape. Specific applications in which polygon bounding has proven useful include pattern recognition, in the case of two dimensional objects, and virtual imaging in the case of objects defined in three dimensional space.

In the field of pattern recognition, a convex-polygon bounding method has been proposed by K. Yamamoto et al, Recognition of Hand-Printed Characters By An Outermost Method, Pattern Recognition, Vol. 12, pp. 229-236 (1980). The Yamamoto et al method approximates the convex hull of a discrete set of points. Approximate convex hull structures are generated by identifying, in the object to be bounded, a series of "outermost" contour points. Those points are sequentially connected to form the sides of the bounding polygon. For example, the letter "A" might be bounded by a polygon having a short horizontal upper side, a long horizontal lower side, and a pair of slanted intermediate sides.

Each side of the polygon so generated is inherently oriented at some angular rotation with respect to a fixed frame of reference. The angular rotations are determined solely by the positions of the contour points, which in turn are determined by the shape of the closed contour to be bounded. Thus, in the prior method, the angular rotations of the polygon sides, and even the number of sides, typically differ from polygon to polygon when different contours are considered. For example, the sides of a polygon constructed to bound the letter "A" would generally be fewer in number and have different angular rotations than a polygon bounding the letter "B". Polygons generated for different contours in accordance with the Yamamoto et al method therefore have few, if any, characteristics in common, and cannot be easily compared.

It is submitted that contour analysis could be significantly improved using convex-polygons having common characteristics, such as a predetermined number of sides and uniform rotational characteristics. In that way, information such as polygon size with respect to selected angular rotations could be easily compared relative to a plurality of polygons, regardless of the shapes of the bounded contours. It would be further desirable to provide a method for generating such convex-polygons in an efficient manner using minimal processing resources. For example, in known character recognition systems, closed contours are detected during one pass over a binary image array representation. It would be convenient to obtain at the same time a convex-polygon bound on that contour. This would simplify classification of the object represented, as well as the computation of intersections, point membership and other topological relations.

What is needed, therefore, is a class of bounding polygons allowing computational advantages that are inherent in their geometrical characteristics, as well as a fast method for generating such polygons as an extension to the classical one-pass algorithm for finding connected components in binary images.

Accordingly viewed from one aspect the present invention provides a data processing system including a character bounding system for evaluating closed contour images of objects, comprising: a central processing unit; a data input system for inputing data representing objects to be evaluated; a data output system; one or more data storage resources; means for generating a binary array representation of one or more closed contour objects to be evaluated with respect to a reference coordinate system; and means for generating from said binary array representation one or more convex-polygon representations of said objects of a form that includes a set of polygon bands oriented relative to said reference coordinate system and to generally uniform angular rotations of said reference coordinate system, said bands defining the contour bounds of the closed contour objects with respect to each rotation of said reference coordinate system.

Viewed from another aspect the present invention provides a method for convex-polygon bounding of closed contour images in a data processing system comprising the steps of: inputing data representing an image to be evaluated; generating a binary array representation of a closed contour input image relative to a reference coordinate system; and generating, in a single pass through said binary array, a data output structure defining the contour bounds of said input image relative to successive, generally uniform rotations of said reference coordinate system.

The apparatus and computer-implemented polygon bounding method generate, in a first step, a binary array representation of a closed contour input object relative to a reference coordinate system. Subsequently, in a single pass through the binary array, a bounding polygon is generated as a sequence of parallel "bands," each representing a pair of opposing sides of the polygon. The polygon bands are oriented at successive generally uniform rotations of the reference coordinate system and are positioned to define the bounds of the closed contour for each rotation angle. The spacing and positioning of the bands can thus be used to define polygon size and position at each angle. In this way, comparisons between a plurality of polygons can be made systematically using defined geometrical criteria.

In a preferred aspect of the invention, each polygon band pair is defined by a pair of contour bounding displacements. The contour bounding displacements represent minimum and maximum contour distance values with respect to a selected axis (e.g. the horizontal "x" axis) of the reference coordinate system, as it is positioned through each angle of rotation. Advantageously, the contour bounding displacements at each rotation angle can be determined by mapping the contour displacement values into the coordinate system at that angle. Contour point displacements (interval end points) are determined for each row of the input array, for each rotation angle. Global minimum and maximum displacements for each rotation angle are found by replacing the largest value found at a given angle by the next value computed, if that next value is still larger. The final minimum and maximum for each angle are stored in an output table.

In still another aspect of the invention, the mapping procedure is performed by selecting rotation angle approximation values representing rational tangents of the form m_Θ/n_Θ, wherein successive m_Θ and successive n_Θ values differ by at most 1. This facilitates determination of the contour displacement, for each rotation angle, by simply incrementing and decrementing the reference system displacements in accordance with a predetermined sequence over the range of angles.

In order that the invention may be fully understood preferred embodiments thereof will now be described, by way of example only, with reference to the accompanying drawings in which: <ul id="ul0001" list-style="none"><li>Fig. 1 is a block diagram showing a data processing system constructed in accordance with the present invention;</li><li>Fig. 2 is a flow diagram showing a preferred method in accordance with the present invention;</li><li>Fig. 3a is a diagrammatic illustration of a document image containing a closed contour object;</li><li>Fig. 3b is a diagrammatic illustration of a binary array representation of the document image showing a reference coordinate system relative thereto together with selected incremental rotations of the reference coordinate system (shown in phantom), and further showing minimum and maximum contour bounding displacements relative to selected rotations of the reference coordinate system;</li><li>Fig. 4 is a diagrammatic illustration of an interval table generated in accordance with the present invention;</li><li>Fig. 5 is a flow diagram showing a fast computational method for performing contour point interval mapping; and</li><li>Fig. 6 is a detailed diagrammatic illustration of a binary array representation of a closed contour image showing a relationship between minimum and maximum contour displacement values in successive scan lines warranting a termination of further rotational processing for the first of the illustrated scan line pair.</li></ul>

Turning now to Fig. 1, a character bounding system for evaluating closed contour images in accordance with a preferred embodiment of the invention is constructed from a data processing apparatus 10. The data processing apparatus 10 includes a processing unit 12, a data input system 14 for the input of data as well as command and control information, a data output system 16, and one or more data storage resources 18. The processing unit 12 includes a plurality of storage register locations 20 as well as local program memory 22 for storing and processing instructions from a compiled computer program 24. The data processing apparatus 10 may be constructed from any number of programmable general purpose computers and data processing systems. Preferably, the apparatus includes a document scanner as part of the data input system 14, or some other mechanism for inputting data files representing input images. The data processing apparatus 10 is configured to perform the method of the present invention using a software program written in the well-known "C" programming language, although it will be understood that many other programming languages could be used to generate a suitable instruction set.

CONSTRUCTION

Referring now to Fig. 2, a method for generating closed contour bounding polygons is shown diagrammatically. In a first process step 30, an input graphics image 32, as shown in Fig. 3a, having a closed contour, is converted using a document image scanner of the data input system 14, to a binary array representation 34, as shown in Fig. 3b. The binary array representation 34 is a data structure defining a plurality of array locations arranged in a series of rows and columns relative to a reference coordinate system 36. By convention, array locations having a value of 1 are assumed to identify darkened portions of the closed contour image, while array locations having 0's represent undarkened portions of the scanned image. As an alternative to scanning, a previously generated array representation 34 could be input to the data processing apparatus 10 as a data file by conventional file handling methods.

The preferred method for generating a bounding polygon representation of the closed contour input image 32, is to scan the binary array representation 34 in a line-by-line (row-by-row) sequence in the direction of the "y" axis of the reference coordinate system 36. The closed contour portion of the array 34 is defined for each scan line, by an interval of "x" coordinate values, including a minimum interval endpoint value "x_l" on the left side of the contour and a maximum interval endpoint value "x_r" on the right side of the contour. The entire closed contour is thus represented in the reference coordinate system as a sequence of such intervals, [x_l(y), x_r(y)], where y ranges between the first scan line of the contour, y_b (bottom), and the line at which the contour closes, y_t (top).

If only a rudimentary polygon is desired, such as a bounding rectangle, the reference coordinate system scan interval sequence may be used directly. In a bounding rectangle, for example, the left side is min{x_l(y)}, the right side is max{x_r(y)}, and the bottom and top are y_b and y_t, respectively. A disadvantage of bounding rectangles and other simple shapes is that they are of limited use for object classification, and for determining the actual proximity of plural closed contour objects. That is because the bounding rectangle is generally a poor approximation of the contour. Thus, in order to improve object classification and proximity determination, the notion of a bounding rectangle must be generalized to that of a bounding convex polygon consisting of an arbitrary fixed number of pairs of opposite parallel sides, instead of just two such pairs. This requires that the bounds of the object be computed along multiple fixed directions in a plane.

As shown in Fig. 3b, it is desired to construct a convex polygon having opposing sides or bands at generally uniform incremental rotations of the reference coordinate system 36. This is done by mapping the scanline interval end displacement values from the reference coordinate system through a sequence of angular rotations. Because the bounds on a contour at an angle Θ are also the bounds at Θ + π, the rotational domain can be restricted to 0 ≦ Θ &lt; π. It is assumed that x_l(y,Θ) and x_r(y,Θ) are the minimum/maximum limits of a scan interval of the reference coordinate system 36, rotated by angle Θ. The coordinate system 36 is assumed to have its origin at the lower left hand corner of the image. To maintain consistency, y_b becomes x_r and y_t becomes x_l under a rotation left by π/2, with the mapping changed accordingly for a right rotation.

Referring now to Fig. 2, the first step in the polygon construction process following input of the array 34 is to initialize in process step 38 an interval table 40, as shown in Fig. 4. The interval table 40 is a data output structure that defines for each angular rotation of the reference coordinate system 36, the global minimum and maximum contour bounding intervals x_l(y,Θ), x_r(y,Θ), and the scanline y on which they are found. The interval table 40 thus provides the output representation of the constructed bounding polygon. Following initialization of the interval table 40, a first line of the input array 34 is scanned in process step 42 and a contour bounding interval x_l(y_n,Θ_n) and x_r(y_n,Θ_n) is determined for the reference coordinate system 36 (Θ_n = 0) in process step 44. In process step 46, the left and right bounding interval displacements x_l(y_n,Θ_n) and x_r(y_n,Θ_n) are separately compared against the corresponding Θ_n entries for the previous scanline (if any) in the interval table 40 (i.e.,x_l(y_n-1,Θ), x_r(y_n-1,Θ) . If one or both are larger, they are stored as a new local minimum, maximum bounding interval at Θ_n. In process step 48, the coordinate system rotation is implemented by mapping the interval values x_l(y,Θ_n), x_r(y,Θ_n) to the next rotation angle Θ_n+1. In step 50, the process returns to step 44 to determine the next left and right interval displacements x_l(y,Θ_n+1), x_r(y,Θ_n+1). Process steps 44-50 are repeated until the selected angular range e.g. 0 ≦ Θ ≦ π, is covered. In process step 52, the process returns to step 42 and the next scanline is considered. Process steps 42-52 are repeated until the array is fully scanned.

FAST COMPUTATION

For each angle Θ representing a rotation of the coordinate system, the global minimum and maximum contour bounding displacement values are represented by the bounds [l_Θ,r_Θ], where (1)<maths id="math0001" num=""><math display="block"><mrow><msub><mrow><mtext>1</mtext></mrow><mrow><mtext>ϑ</mtext></mrow></msub><msubsup><mrow><mtext> = </mtext></mrow><mrow><mtext mathvariant="italic">y</mtext></mrow><mrow><mtext>min</mtext></mrow></msubsup><mtext>{</mtext><mtext mathvariant="italic">x</mtext><mtext>₁(</mtext><mtext mathvariant="italic">y</mtext><mtext>,ϑ)},</mtext></mrow></math><img file="EP0617375A2_D0001.tif" /></maths><maths id="math0002" num=""><math display="block"><mrow><msub><mrow><mtext mathvariant="italic">r</mtext></mrow><mrow><mtext>ϑ</mtext></mrow></msub><msubsup><mrow><mtext> = </mtext></mrow><mrow><mtext mathvariant="italic">y</mtext></mrow><mrow><mtext>max</mtext></mrow></msubsup><mtext>{</mtext><msub><mrow><mtext mathvariant="italic">x</mtext></mrow><mrow><mtext>r</mtext></mrow></msub><mtext>(</mtext><mtext mathvariant="italic">y</mtext><mtext>,ϑ)}.</mtext></mrow></math><img file="EP0617375A2_D0002.tif" /></maths>

Using simple geometry, the x-displacement of a reference system coordinate point (x,y) with respect to axes rotated by an angle Θ is (2)<maths id="math0003" num=""><math display="block"><mrow><msub><mrow><mtext mathvariant="italic">x</mtext></mrow><mrow><mtext>ϑ</mtext></mrow></msub><mtext> = </mtext><mtext mathvariant="italic">x</mtext><mtext>cosϑ + </mtext><mtext mathvariant="italic">y</mtext><mtext>sinϑ.</mtext></mrow></math><img file="EP0617375A2_D0003.tif" /></maths>

It is preferred to compute equation (2) with integer operations. To do so, the rotational angle Θ is first approximated by an angle having a rational tangent, mΘ/nΘ, where the improper expression for the tangent at π/2 is freely written as a shorthand for the corresponding sine/cosine pair. Equation (2) can now be written in the form (3)<maths id="math0004" num=""><math display="block"><mrow><msub><mrow><mtext mathvariant="italic">x</mtext></mrow><mrow><mtext>ϑ</mtext></mrow></msub><mtext> = </mtext><mfrac><mrow><mtext>1</mtext></mrow><mrow><msqrt><msubsup><mrow><mtext mathvariant="italic">m</mtext></mrow><mrow><mtext>ϑ</mtext></mrow><mrow><mtext>2</mtext></mrow></msubsup><mtext> + </mtext><msubsup><mrow><mtext mathvariant="italic">n</mtext></mrow><mrow><mtext>ϑ</mtext></mrow><mrow><mtext>2</mtext></mrow></msubsup></msqrt></mrow></mfrac><mtext> (</mtext><msub><mrow><mtext mathvariant="italic">n</mtext></mrow><mrow><mtext>ϑ</mtext></mrow></msub><mtext mathvariant="italic">x</mtext><mtext>+</mtext><msub><mrow><mtext mathvariant="italic">m</mtext></mrow><mrow><mtext>ϑ</mtext></mrow></msub><mtext mathvariant="italic">y</mtext><mtext>).</mtext></mrow></math><img file="EP0617375A2_D0004.tif" /></maths>

The second step in converting equation (2) to an integer computation is based on the observation that computing the minimum and maximum interval values in equation (1) requires only comparison operations, so that the values in equation (3) may be scaled for convenience. Delaying multiplication by the (generally irrational) factor<maths id="math0005" num=""><math display="block"><mrow><msub><mrow><mtext mathvariant="italic">s</mtext></mrow><mrow><mtext>ϑ</mtext></mrow></msub><mtext> = </mtext><mfrac><mrow><mtext>1</mtext></mrow><mrow><msqrt><msubsup><mrow><mtext mathvariant="italic">m</mtext></mrow><mrow><mtext>ϑ</mtext></mrow><mrow><mtext>2</mtext></mrow></msubsup><mtext> + </mtext><msubsup><mrow><mtext mathvariant="italic">n</mtext></mrow><mrow><mtext>ϑ</mtext></mrow><mrow><mtext>2</mtext></mrow></msubsup></msqrt></mrow></mfrac><mtext>,</mtext></mrow></math><img file="EP0617375A2_D0005.tif" /></maths> equation (1) becomes (4)<maths id="math0006" num=""><math display="block"><mrow><msub><mrow><mtext>1</mtext></mrow><mrow><mtext>ϑ</mtext></mrow></msub><mtext> = </mtext><msub><mrow><mtext mathvariant="italic">s</mtext></mrow><mrow><mtext>ϑ</mtext></mrow></msub><msubsup><mrow><mtext>​</mtext></mrow><mrow><mtext mathvariant="italic">y</mtext></mrow><mrow><mtext>min</mtext></mrow></msubsup><mtext>{</mtext><msub><mrow><mtext mathvariant="italic">n</mtext></mrow><mrow><mtext>ϑ</mtext></mrow></msub><mtext mathvariant="italic">x</mtext><mtext>₁ (</mtext><mtext mathvariant="italic">y</mtext><mtext>) +</mtext><msub><mrow><mtext mathvariant="italic">m</mtext></mrow><mrow><mtext>ϑ</mtext></mrow></msub><mtext mathvariant="italic">y</mtext><mtext>},</mtext></mrow></math><img file="EP0617375A2_D0006.tif" /></maths><maths id="math0007" num=""><math display="block"><mrow><msub><mrow><mtext mathvariant="italic">r</mtext></mrow><mrow><mtext>ϑ</mtext></mrow></msub><mtext> = </mtext><msub><mrow><mtext mathvariant="italic">s</mtext></mrow><mrow><mtext>ϑ</mtext></mrow></msub><msubsup><mrow><mtext>​</mtext></mrow><mrow><mtext mathvariant="italic">y</mtext></mrow><mrow><mtext>max</mtext></mrow></msubsup><mtext>{</mtext><msub><mrow><mtext mathvariant="italic">n</mtext></mrow><mrow><mtext>ϑ</mtext></mrow></msub><msub><mrow><mtext mathvariant="italic">x</mtext></mrow><mrow><mtext mathvariant="italic">r</mtext></mrow></msub><mtext>(</mtext><mtext mathvariant="italic">y</mtext><mtext>) +</mtext><msub><mrow><mtext mathvariant="italic">m</mtext></mrow><mrow><mtext>ϑ</mtext></mrow></msub><mtext mathvariant="italic">y</mtext><mtext>},</mtext></mrow></math><img file="EP0617375A2_D0007.tif" /></maths> where the final products are rounded to the nearest integer. An alternative approach is to omit multiplication by the scale factor s_Θ at this point, leaving the intervals in proportional units and performing inverse transformations on other data as required. Although a case can be made for this alternative in some application environments, the multiplication is indicated here in order to simplify later notation.

Because application of the constant factor s_ϑ is delayed in calculating equation (4), exact integer computation of the (proportional) displacement at Θ involves at most three multiplies. This allows the implementation of fast computation methods, such as limiting m/n to direct or inverse powers of two, or using multiplication tables when the coordinate range is reasonably small.

In order to maintain rotational invariance, at least to the accuracy afforded by the number of angles chosen, the angles would ideally be spaced equally. But then the integer values comprising the approximating rational tangents will not have properties that would allow a reduction in the number of multiplication operations in equation (4). Instead, a set of angles is chosen whose tangents have convenient computational properties, while introducing an acceptably small error in the even distribution of angles. To divide the range 0 ≦ Θ ≦ π into 2ⁿ⁺² parts, the following sequence of m_Θ/n_Θ tangents may be used: (5)<maths id="math0008" num=""><img file="EP0617375A2_D0008.tif" /></maths> In this sequence of tangents, m_Θ runs through the numerators while n_Θ runs through the denominators. Since successive elements of these sequences differ by at most one, it requires at most an addition to form a product in equation (4) for a given tangent as a function of the corresponding product for the previous tangent. The initial value 2ⁿ is generally constant for the entire computation. Using this scheme to generate 32-sided polygons, the maximum error in angular approximation occurs at π/16 and is .07 radian.

Fig. 5 illustrates a preferred fast computation method for performing the coordinate system rotation step 48 of Fig. 2. It is assumed that prior to implementation of the coordinate system rotation step 48, a sequence of rational tangents m_Θ/n_Θ, such as the sequence (5) above, has been selected. In a first series of coordinate system rotation steps 54-60, the equation (4) components n_Θx_l(y) and n_Θx_r(y) are computed using the initial n_Θ sequence value 2ⁿ. For a 32-sided polygon formed by 16 rotations of the reference coordinate system 36, the value of n is 2 such that there are 2ⁿ⁺² = 2⁴ = 16 rotations. The first n_Θ value is thus 2ⁿ = 2² = 4. The first m_Θ value is zero in accordance with sequence (5). To calculate n_Θx_l(y) where n_Θ = 2ⁿ, it is only necessary to shift the value x_l(y) n places. This can be efficiently performed by placing the value x_l(y) determined for the reference coordinate system in one of the processing unit shift registers 20 and performing n logical shift left operations. This operation is performed in process step 56 of Fig. 5. Similarly, to determine the equation component n_Θx_r(y) the reference system coordinate value x_r(y) is placed in a processing unit shift register 20 and a logical shift left operation is performed n times. This operation is performed in step 58 of Fig. 5. There are two logical shifts left in the case of a 32-sided polygon. The equation (4) value m_Θy, with the initial value m_Θ=0 is also equal to zero. Thus, for the first rotation angle, x_l(y,Θ) is equal to the calculated value nΘx_l(y), and x_r(y,Θ) is equal to the calculated value n_Θx_r(y). These values are returned in process step 60 as the bounding interval values x_l(y,Θ), x_r(y,Θ) in step 44.

If it is determined in step 54 that a first rotation has previously been made, the process jumps to step 62 where the values x_l(y,Θ) and x_r(y,Θ) are determined by simple addition operations over a range of m_Θ = 0 to 2ⁿ. Thus, following the first rotation using the m_Θ/n_Θ sequence value 0/2ⁿ, the next angular rotation employs the m_Θ/n_Θ sequence value 1/2ⁿ. Because the n_Θ denominator value remains the same, the only operation required to map this rotation is to add the value m_Θy to each of the previous x_l(y,Θ) and x_r(y,Θ) values. For m_Θ=1, the value m_Θy = y. For subsequent rotations, the value of m_Θ increases by 1. Thus, x_l(y,Θ) and x_r(y,Θ) at each subsequent rotation at which n_Θ = 2_n are determined by simply adding the value y to the previous x_l(y,Θ) and x_r(y,Θ) values. The condition m_Θ = 0 to 2ⁿ is tested in process step 62 and the mapped values x_l(y,Θ) and x_r(y,Θ) are returned in step 64 to the process step 44 as bounding intervals for each new rotation angle. Process steps 62 and 64 are repeated until m_Θ = 2ⁿ. At that point, the values x_l(y,Θ) and x_r(y,Θ) are determined by process steps 66 and 68. Process step 66 tests to determine that n_Θ is in a range between 2ⁿ and -2ⁿ. In this range, the value of n_Θ is sequentially decremented by 1 until n_Θ = -2ⁿ. The operation of decrementing the denominator n_Θ by 1 changes the values n_Θx_l(y) and n_Θx_r(y) by subtracting x_l and x_r, respectively, therefrom. The mapped values x_l(y,Θ) and x,(y,Θ) are returned in process step 68. The final sequence of rotations is mapped in process steps 70 and 72 by holding the denominator value n_Θ constant at -2ⁿ and decrementing the numerator value m_Θ from m_Θ = 2ⁿ to m_Θ=1 This sequence is achieved by subtracting y from the values x_l(y,Θ) and x_r(y,Θ), for each rotation. The mapped values are returned in process step 72.

Thus, the mapping operation is easily achieved by an initial logical shift left operation followed by successive addition and subtraction operations.

A second opportunity for implementation efficiencies arises from the fact that there are transition angles associated with the interval endpoints as the scan moves between successive lines. The values of Θ at which an interval endpoint minimum or maximum can change are determined by the transition angle of that endpoint when proceeding from line y to y+1. This function is expressed implicitly, for the left end, as<maths id="math0009" num=""><math display="block"><mrow><msub><mrow><mtext mathvariant="italic">n</mtext></mrow><mrow><mtext>ϑ</mtext></mrow></msub><mtext mathvariant="italic">x</mtext><mtext>₁(</mtext><mtext mathvariant="italic">y</mtext><mtext>+1) + </mtext><msub><mrow><mtext mathvariant="italic">m</mtext></mrow><mrow><mtext>ϑ</mtext></mrow></msub><mtext>(</mtext><mtext mathvariant="italic">y</mtext><mtext>+1) &lt; </mtext><msub><mrow><mtext mathvariant="italic">n</mtext></mrow><mrow><mtext>ϑ</mtext></mrow></msub><mtext mathvariant="italic">x</mtext><mtext>₁(</mtext><mtext mathvariant="italic">y</mtext><mtext>) + </mtext><msub><mrow><mtext mathvariant="italic">m</mtext></mrow><mrow><mtext>ϑ</mtext></mrow></msub><mtext mathvariant="italic">y</mtext><mtext>,</mtext></mrow></math><img file="EP0617375A2_D0009.tif" /></maths> and this reduces to (6)<maths id="math0010" num=""><math display="block"><mrow><mfrac><mrow><msub><mrow><mtext mathvariant="italic">m</mtext></mrow><mrow><mtext>ϑ</mtext></mrow></msub></mrow><mrow><msub><mrow><mtext mathvariant="italic">n</mtext></mrow><mrow><mtext>ϑ</mtext></mrow></msub></mrow></mfrac><mtext> &lt; </mtext><mtext mathvariant="italic">x</mtext><mtext>₁(</mtext><mtext mathvariant="italic">y</mtext><mtext>) - </mtext><mtext mathvariant="italic">x</mtext><mtext>₁(</mtext><mtext mathvariant="italic">y</mtext><mtext>+1).</mtext></mrow></math><img file="EP0617375A2_D0010.tif" /></maths> Similarly for the right end, (7)<maths id="math0011" num=""><math display="block"><mrow><mfrac><mrow><msub><mrow><mtext mathvariant="italic">m</mtext></mrow><mrow><mtext>ϑ</mtext></mrow></msub></mrow><mrow><msub><mrow><mtext mathvariant="italic">n</mtext></mrow><mrow><mtext>ϑ</mtext></mrow></msub></mrow></mfrac><mtext> &gt; </mtext><msub><mrow><mtext mathvariant="italic">x</mtext></mrow><mrow><mtext mathvariant="italic">r</mtext></mrow></msub><mtext>(</mtext><mtext mathvariant="italic">y</mtext><mtext>) - </mtext><msub><mrow><mtext mathvariant="italic">x</mtext></mrow><mrow><mtext mathvariant="italic">r</mtext></mrow></msub><mtext>(</mtext><mtext mathvariant="italic">y</mtext><mtext>+1).</mtext></mrow></math><img file="EP0617375A2_D0011.tif" /></maths> Process step 48 can be readily modified to test for these conditions so that coordinate system rotations that cannot yield a new interval endpoint minimum or maximum values are not tested. Fig. 5 illustrates the importance of transition angles in a case where the left interval end displacement increases by 1 from line y and y+1 and the right interval end displacement decreases by 1 from line y to y+1. Applying equation (6), there can be no change in the left endpoint and y+1 will not be a new maximum until m_Θ/n_Θ=-1. The right end point at y+1 will not be a new maximum until m_Θ/n_Θ=1.

TOPOLOGY

The term 'topology' is used in a general sense to refer to relationships between the above-described convex polygons which are set-oriented or metric in nature. Advantageously, it is not necessary to compute the actual polygon boundary in order to answer questions relating to comparative characteristics such as containment or proximity. Since the interior of the polygon is the intersection of bands, any such questions can be expressed equivalently as a conjunction of the same questions (or predicate) over the set of component bands.

A bounding polygon "A" of an object may be denoted by a set of bands {A_Θ}, where Θ ranges over the set of angles that are chosen, and where that set will be the same for all objects. Because bands are nothing more than intervals, there is an elementary calculus of bands at the same angle, equivalent to the calculus of intervals on the line. The left-hand and right-hand limits of a band A_Θ may be denoted by L(A_Θ) and R(A_Θ) respectively. The size of a band is then<maths id="math0012" num=""><math display="block"><mrow><mtext>|</mtext><msub><mrow><mtext mathvariant="italic">A</mtext></mrow><mrow><mtext>ϑ</mtext></mrow></msub><mtext>| = </mtext><mtext mathvariant="italic">R</mtext><mtext>(</mtext><msub><mrow><mtext mathvariant="italic">A</mtext></mrow><mrow><mtext>ϑ</mtext></mrow></msub><mtext>) - </mtext><mtext mathvariant="italic">L</mtext><mtext>(</mtext><msub><mrow><mtext mathvariant="italic">A</mtext></mrow><mrow><mtext>ϑ</mtext></mrow></msub><mtext>).</mtext></mrow></math><img file="EP0617375A2_D0012.tif" /></maths>

In order to measure the distance between two bands, and the definition<maths id="math0013" num=""><math display="block"><mrow><msub><mrow><mtext mathvariant="italic">A</mtext></mrow><mrow><mtext>ϑ</mtext></mrow></msub><mtext>⊖ </mtext><msub><mrow><mtext mathvariant="italic">B</mtext></mrow><mrow><mtext>ϑ</mtext></mrow></msub><mtext> = max (</mtext><mtext mathvariant="italic">L</mtext><mtext>(</mtext><msub><mrow><mtext mathvariant="italic">A</mtext></mrow><mrow><mtext>ϑ</mtext></mrow></msub><mtext>) - </mtext><mtext mathvariant="italic">R</mtext><mtext>(</mtext><msub><mrow><mtext mathvariant="italic">B</mtext></mrow><mrow><mtext>ϑ</mtext></mrow></msub><mtext>),</mtext><mtext mathvariant="italic">L</mtext><mtext>(</mtext><msub><mrow><mtext mathvariant="italic">B</mtext></mrow><mrow><mtext>ϑ</mtext></mrow></msub><mtext>) - </mtext><mtext mathvariant="italic">R</mtext><mtext>(</mtext><msub><mrow><mtext mathvariant="italic">A</mtext></mrow><mrow><mtext>ϑ</mtext></mrow></msub><mtext>)),</mtext></mrow></math><img file="EP0617375A2_D0013.tif" /></maths> has the correct properties. If A_Θ and B_Θ are disjoint, then the above value is positive and equal to the distance between their closest limits. If the value is negative, then its magnitude measures the extent of overlap. The following are other important relations:<maths id="math0014" num=""><math display="block"><mrow><mtext>(</mtext><mtext mathvariant="italic">x</mtext><mtext>,</mtext><mtext mathvariant="italic">y</mtext><mtext>) ε</mtext><msub><mrow><mtext mathvariant="italic">A</mtext></mrow><mrow><mtext>ϑ</mtext></mrow></msub><mtext> ⇔ </mtext><mtext mathvariant="italic">L</mtext><mtext>(</mtext><msub><mrow><mtext mathvariant="italic">A</mtext></mrow><mrow><mtext>ϑ</mtext></mrow></msub><mtext>) ≦ </mtext><msub><mrow><mtext mathvariant="italic">x</mtext></mrow><mrow><mtext>ϑ</mtext></mrow></msub><mtext> ≦ </mtext><mtext mathvariant="italic">R</mtext><mtext>(</mtext><msub><mrow><mtext mathvariant="italic">A</mtext></mrow><mrow><mtext>ϑ</mtext></mrow></msub><mtext>),</mtext></mrow></math><img file="EP0617375A2_D0014.tif" /></maths><maths id="math0015" num=""><math display="block"><mrow><msub><mrow><mtext mathvariant="italic">A</mtext></mrow><mrow><mtext>ϑ</mtext></mrow></msub><mtext>⊂</mtext><msub><mrow><mtext mathvariant="italic">B</mtext></mrow><mrow><mtext>ϑ</mtext></mrow></msub><mtext> ⇔ </mtext><mtext mathvariant="italic">L</mtext><mtext>(</mtext><msub><mrow><mtext mathvariant="italic">B</mtext></mrow><mrow><mtext>ϑ</mtext></mrow></msub><mtext>) ≦ </mtext><mtext mathvariant="italic">L</mtext><mtext>(</mtext><msub><mrow><mtext mathvariant="italic">A</mtext></mrow><mrow><mtext>ϑ</mtext></mrow></msub><mtext>),</mtext><mtext mathvariant="italic">R</mtext><mtext>(</mtext><msub><mrow><mtext mathvariant="italic">A</mtext></mrow><mrow><mtext>ϑ</mtext></mrow></msub><mtext>) ≦ </mtext><mtext mathvariant="italic">R</mtext><mtext>(</mtext><msub><mrow><mtext mathvariant="italic">b</mtext></mrow><mrow><mtext>ϑ</mtext></mrow></msub><mtext>),</mtext></mrow></math><img file="EP0617375A2_D0015.tif" /></maths><maths id="math0016" num=""><math display="block"><mrow><msub><mrow><mtext mathvariant="italic">A</mtext></mrow><mrow><mtext>ϑ</mtext></mrow></msub><mtext>∩</mtext><msub><mrow><mtext mathvariant="italic">B</mtext></mrow><mrow><mtext>ϑ</mtext></mrow></msub><mtext> = [max(</mtext><mtext mathvariant="italic">L</mtext><mtext>(</mtext><msub><mrow><mtext mathvariant="italic">A</mtext></mrow><mrow><mtext>ϑ</mtext></mrow></msub><mtext>),</mtext><mtext mathvariant="italic">L</mtext><mtext>(</mtext><msub><mrow><mtext mathvariant="italic">B</mtext></mrow><mrow><mtext>ϑ</mtext></mrow></msub><mtext>)),min(</mtext><mtext mathvariant="italic">R</mtext><mtext>(</mtext><msub><mrow><mtext mathvariant="italic">A</mtext></mrow><mrow><mtext>ϑ</mtext></mrow></msub><mtext>),</mtext><mtext mathvariant="italic">R</mtext><mtext>(</mtext><msub><mrow><mtext mathvariant="italic">B</mtext></mrow><mrow><mtext>ϑ</mtext></mrow></msub><mtext>))],</mtext></mrow></math><img file="EP0617375A2_D0016.tif" /></maths><maths id="math0017" num=""><math display="block"><mrow><msub><mrow><mtext mathvariant="italic">A</mtext></mrow><mrow><mtext>ϑ</mtext></mrow></msub><mtext>∪</mtext><msub><mrow><mtext mathvariant="italic">B</mtext></mrow><mrow><mtext>ϑ</mtext></mrow></msub><mtext> = [min(</mtext><mtext mathvariant="italic">L</mtext><mtext>(</mtext><msub><mrow><mtext mathvariant="italic">A</mtext></mrow><mrow><mtext>ϑ</mtext></mrow></msub><mtext>),</mtext><mtext mathvariant="italic">L</mtext><mtext>(</mtext><msub><mrow><mtext mathvariant="italic">B</mtext></mrow><mrow><mtext>ϑ</mtext></mrow></msub><mtext>)),max(</mtext><mtext mathvariant="italic">R</mtext><mtext>(</mtext><msub><mrow><mtext mathvariant="italic">A</mtext></mrow><mrow><mtext>ϑ</mtext></mrow></msub><mtext>),</mtext><mtext mathvariant="italic">R</mtext><mtext>(</mtext><msub><mrow><mtext mathvariant="italic">B</mtext></mrow><mrow><mtext>ϑ</mtext></mrow></msub><mtext>))].</mtext></mrow></math><img file="EP0617375A2_D0017.tif" /></maths>

The band "axes" thus form a basis for a space of convex polygons. The relations listed above can be further extended using additional attribute definitions. In the following descriptions, roman capital letters without subscripts denote complete polygons over the sent of angles:<maths id="math0018" num=""><math display="block"><mrow><mtext>(</mtext><mtext mathvariant="italic">x</mtext><mtext>,</mtext><mtext mathvariant="italic">y</mtext><mtext>)ε</mtext><mtext mathvariant="italic">A</mtext><mtext> ⇔ (∀ϑ) (</mtext><mtext mathvariant="italic">x</mtext><mtext>,</mtext><mtext mathvariant="italic">y</mtext><mtext>)ε</mtext><msub><mrow><mtext mathvariant="italic">A</mtext></mrow><mrow><mtext>ϑ</mtext></mrow></msub><mtext>.</mtext></mrow></math><img file="EP0617375A2_D0018.tif" /></maths> the point can be said to fall within each band of A. For inclusion,<maths id="math0019" num=""><math display="block"><mrow><mtext mathvariant="italic">A</mtext><mtext>⊂</mtext><mtext mathvariant="italic">B</mtext><mtext> ⇔ (∀ϑ)</mtext><msub><mrow><mtext mathvariant="italic">A</mtext></mrow><mrow><mtext>ϑ</mtext></mrow></msub><mtext>⊂</mtext><msub><mrow><mtext mathvariant="italic">B</mtext></mrow><mrow><mtext>ϑ</mtext></mrow></msub><mtext>.</mtext></mrow></math><img file="EP0617375A2_D0019.tif" /></maths> The check is simply that bands of A are contained within the corresponding bands of B. Note that for this predicate, and for point membership as well, if the result is negative it can generally be determined quickly by checking the condition in pairs -- i.e., a band and its (perhaps approximately) perpendicular band. Two more operations which naturally distribute over bands are the following:<maths id="math0020" num=""><math display="block"><mrow><mtext mathvariant="italic">A</mtext><mtext>∩</mtext><mtext mathvariant="italic">B</mtext><mtext> = {</mtext><msub><mrow><mtext mathvariant="italic">A</mtext></mrow><mrow><mtext>ϑ</mtext></mrow></msub><mtext>∩</mtext><msub><mrow><mtext mathvariant="italic">B</mtext></mrow><mrow><mtext>ϑ</mtext></mrow></msub><mtext>}.</mtext></mrow></math><img file="EP0617375A2_D0020.tif" /></maths><maths id="math0021" num=""><math display="block"><mrow><mtext mathvariant="italic">A</mtext><mtext>∪</mtext><mtext mathvariant="italic">B</mtext><mtext> = {</mtext><msub><mrow><mtext mathvariant="italic">A</mtext></mrow><mrow><mtext mathvariant="italic">ϑ</mtext></mrow></msub><mtext>∪</mtext><msub><mrow><mtext mathvariant="italic">B</mtext></mrow><mrow><mtext>ϑ</mtext></mrow></msub><mtext>}.</mtext></mrow></math><img file="EP0617375A2_D0021.tif" /></maths> Based on the measures for bands, one can define<maths id="math0022" num=""><math display="block"><mrow><mtext mathvariant="italic">Length</mtext><mtext> (</mtext><mtext mathvariant="italic">A</mtext><msubsup><mrow><mtext>) = </mtext></mrow><mrow><mtext>ϑ</mtext></mrow><mrow><mtext>min</mtext></mrow></msubsup><mtext>|</mtext><msub><mrow><mtext mathvariant="italic">A</mtext></mrow><mrow><mtext>ϑ</mtext></mrow></msub><mtext>|,</mtext></mrow></math><img file="EP0617375A2_D0022.tif" /></maths><maths id="math0023" num=""><math display="block"><mrow><mtext mathvariant="italic">Width</mtext><mtext> (</mtext><mtext mathvariant="italic">A</mtext><msubsup><mrow><mtext>) = </mtext></mrow><mrow><mtext>ϑ</mtext></mrow><mrow><mtext>min</mtext></mrow></msubsup><mtext>|</mtext><msub><mrow><mtext mathvariant="italic">A</mtext></mrow><mrow><mtext>ϑ</mtext></mrow></msub><mtext>|.</mtext></mrow></math><img file="EP0617375A2_D0023.tif" /></maths>

One can define, as well, the dimension of a polygon along any of its axes. Distance generalizes as<maths id="math0024" num=""><math display="block"><mrow><mtext mathvariant="italic">Dist</mtext><mtext> (</mtext><mtext mathvariant="italic">A</mtext><mtext>,</mtext><mtext mathvariant="italic">B</mtext><msubsup><mrow><mtext>) = </mtext></mrow><mrow><mtext>ϑ</mtext></mrow><mrow><mtext>max</mtext></mrow></msubsup><msub><mrow><mtext mathvariant="italic">A</mtext></mrow><mrow><mtext>ϑ</mtext></mrow></msub><mtext>⊖</mtext><msub><mrow><mtext mathvariant="italic">B</mtext></mrow><mrow><mtext>ϑ</mtext></mrow></msub><mtext>.</mtext></mrow></math><img file="EP0617375A2_D0024.tif" /></maths> The maximum over all band distances is the correct measure for polygon distance, because no two points on non-intersecting convex polygons can be closer, in the Euclidean sense, than any band distance. Fortunately, computing absolute distance is not as important to document analysis as testing proximity, which is defined as follows:<maths id="math0025" num=""><math display="block"><mrow><mtext mathvariant="italic">Dist</mtext><mtext> (</mtext><mtext mathvariant="italic">A</mtext><mtext>,</mtext><mtext mathvariant="italic">B</mtext><mtext>)≦Δ ⇔ (∀ϑ)</mtext><msub><mrow><mtext mathvariant="italic">A</mtext></mrow><mrow><mtext>ϑ</mtext></mrow></msub><mtext>⊖</mtext><msub><mrow><mtext mathvariant="italic">B</mtext></mrow><mrow><mtext>ϑ</mtext></mrow></msub><mtext>≦Δ.</mtext></mrow></math><img file="EP0617375A2_D0025.tif" /></maths> It is not necessary in this case to compute Dist(A,B), but only to check the band distance at each angle until either the condition is not satisfied or it has been found true for all angles. Again, there is generally a rapid exit from the procedure for negative results. Thus, a judicious choice of the checking order can decrease execution time.

OBJECT CLASSIFICATION

A second advantage to defining the bounding polygon in terms of fixed directions is that there is then a degree of rotational invariance in gauging object structure. It is possible to define a line segment, for example, as an object with a length-to-width ratio between limits, or with length and width between absolute limits. If only one rectangle is used as the bounding figure, only horizontal or vertical lines can be detected. When an array of bounding bands are used, it is possible, to a tolerance determined by the number of angles used, to recognize a line in any orientation.

To take a slightly more complex example, consider the problem of recognizing dashed lines. Let LMIN be a parameter defining required line thinness, and let MINGAP and MAXGAP be parameters delimiting the gap size in a dashed line. A recursive step in recognizing dashed lines could utilize the following comparison: If L is a line segment or dashed line, and S is a line segment, then L ∪ S is a dashed line if Width(L ∪ S) ≦ LMIN and<maths id="math0026" num=""><math display="block"><mrow><mtext>MINGAP ≦ Length (L∪S) - Length (L) - Length (S) ≦ MAXGAP.</mtext></mrow></math><img file="EP0617375A2_D0026.tif" /></maths>

Recognition of another common graphical shape, the circle or disk, is specified as condition that all bounding bands are, to within some tolerance, of the same size. Other approximations to shape may be specified as distributions of band size as well.

These examples illustrate the flexibility inherent in representing the bounding polygon as an array of bands in accordance with the invention. The array can be seen as a basis for any classification which can be done without analyzing the interior of the bounding polygon. Advantageously, it will be appreciated that weights could be assigned to the angles chosen, or the angles could be parameterized in other ways based for specific applications.

DRAWING THE POLYGON

As described above, it is not necessary to calculate the vertices of the bounding polygon in order to perform any of the operations discussed. In graphics applications, however, it is often desirable to distinguish an object by drawing its bounding polygon. Calculation of the boundary is also important in improving estimates of proximity. The proximity (within Δ) of two bounding polygons does not demonstrate the point-to-point proximity of the enclosed figures, but the error may be reduced considerably by inspecting actual picture elements in the interior of a polygon intersection.

Let A+^Δ be the polygon A extended on all sides by Δ. Denote the set of black pels in the interior of a polygon A by I_b(A). Then a more refined test for the proximity of A and B is<maths id="math0027" num=""><math display="block"><mrow><msub><mrow><mtext mathvariant="italic">I</mtext></mrow><mrow><mtext mathvariant="italic">b</mtext></mrow></msub><mtext>(</mtext><msup><mrow><mtext mathvariant="italic">A</mtext></mrow><mrow><mtext>+Δ</mtext></mrow></msup><mtext>∩</mtext><mtext mathvariant="italic">B</mtext><mtext>) ≠ ø, </mtext><msub><mrow><mtext mathvariant="italic">I</mtext></mrow><mrow><mtext mathvariant="italic">b</mtext></mrow></msub><mtext>(</mtext><mtext mathvariant="italic">A</mtext><mtext>∩</mtext><msup><mrow><mtext mathvariant="italic">B</mtext></mrow><mrow><mtext>=Δ</mtext></mrow></msup><mtext>) ≠ ø.</mtext></mrow></math><img file="EP0617375A2_D0027.tif" /></maths> If these conditions hold, then there is point-to-point proximity along some axis. The accuracy of this test increases with the number of polygon sides.

To calculate the polygon vertices, it is first noted that each side of the polygon is a line perpendicular to its Θ axis through the origin, and at a distance d from the origin. The equation of such a line is<maths id="math0028" num=""><math display="block"><mrow><msub><mrow><mtext mathvariant="italic">n</mtext></mrow><mrow><mtext>ϑ</mtext></mrow></msub><mtext mathvariant="italic">x</mtext><mtext>+</mtext><msub><mrow><mtext mathvariant="italic">m</mtext></mrow><mrow><mtext>ϑ</mtext></mrow></msub><mtext mathvariant="italic">y</mtext><mtext> = </mtext><mtext mathvariant="italic">d</mtext><msqrt><msubsup><mrow><mtext mathvariant="italic">m</mtext></mrow><mrow><mtext>ϑ</mtext></mrow><mrow><mtext>2</mtext></mrow></msubsup><mtext>+</mtext><msubsup><mrow><mtext mathvariant="italic">n</mtext></mrow><mrow><mtext>ϑ</mtext></mrow><mrow><mtext>2</mtext></mrow></msubsup></msqrt><mtext>,</mtext></mrow></math><img file="EP0617375A2_D0028.tif" /></maths> or, in the case under consideration, (6)<maths id="math0029" num=""><math display="block"><mrow><msub><mrow><mtext mathvariant="italic">n</mtext></mrow><mrow><mtext>ϑ</mtext></mrow></msub><mtext mathvariant="italic">x</mtext><mtext>+</mtext><msub><mrow><mtext mathvariant="italic">m</mtext></mrow><mrow><mtext>ϑ</mtext></mrow></msub><mtext mathvariant="italic">y</mtext><mtext> = </mtext><msub><mrow><mtext mathvariant="italic">l</mtext></mrow><mrow><mtext>ϑ</mtext></mrow></msub><mtext>/</mtext><msub><mrow><mtext mathvariant="italic">s</mtext></mrow><mrow><mtext>ϑ</mtext></mrow></msub><mtext> (</mtext><mtext mathvariant="italic">or</mtext><mtext></mtext><msub><mrow><mtext mathvariant="italic">r</mtext></mrow><mrow><mtext>ϑ</mtext></mrow></msub><mtext>/</mtext><msub><mrow><mtext mathvariant="italic">s</mtext></mrow><mrow><mtext>ϑ</mtext></mrow></msub><mtext>).</mtext></mrow></math><img file="EP0617375A2_D0029.tif" /></maths> To calculate the vertices, it is only necessary to order the lines of equation (6), for example, by increasing angle and determining the intersections between adjacent lines in the (circular) sequence as the polygon vertices. Denoting the solution of equation (6) for lΘ as LΘ and for rΘ as RΘ, the sequence is<maths id="math0030" num=""><math display="block"><mrow><mtext>{</mtext><msub><mrow><mtext mathvariant="italic">R</mtext></mrow><mrow><mtext mathvariant="italic">o</mtext></mrow></msub><mtext>,...,</mtext><msub><mrow><mtext mathvariant="italic">R</mtext></mrow><mrow><mtext>ϑ&lt;π/2</mtext></mrow></msub><mtext>,</mtext><msub><mrow><mtext mathvariant="italic">L</mtext></mrow><mrow><mtext>π/2</mtext></mrow></msub><mtext>,...,</mtext><msub><mrow><mtext mathvariant="italic">L</mtext></mrow><mrow><mtext>ϑ&lt;π</mtext></mrow></msub><mtext>,</mtext><msub><mrow><mtext mathvariant="italic">L</mtext></mrow><mrow><mtext mathvariant="italic">o</mtext></mrow></msub><mtext>,...,</mtext><msub><mrow><mtext mathvariant="italic">L</mtext></mrow><mrow><mtext>ϑ&lt;π/2</mtext></mrow></msub><mtext>, </mtext><msub><mrow><mtext mathvariant="italic">R</mtext></mrow><mrow><mtext>π/2</mtext></mrow></msub><mtext>,...,</mtext><msub><mrow><mtext mathvariant="italic">R</mtext></mrow><mrow><mtext>ϑ</mtext></mrow></msub><mtext>&lt;π}.</mtext></mrow></math><img file="EP0617375A2_D0030.tif" /></maths>

The algebra need not be reproduced here, but it will be appreciated that the calculations are considerably simplified when using the angular sequence (5).

A class of convex polygons over fixed directions in the plane have thus been defined. It has been shown that the bounding polygons for all connected components in a binary image can be computed efficiently in one pass, and that a particular form of the procedure can be implemented using only shift and add operations. In addition, a basic algebra over the polygons can be used for efficient segmentation, low-level discrimination among basic object shapes, and recognition of complex objects consisting of disconnected components. While preferred embodiments and implementations of the invention have been shown and described, it is expected that modifications or adaptations thereof will be made by persons skilled the art.