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

• US 20040189674A1
• Filed: 03/31/2003
• Published: 09/30/2004
• Est. Priority Date: 03/31/2003
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Zhang, Zhengyou, He, Li-wei
• Granted Patent: US 7,119,816 B2
• Time in Patent Office: Days
• US Class Current: 345/629
• 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 a 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;

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 process action of computing a projective mapping further comprises a process action of:

determining and discarding erroneous matched points of interest in each pair of successive images as part of computing said projective mapping.

3. The computer-implemented process of claim 1 wherein the process action of computing said projective mapping comprises computing a homography between each pair of two successive images.

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

5. 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.

6. 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.

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

8. The computer-implemented process of claim 1 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 score 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.

9. The computer-implemented process 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 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 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 Σ

₁ ∥

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 the sequence of images have been processed.

11. The computer-implemented process of claim 10 wherein k=2.5.

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

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

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

13. 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 one in the newest image.

14. The computer-implemented process of claim 4 further comprising the process actions of:

for a total of N images, chosing a first image as the reference image for the global optimization and letting the 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)}_j'"'"'s by minimizing the errors between the expected positions of the reference points in the images and the observed reference points in the images.

15. The computer-implemented process of claim 14 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

16. 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.

17. 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.

18. 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;

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.

19. The system of claim 18 wherein the module for computing said projective mapping comprises a sub-module for computing a homography between each set of two successive images.

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

21. The system of claim 18 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.

22. The system of claim 18 wherein the 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 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.

23. The system of claim 18 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.

24. The system of claim 18 wherein said module for computing a projective mapping between each set of two successive images in said ordered sequence of image, 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}{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 the summation is over all good matches; and

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

25. The system of claim 24 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˜

for {tilde over (m)}=[u, v, 1]^T, such that {tilde over (m)}₂=λ

H{tilde over (m)}₁.

26. The system of claim 18 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 to 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.

27. 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 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;

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.

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

29. The computer-readable medium of claim 27 wherein said instructions for calculating a homography between each image of said series of images with the image preceding said image in said series of images comprises a sub-instructions for solving the nonlinear problem

30. The computer-readable medium of claim 27 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.

31. The computer-readable medium of claim 27 wherein the instructions for matching said points of interest in each image of said series of images with the image earlier captured image in said series of images comprises sub-instructions for:

for each point of interest in the earlier captured 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 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 score 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.

32. The computer-readable medium of claim 31 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.

33. The computer-readable medium of claim 27 wherein the instructions for matching said points of interest in each image of said series of images with the earlier captured image in said series of images comprises sub-instructions for:

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

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

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;

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;

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);

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;

chosing the homography estimation which corresponds to the largest number of matched points and the smallest RMS;

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<sub>i−

1</sub>, 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

repeating the above sub-instructions until all images of the set of original images are matched, and reporting the last estimated homography as the output.

34. The computer-readable medium of claim 33 wherein the instructions for refining said homography comprises sub-instructions for:

transforming the four image corners using H_i;

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 both 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_i;

matching the points using said defined search range; and

estimating the homography based on least-median-squares.

35. The computer-readable medium of claim 33 wherein the instruction for refining said homography comprises sub-instructions for:

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

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

H_i;

calculating the refined homography as Δ

H_iH_i.

36. The computer-readable medium of claim 27 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.

38. The computer-readable medium of claim 27 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.

39. The computer-readable medium of claim 27 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 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.

40. 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 27, wherein said planar object is a whiteboard.

41. 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 27, wherein said planar object is a piece of paper.

42. A graphical user interface for positioning a camera while capturing a series of images of portions of an object comprising:

a viewing region displaying a composition of a previously acquired image and a current image.

43. The graphical user interface of claim 42 wherein the viewing region displays half of the previously acquired image as opaque and half of the previously acquired image as semi-transparent;

and

wherein the current image overlaps the portion of the previously acquired image that is semi-transparent and the portion of the current image that overlaps the previously acquired image is also semi-transparent, while the non-overlapping portion of the current image is displayed as opaque.

44. The graphical user interface of claim 42 further comprising user-selectable buttons to move the camera to select different portions of said object when acquiring each image in said sequence of images.