Devices, systems, and methods for anomaly detection

Patent metadata

Field	Value
Publication number	US-10410084-B2
Application number	US-201715793759-A
Country	US
Kind code	B2
Filing date	Oct 25, 2017
Priority date	Oct 26, 2016
Publication date	Sep 10, 2019
Grant date	Sep 10, 2019

Abstract

Devices, systems, and methods obtain a first image, obtain a second image, calculate respective distances between a histogram from a patch in the first image to respective histograms from patches in the second image, and identify a patch in the second image that is most similar to the patch in the first image based on the respective distances.

First claim

The invention claimed is:

1. A device comprising:
one or more processors; and
one or more computer-readable media that are coupled to the one or more processors and that include instructions for
obtaining a first image,
obtaining a second image, and
calculating respective distances between a histogram from a patch in the first image and respective histograms from patches in the second image,
wherein calculating the respective distances is based in part on a no-cost shift, and
wherein the no-cost shift indicates a shift
that is applied to each bin in either the histogram from the patch in the first image or at least one of the respective histograms from the patches in the second image and
that does not count toward the distance between the histogram from the patch in the first image and the at least one of the respective histograms from the patches in the second image.

2. The device of claim 1 , wherein the patches in the second image include a central patch and other patches that are offset from the central patch.

3. The device of claim 2 , wherein the central patch has an x, y position in the second image that is identical to an x, y position of the patch in the first image.

4. The device of claim 1 , wherein the patches in the second image partially overlap each other.

5. The device of claim 4 , wherein each patch in the first image and the second image is composed of two or more respective feature patches.

6. The device of claim 5 , wherein each feature patch partially overlaps another feature patch.

7. The device of claim 1 , wherein the no-cost shift is based on a number of surplus pixels and on a total number of pixels.

8. The device of claim 1 , wherein calculating each of the respective distances includes calculating a difference between a number of pixels in a bin at index i in one histogram and a number of pixels in a bin at index i+s in another histogram, where s is the no-cost shift.

9. The device of claim 1 , wherein the one or more computer-readable media further include instructions for identifying a patch in the second image that is most similar to the patch in the first image based on the respective distances.

10. A method comprising:
obtaining a first image;
obtaining a second image; and
calculating respective dissimilarity scores between a histogram from a patch in the first image and respective histograms from patches in the second image,
wherein calculating the respective dissimilarity score between the histogram from the patch in the first image and at least one of the respective histograms from the patches in the second image is based in part on a no-cost shift, and
wherein the no-cost shift indicates a shift
that is applied to a plurality of bins in either the histogram from the patch in the first image or the at least one of the respective histograms from the patches in the second image and
that does not count toward the dissimilarity score between the histogram from the patch in the first image and the at least one of the respective histograms from the patches in the second image.

11. The method of claim 10 , wherein the dissimilarity score is an Earth Mover's Distance.

12. The method of claim 11 , wherein the Earth Mover's Distance is a shift-invariant Earth Mover's Distance.

13. The method of 10 , wherein the patches in the second image partially overlap each other.

14. The method of claim 10 , further comprising:
identifying a patch in the second image that is most similar to the patch in the first image based on the respective dissimilarity scores.

15. The method of claim 14 , further comprising:
adding the dissimilarity score of the patch in the second image that is most similar to the patch in the first image to an image-similarity map.

16. The method of claim 10 , wherein calculating each of the respective dissimilarity scores includes calculating a difference between a number of pixels in a bin at index i in one histogram and a number of pixels in a bin at index i+s in another histogram, where s is the no-cost shift.

17. One or more computer-readable media storing computer-executable instructions that, when executed by one or more computing devices, cause the one or more computing devices to perform operations comprising:
obtaining a first image;
obtaining a second image; and
calculating respective dissimilarity scores between a histogram from a first patch in the first image and respective histograms from patches in the second image,
wherein calculating the respective dissimilarity score between the histogram from the first patch in the first image and at least one of the respective histograms from the patches in the second image is based in part on a no-cost shift, and
wherein the no-cost shift indicates a shift
that is applied to a plurality of bins in either the histogram from the first patch in the first image or the at least one of the respective histograms from the patches in the second image and
that does not count toward the dissimilarity score between the histogram from the first patch in the first image and the at least one of the respective histograms from the patches in the second image.

18. The one or more computer-readable media of claim 17 ,
further comprising:
dividing the first image into a plurality of patches,
wherein the plurality of patches includes the first patch,
wherein each patch of the plurality of patches includes two or more feature patches, and
wherein each of the two or more feature patches overlaps another feature patch.

19. The one or more computer-readable media of claim 17 ,
wherein calculating the respective dissimilarity scores between the histogram from the first patch in the first image and the respective histograms from the patches in the second image includes calculating a difference between a number of pixels in a bin at index i in one histogram and a number of pixels in a bin at index i+s in another histogram, where s is the no-cost shift.

20. The one or more computer-readable media of claim 17 , wherein the no-cost shift is based on a number of surplus pixels and on a total number of pixels.

Assignees

• Canon Virginia Inc

Inventors

• Huang Hung Khei
• Denney Bradley Scott
• Yang Yang

Classifications

• G06T7/0002 Primary

  Inspection of images, e.g. flaw detection · CPC title

• G06V10/98

  Detection or correction of errors, e.g. by rescanning the pattern or by human intervention; Evaluation of the quality of the acquired patterns · CPC title

• G06V10/50

  by performing operations within image blocks; by using histograms, e.g. histogram of oriented gradients [HoG]; by summing image-intensity values; Projection analysis · CPC title

• G06F2218/08

  Feature extraction · CPC title

• G06V10/758

  Involving statistics of pixels or of feature values, e.g. histogram matching · CPC title