Machine learning procedures for generating image domain feature detector structuring elements

• US 4,821,333 A
• Filed: 08/22/1986
• Issued: 04/11/1989
• Est. Priority Date: 08/22/1986
• Status: Expired due to Fees

• Current Assignee: Environmental Research Institute of Michigan
• Original Assignee: Environmental Research Institute of Michigan
• Inventors: Gillies, Andrew M.
• Primary Examiner(s): Boudreau, Leo H.
• Assistant Examiner(s): Couso, Jose L.
• Application Number:
  US06/899,518
• Time in Patent Office: 963 Days
• Field of Search: 364/513, 364/518, 382/1, 382/9, 382/10, 382/14-16, 382/27, 382/28, 382/36, 382/37, 382/39, 382/41, 382/48, 382/49, 382/55
• US Class Current: 382/308
• CPC Class Codes: G06F 18/21 Design or setup of recognition systems or techniques; Extraction of features in feature space; Blind source separation
• CPC Class Codes: G06N 3/126 Evolutionary algorithms, e.g. genetic algorithms or genetic programming
• CPC Class Codes: G06V 10/36 Applying a local operator, i.e. means to operate on image points situated in the vicinity of a given point; Non-linear local filtering operations, e.g. median filtering

Abstract

A method for generating a program to be used in two-class or multi-class image domain feature discrimination problems. A feature discrimination problem is solved by a serial neighborhood processor which is programmed to perform a series of mathematical morphological transformations as specified by structuring elements and morphological operations. The morphological operations are expressed in a program form typically developed by an experienced human, while the sequence of structuring elements used with the program form are generated by an algorithm which iteratively tests and scores the performance of various sequences of transformations, each sequence of transformations being representable by a binary sequence which is allowed to evolve by the processes of mutation and cross-linking. Acceptable forms of binary digit sequences are also disclosed.

Claims

1. A method for generating a set of structuring elements for use in an image processing program in a computer, the image processing program being operative to apply feature detectors to an input image comprising an input digital matrix of points having digital values to generate a corresponding transformed digital matrix of points having digital values, each point of said transformed digital matrix having a digital value which is a function of the digital value of a corresponding point in said input digital matrix and/or the digital values of points immediately neighboring said corresponding point in said input digital matrix, the transformed digital matrix containing either no points having nonzero values or at least one point having a nonzero value, each featuare detector consisting of a program form including a predetermined series of morphological operations applied to the input digital matrix and a spatial constant component comprising a set structuring elements, the method comprising the steps of:

(a) selecting a plurality of sets of structuring elements;

(b) representing each set of structuring elements in a single binary code word chromosome in accordance with a predetermined encoding technique, thereby producing a plurality of said chromosomes;

(c) applying a plurality of featuare detectors equal in number to the number of said plurality of chromosomes to a first set of images known to belong to a predetermined class to and a second set of images known not to belong to said predetermined class, each feature detector consisting of said program form and a unique one of said plurality of chromosomes, each feature detector thereby producing a transformed digital matrix containing either no points having nonzero values or at least one point having a nonzero value;

(d) associating a score with each feature detector based upon the number of input images from said first set of input images in which said feature detector produces a transformed digital matrix containing at least one point having a nonzero value and the number of input images from said second set of input images in which said feature detector produces a transformed digital matrix containing no point having a nonzero value;

(e) determining whether the score for any of said plurality of feature detectors meets a predetermined criterion;

(f) if the score of at least one of said plurality of feature detectors meets said predetermined criterion, identifying the set of structuring elements represented by the single binary code word chromosome for one such feature detector having a score meeting said predetermined criterion said identified set of structuring elements being the set of structuring elements generated by the method;

(g) if the score of none of said plurality of feature detectors meets said predetermined criterion

(1) producing a succeeding plurality of chromosomes representing a succeeding plurality of sets of structural elements by randomly selecting a subset of said plurality of chromosomes where the probability of selection of any chromosome of said plurality of chromosomes is proportional to the score associated with the feature detector employing that chromosome, and augmenting said subset of chromosomes with chromosomes corresponding to modifications and/or combinations of chromosomes of said subset of chromosomes,

(2) repeating said step of applying a plurality of feature detectors to said first set of images known to belong to said predetermined class and to said second set of images known not to belong to said predetermined class employing said succeeding plurality of chromosomes,

(3) repeating said step of associating a score with each feature detector, and

(4) repeating said step of determining whether

the score for any of said plurality of feature

detectors meets said predetermined criterion,

until the score of at least one of said plurality of feature detectors meets said predetermined criterion.

3. The method of claim 1, wherein said score of a feature detector F, is calculated by the formula

4. The method of claim 1, wherein:

said succeeding plurality of chromosomes includes a predetermined number of chromosomes.

5. The method of claim 4, wherein:

