Method and system for recognizing a rotated image pattern with reduced processing time and memory space

An image pattern recognition process and system recognize a rotated predetermined image pattern with reduced processing time and memory requirements based upon the efficient use of the Zernike Moment.

FIELD OF THE INVENTION
 The current invention is generally related to an image pattern recognition
 process and system, and more particularly related to a method and a system
 for recognizing a rotated predetermined image pattern with reduced time
 and memory requirements.
 BACKGROUND OF THE INVENTION
 To recognize a rotated image pattern, a prior art system generally requires
 large memory space and or long processing time. This is because the
 recognition is usually accomplished in real time and the image pattern may
 be reduced, enlarged or rotated. Any combination of these factors further
 complicates the processing time and memory space requirements and tends to
 lower accuracy in correctly recognizing an image pattern.
 Prior art attempts include the use of the Zernike Moment in recognizing an
 image pattern. For example, Japanese Laid Patent Publication Hei 9-147109
 (Application Serial Number Hei 7-301250) discloses the reduced memory
 requirement in recognizing a predetermined image pattern based upon the
 use of a radial polynomial table containing intermediate values for
 determining Zernike Moment values. The Zernike Moment values are defined
 as a product of a radial polynomial value and a pixel value. Although a
 size difference of the predetermined image pattern is accommodated by
 adjusting the radial polynomial table values, a rotated image pattern as
 shown in FIG. 1 is not recognized according to the disclosure. This is
 because the Zernike Moment values for a predetermined image pattern are
 constant over the rotational angle of the image.
 In order to recognize a predetermined image pattern which is rotated at an
 arbitrary angle, prior art attempts such as Japanese Laid Patent
 Publication Hei 8-279021 (Application Serial Number Hei 7-301250) disclose
 that a rotational angle of a predetermined image pattern is determined
 based upon a characteristic value such as a number of "on" pixels at
 equidistant locations from a common point. The measure characteristic
 value is compared to a set of standard dictionary values each for a known
 angle, and a rotational angle is selected according to minimal distance to
 the standard characteristic value. However, this prior art attempt
 requires additional processing for higher degree characteristic values as
 well as the number of comparisons.
 SUMMARY OF THE INVENTION
 In order to solve the above and other problems, according to a first aspect
 of the current invention, a method of recognizing an image pattern having
 an outer boundary, including inputting an input image pattern and a
 standard dictionary containing standard characteristic values for
 predetermined image patterns; determining whether an outer boundary exists
 for the input image pattern; determining a rotational angle of the input
 image pattern based upon the outer boundary; determining a characteristic
 value at each of a set of predetermined relative locations within the
 input image pattern; adjusting the characteristic values according to the
 rotational angle; and determining whether the input image pattern matches
 one of the predetermined image patterns based upon a similarity distance
 between the standard characteristic values and the adjusted characteristic
 values.
 According to a second aspect of the current invention, a method of
 determining a rotational angle of an image pattern having an outer
 boundary, including: inputting an input image pattern and a radial
 polynomial table containing sets of Zernike Moment (ZM) intermediate
 values for a predetermined specific size of the input image pattern, each
 set containing the ZM intermediate values each at a predetermined
 rotational angle for a predetermined periodicity; determining a plurality
 of Zernike Moment (ZM) values by multiplying a predetermined set of the ZM
 intermediate values by pixel values at predetermined equidistant location
 from a center of the input image pattern; assigning an evaluation value
 for each of the ZM values by multiplying the ZM value and a corresponding
 periodicity; and determining a rotational angle of the input image pattern
 based upon a largest one of the evaluation values.
 According to a third aspect of the current invention, a system for
 recognizing an image pattern having an outer boundary, including: an input
 unit for inputting an input image pattern and a standard dictionary
 containing standard characteristic values for predetermined image
 patterns; an outer boundary determination unit connected to the input unit
 for determining whether an outer boundary exists for the input image
 pattern; a rotational angle detection unit connected to the outer boundary
 determination unit for determining a rotational angle of the input image
 pattern based upon the outer boundary; and a pattern matching unit
 connected to the rotational angle detection unit for determining a
 characteristic value at each of a set of predetermined relative locations
 within the input image pattern and for adjusting the characteristic values
 according to the rotational angle, the pattern matching unit determining
 whether the input image pattern matches one of the predetermined image
 patterns based upon a similarity distance between the standard
 characteristic values and the adjusted characteristic values.
 According to a fourth aspect of the current invention, A system for
 determining a rotational angle of an image pattern having an outer
 boundary, comprising: an input unit for inputting an input image pattern
 and a radial polynomial table containing sets of Zernike Moment (ZM)
 intermediate values for a predetermined specific size of the input image
 pattern, each set containing the ZM intermediate values each at a
 predetermined rotational angle for a predetermined periodicity; a Zernike
 Moment generation unit connected to the input unit for determining a
 plurality of Zernike Moment (ZM) values by multiplying a predetermined set
 of the ZM intermediate values by pixel values at predetermined equidistant
 location from a center of the input image pattern; an evaluation unit
 connected to the Zernike Moment generation unit for assigning an
 evaluation value for each of the ZM values by multiplying the ZM value and
 a corresponding periodicity; and a rotational angle determination unit
 connected to the evaluation unit for determining a rotational angle of the
 input image pattern based upon a largest one of the evaluation values.
 These and various other advantages and features of novelty which
 characterize the invention are pointed out with particularity in the
 claims annexed hereto and forming a part hereof. However, for a better
 understanding of the invention, its advantages, and the objects obtained
 by its use, reference should be made to the drawings which form a further
 part hereof, and to the accompanying descriptive matter, in which there is
 illustrated and described a preferred embodiment of the invention.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT(S)
 Referring now to the drawings, wherein like reference numerals designate
 corresponding structure throughout the views, and referring in particular
 to FIG. 2, one preferred embodiment of the system for recognizing a
 rotated image pattern with reduced time and memory space according to the
 current invention includes a CPU 100, a memory unit 102, a communication
 unit 104 which is connected to a communication line, a display unit 110,
 an input unit such as a keyboard 108, and storage unit such as a hard disk
 108 and a compact disk (CD) drive and a CD. An image data containing an
 image pattern to be recognized is imported to the memory unit 102 from the
 storage unit or via the communication unit 104. The CPU 100 run a
 predetermined software including the computer instructions for efficiently
 recognizing the image pattern with reduced memory space. A user interacts
 with the system with the keyboard to specify the commencement of the
 recognition process, and the intermediate and or final results are
 displayed on the display unit 110.
 Now referring to FIG. 3, a second embodiment of the system for recognizing
 a rotated image pattern with reduced time and memory space according to
 the current invention includes an input unit 1, an outer boundary
 determination unit 2, a rotational angle determination unit 3, a pattern
 determination unit 4 and an image output unit 5. The second preferred
 embodiment is either software or hardware. The input unit 1 inputs image
 data containing a predetermined input image pattern to be recognized as
 well as standard or dictionary data to be compared. The outer boundary
 determination unit 2 determines an outer boundary of the input image
 pattern to be recognized. The outer boundary has a predetermined shape
 which includes a circle, a square and a rectangle. After the predetermined
 outer boundary is determined, the rotational angle determination unit 3
 determines a rotational angle of the input image pattern. The rotational
 angle determination unit 3 determines the rotational angle using a
 measured value and a standard value of the outer boundary. One example of
 theses values includes Zernike moment values, and detailed implementations
 will be later described. Based upon the rotational angle, the image
 pattern determination unit 4 first adjusts the standard or measured values
 and then determines whether the adjusted values substantially or most
 closely match the unadjusted values based upon a predetermined set of
 rules. Upon recognizing the image pattern match, the image output unit
 outputs the recognition results.
 Referring to FIG. 4, one example of the outer boundary determination unit 2
 further includes an image input data unit 21 for inputting the image data
 into the outer boundary determination unit 2, an image processing unit 22
 for digitizing and modifying the image data, a binary compression image
 memory 23 and a compression unit 24 for generating compressed binary image
 data, a compressed image memory unit 25 and an edge detection unit 26 for
 detecting a predetermined outer boundary, a circular pattern determination
 unit 27 for determining whether or not the outer boundary is circular, a
 coordinate determination unit 28 for determining coordinates of the
 circular outer boundary based upon the digitized image data and an output
 unit for outputting the results including the outer boundary detection and
 the outer.
 To further describe the outer boundary determination, FIG. 5 is a flow
 chart for illustrating steps involved in detecting a circular outer
 boundary. In a step 101, color image data as well as standard data are
 inputted. The inputted image data is first digitized into black-and-white
 image data based upon a predetermined threshold value such as an intensity
 value and stored in a step 102. For example, the digitized values are
 compressed to 1/4 of 200.times.200 dpi. The digitized data is then
 compressed for further processing in a step 103. The compression is
 accomplished by "ORing" each 4.times.4 pixel block. That is, if any one of
 the pixels is "on," the entire 4.times.4 block is compressed to single
 compressed "on" block data. Still using the above example, after the
 compression, the data amount is 1/16 or 50.times.50 dpi. This compression
 saves memory space during the rotation angle determination and pattern
 recognition processes. In a step 104, a mask of a predetermined size and
 shape is used to detect an edge. In general, the edge detection is
 performed by detecting an edge from predetermined relative locations on
 the mask towards a center of the input image pattern within the mask. If
 an edge is not detected from every location, it is determined whether or
 not every pixel has been processed in a step 109. If the processing has
 not been complete, the mask is moved by one pixel in a step 110, and the
 steps 104 and 105 are repeated. In case the processing has been complete
 for every pixel, it is determined that the predetermined outer boundary is
 lacking in the image pattern, and the edge detection process is finished.
 On the other hand, if the edge is detected from every detection point or
 predetermined relative location in a step 105, a predetermined outer
 boundary is recognized in the input image pattern in step 106. The
 coordinates of the detected edge or outer boundary are determined, and the
 coordinates are also corrected for the compression in a step 107. The
 corrected coordinates are outputted in a step 108.
 Now referring to FIG. 6, one exemplary circular mask is illustrated. The
 size of the mask is 33 by 33 pixels, and there are sixteen predetermined
 locations on the mask. An edge detection step is performed from each of
 these locations towards the center of the mask as indicated by arrows. At
 each location, a particular set of pixel patterns or local mask patterns
 is used to detect a circular edge, and the same set of pixel patterns is
 moved towards the center of the mask to further find any match. At certain
 locations, only one pixel pattern (4.times.4 or 3.times.2 pixels) is used
 while at other locations, two pixel patters (3.times.3 pixels) are used.
 One way to determine the circular mask size is: (a diameter of a circular
 outer boundary/a compression rate)+line width+margin. For example, a
 circular mask size for the 15 mm diameter circular outer boundary is 33
 pixels if each mm contains 16 pixels. That is, 240 pixels
 (15.times.16)/8+2 pixel line width+1 pixel margin=33.
 FIGS. 7A and 7B are tables which summarize the coordinate determination for
 the detected edge at each predetermined location as indicated in the left
 most column. The X coordinate and Y coordinate are determined by a
 respective equation, and the initial coordinates for each location is
 enumerated for either a 33.times.33 mask or a 35.times.35 mask. In
 addition, the tables include associated local mask patterns, the direction
 of the movement of the mask towards the center as well as the number of
 pixels to be moved for each pattern. The tables are illustrated for
 exemplary purposes and are not limited to any particular format or
 contents.
 FIG. 8 further illustrates the edge detection at a particular location
 using a predetermined mask pattern. At the south location, the 3.times.2
 pixel pattern is used. Although the pixel pattern in FIG. 7B indicates
 that three adjacent pixels in the same row need to be "on" while the other
 row need be "off" in order to detect an edge. According to one method of
 the current invention, if there are at least two contrasting adjacent
 pixels as indicated by arrows, these adjacent pairs of pixels indicate an
 edge.
 Now referring to FIGS. 9A and 9B, the coordinates of the edge line are
 determined using compressed and uncompressed pixel patterns. FIG. 9A
 illustrates one exemplary coordinate determination in the compressed data
 that a first "on" pixel is located at a southern end of an edge. As
 described above, a row of the three adjacent pixel pattern is used to
 detect the edge. The southern end is the Y-ending coordinate while a
 northern end is the Y-beginning coordinate. Similarly, an eastern end is
 the X-beginning coordinate while a western end is the X-ending coordinate.
 In other words, within the nine (3.times.3) pixels in hatched lines, at
 least one is originally "on" before the compression.
 Now referring to FIG. 9B, the original pixel data size is 12 by 12 since
 the compression rate is 1/16. The edge detection position is indicated by
 the 3.times.3 pixels which are located at the southern position. Each row
 of 12 pixels is examined at a time in an upward direction indicated by an
 arrow, and when at least one pixel is "on," the row is considered to be
 the Y-beginning coordinate. Similarly, each row of 12 pixels is examined
 at a time in a downward direction to located the Y-ending coordinate. To
 determine X-coordinates, each column of 12 pixels is examined respectively
 in a left-to-right direction to locate a western end or the X-beginning
 coordinate and in a right-to-left direction to locate an eastern end or
 the X-ending coordinate. However, for the western and northern ends are
 determined by shifting by only one pixel, forty-eight pixels are detected.
 Based upon the above described X and Y coordinates, a center of a
 predetermined outer boundary is determined. The above determined
 information is generally used for determining a rotational angle.
 In addition to the above described circular outer boundaries or masks,
 referring to FIGS. 10A through 10F, alternative embodiments include square
 and rectangular masks and outer boundaries. To determine the non-circular
 outer boundaries, an image pattern is circumscribed by a minimal
 circumscribing boundary as shown in FIGS. 10A through 10D. The minimal
 circumscribing boundary or rectangle minimally encloses an image pattern.
 The minimal circumscribing rectangle as shown in FIG. 10D matches the
 image pattern itself. However, if the rectangular image is rotated, and if
 it contacts at one point on each edge of a horizontally placed
 predetermined square with an equal distance a, b, c and d from each corner
 as shown in FIG. 10E, the minimal circumscribing rectangle is determined
 to be a rotated square. On the other hand, if the minimal circumscribing
 boundary is not rectangle as shown in FIG. 10F, the distances a, b, c, and
 d are not equal from each corner of the predetermined horizontally placed
 rectangle.
 In order to describe the rotational angle determination process, the
 Zernike moment is first described. As defined by Kim and Po Yuan in "A
 Practical Pattern Recognition System for Translation, Scale and Rotation
 Invariance," Pp. 391-396, Proc. CVPR, June, 1994:
 ##EQU1##
 where Rnm(.rho.) is a radial polynomial equation which is determined by a
 degeree, periodicity, and a distance from the center.
 ##EQU2##
 where Re.sub.(anm) is a real number portion of the Zernike moment.
 ##EQU3##
 where Im.sub.(anm) is an imaginary number portion of the Zernike moment.
 In the above equations (1) through (3), n is a degree of the Zernike Moment
 while m is periodicity. The absolute value of m is equal to or smaller
 than that of n, and the difference between them must be an even number.
 The Zernike moment as defined below is constant over a rotational angle.
