RULES FOR MERGING BLOCKS OF CONNECTED COMPONENTS IN NATURAL IMAGES

• US 20130194448A1
• Filed: 01/23/2013
• Published: 08/01/2013
• Est. Priority Date: 01/26/2012
• Status: Abandoned Application

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Baheti, Pawan Kumar, Gore, Dhananjay Ashok, Agarwal, Ankit
• Application Number:
  US13/748,574
• Publication Number:
  US 20130194448A1
• Time in Patent Office: Days
• US Class Current: 348/222.1
• CPC Class Codes: G06T 11/60 Editing figures and text; Combining figures or text
• 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/18095 Summing image-intensity values; Projection and histogram analysis
• CPC Class Codes: G06V 30/413 Classification of content, e.g. text, photographs or tables

Abstract

An electronic device and method may capture an image of an environment, followed by identification of blocks of connected components in the image. A test for overlap of spans may be made, between a span of a block selected (e.g. for having a line of pixels) and another span of an adjacent block located above, or below, or to the left, or to the right of the selected block and when satisfied, these two blocks are merged. Blocks may additionally be tested, e.g., for relative heights of the two blocks, and/or aspect ratio of either or both blocks, etc. Classification of a merged block as text or non-text may use attributes of the merged block, such as location of a horizontal pixel line, number of vertical pixel lines, and number of black-white transitions and number of white-black transitions in a subset of rows located below the horizontal pixel line.

Claims

1. A method to determine whether to merge blocks of regions of an image, the method comprising:

checking whether a first block and a second block that are located adjacent to one another and not overlapping one another in the image are such that a first projection of the first block on a straight line and a second projection of the second block on the straight line satisfy a test of overlap;

wherein the first block comprises a first region in the image with a first plurality of pixels that are contiguous with one another and comprising a first local extrema of intensity in the image;

wherein the second block comprises a second region in the image with a second plurality of pixels that are contiguous with one another and comprising a second local extrema of intensity in the image;

merging a first set of positions indicative of the first region in the first block with a second set of positions indicative of the second region in the second block to obtain a merged set of positions in a merged block, based at least on an outcome of the test of overlap;

wherein the first region and the second region do not contact one another in the merged block;

wherein the merged block comprises at least the first plurality of pixels in the first block and the second plurality of pixels in the second block; and

storing information related to the merged block in a memory;

wherein at least one of the checking, the merging and the storing are performed by one or more processors.

2. The method of claim 1 wherein:

the second projection is smaller than the first projection; and

the test of overlap is satisfied when the second projection is entirely overlapped by the first projection.

3. The method of claim 1 wherein the test of overlap is hereinafter first test, and the method further comprises:

checking whether a first additional projection and a second additional projection of the first block and the second block respectively on an additional straight line perpendicular to the straight line satisfy a second test;

wherein the merging is further based on at least the outcome of the second test.

4. The method of claim 3 wherein:

the first test is satisfied when a portion of the second projection overlapped by the first projection, is less than a first predetermined percentage; and

the second test is satisfied when the portion of the second additional projection overlapped by the first additional projection, is greater than a second predetermined percentage.

5. The method of claim 1 further comprising:

checking whether an additional test comparing a height of the first block to the height of the second block is satisfied;

wherein the height of the first block and the height of the second block are both in a first direction that is perpendicular to a second direction of the straight line;

wherein the merging is further based on at least the outcome of the additional test.

6. The method of claim 5 wherein:

the second projection is smaller than the first projection; and

the additional test is satisfied when the height of the second block is between two predetermined fractions of the height of the first block.

7. The method of claim 1 further comprising:

checking whether an additional test on an aspect ratio of the second block is satisfied, when the second projection is smaller than the first projection;

wherein the merging is further based on at least the outcome of the additional test.

8. The method of claim 1 further comprising:

checking whether an additional test is satisfied, on a space between the first block and the second block in a direction perpendicular to the straight line;

wherein the merging is further based on at least the outcome of the additional test.

9. The method of claim 8 wherein:

when the second block is located above the first block, the additional test compares a distance of the space to a first predetermined limit thereon; and

when the second block is located below the first block, the additional test compares the distance of the space to a second predetermined limit thereon.

10. The method of claim 1 wherein:

the second projection is smaller than the first projection;

the method further comprises checking whether an additional test is satisfied, for presence of the pixels of a common binary value in a binarized version of the image along an additional straight line passing through at least the first block; and

wherein the merging is further based on at least the outcome of the additional test.

11. The method of claim 1 wherein:

prior to the checking, the first block and the second block are not classified as text or non-text;

the method further comprises verification of the merged block, followed by classifying the merged block as text or non-text.

