Image boundary detection for a scanned image

• US 5,995,661 A
• Filed: 10/08/1997
• Issued: 11/30/1999
• Est. Priority Date: 10/08/1997
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Company (HP Inc.)
• Inventors: Amidei, James Stephen
• Primary Examiner(s): Au, Amelia
• Assistant Examiner(s): FREDERICK, GILBERTO
• Application Number:
  US08/946,676
• Time in Patent Office: 783 Days
• Field of Search: 382/192, 382/193, 382/194, 382/199, 382/203, 382/292, 382/177, 382/173, 382/295, 382/174, 358/462
• US Class Current: 382/199
• CPC Class Codes: G06T 2207/10008 from scanner, fax or copier
• CPC Class Codes: G06T 2207/30176 Document
• CPC Class Codes: G06T 7/12 Edge-based segmentation

Abstract

A bounding box is generated for a scanned image. A vertical edge of the scanned image is detected. A horizontal edge of the scanned image is also detected. The vertical edge is used as a rightmost edge of the bounding box. The horizontal edge is used as a bottom edge of the bounding box. The vertical edge is detected by, for each scan row, detecting when a first pixel in a substep of pixels of the scan row has a grey value which differs from a grey value of a pixel immediately to the right of the first pixel by at least a first predetermined constant. When such a first pixel is found, any edge from a previous row which is continued by the first pixel is detected. A longest edge in any row continued by the first pixel a length of the longest edge is stored. Also stored is an indication of a rightmost pixel of any edge continued by the first pixel. When the length of the longest edge continued by the first pixel exceeds a second predetermined constant, an x-coordinate of the rightmost pixel of any edge continued by the first pixel is stored as a current rightmost edge.

Claims

1. A method for generating a bounding box for a scanned image comprising the following steps:

(a) detecting a vertical edge of the scanned image, including the following substep;

(a.1) for each scan row, performing the following substeps for a subset of pixels in the scan row;

(a.1.1) detecting when a first pixel in the substep of pixels has a grey value which differs from a grey value of a pixel immediately to the right of the first pixel by at least a first predetermined constant, and

(a.1.2) when in substep (a.1.1), the first pixel in the substep of pixels has a grey value which differs from the grey value of the pixel immediately to the right of the first pixel by at least the first predetermined constant, performing the followings substeps;

(a.1.2.1) detecting any edge from a previous row which is continued by the first pixel,

(a.1.2.2) storing, for a longest edge in any row continued by the first pixel, a length of the longest edge,

(a.1.2.3) storing an indication of a rightmost pixel of any edge continued by the first pixel, and

(a.1.2.4) when the length of the longest edge continued by the first pixel exceeds a second predetermined constant, storing an x-coordinate of the rightmost pixel of any edge continued by the first pixel as a current rightmost edge;

(b) detecting a horizontal edge of the scanned image;

(c) using the vertical edge as a rightmost edge of the bounding box; and

,

(d) using the horizontal edge as a bottom edge of the bounding box.

2. A method as in claim 1 wherein in substep (a.1) for each scan row, the subset of pixels includes pixels located right of the current rightmost edge.

3. A method as in claim 1 wherein in substep (a.1.2.1) a first edge is included within any edge from a previous row which is continued by the first pixel when the first edge either includes a pixel directly above the first pixel or includes a pixel one pixel above and one pixel to the right of the first pixel.

4. A method as in claim 1 wherein step (b) includes the following substep:

(b.1) for each scan row, performing the following substeps for a horizontal subset of pixels in the scan row;

(b.1.1) detecting when a second pixel in the substep of pixels has a grey value which differs from a grey value of a pixel immediately above the second pixel by at least the first predetermined constant, and

(b.1.2) when in substep (a.1), the second pixel in the substep of pixels has the grey value which differs from the grey value of the pixel immediately above the second pixel by at least the first predetermined constant, performing the followings substeps;

(b.1.2.1) detecting a longest horizontal edge which includes the second pixel, and

(b.1.2.2) when a total length of the longest horizontal edge exceeds the second predetermined constant, storing a y-coordinate of the second pixel as a current bottom edge.