EQU Re.sub.(anm).sup.2 +Im.sub.(anm).sup.2
 Because of this constant characteristic of the Zernike moment, a
 predetermined image pattern f.sub.(x,y) is identified based upon the
 Zernike moment. Variables x and y specify a particular image pattern size.
 One exemplary method normalizes the variable x and y values which range
 from 0 to 1. The coordinates are adjusted (enlarged or reduced) so that
 the furtherest point from the center of the image pattern is 1.
 If the equations (2) and (3) are used to determine the Zernike moment for
 every image pattern candidate, since it takes a large amount of processing
 time, the use of the equations is not practical. To shorten the processing
 time, a table containing intermediate values for the Zernike moment is
 prepared in advance for a predetermined image pattern in predetermined
 sizes. The intermediate values are determined by the following equations.
 ##EQU4##
 A product of a pixel value and the above described Zernike moment
 intermediate value is the Zernike moment. In addition to the equation (4)
 and (5), the following equations (6) and (7) incorporate the Zernike
 moment intermediate table values in order to determine the Zernike moment.
EQU Re.sub.(Anm) =.intg..sub.x.sub..sup.2 .sub.+y.sub..sup.2
 .sub..ltoreq.1.function..sub.(x,y) ReT.sub.(Anm) (x,y)dxdy (6)
