System and method for whiteboard scanning to obtain a high resolution image

• US 7,119,816 B2
• Filed: 03/31/2003
• Issued: 10/10/2006
• Est. Priority Date: 03/31/2003
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Zhang, Zhengyou, He, Li-wei
• Primary Examiner(s): Brier, Jeffery A.
• Application Number:
  US10/404,745
• Publication Number:
  US 20040189674A1
• Time in Patent Office: 1,289 Days
• Field of Search: 345/629, 345/634, 345/635, 382/284, 382/294, 248/218.1
• US Class Current: 345/634
• CPC Class Codes: H04N 1/04 Scanning arrangements , i.e. arrangements for the displacement of active reading or reproducing elements relative to the original or reproducing medium, or vice versaH04N1/387 takes precedence
• CPC Class Codes: H04N 1/195 the array comprising a two-dimensional array or a combination of two-dimensional arrays
• CPC Class Codes: H04N 1/19594 using a television camera or a still video camera
• CPC Class Codes: H04N 2201/0414 Scanning an image in a series of overlapping zones
• CPC Class Codes: H04N 2201/0424 Scanning non-straight lines
• CPC Class Codes: H04N 2201/0426 Scanning an image in a series of contiguous zones
• CPC Class Codes: H04N 2201/0438 Scanning displays; Scanning large surfaces, e.g. projection screens, writing boards

Abstract

This invention is directed toward a system and method for scanning a scene or object such as a whiteboard, paper document or similar item. More specifically, the invention is directed toward a system and method for obtaining a high-resolution image of a whiteboard or other object with a low-resolution camera. The system and method of the invention captures either a set of snapshots with overlap or a continuous video sequence, and then stitches them automatically into a single high-resolution image. The stitched image can finally be exported to other image processing systems and methods for further enhancement.

Claims

1. A computer-implemented process for converting the contents of a planar object into a high-resolution image, comprising the process actions of:

acquiring a sequence of images of portions of a planar object which have been captured in a prescribed pattern and wherein each subsequent image overlaps a previous image in said pattern;

extracting points of interest in each image;

matching said points of said interest between each pair of successive images wherein the process action of matching said points of said interest between each pair of successive images comprises the process actions of;

for each point of interest in the earlier captured image of the pair of images under consideration, establishing a window of pixels centered on the point of interest;

for each point of interest,

comparing said window in said earlier captured image of the pair under consideration with windows of pixels the same size which are centered on the points of interest in the later-captured image of the pair by computing a zero-mean normalized cross correlation between the windows; and

whenever the largest correlation scare computed between the window of the earlier captured image and each of the windows in the later captured image exceeds a prefixed threshold, designating the associated point in the later-captured image as a match candidate for the point under consideration in the earlier-captured image;

computing a projective mapping between each pair of successive images in order to determine corresponding pixel locations in the images; and

generating a composite image from said sequence of images using said projective mapping.

2. The computer-implemented process of claim 1 wherein the match candidate with the largest correlation in the earlier-captured image is considered a match when the point under consideration in the later-captured is the same as the point corresponding to the match candidate in the earlier captured image.

3. The computer-implemented process of claim 1 wherein said process action of computing a projective mapping between each set of two successive images in said ordered sequence of image, comprises the process actions of:

(a) inputting a first image and a second image;

(b) drawing m random subsamples of p=4 different point matches;

(c) for each subsample J, computing a homography matrix H_j;

(d) for each H_J, determining the median of the squared residuals, denoted by

M_J, with respect to the whole set of point matches, where the squared residual for match i is given by ∥

m_2i−

{circumflex over (m)}_1i∥

² where {circumflex over (m)}_1i is point in m_1i, transferred to the second image by H_J;

(e) retaining the estimate H_J for which M_J is minimal among all m M_J'"'"'s;

(f) computing a robust standard deviation estimate {circumflex over (σ

)};

(g) declaring a point match as a false match if its residual is larger than k{circumflex over (σ

)}, where k is set to a prescribed value;

(h) discarding the false matches and re-estimating H by minimizing the sum of squared errors Σ

_i1 ∥

m_2i−

{circumflex over (m)}_1i∥

² where the summation is over all good matches; and

(i) repeating process actions (a) through (h) until all images of me sequence of images have been processed.

4. The computer-implemented process of claim 3 wherein k=2.5.