5. A method as in claim 4 wherein substep (b.1.2.1) includes the following substeps:

(b.1.2.1.1) detecting any edge from a right of the second pixel which is continued by the second pixel;

(b.1.2.1.2) detecting any edge from a left of the second pixel which is continued by the second pixel; and

(b.1.2.1.3) combining any edge from the right of the second pixel detected in substep (b.1.2.1.1) with any edge from the left of the second pixel detected in substep (b.1.2.1.2) to produce the longest horizontal edge.

6. A method as in claim 5 wherein substep (b.1.2.1.1) a first edge is included within any edge from the right of the second pixel which is continued by the second pixel when the first edge either includes a pixel directly to the right of the second pixel or includes a pixel one pixel above and one pixel to the right of the second pixel.

7. A method as in claim 5 wherein substep (b.1.2.1.2) a first edge is included within any edge from the left of the second pixel which is continued by the second pixel when the first edge either includes a pixel directly to the left of the second pixel or includes a pixel one pixel above and one pixel to the left of the second pixel.

8. A method for generating a bounding box for a scanned image comprising the following steps:

(a) detecting a vertical edge of the scanned image;

(b) detecting a horizontal edge of the scanned image, including the following substep;

(b.1) for each scan row, performing the following substeps for a horizontal subset of pixels in the scan row;

(b.1.1) detecting when a first pixel in the substep of pixels has a grey value which differs from a grey value of a pixel immediately above the first pixel by at least a first predetermined constant, and

(b.1.2) when in substep (b.1.1), the first pixel in the substep of pixels has the grey value which differs from the grey value of the pixel immediately above the first pixel by at least the first predetermined constant, performing the followings substeps;

(b.1.2.1) detecting a longest horizontal edge which includes the first pixel, and

(b.1.2.2) when a total length of the longest horizontal edge exceeds a second predetermined constant, storing a y-coordinate of the first pixel as a current bottom edge;

(c) using the vertical edge as a rightmost edge of the bounding box; and

,

(d) using the horizontal edge as a bottom edge of the bounding box.

9. A method as in claim 8 wherein substep (b.1.2.1) includes the following substeps:

(b.1.2.1.1) detecting any edge from a right of the first pixel which is continued by the first pixel;

(b.1.2.1.2) detecting any edge from a left of the first pixel which is continued by the first pixel; and

(b.1.2.1.3) combining any edge from the right of the first pixel detected in substep (b.1.2.1.1) with any edge from the left of the first pixel detected in substep (b.1.2.1.2) to produce the longest horizontal edge.

10. A method as in claim 9 wherein substep (b.1.2.1.1) a first edge is included within any edge from the right of the first pixel which is continued by the first pixel when the first edge either includes a pixel directly to the right of the first pixel or includes a pixel one pixel above and one pixel to the right of the first pixel.

11. A method as in claim 9 wherein substep (b.1.2.1.2) a first edge is included within any edge from the left of the first pixel which is continued by the first pixel when the first edge either includes a pixel directly to the left of the first pixel or includes a pixel one pixel above and one pixel to the left of the first pixel.

12. A method for detecting a vertical edge of a scanned image comprising the following step:

(a) for each scan row, performing the following substeps for a subset of pixels in the scan row;

(a.1) detecting when a first pixel in the substep of pixels has a grey value which differs from a grey value of a pixel immediately to the right of the first pixel by at least a first predetermined constant, and

(a.2) when in substep (a.1), the first pixel in the substep of pixels has a grey value which differs from the grey value of the pixel immediately to the right of the first pixel by at least the first predetermined constant, performing the followings substeps;

(a.2.1) detecting any edge from a previous row which is continued by the first pixel,

(a.2.2) storing, for a longest edge in any row continued by the first pixel, a length of the longest edge,

(a.2.3) storing an indication of a rightmost pixel of any edge continued by the first pixel, and

(a.2.4) when the length of the longest edge continued by the first pixel exceeds a second predetermined constant, storing an x-coordinate of the rightmost pixel of any edge continued by the first pixel as a current rightmost edge.

13. A method as in claim 12, wherein in substep (a.1) the first predetermined constant is 7.