said subset of chromosomes is approximately three quarters of said plurality of chromosomes.

6. The method of claim 1, wherein:

said subset of chromosomes is augmented by at least one chromosome created from a corresponding chromosome in said subset of chromosomes by random alteration of at least one individual bit of said corresponding chromosome.

7. The method of claim 1, wherein:

said subset of chromosomes is augmented by at least one chromosome created having an initial group of bits identical to the initial group of bits of a first corresponding chromosome of said subset of chromosomes and a final group of bits identical to the final group of bits of a second corresponding chromosome of said subset of chromosomes.

8. The method of claim 1, wherein:

said subset of chromosomes is augmented by at least one augmentation chromosome created having an initial group of bits identical to the initial bits of a first corresponding chromosome of said subset of chromosomes and a final group of bits identical to the final bits of a second corresponding chromosome of said subset of chromosomes, said augmentation chromosome further subject to random alteration of at least one individual bit.

9. The method of claim 1, wherein:

said step of representing each set of structuring elements by a binary code word chromosome includes representing each structuring element of said set of structuring elements by a corresponding predetermined subset of the bits of said binary code word chromosome.

10. The method of claim 9, wherein:

said step of representing each set of structuring elements by a binary code word chromosome includes representing at least one structuring element by N elemental structuring elements, each elemental structuring element represented by an M-bit string, said at least one structuring element formed by sequential dilation of said N elemental structuring elements.

11. The method of claim 10, wherein:

said M-bit strings each include 6 bits and said N elemental structuring elements comprise 64 elemental structuring elements, the 64 elemental structuring elements including an elemental structuring element consisting of an origin point and all possible elemental structuring elements consisting of an origin point and one or more points hexagonally adjacent to the origin point

12. The method of claim 10, wherein:

N is 10.

13. The method of claim 9, wherein:

said step of representing each set of structuring elements by a binary code word chromosome includes representing at least one structuring element by 4 M-bit strings, the first M-bit string representing a first repetition number, the second M-bit string representing an elemental structuring element, the third M-bit string representing a second repetition number and the fourth M-bit string representing an elemental structuring element, said at least one structuring element formed by dilation of the elemental structuring element represented by said second M-bit string dilated by itself a number of times equal to said first repetition number with the elemental structuring element represented by said fourth M-bit string dilated by itself a number of times equal to said second repetition number.

14. The method of claim 13, wherein:

said M-bit strings each include 4 bits and said first M-bit string representing said first repetition number and said third M-bit string representing said second repetition number are each in the range between 1 and 15 inclusive in accordance with a gray code in which the M-bit strings representing consecutive numbers differ in only a single bit.

15. The method claimed in claim 13 wherein:

said M-bit strings each include 4 bits and said second M-bit string and said fourth M-bit string represents elemental structuring elements by the same encoding technique, said encoding technique enabling said second M-bit string and said fourth M-bit string to represent all possible elemental structuring elements consisting of an origin point and one point hexagonally adjaacent to the origin point and a subset of all possible elemental structural elements consisting of an origin point and two or more points hexagonally adjacent to the origin point.

16. The method of claim 9, wherein:

said step of representing each set of structuring element by a binary code word chromosome includes representing at least one structuring element by 3 M-bit strings, the first M-bit string representing a first repetition number, the second M-bit string representing a first elemental structuring element according to a first encoding and a second elemental structuring element according to a second encoding and the third M-bit string representing a second repetition number, said structuring element formed by dilation of said first elemental structuring element representing a second repetition number, said structuring element formed by dilation of said first elemental structuring element represented by the second M-bit string in accordance with said first encoding dilated by itself a number of times equal to said first repetition number with said second elemental structuring element represented by said second M-bit string in accordance with said second encoding dilated by itself a number of times equal to said second repetition number.

17. The method of claim 16, wherein:

said M-bit strings each include 4 bits and said first M-bit string representing said first repetition number and said third M-bit string rerresenting said second repetition number are each in range between 1 and 15 inclusive in accordance with a gray code in which the M-bit strings representing consecutive numbers differ in only a single bit.

18. The method claimed in claim 16 wherein:

said M-bit strings each include 4 bits and said first encoding technique enabling said second M-bit string to represent all possible elemental structuring elements consisting of one point hexagonally adjacent to an origin point and said second encoding technique enabling said second M-bit string to represent all possible elemental structuring elements consisting of one point hexagonally adjacent to an origin point.

19. The method of claim 9, wherein:

each set of structuring elements includes a plurality of structuring elements; and

a first predetermined subset of bits of said single binary code word chromosome representing a first structuring element of said plurality of structuring elements represents its corresponding structuring element in an encoding techniue which differs from the encoding technique by which at least one other predetermined subset of bits of said single binary code word chromosome represents its corresponding structuring element.

