Methods and apparatus for optically determining the acceptability of products

Claim 3

The method defined in claim 1 wherein said discriminant values collectively comprise a discriminant image F and wherein said method further comprises the steps of: converting the binary values associated with said training objects to a plurality of eigenimages Φ.sup.(j), all of said eigenimages being orthogonal to one another; and forming said discriminant image from a truncated linear combination of said eigenimages.

Claim 4

The method defined in claim 2 wherein the binary values associated with each of said training objects i collectively comprise a training image I.sup.(i), and wherein said method further comprises the step of: computing each of said eigenimages as in the equation: ##EQU9## where n is the total number of training images and the transformation matrix B is orthogonal.

Claim 5

The method defined in claim 3 wherein said step of forming said discriminant image from a truncated linear combination of said eigenimages comprises the step of: computing said discriminant image as in the equation: ##EQU10## where s is an integer less than n.

Claim 6

The method defined in claim 4 further comprising the step of: selecting the value of s for the equation in claim 4 which gives the minimum value for V(s), where V(s) is computed as in the equation: ##EQU11## where a i is a nonzero constant for all good training images and zero for any bad training images.

Claim 7

The method defined in claim 5 further comprising the step of: computing the values C j for the equation of claim 4 as in the equation: ##EQU12## where the eigenvalues γ j are the diagonal elements of a matrix G given by the equation AB=BG, where A is the real, symmetric matrix given by the dot product of every possible training image pair, and the transformation matrix B is such that BB + =B + B=1.

Claim 8

The method defined in claim 6 wherein said eigenimages are ordered such that γ 1 >γ 2 >γ 3 > . . . >γ n .

Claim 9

The method defined in claim 1 wherein said discriminant values are additionally chosen so that the sum of the squares of the discriminant values is approximately minimized.

Claim 10

The method defined in claim 1 wherein said discriminant values are additionally chosen so that the sum of the discriminant values is approximately zero.

Claim 11

The method defined in claim 1 wherein said two-dimensional images of said training objects may not be in registration with one another, and wherein, prior to said step of associating a discriminant value with each of said pixels, said method further comprises the steps of: for each training object, (f) computing the center of gravity of at least a portion of the associated two-dimensional image, and (g) shifting the associated binary values so that the centers of gravity associated with all of said training objects are approximately coincident.

Claim 12

The method defined in claim 10 wherein, after repeating steps (a)-(e) for said object, said method further comprises the steps of: computing the center of gravity of at least a portion of the two-dimensional image associated with said object; and shifting the binary values associated with said object so that the center of gravity associated with said object is approximately coincident with the approximately coincident centers of gravity associated with said training objects.

Claim 13

The method defined in claim 1 wherein a plurality of sample objects representative of the range of variation likely to occur among acceptable objects is available, and wherein, prior to said step of repeating steps (a)-(e) for said object, said method further comprises the steps of: repeating steps (a)-(e) for each sample object; computing a correlation value for each sample object by forming the dot product of said discriminant values and the binary values for said sample object; computing the average of the correlation values for all of said sample objects; computing the standard deviation of the correlation values for all of said sample objects; and computing first and second threshold correlation values respectively equal to said average of the correlation values plus or minus predetermined numbers of said standard deviation.

Claim 14

The method defined in claim 12 wherein said step of comparing the dot product of said discriminant values and the binary values for said object to said predetermined nonzero constant value comprises the step of: determining whether or not said dot product of said discriminant values and the binary values for said object is between said first and second threshold correlation values.

Claim 15

The method defined in claim 1 wherein at least one unacceptable object is available, and wherein said step of associating a discriminant value with each of said pixels comprises the steps of: repeating steps (a)-(e) for said unacceptable object; and additionally choosing said discriminant values so that the dot product of the discriminant values and the binary values associated with said unacceptable object is approximately zero.

Claim 16

The method defined in claim 1 wherein the number of pixels is substantially greater than the number of training objects.

Claim 17

Apparatus for determining whether or not a surface of an object has substantially the same appearance as the corresponding surface of a plurality of training objects comprising: means for, for each training object, (a) forming a two-dimensional image of said surface, (b) subdividing said two-dimensional image into a plurality of pixels, (c) digitizing each of said pixels by associating with each pixel an initial digital value proportional to an optical characteristic of the associated pixel, (d) edge detecting said initial digital values by processing said initial digital values to produce output digital values such that initial digital values associated with pixels at or near substantial changes in initial digital value are relatively emphasized to produce the associated output digital values, while initial digital values associated with all other pixels are relatively de-emphasized to produce the associated output digital values, and (e) binarizing each of said output digital values by associating a first binary value with each of said output digital values which is on one side of a first predetermined threshold value and by associating a second binary value with each of said output digital values which is on the other side of said first predetermined threshold value; means for associating a discriminant value with each of said pixels, each discriminant value being chosen so that, for each training object, the dot product of the discriminant values and the binary values is approximately a predetermined non-zero constant value; means for repeating functions (a)-(e) with respect to said object; and means for comparing the dot product of said discriminant values and the binary values for said object to said predetermined nonzero constant value.

Claim 18