EQU Im.sub.(Anm) =.intg..sub.x.sub..sup.2 .sub.+y.sub..sup.2
 .sub..ltoreq.1.function..sub.(x,y) ImT.sub.(Anm) (x,y)dxdy (7)
 Now referring to FIG. 11, one preferred embodiment of the rotational angle
 determination unit according to the current invention further includes an
 image buffer unit 31 for temporarily storing input image pattern data
 having a predetermined outer boundary, a product summation unit for
 determining a product between a pixel value and a corresponding
 intermediate value from a radial polynomial table 33, a Zernike Moment
 (ZM) determination unit 34 for determining a ZM value; a ZM value
 comparison unit 35 for comparing the ZM value to standard or dictionary ZM
 values stored in a ZM dictionary; a rotational angle determination unit 37
 for determining a rotational angle based upon a ZM value; an evaluation
 value determination unit 38 for determining a evaluation value for each
 rotational angle based upon the ZM value, degree and periodicity; a
 rotational angle selection unit 39 for selecting the most appropriate
 rotational angle based upon an evaluation value; an angular difference
 determination unit 40 for determining an angle difference; and a
 rotational angle output unit 41 for outputting a final rotational angle
 based upon the selected rotational angle and the angle difference.
 FIGS. 12 through 14 each illustrate a Zernike radial polynomial table
 (ZPT). A "off" or white pixel indicates a value of -63 while an "on" or
 black pixel indicates a value of 63. A value of 0 indicates gray. Now
 referring to FIGS. 12A and 12B, these ZPT's are third degree and first
 periodicity. FIG. 12A illustrates a real number portion of the ZPT while
 FIG. 12B illustrates an imaginary number portion of the ZPT, which is
 1/2.pi. rotated with respect to the real number portion. First periodicity
 means that one cycle for a change from black to white. FIGS. 13A and 13B
 respectively illustrate a real number portion and an imaginary number
 portion of the 4.sup.th degree 2.sup.nd periodicity ZPT. The imaginary
 number portion is rotated by 1/4.pi. with respect to the real number
 portion. FIGS. 14A and 14B respectively illustrate a real number portion
 and an imaginary number portion of the 6.sup.th degree 4.sup.th
 periodicity ZPT. The imaginary number portion is rotated by 1/8.pi. with
 respect to the real number portion.
 Now referring to FIG. 15, a product summation is illustrated for
 determining a real number portion of a Zernike Moment value. A Zernike
 Moment radial polynomial table (ZPT) 51 contains intermediate values or
 Zernike Moment (ZM) radial polynomial values for a corresponding portion
 52 of input image data. Since the input image data 52 is digitized, only
 black or "on" pixels are considered for the product summation. The ZM
 radial polynomial values corresponding to the "on" pixels as shown in a
 product 53 are summed to render a ZM value. In other words, the summation
 includes 0+0+0+-1+1+-2+-1+-5+-3+1+1+-3+-4+-2+-1+2+4+1+1+2+0+0=-9. In one
 preferred method of determining a ZM value, a plurality of ZPT's for
 various degrees and periodicity is used. For example, the ZPT's are
 prepared for 1.sup.st, 2.sup.nd and 4.sup.th periodicity, and for each
 periodicity, ZPT's have a real number portion and an imaginary number
 portion. Thus, using six separate ZPT's, six ZM values are determined.
 FIG. 16 is a flow chart illustrating steps involved in one preferred
 process of determining a rotational angle according to the current
 invention. In a step 301, input image data and corresponding outer
 boundary information are inputted. In a step 302, a center coordinate of
 the above determined outer boundary and a corresponding coordinate (0, 0)
 of the Zernike radial polynomial table are matched. Alternatively, a
 center of gravity is used to align the outer boundary. After the center is
 correctly positioned in the ZM radial polynomial table, a product between
 a pixel value and the corresponding intermediate value in the ZM radial
 polynomial table is determined in a step 303. The product determination is
 performed on every pixel within an area bound by the outer boundary for
 each of the predetermined set of periodicity by repeating the step 303
 until every periodicity is considered in a step 304. Although this
 preferred process shows a sequential processing for each periodicity, an
 alternative process determines a number of product summation values in
 parallel. After the product summations are obtained for all of the
 predetermined periodicity, ZM values are determined in a step 305.
 Still referring to FIG. 16, assuming the predetermined set of periodicity
 includes 1.sup.st, 2.sup.nd and 4.sup.th periodicity, a ZM value is
 determined and ascertained as follows in steps 305 through 308. Let ZMr1
 and ZMi1 be respectively a real number portion and an imaginary number
 portion of the product sum using a 1.sup.st periodicity ZM radial
 polynomial table. Similarly, ZMr2 and Zmi2 be respectively a real number
 portion and an imaginary number portion of the product sum using a
 2.sup.nd periodicity ZM radial polynomial table. Lastly, ZMr4 and Zmi4 be
 respectively a real number portion and an imaginary number portion of the
 product sum using a 4.sup.th periodicity ZM radial polynomial table. By
 using the similar notation, let Zmag1, Zmag2 and Zmag4 be respectively a
 ZM value for the 1.sup.st, 2.sup.nd and 4.sup.th periodicity, and the ZM
 values are not affected by a rotational angle of an input image pattern.
 Based upon the above notations, the ZM values Zmag1, Zmag2 and Zmag4 are
 defined as follows:
EQU Zmag1=(ZMr1).sup.2 +(Zmi1).sup.2
EQU Zmag2=(ZMr2).sup.2 +(Zmi2).sup.2
EQU Zmag4=(ZMr4).sup.2 +(Zmi4).sup.2
 These ZM values are compared to a series of predetermined ranges in steps
 306 through 308 in order to ascertain their appropriateness. In other
 words, in the step 306, the 1.sup.st periodicity ZPT-based ZM value Zmag1
 is compared to a first predetermined range defined by two threshold values
 TH2 and TH1. If Zmag1 is not within the first predetermined range in a
 step 306, the rotational angle determination process is terminated without
 outputting a rotational angle. Similarly, if Zmag2 is not within a second
 predetermined range defined by threshold values TH3 and TH4 in a step 307,
 the rotational angle determination process is terminated without
 outputting a rotational angle. Lastly, if Zmag4 is not within a third
 predetermined range defined by threshold values TH5 and TH6 in a step 308,
 the rotational angle determination process is terminated without
 outputting a rotational angle. On the other hand, if the ZM values Zmag1,
 Zmag2 and Zmag4 are each within a respective predetermined range, the
 following steps are performed.
 When appropriateness of the ZM values is satisfied by the above described
 steps, a set of steps 309 through 313 are further performed to determine a
 rotational angle. In a step 309, a set of evaluation values is determined
 for each of the ZM values. The evaluation value is defined as a product of
 a ZM value and a corresponding periodicity. For example, if a first
 periodicity ZM value Zmag1 is -9, its evaluation value is -9.times.1=-9.
 In a step 310, a first rotational angle .theta.1 is determined based upon
 a real number portion ZM value Zmr1 or an imaginary portion ZM value Zmi1.
 Similarly, a second rotational angle .theta.2 is determined based upon a
 real number portion ZM value Zmr2 or an imaginary portion ZM value Zmi2.
 Lastly, a third rotational angle .theta.3 is determined based upon a real
 number portion ZM value Zmr4 or an imaginary portion ZM value Zmi4. In a
 step 311, a rotational angle with the largest evaluation value is
 selected. In a step 312, an angle .theta.a is defined as an angle
 difference between the first and second rotational angles .theta.1 and
 .theta.2 while an angle .theta.b is defined as an angle difference between
 the first and second rotational angles .theta.2 and .theta.4. Similarly,
 an angle .theta.c is defined as an angle difference between the first and
 third rotational angles .theta.1 and .theta.4. It is determined whether or
 not the angle difference values .theta.a, .theta.b and .theta.c satisfy
 the following condition in the step 312:
EQU .theta.a+2.theta.b+2.theta.c&lt;TH
 where TH is a predetermined threshold value. If the above condition is
 satisfied, the rotational angle selected in the step 311 is outputted in a
 step 313. On the other hand, the above condition is not met, no rotational
 angle is outputted, and the rotational angle determination process is
 terminated.
 Now referring to FIGS. 17A, 17B and 17C, a rotational angle determination
 is further described for each periodicity. FIGS. 17A, 17B and 17C
 respectively show a real number portion of the standard ZM value over
 rotational angle of a predetermined image pattern for a 3.sup.rd degree
 1.sup.st periodicity; a 4.sup.th degree 2.sup.nd periodicity and a
 6.sup.th degree 4.sup.th periodicity. Each graph or a standard dictionary
 is generated by computationally rotating a predetermined image pattern by
 one degree between 0 and 360. The X axis indicates angle (0-2.pi.) which
 is quantified in 296. The imaginary portion is phased by 1/2.pi.. The
 product sum or ZM value obtained for an input image is thus compared to
 the standard dictionary to determine a rotational angle. Alternatively,
 the rotational angle is also determined by arctan (an imaginary number
 portion/a real number portion) of the ZM value. Yet another alternative
 method for determining the rotational angle takes arcsin of (an imaginary
 portion/a ZM value).
 Referring to FIG. 17A, a single rotational angle for first periodicity is
 generally determined based upon a ZM value of an input image data that is
 obtained by generating a product using a first periodicity based ZPT. For
 an improved accuracy, it is preferred to use either of a real number
 portion or an imaginary number portion of the ZM value that has the
 smaller absolute value. In other words, a portion having a larger change
 ratio between an angle and a ZM value is preferred. For example, if the
 obtained ZM value is Rel, a rotational angle is .theta.1 as shown in FIG.
 17A.
 Now referring to FIG. 17B, second periodicity based ZM values are plotted
 over angle ranging from 0 to 2.pi.. As shown, within this range, for a
 given ZM value, there are two candidates for a rotational angle. Only one
 of the candidates is correct since the other angle is due to cyclic
 periodicity of the Zernike Moment. In order to select the correct
 rotational angle, a difference in angle with respect to the above
 rotational angle that is selected in the first periodicity based ZM values
 is compared. The difference is usually smaller than .pi./2. One of the
 candidates is selected so that the second periodicity based rotational
 angle has a smaller difference or is closer to the above determined first
 periodicity based rotational angle. For example, between the two
 candidates .theta.2 and .theta.2', the rotational angle .theta.2 is
 selected since it is closer to the first periodicity based rotational
 angle .theta.1.
 Now referring to FIG. 17C, fourth periodicity based ZM values are plotted
 over angle ranging from 0 to 2.pi.. As shown, within this range, for a
 given ZM value, there are four candidates for a rotational angle. Only one
 of the candidates is correct since other angles are due to cyclic
 periodicity of the Zernike Moment. In order to select the correct
 rotational angle, the above defined evaluation values are used. If the
 evaluation value for the first periodicity based ZM value is lager than
 that of the second periodicity based ZM value, one of the four candidates
 that is the closest to the first periodicity based angle is selected. On
 the other hand, if the evaluation value for the second periodicity based
 ZM value is lager than that of the first periodicity based ZM value, one
 of the four candidates that is the closest to the second periodicity based
 angle is selected. For example, among the four candidates .theta.4,
 .theta.4', .theta.4" and .theta.4'", the rotational angle .theta.4 is
 selected since it is closer to the first or second periodicity based
 rotational angles .theta.1 or .theta.2.
 Now referring to FIG. 18, one preferred embodiment of the pattern
 determination unit according to the current invention is further
 described. This exemplary embodiment is designed for a circular outer
 boundary and includes an image buffer unit 61 for storing the image
 pattern data; a characteristic value determination unit 62 for determining
 a certain characteristic value of pixels located in a predetermined
 circumference; a circumference table 63 for storing a position of each
 circumference; a sequence table 64 for storing positions corresponding to
 each characteristic value; a standard circumference dictionary 67 for
 storing characteristic values for a standard image; a distance
 determination unit 66 for determining a distance between a characteristic
 value in the characteristic value memory unit 65 and the characteristic
 value in the standard circumference dictionary 67; an evaluation unit 68
 for determining whether or not an input image pattern matches a standard
 image pattern based upon an evaluation value; and an image output unit for
 outputting the evaluation result.
 FIGS. 19 and 20 respectively illustrate one example of the circumference
 position table 63 and the circumference sequence table 64. A position
 marked by an "x" at (15, 15) is a center. From the center, positions on
 each circumference is marked by the same numeral. In this exemplary
 circumference table 63, there are five circumferences referenced by 0
 through 4. The circumference reference numbers 0 through 4 is also used as
 an index to retrieve or store a characteristic value. In an alternative
 embodiment, an outer boundary is not limited to a circle, and the
 circumference table 63 is more properly named as an outer boundary
 position table. FIG. 20 illustrates one example of the circumference
 sequence table 64 containing the corresponding number and position of
 circumferences as the circumference position table 63. Each circumference
 includes a set of indexes ranging from 0 to 15 and from 0 to 31, and the
 index is used to retrieve or store a characteristic value.
 FIG. 21 illustrates the use of the above described circumference table 63
 and the sequence table 64 in determining and storing a characteristic
 value. To illustrate the use, the tables 63 and 64 have exemplary values.
 Each pixel in input image pattern data is scanned in both X as well as Y
 directions. Assuming a current pixel is located at X=2, Y=1 in the input
 image data, it is determine whether or not the current pixel requires a
 characteristic value determination by looking at the content of the
 circumference table at the corresponding coordinates. According to the
 exemplary circumference table, the cell at (2, 1) contains an index whose
 value is 5, and the presence of a value indicates that the current pixel
 requires a characteristic value determination. The index is a row location
 reference in a characteristic value table. By the same token, the
 exemplary sequential table at (2, 1) contains a second index whose value
 is 10, and the second index is used to reference a column location in the
 characteristic value table. A characteristic value for the current pixel
 is determined based upon a number of "on" or black pixels in a 3.times.3
 pixel area whose center pixel is the current pixel. If the number of "on"
 pixels in the 3.times.3 pixel area is more than 4, a characteristic value
 is defined to be 1. Otherwise, the characteristic value is defined to be
 0. In this example, since the number of the "on" pixels in the 3.times.3
 pixel area is 4, the corresponding characteristic value is 0. The
 characteristic value 0 is then stored at the above specified location (10,
 5) in the characteristic value table.
 Now referring to FIG. 22, steps involved in a preferred process of pattern
 determination according to the current invention are illustrated in a flow
 chart. Although this preferred process is designed for an image pattern
 having a circular outer boundary, the process according to the current
 invention is not limited to a circular outer boundary. An input image
 pattern having a circular outer boundary and the above determined
 rotational angle are inputted in a step 401. In order to determine a
 characteristic value, a center position of the input image pattern is
 aligned with that of the circumference table in a step 402. It is
 determined whether or not a current pixel requires a characteristic value
 determination in a step 403. As described above with respect to FIG. 21,
 if a characteristic value determination is not necessary, the current
 pixel position is moved by one pixel in a predetermined direction in a
 step 404. On the other hand, if the current pixel requires a
 characteristic value determination, a characteristic value is determined
 in a step 405 according to a predetermined rule such as one described
 above. The above steps 403 and 405 are repeated until every pixel is
 scanned. When the characteristic value determination is complete, a
 distance between a characteristic value of an input image pattern and that
 of a standard image pattern is determined in a step 407.
 Still referring to FIG. 22, the following steps 408 through 415 are
 performed to determine whether an input image pattern matches a standard
 image pattern. In a step 408, an evaluation value is defined by an
 equation:
EQU (1-(the above determined distance/a number of pixels on a
 circumference)).times.100.
 If the evaluation value is not above a predetermined threshold value TH in
 a step 409, a corresponding circumference is removed for the further
 consideration. On the other hand, if the evaluation value exceeds the
 threshold value, the corresponding circumference is further statistically
 evaluated in a step 410. If the evaluation value for a current
 circumference is statistically low in view of other evaluation values, the
 current circumference is removed from further consideration. For example,
 when one pixel is moved in aligning the center of a circle, if a number of
 pixels on a circumference changing from "off" to "on" is large, the
 circumference is removed. In a step 412, a number of remaining
 circumferences and a number of valid circumferences are determined. The
 number of remaining circumferences is defined as a number of evaluated
 circumferences after invalid circumferences are removed in a step 410. The
 number of valid circumferences is defined as a total number of
 circumferences less invalid circumferences. In a step 413, the ratio
 between the number of remaining circumferences and the number of valid
 circumferences is compared to a second predetermined threshold value Th2
 in a step 413. If the ratio exceeds the second predetermined threshold
 value Th2, the input image pattern is considered to match the standard
 image pattern in a step 414. On the other hand, if the ratio fails to
 exceed the second predetermined threshold value Th2, the input image
 pattern is not considered to match the standard image pattern in a step
 415.
 Now referring to FIG. 23, a distance determination step is further
 illustrated. A characteristic value of each input circumference is
 compared to that of a standard circumference by shifting the standard
 characteristic value by one position. At each shifted position, a
 difference between a pair of the corresponding two characteristic values
 is summed. The least difference is considered to be the distance for a
 circumference. In a preferred process according to the current invention,
 the above described shifting is minimized by shifting near a rotational
 angle. For example, if a rotational angle is 30 degrees, the values are
 shifted within a limited range from position 2 to position 6. This limited
 shifting saves both time and memory space.
 Now referring to FIG. 24, a number of pixels in determining a distance is
 illustrated for an exemplary set of 16 circumferences. For example,
 circumference No 7 has a radius of 28 pixels while its circumference has a
 160-pixel length. For this circumference data to be shifted by 9 pixels in
 total, the amount of total calculation is reduced to almost 5%.
 It is to be understood, however, that even though numerous characteristics
 and advantages of the present invention have been set forth in the
 foregoing description, together with details of the structure and function
 of the invention, the disclosure is illustrative only, and that although
 changes may be made in detail, especially in matters of shape, size and
 arrangement of parts, as well as implementation in software, hardware, or
 a combination of both, the changes are within the principles of the
 invention to the full extent indicated by the broad general meaning of the
 terms in which the appended claims are expressed.