US 5,982,934 AGrant

System and Method for Distinguishing Objects

Issue Date:1999-11-09

•76 Claims

•7 Drawing Sheets

Abstract

A method and system are provided for distinguishing objects. Signals representative of the objects are input. From the signals, measurements of multiple types are acquired. At least one of the measurement types is continuously variable. In response to the measurements, respective amounts of mutual information of the measurement types are determined. In response to the respective amounts of mutual information, at least one measurement type is selected for evaluation in distinguishing the objects.

Metadata

Assignee

Texas Instruments Incorporated

Inventor

Michael Joseph Villalba

Application Information

Application Number:US 8038481

Filing Date:1997-02-28

Priority Date:1992-06-30

Art Unit:273

Classifications

IPC:

G06K 968

Field of Search:

382203;209;226;227;228;103;205

Patent Drawings (7 sheets)

Description

Background of the Invention

Various types of signals are processed. In voice signals, amplitude values are typically a function of time. In image signals, pixel intensity values are typically a function of (x,y) coordinates in an image. Such signals can be processed to distinguish one or more objects represented in the signals. For example, amplitude values in voice signals can be processed to distinguish objects such as spoken words represented in the voice signals. Similarly, pixel intensity values in image signals can be processed to distinguish one or more target objects represented in the image.

Such objects can be distinguished by processing the signals to acquire various types of measurements. The acquired measurements are evaluated relative to known measurements ("features") of objects in order to distinguish an object as being either represented or not represented in the signals. In evaluating acquired measurements, efficiency is desirably increased by selecting the acquired measurements for evaluation in an optimal order, so that uncertainty regarding the object's representation is eliminated in a short amount of processing time.

According to many previous techniques, a human developer manually selects measurements for evaluation, relying upon the human developer's subjective intuition concerning the manner in which acquired measurements relate to the goal of distinguishing objects. Nevertheless, such introspective techniques might have poor effectiveness if acquired measurements are difficult to relate to the goal of distinguishing the object. For example, it is difficult to intuitively relate the raw signal output from a naval inverse synthetic aperture radar ("ISAR") to target objects for recognition.

In some previous techniques, predefined types of measurements are always evaluated. A shortcoming of such techniques is that they fail to adapt to a recognition domain by selecting measurements for evaluation according to each measurement's usefulness. A recognition domain includes the signal acquisition device, signal environment, available measurement types, and objects to be distinguished. Essentially, such previous techniques have relatively poor efficiency and poor robustness, because they evaluate measurements according to a preconceived recognition strategy rather than by adapting to the recognition domain. Moreover, such previous techniques are frequently ineffective at distinguishing among a large number of different objects.

Certain previous techniques use a binary decision tree having one or more nodes each specifying an associated measurement for evaluation. Each node has only two branches separated by a single associated threshold value. As the binary decision tree is traversed, one of a node's two branches is specified in response to an evaluated measurement either satisfying or failing to satisfy the single threshold value. Often, it is desirable to represent more than two values for a measurement. In this case, the binary decision tree uses more than one node to represent the measurement's value. For example, a measurement for which it is desirable to represent three values would require two binary nodes.

By requiring more than one node to represent such a measurement's value, binary decision trees inefficiently occupy additional system memory, and additional processing time is consumed in traversing the binary decision tree. Accordingly, binary decision trees fail to select a suitable number of branches by adapting to a recognition domain. Likewise, binary decision trees fail to select suitable threshold values associated with the suitably selected number of branches by adapting to the recognition domain.

In response to available measurements, it might be impractical to distinguish objects in an absolutely reliable manner. In such cases, some previous techniques fail to provide a sufficiently accurate estimate of their reliability in distinguishing objects in response to available measurements.

Also, some previous techniques fail to provide a sufficiently accurate estimate of a measurement's probability of having a value within a specified range.

Thus, a need has arisen for a method and system for distinguishing among a large number of different objects in an efficient and robust manner. A need has also arisen for a method and system for distinguishing objects in a short amount of processing time. A further need has arisen for a method and system for distinguishing objects, in which system memory is efficiently occupied. Moreover, a need has arisen for a method and system for distinguishing objects by adapting to a recognition domain. Another need has arisen for a method and system for distinguishing objects, in which a sufficiently accurate estimate is provided of reliability in distinguishing objects in response to available measurements.

Also, a need has arisen for a method and system for distinguishing objects, in which measurements are objectively selected for evaluation in an optimal order. Further, a need has arisen for a method and system for distinguishing objects, in which measurements are selected for evaluation according to each measurement's usefulness by adapting to a recognition domain. An even further need has arisen for a method and system for distinguishing objects, in which measurements are effectively selected for evaluation even if introspection is difficult.

Additionally, a need has arisen for a method and system for distinguishing objects, in which more than two possible measurement values are represented in an efficient manner. Yet a further need has arisen for a method and system for distinguishing objects, in which a suitable number of branches is selected for a node of a decision tree, and in which one or more suitable threshold values associated with the suitably selected number of branches are selected by adapting to a recognition domain.

Finally, a need has arisen for a method and system for providing a sufficiently accurate estimate of a measurement's probability of having a value within a specified range.

Summary of the Invention

It is a technical advantage of the present invention that a large number of different objects are distinguished.

It is another technical advantage of the present invention that objects are distinguished in an efficient and robust manner.

It is a further technical advantage of the present invention that objects are distinguished in a short amount of processing time.

It is yet another technical advantage of the present invention that system memory is efficiently occupied.

It is yet a further technical advantage of the present invention that objects are distinguished by adapting to a recognition domain.

In another technical advantage of the present invention, a sufficiently accurate estimate is provided of reliability in distinguishing objects in response to available measurements.

In a first aspect of a method and system for distinguishing objects, signals representative of the objects are input. From the signals, measurements of multiple types are acquired. At least one of the measurement types is continuously variable. In response to the measurements, respective amounts of mutual information of the measurement types are determined. In response to the respective amounts of mutual information, at least one measurement type is selected for evaluation in distinguishing the objects.

It is a technical advantage of this aspect that measurements are objectively selected for evaluation in an optimal order.

It is another technical advantage of this aspect that measurements are selected for evaluation according to each measurement's usefulness by adapting to a recognition domain.

It is a further technical advantage of this aspect that measurements are effectively selected for evaluation even if introspection is difficult.

In a second aspect, in response to the measurements, a continuously variable measurement type is quantized into a number of intervals selected in response to mutual information of the quantized continuously variable measurement type. In response to the quantized continuously variable measurement type, at least one measurement from a set of signals is evaluated for distinguishing at least one of the objects as being represented in the set of signals.

It is a technical advantage of this aspect that more than two possible measurement values are represented in an efficient manner.

It is another technical advantage of this aspect that a suitable number of branches is selected for a node of a decision tree by adapting to a recognition domain.

It is a further technical advantage of this aspect that one or more suitable threshold values associated with the suitably selected number of branches are selected by adapting to a recognition domain.

In a third aspect, a probability density of a measurement type is determined. Signals are input. From the signals, measurements of the measurement type are acquired. In response to the measurements, kernels are formed. Each kernel is associated with one of the measurements. Each kernel has a respective size selected in response to ones of the measurements in a locality of the associated measurement. The probability density is determined in response to the kernels.

It is a technical advantage of this aspect that a sufficiently accurate estimate is provided of a measurement's probability of having a value within a specified range.

Brief Description of the Drawings

For a more complete understanding of the present invention, and the advantages thereof, reference is now made to the following descriptions taken in conjunction with the accompanying drawings, in which:

FIG. 1 illustrates an exemplary set of objects to be distinguished as being either represented or not represented in a set of signals;

FIG. 2 illustrates a sensor carried by a platform located on an aircraft;

FIG. 3 is a block diagram of process circuitry of the preferred embodiment;

FIGS. 4a-b are exemplary images of a target object to be distinguished as being represented in image signals sensed by the sensor of FIG. 2;

FIG. 5 illustrates an exemplary n-ary decision tree formed by process circuitry of FIG. 3 to specify measurements for evaluation in an optimal order;

FIGS. 6a-b are exemplary graphs of object probability versus object type for different types of objects in an object set;

FIGS. 7a-c are exemplary graphs of object probability versus object type, conditioned on given values of different measurement types;

