Segmenting Digital Image And Producing Compact Representation

• US 20080123945A1
• Filed: 12/20/2005
• Published: 05/29/2008
• Est. Priority Date: 12/21/2004
• Status: Active Grant

• Current Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Original Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Inventors: Besley, James Austin, Chong, Eric Wai-Shing, Chen, Yu-Ling, Irrgang, Steven Richard, Lawther, Michael Jan, Wark, Timothy John, Andrew, James Philip
• Granted Patent: US 7,991,224 B2
• Time in Patent Office: Days
• US Class Current: 382/164
• CPC Class Codes: G06T 2207/10024 Color image
• CPC Class Codes: G06T 2207/30176 Document
• CPC Class Codes: G06T 7/11 Region-based segmentation
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/162 Quantising the image signal
• CPC Class Codes: G06V 30/413 Classification of content, e.g. text, photographs or tables

Abstract

A method (100), an apparatus, and a computer program product for automatically producing a compact representation of a colour document are disclosed. In the method, a digital image of a colour-document page is segmented (110) into connected components in one-pass, block raster order. The digital image of the page is partitioned into foreground and background images using layout analysis (120) based on compact, connected-component statistics of the whole page. At least one portion of the background image where at least one portion of the foreground image obscures the background image is inpainting (520) in one-pass block raster order. The foreground and background images are combined (130) to form a compact document. A method, an apparatus, and a computer program product for segmenting a digital image comprising a plurality of pixels are also disclosed.

Claims

1. A method of segmenting a digital image comprising a plurality of pixels, said method comprising the steps of:

generating a plurality of blocks of pixels from said digital image; and

producing at least one connected component for each block using said blocks of pixels in a one-pass manner, said producing step comprising;

segmenting a block of pixels into at least one connected component, each connected component comprising a group of pixels that are spatially connected and semantically related;

merging said at least one connected component of said block with at least one connected component segmented from at least one other block that has been previously processed; and

storing in a compact form a location in said image of said connected components of said block.

2. The method according to claim 1, wherein said semantically related pixels comprise pixels that are similarly coloured.

3. The method according to claim 1, wherein said generating step comprises the sub-steps of:

arranging said digital image into a plurality of bands, each band comprising a predetermined number of consecutive lines of pixels; and

buffering and processing said bands one-by-one, wherein said processing step comprises the sub-steps performed on each currently buffered band;

arranging said current band into a plurality of blocks of pixels; and

buffering and processing said blocks of said current band one-by-one for said producing step.

4. The method according to claim 1, wherein said storing sub-step comprises storing M−

1 binary bitmaps, where M-connected components are in a block, M being an integer.

5. The method according to claim 1, wherein said storing sub-step comprises storing an index map.

6. The method according to claim 1, wherein said segmenting sub-step comprises:

estimating a number of representative colours for each block;

quantizing each block to said representative colours; and

forming connected components from each quantized block.

7. The method according to claim 6, wherein said segmenting sub-step further comprises merging a subset of said connected components that are formed.

8. The method according to claim 7, wherein said merging sub-step comprises gathering statistics of said connected components.

9. The method according to claim 8, further comprising the step of removing said formed connected components that are deemed to be noise.

10. The method according to claim 9, wherein said noise comprises connected components having a pixel count that is below a predefined threshold and a border-length-to-pixel-count ratio above another predefined threshold.

11. The method according to claim 8, wherein said statistics comprise any one or more of bounding boxes, pixel count, border length, and average colour.

12. The method according to claim 8, wherein said merging step comprises:

merging connected components of a block with connected components of a block on the left and above; and

updating said statistics of said merged connected components.

13. The method according to claim 12, wherein said statistics comprise any one of more of bounding boxes, pixel count, fill ratio, and average colour.

14. The method according to claim 6, wherein said estimating sub-step comprises:

forming a histogram related to a plurality of colour bins based on YUV data of pixels in each block;

classifying each block based on histogram statistics; and

merging bin colours to form said representative colours based on said block classification.

15. The method according to claim 14, further comprising the step of forming an indexed map for each pixel in one pass.

16. The method according to claim 15, wherein said quantizing step comprises:

quantizing non-empty bins to representative colours;

creating a bin mapping to said representative colours; and

remapping said indexed map to said representative colours using said bin mapping.

17. The method according to claim 14, wherein said forming sub-step comprises:

deciding a luminance band based on Y value;

deciding a colour column based on U and V value;

accumulating the pixel colour to the mapped bin; and

incrementing the pixel count of the mapped bin.

