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

• US 7,301,548 B2
• Filed: 12/11/2004
• Issued: 11/27/2007
• 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:
  US11/010,150
• Publication Number:
  US 20050104902A1
• Time in Patent Office: 1,081 Days
• Field of Search: 345/629, 345/634, 345/635, 382/284, 382/294, 348/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 thereby creating a set of point matches;

computing a projective mapping between each pair of successive images using a least median squares technique which detects both false point matches and simultaneously estimates a homography matrix in order to determine corresponding pixel locations in the images, wherein said computing a projective mapping comprises,

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

(b) drawing m random subsamples of a specified number of at least four different point matches of said set of point matches;

(c) for each subsample J, computing a homograph 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₂₁−

{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 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

$\underset{i}{\sum <br><br>}<br><br>{<br><br>m_{2<br><br>i}-{\hat{m}}_{1<br><br>i}<br><br>}^2$

where the summation is over all good matches; and

(i) repeating process actions (a) through (h) until all images of the sequence of images have been processed; and

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

2. The computer-implemented process of claim 1 further comprising the process action of refining the homographies computed for the pairs of successive images through global optimization.

3. The computer-implemented process of claim 1 wherein the process action of acquiring an ordered sequence of images, comprises the process actions of:

capturing a first row of images by,

taking a first snapshot of the upper left corner of the planar object;

taking a second snapshot by pointing to the right of said first snapshot but having overlap with first snapshot;

taking a subsequent snapshot by pointing to the right of the previous snapshot but having an overlap with said previous snapshot;

continuing to take subsequent snapshots with overlap by pointing to the right of the previous snapshot until reaching the upper right corner of the planar object;

capturing a second row of images by,

moving the camera lower and taking with overlap a snapshot below the snapshot in the upper right corner;

taking another snapshot by pointing with overlap to the left of said snapshot below the snapshot in the upper right corner,

continuing to take subsequent snapshots by pointing with overlap to the left of the previous snapshot until reaching the left edge of the planar object;

continuing capturing snapshots in the manner of capturing the first and second rows starting with the portion of the planar object under but overlapping the portion of the planar object last captured until the entire lower border of the planar object is captured.

4. The computer-implemented process of claim 1 wherein the process action of acquiring an ordered sequence of images, comprises the process actions of:

capturing a first row of images by initially focusing the camera on an upper left corner of the planar object and continually capturing images while moving the camera in a left to right motion that ensures the overlap between successive images until the last capture image comprises the upper right corner of the planar object,

capturing a second row of images by moving the optical axis of the camera lower and focusing below but overlapping the portion captured in the last captured image and continuously capturing images while moving the camera in a right to left direction at a speed that ensures the overlap between successive images until the last capture image comprises the left edge of the planar object,

continuing capturing images in the manner of capturing the first and second rows starting with the portion of the planar object under but overlapping the last captured portion of the planar object until the entire last portion of the planar object is captured.

5. The computer-implemented process of claim 1 wherein extracting points of interest in each image comprises the process actions of:

defining the image under consideration as a three dimensional surface, having two displacement dimensions with a third dimension being the intensity

locating high curvature points in the intensity surface; and

designating said points corresponding to the high curvature points as the points of interest.

6. The computer-implemented process of claim 1 wherein said process action of generating a composite image comprises the process actions of:

using the first captured image as the reference frame of the final composite image;

successively registering said images in the order in which they were captured with the immediately previously captured image to said reference frame using the projective mapping computed between the pair of images under consideration; and

if a pixel in the reference frame appears several times in the original images, then retaining the pixel in the newest image.

7. The computer-implemented process of claim 1 for converting the contents of a planar object into a high-resolution image, wherein said planar object is a whiteboard.

8. The computer-implemented process of claim 1 for converting the contents of a planar object into a high-resolution image, wherein said planar object is a piece of paper.

9. 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 corrupting 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 thereby creating a set of point matches;

compute a projective mapping between each set of two successive images in said sequence of images using a east median squares technique which detects both false point matches and simultaneously estimates a homography matrix in order to determine corresponding pixel locations in the images of each set, therein said computing a projective mapping comprises,

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

(b) drawing m random subsamples of a specified number of at least four different point matches of said set of point matches;

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

(d) for each H_J, determining the median of th squared residuals, denoted by M_J, with respect to the whole set of point matches, where the squared residual for match j 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 a robust standard deviation estimated {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

$\underset{i}{\sum <br><br>}<br><br>{<br><br>m_{2<br><br>i}-{\hat{m}}_{1<br><br>i}<br><br>}^2$

where the summation is over all good matches; and

(i) repeating process actions (a) through (h) until all images of the sequence of images have been processed; and

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

10. The system of claim 9 further comprising a module for adjusting all of the homographies computed for said sets of two successive images through global optimization.

11. The system of claim 9 wherein the module for extracting points of interest in each image in the sequence comprises sub-modules for:

inputting an image;

locating corners corresponding to high curvature points in the intensity surface if defining said image as a three dimensional surface, defined by two displacement dimensions and a third dimension being the intensity; and

extracting said points corresponding to the corners as the points of interest.

12. The system of claim 9 wherein said module for generating a composite image comprises modules for:

using the first captured image as the reference frame of the final composite image;

successively registering said images in the order in which they were captured with the immediately previously captured image to said reference frame using the projective mapping computed between the pair of images under consideration; and

if a pixel in the reference frame appears several times in the original images, then retaining the one in the newest image.

13. 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 thereby creating a set of point matches;

using a least median squares technique which detects both false point matches and simultaneously estimates a homography matrix to calculate a homography between each image of said series of images with the image preceding said image in said series of images, wherein said calculating a homography comprises,

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

(b) drawing m random subsamples of a specified number of at least for different point matches of said set of 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 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 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

$\underset{i}{\sum <br><br>}<br><br>{<br><br>m_{2<br><br>i}-{\hat{m}}_{1<br><br>i}<br><br>}^2$

matches; and

(i) repeating process actions (a) through (h) until all images of the sequence of images have been processed; and

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

14. The computer-readable medium of claim 13 further comprising instructions for globally optimizing said homographies prior to stitching said images together.

15. The computer-readable medium of claim 13 wherein said instructions for extracting points of interest in each image comprises sub-instructions for:

defining the image under consideration as a three dimensional surface, having two displacement dimensions with a third dimension being the intensity

locating high curvature points in the intensity surface; and

designating said points corresponding to the high curvature points as the points of interest.

16. The computer-readable medium of claim 13 wherein said instruction for stitching said images together to create a composite image comprises sub-instructions for:

using the first image in said series of images as the reference frame of the final composite image;

successively matching said images in said series of images to said reference frame using said homographies to determine pixel location; and

if a pixel in the reference frame appears several times in the original images, then retaining the one in the newest image.

17. The computer-readable medium of claim 13 wherein the instruction for acquiring an ordered sequence of images, comprises sub-instructions for:

capturing a first row of images by,

taking a first snapshot of the lower right corner of the planar object;

taking a second snapshot by pointing to the left of said first snapshot but having overlap with first snapshot;

taking a subsequent snapshot by pointing to the left of the previous snapshot but having an overlap with said previous snapshot;

continuing to take subsequent snapshots with overlap by pointing to the left of the previous snapshot until reaching the lower left corner of the planar object;

capturing a second row of images by,

moving the camera higher and taking with overlap a snapshot above the snapshot in the lower left corner;

taking another snapshot by pointing with overlap to the right of said snapshot above the snapshot in the lower left corner,

continuing to take subsequent snapshots by pointing with overlap to the right of the previous snapshot until reaching the right edge of the planar object;

continuing capturing snapshots in the manner of capturing the first and second rows starting with the portion of the planar object above but overlapping the portion of the planar object last captured until the entire upper border of the planar object is captured.

18. The computer-readable medium of claim 13 wherein the instructions for acquiring an ordered sequence of images, comprises sub-instructions for:

capturing a first row of images by initially focusing the camera on an upper right corner of the planar object and continually capturing images while moving the camera in a right to left motion that ensures the overlap between successive images until the last capture image comprises the upper left corner of the planar object,

capturing a second row of images by moving the optical axis of the camera lower and focusing below but overlapping the portion captured in the last captured image and continuously capturing images while moving the camera in a left to right direction at a speed that ensures the overlap between successive images until the last capture image comprises the right edge of the planar object,

continuing capturing images in the manner of capturing the first and second rows stating with the portion of the planar object under but overlapping the last captured portion of the planar object until the entire last portion of the planar object is captured.

19. The computer-readable medium for converting a series of low resolution images of portions of a planar object into a high resolution image of said object of claim 13, wherein said planar object is a whiteboard.

20. The computer-readable medium for converting a series of low resolution images of portions of a planar object into a high resolution image of said object of claim 13, wherein said planar object is a piece of paper.