FIG. 8 is a flow chart of the technique of the preferred embodiment by which process circuitry of FIG. 3 forms an n-ary decision tree;

FIG. 9 is a flow chart of the technique of the preferred embodiment by which process circuitry of FIG. 3 recursively selects measurements for evaluation at measurement nodes of an n-ary decision tree;

FIG. 10 is a flow chart of the technique of the preferred embodiment by which process circuitry of FIG. 3 selects a number of quantization thresholds and associated threshold values at a measurement node of an n-ary decision tree;

FIG. 11 is an exemplary graph of quantized mutual information;

FIG. 12a is an exemplary plot of kernels selected by process circuitry of FIG. 3;

FIG. 12b is a plot of a probability density function estimate formed by combining kernels of FIG. 12a into a single continuous curve;

FIG. 13a is a plot of a probability density curve;

FIG. 13b is a plot of a continuous probability density curve representing a probability density function estimated by process circuitry of FIG. 3; and

FIGS. 14a-b are plots of continuous probability density curves representing probability density functions estimated by process circuitry of FIG. 3.

Detailed Description of the Invention

The preferred embodiment of the present invention and its advantages are best understood by referring to FIGS. 1 through 14 of the drawings, like numerals being used for like and corresponding parts of the various drawings.

FIG. 1 illustrates an exemplary set, indicated generally at 20, of twenty objects numbered 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18 and 19, to be distinguished as being either represented or not represented in a set of signals. Although all objects in set 20 are aircraft target objects to be distinguished in a set of image signals, set 20 can include any type of object (such as a spoken word) to be distinguished as being either represented or not represented in any type of signal (such as voice signals). Moreover, set 20 can include other types of target objects such as terrain obstacles, ground targets and enemy weapons.

Further, set 20 can include ground objects such as crop types, rivers, mountains and other elements. Such ground objects can be represented in image signals sensed by an earth resource satellite sensor located aboard an earth orbiting satellite. Also, set 20 can include character objects to be distinguished in typed or handwritten text after optical scanning. Similarly, set 20 can include fingerprint or face patterns to be distinguished by a security system.

FIG. 2 illustrates a sensor 22 carried by a platform 24 located on an aircraft 26. Alternatively, platform 24 can be located on any type of moving vehicle such as a tank, or can be located at a stationary site. In FIG. 2, sensor 22 is a forward looking infrared ("FLIR") sensor. Aircraft 26 further includes process circuitry 28 connected to sensor 22 by electrical path 30.

Sensor 22 by inputting circuitry senses signals for processing by process circuity 28 to distinguish one or more objects as being either represented or not represented in the signals. As shown in FIG. 2, sensor 22 and process circuitry 28 form an automatic target recognition ("ATR") system where process circuitry 28 distinguishes one or more of target objects 0-19 (FIG. 1) as being either represented or not represented in image signals sensed by sensor 22.

In an exemplary alternative embodiment, sensor 22 can be a microphone for sensing voice signals. In such an alternative embodiment, process circuitry 28 and sensor 22 form a voice recognition system, where process circuitry 28 distinguishes one or more spoken words as being either represented or not represented in voice signals sensed by sensor 22.

FIG. 3 is a block diagram of process circuitry 28. Process circuitry 28 includes a processor 32 programmed in accordance with the preferred embodiment for distinguishing one or more objects. Processor 32 is connected to non-volatile storage circuitry 34, such as a battery backed static random access memory ("SRAM"). Storage circuitry 34 stores instructions and other digital data used by processor 32 in distinguishing objects. Processor 32 reads digital data and instructions from storage circuitry 34, as needed, to distinguish one or more objects. Moreover, processor 32 writes digital data to storage circuitry 34 so that results of the object distinguishing process are stored in a non-volatile manner. The object distinguishing process is described further hereinbelow in connection with FIGS. 4-14.

Processor 32 is further connected to fast-access memory circuitry 36, such as a dynamic random access memory ("DRAM"). Memory circuitry 36 inputs, stores and outputs instructions and other frequently accessed data as directed by processor 32 during the object distinguishing process. By storing such frequently accessed data in memory circuitry 36 instead of in storage circuitry 34, speed of the object distinguishing process is increased. A human operator (not shown) can specify commands and data to processor 32 using a keyboard 38. A digitizer 40 inputs signals from sensor 22 (FIG. 2). After inputting signals from sensor 22, digitizer 40 translates the signals into digital data for output to processor 32. In response to the digital data from digitizer 40, processor 32 distinguishes one or more objects and displays results of the object distinguishing process on a display 42.

With advances in very large scale integration ("VLSI") technology and military computing hardware, special purpose parallel architectures can be used for real-time processing. Accordingly, in response to distinguishing a target object, processor 32 outputs digital data to display 42, so that a human operator (not shown) in aircraft 26 (FIG. 2) is notified that a distinguished target object was within view of sensor 22. The human operator can take action to evade or debilitate a target object distinguished by process circuitry 28 as being potentially dangerous, such as a ground obstacle or an enemy weapon. In an alternative embodiment, processor 32 outputs digital signals to special purpose hardware (not shown) for automatically taking action to evade or debilitate the potentially dangerous target object.

In order to quickly evade or debilitate a target object distinguished as being potentially dangerous, it is desirable to perform the object distinguishing process in a fast and reliable manner. If the object distinguishing process is slow or inaccurate, then the potentially dangerous target object might be considerably outside the view of sensor 22 before suitable evasive or debilitating action can be taken.

FIG. 4a is an exemplary image 44 of a target object, indicated generally at 46. Target object 46 is distinguishable as representing target object 12 of FIG. 1. Image 44 is synthetically generated and embedded in 30% binary white noise. Referring also to FIG. 3, image 44 is illustrative of an image represented by digital data output from digitizer 40 to processor 32. In FIG. 4a, such digital data specifies which (x,y) coordinate pixels of image 44 are black. Processor 32 inputs such digital data from digitizer 40 after digitizer 40 translates image signals from sensor 22.

After processor 32 inputs such digital data from digitizer 40, processor 32 directs display 42 to display image 44. Also, processor 32 processes image 44 to identify a region of image 44 that substantially includes target object 46. An exemplary technique for identifying such a region is to isolate the largest continuously connected set of pixels ("pixel set") within image 44. FIG. 4b is an image 48 of such a pixel set 50 that substantially includes target object 46. As shown in FIG. 4b, the binary white noise of image 44 is substantially eliminated by displaying only pixel set 50 in image 48. Alternatively, any suitable segmentation technique can be used to identify a region of image 44 that substantially includes target object 46.

After processor 32 identifies pixel set 50 of image 48 as a region of image 44 that substantially includes target object 46, processor 32 further processes image 48 to acquire various types of measurements. Appendix I describes 149 exemplary types of measurements acquired by processor 32 in response to an image such as image 48 of FIG. 4b. The measurement types described in Appendix I are characteristic, to varying degrees, of objects in an automated target recognition domain.

In an important aspect of the preferred embodiment, process circuitry 28 is adaptable to any recognition domain. Accordingly, process circuitry 28 alternatively can acquire suitable types of measurements in response to an image (such as image 44 of FIG. 4a), without having to first identify a region (such as pixel set 50 in FIG. 4b) that substantially includes target object 46. Similarly, in the recognition domain of distinguishing spoken words in voice signals, process circuitry 28 processes voice signals in order to acquire suitable types of measurements that are characteristic, to varying degrees, of one or more word objects to be distinguished.

In yet another exemplary recognition domain, object situations are distinguished. For example, if only a single target object (such as target object 12 in FIG. 1) is to be recognized as being represented in image signals, then process circuitry 28 essentially distinguishes two object situations, namely a first object situation where the single target object is represented in the image signals, and a second object situation where the single target object is not represented in the image signals.

In another example of distinguishing object situations, process circuitry 28 processes signals sensed from a heart patient in order to acquire characteristic measurements such as blood pressure, pulse and temperature. Process circuitry 28 evaluates such measurements to distinguish object situations, such as a health condition of the heart patient. In response to a distinguished object situation, an appropriate course of action is identifiable for treating the heart patient.

Referring again to FIG. 4a, target object 46 is distinguishable as representing target object 12 of FIG. 1. Accordingly, in response to the signals from sensor 22, process circuitry 28 by acquiring circuits acquires measurements (such as measurements 0-148 of Appendix I) from the signals, and distinguishes target object 12 as being represented in the signals by evaluating the acquired measurements.

