Identifying A Maximally Stable Extremal Region (MSER) In An Image By Skipping Comparison Of Pixels In The Region

• US 20140023271A1
• Filed: 03/12/2013
• Published: 01/23/2014
• Est. Priority Date: 07/19/2012
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Baheti, Pawan Kumar, Krishnamoorthi, Raghuraman, Vrcelj, Bojan, Barman, Kishor K.
• Granted Patent: US 9,014,480 B2
• Time in Patent Office: Days
• US Class Current: 382/171
• CPC Class Codes: G06V 20/63 Scene text, e.g. street names
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/147 Determination of region of interest
• CPC Class Codes: G06V 30/18076 by analysing connectivity, e.g. edge linking, connected component analysis or slices
• CPC Class Codes: G06V 30/18086 by performing operations within image blocks or by using histograms

Abstract

A difference in intensities of a pair of pixels in an image is repeatedly compared to a threshold, with the pair of pixels being separated by at least one pixel (“skipped pixel”). When the threshold is found to be exceeded, a selected position of a selected pixel in the pair, and at least one additional position adjacent to the selected position are added to a set of positions. The comparing and adding are performed multiple times to generate multiple such sets, each set identifying a region in the image, e.g. an MSER. Sets of positions, identifying regions whose attributes satisfy a test, are merged to obtain a merged set. Intensities of pixels identified in the merged set are used to generate binary values for the region, followed by classification of the region as text/non-text. Regions classified as text are supplied to an optical character recognition (OCR) system.

Claims

1. A method to identify regions, the method comprising:

receiving an image of a scene of real world;

creating a plurality of sets of positions automatically, by at least performing comparisons using multiple pluralities of pixels hereinafter compared pixels that are located in the image at corresponding positions comprised in the plurality of sets of positions;

wherein a first set in the plurality of sets of positions is created without using in any comparison, a plurality of pixels hereinafter skipped pixels that are located in the image at additional positions comprised in the first set;

wherein a first region identified by the first set is contiguous in the image, the first region comprising the compared pixels and the skipped pixels identified respectively by the corresponding positions and the additional positions;

wherein a second region is contiguous in the image, the second region being identified by positions in a second set, in the plurality of sets of positions created by the creating;

checking automatically, whether a test is satisfied by a first attribute of the first region and a second attribute of the second region;

preparing automatically, a merged set comprising the positions in the first set and the positions in the second set, based on at least an outcome of said test; and

storing automatically, in one or more memories, the merged set;

wherein the receiving, the creating, the checking, the preparing and the storing are performed by one or more processors coupled to the one or more memories.

2. The method of claim 1 further comprising:

low-pass filtering the image, hereinafter original image, prior to the creating, to obtain a low-pass image;

wherein comparisons performed by said performing use pixels located adjacent to one another in the low-pass image, thereby to exclude from the comparisons the skipped pixels of the original image.

3. The method of claim 1 wherein:

comparisons performed by said performing are between a pair of pixels that are separated in the first region from one another by one or more of the skipped pixels;

the comparisons are performed repeatedly; and

a number of pixels to be skipped in a next comparison at a next iteration are determined at least partially based on a predetermined threshold being not exceeded by a difference in intensities, between one compared pixel used in a current comparison at a current iteration and another compared pixel used in a prior comparison at a prior iteration.

4. The method of claim 1 further comprising:

using a discrete wavelet transform of the image to determine a factor; and

using at least the factor, to identify a number of pixels to be skipped in performing the creating.

5. The method of claim 4 wherein:

the factor depends on a limit being not exceeded by at least one coefficient, of the discrete wavelet transform of the image.

6. The method of claim 1 wherein:

comparisons performed by said performing are between an intensity i used as a threshold and the intensity of each pixel included in a region Qi among the first region and the second region;

said region Qi comprises a local extrema in said image; and

said region Qi is maximally stable relative to changes in a range i−

Δ

to i+Δ

, with a local minima in ratio [Qi−

Δ

−

Qi+Δ

]/Qi occurring at the intensity i.

7. The method of claim 1 wherein:

