General method of pattern classification using the two domain theory

• US 5,181,259 A
• Filed: 09/25/1990
• Issued: 01/19/1993
• Est. Priority Date: 09/25/1990
• Status: Expired due to Fees

• Current Assignee: The United States of America As Represented By The Secretary of Agriculture
• Original Assignee: United States Of America As Represented By The Administrator Of The National Aeronautics And Space Administration
• Inventors: Rorvig, Mark E.
• Primary Examiner(s): Razavi, Michael T.
• Assistant Examiner(s): COUSO, YON JUNG
• Application Number:
  US07/587,922
• Time in Patent Office: 847 Days
• Field of Search: 382/6, 382/30, 382/18, 382/1, 382/36, 364/715, 364/413.08, 364/413.17, 364/413.18
• US Class Current: 382/225
• CPC Class Codes: G06F 18/21 Design or setup of recognition systems or techniques; Extraction of features in feature space; Blind source separation

Abstract

Human beings judge patterns (such as images) by complex mental processes, some of which may not be known, while computing machines extract features. By representing the human judgements with simple measurements and reducing them and the machine extracted features to a common metric space and fitting them by regression, the judgements of human experts rendered on a sample of patterns may be imposed on a pattern population to provide automatic classification.

Claims

1. A method for automatic classification of a collection C of patterns using the judgments of human experts on a plurality of sample patterns, said method comprising the steps of:

(a) selecting a set of sample patterns;

(b) manually comparing members of said set of sample patterns to determine the degree of dissimilarity of each member of said set with respect to other members of said set;

(c) producing an ordering Φ

of said members of said set by their degree of dissimilarity in an n-dimensional space by means of multi-dimensional scaling to produce a real-valued ordering Φ

of said sample patterns;

(d) sensing the collection C of patterns to produce a signal S representing said patterns;

(e) processing the signal S to produce a plurality of machine derived signatures representing distributions of primitive features of interest;

(f) calculating the spatial distance among pairs of said patterns from said machine derived signatures to produce a matrix M of interpoint distances; and

(g) creating a mapping of the ordering Φ

on the matrix M by multiple regression;

whereby said collection of patterns is organized into sets of similar patterns.

2. The method defined in claim 1, wherein said patterns are images.

3. The method defined in claim 1, wherein said sample patterns are selected from said collection of patterns.

4. The method defined in claim 3, wherein said sample patterns are selected at random from said collection of patterns so as to be representative of said collection.

5. The method defined in claim 1, wherein each member of the set of sample patterns is manually compared as a pair with every other member of said set to determine the degree of dissimilarity of each pair.

6. The method defined in claim 5, wherein said comparing step includes the steps of manually marking a line, for each pair of sample patterns, which indicates, on an arbitrary scale from dissimilar to similar, the degree of dissimilarity of such pair;

and sensing the line to produce a signal representative of the position of the mark on the line.

7. The method defined in claim 1, wherein said n-dimensional space is a Euclidean space.

8. The method defined in claim 1, wherein said step of sensing said collection C of patterns includes the step of digitizing each pattern and storing the digitized values.

9. The method defined in claim 1, wherein said signal S processing step includes the step of producing a histogram for each of said primitive features.

10. The method defined in claim 9, wherein said signal S processing step further includes the step of converting the feature histograms for each pattern into Lorenz information measures.

11. The method defined in claim 10, wherein said calculating step includes the step of calculating the Euclidean distance among pairs of said patterns over the Lorenz information measures to produce said matrix M.

12. The method defined in claim 11, wherein said step of creating a mapping includes the step of creating a linear mapping of the ordering Φ

on the matrix M.

13. The method defined in claim 1, wherein said step of creating a mapping includes the steps of regressing the ordering Φ

with the sample of matrix M corresponding to the sample manually compared to obtain a matrix of weights β

by multiple regression and multiplying the matrix M by the matrix Φ

.

14. The method defined in claim 13, further comprising the step of submitting the results of the matrix multiplication to multi-dimensional scaling to produce the final ordering Φ

'"'"', consisting of patterns segregated into classes in an n-dimensional space.

15. A method for synthesizing human judgement measurements and machine derived measurements with respect to a collection C of patterns, said method comprising the steps of:

(a) selecting from the collection C of patterns a sample set comprising a plurality of sample patterns;

(b) forming pairs of patterns from said sample set by pairing each sample pattern with at least one other sample pattern;

(c) determining, using the subjective judgement of at least one human, a relative degree of dissimilarity between the patterns of each said pair;

(d) sensing the collection C of patterns to produce a signal S representing each pattern of said collection;

(e) extracting machine derived measurements of selected features from signal S for each pattern of collection C to create a set X of said machine derived feature measurements;

(f) selecting from the set X of machine derived feature measurements the subset Y of machine derived feature measurements corresponding to the set of sample patterns of step (a)

(g) processing the results of steps (c) and (f) to produce a matrix of weights relating the human judgement measurements with the machine derived feature measurements for the set of sample patterns; and

(h) applying the weights from step (g) to the machine derived feature measurements for the set X, whereby, the human judgement measurements and the machine measurements are related for the entire collection C of patterns.

16. The method of claim 15, wherein said set of sample patterns are selected so as to be representative of said collection.

17. The method of claim 15, wherein the sensing step includes digitizing and storing the patterns.

18. The method of claim 15, wherein the machine derived features comprise one or more primitive measurements.

19. The method of claim 15 comprising the further step of producing an ordering consisting of patterns segregated into classes in a n-dimensional space.