In evaluating acquired measurements, process circuitry 28 desirably increases efficiency through selecting circuitry by selecting acquired measurements for evaluation in an optimal order, so that uncertainty regarding the object's representation is eliminated in a short amount of processing time. Such a technique for selecting measurements for evaluation is effective, even if introspection is difficult.

FIG. 5 illustrates an exemplary n-ary decision tree, indicated generally at 52, of the preferred embodiment, which is formed by process circuitry 28 to specify measurements for evaluation in an optimal order. In the preferred embodiment, a decision tree (such as decision tree 52) is formed by process circuitry 28 in advance of inputting signals from sensor 22. In decision tree 52 of FIG. 5, each of measurement nodes 54a-i specifies an associated type of measurement in Appendix I for evaluation.

For example, root measurement node 54 a specifies measurement #17 ("1/eccentricity") of Appendix I for evaluation. Each of measurement nodes 54a-i may have more than two associated branches. For example, root measurement node 54a has seven associated branches 56a-g. Adjacent branches are separated by an associated threshold value. Accordingly, adjacent branches 56a-b are separated by an associated threshold value. Likewise, adjacent branches 56b-c are separated by an associated threshold value.

After process circuitry 28 forms a decision tree (such as decision tree 52), process circuitry 28 inputs signals from sensor 22, acquires measurements from the signals, and distinguishes one or more objects as being represented in the signals by traversing a path of the decision tree. For example, process circuitry 28 traverses a path of decision tree 52 by first evaluating the measurement type specified at root measurement node 54a. Accordingly, if measurement #17 has a value between the associated threshold value of branches 56b-c and the associated threshold value of branches 56c-d, then process circuitry 28 distinguishes target object 10 (FIG. 1) as being represented in the signals from sensor 22. Otherwise, process circuitry 28 evaluates the measurement type specified at one of measurement nodes 54b-g.

For example, if measurement #17 has a value between the associated threshold value of branches 56d-e and the associated threshold value of branches 56e-f, then process circuitry 28 evaluates measurement #47 of Appendix I specified at measurement node 54e. In such a situation, process circuitry 28 advantageously adapts to the recognition domain and saves processing time by traversing only branch 56e at the first level of decision tree 52, such that process circuitry 28 is not required to evaluate measurement types specified at nodes 54b,c,d,f and g. Likewise, if measurement #47 has a value between the associated threshold value of branches 58b-c and the associated threshold value of branches 58c-d, then process circuitry 28 traverses only branch 58c at the second level of decision tree 52, such that process circuitry 28 next evaluates measurement #0 of Appendix I specified at measurement node 54h.

Finally, if measurement #0 satisfies the associated threshold value between branches 60a-b, then process circuitry 28 traverses branch 60b at the third level of decision tree 52, such that process circuitry 28 distinguishes target object 12 (FIG. 1) as being represented in the signals from sensor 22. Otherwise, process circuitry 28 traverses branch 60a and distinguishes target object 15 (FIG. 1) as being represented in the signals. Thus, in distinguishing target object 15, process circuitry 28 traverses a path of decision tree 52 including nodes 54a, 54e, and 54h and branches 56e, 58c, and 60a.

As decision tree 52 of FIG. 5 demonstrates, process circuitry 28 is not required to always evaluate predefined types of acquired measurements. Instead, process circuitry 28 effectively adapts to a recognition domain by selecting measurements for evaluation according to each measurement's usefulness. For example, several types of measurements described in Appendix I are not specified in decision tree 52, such that process circuitry 28 is not required to spend processing time acquiring the non-specified types of measurements for evaluation. Further, process circuitry 28 is not required to spend processing time evaluating each of nodes 54a-i, because process circuitry 28 traverses only one branch at each level of decision tree 52. Accordingly, process circuitry 28 has relatively good efficiency and good robustness, because it evaluates measurements by adapting to the recognition domain rather than according to a preconceived recognition strategy.

Process circuitry 28 forms the n-ary decision tree by selecting measurement types for evaluation in an optimal order, thereby enhancing the efficiency with which process circuitry 28 eliminates uncertainty regarding an object's representation in the signals. In the preferred embodiment, process circuitry 28 selects the optimal order of measurement types in response to entropy of an object probability function. Entropy is one measure of uncertainty regarding an object's representation in the signals.

Process circuitry 28 estimates reduction in entropy by evaluating sample measurements acquired from a set of sample signals. Assuming n objects in the object set, process circuitry 28 establishes the a priori object entropy at a particular measurement node as ##EQU1## where H denotes entropy, where X denotes the object set (X=[x.sub.1 . . . x.sub.n ]) with x.sub.i denoting the ith element, and where P denotes object probability as a function of object x.sub.i conditioned on all measurement values satisfying the decision tree path from and including the root measurement node leading to but not including the particular measurement node.

For example, FIG. 6a is a first exemplary graph of object probability versus object type for five different types of objects in an object set. In the graph of FIG. 6a, object probability is distributed evenly among all objects of the object set. The maximum value of entropy occurs with each object having equal probability of being represented in the signals, as in FIG. 6a.

FIG. 6b is a second exemplary graph of object probability versus object type for five different types of objects. In the graph of FIG. 6b, object probability is concentrated solely at object #2, such that the minimum value of entropy (entropy=0) occurs with object #2 having maximum probability (probability=1) of being represented in the signals.

Without conditioning object probability on a given value of any particular measurement type being considered by process circuitry 28 for selection to be specified at a particular measurement node, the graph of FIG. 6a shows object probability versus object type (for five different types of objects) where each object has equal probability of being represented in the signals. By comparison, the exemplary graph of FIG. 7a shows object probability versus object type, conditioned on a given value of a hypothetical measurement type #1. Similarly, the exemplary graph of FIG. 7b shows object probability versus object type, conditioned on a given value of a hypothetical measurement type #2. The exemplary graph of FIG. 7c shows object probability versus object type, conditioned on a given value of a hypothetical measurement type #3.

After process circuitry 28 conditions the object entropy on a sample measurement value y, the object entropy at a particular measurement node becomes ##EQU2## where y denotes a sample measurement value of a particular measurement type, and where P(x.sub.i .vertline.y) denotes object probability as a function of object x.sub.i conditioned on the sample measurement value y and additionally conditioned on all measurement values satisfying the decision tree path from and including the root measurement node leading to the particular measurement node.

The actual reduction in uncertainty is measured by

where process circuitry 28 obtains the expectation by averaging over the sample space of possible measurement values Y, and where I(X;Y) is the average mutual information between the sample measurements and the objects to be distinguished. Average mutual information measures reduction in entropy averaged over possible measurement values for a particular measurement type.

In response to differences in entropy resulting from conditioning object probability on given values of different measurement types in a measurement set (such as the differences in entropy exhibited by the exemplary graphs of FIGS. 7a-c), process circuitry 28 selects an optimal measurement type for evaluation at a measurement node of the n-ary decision tree. As a simple example, based only on the measurement values in the exemplary graphs of FIGS. 7a-c, the optimal measurement type for evaluation is hypothetical measurement type #1, because the graph of FIG. 7a exhibits the highest concentration of probability and hence the highest reduction in entropy. Thus, in response only to object probabilities shown by the exemplary graphs of FIGS. 7a-c, process #1 for evaluation at a measurement node of the n-ary decision tree. In actual practice, process circuitry 28 considers all measurement values, as indicated in Equation (3).

Similarly, process circuitry 28 evaluates the reduction in entropy to estimate whether an entire set of selected measurements is sufficient to distinguish each object of an object set with a specified reliability. Process circuitry 28 estimates the sufficiency of selected measurements in a manner independent of a preconceived recognition strategy. By making such an estimation, process circuitry 28 likewise estimates its own reliability in distinguishing objects.

In forming a decision tree (such as decision tree 52), process circuitry 28 estimates reduction in entropy by evaluating sample measurements acquired from a set of sample signals. Similarly, process circuitry 28 estimates its actual reliability in distinguishing each object represented in actual signals, by determining its sample reliability in distinguishing each object represented in the set of sample signals.