2. The method of claim I, wherein said step of selecting a plurality of sets of structuring elements consists of randomly selecting a predetermined number of structuring elements.

20. A method for generating a plurality of sets of structuring elements for use in an image processing program in a computer, the image processing program being operative to apply feature detectors to an input image comprising an input digital matrix of points having digital values to generate a corresponding transformed digital matrix of points having digital values, each point of said transformed digital matrix having a digital value which is a function of the digital value of a corresponding point in said input digital matrix and/or the digital values of points immediately neighboring said corresponding point in said input digital matrix, the transformed digital matrix containing either no points having nonzero values or at least one point having a nonzero value, each feature detector consisting of a program form including a predetermined series of morphological operations applied to the input digital matrix and a spatial constant component comprising a set structuring elements, the method comprising the steps of:

(a) selecting a plurality of sets of structuring elements;

(b) representing each set of structuring elements in a single binary code word chromosome in accordance with a predetermined encoding technique, thereby producing a plurality of said chromosomes;

(c) applying a plurality of feature detectors equal in number to the number of said plurality of chromosomes to a set of training images, each training image known to belong to one class of a predetermined set of classes, each feature detector consisting of said program form and a unique one of said plurality of chromosomes, each feature detector having a response of either a first type by producing a transformed digital matrix containing no points having nonzero values or of a second type by producing at least one point having a nonzero value;

(d) computing a weighting factor for each feature detector for each class of said predetermined set of classes for each of said first type and said second type response, the weighting factor for a particular feature detector for a particular class for a particular response type based upon the number of training images belonging to said class for which said feature detector produces a response of the particular response type and the number of training images not belonging to said class for which said feature detector produces a response of the particular response type;

(e) computing a system response vector having a component for each class of said predetermined set of classes for each training image of said set of training images, the component for a particular class for a particular training image based upon the summation over all feature detectors of the weighting factors for each feature detector for the response type which the feature detector produces for the particular training image for the particular class;

(f) associating a score with each feature detector for each class, the score for each particular class based upon the capability of said feature detector to produce a response of one of said first and second types for training images belonging to the particular class and a response of the other of said first and second types for training images not belonging to the particular class;

(g) determining whether there exists a set of feature detectors having scores for each class which meets a predetermined criterion;

(h) if there exists a set of feature detectors having scores for each class which meets said predetermined criterion, identifying the set of structuring elements represented by the single binary code word chromosome for each feature detector of said set of feature detectors, said identified sets of structuring elements being the sets of structuring elements generated by the method;

(i) if there does not exist a set of feature detectors having scores for each class which meets said predetermined criterion,

(1) producing a succeeding plurality of chromosomes repre se nting a succeeding plurality of sets of structural elements by randomly selecting a subset of said plurality of chromosomes where the probability of selection of any chromosome of said plurality of chromosomes is proportional to the score associated with the feature detector employing that chromosome, and augmenting said subset of chromosomes with chromosomes corresponding to modifications and/or combinations'"'"' of chromosomes of said subset of chromosomes,

(2) repeating said step of applying a plurality of feature detectors to said set of training images,

(3) repeating said step of computing a weighting factor for each feature detector for each class of said predetermined set of classes for each of said first type and said second type response,

(4) repeating said step of computing a system response vector having a component for each class of said predetermined set of classes for each training image of said set of training images,

(5) repeating said step of associating a score with each feature detector for each class, and until there exists a set of feature detectors having scores for each class which meets said predetermined criterion.

21. The method of claim 20, wherein:

said step of representing each set of structuring elements by a binary code word chromosome includes representing each structuring element of said set of structuring elements by a corresponding predetermined subset of the bits of said binary code word chromosome.

22. The method of claim 21, wherein:

said step of representing each set of structuring elements by a binary code word chromosome includes representing at least one structuring element by N elemental structuring elements, each elemental structuring element represented by an M-bit string, said at least one structuring element formed by sequential dilation of said N elemental structuring elements.

23. The method of claim 22, wherein:

said M-bit strings each include 6 bits and said N elemental structuring elements comprise 64 elemental structuring elements, the 64 elemental structuring elements including an elemental structuring element consisting of an origin point and all possible elemental structuring elements consisting of an origin point and one or more points hexagonally adjacent to the origin point.

24. The method of claim 22, wherein:

N is 10.

25. The method of claim 21 wherein:

said step of representing each set of structuring elements by a binary code word chromosome includes representing at least one structuring element by 4 M-bit strings, the first M-bit string representing a first repetition number, the second M-bit string representing an elemental structuring element, the third M-bit string representing a second repetition number and the fourth M-bit string representing an elemental structuring element, said at least one structuring element formed by dilation of the elemental structuring element represented by said second M-bit string dilated by itself a number of times equal to said first repetition number with the elemental structuring element represented by said fourth M-bit string dilated by itself a number of times equal to said second repetition number.

