Methods and apparatus for analyzing an image

• US 7,672,022 B1
• Filed: 11/09/2000
• Issued: 03/02/2010
• Est. Priority Date: 04/07/2000
• Status: Expired due to Fees

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Fan, Jian
• Primary Examiner(s): Worku; Negussie
• Application Number:
  US09/709,685
• Time in Patent Office: 3,400 Days
• Field of Search: 358/1.9, 358/2.1, 358/2.99, 358/3.01, 358/474, 358/501, 358/505, 358/509, 358/518, 358/448, 358/462, 358/1.1, 358/1.15, 358/1.2, 358/3.27, 382/173, 382/181, 382/199, 382/205, 382/162, 382/165, 382/186, 382/176, 348/207.99
• US Class Current: 358/474
• CPC Class Codes: G06T 2200/24 involving graphical user interfaces [GUIs]
• CPC Class Codes: G06T 2207/10008 from scanner, fax or copier
• CPC Class Codes: G06T 2207/20192 Edge enhancement; Edge preservation
• CPC Class Codes: G06T 2207/30176 Document
• CPC Class Codes: G06T 5/20 using local operators
• CPC Class Codes: G06T 5/73 Deblurring; Sharpening
• CPC Class Codes: G06T 7/12 Edge-based segmentation
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/15 Cutting or merging image elements, e.g. region growing, watershed or clustering-based techniques
• CPC Class Codes: G06V 30/18105 related to colour

Abstract

A method analyzes an image to be scanned and analyzes at least part of the image pixel-by-pixel. Elements in the image are characterized according to a perceived characteristic and each image element having a given characteristic that is adjacent a similar or identical image element is identified. In one form, there are preferably at least three different characteristics, such as black, background and edge, by which the image elements can be characterized. In another form, image elements that are close enough to each other in physical location and close enough to each other in image characteristic are grouped together or included in a blob. Sub-blobs can be found to be part of a more predominant blob. In a further form, image elements are identified that represent an edge in the image, along with identifying those edge elements that are adjacent at least one other edge element.

Claims

1. A method of processing an image of elements, comprising:

assigning each of multiple ones of the elements a respective element label selected from a set of at least three element labels that includes at least one edge element label;

grouping spatially connected ones of the elements into respective blobs based on the element labels assigned to the elements, wherein each of the blobs is assigned a respective one of at least two blob labels; and

processing ones of the elements based at least in part on the blob labels assigned to the blobs and the element labels assigned to the elements;

wherein the assigning, the grouping, and the processing are performed by a processor.

2. The method of claim 1, further comprising segmenting spatially connected ones of the elements in each of the blobs into respective sub-blobs based on the labels assigned to the elements, wherein each of the sub-blobs is assigned to a respective one of at least two sub-blob labels, wherein the processing is based at least in part on the sub-blob labels assigned to the sub-blobs.

3. The method of claim 2, wherein the segmenting comprises segmenting adjacent ones of the elements into a respective one of a black sub-blob label, a gray sub-blob label, a gray edge sub-blob label, a color sub-blob label, a color edge sub-blob label, and a white sub-blob label.

4. The method of claim 2, wherein the grouping comprises assigning at least some adjacent ones of the elements a background blob label, and the segmenting comprises segmenting at least some adjacent ones of the elements assigned the background blob label into a respective one of the sub-blob labels based on the element labels assigned to the elements.

5. The method of claim 2, wherein the grouping comprises labeling at least some adjacent ones of the elements with a non-background blob label, and the segmenting comprises assigning a respective one of the sub-blob labels to at least some adjacent ones of the elements labeled with the non-background label based on the element labels assigned to the elements.

6. The method of claim 5, wherein the segmenting comprises labeling adjacent ones of the elements assigned the non-background blob label with a respective one of an edge element sub-blob label, a color element sub-blob label, a gray element sub-blob label, and a black element sub-blob label.

7. The method of claim 5, further comprising classifying each of multiple ones of the blobs into a respective one of at least two blob type classes based on the blob label assigned to the blob and statistics of the sub-blobs linked to the blob.

8. The method of claim 2, wherein the segmenting comprises labeling at least some adjacent ones of the elements with an edge sub-blob label.

9. The method of claim 8, wherein the segmenting comprises labeling at least some neighboring ones of the elements with the edge sub-blob label.

10. The method of claim 8, wherein the labeling is based on an eight-neighbors system connectivity analysis performed for each of the elements.

11. The method of claim 8, wherein the labeling comprises labeling the at least some adjacent ones of the elements with a respective label selected from a white edge sub-blob label and a gray edge sub-blob label.

12. The method of claim 8, wherein the segmenting comprises identifying elements that are assigned the edge element label and are adjacent at least two other elements each of which is assigned the edge element label.

13. The method of claim 8, wherein the segmenting comprises labeling ones of the elements having similar element labels with respective ones of the sub-blob labels image characteristic.

14. The method of claim 13, wherein the labeling comprises identifying ones of the elements assigned an identical element label selected from a color element label, a gray element label, and a black element label.

15. The method of the claim 14, wherein the labeling comprises identifying spatially connected ones of the elements that are assigned a mutual one of the selected element labels.

16. The method of claim 15, wherein the identifying of spatially connected ones of the elements comprises identifying ones of the elements that are assigned the mutual element label and are connected through other ones of the elements assigned the mutual element label.

17. The method of claim 16, wherein the grouping comprises labeling connected ones of the identified elements assigned the mutual element label with a non-background sub-blob label.

18. The method of claim 13, wherein the segmenting comprises identifying connected ones of the elements having at least one element label in common.