FIG. 8 is a flow chart of the technique of the preferred embodiment by which process circuitry 28 forms an n-ary decision tree in response to a set of sample signals representing all objects to be distinguished in an object set. At step 61, process circuitry 28 inputs definitions of a set of objects (such as set 20 of FIG. 1) to be distinguished as being either represented or not represented in the actual signals. At step 62, process circuitry 28 inputs definitions of a set of measurement types (such as the set of measurement types described in Appendix I) that are characteristic, to varying degrees, of one or more of the objects to be distinguished. At step 63, process circuitry 28 inputs a set of sample signals.

For example, at step 63, process circuitry 28 can input a set of 500 sample images (such as image 44 of FIG. 4a) of target objects 0-19 (FIG. 1), such that each of target objects 0-19 is represented in an average of twenty-five sample images. If each of target objects 0-19 is proportionately represented in exactly twenty-five sample images, then process circuitry 28 treats each of target objects 0-19 as having equal initial probability of being represented the actual signals (maximum entropy). If any of target objects 0-19 is represented in a disproportionate number of sample images, then process circuitry 28 adjusts the initial probabilities obtained by establishing circuitry, according to the ratios with which target objects 0-19 are represented in the set of sample images. Within the set of sample images, a sample image representing a particular target object can be duplicated as desired in order to reflect the particular target object's increased initial probability of being represented in the actual signals.

Preferably, the set of sample signals represents each object under a variety of actual conditions. For example, each of target objects 0-19 is preferably represented in multiple sample images under a variety of different actual viewing conditions, such as varying orientations, lighting conditions, distances and backgrounds. Since process circuitry 28 estimates its actual reliability by determining its sample reliability, the actual reliability of process circuitry 28 is sufficiently estimated where the set of sample signals is sufficiently representative of actual signals.

After inputting the set of sample signals, process circuitry 28 acquires sample measurements from the set of sample signals at step 64. For example, if process circuitry 28 at step 63 inputs a set of 500 sample images (such as image 44 in FIG. 4a of target object 12 in FIG. 1) of target objects 0-19, then process circuitry 28 at step 64 would acquire a sample measurement from each of the 500 sample images for each type of measurement 0-148 (Appendix I), such that 500 sample measurements are acquired for each type of measurement 0-148. Moreover, at step 64, the sample measurements are classified according to object type. For example, if each of target objects 0-19 is proportionately represented in exactly twenty-five sample images, then for each type of target object 0-19 twenty-five sample measurements are acquired for each type of measurement 0-148.

At step 65, process circuitry 28 forms an n-ary decision tree (such as decision tree 52 of FIG. 5) in response to the sample measurement values acquired at step 64. The technique of the preferred embodiment by which process circuitry 28 forms the n-ary decision tree at step 65 is described further hereinbelow in connection with FIGS. 9-14.

After forming the decision tree, process circuitry 28 inputs actual signals at step 66. At step 67, process circuitry 28 traverses the decision tree to distinguish one or more objects represented in the actual signals, according to the technique described further hereinabove in connection with FIG. 5. After traversing the decision tree, process circuitry 28 determines at decision block 68 whether to process more actual signals. If more actual signals are to be processed, then execution returns to step 66; otherwise, execution stops.

In forming the decision tree at step 65, it is frequently impractical for process circuitry 28 to require that the decision tree resolve all uncertainty in object identity. It is frequently practical for process circuitry 28 to accept some uncertainty in object identity.

Accordingly, in order to identify an object as being distinguished at a branch of a particular measurement node, it is frequently practical for process circuitry 28 to require that there is an i such that

where C is a specified reliability of distinguishing the object, and where sample measurement vector y contains all measurement values satisfying the decision tree path from and including the root measurement node leading to and including the particular measurement node.

Alternatively, process circuitry 28 can require that ##EQU3## where .epsilon. represents the allowable uncertainty.

In yet another alternative, process circuitry 28 can require that

For discretely variable measurements, process circuitry 28 calculates mutual information I(X;Y) by collecting sample measurement values for each of the n objects X=[x.sub.1 . . . X.sub.n ], and by using estimated (instead of exact) probabilities to estimate the entropies found in the expression for mutual information (Equation (3)).

Where process circuitry 28 considers selecting a continuously variable measurement to be specified at a particular measurement node of the decision tree, process circuitry 28 exploits the symmetry of mutual information, namely I(X;Y)=I(Y;X), such that ##EQU4## where p(y) denotes a probability density function estimate for a particular measurement value of a particular measurement type, and where p(y.vertline.x.sub.i) denotes a probability density function estimate for a particular measurement value of a particular measurement type conditioned on a particular object x.sub.i.

Accordingly, process circuitry 28 estimates mutual information by obtaining sample measurement values for each object x.sub.i, and by using a probability density estimator to estimate p(Y.vertline.x.sub.i). The probability density function estimates p(y) and p(y.vertline.x.sub.i) are additionally conditioned on all measurement values satisfying the decision tree path from and including the root measurement node leading to the particular measurement node. In the preferred embodiment, process circuitry 28 uses any suitable numerical integration technique to estimate integrals of Equation (7). In practice, process circuitry 28 normally does not need to integrate over the full range from -.infin. to .infin. in Equation (7), but instead process circuitry 28 normally can integrate over a limited range.

Significantly, not all measurement types are necessarily relevant to distinguishing [x.sub.1 . . . x.sub.n ]. Further, some measurement types are possibly redundant with respect to information provided by other measurement types. Accordingly, process circuitry 28 accounts for redundant or irrelevant measurement types by recursively selecting measurements for evaluation at measurement nodes of an n-ary decision tree.

If a decision tree is not formed by process circuitry 28 in advance of inputting signals from sensor 22, then a significant performance penalty results. As illustrated in FIG. 8, process circuitry 28 preferably forms an n-ary decision tree (such as decision tree 52 of FIG. 5) at step 65 in advance of the time when objects are to be distinguished. At step 65, the measurement selected by process circuitry 28 for evaluation at a particular measurement node is that which provides the highest estimated mutual information in consideration of a decision tree path. As described hereinabove in connection with FIG. 5, a decision tree path includes all measurements and branches in a decision tree from and including the decision tree's root measurement node leading to the particular measurement node.

After selecting a measurement for evaluation at a particular measurement node, process circuitry 28 determines at a particular branch whether an i exists such that P(x.sub.i .vertline.measurement values satisfying decision tree path)>C, where C is the specified reliability of distinguishing objects. Thus, process circuitry 28 determines an optimal sequence of measurements for evaluation in order to achieve the specified reliability C.

FIG. 9 is a flow chart of the technique of the preferred embodiment by which process circuitry 28 recursively selects measurements for evaluation at measurement nodes of an n-ary decision tree. Execution begins at step 69, where process circuitry 28 initializes a present measurement node indicator to indicate the decision tree's root measurement node (such as root measurement node 54a of FIG. 5). At step 70, process circuitry 28 determines the mutual information provided by each type of continuously variable measurement. At step 71, process circuitry 28 determines by determining circuitry the mutual information provided by each type of discretely variable measurement. At step 72, process circuitry 28 selects a measurement type for evaluation at the present measurement node, such that the selected measurement type provides the highest mutual information (as most recently determined by process circuitry 28) relative to each of the non-selected measurement types.

At decision block 73, process circuitry 28 determines whether the selected measurement type is continuously variable. If the selected measurement type is not continuously variable, then execution continues to step 74. If the selected measurement type is continuously variable, then process circuitry 28 by ordering circuit quantizes the selected measurement at step 75 according to the technique of the preferred embodiment described further hereinbelow in connection with FIGS. 10-14, and execution continues to step 74.

At step 74, process circuitry 28 selects any branch of the present measurement node. By definition, the selected branch leads to the next level of the decision tree. At decision block 76, process circuitry 28 determines whether the specified reliability C is achieved at the selected branch. If the specified reliability C is not achieved at the selected branch, then execution continues to step 78. If the specified reliability C is achieved at the selected branch, then at step 80 process circuitry 28 terminates the selected branch by specifying the object type having the highest probability of being represented in the signals.

At decision block 82, process circuitry 28 determines whether all branches of the decision tree have been terminated. If all branches of the decision tree have been terminated, then execution ends. If all branches of the decision tree have not been terminated, then at step 84 process circuitry 28 selects a non-terminated branch, and execution returns to decision block 76.

