Detection of highlighted regions

• US 5,048,109 A
• Filed: 12/08/1989
• Issued: 09/10/1991
• Est. Priority Date: 12/08/1989
• Status: Expired due to Fees

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Sang, Henry W. Jr., Bloomberg, Dan S., Dasari, Lakshmi
• Primary Examiner(s): Boudreau, Leo H.
• Assistant Examiner(s): NOT, DEFINED
• Application Number:
  US07/447,985
• Time in Patent Office: 641 Days
• Field of Search: 382/50, 382/41, 382/48, 382/9
• US Class Current: 382/164
• CPC Class Codes: G06V 10/10 Image acquisition document image scanning and transmission H04N1/00; control of digital cameras H04N23/60
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/1444 Selective acquisition, locating or processing of specific regions, e.g. highlighted text, fiducial marks or predetermined fields
• CPC Class Codes: H04N 1/38 Circuits or arrangements for blanking or otherwise eliminating unwanted parts of pictures H04N1/387 takes precedence

Abstract

A method and apparatus for detection of highlighted regions of a document. A document containing highlighted regions is scanned using a gray scale scanner. Morphology and threshold reduction techniques are used to separate highlighted and non-highlighted portions of the docment. Having separated the highlighted and non-highlighted portions, optical character recognition (OCR) techniques can then be used to extract text from the highlighted regions.

Claims

1. A method for processing a first image in a digital computer to identify a location of highlight regions in said first image, said first image comprising mark regions having a first grayscale, a highlighted portion of said marks at least partially surrounded by said highlight regions, said highlight regions having a second grayscale, comprising the steps of:

a) inputting a grayscale image of said first image;

b) identifying a location of said portion of said marks in said first image using said grayscale image, said step of identifying a location further comprising the step of converting said highlight regions to substantially solid regions, said substantially solid regions corresponding to said highlight regions; and

c) using said substantially solid regions in combination with an image comprising at least marks of said first image to extract a second image, said second image comprising said highlighted portion of said marks.

2. The method as recited in claim 1 wherein said second image comprises an entirety of marks partially within said substantially solid regions.

3. The method as recited in claim 1 further comprising the step of identifying characters in said substantially solid regions.

4. The method as recited in claim 1 preceded by the step of forming said highlighted regions with a color highlight pen.

5. The method as recited in claim 1 wherein said second image comprises marks fully surrounded by said highlight regions.

6. The method as recited in claim 2 wherein the second image consists essentially of characters partially and fully surrounded by said highlight regions.

7. The method as recited in claim 1 wherein the step of identifying further comprises the step of band-pass filtering said grayscale image to produce a highlight image, said highlight image filled to produce said substantially solid regions.

8. The method as recited in claim 7 wherein the step of filling further comprises the step of producing a highlight region mask from said highlight image, said mask comprising substantially solid ON pixels in said highlight regions.

31. A method as recited in claim 3 wherein said step of identifying a location uses a first resolution image and said step of identifying characters uses a second resolution image, said second resolution substantially higher than said first resolution.

32. A method as recited in claim 31 wherein said first resolution is about 75 pixels/inch and said second resolution is about 300 pixels/inch.

9. A method for processing a first image in a digital computer to identify a location of highlight regions in said first image, said first image comprising mark regions having a first grayscale, a highlighted portion of said marks at least partially surrounded by said highlight regions, said highlight regions having a second grayscale, comprising the steps of:

a) inputting a grayscale image of said first image;

b) identifying a location of said portion of said marks in said first image using said grayscale image, said step of identifying a location further comprising the step of converting said highlight regions to substantially solid regions, said substantially solid regions corresponding to said location of said portions of said marks;

c) producing a highlight image;

d) band-pass filtering said grayscale image to produce a highlight image, said highlight image filled to produce said substantially solid regions; and

e) producing a highlight region mask from said highlight image further comprising the steps of;

i) opening said highlight image with a structuring element of substantially solid ON entries to produce a first intermediate image; and

ii) closing said first intermediate image to substantially fill mark regions and produce said highlight region mask.

10. The method as recited in claim 9 further comprising the step of eroding said highlight region mask.

11. The method as recited in claim 10 wherein the step of eroding shrinks a boundary of said second intermediate image by about one pixel.

12. The method as recited in claim 9 wherein the step of opening is preceded by the step of reducing said highlight image.

19. The method as recited in claims 12 or 13 further comprising the step of expanding said highlight region mask.

13. A method for processing a first image in a digital computer to identify a location of highlight regions in said first image, said first image comprising mark regions having a first grayscale, a highlighted portion of said marks at least partially surrounded by said highlight regions, said highlight regions having a second grayscale, comprising the steps of:

a) inputting a grayscale image of said first image;

b) identifying a location of said portion of said marks in said first image using said grayscale image, said step of identifying a location further comprising the step of converting said highlight regions to substantially solid regions, said substantially solid regions corresponding to said location of said portions of said marks;

c) producing a highlight image;

d) band-pass filtering said grayscale image to produce a highlight image, said highlight image filled to produce said substantially solid regions; and

e) producing a highlight region mask from said highlight image further comprising the step of reducing said highlight image at least once to produce said mask.

14. The method as recited in claim 13 wherein the step of reducing is followed by the step of closing said mask.

15. The method as recited in claim 13 wherein the step of reducing comprises first and second reduction steps.

16. The method as recited in claim 15 wherein said second reduction step has a lower threshold level than said first reduction step.

17. The method as recited in claim 13 further comprising the step of opening said highlight region mask.

18. The method as recited in claim 17 further comprising the step of eroding said highlight region mask.

20. The method as recited in claims 9 or 17 wherein the step of opening further comprises the steps of eroding and then dilating with one-dimensional structuring elements.

21. The method as recited in claims 9 or 17 wherein the step of opening further comprises the steps of:

a) eroding with one-dimensional vertical structuring elements; and

b) dilating with one-dimensional horizontal structuring elements.

22. The method as recited in claims 9 or 14 wherein the step of closing further comprises the steps of dilating and then eroding with one-dimensional structuring elements.

23. The method as recited in claim 21 wherein the steps of eroding and dilating further comprise the steps of:

a) eroding with one-dimensional horizontal structuring element;

b) eroding with one-dimensional vertical structuring element;

c) dilating with a one-dimensional horizontal structuring element; and

d) dilating with a one-dimensional vertical structuring element.

24. The method as recited in claim 22 wherein the steps of dilating and eroding further comprise the steps of:

a) dilating with a one-dimensional horizontal structuring element;

b) dilating with a one-dimensional vertical structuring element;

c) eroding with one-dimensional horizontal structuring element; and

d) eroding with one-dimensional vertical structuring element.

25. A method for processing a first image in a digital computer to identify a location of highlight regions in said first image, said first image comprising mark regions having a first grayscale, a highlighted portion of said marks at least partially surrounded by said highlight regions, said highlight having a second grayscale, comprising the steps of:

a) inputting a grayscale image of said first image;

b) identifying a location of said portion of said marks in said first image using said grayscale image, said step of identifying a location further comprising the step of converting said highlight regions to substantially solid regions, said substantially solid regions corresponding to said location of said portions of said marks;

c) producing a highlight image;

d) band-pass filtering said grayscale image to produce a highlight image, said highlight image filled to produce said substantially solid regions; and

e) forming a second highlight mark image by the steps of;

i) inverting said highlight image to produce an inverted highlighted image; and

ii) ANDing said inverted highlighted image with said substantially solid regions to produce said highlight mark image.

26. The method as recited in claim 25 further comprising the step of opening said highlight mark image.

27. The method as recited in claim 25 further comprising the step of using said highlight mark image as a seed to produce a whole mark image.

28. The method as recited in claim 27 wherein the step of producing a whole mark image further comprises the steps of:

a) closing a highlight mark image to produce a mark mask; and

b) fillclipping said mark mask to said highlight mark image.

29. The method as recited in claim 27 wherein the whole mark image is used to produce a wholly highlighted mark image by:

a) XORing a slightly filled highlighted mark image and a sum of said whole marks and partial mark images to produce a first seed;

b) fillclipping said first seed using a mark image as a mask to produce a partial mark image; and

c) XORing said partial mark image with said sum image to produce said wholly highlighted mark image.

30. The method as recited in claim 28 or 29 wherein said fillclip step further comprises the steps of:

a) copying a seed image;

b) dilating said seed image to produce a dilated seed image;

c) ANDing said dilated seed image with said mask image to produce a partially filled seed;

d) XORing said partially filled seed with said copied seed image;

e) testing to determine if a change has been made;

f) if a change has been made, copying said partially filled seed image and repeating from step b; and

g) if a change has not been made, outputting said partially filled seed as a filled seed.

33. A method for processing a first image in a digital computer to identify a location of highlight regions in said first image, said first image comprising mark regions having a first grayscale, a highlighted portion of said marks at least partially surrounded by said highlight regions, said highlight regions having a second grayscale, comprising the steps of:

a) inputting a grayscale image of said first image;

b) identifying a location of said portion of said marks in said first image using said grayscale image, said step of identifying a location further comprising the step of converting said highlight regions to substantially solid regions, said substantially solid regions corresponding to said location of said portions of said marks;