26. The method of claim 25, wherein:

said M-bit strings each include 4 bits and said first M-bit string representing said first repetition number and said third M-bit string representing said second repetition number are each in the range between 1 and 15 inclusive in accordance with a gray code in which the M-bit strings representing consecutive numbers differ in only a single bit.

27. The method claimed in claim 25 wherein:

said M-bit strings each include 4 bits and said second M-bit string and said fourth M-bit string represents elemental structuring elements by the same encoding technique, said encoding technique enabling said second M-bit string and said fourth M-bit string to represent all possible elemental structuring elements consisting of an origin point and one point hexagonally adjacent to the origin point and a subset of all possible elemental structural elements consisting of an origin point and two or more points hexagonally adjacent to the origin point.

28. The method of claim 21, wherein:

said step of representing each set of structuring element by a binary code word chromosome includes representing at least one structuring element by 3 M-bit strings, the first M-bit string representing a first repetition number, the second M-bit string representing a first elemental structuring element according to a first encoding and a second elemental structuring element according to a second encoding and the third M-bit string representing a second repetition number, said structuring element formed by dilation of said first elemental structuring element represented by the second M-bit string in accordance with said first encoding dilated by itself a number of times equal to said first repetition number with said second elemental string represented by said second M-bit string in accordance with said second encoding dilated by itself a number of times equal to said second repetition number.

29. The method of claim 28, wherein:

said M-bit strings each include 4 bits and said first M-bit string representing said first repetition number and said third M-bit string representing said second repetition number are each in range between 1 and 15 inclusive in accordance with a gray code in which the M-bit strings representing consecutive numbers differ in only a single bit.

30. The method of claim 21, wherein:

each set of structuring elements includes a plurality of structuring elements; and

a first predetermined subset of bits of said single binary word chromosome representing a first structuring element of said plurality of structuring elements represents its corresponding structuring element in an encoding technique which differs from the encoding technique by which at least one other predetermined subset of bits of said single binary word chromosome represents its corresponding structuring element.

31. The method of claim 20, wherein:

said succeeding plurality of chromosomes includes a predetermined number of chromosomes.

32. The method of claim 31, wherein:

said subset of of chromosomes is approximately three quarters of said plurality of chromosomes.

33. The method of claim 20, wherein:

said subset of chromosomes is augmented by at least one chromosome created from a corresponding chromosome in said subset of chromosomes by random alteration of at least one individual bit of said corresponding chromosome.

34. The method of claim 20, wherein:

said subset of chromosomes is augmented by at least one chromosome created having group of bits identical to the initial group of bits of a first corresponding chromosome of said subset of chromosomes and a final group of bits identical to the final group of bits of a second corresponding chromosome of said subset of chromosomes.

35. The method of claim 20, wherein:

said subset of chromosomes is augmented by at least one augmentation chromosome created having an initial group of bits identical to the initial group of bits corresponding chromosome of said subset of chromosomes and a final group of bits identical to the final group of bits of a second corresponding chromosome of said subset of chromosomes, said augmentation chromosome further subject to random alteration of at least one individual bit.

36. The method of claim 20, wherein;

the weighting factor for the feature detector F, the response type R and the class C is computed according to the formula;

##EQU5## where N(F,R,C) is the number of training images of the set of training images within the class C receiving the response type R upon application of feature detector F, N(F,R,˜

C) is the number of training images of the set of training images not within the class C receiving the response R upon application of feature detector F, and ? is a predetermined constant.

37. The method of claim 36 wherein:

the sytem response vector for each class is computed according to the formula ##EQU6## where R(F,1) is the response type upon application of feature detector F to training image I.

38. The method of claim 37, further comprising the step of:

determining a system classification response to an image I by selecting the class C as the system classification response which provides the maximum system response vector S(C,I).

39. The method claimed in claim 28 wherein:

said M-bit strings each include 4 bits and said said first encoding technique enabling said second M-bit string to represent all possible elemental structuring elements consisting of one point hexagonally adjacent to an origin point and said second encoding technique enabling said second M-bit string to represent all possible elemental structuring elements consisting of one point hexagonally adjacent to an origin point.

40. The method of claim 36 wherein:

the step of assorting a score with each feature detector includes

computing a safety margin for each feature detector F with respect to each class C and training image I according to the formula

space="preserve" listing-type="equation">M(F,C,I)=W(F,R(F,I), C(I))-W(F,R(F,I),C)

where (R(F,I) is the response type upon application of the feature vector F to the training image I and C(I) is the class of the training image I,

computing a system safety margin with respect to a class C and a training image I according to the formula ##EQU7## and computing the feature detector score according to the following formula ##EQU8## where K1 is a positive constant.

41. The method of claim 20, wherein said step of selecting a plurality of sets of structuring elements consists of randomly selecting a predetermined number of structuring elements.