the one or more processors and the one or more memories are comprised in a handheld device; and

the image is received by the one or more processors from a camera comprised in the handheld device.

8. The method of claim 1 further comprising:

determining an attribute of a rectangular block that comprises pixels identified in the merged set; and

applying the test based on said attribute, to at least intensities of pixels identified in the merged set, to generate binary values.

9. The method of claim 8 further comprising:

classifying the rectangular block as text or non-text.

10. A handheld device to generate regions of binary values for use in text recognition, the handheld device comprising:

one or more memories comprising an image of a scene of real world;

one or more processors operatively coupled to the one or more memories to execute therefrom a plurality of instructions, the plurality of instructions comprising;

first instructions to create a plurality of sets of positions automatically, by at least performing comparisons using multiple pluralities of pixels hereinafter compared pixels that are located in the image at corresponding positions comprised in the plurality of sets of positions;

wherein a first set in the plurality of sets of positions is created without using in any comparison, a plurality of pixels hereinafter skipped pixels that are located in the image at additional positions comprised in the first set;

wherein a first region identified by the first set is contiguous in the image, the first region comprising the compared pixels and the skipped pixels identified respectively by the corresponding positions and the additional positions;

wherein a second region is contiguous in the image, the second region being identified by positions in a second set, in the plurality of sets of positions created by the creating;

second instructions to check, whether a test is satisfied by a first attribute of the first region and a second attribute of the second region;

third instructions to prepare a merged set comprising the positions in the first set and the positions in the second set, based on at least an outcome of said test; and

fourth instructions to store in at least one memory, the merged set.

11. The handheld device of claim 10 further comprising:

fifth instructions to low-pass filter the image, hereinafter original image, prior to execution of the first instructions, to obtain a low-pass image;

wherein comparisons performed by said performing are performed using pixels located adjacent to one another in the low-pass image, thereby to exclude from the comparisons the skipped pixels of the original image.

12. The handheld device of claim 10 wherein:

comparisons performed by said performing are between a pair of pixels that are separated in the first region from one another by one or more of the skipped pixels;

the comparisons are performed repeatedly; and

a number of pixels to be skipped in a next comparison at a next iteration are determined at least partially based on a predetermined threshold being not exceeded by a difference in intensities, between one compared pixel used in a current comparison at a current iteration and another compared pixel used in a prior comparison at a prior iteration.

13. The handheld device of claim 10 wherein:

comparisons performed by said performing are between an intensity i used as a threshold and the intensity of each pixel included in a region Qi among the first region and the second region;

said region Qi is maximally stable relative to changes in a range i−

Δ

to i+Δ

, with a local minima in ratio [Qi−

Δ

−

Qi+Δ

]/Qi occurring at the intensity i.

14. The handheld device of claim 10 wherein the plurality of instructions comprise:

fifth instructions to determine an attribute of a rectangular block that comprises pixels identified in the merged set and apply the test based on said attribute, to at least intensities of the pixels identified in the merged set, to generate binary values.

15. The handheld device of claim 10 wherein the plurality of instructions comprise:

fifth instructions to classify a rectangular block as text or non-text.

16. The handheld device of claim 10 further comprising:

a camera to capture the image and store the image in the one or more memories.

17. One or more storage media comprising a sequence of instructions, which, when executed cause a processor to perform operations, the sequence of instructions comprising:

first instructions to create a plurality of sets of positions automatically, by at least performing comparisons using multiple pluralities of pixels hereinafter compared pixels that are located in an image at corresponding positions comprised in the plurality of sets of positions;

wherein a first set in the plurality of sets of positions is created without using in any comparison, a plurality of pixels hereinafter skipped pixels that are located in the image at additional positions comprised in the first set;

wherein a first region identified by the first set is contiguous in the image, the first region comprising the compared pixels and the skipped pixels identified respectively by the corresponding positions and the additional positions;

wherein a second region is contiguous in the image, the second region being identified by positions in a second set, in the plurality of sets of positions created by the creating;

second instructions to check, whether a test is satisfied by a first attribute of the first region and a second attribute of the second region;

