Abstract:
Computer apparatus and method in a computer system provides shape matching. A template of a desired shape is matched to a subset of points in a subject image. The matching is determined according to an arbitrarily complex function of image point values and template point values followed by an arbitrary operation on the plurality of results of the arbitrarily complex function. In the case of fuzzy template matching, the operation is the average preferably followed by clipping to the range [0, 1] for defining fuzzy membership values. The arbitrarily complex function may be formed of a discrete array of single variable functions or single variable lookup tables.

Description:
GOVERNMENT SUPPORT 
     The following was supported by DARPA TTO under contract number F19628-90-C-0002. Under this contract the U.S. Government has certain rights to the present invention. 
    
    
     This is a continuation of co-pending application Ser. No. 07/675,311, filed on Mar. 26, 1991, now abandoned. 
    
    
     BACKGROUND OF THE INVENTION 
     As used herein &#34;f(x)&#34;, refers to a general class of n dimensional signals or value measurements (e.g. light intensity, voltage level, temperature, height, weight, etc.) where x=(x 1 , . . . x n ) is a vector in n dimensional space. Although applicable to arbitrary values of n, the following discussion assumes n=2 for ease of illustration and comprehension. In this simpler context, f(x) is a function defined over the usual (x,y) plane, and f is referred to as an image, even in the case where x and y take continuous (non-discrete) values. Thus, x refers to some location in an image. In the discretized case, x refers to a particular pixel in a real image. 
     In addition, &#34;g(y)&#34; refers to a class, generally preestablished, of n dimensional values where y=(y 1 , . . . y n ) is a vector in n dimensional space. In particular, g(y) serves as a standard against which f(x) is measured for purposes of image processing, and especially pattern matching as discussed next. 
     A large class of image processing operations involve moving a &#34;kernel&#34; g (variously called a window, template, or stencil) over an image f and performing an operation on the pairs of points that are superimposed at each relative displacement of f and g. This is illustrated in FIG. 1, where the point in f being probed is x. The kernel is positioned over the image such that the kernel origin (or reference point) coincides with x. Each point y of g, is defined with respect to the kernel origin. The set of points over which g is defined is denoted by Ros(g), i.e. region of support of g. Note that Ros(g) may be a rectangle as shown in FIG. 1 or the set of points defining a more complex shape (as shown in FIG. 2). In FIG. 1 it is clearly seen that a kernel point y coincides with the image point x+y. Consequently, the pairs of values to be considered at each point y ε Ros(g) are f(x+y) and g(y). 
     This common framework is employed by three traditional shape matching techniques: template matching by cross correlation, function mathematical morphology (MM) dilation, and function MM erosion. In each case, the value of g have the same dimensionality as the values of f (e.g., f and g may both have units of temperature, range, etc.). In the following equations, ⊕ and ⊖ are the symbols for Minkowski addition and Minkowski subtraction, respectively. The symbol g indicates the symmetric function of g, i.e., g(x)=g(-x). 
     In cross correlation, the values f(x+y) and g(y) considered at each kernel point y ε Ros(g) are multiplied, and the sum (or integral) of the f and g value pair products defines the final outcome of the template matching. Restated as an equation, cross correlation matching, i.e. cc(x), is defined as follows: ##EQU1## 
     In function MM dilation, the values f(y+y) and g(y) considered at each kernel point y ε Ros(g) are summed together, and the maximum f and g value pair sum defines the final outcome of the template matching. Expressed as an equation, function MM dilation matching, i.e. md(x), is defined as follows: 
     
         md(x)=[f⊕g](x)=MAX.sub.y {f(+y)+g(y)}, yεRos(g). Equation 2 
    
     In function MM erosion, the difference of the values f(x+y) and g(y) considered at each kernel point y ε Ros(g is computed, and the minimum f and g value pair difference is used as the final outcome of the template matching. The equation defining function MM erosion, i.e. me(x), reads: 
     
         me(x)=[f⊖g](x)=MIN.sub.y {f(x+y)-g(y)}, yεRos(g). Equation 3 
    
     One disadvantage of template (kernel) matching by cross correlation and MM is that these methods are easily confounded by distortions of shapes within images due to a variety of causes e.g., noise, occlusion (i.e., obscuration), articulation (of shape parts), etc. In the case of noise, methods for reducing noise in images are known but also change those portions of original image data which are noise free. Thus, such image noise reduction methods create a further loss in integrity in image processing. 
     Despite the lack of robustness, template matching by cross correlation has found application in the recognition of printed characters and the inspection of printed circuit boards (see A. K. Jain, Fundamentals of Digital Image Processing, New Jersey: Prentice-Hall, Inc., 1989, p. 402), and edge detection in medical images. And despite similar limitations, MM is a widely used tool for image processing (see J. Serra, Image Analysis and Mathematical Morphology, New York: Academic Press, 1982). 
     A further disadvantage of the existing template matching techniques, especially in image processing, is the computational expense in terms of processing time. 
     Accordingly there is a need for more efficient and robust shape matching apparatus and/or method. 
     SUMMARY OF THE INVENTION 
     The present invention provides a shape matching method and apparatus which overcome the problems of prior art. In particular, the present invention provides a generalized template matching computer method and apparatus which employ arbitrarily complex relationships between working pair values of f(x+y) and g(y) instead of the standard operations (i.e. *, +, or -) used in the prior art. Through careful design of the arbitrarily complex relationships, templates of the preferred embodiment can perform object recognition, feature extraction, or shape filtering under conditions not possible, or at best very difficult, with shape/template matching tools of the prior art. These conditions include: 
     1. Noisy sensors. 
     2. Uncertainty in image values. 
     3. Partial object occlusion. 
     4. Articulated objects. 
     5. Objects that may appear in multiple configurations. 
     Further, preferred embodiment templates for some objects are constructed with sufficient detail to accomplish reliable object recognition directly from pixel-level data. Consequently, for some applications, very simple computer vision systems with only a few processing steps are possible, saving software development time and software errors inherent in managing complex programs. In addition, the simplicity of the present invention template processing makes it particularly suited for massively parallel implementation. Furthermore, expense may be markedly reduced by implementing the arbitrarily complex relationships as lookup tables, and by using masks constructed with a prior knowledge of objects and scenes to avoid probing pixels that are unlikely locations for objects. 
     In a preferred embodiment of the present invention computer apparatus for shape matching is employed in a computer system. In particular, a template of a desired shape is coupled to a digital processor. The template has a plurality of points, each point having a predetermined value. A subject image is held in a working memory area of the digital processor. The subject image is formed of a plurality of points, each point having a respective measurement value. Processor means executable by the digital processor match shape of the template to a subset of points of the subject image held in the working memory area. Said matching generates an output image having a plurality of points, each output image point having a respective value. 
     Specifically, for each point in the subject image the processor means determines a corresponding point in the output image according to an arbitrarily complex function. In one embodiment, the template provides, for each template point, an arbitrarily complex function for use by the processor means to determine output image points values. The processor means employs a parameter pair to call (i.e., as input to) the arbitrarily complex function. The parameter pair is formed of one image point measurement value and one template point generally predetermined value. Thus, for each subject image point, the processor means determines value of a corresponding output image point according to an arbitrarily complex function of measurement values of a subset of points in the subject image and generally predetermined values of points in the template. 
     In a preferred embodiment, the arbitrarily complex function is formed of a plurality of single variable functions, one function for each possible predetermined value of a template point. Other single variable functions are suitable. Further the processor means determines a corresponding output image point according to an arbitrarily complex operation on a multiplicity of results from the arbitrarily complex function. Preferably the operation includes a mathematical average of the results from the arbitrarily complex function over the number of points in the template. In addition, preferably the operation generates an output image point value in the range 0 to 1, or a range of numbers mapped to the range [0, 1]. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     The foregoing and other objects, features and advantages of the invention will be apparent from the following more particular description of preferred embodiments of the invention, as illustrated in the accompanying drawings in which like reference characters refer to the same parts throughout the different views. The drawings are not necessarily to scale, emphasis instead being placed upon illustrating the principles of the invention. 
     FIG. 1 is a schematic illustration of template matching in the prior art. 
     FIG. 2 is a schematic illustration of the present invention shape matching. 
     FIGS. 3a through 3b are a block diagram and flow chart respectively of a computer system embodiment of the present invention. 
     FIG. 4 is a schematic illustration of a template g for processing an elongated object in the present invention. 
     FIGS. 5a through 5c are graphs of scoring functions used for various values along the b axis of the embodiment of FIG. 2. 
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS 
     By way of overview, Applicants have recognized that the lack of robustness in prior template matching techniques stems from the use of only standard operations (*, +, or -) in the relationships between pair values of f(x+y) and g(y) per kernel or image position x. To that end, the present invention provides a user definable function s(a, b) to define arbitrarily complex relationships between f and g values, where operand a equals the value of f(x+y) and operand b equals the value of g(y). Function s is referred to as the scoring function of the present invention. 
     In turn, the present invention defines a generalized form (equation) of template matching hereinafter called &#34;shape matching&#34;, sm(x), in terms of the arbitrarily complex function s as follows: 
     
         sm(x)=O.sub.y {s(f(x+y),g(y))}, yεRos(g).          Equation 4 
    
     This equation states that the operator O processes the set of values produced by the 2-D function s as y explores Ros(g). It is noted: 
     1. For O≡Σ and s(a,b)=ab, Eq. 4 reduces to Eq. 1. 
     2. For O≡MAX and s(a,b)=a+b, Eq. 4 reduces to Eq. 2. 
     3. For O≡MIN and s(a,b)=a-b, Eq. 4 reduces to Eq. 3. 
     However, replacing prior art standard operations (i.e. *,+,or -) on a and b with the present invention scoring function s(a,b) allows for the definition of arbitrarily complex relationships between values of f(x+y) and g(y). The power of this approach is discussed next in a general application of the present invention illustrated in FIGS. 2 through 3b. Following that discussion is a specific application of the present invention described with reference to FIGS. 4 through 5c. 
     Referring to FIG. 2, a subject input image is generally shown at 15. The image input is two-dimensional and lies in the x1-x2 plane illustrated in FIG. 2. For each point or position in the image 15, there is an associated value defined by f(x) and indicated along an axis orthogonal to the xl and x2 axes. Illustrating the input image f 15 in this manner allows for various cases of image input signals from video signals to radar signals, where the values of f(x) are temperature measurements, linear dimension measurements, mass measurements and the like. That is, this approach allows for n-dimensional image input signals. 
     A template g 19 is applied to the input image 15 one image point x at a time. In particular, the template g 19 defines a region in the x1&#39;-x2&#39; coordinate system which is designated Ros(g), i.e. the region of support of g. The region is formed of a reference point referred to as the template origin 22 and a plurality of points y spaced from the template origin 22. For each point in the region of support of the template g 19, there is a value defined by g(y) and indicated along an axis orthogonal to the x1&#39; and x2&#39; axes. 
     Operation of the template g 19 on an input image 15 is then as follows and outlined in FIG. 3b. For a given point x in the input image 15, the template g 19 is positioned such that the template origin 22 corresponds with the position of the subject point x in the x1-x2 plane. This step is indicated at 47 in FIG. 3b. For each point y in the region of support of template g 19, the values of f(x+y) and g(y) are obtained. A variable &#34;a&#34; is then set equal to the obtained value of f(x+y), and variable &#34;b&#34; is set equal to the obtained value of g(y) as shown at 49 in FIG. 3b. Variables a and b are then used as operands in the scoring function s(a,b). That is, a call to the scoring function s 21 with the assigned values of a and b is made and produces a scoring function value. This is illustrated in FIG. 2 where the input variables a and b are indicated along respective axes a and b of the scoring function s 21 and the resulting function value is indicated along an axis perpendicular to the a and b axes. 
     This resulting s function value is stored in a buffer 31 (FIG. 3a) and the foregoing calculations of f(x+y), g(y) and s(a,b) where a=f(x+x) and b=g(y) are repeated for each point y in the region of support of the template g 19. As a result, for each yε Ros(g) there is a resulting scoring function value held in the buffer 31. The multiplicity of values held in the buffer 31 are then operated on by an operation O such as a mathematical average, the maximum, or the minimum, or the like as shown at 51 in FIG. 3b. The outcome of the operation O provides the value of a output image point x o  corresponding to the given input image point x. The template 19 is similarly applied to each point x in the input image 15 to produce, through scoring function s and ultimately operation O, values for corresponding points x o  in the output image 17. To that end template g, scoring function s and operation 0 define output image 17 from a subject input image 15. From the output image 17, various patterns and shapes are presented as recognized or matched in the input image 15 with respect to the template g. 
     FIGS. 3a and 3b provide a block diagram and flow chart of computer software and/or hardware implementation of the present invention. FIG. 3b is discussed above and FIG. 3a is discussed next. In particular, FIG. 3a schematically diagrams an embodiment of the present invention as held in memory of a digital processor 45 of a computer system. The invention embodiment includes a working memory area 39 for receiving and holding an image f from an image source. Another memory area 41 holds a predetermined template g. Template g is applied to the image f held in the working memory 39. This in turn generates output values g(y) from the template memory 41 and values f(x+y) from the working memory 39. The two output values are used as inputs to the scoring function held in a register 37 or similar computational memory area (e.g. module, routine or procedure) of the digital processor 45. The output of the s function register 37 is held in a buffer 31. Under the control of counting circuit 33, buffer 31 stores the outputs of the s function register 37 for each y in the region of support of template g, for a given x placement of template g. After a last point y in the region of support of template g, the counting circuit 33 applies the values stored in buffer 31 to the O operation module 35. Output of O operation module 35 is then used to define the point x o  in the output image 17 held in memory area 43 and corresponding to the subject point x in the input image held in working memory 39. As formed by the foregoing steps, the output image is held in the memory area 43 in a manner which is accessible by the digital processor 45 for display on a display unit or similar output means. 
     In a preferred embodiment, fuzzy set theory is incorporated with the present invention shape matching described for general application in FIGS. 2 through 3b.  By way of background, in classical set theory, membership of an object in a set is denoted either by a 0 or 1. In practice, however set membership is not a binary, either/or condition. To extend the functionality of set theory L. A. Zadeh in &#34;Fuzzy Sets&#34; Information and Control No. 3, Vol. 8, June 1965, pages 338-353, introduced the idea of representing set membership as a real number in the range [0,1], permitting varying degrees of membership reflecting uncertainty or contradiction. Fuzzy set membership is calculated by a membership function f A  (x) returning a value in the range [0,1] for a given object x, and representing the &#34;A-ness&#34; of object x. The use of fuzzy set theory has exploded in the last few years, being used extensively, for example, in computer vision, control processes, and artificial intelligence. 
     In the present invention, a fuzzy template kernel g (described later) is constructed to encode the shape of an object to be sought in image f. In this technique, the scoring function s is implemented as a discrete array of indexed scoring functions, each of which, given a value of f(x+y), returns a match score. As later discussed, individual slices of s for a particular index m (m being a point along the b axis in FIG. 2) are denoted by s m  (a) as an alternative way of expressing s(a,m). The kernel g can then be thought of as a set of labels (or values of m) that specify particular indexed scoring functions appropriate for different locations on the object. In the preferred embodiment, the O operation is the average over points yεRos(g) and the final output (defining an output image) is defined according to the following two equations. First ##EQU2## where n is the number of pixels in the Ros(g) and O≡ ##EQU3## denotes mathematical average over points y. Typically, the values returned are at this point approximately in the range [0,1]. However, for several practical reasons, the values returned by each s m  are not restricted to the range [0,1]. Consequently, the value of m(x) cannot be guaranteed to be in the range [0,1] and needs to be clipped: ##EQU4## The final output is an image whose values are each a fuzzy membership score representing the degree of belief that the shape encoded in the fuzzy template g is found at each input image location x. 
     Given the possibility that the shape represented by a template may be scaled or rotated in the image, the fuzzy membership score may need to be computed with copies of the template that have been appropriately scaled or rotated. Equation 6 handles only the case of scale and rotation invariance. Situations where the shape to be searched in an input image is unconstrained with regard to scaling requires the construction of multiple templates from which a most appropriate copy is selected for probing a particular location x, depending on the distance to that location. Similarly, situations where the orientation is unconstrained requires the use of multiple templates, each representing a different orientation. In this case, the membership value assigned to a location in the output image is the maximum membership value across all orientations tested. 
     The following example illustrates the construction and use of fuzzy template correlation in automatic recognition of targets in downlooking laser radar range and intensity images. The scoring functions for the range image use height above ground as the independent variable. 
     A simple template 60 for an elongated object (a crude model of a semi-truck) with expected height of 3.0 m is constructed as follows and shown in FIG. 4. First, the template function g is constructed as an array of indices (FIG. 4), where 1&#39;s indicate the top of the object, 2&#39;s indicate locations where ground values are expected, and n indicates a location of uncertainty where no scoring function should be evaluated (i.e., not in the region of support). 
     Then, consider FIG. 5a as the indexed scoring function s 1  (a), i.e., s(a,1) of FIG. 2, for the surface expected to be 3.0 m above ground. Image height values in the neighborhood of 3.0 m return a maximum score of 1.0. The width of the maximal scoring interval can be adjusted to adapt to such conditions as sensor accuracy or the variability of surface height found in various instances of the target class. For height values from 2.5 down to 1.5 m, the scoring function returns progressively lower values, reflecting the decreasing confidence that the image height matches the expected surface height. Below 1.5 m, the function s 1  returns negative values (the need for negative values is explained later). A similar drop off is evident with heights above 3.5 m. Note however that the minimum returned value for heights above the expected surface height is 0.5, a completely ambiguous score reflecting the fact that surfaces with heights above 3.0 m may be occluding the object. Consequently, a sufficiently large surface that is 5.0 m above ground will elicit a target membership score of 0.5, reflecting the possibility that the target might be totally concealed underneath. 
     FIG. 5b shows the indexed scoring function s 2  (a), i.e., s(a,2) of FIG. 2, which encodes the scores for ground values surrounding the target (in practice, one treats the ground surface in the immediate vicinity of an object as a part of the object). Maximal scores are returned for values within 0.25 m of ground, intermediate scores out to 0.5 m and an ambiguous score of 0.5 for heights above 0.5 m (again, accommodating possibly occluding surfaces). 
     The reason the present invention permits negative numbers to be returned from the height distribution (scoring) function as shown in FIG. 5a is related to the practice of including neighboring ground as part of the target in the fuzzy template. Preferably, the situation that generates a fuzzy membership value of 0.0 is a patch of bare ground (by definition, ground height=0). However as is evident in FIG. 5b, locations in the template where ground is expected return a value of 1.0. Looking again at FIG. 4, consider what would happen if that template were superimposed on a uniform area of bare ground. All template locations with index 0 would return a score of 1.0. Consequently, in order for bare ground to result in a score of 0.0, s 1  (a) must return sufficiently negative scores for an input height=0 to balance the positive scores contributed by s o  (a). 
     One further example of an indexed scoring function illustrates how object articulation or multiple object configurations can be handled. Consider a tank with an elongated turret. Assume that the hull height is 1.5 m and the turret height is 3.5 m. Some locations on the hull near the turret may or may not be occluded depending on the turret azimuth. FIG. 5c contains a bimodal height distribution for such a location near the turret: one maximum scoring range corresponds to the height of the turret, the other maximum scoring range corresponds to the height of the hull. In particular, FIG. 5c shows a scoring function for a location of an articulated object &amp;with two possible surfaces at 1.5 m and 3.0 m above ground. 
     Although range information is generally necessary for purposes of scaling, scoring functions can accommodate sensory modalities other than height as long as reasonably accurate range information is available. For example, thermal distribution functions may be used as scoring functions to process passive infrared images. 
     According to the foregoing, in situations where the effects of scaling or rotation can be minimized and the number of objects to be searched for is small, the present invention (functional shape matching in general and fuzzy template correlation in particular) is already computationally practical. The fuzzy template correlation embodiment of the present invention works best in situations where the objects to be modeled are either rigid or are articulated with rigid parts having known pivot points. Fuzzy template correlation excels in its ability to perform shape matching in images containing significant amounts of clutter and/or occlusion (i.e. natural scenes) and for objects that have an uncertain or variable image signature. 
     The following is an incomplete list of possible commercial (non-military) applications for fuzzy templates of the present invention: 
     1. Low level vision tools: Traditional shape matching techniques are currently used in image processing for such things as edge detection, image segmentation, and feature extraction. A likely possibility is that wherever these techniques are already in use, fuzzy templates have the potential of doing it better. 
     2. Visual inspection: 
     (a) Quality control of manufactured items (e.g., printed circuit boards). 
     (b) searching for concealed weapons in carry-on luggage at airports. 
     3. Free moving robots/autonomous navigation systems. 
     4. Visual feedback for process control. 
     5. Character (or pattern) recognition. 
     6. Medical imaging. 
     Equivalents 
     While the invention has been particularly shown and described with reference to a preferred embodiment thereof, it will be understood by those skilled in the art that various changes in form and details may be made therein without departing from the spirit and scope of the invention as defined by the appended claims. 
     For example multiple templates g may be employed for processing multiple measurements (i.e. height, temperature, weight, etc.) at the same time through data fusion. Further two templates g may be employed for articulating subjects in that case, a first (dominant) template is employed to recognize a main portion of the input image. From the main portion a pivot point is determined. The second template is then employed to recognize/detect the articulating portion of the subject out of image portions within the pivoting range of the determined pivot point. 
     Functions g and s could be modified as a function of the location x being probed. The modification can be specified a priori by specifying g and s as the 2-dimensional function g(x, y) and the 3-dimensional function s(x, a, b), respectively (this processing strategy is usually termed &#34;space-variant&#34;). The modification can also be determined dynamically by adjusting g and s as a function of the values of the image f in some neighborhood of x (this processing strategy is usually termed &#34;adaptive&#34;). More generally, the functions g and s could be modified arbitrarily as each location x in f is probed.