5. The computer-implemented process of claim 3 wherein the robust standard deviation {circumflex over (σ

)}=1,4826[1+5/(n−

p)]√

{square root over (M_j)} where n is twice the number of the matched points.

6. The computer-implemented process of claim 1, wherein the process action of computing a projective mapping comprises computing a homography in the form of a homography matrix between each pair of two successive images and refining the homographies computed for each pair of successive images through global optimization;

further comprising the process actions of;

for a total of N images, choosing a first image as the reference image for the global optimization and letting me homography matrix from the reference image to image i be H_i, with H₁=1, the identity matrix, and defining that there are M distinct points in the reference image, which are called reference points, denoted by {circumflex over (m)}_j;

defining a variable φ

_ij=1 if point j is observed in image i and φ

_ij=0 otherwise;

formulating the global optimization as an estimation of both homography matrices H_i'"'"'s and reference points {circumflex over (m)}_ij'"'"'s by minimizing the errors between the expected positions of the reference points in the images and the observed reference points in the images.

7. The computer-implemented process of claim 6 where the estimation of both homography matrices H_i'"'"'s and reference points {circumflex over (m)}_j'"'"'s is computed by minimizing the errors between the expected positions of said reference points and the observed reference points in the images using the equation

$\underset{\left\{H_i\right\},\left\{{\hat{m}}_j\right\}}{\min }$

∑

i = 1 N ⁢

⁢

∑

j = 1 M ⁢

⁢



m ij - m ^ ii 

2 ,

