Content-based detection and three dimensional geometric reconstruction of objects in image and video data

• US 10,127,636 B2
• Filed: 08/11/2016
• Issued: 11/13/2018
• Est. Priority Date: 09/27/2013
• Status: Active Grant

• Current Assignee: Tungsten Automation Corp.
• Original Assignee: Kofax Incorporated
• Inventors: Ma, Jiyong, Thompson, Stephen Michael, Amtrup, Jan W.
• Primary Examiner(s): Patel, Jayesh A
• Application Number:
  US15/234,993
• Publication Number:
  US 20160350592A1
• Time in Patent Office: 824 Days
• Field of Search: None
• CPC Class Codes: G01B 11/14 for measuring distance or clearance between spaced objects or spaced apertures G01B11/26 takes precedence; rangefinders G01C3/00
• CPC Class Codes: G06T 2207/30176 Document
• CPC Class Codes: G06T 3/00 Geometric image transformations in the plane of the image
• CPC Class Codes: G06T 5/70 Denoising; Smoothing
• CPC Class Codes: G06T 7/50 Depth or shape recovery
• CPC Class Codes: G06V 10/462 Salient features, e.g. scale invariant feature transforms [SIFT]
• CPC Class Codes: G06V 10/757 Matching configurations of points or features
• CPC Class Codes: G06V 30/418 Document matching, e.g. of document images
• CPC Class Codes: H04N 1/00 Scanning, transmission or reproduction of documents or the like, e.g. facsimile transmission; Details thereof

Abstract

Systems, computer program products, and techniques for reconstructing objects depicted in digital image data within a three-dimensional space are disclosed, according to various exemplary embodiments. The inventive concepts uniquely utilize internal features to accomplish reconstruction, thereby avoiding reliance on reconstructing objects based on information derived from location of edges. The inventive concepts thus provide an improvement over conventional object reconstruction since objects may be reconstructed even when edges are obscured or not depicted in the digital image data. In one aspect, a computer-implemented method of reconstructing an object depicted in a digital image includes: detecting a plurality of identifying features of the object, wherein the plurality of identifying features are located internally with respect to the object; and reconstructing the digital image of the object within a three dimensional coordinate space based at least in part on some or all of the plurality of identifying features.

Claims

1. A computer-implemented method of reconstructing an object depicted in a digital image, the method comprising:

detecting a plurality of identifying features of the object depicted in the digital image, wherein the plurality of identifying features are depicted in the digital image and located internally with respect to the object;

reconstructing the digital image of the object within a three dimensional coordinate space based at least in part on some or all of the plurality of identifying features, wherein reconstructing the digital image of the object comprises estimating a homography transform H, wherein estimating the homography transform H comprises an iterative process, and wherein each iteration of the iterative process comprises;

randomly selecting four key points from among the plurality of identifying features of the object;

using a four point algorithm to estimate an i^th homography transform H_i based on the four key points; and

applying the estimated i^th homography transform H_i to a set of corresponding key points;

wherein the set of corresponding key points comprises a plurality of point correspondences, each point correspondence including;

an other key point from the digital image and corresponding to one of the plurality of identifying features of the object; and

a corresponding key point from a reference image corresponding to the digital image;

determining one or more outlier key points from among each set of corresponding key points;

identifying, from among each set of corresponding key points, the set of corresponding key points having a lowest number of outlier key points;

defining a set of inlier key points from among the set of corresponding key points having the lowest number of outlier key points, the set of inlier key points excluding the outlier key points determined from among the set of corresponding key points having the lowest number of outlier key points; and

estimating the homography transform H based on the set of inlier key points;

wherein the digital image is a single digital image; and

wherein the plurality of identifying features are detected from within the single digital image.

2. The computer-implemented method as recited in claim 1, wherein reconstructing the digital image of the object comprises transforming the object to represent dimensions of the object as viewed from an angle normal to the object.

3. The computer-implemented method as recited in claim 1, wherein reconstructing the digital image of the object is based on four of the plurality of identifying features;

and

wherein the four of the plurality of identifying features are randomly selected from among the plurality of identifying features.

4. The computer-implemented method as recited in claim 1, wherein reconstructing the digital image of the object is based at least in part on applying a four-point algorithm to at least some of the plurality of identifying features.

5. The computer-implemented method as recited in claim 1, wherein estimating H comprises detecting one or more point correspondences p_i ↔

P_i′

with p_i=(x_i,y_i,1)^T.

6. The computer-implemented method as recited in claim 5, wherein each point correspondence p_i ↔

P_i′

corresponds to a position p_i of one of the plurality of identifying features of the object, and a respective position P_i′

of a corresponding identifying feature of the reconstructed digital image of the object.