At step 78, process circuitry 28 updates the present measurement node indicator to indicate a new measurement node connected to the selected branch. At step 86, process circuitry 28 determines the mutual information provided by each type of continuously variable measurement, using sample measurement values satisfying a decision tree path from and including the root measurement node leading to the present measurement node. At step 88, process circuitry 28 determines the mutual information provided by each type of discretely variable measurement, using sample measurement values satisfying a decision tree path from and including the root measurement node leading to the present measurement node. Execution then returns to step 72.

In this manner, selection of measurements for evaluation continues until the specified reliability C is achieved. Process circuitry 28 does not select irrelevant or redundant measurement types for evaluation at measurement nodes, resulting in successful pruning of measurement types for evaluation. Accordingly, process circuitry 28 achieves data driven dimensionality reduction and operates at high efficiency, because process circuitry 28 does not need to acquire all measurements from the signals in order to distinguish one or more objects in the set of objects.

Moreover, under the technique of FIG. 9, process circuitry 28 determines mutual information provided by each type of continuously variable measurement. Then, process circuitry 28 selects the measurement type providing the highest mutual information relative to each of the non-selected measurement types. Under this approach of the preferred embodiment, process circuitry 28 advantageously quantizes only those continuously variable measurements which are selected for evaluation at measurement nodes of the decision tree. Thus, process circuitry 28 efficiently forms the decision tree, without having to quantize those continuously variable measurements that are not selected for evaluation at measurement nodes of the decision tree.

Alternatively, process circuitry 28 can initially quantize all continuously variable measurements, so that process circuitry 28 could determine mutual information provided by each of the resulting types of quantized measurements. In such an alternative approach, process circuitry 28 selects the quantized measurement type providing the highest mutual information relative to each of the non-selected measurement types. By forming the decision tree in response to mutual information provided by quantized measurement types, process circuitry 28 reflects the fact that it subsequently traverses the decision tree by evaluating measurements by evaluating circuitry in a quantized manner. Accordingly, it is possible that such an alternative approach might provide a slightly more optimal ordering of measurements for evaluation within the decision tree.

Nevertheless, such an alternative approach is not preferred because process circuitry 28 uses additional processing time to quantize all continuously variable measurements at each new node of the decision tree, even those continuously variable measurements that are not selected for evaluation at measurement nodes of the decision tree. Also, if a first quantized measurement ("QM1") is formed by quantizing a first continuously variable measurement ("CM1"), if a second quantized measurement ("QM2") is formed by quantizing a second continuously variable measurement ("CM2"), and if QM1 provides more mutual information than QM2, then it is unlikely that CM1 will provide less mutual information than CM2.

Process circuitry 28 forms an n-ary decision tree (such as decision tree 52 of FIG. 5), such that process circuitry 28 is able to consider more than two possible values of a discretely variable measurement type or a quantized continuously variable measurement type at a single node (such as measurement node 54a). Thus, process circuitry 28 efficiently uses available system memory, and consumes relatively small processing time in evaluating acquired measurements by traversing a path of an n-ary decision tree of the preferred embodiment.

In forming the n-ary decision tree, process circuitry 28 advantageously selects a suitable number of branches at each measurement node by adapting to a recognition domain. For example, process circuitry 28 forms decision tree 52 with seven branches 56a-g associated with measurement node 54a, and with four branches 58a-d associated with measurement node 54e. Moreover, process circuitry 28 advantageously selects suitable threshold values associated with such branches by adapting to the recognition domain.

Accordingly, process circuitry 28 advantageously by quantizing circuit quantizes continuous measurement types into discrete measurement types. For a measurement type selected for evaluation at a measurement node, process circuitry 28 chooses the number of associated branches ("quantization intervals") in a manner consistent with the mutual information provided by the selected measurement type. Process circuitry 28 chooses a small number of quantization intervals for measurements yielding a small amount of mutual information, and chooses a large number of quantization intervals for measurements yielding a large amount of mutual information.

Moreover, process circuitry 28 performs quantization such that mutual information is optimized for the chosen number of quantization intervals. Accordingly, process circuitry 28 estimates mutual information as a continuously variable function of threshold values. For m quantization intervals, process circuitry 28 determines m-1 ordered associated threshold values which optimize the estimated mutual information function. In the preferred embodiment, process circuitry 28 uses the downhill simplex method (modified to preserve the order of thresholds) for such multidimensional optimization, because it does not require that derivatives be evaluated or that the estimated mutual information function be differentiable.

In selecting m, process circuitry 28 follows two guidelines. First, process circuitry 28 recovers mutual information efficiently with respect to m. For example, if m=4 yields 2 bits of mutual information, and if m=8 yields 2.1 bits of mutual information, then the choice of m=8 is not preferred. This is because the decision tree would occupy significant additional memory for only a marginal increase in mutual information, and also because each succeeding subtree would have access to an average of only half as much data for its formation. Second, process circuitry 28 performs quantization with respect to m, such that m is consistent with the amount of mutual information provided. In this manner, m is sufficiently large to avoid an unnecessarily large number of levels in the decision tree. By comparison, the large number of levels in a binary decision tree results in slow performance.

FIG. 10 is a flow chart of the technique by which process circuitry 28 selects m, together with the m-1 ordered associated threshold values. At step 90, process circuitry 28 sets m=2. At step 92, process circuitry 28 determines m-1 ordered associated threshold values which optimize mutual information for m quantization intervals. At step 94, process circuitry 28 sets q to equal the optimized value of mutual information from step 92. Decision block 96 determines whether 2.sup.q .ltoreq.m-1. If decision block 96 determines that 2.sup.q .ltoreq.m-1, then at step 98 process circuitry 28 sets m=m-1, and execution stops. If decision block 96 determines that 2.sup.q >m-1, then at step 100 process circuitry 28 sets m=m+1, and execution returns to step 92.

The technique of FIG. 10 is efficient with respect to m, because process circuitry 28 increases m only until mutual information slows its growth with respect to m. Notably, a measurement can be specified for evaluation at multiple measurement nodes in the decision tree, so that process circuitry 28 is not required to extract all mutual information at a single measurement node via numerous quantization intervals. Moreover, this technique is opportunistic, because measurements yielding high mutual information result in high values for m.

FIG. 11 is an exemplary graph of quantized mutual information, showing how quantized mutual information typically grows as the number m of quantization intervals increases. As m increases, quantized mutual information curve 102 asymptotically approaches continuous mutual information level 104.

Process circuitry 28 automatically selects optimal measurements for evaluation, such that the recognition strategy is adapted to the recognition domain. More particularly, process circuitry 28 autonomously selects measurements for evaluation by adapting to properties of the sample measurement data when estimating probability densities for mutual information estimation and quantization of continuously variable measurements.

Advantageously, process circuitry 28 does not determine mutual information over an entire measurement vector. Thus, process circuitry 28 is not required to estimate multidimensional probability densities. Instead, process circuitry 28 determines mutual information between a single measurement y.sub.j and the objects to be distinguished. This approach simplifies the computational requirements of process circuitry 28, since only one-dimensional probability densities are estimated.

Unlike the situation where a measurement is discretely variable, for a continuously variable measurement it is impractical to estimate object probabilities conditioned on each possible measurement value. Instead, process circuitry 28 estimates probability densities of continuously variable measurements conditioned on objects to be distinguished, as specified in Equation (7). Since sample measurement data are arbitrary, process circuitry 28 does not assume a predetermined model for the probability densities. Instead, process circuitry 28 implements an adaptive nonparametric density estimation technique.

A standard nonparametric density estimation technique is the Parzen technique, which superimposes kernel functions on the sample measurement data, where the kernel functions correspond to legitimate probability density functions. Commonly, the Parzen technique uses a Gaussian kernel function. In the Parzen technique, the mean of the sample measurement data agrees with the mean of the corresponding Parzen probability density estimate.

As a number of sample measurement data points approaches infinity, the Parzen technique results in an estimate guaranteed to converge to the actual density function, independently of the initial kernel size (typically measured by standard deviation .sigma. of the Gaussian). Nevertheless, practicality imposes limits on the number of sample measurement data points. Thus, kernel size is significant, because kernel size frequently determines the smoothness and resolution of the probability density estimate for finite sample measurement data.