where={tilde over ({circumflex over (m)}_ij=λ

_ijH{tilde over ({circumflex over (m)}_j with λ

_ij being a scalar factor.

8. A system for converting markings on a planar object into a high resolution image, the system comprising:

a general purpose computing device; and

a computer program comprising program modules executable by the computing device, wherein the computing device is directed by the program modules of the computer program to,

acquire a sequence of images of portions of a planar object having been captured in a prescribed pattern, each subsequent image overlapping a previous image in said pattern;

extract points of interest in each image in said sequence;

match said points of said interest between two successive images in said sequence;

wherein the program module for matching said points of said interest between two successive images in said sequence comprises sub-modules for,

for each point of Interest in the earlier captured image of the set of images under consideration, establishing a window of pixels centered on the point of interest,

for each point of interest,

comparing said window in said earlier captured image of the set under consideration with windows of pixels the same size which are centered on the points of interest in the later-captured image of the set by computing a zero-mean normalized cross correlation between the windows, and

whenever the largest correlation score computed between the window of the earlier captured image and each of the windows in the later captured captured image as a match candidate for the point under consideration in the earlier-captured image;

compute a projective mapping between each set of two successive images in said sequence of images in order to determine corresponding pixel locations in the images of each set; and

generate a composite image from said images using said projective mapping.

9. The system of claim 8 wherein the match candidate with the largest correlation in the earlier-captured image is considered a match when the point under consideration in the later-captured image is the same as the point corresponding to the match candidate in the earlier captured image.

10. The system of claim 8 wherein said program module for computing a projective mapping between each set of two successive images in said sequence of images, comprises sub-modules for:

(a) inputting a first image and a second image;

(b) drawing m random subsamples of p=4 different point matches;

(c) for each subsample J, computing a homography matrix H_j,

(d) for each H_J, determining the median of the squared residuals, denoted by M_J, with respect to the whole set of point matches, where the squared residual for match i is given by ∥

m_2i−

{circumflex over (m)}_1i ∥

² where {circumflex over (m)}_1i is point m_1i transferred to the second image by H_J;

(e) retaining the estimate H_J for which M_J is minimal among all m M_J'"'"'s;

(f) computing the robust standard deviation estimate {circumflex over (σ

)}=1.4826[1+5/(n−

p)]√

{square root over (M_J )}where n, is twice the number of matched points;

(g) declaring a point match as a false match if its residual is larger than k{circumflex over (σ

)}, where k is set to a prescribed number;

(h) discarding the false matches and re-estimating H by minimizing the sum of squared errors Σ

₁∥

m_2i−

{circumflex over (m)}_1i∥

² where me summation is over all good matches; and

(i) repeating process actions (a) through (h) until all images have been processed.

11. The system of claim 10 wherein the homography matrix H_J is calculated by letting m₁=[u₁, v₁]^T and m₂=[u₂, v₂]^T be a pair of corresponding points, and using the notation {tilde over ( )} for {tilde over (m)}=[u ,v1]^T, such that {tilde over (m)}₂=σ

H{tilde over (m)}_j.

12. A computer-readable medium having computer-executable instructions for converting a series of low resolution images of portions of a planar object into a high resolution image of said object, said computer executable instructions causing a computer to execute the method comprising:

acquiring a series of images of the depicting portions of the same scene;

extracting points of interest in each image of said series of images;

matching said points of interest in each image of said series of images with the image preceding said image in said series of images, wherein said matching said points of interest in each image of said series of images with the preceding said image in said series of images comprises,

for each point of interest in the preceding image of a pair of images under consideration, establishing a window of pixels centered on the point of interest;

for each point of interest,

comparing said window in said preceding image of the pair under consideration with windows of pixels the same size which are centered on the points of interest in the later-captured image of the pair by computing a zero-mean normalized cross correlation between the windows, and

whenever the largest correlation score computed between the window of the preceding image and each of the windows in the later captured image exceeds a prefixed threshold, designating the associated point in the later-captured image as a match candidate for the point under consideration in the preceding images;

calculating a homography between each image of said series of images with the image preceding said image in said series of images; and

stitching each image in said series of images together using said homographies to create a composite image.

13. The computer-readable medium of claim 12 wherein said calculating a homography between each image of said series of images with the image preceding said image in said series of images comprises solving the nonlinear problem

$\underset{}{\min }$

⁢

median H ⁢

⁢

i ⁢

⁢



m 2 ⁢

i - m ^ 1 ⁢

i 

2

where {(m_1i, m_2i)} are the pairs of points between two matched images, H is the homography matrix, {circumflex over (m)}_1i is the point m_1i transferred to the current image by H , and where {tilde over ({circumflex over (m)}_1i=λ

_iH{tilde over (m)}_1i, λ

_i being a scalar factor.

14. The computer-readable medium of claim 12 wherein the match candidate with the largest correlation in the preceding image is considered a match when the point under consideration in the later-captured image is the same as the point corresponding to the match candidate in the preceding image.

15. The computer-readable medium of claim 12 wherein said matching said points of interest in each image of said series of images with the preceding image in said series of images further comprises:

(a) inputting a pair of consecutive images of a set of original images;

(b) checking whether the image resolution is greater than a prescribed value;

(c) if the resolution is too high, then downsampling the images by half at each iteration that the resolution is too high, thus building a pyramidal structure for each image up to a level at which the image resolution reaches a prescribed resolution;

(d) at the lowest level, or with the original resolution if the size of input images is not too large, employing a multi-start search strategy is employed to estimate a homography between the pair of images;

(e) generating nine start points, each defining the center of a search window of the previously described matching algorithm, where W and H are defined as the width and height of an image and the nine points are (−

W/2, −

H/2), (0, −

H/2), (W/2, −

H/2);

(−

W/2,

     0), (0,

     0), (W/2,

     0);

(−

W/2, H/2), (0, H/2), (W/2, H/2);

(f) for each start point, running a matching and homography estimation procedure, which gives the number of matched points and the root of mean square errors (RMS) of matched points, as well as an estimation of the homography between the two images;

(g) choosing the homography estimation which corresponds to the largest number of matched points and the smallest RMS;

(h) if the last level has not been reached, proceeding to the higher level using the previously estimated homography;

projecting the homography to the higher level, letting H_i-1 be the homography at level i−

1 and the corresponding homography at level i, setting H_i, equal to S H<sub>i−

1</sub>S<sup>−

1</sup>, where S=diag(2, 2,

     1);

refining the homography at the current level; and

(i) repeating (a) through (h) until all images of the set of original images are matched, and reporting the last estimated homography as the output.

16. The computer-readable medium of claim 15 wherein said refining said homography comprises

transforming the four image corners using H_j;

computing the disparity for each point wherein the disparity is the difference between the transformed corner point and the original one;

computing the maximum and minimum disparities in born the horizontal and vertical directions;

defining the search range by enlarging the difference between the maximum and minimum disparities by a certain amount to account for the imprecision of the estimation H_j;

matching the points using said defined search range; and

estimating the homography based on least-median-squares.

17. The computer-readable medium of claim 15 wherein said refining said homography comprises:

transforming the first image and all the detected corners using H_j;

matching the corners and estimating the homography between the transformed image and the second image, said estimated imaged being denoted by Δ

H_j, calculating the refined homography as Δ

H_jH_i.