14. A method as in claim 12 wherein in step (a) for each scan row, the subset of pixels includes pixels located right of the current rightmost edge.

15. A method as in claim 12 additionally comprising the following step:

(b) using the current rightmost edge as an x-coordinate of the vertical edge.

16. A method as in claim 12 wherein in substep (a.2.1) a first edge is included within any edge from a previous row which is continued by the first pixel when the first edge either includes a pixel directly above the first pixel or includes a pixel one pixel above and one pixel to the right of the first pixel.

17. A method for detecting a horizontal edge of a scanned image comprising the following step:

(a) for each scan row, performing the following substeps for a subset of pixels in the scan row;

(a.1) detecting when a first pixel in the substep of pixels has a grey value which differs from a grey value of a pixel immediately above the first pixel by at least a first predetermined constant, and

(a.2) when in substep (a.1), the first pixel in the substep of pixels has the grey value which differs from the grey value of the pixel immediately above the first pixel by at least the first predetermined constant, performing the followings substeps;

(a.2.1) detecting a longest horizontal edge which includes the first pixel, and

(a.2.2) when a total length of the longest horizontal edge exceeds a second predetermined constant, storing a y-coordinate of the first pixel as a current bottom edge.

18. A method as in claim 17 wherein substep (a.2.1) includes the following substeps:

(a.2.1.1) detecting any edge from a right of the first pixel which is continued by the first pixel;

(a.2.1.2) detecting any edge from a left of the first pixel which is continued by the first pixel; and

(a.2.1.3) combining any edge from the right of the first pixel detected in substep (a.2.1.1) with any edge from the left of the first pixel detected in substep (a.2.1.2) to produce the longest horizontal edge.

19. A method as in claim 17 wherein substep (a.2.1.1) a first edge is included within any edge from the right of the first pixel which is continued by the first pixel when the first edge either includes a pixel directly to the right of the first pixel or includes a pixel one pixel above and one pixel to the right of the first pixel.

20. A method as in claim 17 additionally comprising the following step:

(b) using the current bottom edge as a y-coordinate of the horizontal edge.

21. A processing system for determining in a matrix array having fixed minimum and maximum x coordinate values and fixed minimum and maximum y coordinate values a minimal rectangular boundary box within which a replica image of an original scanned document is defined, comprising:

a processor having;

a horizontal edge arrangement for determining a variable right edge x coordinate value for helping to define a bottom right corner of said boundary box; and

a vertical edge arrangement for determining a variable bottom edge y coordinate value for further helping to define said bottom right corner of said boundary box, wherein said vertical edge arrangement includes;

a portion of a buffer memory for temporarily storing image data indicative of the replica image, said image data being defined by a plurality of gray scale pixel values arranged in rows and columns to facilitate image processing purposes;

a pixel processor for determining row by row and pixel by pixel whether the gray scale pixel value of a current pixel in a given row differs from the gray scale value of an adjacent pixel in the same row by at least a predetermined constant vertical value and for determining whether the current pixel in said given row extends a line segment having a given length exceeding another predetermined constant vertical value; and

,

a portion of a scratch memory for storing an x coordinate value of the right most pixel in said line segment extended by said current pixel when said line segment has a given length exceeding said another predetermined constant vertical value;

wherein said x coordinate value of the right most pixel in said line segment being defined as said variable right edge x coordinate value when the current pixel is the last pixel in said image data.

22. A processing system according to claim 21, wherein said horizontal edge arrangement includes:

another portion of said buffer memory for temporarily storing image data indicative of the replica image;

said pixel processor for further determining row by row and pixel by pixel whether the gray scale pixel value of said current pixel in said given row differs from the gray scale value of an adjacent pixel immediately above in an adjacent row not defining a boundary edge with a y coordinate value of zero by at least a predetermined constant horizontal value and for determining whether the current pixel in said given row extends a horizontal line segment having a given length exceeding another predetermined constant horizontal value;

another portion of said scratch memory for storing a y coordinate value of the current pixel when said horizontal line segment has a length exceeding said another predetermine constant horizontal value; and

said y coordinate value of the current pixel being defined as said variable bottom edge y coordinate value when the current pixel is the last pixel in said image data.

