System and method for converting whiteboard content into an electronic document

• US 20040165786A1
• Filed: 02/22/2003
• Published: 08/26/2004
• Est. Priority Date: 02/22/2003
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: He, Li-Wei, Zhang, Zhengyou
• Granted Patent: US 7,171,056 B2
• Time in Patent Office: Days
• US Class Current: 382/276
• CPC Class Codes: G06T 2207/10016 Video; Image sequence
• CPC Class Codes: G06T 2207/20061 Hough transform
• CPC Class Codes: G06T 5/80 Geometric correction
• CPC Class Codes: G06T 7/12 Edge-based segmentation
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/146 Aligning or centring of the image pick-up or image-field
• CPC Class Codes: G06V 30/166 Normalisation of pattern dimensions
• CPC Class Codes: H04N 1/387 Composing, repositioning or otherwise geometrically modifying originals
• CPC Class Codes: H04N 1/4072 dependent on the contents of the original
• CPC Class Codes: H04N 1/6027 Correction or control of colour gradation or colour contrast H04N1/6058 takes precedence

Abstract

A system and method of converting the content of a regular whiteboard into an electronic document. This system and method provides an effective, economical and easy to use way to convert whiteboard content as an enhanced and easily editable electronic document though the use of a still or video camera. It uses a series of image processing steps to clip borders, rectify the whiteboard image and correct colors.

Claims

1. A process for converting the contents of a whiteboard into an electronic document, comprising the process actions of:

acquiring a digitized image of a whiteboard having four edges and content written thereon;

locating a quadrangle formed by the edges of the whiteboard in the image;

estimating the actual aspect ratio of the whiteboard from the quadrangle in the image; and

rectifying the quadrangle.

2. The process of claim 1 further comprising a process action of white-balancing the whiteboard background color to create a version of the image wherein the whiteboard background color is uniform.

3. The process of claim 2 further comprising the process action of increasing stroke saturation of strokes written on the whiteboard.

4. The process of claim 1 further comprising the process action of converting said image of the whiteboard content into vector equations describing the content of the whiteboard.

5. The process of claim 4 wherein said whiteboard content in vector equation format are processed using handwriting recognition procedures to provide an editable electronic document.

6. The process of claim 1 wherein said process action for locating the quadrangle in the image comprises the following process actions:

inputting said digitized image of said whiteboard;

detecting edges in the image;

locating straight lines in said image using said edges and a Hough transform; and

forming a quadrangle encompassing boundaries of the whiteboard using said straight lines.

7. The process of claim 6 further comprising the process action of verifying the formed quadrangle.

8. The process of claim 6 further comprising the process action of refining the quadrangle encompassing the whiteboard boundaries.

9. The process of claim 6 wherein said process action for detecting the edges of the whiteboard comprises the following process actions:

converting said image to grayscale if said image is a colored image;

for each pixel in said image,

using a Sobel filter to compute a gradient in the x direction and a gradient in the y direction;

computing an overall gradient by adding the gradient in the x direction and a gradient in the y direction and taking the absolute value; and

if said overall gradient is greater than a prescribed gradient threshold designating said pixel as an edge pixel.

10. The process of claim 9 wherein said prescribed gradient threshold is 40.

11. The process of claim 6 wherein said process action of locating straight lines in said image using a Hough transform comprises the process actions of:

dividing said image into cells;

inputting each edge, comprised of a series of edge pixels, detected and designating said edge as a line with an orientation;

if the said line crosses into a cell, assigning this cell a vote; and

once all edges have been processed, assigning all cells that have a significant number of votes as being a straight line.

12. The process of claim 11 wherein said cells that have greater than five percent of the total number of votes are assigned as being a straight line.

13. The process of claim 10 wherein said line is defined by the equation x₀ cos θ

+y₀ sin θ

=ρ and

wherein the range of angle θ

is [−

180°

, 180°

]; and

for a given edge at (x₀,y₀), its orientation is computed by θ

=a tan 2 (G_y, G_x) and its distance ρ

=x₀ cos θ

+y₀ sin θ

, where G_y, G_x are the gradients in the y and x directions, respectively.

14. The process of claim 13 wherein said process action of forming said quadrangle comprises the process actions of:

inputting sets of lines that have been identified as edges of a perspective quadrangle;

if opposite lines do not have opposite orientations, discarding said perspective quadrangle;

if opposite lines are not far from each other, discarding said perspective quadrangle;