For finite sample measurement data, a significant shortcoming of the Parzen technique is its inability to automatically and objectively choose .sigma. so that first and second order characteristics of the sample measurement data agree with first and second order characteristics of the estimated probability density function. Initially, .sigma. is manually chosen under the Parzen technique according to a cumbersome and subjective process of iteration. Moreover, under the Parzen technique, the size of each kernel is identical, which less accurately estimates probability density when sample measurement data is limited.

In the preferred embodiment, process circuitry 28 advantageously forms smooth probability density estimates having large .sigma. when adapting to a few sample measurement data points, in order to realistically and accurately reflect lack of knowledge. Conversely, process circuitry 28 advantageously forms sharp probability density estimates having small .sigma. when adapting to numerous sample measurement data points.

Accordingly, in a significant aspect of the preferred embodiment, process circuitry 28 adaptively chooses .sigma. in response to the sample measurement data. In forming an adaptive probability density estimate, process circuitry 28 automatically and objectively chooses .sigma. so that first and second order characteristics of the sample measurement data agree with first and second order characteristics of the estimated probability density function. Moreover, process circuitry 28 individually chooses .sigma. for each kernel, such that probability density is accurately estimated when sample measurement data is limited.

The difference between the sample measurement data variance and the probability density estimate variance is .sigma..sup.2 for uniform kernel sizes. Thus, process circuitry 28 does not require exact agreement, because exact agreement would indicate .sigma.=0. Instead, process circuitry 28 specifies a maximum allowable difference between the sample measurement data variance and the probability density estimate variance. Process circuitry 28 specifies the maximum allowable difference as being the root mean squared error in the variance estimate obtained from the sample measurement data. By choosing .sigma. such that the maximum allowable difference is attained, process circuitry 28 effectively chooses the smoothest probability density estimate consistent with second order characteristics of the sample measurement data.

For unbiased sample measurement data, the variance estimate obtained from n sample measurement data points [X.sub.1 . . . X.sub.n ] is ##EQU5##

Process circuitry 28 sets the maximum allowable kernel variance to equal the root mean squared error in the variance estimate obtained from the sample measurement data. Thus, the maximum allowable average of kernel variances is ##EQU6## Accordingly, process circuitry 28 sets the maximum value of .sigma. to ##EQU7##

In the above expression, quantities estimated from the sample measurement data replace the expected values. In this manner, .sigma. advantageously varies with the amount of sample measurement data.

Accordingly, in the preferred embodiment, process circuitry 28 forms a probability density estimate that is globally consistent with first and second order characteristics of the sample measurement data. Moreover, process circuitry 28 advantageously imposes local neighborhood consistency on the adaptive probability density estimate. More particularly, process circuitry 28 adapts .sigma. in response to local properties of the sample measurement data. In comparison to a typical Parzen estimation technique, process circuitry 28 allows non-uniform kernel sizes, which is advantageous for estimating multi-modal densities.

By allowing non-uniform kernel sizes, the difference between the sample measurement data variance and the probability density estimate variance is the average variance of the kernels as indicated in ##EQU8## Accordingly, process circuitry 28 chooses .sigma..sub.i (corresponding to data point i) in response to local structure of the data, such that the maximum allowable value of the average kernel variance is ##EQU9##

In order to respond to the local second order characteristics of the data, process circuitry 28 uses a K-nearest approach for determining .sigma..sub.i. Accordingly, process circuitry 28 establishes .sigma..sub.i equal to the .sigma. of data points in the local neighborhood of data point i. The local neighborhood of data point i includes the K data points nearest to data point i, where K is an integer variable. It is unlikely that a K will exist yielding equality in the above expression. As K increases from 1 to n-1, the average kernel variance increases. In the preferred embodiment, process circuitry 28 implements a bisection search to efficiently determine the maximum K satisfying ##EQU10##

FIG. 12a is an exemplary plot, where K=1, of kernels 106a-c respectively selected by process circuitry 28 in response to sample measurement data points 108a-c, and of kernels 110a-c respectively selected by process circuitry 28 in response to sample measurement data points 112a-c. FIG. 12b is a plot of a probability density function estimate formed by combining kernels 106a-c and 110a-c into a single continuous curve 114.

As FIGS. 12a-b illustrate, by choosing .sigma..sub.i according to the preferred embodiment, process circuitry 28 adapts to the recognition domain by adapting to the sample measurement data. More particularly, process circuitry 28 provides a probability density estimate globally consistent with first and second order characteristics of the sample measurement data, and locally consistent with second order characteristics of the sample measurement data. Kernels 110a-c together form a smooth probability density estimate having large a by adapting to a few widely distributed sample measurement data points 112a-c. Conversely, kernels 106a-c together form a sharp probability density estimate having small .sigma. by adapting to closely concentrated sample measurement data points 108a-c.

FIG. 13a is a plot of a theoretical probability density curve having a uniform probability density component 116, and having a Gaussian probability density component 118. FIG. 13b is a plot of a continuous probability density curve 120 representing a probability density function estimated by process circuitry 28 according to the technique of the preferred embodiment. Process circuitry 28 estimated the probability density function of curve 120 by adapting to one-hundred sample measurement data points randomly generated from the uniform component 116 and the Gaussian component 118. As FIGS. 13a-b illustrate, the probability density function of curve 120 estimated by process circuitry 28 advantageously achieves a close correlation with the theoretical probability density curve of FIG. 13a, in response to only a limited number of one-hundred sample measurement data points.

FIG. 14a is a plot of a continuous probability density curve 122 representing a probability density function that process circuitry 28 estimated for measurement #2 (Appendix I) by adapting to five-hundred sample measurement data points acquired by process circuitry 28 from five-hundred sample images. FIG. 14b is a plot of a continuous probability density curve 124 representing a probability density function that process circuitry 28 estimated for measurement #17 (Appendix I) by adapting to five-hundred sample measurement data points acquired by process circuitry 28 from five-hundred sample images.

Curve 122 of FIG. 14a illustrates a relatively smooth probability density estimate having large average .sigma.. Conversely, curve 124 of FIG. 14b illustrates a sharp probability density estimate having small average .sigma. reflecting highly distinguishing characteristics of the sample measurement data acquired for measurement #17 (Appendix I). This highly distinguishing character of measurement #17 is acknowledged in decision tree 52 (FIG. 5) by measurement #17 being specified for evaluation at root measurement node 54a.