c) producing a highlight image;

d) band-pass filtering said grayscale image to produce a highlight image, said highlight image filled to produce said substantially solid regions; and

e) filling said highlight image to produce substantially solid regions, wherein said highlight regions comprise loops and wherein said step of converting to substantially solid regions further comprises the step of closing said highlight image with a plurality of structuring elements, said plurality of structuring elements comprising lines of ON pixels oriented in at least two directions to produce said substantially solid regions.

34. The method as recited in claim 33 further comprising an additional step of closing with said plurality of structuring elements when at least a portion of said loops are broken.

35. A digital computer programmed to process a first image to identify a location of highlight regions in said first image, said first image comprising mark regions having a first grayscale, a highlighted portion of said marks at least partially surrounded by said highlight regions, said highlight regions having a second grayscale, comprising:

a) means to input a grayscale image of said first image;

b) means programmed to identify a location of said portion of said marks in said first image using said grayscale image, said means for identifying a location programmed to convert said highlight regions to substantially solid regions, said substantially solid regions corresponding to said highlight regions; and

c) means to use said substantially solid regions in combination with an image comprising marks of said first image to extract a second image, said second image comprising said highlighted portion of said marks.

36. The computer as recited in claim 35 wherein said second image comprises an entirety of marks partially within said substantially solid regions.

37. The computer as recited in claim 35 further programmed to identify characters in said substantially solid regions.

38. The computer as recited in claim 37 wherein said substantially solid regions comprise greater than about 90% ON pixels.

39. The computer as recited in claim 35 further programmed to form a second image, said second image comprising marks fully surrounded by said highlight regions.

40. The computer as recited in claim 35 wherein said second image comprises characters partially and fully surrounded by said highlight regions.

41. The computer as recited in claim 35 further programmed to band-pass filter said grayscale image to produce a highlight image, said highlight image filled to produce said substantially solid regions.

42. The computer as recited in claim 41 further to produce a highlight region mask from said highlight image, said mask comprising substantially solid ON pixels in said highlight regions.

65. A computer as recited in claim 37 programmed to identify a location using a first resolution image and identify characters using a second resolution image, said second resolution substantially higher than said first resolution.

66. The computer as recited in claim 35 wherein said first resolution is about 75 pixels/inch and said second resolution is about 300 pixels/inch.

43. A digital computer programmed to process a first image to identify a location of highlight regions in said first image, said first image comprising mark regions having a first grayscale, a highlighted portion of said marks at least partially surrounded by said highlight regions, said highlight regions having a second grayscale, comprising:

a) means to input a grayscale image of said first image;

b) means programmed to identify a location of said portion of said marks in said first image using said grayscale image, said means for identifying a location programmed to convert said highlight regions to substantially solid regions, said substantially solid regions corresponding to said location of said portions of said marks;

c) means programmed to band-pass filter said grayscale image to produce a highlight image, said highlight image filled to produce said substantially solid regions;

d) means programmed to produce a highlight region mask from said highlight image, said mask comprising substantially solid ON pixels in said highlight regions; and

e) means programmed to produce said highlight region mask from said highlight image by the steps of;

i) opening said highlight image with a structuring element of substantially solid ON entries to produce a first intermediate image; and

ii) closing said first intermediate image to substantially fill mark regions and produce said highlight region mask.

44. The computer as recited in claim 43 further programmed to erode said highlight region mask.

45. The computer as recited in claim 44 wherein eroding shrinks a boundary of said second intermediate image by about one pixel.

46. The computer as recited in claim 43 wherein opening is preceded by the step of reducing said highlight image.

53. The computer as recited in claims 46 or 47 further programmed to expand said highlight region mask.

54. The computer as recited in claim 43 or 51 wherein the computer is programmed to open by the steps of eroding and then dilating with one-dimensional structuring elements.

55. The computer as recited in claims 43 or 51 programmed to open by the steps of:

a) eroding with one-dimensional vertical structuring elements; and

b) dilating with one-dimensional horizontal structuring elements.

56. The computer as recited in claims 45 or 48 wherein the computer is programmed to close with the steps of dilating and then eroding with one-dimensional structuring elements.

57. The computer as recited in claim 54 programmed to erode and dilate by the steps of:

a) eroding with one-dimensional horizontal structuring element;

b) eroding with one-dimensional vertical structuring element;

c) dilating with a one-dimensional horizontal structuring element; and

d) dilating with a one-dimensional vertical structuring element.

58. The computer as recited in claim 56 programmed to dilate and erode by the steps of:

a) dilating with a one-dimensional horizontal structuring element;

b) dilating with a one-dimensional vertical structuring element;

c) eroding with one-dimensional horizontal structuring element; and

d) eroding with one-dimensional vertical structuring element.

60. The computer as recited in claim 58 further programmed to open said highlight mark image.

61. The computer as recited in claim 53 further programmed to use said highlight mark image as a seed to produce a whole mark image.

62. The computer as recited in claim 61 programmed to produce said whole mark image by the steps of:

a) closing a highlight mark image to produce a mark mask; and

b) fillclipping said mark mask to said highlight mark image.

63. The computer as recited in claim 61 programmed to produce a wholly highlighted mark image from the whole mark image and a partial mark sum image by:

a) XORing a slightly filled highlighted mark image and a sum of said whole marks and partial mark images to produce a first seed;

b) fillclipping said first seed using a mark image as a mask to produce a partial mark sum image; and

c) XORing said partial mark image with said sum image to produce said wholly highlighted mark image.

64. The computer as recited in claims 62 or 63 programmed to fillclip by the steps of:

a) copying a seed image;

b) dilating said seed image to produce a dilated seed image;

c) ANDing said dilated seed image with said mask image to produce a partially filled seed;

d) XORing said partially filled seed with said copied seed image;

e) testing to determine if a change has been made;

f) if a change has been made, copying said partially filled seed image and repeating from step b; and

g) if a change has not been made, outputting said partially filled seed as a filled seed.

47. A digital computer programmed to process a first image to identify a location of highlight regions in said first image, said first image comprising mark regions having a first grayscale, a highlighted portion of said marks at least partially surrounded by said highlight regions, said highlight regions having a second grayscale, comprising:

a) means to input a grayscale image of said first image;

b) means programmed to identify a location of said portion of said marks in said first image using said grayscale image, said means for identifying a location programmed to convert said highlight regions to substantially solid regions, said substantially solid regions corresponding to said location of said portions of said marks;

c) means programmed to band-pass filter said grayscale image to produce a highlight image, said highlight image filled to produce said substantially solid regions;

d) means programmed to produce a highlight region mask from said highlight image, said mask comprising substantially solid ON pixels in said highlight regions; and

e) means programmed to produce said highlight region mask from said highlight image by the step of reducing said highlight image at least once to produce said mask.

48. The computer as recited in claim 47 further programmed to close said mask.

49. The computer as recited in claim 47 wherein the reduction comprises first and second reduction steps.

50. The computer as recited in claim 49 programmed such that said second reduction step has a lower threshold level than said first reduction step.

51. The computer as recited in claim 47 further programmed to open said highlight region mask.

52. The computer as recited in claim 51 further programmed to erode said highlight region mask.

59. A digital computer programmed to process a first image to identify a location of highlight regions in said first image, said first image comprising mark regions having a first grayscale, a highlighted portion of said marks at least partially surrounded by said highlight regions, said highlight regions having a second grayscale, comprising:

a) means to input a grayscale image of said first image;

b) means programmed to identify a location of said portion of said marks in said first image using said grayscale image, said means for identifying a location programmed to convert said highlight regions to substantially solid regions, said substantially solid regions corresponding to said location of said portions of said marks;

c) means programmed to band-pass filter said grayscale image to produce a highlight image, said highlight image filled to produce said substantially solid regions;

d) means programmed to produce a highlight region mask from said highlight image, said mask comprising substantially solid ON pixels in said highlight regions; and

e) means programmed to form a second image by the steps of;

i) inverting said highlight image to produce an inverted highlighted image; and

ii) ANDing said inverted highlighted image with said highlight region mask to produce a highlight mark image.

67. A digital computer programmed to process a first image to identify a location of highlight regions in said first image, said first image comprising mark regions having a first grayscale, a highlighted portion of said marks at least partially surrounded by said highlight regions, said highlight regions having a second grayscale, comprising:

a) means to input a grayscale image of said first image;

b) means programmed to identify a location of said portion of said marks in said first image using said grayscale image, said means for identifying a location programmed to convert said highlight regions to substantially solid regions, said substantially solid regions corresponding to said location of said portions of said marks; and

c) means programmed to band-pass filter said grayscale image to produce a highlight image, said highlight image filled to produce said substantially solid regions, wherein said highlight regions comprise broken loops and wherein said step of converting to substantially solid regions further comprises the step of closing said highlight image sequentially with a plurality of structuring elements, said plurality of structuring elements comprising lines of ON pixels oriented in at least two directions to produce said substantially solid regions.

68. The computer as recited in claim 67 further programmed to close a second time with said plurality of structuring elements.