if the angle between two neighboring lines is not close to plus or minus 90 degrees, discarding said perspective quadrangle;

if the orientation of said lines in said perspective quadrangle are not consistent in either a clockwise or counterclockwise direction, discarding said perspective quadrangle;

if the quadrangle circumference is not greater than a quarter of its width plus its height, discarding said perspective quadrangle; and

forming said quadrangle with said sets of lines if said perspective quadrangle was not previously discarded.

15. The process of claim 7 wherein the process action of verifying the quadrangle encompassing the whiteboard boundaries comprises the process actions of:

for each possible quadrangle,

inputting a perspective quadrangle formed from said straight lines;

counting the number of edges along each side;

calculating the circumference of said perspective quadrangle;

calculating the ratio of the number of edges to the circumference; and

retaining the quadrangle with the greatest ratio as the quadrangle encompassing the whiteboard boundaries.

16. The process of claim 1 wherein the process action for estimating the actual aspect ratio of the whiteboard from the quadrangle in the image comprises the process actions of:

for a rectangle with width and height of w and h and the coordinates of the four corners, M_i (i=1, . . . ,

     4)=(0,0), (w,0), (0,h), (w,h) in the plane coordinate system (z=0), whose projection of the rectangle in the image is a quadrangle with observed corners in the image are denoted by m₁, m₂, m₃, and m₄, respectively, and modeling the projection from a space point M to an image point m as λ

{tilde over (m)}=A[Rt]{tilde over (M)} where

$A=\left[\begin{array}{ccc}f& 0& u_0\\ 0& \mathrm{sf}& v_0\\ 0& 0& 1\end{array}\right]$

and R=[r₁ r₂ r₃] where ƒ

is the focal length of the camera, λ

is a scalar factor, s is the pixel ratio, A is a matrix of the camera parameters, u₀, v₀ are the coordinates of the image center, and (R, t) is the 3D transformation between the world coordinate system, in which the rectangle is described, and the camera coordinate system, {tilde over (x)} is used to denote the augmented x vector by adding 1 as the last element to vector x, i.e., {tilde over (x)}=[x₁, . . . x_n, 1]^T if x=[x₁, . . . x_n]^T

estimating the aspect ratio w/h of the whiteboard as the square root of

$\frac{n_2^T<br><br>A^{-T}<br><br>A^{-1}<br><br>n_2}{n_3^T<br><br>A^{-T}<br><br>A^{-1}<br><br>n_3}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{where}$$n_2=\frac{\left({\tilde{m}}_1\times <br><br>{\tilde{m}}_4\right)·<br><br>{\tilde{m}}_3}{\left({\tilde{m}}_2\times <br><br>{\tilde{m}}_4\right)·<br><br>{\tilde{m}}_3}<br><br>{\tilde{m}}_2-{\tilde{m}}_1<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{and}$$n_3=\frac{\left({\tilde{m}}_1\times <br><br>{\tilde{m}}_4\right)·<br><br>{\tilde{m}}_2}{\left({\tilde{m}}_2\times <br><br>{\tilde{m}}_4\right)·<br><br>{\tilde{m}}_2}<br><br>{\tilde{m}}_3-{\tilde{m}}_1.$

17. The process of claim 16 wherein the process action for rectifying the image comprises the process actions of:

determining the maximum of the upper and lower sides of the quadrangle;

determining the maximum of the left and right sides of the quadrangle;

calculating the ratio of the maximum of the upper and lower sides to the maximum of the left and right sides;

if the ratio of the maximum of the upper and lower sides to the maximum of the left and right sides is greater than the estimated aspect ratio, calculating the width of the rectified quadrangle as the maximum of the upper and lower sides of the quadrangle and the height of the rectified quadrangle as the width divided by the estimated aspect ratio;

if the ratio of the maximum of the upper and lower sides to the maximum of the left and right sides is less than the estimated aspect ratio, calculating the height of the rectified quadrangle as the maximum of the left and right sides of the quadrangle and the width of the rectified quadrangle as the estimated aspect ratio multiplied by the height;

computing a rectifying homography; and

mapping new pixel locations using said rectifying homography.

18. The process of claim 17 further comprising applying new colors to said rectified image.

19. The process of claim 18 wherein said applied new colors are computed by one of:

bilinear interpolation; and

bi-cubic interpolation.

20. The process of claim 2 wherein the wherein the white-balancing process action comprises:

estimating the background color of the whiteboard, wherein said background color is the whiteboard color under perfect lighting and without anything written on it;

making the whiteboard background uniformly white; and

increasing the color saturation of pen strokes written on said whiteboard.

21. The process of claim 20 further comprising the process action of reducing image noise prior to increasing the saturation of the pen strokes written on said whiteboard.

22. The process of claim 20 wherein the process action for estimating the background color of the whiteboard comprises the process actions of:

dividing the image of the whiteboard into rectangular cells;

sorting the pixels in each cell according to their luminance value; and

assigning the color with highest luminance in each cell as the whiteboard color of that cell.

23. The process of claim 22 further comprising the process action of filtering the colors of the cells to reject outlying color values.

24. The process of claim 23 wherein the process action of filtering the colors of the cells comprises:

locally fitting a plane in RGB space; and

rejecting outlying values and replacing them with interpolated values of neighboring cells.

25. The process of claim 20 wherein the process action for estimating the background color of the whiteboard comprises the process actions of:

dividing the image of the whiteboard into rectangular cells;

sorting the pixels in each cell according to their luminance value;

averaging the cells with a luminance value in the top 25 percent; and

assigning each cell the averaged luminance value.

26. The process of claim 25 further comprising the process action of filtering the colors of the cells to reject outlying values.

27. The process of claim 26 wherein the process action of filtering the colors of the cells comprises:

locally fitting a plane in RGB space; and

rejecting outlying values and replacing them with interpolated values of neighboring cells.

28. A system for converting markings on a planar object into an electronic document, 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 with camera a digital image of a four-sided planar object having content written thereon;

locate a quadrangle formed by the edges of the planar object in the image;

estimate the actual aspect ratio of the planar object from the quadrangle in the image;

rectify the planar object in the image; and

color-balance the background color of the planar object to produce a rectified and color-balanced version of the content of planar object.

29. The system of claim 28 further comprising a module for converting content written on the planar object into vectors.

30. The system of claim 29 wherein said vectors are processed using handwriting recognition procedures to provide an editable electronic document.

31. The system of claim 28 wherein said module for locating the quadrangle in the image comprises the following process actions:

inputting said image of said planar object;

detecting edges in the image;

locating straight lines in said image using said edges and a Hough transform; and

forming a quadrangle encompassing the boundaries of the planar object using said straight lines.

32. The system of claim 31 further comprising a module for verifying the formed quadrangle.

33. The system of claim 31 further comprising a module for refining the quadrangle encompassing the boundaries of the planar object.

34. The system of claim 31 wherein said module for detecting the edges of the planar object comprises sub-modules for:

converting said image to grayscale if said image is a colored image;

for each pixel in said image,

using a Sobel filter to compute a gradient in the x direction and a gradient in the y direction;

computing an overall gradient by taking the absolute value of the gradient in the x direction and a gradient in the y direction; and

if said overall gradient is greater than a prescribed gradient threshold designating said pixel as an edge.

35. The system of claim 31 wherein said module for locating straight lines in said image using a Hough transform comprises sub-modules for:

dividing said image into cells;

inputting each edge detected and considering it as a line with an orientation;

if the parameters of said line fall into a cell, assigning this cell a vote; and

once all edges have been processed, assigning all cells that have a significant number of votes as being a straight edge.

36. The system of claim 35 wherein said cells that have greater than five percent of the total number of votes are assigned as being a straight edge.

37. The system of claim 35 wherein said line is defined by the equation x₀ cos θ

+y₀ sin θ

=ρ and

wherein the range of angle θ

is [−

180°

, 180°

]; and

for a given edge at (x₀,y₀), its orientation is computed by θ

=a tan 2 (G_y, G_x) and its distance ρ

=x₀ cos θ

+y₀ sin θ

, where G_y, G_x are the gradients in the y and x directions, respectively.

38. The system of claim 35 wherein said module for forming said quadrangle comprises sub-modules for:

inputting sets of lines that have been identified as edges of a perspective quadrangle;

if opposite lines do not have opposite orientations, discarding said perspective quadrangle;

if opposite lines are not far from each other, discarding said perspective quadrangle;

if the angle between two neighboring lines is not close to plus or minus 90 degrees, discarding said perspective quadrangle;

if the orientation of said lines in said perspective quadrangle are not consistent in either a clockwise or counterclockwise direction, discarding said perspective quadrangle;