Apparatus for determining whether or not a surface of an object has substantially the same appearance as the corresponding surface of a plurality of training objects comprising: means for, for each training object, (a) forming a two-dimensional image of said surface, (b) subdividing said two-dimensional image into a plurality of pixels, (c) digitizing each of said pixels by associating with each pixel an initial digital value proportional to an optical characteristic of the associated pixel, (d) edge detecting said initial digital values by processing said initial digital values to produce output digital values such that initial digital values associated with pixels at or near substantial changes in initial digital value are relatively emphasized to produce the associated output digital values, while initial digital values associated with all other pixels are relatively de-emphasized to produce the associated output digital values, and (e) binarizing each of said output digital values by associating a first binary value with each of said output digital values which is on one side of a first predetermined threshold value and by associating a second binary value with each of said output digital values which is on the other side of said first predetermined threshold value; means for associating a discriminant value with each of said pixels, each discriminant value being chosen so that, for each training object, the dot product of the discriminant values and the binary values is approximately a predetermined non-zero constant value; means for repeating functions (a)-(e) with respect to said object; and means for comparing the dot product of said discriminant values and the binary values for said object to said predetermined nonzero constant value.

Claim 19

The apparatus defined in claim 16 wherein said discriminant values collectively comprise a discriminant image F and wherein said apparatus further comprises: means for converting the binary values associated with said training objects to a plurality of eigenimages Φ.sup.(j), all of said eigenimages being orthogonal to one another; and means for forming said discriminant image from a truncated linear combination of said eigenimages.

Claim 20

The apparatus defined in claim 17 wherein the binary values associated with each of said training objects i collectively comprise a training image I.sup.(i), and wherein said apparatus further comprises: means for computing each of said eigenimages as in the equation: ##EQU13## where n is the total number of training images and the transformation matrix B is orthogonal.

Claim 21

The apparatus defined in claim 18 wherein said means for forming said discriminant image from a truncated linear combination of said eigenimages comprises: means for computing said discriminant image as in the equation: ##EQU14## where s is an integer less than n.

Claim 22

The apparatus defined in claim 19 further comprising: selecting the value of s for the equation of claim 19 which gives the minimum value for V(s), where V(s) is computed as in the equation: ##EQU15## where a i is a nonzero constant for all good training images and zero for any bad training images.

Claim 23

The apparatus defined in claim 20 further comprising: means for computing the values C j for the equation of claim 19 as in the equation: ##EQU16## where the eigenvalues γ j are diagonal elements of a matrix G given by the equation AB=BG, where A is the real, symmetric matrix given by the dot product of every possible training image pair, and the transformation matrix B is such that BB + =B + B =1.

Claim 24

The apparatus defined in claim 21 wherein said eigenimages are ordered such that γ 1 >γ 2 >γ 3 > . . . >γ n .

Claim 25

The apparatus defined in claim 16 wherein said discriminant values are additionally chosen so that the sum of the squares of the discriminant values is approximately minimized.

Claim 26

The apparatus defined in claim 16 wherein said discriminant values are additionally chosen so that the sum of the discriminant values is approximately zero.

Claim 27

The apparatus defined in claim 16 wherein said two-dimensional images of said training objects may not be in registration with one another, and wherein, prior to operation of said means for associating a discriminant value with each of said pixels, said apparatus further comprises: means for, for each training object, (f) computing the center of gravity of at least a portion of the associated two-dimensional image, and (g) shifting the associated binary values so that the centers of gravity associated with all of said training objects are approximately coincident.

Claim 28

The apparatus defined in claim 25 wherein said means for repeating functions (a)-(e) with respect to said object comprises: means for computing the center of gravity of at least a portion of the two-dimensional image associated with said object; and means for shifting the binary values associated with said object so that the center of gravity associated with said object is approximately coincident with the approximately coincident centers of gravity associated with said training objects.

Claim 29

The apparatus defined in claim 16 wherein a plurality of sample objects representative of the range of variation likely to occur among acceptable objects is available, and wherein, prior to operation of said means for repeating functions (a)-(e) with respect to said object, said apparatus further comprises the steps of: means for repeating functions (a)-(e) with respect to each sample object; means for computing a correlation value for each sample object by forming the dot product of said discriminant values and the binary values for said sample object; means for computing the average of the correlation values for all of said sample objects; means for computing the standard deviation of the correlation values for all of said sample objects; and means for computing first and second threshold correlation values respectively equal to said average of the correlation values plus or minus predetermined numbers of said standard deviation.

Claim 30

The apparatus defined in claim 27 wherein said means for comparing the dot product of said discriminant values and the binary values for said object to said predetermined nonzero constant value comprises: means for determining whether or not said dot product of said discriminant values and the binary values for said object is between said first and second threshold correlation values.

Claim 31

The apparatus defined in claim 16 wherein at least one unacceptable object is available, and wherein said means for associating a discriminant value with each of said pixels comprises: means for repeating functions (a)-(e) with respect to said unacceptable object; and means for additionally choosing said discriminant values so that the dot product of the discriminant values and the binary values associated with said unacceptable object is approximately zero.

Claim 32

The apparatus defined in claim 16 wherein the number of pixels is substantially greater than the number of training objects.

Claim 35

The method defined in claim 31 wherein said step of computing said discriminant image further comprises the step of: selecting the individual values which make up said discriminant image so that the sum of the squares of all of said individual values is approximately minimized.

Claim 36

The method defined in claim 31 wherein said step of computing said discriminant image further comprises the step of: selecting the individual values which make up said discriminant image so that the sum of all of said individual values is approximately zero.

Claim 37

The method defined in claim 31 wherein said eigenimages are ordered such that γ 1 >γ 2 γ 3 > . . . >γ n .