BLURRING BASED CONTENT RECOGNIZER

• US 20100187311A1
• Filed: 01/27/2009
• Published: 07/29/2010
• Est. Priority Date: 01/27/2009
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Serlet, Bertrand, van der Merwe, Rudolph, Noble, Samuel Gordon, Kounitski, Stanislav, Crandall, Richard Eugene
• Granted Patent: US 8,948,513 B2
• Time in Patent Office: Days
• US Class Current: 235/462.10
• CPC Class Codes: G06T 2207/10004 Still image; Photographic image
• CPC Class Codes: G06T 2207/20076 Probabilistic image processing
• CPC Class Codes: G06T 7/11 Region-based segmentation
• CPC Class Codes: G06T 7/136 involving thresholding
• CPC Class Codes: G06T 7/143 involving probabilistic approaches, e.g. Markov random field [MRF] modelling
• CPC Class Codes: G06T 7/187 involving region growing; involving region merging; involving connected component labelling
• CPC Class Codes: G06V 30/2247 Characters composed of bars, e.g. CMC-7

Abstract

Methods, systems, and apparatus, including computer program products, for identifying regions of interest in an image and identifying a barcode in a degraded image are provided. A region of interest is identified by pre-processing an image, generating a binary image based on a metric calculated on the pre-processed image, and analyzing regions of the image identified using connected components and other analysis. A barcode is identified by searching a population of barcodes, degrading ideal image intensity profiles of candidate barcodes, and comparing the degraded ideal image intensity profiles to an image intensity profile of the degraded image.

Claims

1. A computer implemented method, comprising:

receiving an image;

pre-processing the image resulting in a pre-processed image;

calculating a metric based on the pre-processed image;

generating a binary image from the pre-processed image based on the metric;

identifying one or more regions of the binary image using connected components analysis;

selecting a region of interest in the image based on an analysis of the identified regions of the binary image; and

using a probabilistic cost function to refine the region of interest.

2. The method of claim 1, wherein:

the image includes a barcode.

3. The method of claim 2, wherein:

pre-processing the image includes applying an image gradient magnitude filter to the image.

4. The method of claim 2, wherein the analysis of the identified regions includes analyzing the mass, aspect ratio, shape, or image moment of each region.

5. A computer implemented method, comprising:

receiving a degraded image of a first barcode;

generating an image intensity profile of the degraded image;

searching a population of barcodes, the searching including selecting a candidate barcode from the population of barcodes and comparing a degraded version of an ideal image intensity profile of the candidate barcode to the image intensity profile of the degraded image; and

selecting a final barcode from the population of barcodes based on the comparison.

6. The method of claim 5, further comprising:

identifying a region of interest containing the first barcode in the degraded image; and

wherein the image intensity profile of the degraded image is an image intensity profile of the region of interest.

7. The method of claim 5, further comprising:

receiving context information about the degraded image; and

wherein the searching is biased based on the context information.

8. The method of claim 7, wherein:

the context information includes an approximation of a physical location corresponding to where the degraded image was captured.

9. The method of claim 7, wherein:

the context information includes previous selections of one or more barcodes corresponding to one or more other degraded images captured at one or more physical locations that are approximately the same as a physical location where the degraded image was captured.

10. The method of claim 7, wherein:

the context information is received from a data processing apparatus associated with one or more objects in a vicinity of where the degraded image was captured.

11. The method of claim 5, further comprising:

receiving accelerometer data regarding a device used to capture the degraded image;

estimating a motion blur in the degraded image using the accelerometer data; and

wherein the degraded version of the ideal image intensity profile of the candidate barcode is generated using the estimated motion blur.

12. The method of claim 5, further comprising:

receiving accelerometer data regarding a device used to capture the degraded image;

using the accelerometer data to estimate a degree of variance from the horizontal or vertical axis of the device at the time the degraded image was captured; and

wherein the degraded version of the ideal image intensity profile of the candidate barcode is generated using the estimated degree of variance.

13. The method of claim 5, further comprising:

receiving calibration information; and

wherein the degraded version of the ideal image intensity profile of the candidate barcode is generated using the calibration information.

14. The method of claim 5, wherein:

searching the population of barcodes further includes repeating the selecting and comparing steps for each barcode in the population of barcodes.

15. The method of claim 5, wherein:

searching the population of barcodes further includes using a genetic algorithm to direct the search.

16. The method of claim 5, further comprising:

retrieving information corresponding to the final barcode from a database.

17. The method of claim 5, wherein comparing the degraded version of the ideal image intensity profile of the candidate barcode to the image intensity profile of the degraded image further comprises:

pre-computing a degraded version of parts of ideal image intensity profiles of barcodes in the population of barcodes; and

generating the degraded version of the ideal image intensity profile of the candidate barcode by combining the identified degraded versions of parts of the ideal image intensity profile of the candidate barcode.

18. The method of claim 5, wherein comparing the degraded version of the ideal image intensity profile of the candidate barcode to the image intensity profile of the degraded image further comprises:

pre-computing a plurality of error signals for each of a plurality of regions in an image intensity profile space;

identifying an error signal corresponding to the degraded version of the ideal image intensity profile of the candidate barcode for each of the plurality of regions;

combining the identified error signals.

19. A computer implemented method, comprising:

receiving a degraded image of a first barcode;

generating an image intensity profile for the degraded image;

searching a population of barcodes, the searching including identifying a current population of barcodes and repeating the following steps one or more times;

for each barcode in the current population, calculating a fitness score comparing a degraded version of an ideal intensity profile corresponding to the barcode to an intensity profile of the degraded image; and

updating the current population using the calculated fitness scores; and

selecting a final barcode from the population of barcodes based on the calculated fitness scores.

20. A computer implemented method, comprising:

receiving a degraded image of a first barcode;

pre-processing the degraded image resulting in a pre-processed image;

calculating a metric based on the pre-processed image;

generating a binary image from the pre-processed image based on the metric;

identifying one or more regions of the binary image using connected components analysis;

selecting a region of interest in the degraded image based on an analysis of the identified regions of the binary image;

using a probabilistic cost function to refine the region of interest;

generating an intensity profile of the refined region of interest.

searching a finite population of barcodes, the searching including identifying a current population of barcodes and repeating the following steps one or more times;

for each barcode in the current population, calculating a fitness score comparing a degraded version of an ideal intensity profile corresponding to the barcode to the intensity profile of the refined region of interest; and

updating the current population using the calculated fitness scores; and

selecting a final barcode from the population of barcodes based on the calculated fitness scores.

21. A system comprising:

a processor; and

a computer-readable medium coupled to the processor and including instructions, which, when executed by the processor, causes the processor to perform operations comprising;

receiving an image;

pre-processing the image resulting in a pre-processed image;

calculating a metric based on the pre-processed image;

generating a binary image from the pre-processed image based on the metric;

identifying one or more regions of the binary image using connected components analysis;

selecting a region of interest in the image based on an analysis of the identified regions of the binary image; and

using a probabilistic cost function to refine the region of interest.

22. A system comprising:

a processor; and

a computer-readable medium coupled to the processor and including instructions, which, when executed by the processor, cause the processor to perform operations comprising;

receiving a degraded image of a first barcode from a client;

generating an image intensity profile of the degraded image;

searching a population of barcodes, the searching including selecting a candidate barcode from the population of barcodes and comparing a degraded version of an ideal image intensity profile of the candidate barcode to the image intensity profile of the degraded image;

selecting a final barcode from the population of barcodes based on the comparison; and

sending the final barcode to the client.

23. The system of claim 22, wherein the processor perform operations comprising:

receiving context information about the degraded image; and

wherein the searching is biased based on the context information.

24. The system of claim 22, wherein the processor performs operations comprising:

retrieving information corresponding to the final barcode from a database; and

sending the information to the client.

25. The system of claim 22, wherein comparing the degraded version of the ideal image intensity profile of the candidate barcode to the image intensity profile of the degraded image further comprises:

pre-computing a degraded version of parts of image intensity profiles of barcodes in the population of barcodes; and

generating the degraded version of the ideal image intensity profile of the candidate barcode by combining the identified degraded versions of the ideal image intensity profile of the candidate barcode.

26. The system of claim 22, wherein comparing the degraded version of the ideal image intensity profile of the candidate barcode to the image intensity profile of the degraded image further comprises:

pre-computing a plurality of error signals for each of a plurality of regions in an image intensity profile space;

identifying an error signal corresponding to the degraded version of the ideal image intensity profile of the candidate barcode for each of the plurality of regions;

combining the identified error signals.

27. A system comprising:

a processor; and

a computer-readable medium coupled to the processor and including instructions, which, when executed by the processor, cause the processor to perform operations comprising;

receiving a degraded image of a first barcode from a client;

generating an image intensity profile for the degraded image;

searching a population of barcodes, the searching including identifying a current population of barcodes and repeating the following steps one or more times;

for each barcode in the current population, calculating a fitness score comparing a degraded version of an ideal intensity profile corresponding to the barcode to an intensity profile of the degraded image; and

updating the current population using the calculated fitness scores;

selecting a final barcode from the population of barcodes based on the calculated fitness scores; and