if the quadrangle circumference is not greater than a quarter of its width plus its height, discarding said perspective quadrangle; and

forming said quadrangle with said sets of lines is said perspective quadrangle is not previously discarded.

39. The system of claim 32 wherein the module for verifying the quadrangle encompassing the planar object'"'"'s boundaries comprises sub-modules for:

for each possible quadrangle,

inputting a perspective quadrangle formed from said straight lines;

counting the number of edges along each side;

calculating the circumference of said perspective quadrangle;

calculating the ratio of the number of edges to the circumference; and

retaining the quadrangle with the greatest ratio as the quadrangle encompassing the whiteboard boundaries.

40. The system of claim 28 wherein the module for estimating the actual aspect ratio of the planar object from the quadrangle in the image comprises sub-modules for:

for a planar object with width and height of w and h and the coordinates of the four corners, M_i(i=1, . . . ,

     4)=(0,0), (w,0), (0,h), (w,h) in the plane coordinate system (z=0), whose projection of the rectangle in the image is a quadrangle with observed corners in the image are denoted by m₁, m₂, m₃, and m₄, respectively, and modeling the projection from a space point M to an image point m as

$\mathrm{\lambda <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>\tilde{m}=A<br><br>\left[\mathrm{Rt}\right]<br><br>\tilde{M}$$\mathrm{where}<br><br>\text{\hspace{1em}<br><br>}<br><br>A=\left[\begin{array}{ccc}f& 0& u_0\\ 0& \mathrm{sf}& v_0\\ 0& 0& 1\end{array}\right]<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{and}$$R=\left[\begin{array}{ccc}{r}_1& r_2& r_3\end{array}\right]<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{where}<br><br>\text{\hspace{1em}<br><br>}<br><br>f<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{is}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{the}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{focal}$

length of the camera, λ

is a scalar factor, s is the pixel ratio, A is a matrix of the camera parameters, u₀, v₀ are the coordinates of the image center, and (R, t) is the 3D transformation between the world coordinate system, in which the rectangle is described, and the camera coordinate system, and {tilde over (x)} is used to denote the augmented x vector by adding 1 as the last element to vector x, i.e., {tilde over (x)}=[x₁, . . . x_n, 1]^T if x=[x₁, . . . x_n]^T

estimating the aspect ratio w/h of the planar object as the square root of

$\frac{n_2^T<br><br>A^{-T}<br><br>A^{-1}<br><br>n_2}{n_3^T<br><br>A^{-T}<br><br>A^{-1}<br><br>n_3}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{where}<br><br>\text{\hspace{1em}<br><br>}$$n_2=\frac{\left({\tilde{m}}_1\times <br><br>{\tilde{m}}_4\right)<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{•<br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>{\tilde{m}}_3}{\left({\tilde{m}}_2\times <br><br>{\tilde{m}}_4\right)<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{•<br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>{\tilde{m}}_3}<br><br>{\tilde{m}}_2-{\tilde{m}}_1<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{and}<br><br>\text{\hspace{1em}<br><br>}<br><br>n_3=\frac{\left({\tilde{m}}_1\times <br><br>{\tilde{m}}_4\right)<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{•<br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>{\tilde{m}}_2}{\left({\tilde{m}}_2\times <br><br>{\tilde{m}}_4\right)<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{•<br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>{\tilde{m}}_2}<br><br>{\tilde{m}}_3-{\tilde{m}}_1.$

41. The system of claim 40 wherein the module for rectifying the image comprises sub-modules for:

determining the maximum of the upper and lower sides of the quadrangle;

determining the maximum of the left and right sides of the quadrangle;

calculating the ratio of the maximum of the upper and lower sides to the maximum of the left and right sides;

if the ratio of the maximum of the upper and lower sides to the maximum of the left and right sides is greater than the estimated aspect ratio, calculating the width of the rectified quadrangle as the maximum of the upper and lower sides of the quadrangle and the height of the rectified quadrangle as the width divided by the estimated aspect ratio;

if the ratio of the maximum of the upper and lower sides to the maximum of the left and right sides is less than the estimated aspect ratio, calculating the height of the rectified quadrangle as the maximum of the left and right sides of the quadrangle and the width of the rectified quadrangle as the estimated aspect ratio multiplied by the height;

computing a rectifying homography;

mapping new pixel locations using said rectifying homography; and

applying new colors to the rectified quadrangle.

42. The system of claim 41 wherein said applied new colors are computed using one of:

bilinear interpolation; and

bi-cubic interpolation.

43. The system of claim 28 wherein the wherein the color-balancing module comprises sub-modules for:

estimating the background color of the planar object, wherein said background color is the background color under perfect lighting and without anything written on it;

making the planar object'"'"'s background uniformly colored; and

increasing the color saturation of pen strokes written on said planar object.

44. The system of claim 41 wherein the module for estimating the background color of the planar object comprises sub-modules for:

dividing the image of the planar object into rectangular cells;

sorting the pixels in each cell according to their luminance value; and

assigning the color with highest luminance in each cell as the background color of that cell.

45. The system of claim 44 further comprising a sub-module for filtering the background colors of the cells to reject outlying values.

46. The system of claim 43 wherein the module for estimating the background color of the planar object comprises sub-modules for:

dividing the image of the planar object into rectangular cells;

sorting the pixels in each cell according to their luminance value;

averaging the cells with a luminance value in the top 25 percent; and

assigning each cell the averaged luminance value.

47. The system of claim 43 wherein the module for making the background color uniformly colored comprises a sub-module for:

for each cell, using the estimated background color to scale each pixel color in the cell.

48. The system of claim 43 wherein the module increasing the color saturation of pen strokes written on said planar object, comprises a sub-module for:

for each pixel, remapping the value of each color channel according to an S-shaped curve.

49. The system of claim 28 wherein the four-sided planar object is a whiteboard.

50. The system of claim 28 wherein the four-sided planar object is a sheet of paper.

51. The system of claim 28 wherein the four-sided planar object is a poster.

53. The computer-readable medium of claim 47 further comprising a module for color-balancing the planar object'"'"'s background color to create a version of the image wherein the planar object'"'"'s background color is uniform.

52. A computer-readable medium having computer-executable instructions for converting the content of a whiteboard into an editable document, said computer executable instructions comprising modules for:

acquiring a digitized image of a planar object having four edges and content written thereon with a camera;

locating a quadrangle formed by the edges of the whiteboard in the image;

estimating the actual aspect ratio of the whiteboard from the quadrangle in the image; and

rectifying the quadrangle.

54. A process for estimating the actual aspect ratio of the planar object from the quadrangle in an image comprising the process actions of:

for a planar object with width and height of w and h and the coordinates of the four corners, M_i(i=1, . . . ,

     4)=(0,0), (w,0), (0,h), (w,h) in the plane coordinate system (z=0), whose projection of the rectangle in the image is a quadrangle with observed corners in the image are denoted by m₁, m₂, m₃, and m₄, respectively, and modeling the projection from a space point M to an image point m as λ

{tilde over (m)}=A[Rt]{tilde over (M)} where

$A=\left[\begin{array}{ccc}f& 0& u_0\\ 0& \mathrm{sf}& v_0\\ 0& 0& 1\end{array}\right]$

and R=[r₁ r₂ r₃] where ƒ

is the focal length of the camera, λ

is a scalar factor, s is the pixel ratio, A is a matrix of the camera parameters, u₀, v₀ are the coordinates of the image center, and (R, t) is the 3D transformation between the world coordinate system, in which the rectangle is described, and the camera coordinate system, {tilde over (x)} is used to denote the augmented x vector by adding 1 as the last element to vector x, i.e., {tilde over (x)}=[x₁, . . . x_n, 1]^T if x=[x₁, . . . x_n]^T, estimating the aspect ratio w/h of the planar object as the square root of

$\frac{n_2^T<br><br>A^{-T}<br><br>A^{-1}<br><br>n_2}{n_3^T<br><br>A^{-T}<br><br>A^{-1}<br><br>n_3}$

where n₂

$n_2=\frac{\left({\tilde{m}}_1\times <br><br>{\tilde{m}}_4\right)<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{•<br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>{\tilde{m}}_3}{\left({\tilde{m}}_2\times <br><br>{\tilde{m}}_4\right)<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{•<br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>{\tilde{m}}_3}<br><br>{\tilde{m}}_2-{\tilde{m}}_1$

and

$n_3=\frac{\left({\tilde{m}}_1\times <br><br>{\tilde{m}}_4\right)<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{•<br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>{\tilde{m}}_2}{\left({\tilde{m}}_2\times <br><br>{\tilde{m}}_4\right)<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{•<br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>{\tilde{m}}_2}<br><br>{\tilde{m}}_3-{\tilde{m}}_1.$