19. The method of claim 18, wherein the segmenting comprises assigning a respective one of the sub-blob labels to each set of the connected elements having the at least one element label in common.

20. The method of claim 18, further comprising determining for each of multiple ones of the blobs a respective number of constituent ones of the connected elements having a first one of the element labels in common.

21. The method of claim 20, further comprising for each of multiple ones of the blobs determining a respective second number of constituent ones of the connected elements that have a second one of the element labels in common, and comparing the respective first and second numbers of elements.

22. The method of claim 21, further comprising identifying elements that have the first element label in common and are adjacent to elements having the second element label in common.

23. The method of claim 21, wherein the processing comprises changing attribute values of the elements having the second element label in common to values that are closer to corresponding attribute values of the elements having the first element label in common.

24. The method of claim 23, wherein the changing comprises changing the attribute values of the elements having the second element label in common by multiplying their attribute values by a number less than one.

25. The method of claim 23, wherein the changing comprises changing the attribute values of the elements having the second element label in common to an average of the corresponding attribute values of the elements having the first element label in common.

26. The method of claim 21, wherein the first element label is a black element label and the second element label is different from the black element label.

27. The method of claim 26, further comprising for each of the blobs comparing number of connected elements labeled with the second element label to number of connected elements labeled with the black element label.

28. The method of claim 2, wherein:

the grouping comprises labeling ones of the elements with a background blob label;

the assigning comprises assigning ones of the elements the edge element label; and

the segmenting comprises segmenting connected ones of the elements assigned the edge element label to an edge sub-blob label.

29. The method of claim 28, wherein the assigning comprises labeling ones of the elements with a black element label.

30. The method of claim 28, wherein the assigning comprises labeling each of multiple ones of the elements with a respective one of a gray element label and a gray edge element label.

31. The method of claim 28, wherein the labeling of ones of the elements with the edge element label comprises assigning each of multiple ones of the elements to a respective one of a white edge element label, a gray edge element label, and a color edge element label.

32. The method of claim 28, wherein the segmenting comprises assigning a respective sub-blob label and a respective blob pointer to each of multiple ones of the elements such that identical blob pointers are assigned to connected ones of the elements assigned an identical sub-blob label.

33. The method of claim 28, wherein the assigning comprises applying a gradient operator to ones of the elements to produce gradient data and labeling ones of the elements with the edge element label based on the gradient data.

34. The method of claim 2, wherein ones of the elements are associated with respective grayscale image data.

35. The method of claim 34, wherein the assigning comprises assigning ones of the elements a black element label based on the grayscale image data.

36. The method of claim 34, wherein the assigning comprises assigning ones of the elements a respective one of a gray element label and a gray edge element label.

37. The method of claim 34, wherein the assigning of ones of the elements the edge element label comprises labeling each of multiple ones of the elements with a respective one of a white edge element label, a gray edge element label, and a color edge element label.

38. The method of claim 34 wherein the assigning comprises applying a gradient operator to ones of the elements to produce gradient data and labeling ones of the elements with the edge element label based on the gradient data.

39. The method of claim 34, further comprising assigning a respective sub-blob label and a respective blob pointer to each of multiple ones of the elements such that identical pointers are assigned to connected ones of the elements assigned an identical sub-blob label.

40. The method of claim 34, wherein the segmenting comprises identifying adjacent ones of the elements assigned the edge element label, and labeling the identified adjacent elements with a respective ones of the sub-blob labels.

41. The method of claim 34, further comprising for each of multiple ones of the blobs:

determining a respective number of connected ones of the constituent elements assigned a first one of the element labels;

determining a respective second number of connected ones of the constituent elements assigned a second one of the element labels; and

classifying ones of the blobs based on comparisons of the respective first and second numbers of elements.

42. The method of claim 1, wherein the elements correspond to pixels of the image.

43. The method of claim 1, wherein the assigning comprises determining a white threshold value from luminance values associated with ones of the elements.

44. The method of claim 43, wherein the assigning comprises determining a black threshold value from the determined white threshold value.

45. The method of claim 1, wherein the assigning comprises labeling ones of the elements with respective ones of the element labels based at least in part on luminance values respectively associated with the elements.

46. The method of claim 45, wherein the labeling comprises comparing the luminance values to a white threshold value.

47. The method of claim 45, wherein the labeling comprises assigning each of multiple ones of the elements a respective one of a black element label, a white element label, and a gray element label based on comparisons of the luminance values to a white threshold and a black threshold.

48. The method of claim 45, wherein the labeling comprises comparing the luminance values to a black threshold value.

49. The method of claim 1, wherein the labeling comprises assigning each of multiple ones of the elements a respective one of a black element label, a white element label, and a color element label.

50. The method of claim 1, wherein the grouping comprises grouping spatially connected ones of the elements that are assigned element labels within a first subset of the element labels into a respective one of the blobs assigned a first blob label, and grouping spatially connected ones of the elements that are assigned element labels within a second subset of the element labels into a respective one of the blobs assigned a second blob label.

51. The method of claim 1, wherein the grouping is based on a respective eight-neighbors system connectivity analysis performed for each of the elements.

52. The method of claim 1, wherein the grouping comprises labeling at least some of adjacent ones of the elements with a background blob label.

53. The method of claim 52, wherein the grouping comprises labeling adjacent ones of the elements that are outside the background blob label with a non-background blob label.

54. The method of claim 1, wherein the assigning comprises applying a gradient operator to ones of the elements to produce gradient data and labeling ones of the elements with the edge element label based on the gradient data.

55. The method of claim 1, wherein the assigning comprises determining a color threshold based at least in part on color values respectively associated with ones of the elements.