sending the final barcode to the client.

28. A system comprising:

a processor; and

a computer-readable medium coupled to the processor and including instructions, which, when executed by the processor, cause the processor to perform operations comprising;

receiving a degraded image of a first barcode from a client;

pre-processing the degraded image resulting in a pre-processed image;

calculating a metric based on the pre-processed image;

generating a binary image from the pre-processed image based on the metric;

identifying one or more regions of the binary image using connected components analysis;

selecting a region of interest in the degraded image based on an analysis of the identified regions of the binary image;

using a probabilistic cost function to refine the region of interest;

generating an intensity profile of the refined region of interest.

searching a finite population of barcodes, the searching including identifying a current population of barcodes and repeating the following steps one or more times;

for each barcode in the current population, calculating a fitness score comparing a degraded version of an ideal intensity profile corresponding to the barcode to the intensity profile of the refined region of interest; and

updating the current population using the calculated fitness scores;

selecting a final barcode from the population of barcodes based on the calculated fitness scores; and

sending the final barcode to the client.

29. A computer-readable medium having instructions stored thereon, which, when executed by a processor, causes the processor to perform operations comprising:

receiving an image;

pre-processing the image resulting in a pre-processed image;

calculating a metric based on the pre-processed image;

generating a binary image from the pre-processed image based on the metric;

identifying one or more regions of the binary image using connected components analysis;

selecting a region of interest in the image based on an analysis of the identified regions of the binary image; and

using a probabilistic cost function to refine the region of interest.

30. A computer-readable medium having instructions stored thereon, which, when executed by a processor, causes the processor to perform operations comprising:

receiving a degraded image of a first barcode;

generating an image intensity profile of the degraded image;

searching a population of barcodes, the searching including selecting a candidate barcode from the population of barcodes and comparing a degraded version of an ideal image intensity profile of the candidate barcode to the image intensity profile of the degraded image; and

selecting a final barcode from the population of barcodes based on the comparison.

31. The computer-readable medium of claim 30, further having instructions stored thereon which, when executed by a processor, causes the processor to perform operations comprising:

receiving context information about the degraded image; and

wherein the searching is biased based on the context information.

32. The computer-readable medium of claim 30, further having instructions stored thereon which, when executed by a processor, causes the processor to perform operations comprising:

retrieving information corresponding to the final barcode from a database.

33. The computer-readable medium of claim 30, wherein comparing the degraded version of the ideal image intensity profile of the candidate barcode to the image intensity profile of the degraded image further comprises:

pre-computing a degraded version of parts of ideal image intensity profiles of barcodes the population of barcodes; and

generating the degraded version of the ideal image intensity profile of the candidate barcode by combining the identified degraded versions of parts of the ideal image intensity profile of the candidate barcode.

34. The computer-readable medium of claim 30, wherein comparing the degraded version of the ideal image intensity profile of the candidate barcode to the image intensity profile of the degraded image further comprises:

pre-computing a plurality of error signals for each of a plurality of regions in an image intensity profile space;

identifying an error signal corresponding to the degraded version of the ideal image intensity profile of the candidate barcode for each of the plurality of regions;

combining the identified error signals.

35. A computer-readable medium having instructions stored thereon, which, when executed by a processor, causes the processor to perform operations comprising:

receiving a degraded image of a first barcode;

generating an image intensity profile for the degraded image;

searching a population of barcodes, the searching including identifying a current population of barcodes and repeating the following steps one or more times;

for each barcode in the current population, calculating a fitness score comparing a degraded version of an ideal intensity profile corresponding to the barcode to an intensity profile of the degraded image; and

updating the current population using the calculated fitness scores; and

selecting a final barcode from the population of barcodes based on the calculated fitness scores.

36. A computer-readable medium having instructions stored thereon, which, when executed by a processor, causes the processor to perform operations comprising:

receiving a degraded image of a first barcode;

pre-processing the degraded image resulting in a pre-processed image;

calculating a metric based on the pre-processed image;

generating a binary image from the pre-processed image based on the metric;

identifying one or more regions of the binary image using connected components analysis;

selecting a region of interest in the degraded image based on an analysis of the identified regions of the binary image;

using a probabilistic cost function to refine the region of interest;

generating an intensity profile of the refined region of interest.

searching a finite population of barcodes, the searching including identifying a current population of barcodes and repeating the following steps one or more times;

for each barcode in the current population, calculating a fitness score comparing a degraded version of an ideal intensity profile corresponding to the barcode to the intensity profile of the refined region of interest; and

updating the current population using the calculated fitness scores; and

selecting a final barcode from the population of barcodes based on the calculated fitness scores.