23. A processing system according to claim 22, further comprising:

a boundary coordinate defining arrangement responsive to said horizontal edge arrangement and said vertical edge arrangement for defining top left corner coordinate values, top right corner coordinate values, bottom left corner coordinate values and bottom right corner coordinate values of the boundary box;

said top left corner having x and y coordinate values defined respectively by 0 and 0 respectively;

said top right corner having x and y coordinate values defined respectively by 0 and a determined variable right edge x coordinate value;

said bottom left corner having x and y coordinate values defined respectively by 0 and a determined variable bottom edge y coordinate value; and

said bottom right corner having x and y coordinate values defined respectively by said determined variable right edge x coordinate value and said determined variable bottom edge y coordinate value.

24. A method for determining in a matrix array having

fixed minimum and maximum x coordinate values and fixed minimum and maximum y coordinate values a minimal rectangular boundary box within which a replica image of an original scanned document is defined, comprising:

determining a variable right edge x coordinate value for helping to define a bottom right corner of said boundary box; and

determining a variable bottom edge y coordinate value for further helping to define said bottom right corner of said boundary box;

wherein said step of determining a variable right edge x coordinate value includes;

temporarily storing image data indicative of the replica image, said image data being defined by a plurality of gray scale pixel values arranged in rows and columns to facilitate image processing purposes;

determining row by row and pixel by pixel whether the gray scale pixel value of a current pixel in a given row differs from the gray scale value of an adjacent pixel in the same row by at least a predetermined constant value and for determining whether the current pixel in said given row extends a line segment having a given length exceeding another predetermined constant value; and

storing an x coordinate value of the right most pixel in said line segment extended by said current pixel when said line segment has a given length exceeding said another predetermined constant;

said x coordinate value of the rightmost pixel in said line segment being defined as said variable right edge x coordinate value when the current pixel is the last pixel in said image data.

25. A method according to claim 24, further comprising:

defining a top left corner location of the boundary box in said matrix array, said top left corner having x and y coordinate values defined respectively by 0 and 0 respectively;

determining a top right corner location of the boundary box in said matrix array, said top right corner having x and y coordinate values defined respectively by 0 and a determined variable right edge x coordinate value;

determining a bottom left corner location of the boundary box in said matrix array, said bottom left corner having x and y coordinate values defined respectively by 0 and a determined variable bottom edge y coordinate value; and

determining a bottom right corner location of the boundary box in said matrix array, said bottom right corner having x and y coordinate values defined respectively by said determined variable night edge x coordinate value and said determined variable bottom edge y coordinate value.

26. A method for generating a bounding box for an image comprising the following steps:

(a) performing a scan of an original of the image to produce a scanned image;

(b) processing the scanned image one row at a time, including the following substeps;

(b.1) using limited statistics computed from previous rows to define vertical edges and horizontal edges in the scanned image, and

(b.2) performing the following substeps for every scan row processed;

(b.2.1) attempting to extend previously identified edge segments, and

(b.2.2) keeping track of columns through which vertical edges have passed and rows through which horizontal edges have passed;

(c) using a rightmost column through which an edge segment of at least a first minimal length has passed as a vertical edge of the bounding box; and

,

(d) using a bottommost row through which an edge segment of at least a second minimal length has passed as a bottom edge of the bounding box;

wherein in step (b) edge segments can be continued along 45 degree angles.

27. A method for generating a bounding box for an image comprising the following steps:

(a) performing a scan of an original of the image to produce a scanned image, wherein the scan is an 8-bits per pixel prescan;

(b) processing the scanned image one row at a time, including the following substeps;

(b.1) using limited statistics computed from previous rows to define vertical edges and horizontal edges in the scanned image, and

(b.2) performing the following substeps for every scan row processed;

-(b.2.1) attempting to extend previously identified edge segments, and

(b.2.2) keeping track of columns through which vertical edges have passed and rows through which horizontal edges have passed;

(c) using a rightmost column through which an edge segment of at least a first minimal length has passed as a vertical edge of the bounding box; and

,

(d) using a bottommost row through which an edge segment of at least a second minimal length has passed as a bottom edge of the bounding box.