7. The computer-implemented method as recited in claim 5, wherein estimating H comprises normalizing coordinates of some or all of the point correspondences.

8. The computer-implemented method as recited in claim 1, wherein determining the one or more outlier key points from among each set of corresponding key points comprises:

determining whether each of the plurality of point correspondences fits a transformation model corresponding to the estimated i^th homography transform H_i; and

, for each of the plurality of point correspondences, either;

designating the other key point of the point correspondence as an outlier key point in response to determining the point correspondence does not fit the transformation model;

or

designating the other key point of the point correspondence as an inlier key point in response to determining the point correspondence does fit the transformation model.

9. The computer-implemented method as recited in claim 1, wherein the plurality of identifying features correspond to boilerplate content of the object.

10. The computer-implemented method as recited in claim 1, wherein at least one edge of the object is either obscured or missing from the digital image.

11. The computer-implemented method as recited in claim 1, comprising cropping the reconstructed digital image of the object based at least in part on a projected location of one or more edges of the object within the reconstructed digital image.

12. The computer-implemented method as recited in claim 11, wherein the projected location of the one or more edges of the object is based at least in part on an estimated homography transform H.

13. The computer-implemented method as recited in claim 1, comprising classifying the reconstructed digital image of the object.

14. A computer program product for reconstructing an object depicted in a digital image, comprising a non-transitory computer readable medium having stored thereon computer readable program instructions configured to cause a processor, upon execution thereof, to:

detect, using the processor, a plurality of identifying features of the object depicted in the digital image, wherein the plurality of identifying features are depicted in the digital image and located internally with respect to the object;

reconstruct, using the processor, the digital image of the object within a three dimensional coordinate space based at least in part on some or all of the plurality of identifying features, wherein reconstructing the digital image of the object comprises estimating a homography transform H, wherein estimating the homography transform H comprises an iterative process, and wherein each iteration of the iterative process comprises;

randomly selecting four key points from among the plurality of identifying features of the object;

using a four point algorithm to estimate an i^th homography transform H_i based on the four key points; and

applying the estimated i^th homography transform H_i to a set of corresponding key points;

wherein the set of corresponding key points comprises a plurality of point correspondences, each point correspondence including;

an other key point from the digital image and corresponding to one of the plurality of identifying features of the object; and

a corresponding key point from a reference image corresponding to the digital image;

determine one or more outlier key points from among each set of corresponding key points;

identify, from among each set of corresponding key points, the set of corresponding key points having a lowest number of outlier key points;

define a set of inlier key points from among the set of corresponding key points having the lowest number of outlier key points, the set of inlier key points excluding the outlier key points determined from among the set of corresponding key points having the lowest number of outlier key points; and

estimate the homography transform H based on the set of inlier key points;

wherein the digital image is a single digital image; and

wherein the plurality of identifying features are detected from within the single digital image.

15. The computer program product as recited in claim 14, wherein reconstructing the digital image of the object is based on four of the plurality of identifying features;

and

wherein the four of the plurality of identifying features are randomly selected from among the plurality of identifying features.

16. The computer program product as recited in claim 14, wherein reconstructing the digital image of the object is based at least in part on applying a four-point algorithm to at least some of the plurality of identifying features.

17. A system for reconstructing an object depicted in a digital image, comprising a processor and logic embodied with the processor, the logic being configured to cause the processor, upon execution thereof, to:

detect a plurality of identifying features of the object depicted in the digital image, wherein the plurality of identifying features are depicted in the digital image and located internally with respect to the object;

reconstruct the digital image of the object within a three dimensional coordinate space based at least in part on some or all of the plurality of identifying features, wherein reconstructing the digital image of the object comprises estimating a homography transform H, wherein estimating the homography transform H comprises an iterative process, and wherein each iteration of the iterative process comprises;

randomly selecting four key points from among the plurality of identifying features of the object;

using a four point algorithm to estimate an i^th homography transform H_i based on the four key points; and

applying the estimated i^th homography transform H_i to a set of corresponding key points;

wherein the set of corresponding key points comprises a plurality of point correspondences, each point correspondence including;

an other key point from the digital image and corresponding to one of the plurality of identifying features of the object; and

a corresponding key point from a reference image corresponding to the digital image;

determine one or more outlier key points from among each set of corresponding key points;

identify, from among each set of corresponding key points, the set of corresponding key points having a lowest number of outlier key points;

define a set of inlier key points from among the set of corresponding key points having the lowest number of outlier key points, the set of inlier key points excluding the outlier key points determined from among the set of corresponding key points having the lowest number of outlier key points; and

estimate the homography transform H based on the set of inlier key points;

wherein the digital image is a single digital image; and

wherein the plurality of identifying features are detected from within the single digital image.