In this manner, process circuitry 28 provides a sufficiently accurate estimate of an acquired measurement's probability of having a value within a specified range. The probability density function estimate provided by process circuitry 28 is useful in any application that benefits from a probabilistic characterization of at least one random variable in response to samples of the random variable. For example, a manufacturer of a product (such as a resistor) can manufacture samples of the product and then measure the product's performance (such as the resistor's resistance). With the probability density function estimate provided by process circuitry 28, quality assurance personnel can determine a statistical tolerance for quotation to customers as a product specification, such as a percentage likelihood that the product's performance will fall within a specified range. In a similar manner, with the probability density function estimate provided by process circuitry 28 in response to a limited number of data samples, numerous engineering and physical science applications can estimate likelihood of an occurrence such as automotive engine performance and geophysical conditions.

In a test, process circuitry 28 achieved approximately 97% reliability in distinguishing target objects 0-19 (FIG. 1) as being either represented or not represented in a set of 19,500 sample images. Process circuitry 28 successfully distinguished each object by traversing a path of an n-ary decision tree formed by process circuitry 28 according to the preferred embodiment. In traversing a path of the n-ary decision tree, process circuitry 28 evaluated selected types of measurements 0-148 (Appendix I) acquired from the set of 19,500 sample images, as specified at nodes of the n-ary decision tree. Process circuitry 28 used an average of approximately 0.38 seconds to distinguish an object by traversing a path of the n-ary decision tree.

Although the present invention and its advantages have been described in detail, it should be understood that various changes, substitutions and alterations can be made herein without departing from the spirit and scope of the invention as defined by the appended claims.

Claims

What is claimed is:

1. A system for distinguishing objects, comprising: inputting circuitry for inputting first signals representative of the objects; acquiring circuitry coupled to said inputting circuitry for acquiring measurements of a plurality of measurement types from said first signals, at least one of said measurement types being continuously variable; determining circuitry coupled to said acquiring circuitry for determining respective amounts of mutual information of said measurement types in response to said measurements; selecting circuitry coupled to said determining circuitry for selecting, in response to said respective amounts, a measurement type of said measurement types, and; ordering circuitry coupled to said selecting circuitry for ordering each of said selected measurement types in an n-ary decision tree having branches for evaluation in distinguishing the object, where n is at least 3 and wherein said branches are only directly connected to a parent of said branches.

2. The system as in claim 1, wherein said system further comprises evaluating circuitry coupled to said selecting circuitry for evaluating, in response to said selected measurement type, at least one measurement from a set of second signals from a sample location for distinguishing at least one of the objects as being represented in said set.

3. The system as in claim 2, wherein said evaluating circuitry is operable to distinguish said at least one of the objects with a specified reliability.

4. A method of distinguishing objects using process circuitry, said method comprising the steps of: inputting signals representative of the objects; acquiring measurements of a plurality of types from said signals, at least one of said measurement types being continuously variable; determining respective amounts of mutual information of said measurement types in response to acquiring said measurements; selecting at least one of said types for evaluation in distinguishing the objects, by employing a nary decision tree having branches, said branches being only directly connected to a parent of said branches, in response to determining said respective amounts; and quantizing each of said selected continuously variable measurement type for evaluation in distinguishing the objects.

5. The method as in claim 4, wherein said step of quantizing comprises the step of quantizing each of selected continuously variable measurement types into intervals selected in response to additional mutual information of said quantized continuously variable measurement types.

6. The system of claim 1, wherein said ordering circuitry is further operable to quantize each of said selected measurement type to form quantized measurement types being continuously variable, such that said decision tree includes each of said quantized measurement types for evaluation in distinguishing the objects.

7. The system of claim 1, wherein said system further comprises circuitry coupled to said ordering circuitry for traversing a path of said decision tree, such that multiple measurements from a set of second signals from a sample location are evaluated for distinguishing at least one of the objects as being represented in said set.

8. The system as in claim 1, wherein said system further comprises establishing circuitry coupled to said inputting circuitry for establishing, in response to a representation of the objects in said first signals, initial probabilities of the objects being represented in a set of second signals.

9. The system as in claim 8, wherein said establishing circuitry is operable to establish said initial probabilities in response to a proportionate representation of the objects in said second signals.

10. The system as in claim 1, wherein said measurement types are variably characteristic of the objects.

11. The system as in claim 1, wherein at least one of said measurement types is discretely variable.

12. A system for distinguishing objects, comprising: inputting circuitry for inputting first signals representative of the objects; acquiring circuitry coupled to said inputting circuitry for acquiring measurements of a continuously variable measurement type corresponding to the objects from said first signals; quantizing circuitry coupled to said acquiring circuitry for quantizing said continuously variable measurement type to form a quantized continuously variable measurement type into intervals in response to said measurements, said intervals being selected in response to mutual information of said quantized continuously variable measurement type; and evaluating circuitry coupled to said quantizing circuitry for evaluating, in response to said quantized continuously variable measurement type, at least one measurement from a set of second signals from a sample location for distinguishing, by an n-ary decision tree having branches, said branches being only directly connected to a parent of said branches, at least one of the objects as being represented in said set.

13. The system as in claim 12, wherein said quantizing circuitry is operable to quantize said continuously variable measurement type into said intervals proportional to said mutual information of said quantized continuously variable measurement type.

14. The system as in claim 12, wherein said quantizing circuitry is operable to quantize said continuously variable measurement type into said intervals such that m-1<2.sup.q .ltoreq.m, where q is said mutual information and m is a number of said intervals.

15. The system as in claim 12, wherein said quantizing circuitry is operable to optimize said mutual information of said quantized continuously variable measurement type to form optimized mutual information by adjusting at least one threshold value separating said intervals.

16. The system as in claim 15, wherein said quantizing circuitry is operable to select said intervals in response to said optimized mutual information.

17. The system as in claim 15, wherein said quantizing circuitry is operable to optimize said mutual information according to a downhill simplex technique.

18. The system as in claim 15, wherein said quantizing circuitry is operable to multidimensionally optimize said mutual information by adjusting multiple threshold values separating said intervals.

19. The system as in claim 12, wherein said acquiring circuitry is further operable to acquire additional measurements of a plurality of types from said first signals.

20. The system as in claim 19, wherein said system further comprises: determining circuitry coupled to said acquiring circuitry for determining respective amounts of additional mutual information of said additional measurement types in response to said additional measurements; and selecting circuitry coupled to said determining circuitry for selecting, in response to said respective amounts and to said mutual information of said quantized continuously variable measurement type, at least one measurement type of said additional measurement types for evaluation in distinguishing the objects.

21. A system for determining a probability density of a measurement type, comprising: inputting circuitry for inputting a plurality of signals; acquiring circuitry coupled to said inputting circuitry for acquiring measurements of a measurement type from said signals; forming circuitry coupled to said acquiring circuitry for forming in response to said measurements, a plurality of kernels, each of said kernels associated with one of said measurements and each of said kernels having a respective size selected in response to one of said measurements in an area of an associated measurement of said measurements; and determining circuitry coupled to said forming circuitry for determining the probability density in response to said kernels.

22. The system as in claim 21, wherein said forming circuitry is operable to form said kernels such that said respective size of each of said kernels is a standard deviation of said kernels.

23. The system as in claim 21, wherein said forming circuitry is operable to form said kernels such that each of said kernels having said respective size is selected in response to a variance of said one of said measurements in said locality of said associated measurement.

24. The system as in claim 21, wherein at least one of said kernels comprises a Gaussian kernel.

25. The system as in claim 21, wherein the measurement type is continuously variable.

26. The system as in claim 21, wherein said system comprises determining mutual information circuitry coupled to said determining circuitry for determining mutual information of the measurement type in response to the probability density.

27. The system as in claim 21, wherein said signals are representative of an object.

28. The system as in claim 27, wherein said determining circuitry is operable to determine the probability density in accordance with said object.

29. The system as in claim 28, wherein said acquiring circuitry is operable to acquire at least one additional measurement of at least one additional measurement type from said signals.

30. The system of claim 29, wherein said determining circuitry is operable to determine the probability density in accordance with said at least one additional measurement.

31. A system for distinguishing objects, comprising: inputting circuitry for inputting signals representative of the objects; acquiring circuitry coupled to said inputting circuitry for acquiring measurements of a plurality of measurement types from said signals, at least one of said measurement types being continuously variable; determining circuitry coupled to said acquiring circuitry for determining respective amounts of mutual information of said measurement types in response to said measurements; selecting circuitry coupled to said determining circuitry for selecting, in response to said respective amounts, at least one of said measurement types to form selected at least one of said measurement types for evaluation in distinguishing the objects; and quantizing circuitry coupled to said selecting circuitry for quantizing said at least one of said measurement types for evaluation in distinguishing, by employing a n-ary decision tree having branches, said branches being only directly connected to a parent of said branches, the objects.

32. The system as in claim 31, wherein said quantizing circuitry is operable to quantize each of said selected at least one of said measurement types into intervals selected in response to additional mutual information of said quantized measurement types.

33. The system as in claim 31, wherein said signals are representative of object situations.

34. The system as in claim 31, wherein said signals comprise image signals.

35. The system as in claim 34, wherein said image signals are representative of target objects.

36. The system as in claim 31, wherein said signals comprise voice signals.

37. The system as in claim 36, wherein said voice signals are representative of word objects.

38. The system as in claim 31, wherein said signals comprise sample signals.

39. The system as in claim 38, wherein said sample signals comprise synthetically generated sample signals.

40. The system as in claim 31, wherein said system further comprises sufficient measurement circuitry coupled to said selecting circuitry for determining whether said measurements are sufficient to distinguish at least one of the objects with a specified reliability.

41. A method of distinguishing objects using process circuitry, said method comprising the steps of: inputting signals representative of the objects; acquiring measurements of a plurality of types from the signals, at least one of said types being continuously variable; determining respective amounts of mutual information of said types, responsive to said measurements; selecting in response to said respective amounts at least one of said types for evaluation in distinguishing the objects; and ordering each of the selected types in a n-ary decision tree having branches when n is at least 3, for evaluation in distinguishing the objects, said branches being only directly connected to a parent of said branches.

42. The method as in claim 41, wherein said method further comprises the step of evaluating, in response to said selected type, at least one measurement from a set of signals for distinguishing at least one of the objects as being represented in said set.

43. The method as in claim 42, wherein said evaluating step comprises the step of distinguishing said at least one of the objects with a specified reliability.

44. The method as in claim 4, wherein said step of inputting signals comprises the step of inputting signals representative of object situations.

45. The method as in claim 4, wherein said step of inputting signals comprises the step of inputting image signals.

46. The method as in claim 41, wherein said ordering step comprises the step of quantizing each of selected types being continuously variable, such that said decision tree includes each of said quantized types for evaluation in distinguishing the objects.

47. The method as in claim 41, wherein said method further comprises the step of traversing a path of said decision tree, such that said measurements from a set of signals are evaluated for distinguishing at least one of the objects as being represented in said set.

48. The method as in claim 41, wherein said method further comprises the step of establishing, in response to a representation of the objects in said signals, initial probabilities of the objects being represented in a set of signals.

49. The method as in claim 48, wherein said establishing step comprises the step of establishing said initial probabilities in response to a proportionate representation of the objects in said signals.

50. The method as in claim 41, wherein said acquiring step comprises the step of acquiring said measurements of a plurality of types being variably characteristic of the objects.

51. The method as in claim 41, wherein said acquiring step comprises the step of acquiring said measurements of said plurality of types, such that at least one of said types is discretely variable.

52. A method of distinguishing objects using process circuitry, said method comprising the steps of: inputting signals representative of the objects; acquiring measurements of a continuously variable measurement type from said signals; quantizing said continuously variable measurement type into intervals in response to said measurements, said intervals being selected in response to mutual information of said quantized continuously variable measurement type; and evaluating at least one measurement from a set of signals for distinguishing at least one of the objects, by a n-ary decision tree having branches, said branches being only directly connected to a parent of said branches as being represented in said set in response to said quantized continuously variable measurement type.

53. The method as in claim 52, wherein said quantizing step comprises the step of quantizing said continuously variable measurement type into said intervals proportional to said mutual information of said quantized measurement type.

54. The method as in claim 52, wherein said quantizing step comprises the step of quantizing said continuously variable measurement type into said intervals such that m-1<2.sup.q .ltoreq.m, where q corresponds to said mutual information and m corresponds to said intervals.

55. The method as in claim 52, wherein said quantizing step comprises the step of optimizing said mutual information of said quantized continuously variable measurement type by adjusting at least one threshold value separating said intervals.

56. The method as in claim 55, wherein said quantizing step comprises the step of selecting said intervals in response to said optimized mutual information.

57. The method as in claim 55, wherein said step of optimizing comprises the step of optimizing said mutual information according to a downhill simplex technique.

58. The method as in claim 55, wherein said step of optimizing comprises the step of multidimensionally optimizing said mutual information by adjusting multiple threshold values separating said intervals.

59. The method of claim 52 and further comprising the steps of: acquiring additional measurements of a plurality of types from said signals; determining respective amounts of additional mutual information of said additional measurement types in response to said additional measurements; and selecting at least one of said types for evaluation in distinguishing the objects in response to said respected amounts and to said mutual information of said quantized continuously variable measurement types.

60. The method as in claim 52, wherein said evaluating step comprises the step of distinguishing at least one of the objects with a specified reliability.

61. A method of determining a probability density of a measurement type using process circuitry said method comprising the steps of: inputting a plurality of signals; acquiring measurements of the measurement type from said signals; forming a plurality of kernels in response to said measurements, each of said kernels being associated with one of said measurements and each of said kernels having a respective size selected in response to one of said measurements in a locality of said associated measurement; and determining a probability density in response to said kernels.

62. The method as in claim 61, wherein said forming step comprises the step of forming said kernels such that said respective size of each of said kernels is a standard deviation of said kernels.

63. The method as in claim 61, wherein said forming step comprises the step of forming said kernels such that each of said kernels have a respective size selected in response to a variance of one of said measurements in a locality of said associated measurement.

64. The method as in claim 61, wherein the forming step comprises the step of forming a Gaussian kernel.

65. The method as in claim 61, wherein the step of acquiring said measurements comprises the step of acquiring a measurement of said measurements being continuously variable.

66. The method as in claim 61, wherein the method further comprises the step of determining said mutual information of the measurement type in response to a probability density.

67. The method as in claim 61, wherein said step of inputting signals comprises the step of inputting signals representative of an object.

68. The method as in claim 67, wherein said step of determining the probability density comprises the step of determining the probability density being conditioned on said object.

69. The method as in claim 68, wherein said method further comprises the step of acquiring, from said signals, at least one additional measurement of at least one additional measurement type.

70. The method as in claim 69, wherein said step of determining the probability density comprises the step of determining the probability density being conditioned on said additional measurement.

71. The method as in claim 45, wherein said step of inputting image signals comprises the step of inputting image signals representative of target objects.

72. The method as in claim 4, wherein said step of inputting signals comprises the step of inputting voice signals.

73. The method as in claim 72, wherein said step of inputting voice signals comprises the step of inputting voice signals representative of word objects.

74. The method as in claim 4, wherein said step of inputting signals comprises the step of inputting sample signals.

75. The method as in claim 74, wherein said step of inputting sample signals comprises the step of inputting synthetically generated sample signals.

76. The method as in claim 4, wherein said method further comprises the step of determining whether said measurements are adapted to distinguish at least one of the objects with a specified reliability.

Patent Citations (5)

Patent	Date	Inventor
US4944023	1990-07-01	Zmao
US5077809	1991-12-01	Ghazizadeh
US5123057	1992-06-01	Verly et al.
US5181256	1993-01-01	Kamiya
US5222155	1993-06-01	Delanoy

Non-Patent Literature (13)

P.M. Lewis II, "The Characteristic Selection Problem in Recognition Systems," IRE Transactions on Information Theory, vol. IT-8, No. 2, Feb. 1992, pp. 171-178.
Harold J. Payne and William S. Meisel, "An Algorithm for Constructing Optical Binary Decision Trees", IEEE Transactions on Computers, vol. C-26, No. 9, Sep. 1977, pp. 905-916.
I.K. Sethi and P.R. Sarvarayudu, "Hierarchical Classifier Design Using Mutual Information", IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. PAMI-4, No. 4, Jul. 1982, pp. 441-445.
Luo, Ralph S. Scherp and Mark Lanzo, "Object Identification Using Automated Decision Tree Construction Approach for Robotics Applications," Journal of Robotic Systems, 4 (3), 1967, pp. 423-433.
Qing Ren Wang and Ching Y. Suen, "Analysis and Design of a Decision Tree Based on Entropy Reduction and Its Application to Large Character Set Recognition", IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. PAMI-6, No. 4, Jul. 1984, pp. 406-417.
Usama M. Fayyad and Keki B. Irani, "Technical Note On the Handling of Continuous-Valued Attributes in Decision Tree Generation", Machine Learning, 8, 1992, pp. 87-102.
Philip H. Swain and Hans Kauska, "The Decision Tree Classifier: Design and Potential", IEEE Transactions on Geoscience Electronics, vol. GE-15, No. 3, Jul. 1977, pp. 142-147.
Kerim Demirbas, "Distributed Sensor Data Fusion with Binary Decision Trees", IEEE Transactions on Aerospace and Electronic Systems, vol. 25, No. 5, Sep. 1989, pp. 643-649.
Paul E. Utgoff, "ID5: An Incremental ID3", Proceedings of the Fifth International Conference on Machine Learning, Jun. 12-14, 1988, pp. 107-120.
Jie Cheng, Usama M. Fayyad, Keki B. Irani and Zhaogang Qian, "Improved Decision Trees: A Generalized Version of ID3", Proceedings of the Fifth International Conference on Machine Learning, Jun. 12-14, 1988, pp. 100-104.
Krzysztof J. Cios and Ning Liu, "A Machine Learning Method for Generation of a Neural Network Architecture: A continuous ID3 Algorithm", IEEE Transactions on Neural Networks, vol. 3, No. 2, Mar. 1992, pp. 280-291.
J. R. Quinlan, "Induction of Decision Trees", Machine Learning 1, 1986, pp. 1-106.
L. Breiman, et al., "Classification and Regression Trees", book, Published by Wadsworth & Brooks/Cole Advanced Books & Software, Pacific Grove, California, 1984.

Abstract

Description