12. The method of claim 11 wherein:

the verification comprises additionally checking whether an additional test is satisfied by the merged block, for presence of the pixels with a common binary value along another straight line passing through the merged block.

13. The method of claim 12 wherein the additionally checking comprises:

using a peak in a profile obtained by projection of intensities of the pixels in the merged block along a predetermined direction.

14. The method of claim 13 wherein the additionally checking comprises:

using a location of the peak relative to a span of the profile.

15. The method of claim 11 wherein the verification comprises:

binarizing each pixel in the merged block by assigning one of two binary values, based on comparison of an intensity of the pixel with a threshold determined by use of the pixels in the merged block; and

using an attribute of the merged block indicative of a ratio of (A) a mean of a number of transitions in a predetermined direction from a first binary value to a second binary value in each row in a set of rows in the merged block and (B) a width of the merged block.

16. The method of claim 15 wherein the verification further comprises:

using another attribute of the merged block;

wherein said another attribute is indicative of another mean of another number of transitions in the predetermined direction, from the second binary value to the first binary value in said row in the set of rows.

17. The method of claim 11 wherein the classifying comprises:

using an attribute of the merged block indicative of a ratio of (A) a number of vertical lines in the merged block and (B) a length of the merged block.

18. A mobile device comprising:

a camera;

a memory operatively connected to the camera to receive at least an image therefrom;

at least one processor operatively connected to the memory to execute a plurality of computer instructions stored in the memory, to supply information related to a merged block, the merged block being obtained by the at least one processor executing the plurality of computer instructions to merge a first block with a second block that is located adjacent to and not overlapping the first block;

wherein the plurality of computer instructions cause the at least one processor to check whether a first projection of the first block on a straight line and a second projection of the second block on the straight line satisfy a test for overlap; and

wherein the first block and the second block comprise a first region and a second region in the image having pixels contiguous with one another and comprising a local extrema of intensity in the image.

19. The mobile device of claim 18 wherein:

the second projection is smaller than the first projection; and

the test is satisfied when the second projection is entirely overlapped by the first projection.

20. The mobile device of claim 19 wherein the plurality of computer instructions when executed cause the at least one processor to:

further check whether a first additional projection and a second additional projection of the first block and the second block respectively on an additional straight line perpendicular to the straight line satisfy an additional test;

wherein execution of the plurality of computer instructions to merge is based on at least an outcome of the additional test.

21. One or more non-transitory computer readable storage media comprising computer instructions, which when executed in a handheld device, cause one or more processors in the handheld device to perform operations, the computer instructions comprising:

first instructions to check whether a first block and a second block located adjacent to one another in an image and not overlapping one another are such that a first projection of the first block on a straight line and a second projection of the second block on the straight line satisfy a test for overlap; and

wherein the first block and the second block comprise a first region and a second region in the image having pixels contiguous with one another and comprising a local extrema of intensity in the image;

second instructions to merge the first block and the second block to obtain a merged block, based at least on an outcome of the test;

wherein pixels in the merged block comprise at least a first plurality of pixels in the first block and a second plurality of pixels in the second block; and

third instructions to store information related to the merged block in a memory;

wherein one or more of the first instructions, the second instructions, and the third instructions are to be executed by at least one processor among the one or more processors.

22. The one or more non-transitory computer readable storage media of claim 21 wherein:

the second projection is smaller than the first projection; and

the test is satisfied when the second projection is entirely overlapped by the first projection.

23. The one or more non-transitory computer readable storage media of claim 22 wherein the computer instructions further comprise:

instructions to further check whether a first additional projection and a second additional projection of the first block and the second block respectively on an additional straight line perpendicular to the straight line satisfy an additional test;

wherein execution of the second instructions is based on at least the outcome of the additional test.

24. An apparatus for identifying regions of text, the apparatus comprising:

a memory storing an image of an environment outside the apparatus;

means, coupled to the memory, for checking whether a first block and a second block that are adjacent to one another and do not overlap are such that a first projection of the first block on a straight line and a second projection of the second block on the straight line satisfy a test for overlap; and

wherein the first block and the second block comprise a first region and a second region in the image having pixels contiguous with one another and comprising a local extrema of intensity in the image;

means for merging the first block and the second block to obtain a merged block, based at least on an outcome of the test;

wherein pixels in the merged block comprise at least a first plurality of pixels in the first block and a second plurality of pixels in the second block; and

means for storing in at least one memory, information related to the merged block.

25. The apparatus of claim 24 wherein:

the second projection is smaller than the first projection; and

the test is satisfied when the second projection is entirely overlapped by the first projection.