18. The method according to claim 17, wherein said step of deciding a luminance band further comprises luminance-band anti-aliasing.

19. The method according to claim 17, wherein said deciding a colour column further comprises colour column anti-aliasing.

20. The method according to claim 12, wherein said merging step comprises the following sub-steps performed for each connected component in a current block touching the left and above border:

finding a list of connected components that touch the current connected component along the common border; and

deciding the best candidate to merge.

21. An apparatus comprising a processor and memory for segmenting a digital image comprising a plurality of pixels in accordance with the method of claim 1.

22. A computer program product comprising a computer readable medium having recorded therein a computer program for segmenting a digital image comprising a plurality of pixels in accordance with the method of claim 1.

23. A method of automatically producing a compact representation of a colour document, said method comprising the steps of:

segmenting a digital image of a colour-document page into connected components in one-pass, block raster order;

partitioning said digital image of said page into foreground and background images using layout analysis based on compact, connected-component statistics of said whole page;

inpainting in one-pass block raster order at least one portion of said background image where at least one portion of said foreground image obscures said background image; and

storing said foreground and background images to form a compact document.

24. The method according to claim 23, further comprising the step of downsampling said background image.

25. The method according to claim 23, further comprising the step of compressing said background image.

26. The method according to claim 25, wherein said compressing step involves lossy compression.

27. The method according to claim 26, further comprising a different compressing of said lossy compressed background image.

28. An apparatus comprising a processor and memory for automatically producing a compact representation of a colour document in accordance with the method of claim 23.

29. A computer program product comprising a computer readable medium having recorded therein a computer program for automatically producing a compact representation of a colour document in accordance with the method of claim 23.

30. A method of analysing a digital image comprising a plurality of pixels, said method comprising the steps of:

segmenting said digital image into objects, where said segmentation is represented by more than two labels;

providing a set of properties for each object;

for a subset of said objects, using a measure of containment to determine if a parent-child relationship exists between adjacent objects sharing a boundary;

forming groups of objects that share a common parent based on object properties; and

classifying objects according to their properties and grouping.

31. The method according to claim 30, wherein said containment is determined using bounding boxes around each object and information describing touching relationships between objects.

32. The method according to claim 31, wherein an object contains another object if the two objects touch at a boundary and the bounding box of said object completely contains the bounding box of said other object.

33. The method according to claim 30, wherein said forming groups step comprises:

considering pairs of child objects from a list of children of a common parent; and

determining using the object properties whether each pair should be grouped together.

34. The method according to claim 33, wherein only neighbouring objects from a list of child objects with the same parent are considered for grouping.

35. The method according to claim 33, wherein objects are grouped based on bounding box and colour information.

36. The method according to claim 30, wherein a group of objects is classified as text according to a test of text-like qualities of said objects within said group.

37. The method according to claim 36, wherein said test for text-like qualities comprises:

identifying a single value for each object representing that a location of said object;

forming a histogram of said values; and

identifying text by a property of said histogram.

38. The method according to claim 30, further comprising the step of adding further objects to a text-classified group of objects according to their properties, but regardless of their parent-child properties.

39. A method of analysing a digital image comprising a plurality of pixels of a document page, said method comprising the steps of:

segmenting said digital image to form objects based on said image;

forming groups of said objects; and

determining if said groups of objects each represent text, said determining step comprising;

identifying a single value for each object dependent on a location of said object on said page;

forming a histogram of said values; and

identifying text by a property of said histogram.

40. The method according to claim 39, wherein said property of said histogram is the total number of objects in bins in said histogram that have more than a specified number of objects.

41. The method according to claim 39, wherein said property is the sum of the squares of counts in said histogram.

42. The method according to claim 39, wherein said single value for each object representing the location of said object is an edge of a bounding box of said object.

43. An apparatus comprising a processor and a memory for analysing a digital image comprising a plurality of pixels in accordance with the method of claim 39.

44. A computer program product comprising a computer readable medium having recorded therein a computer program for analysing a digital image comprising a plural of pixels in accordance with the method of claim 39.

45. A method of segmenting a digital image comprising a plurality of pixels, said method comprising the steps of:

generating a plurality of blocks of pixels from said digital image; and

producing at least one connected component for each block using said blocks of pixels, said producing step comprising;

segmenting a block of pixels into at least one connected component, each connected component comprising a group of pixels that are spatially connected and semantically related;

merging said at least one connected component of said block with at least one connected component segmented from at least one other block; and

storing a location In said Image of said connected components of said block.