Systems and methods for mobile image capture and processing

• US 9,165,187 B2
• Filed: 01/11/2013
• Issued: 10/20/2015
• Est. Priority Date: 01/12/2012
• Status: Active Grant

• Current Assignee: Tungsten Automation Corp.
• Original Assignee: Kofax Incorporated
• Inventors: Macciola, Anthony, Shustorovich, Alexander, Thrasher, Christopher W.
• Primary Examiner(s): COUSO, JOSE L
• Application Number:
  US13/740,127
• Publication Number:
  US 20130182973A1
• Time in Patent Office: 1,012 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 17/40 Data acquisition and logging for input to computer G06F3/00
• CPC Class Codes: G06F 3/005 Input arrangements through a video camera
• CPC Class Codes: G06Q 40/08 Insurance
• CPC Class Codes: G06Q 50/18 Legal services
• CPC Class Codes: G06T 1/0007 Image acquisition
• CPC Class Codes: G06T 11/20 Drawing from basic elements, e.g. lines or circles
• CPC Class Codes: G06T 2207/10024 Color image
• CPC Class Codes: G06T 2207/20021 Dividing image into blocks, subimages or windows
• CPC Class Codes: G06T 2207/20164 Salient point detection; Corner detection
• CPC Class Codes: G06T 2207/30004 Biomedical image processing
• CPC Class Codes: G06T 2207/30176 Document
• CPC Class Codes: G06T 3/02 Affine transformations for image registration G06T3/147; for image mosaicing G06T3/4038
• CPC Class Codes: G06T 3/10 Selection of transformation methods according to the characteristics of the input images
• CPC Class Codes: G06T 5/00 Image enhancement or restoration
• CPC Class Codes: G06T 5/70 Denoising; Smoothing
• CPC Class Codes: G06T 5/73 Deblurring; Sharpening
• CPC Class Codes: G06T 7/00 Image analysis
• CPC Class Codes: G06T 7/0002 Inspection of images, e.g. flaw detection
• CPC Class Codes: G06T 7/12 Edge-based segmentation
• CPC Class Codes: G06T 7/13 Edge detection
• CPC Class Codes: G06T 7/143 : involving probabilistic approaches, e.g. Markov random field [MRF] modelling
• CPC Class Codes: G06T 7/194 : involving foreground-background segmentation
• CPC Class Codes: G06V 10/247 : by affine transforms, e.g. correction due to perspective effects; Quadrilaterals, e.g. trapezoids
• CPC Class Codes: G06V 10/25 : Determination of region of interest [ROI] or a volume of interest [VOI]
• CPC Class Codes: G06V 30/413 : Classification of content, e.g. text, photographs or tables
• CPC Class Codes: G06V 30/414 : Extracting the geometrical structure, e.g. layout tree; Block segmentation, e.g. bounding boxes for graphics or text
• CPC Class Codes: H04N 1/00116 : of multimedia information
• CPC Class Codes: H04N 1/00251 : with an apparatus for taking photographic images, e.g. a camera
• CPC Class Codes: H04N 1/00403 : Voice input means, e.g. voice commands
• CPC Class Codes: H04N 1/387 : Composing, repositioning or otherwise geometrically modifying originals
• CPC Class Codes: H04N 1/3872 : Repositioning or masking
• CPC Class Codes: H04N 1/3878 : Skew detection or correction
• CPC Class Codes: H04N 1/40 : Picture signal circuits H04N1/387 takes precedence
• CPC Class Codes: H04N 2201/0081 : Image reader H04N2201/0091 - H04N2201/0094 take precedence
• CPC Class Codes: H04N 2201/0096 : Portable devices

Abstract

In various embodiments, methods, systems, and computer program products for processing digital images captured by a mobile device are disclosed. Myriad features enable and/or facilitate processing of such digital images using a mobile device that would otherwise be technically impossible or impractical, and furthermore address unique challenges presented by images captured using a camera rather than a traditional flat-bed scanner, paper-feed scanner or multifunction peripheral.

Claims

1. A method for modifying one or more spatial characteristics of a digital representation of a document in a digital image, the method comprising:

transforming a tetragon into a rectangle using at least one processor,

wherein the tetragon is characterized by a plurality of equations,

wherein each equation corresponds to a side of the tetragon,

wherein each equation is selected from a chosen class of functions, and

wherein at least one of the equations is a second-degree or higher polynomial.

2. The method as recited in claim 1, wherein the transforming comprises smooth stretching of the tetragon into the rectangle.

3. The method as recited in claim 1, wherein the transforming comprises:

determining a height of the rectangle;

determining a width of the rectangle;

determining a skew angle of the rectangle; and

determining a center position of the rectangle.

4. The method as recited in claim 1, wherein the transforming comprises:

defining a plurality of tetragon-based intrinsic coordinate pairs (p, q) within the tetragon, each intrinsic coordinate pair (p, q) corresponding to an intersection of;

a top-to-bottom curve characterized by an equation derived from an equation corresponding to a left side of the tetragon and an equation corresponding to a right side of the tetragon, and

a left-to-right curve characterized by an equation derived from an equation corresponding to a top side of the tetragon and an equation corresponding to a bottom side of the tetragon,

wherein the top-to-bottom curve equation is derived by combining one or more coefficients of the equation corresponding to a left side of the tetragon and one or more coefficients of the equation corresponding to the right side of the tetragon in a ratio of p to (1−

p),

wherein 0≦

p≦

1,

wherein the left-to-right curve equation is derived by combining one or more coefficients of the equation corresponding to the top side of the tetragon and one or more coefficients of the equation corresponding to the bottom side of the tetragon in a ratio of q to (1−

q), and

