Methods and apparatus for locating lines in images and using located lines to make image adjustments

• US 9,336,455 B1
• Filed: 02/10/2015
• Issued: 05/10/2016
• Est. Priority Date: 12/22/2014
• Status: Active Grant

• Current Assignee: Accusoft Corporation
• Original Assignee: Accusoft Corporation
• Inventors: Withers, William Douglas, Martucci, Stephen A.
• Primary Examiner(s): Vu, Kim
• Assistant Examiner(s): Bloom, Nathan
• Application Number:
  US14/618,794
• Time in Patent Office: 455 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06T 2207/10008 from scanner, fax or copier
• CPC Class Codes: G06T 2207/20021 Dividing image into blocks, subimages or windows
• CPC Class Codes: G06T 2207/30176 Document
• CPC Class Codes: G06T 7/13 Edge detection
• CPC Class Codes: G06V 10/48 by mapping characteristic values of the pattern into a parameter space, e.g. Hough transformation
• CPC Class Codes: H04N 1/3873 defined only by a limited number of coordinate points or parameters, e.g. corners, centre; for trimming
• CPC Class Codes: H04N 1/3878 Skew detection or correction
• CPC Class Codes: H04N 1/40062 Discrimination between different image types, e.g. two-tone, continuous tone

Abstract

Methods and apparatus for identifying lines in an image are described. An image to be processed is divided into a plurality of tiles, and processing is performed on a per tile basis. Lines are identified in tiles and a weight is assigned to each line based on among other things, the length of the line. Quantized first and second parameter values, e.g., values defining where lines enters and leave an area, are used in defining the identified lines. A set of lines is selected based on the weight information and output or used in image processing the image including the lines.

Claims

1. A method of identifying lines in an image, the method comprising:

processing a tile of said image, said processing including;

performing a line identification operation on a tile of said image, said line identification operation identifying a line in said tile when a line is present;

determining, when said line identification operation identifies a line in said tile of interest;

i) a first quantized parameter value used in defining the identified line, and ii) a line weight corresponding to the identified line;

updating, based on the determined line weight, i) an accumulated line weight value corresponding to the determined first quantized parameter value defining the identified line ii) a first accumulated parameter weighted sum corresponding to the identified line and iii) a second accumulated parameter weighted sum corresponding to the identified line; and

identifying a number of lines in said image based on accumulated values generated from processing multiple different tiles of said image, said identifying a number of lines including identifying n largest accumulated line weights, each of the n largest accumulated line weights corresponding to a different pair of quantized perimeter locations, where n is a positive integer value.

2. The method of claim 1, further comprising:

determining, when said line identification operation identifies a line in said tile of interest, prior to updating the second accumulated parameter weighted sum, a second quantized parameter value corresponding to the identified line.

3. The method of claim 2, wherein said method includes performing said step of processing a tile for each of multiple tiles of said image.

4. The method of claim 3,

wherein identifying a number of lines in said image includes:

i) dividing the accumulated first parameter weighted sum corresponding to the identified largest accumulated line weight, by the largest accumulated line weight, to determine a first line parameter value corresponding to a first line and ii) dividing the second accumulated parameter weighted sum corresponding to the identified largest accumulated line weight, by the largest accumulated line weight, to determine a second line parameter value of the first line, said first and second line parameters values of the first line defining the first line in said image.

5. The method of claim 2, wherein the quantized parameter values indicate perimeter locations indicating where the identified line would enter and exit said image perimeter if extended through the image perimeter.

6. The method of claim 5, wherein first accumulated parameter weighted sum corresponding to the identified line is an accumulated perimeter entry point weighted sum;

and iii) the second accumulated parameter weighted sum is an accumulated perimeter exit point weighted sum corresponding to the determined quantized perimeter locations of the identified line.

7. The method of claim 3,

wherein said step of performing a line identification operation of a tile is performed for a space corresponding to a tile;

and

determining, when said line identification operation identifies a line in said tile of interest quantized perimeter locations, includes determining where the identified line would intersect the perimeter of said image if the identified line was extended beyond a boundary of a tile to the perimeter of said image.

8. The method of claim 7, wherein said quantized perimeter locations are image perimeter segment locations.

9. The method of claim 8, wherein said image perimeter segment locations identify perimeter segments which are of a different length than a side of said tile.

10. The method of claim 2, wherein said line is a transition between light and dark image regions.

11. The method of claim 2, wherein said line is a straight image region bordered on each side of the straight image region by pixels having a different intensity than pixels in said straight image region.

12. A non-transitory computer readable medium for use in a computer comprising:

code for causing said computer to process a tile of said image, said processing including;

performing a line identification operation on a tile of said image, said line identification operation identifying a line in said tile when a line is present;

determining, when said line identification operation identifies a line in said tile of interest;

i) a first quantized parameter value used in defining the identified line, and ii) a line weight corresponding to the identified line; and

updating, based on the determined line weight, i) an accumulated line weight value corresponding to the determined first quantized parameter value defining the identified line ii) a first accumulated parameter weighted sum corresponding to the identified line and iii) a second accumulated parameter weighted sum corresponding to the identified line; and

code for causing said computer to identify a number of lines in said image based on accumulated values generated from processing multiple different tiles of said image, said identifying a number of lines including identifying n largest accumulated line weights, each of the n largest accumulated line weights corresponding to a different pair of quantized perimeter locations, where n is a positive integer value.

13. The non-transitory computer readable medium of claim 12, wherein said a non-transitory computer readable medium further comprises:

code for causing said computer to determine, when said line identification operation identifies a line in said tile of interest, prior to updating the second accumulated parameter weighted sum, a second quantized parameter value corresponding to the identified line.

14. The non-transitory computer readable medium of claim 13, wherein said non-transitory computer readable medium further comprises code for causing said computer to perform said step of processing a tile for each of multiple tiles of said image.

15. A system comprising:

at least one processor configured to;

process a tile of said image, said processing including;

performing a line identification operation on a tile of said image, said line identification operation identifying a line in said tile when a line is present;

determining, when said line identification operation identifies a line in said tile of interest;

i) a first quantized parameter value used in defining the identified line, and ii) a line weight corresponding to the identified line;

updating, based on the determined line weight, i) an accumulated line weight value corresponding to the determined first quantized parameter value defining the identified line ii) a first accumulated parameter weighted sum corresponding to the identified line and iii) a second accumulated parameter weighted sum corresponding to the identified line; and

identify a number of lines in said image based on accumulated values generated from processing multiple different tiles of said image, said processor identifying n largest accumulated line weights, each of the n largest accumulated line weights corresponding to a different pair of quantized perimeter locations, n being a positive integer value, as part of being configured to identify a number of lines in said image; and

memory coupled to said at least one processor.

16. The computer of claim 15, wherein said processor is further configured to:

determine, when said line identification operation identifies a line in said tile of interest, prior to updating the second accumulated parameter weighted sum, a second quantized parameter value corresponding to the identified line.

17. The system of claim 16, wherein said processor is further configured to perform said step of processing a tile for each of multiple tiles of said image.

18. The system of claim 17, wherein said processor is configured to:

i) divide the accumulated first parameter weighted sum corresponding to the identified largest accumulated line weight, by the largest accumulated line weight, to determine a first line parameter value corresponding to a first line and ii) divide the second accumulated parameter weighted sum corresponding to the identified largest accumulated line weight, by the largest accumulated line weight, to determine a second line parameter value of the first line, said first and second line parameters values of the first line defining the first line in said image, as part of being configured to identify a number of lines in said image.