Direct homography computation by local linearization

• US 7,403,658 B2
• Filed: 04/15/2005
• Issued: 07/22/2008
• Est. Priority Date: 04/15/2005
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Dang, Yingnong, Chen, Liyong, Lin, Zhouchen, Wang, Jian
• Primary Examiner(s): Ahmed; Samir A.
• Assistant Examiner(s): Woldemariam; Aklilu k
• Application Number:
  US11/106,725
• Publication Number:
  US 20060232569A1
• Time in Patent Office: 1,194 Days
• Field of Search: 382/209
• US Class Current: 382/209
• CPC Class Codes: G06F 3/03545 Pens or stylus

Abstract

A method and apparatus for determining a homography between an image and an expected image is described. The homography accounts for differences in perspective of a camera viewing an objective plane of the image, in some examples, a paper with information on it.

Claims

1. A process for determining a homography matrix by processing an image containing codes, the process comprising the steps of:

extracting features from the image;

determining four candidates for main directions of parallel lines within the image;

identifying two pairs of near perpendicular directions from the four candidates;

determining two main directions from the two pairs of near perpendicular directions;

creating a homography matrix from the extracted features and from the two main directions, wherein the homography matrix is based on the parallel lines in the image, and the homography matrix attempts to minimize a distance between the features and the parallel lines;

wherein the codes are EIC codes arranged in EIC symbols, and the creating step attempts to minimize distance between lines and the EIC codes such that

$g<br><br>\left(H\right)=\frac{1}{2<br><br>N}<br><br>\underset{i=1}{\stackrel{m^h}{\sum <br><br>}}<br><br>\underset{j=1}{\stackrel{m_i^h}{\sum <br><br>}}<br><br>{{\mathrm{\gamma <br><br>}}_{\mathrm{ij}}^h<br><br>\left(x_{\mathrm{ij}}^h<br><br>c_i^h+y_{\mathrm{ij}}^h<br><br>s_i^h+R_i^h\right)}^2+\frac{1}{2<br><br>N}<br><br>\underset{i=1}{\stackrel{m^v}{\sum <br><br>}}<br><br>\underset{j=1}{\stackrel{m_i^v}{\sum <br><br>}}<br><br>{{\mathrm{\gamma <br><br>}}_{\mathrm{ij}}^v<br><br>\left(x_{\mathrm{ij}}^v<br><br>c_i^v+y_{\mathrm{ij}}^v<br><br>s_i^v+R_i^v\right)}^2$

is minimized where

$N=\underset{i=1}{\overset{m^h}{\sum <br><br>}}<br><br>m_i^h+\underset{i=1}{\overset{m^v}{\sum <br><br>}}<br><br>m_i^v,$

 

N is the total number of effective EIC pattern pixels associated with all the lines, and γ

_ij^h and γ

_ij^v are weights; and

wherein EICs are embedded interaction codes, H is a homography matrix, and each c_i, s_i, and R_i are coefficients defining straight lines defining the two main directions determined from the near perpendicular directions.

2. The process according to claim 1, said extracting features step includes determining the rotation of said image.

3. The process according to claim 1, said extracting features step includes determining the scale of said image.

4. The process according to claim 1, said extracting features step includes determining the translation of said image.

5. The process according to claim 1, wherein said codes are EIC codes.

6. The process according to claim 1, wherein said parallel lines are formed by collections of dots.

7. The process according to claim 1, wherein said homography matrix is represented by the form:

$H=\left(\begin{array}{ccc}{h}_{11}& h_{12}& h_{13}\\ h_{21}& h_{22}& h_{23}\\ h_{31}& h_{32}& h_{33}\end{array}\right).$

8. The process according to claim 1, wherein repeated computation is minimized by introduction of intermediate variables.

9. The process according to claim 1, wherein a number of terms of said homography matrix are zero.

10. The process according to claim 1, wherein terms differ at most by two variables.

11. A system for processing an image containing codes comprising:

an input receiving an image from a camera;

a processor that processes the image, the processor extracting features from the image and segmenting the features;

the processor determining four candidates for main directions of parallel lines within the image;

the processor identifying two pairs of near perpendicular directions from the four candidates;

the processor determining two main directions from the two pairs of near perpendicular directions;

and an output receiving an output from the processor, the output including a homography matrix, wherein the homography matrix is based on the parallel lines in the image from the camera, and the homography matrix attempting to minimize a distance between the parallel lines and the extracted features;

wherein the codes are EIC codes arranged in EIC symbols, and minimizing a distance attempts to minimize distance between lines and the EIC codes such that

$g<br><br>\left(H\right)=\frac{1}{2<br><br>N}<br><br>\underset{i=1}{\stackrel{m^h}{\sum <br><br>}}<br><br>\underset{j=1}{\stackrel{m_i^h}{\sum <br><br>}}<br><br>{{\mathrm{\gamma <br><br>}}_{\mathrm{ij}}^h<br><br>\left(x_{\mathrm{ij}}^h<br><br>c_i^h+y_{\mathrm{ij}}^h<br><br>s_i^h+R_i^h\right)}^2+\frac{1}{2<br><br>N}<br><br>\underset{i=1}{\stackrel{m^v}{\sum <br><br>}}<br><br>\underset{j=1}{\stackrel{m_i^v}{\sum <br><br>}}<br><br>{{\mathrm{\gamma <br><br>}}_{\mathrm{ij}}^v<br><br>\left(x_{\mathrm{ij}}^v<br><br>c_i^v+y_{\mathrm{ij}}^v<br><br>s_i^v+R_i^v\right)}^2$

is minimized where

$N=\underset{i=1}{\overset{m^h}{\sum <br><br>}}<br><br><br><br>m_i^h+\underset{i=1}{\overset{m^v}{\sum <br><br>}}<br><br><br><br>m_i^v,$

 

N is the total number of effective EIC pattern pixels associated with all the lines, and γ

_ij^h and γ

_ij^v are weights; and

wherein EICs are embedded interaction codes, H is a homography matrix, and each c_i, s_i, and R_i, are coefficients defining straight lines defining the two main directions determined from the near perpendicular directions.

12. The system according to claim 11, wherein said homography matrix is of the form of:

$H=\left(\begin{array}{ccc}{h}_{11}& h_{12}& h_{13}\\ h_{21}& h_{22}& h_{23}\\ h_{31}& h_{32}& h_{33}\end{array}\right).$

13. The system according to claim 11, wherein repeated computation is minimized by introduction of intermediate variables.

14. The system according to claim 11, wherein a number of terms of said homography matrix are zero.

15. The system according to claim 11, wherein terms of said homography matrix differ at most by two variables.

16. A process for determining a homography for a camera comprising the steps of:

obtaining an image having parallel lines;

determining four candidates for main directions of parallel lines within the image;

identifying two pairs of near perpendicular directions from the four candidates;

determining two main directions from the two pairs of near perpendicular directions;

determining a homography matrix for the camera, the homography matrix based on the parallel lines in the obtained image, where the homography matrix attempts to minimize a difference between the parallel lines in the obtained image and expected parallel lines; and

applying the homography matrix to the obtained image to adjust the obtained image.

17. The process according to claim 16, wherein said homography matrix is stored for different ranges of magnification.

18. The process according to claim 16, wherein said homography matrix is of the form:

$H=\left(\begin{array}{ccc}{h}_{11}& h_{12}& h_{13}\\ h_{21}& h_{22}& h_{23}\\ h_{31}& h_{32}& h_{33}\end{array}\right).$

19. The process according to claim 16, wherein repeated computation is minimized by introduction of intermediate variables.

20. The process according to claim 16, wherein a number of terms of said homography matrix are zero.

21. The process according to claim 16, wherein terms of said homography matrix differ at most by two variables.