wherein 0≦

q≦

1.

5. The method as recited in claim 4, wherein the tetragon is characterized by a substantially rectangular shape.

6. The method as recited in claim 4, wherein the equation characterizing the top-to-bottom curve is:

x=((1−

p)*a₂+p*b₂)*y²+((1−

p)*a₁+p*b₁)*y+((1−

p)*a₀+p*b₀), and

wherein the equation characterizing the left-to-right curve is;

y=((1−

q)*c₂+p*d₂)*x²+((1−

q)*c₁+q*d₁)*x+((1−

q)*c₀+q*d₀).

7. The method as recited in claim 1, wherein the transforming further comprises:

generating a rectangularized digital image from the digital image;

determining a p-coordinate and a q-coordinate for a plurality of points within the rectangularized digital image;

wherein each point located to the left of the rectangle has a p-coordinate value p<

0,

wherein each point located to the right of the rectangle has a p-coordinate value p>

1,

wherein each point located above the rectangle has a q-coordinate value q<

0, and

wherein each point located below the rectangle has a q-coordinate value q>

1.

8. The method as recited in claim 1, wherein the transforming further comprises:

generating a rectangularized digital image from the digital image;

determining a pair of rectangle-based coordinates for each point within the rectangularized digital image; and

matching each pair of rectangle-based coordinates to an equivalent pair of tetragon-based intrinsic coordinates within the digital image, the matching comprising performing an iterative search for an intersection of a top-to-bottom curve and a left-to-right curve.

9. The method as recited in claim 1, wherein the digital image exhibits characteristics of being captured by a mobile device, and wherein the at least one processor includes a processor of the mobile device.

10. The method as recited in claim 1, the matching comprising performing an iterative search for an intersection of the top-to-bottom curve and the left-to-right curve, the iterative search comprising:

designating a starting point (x₀, y₀);

projecting the starting point (x₀, y₀) onto the left-to-right curve based on an equation

x₁=u₂*y₀²+u₁*y₀+u₀; and

projecting a next point (x₁, y₀) onto the top-to-bottom curve based on an equation

y₁=v₂*x₁²+v₁*x₁+v₀,

wherein u_i=(1−

p)*a₁+p*b₁, and

wherein v_i=(1−

q)*c_i+q*d_i and

the method further comprising;

iteratively projecting a plurality of points (x_k, y_k) onto the left-to-right curve based on an equation

x_k+1=u₂*y_k²+U₁*y_k+u₀; and

iteratively projecting a plurality of points (x_k+1, y_k) onto the top-to-bottom curve based on an equation

y_k+1=v₂*x_k+1² v₁*x_k+1+v₀.

11. The method as recited in claim 10, wherein the matching further comprises:

determining a distance between (x_k, y_k) and (x_k+1, y_k+1); and

determining whether the distance is less than a predetermined threshold.

12. The method as recited in claim 11, further comprising terminating the iterative search upon determining that the distance is less than the predetermined threshold.

13. The method as recited in claim 1,

wherein a left side of the tetragon is characterized by a second degree polynomial equation:

x=a₂*y²+a₁*y+a₀,

wherein a right side of the tetragon is characterized by a second degree polynomial equation;

x=b₂*y²+b₁*y+b₀,

wherein a top side of the tetragon is characterized by a second degree polynomial equation;

y=c₂*x²+c₁*x+c₀, and

wherein a bottom side of the tetragon is characterized by a second degree polynomial equation;

y=d₂*x²+d₁*x+d₀.

14. A system, comprising:

a processor configured to execute logic; and

logic for transforming a tetragon into a rectangle,

wherein the tetragon is characterized by a plurality of equations,

wherein each equation corresponds to a side of the tetragon,

wherein each equation is selected from a chosen class of functions, and

wherein at least one of the equations is a second-degree or higher polynomial.

15. A computer program product comprising a computer readable storage medium having computer readable program code stored thereon, the computer readable program code comprising:

computer readable program code configured to transform a tetragon depicted in a digital image into a rectangle,

wherein the tetragon is characterized by a plurality of equations,

wherein each equation corresponds to a side of the tetragon, and

wherein each equation is selected from a chosen class of functions, and

wherein at least one of the equations is a second-degree or higher polynomial.

16. The computer program product as recited in claim 15, wherein the transforming comprises smooth stretching of the tetragon into the rectangle.

17. The computer program product as recited in claim 15, wherein the transforming comprises:

determining a height of the rectangle;

determining a width of the rectangle;

determining a skew angle of the rectangle; and

determining a center position of the rectangle.

18. The computer program product as recited in claim 15, wherein the transforming further comprises:

generating a rectangularized digital image from the digital image;

determining a p-coordinate and a q-coordinate for a plurality of points within the rectangularized digital image;

wherein each point located to the left of the rectangle has a p-coordinate value p<

0,

wherein each point located to the right of the rectangle has a p-coordinate value p>

1,

wherein each point located above the rectangle has a q-coordinate value q<

0, and

wherein each point located below the rectangle has a q-coordinate value q>

1.

19. The computer program product as recited in claim 15, wherein the transforming further comprises:

generating a rectangularized digital image from the digital image;

determining a pair of rectangle-based coordinates for each point within the rectangularized digital image; and

matching each pair of rectangle-based coordinates to an equivalent pair of tetragon-based intrinsic coordinates within the digital image.

20. The computer program product as recited in claim 15, wherein the digital image exhibits characteristics of being captured by a mobile device, and wherein the computer readable program code is configured to cause a processor of the mobile device to transform the tetragon into the rectangle.