third instructions to prepare a merged set comprising the positions in the first set and the positions in the second set, based on at least an outcome of said test; and

fourth instructions to store in at least one memory, the merged set.

18. The one or more storage media of claim 17 wherein the sequence of instructions comprise:

fifth instructions to low-pass filter the image, hereinafter original image, prior to execution of the first instructions, to obtain a low-pass image;

wherein comparisons performed by execution of the first instructions are performed using pixels located adjacent to one another in the low-pass image, thereby to exclude from the comparisons the skipped pixels of the original image.

19. The one or more storage media of claim 17 wherein:

comparisons performed by execution of the first instructions are between a pair of pixels that are separated in the first region from one another by one or more of the skipped pixels;

the comparisons are performed repeatedly; and

a number of pixels to be skipped in a next comparison at a next iteration are determined at least partially based on a predetermined threshold being not exceeded by a difference in intensities, between one compared pixel used in a current comparison at a current iteration and another compared pixel used in a prior comparison at a prior iteration.

20. The one or more storage media of claim 17 wherein:

comparisons performed by execution of the first instructions are between an intensity i used as a threshold and the intensity of each pixel included in a region Qi among the first region and the second region;

said region Qi is maximally stable relative to changes in a range i−

Δ

to i+Δ

, with a local minima in ratio [Qi−

Δ

−

Qi+Δ

]/Qi occurring at the intensity i.

21. The one or more storage media of claim 17 wherein the sequence of instructions comprise:

fifth instructions to determine an attribute of a rectangular block that comprises pixels identified in the merged set;

sixth instructions to apply the test based on said attribute, to at least intensities of pixels identified in the merged set, to generate binary values; and

seventh instructions to classify the rectangular block as text or non-text.

22. An apparatus for generating binary values for use in text recognition, the apparatus comprising:

first means for creating a plurality of sets of positions automatically, by at least performing comparisons using multiple pluralities of pixels hereinafter compared pixels that are located in an image at corresponding positions comprised in the plurality of sets of positions;

wherein a first set in the plurality of sets of positions is created without using in any comparison, a plurality of pixels hereinafter skipped pixels that are located in the image at additional positions comprised in the first set;

wherein a first region identified by the first set is contiguous in the image, the first region comprising the compared pixels and the skipped pixels identified respectively by the corresponding positions and the additional positions;

wherein a second region is contiguous in the image, the second region being identified by positions in a second set, in the plurality of sets of positions created by the creating;

second means for checking, whether a test is satisfied by a first attribute of the first region and a second attribute of the second region;

third means for preparing a merged set comprising the positions in the first set and the positions in the second set, based on at least an outcome of said test; and

fourth means for storing in at least one memory, the merged set.

23. The apparatus of claim 22 further comprising:

means for low-pass filtering the image, hereinafter original image, coupled to the first means to supply thereto a low-pass image;

wherein comparisons performed by operation of the first means are performed using pixels located adjacent to one another in the low-pass image, thereby to exclude from the comparisons the skipped pixels of the original image.

24. The apparatus of claim 22 wherein:

comparisons performed by operation of the first means are between a pair of pixels that are separated in the first region from one another by one or more of the skipped pixels;

the comparisons are performed repeatedly; and

a number of pixels to be skipped in a next comparison at a next iteration are determined at least partially based on a predetermined threshold being not exceeded by a difference in intensities, between one compared pixel used in a current comparison at a current iteration and another compared pixel used in a prior comparison at a prior iteration.

25. The apparatus of claim 22 wherein:

comparisons performed by operation of the first means are between an intensity i used as a threshold and the intensity of each pixel included in a region Qi among the first region and the second region;

said region Qi is maximally stable relative to changes in a range i−

Δ

to i+Δ

, with a local minima in ratio [Qi−

Δ

−

Qi+Δ

]/Qi occurring at the intensity i.

26. The apparatus of claim 22 further comprising:

means for determining an attribute of a rectangular block that comprises pixels identified in the merged set;

means for applying the test based on said attribute, to at least intensities of the pixels identified in the merged set, to generate a plurality of binary values; and

means for classifying the rectangular block as text or non-text.