Proportionen eines perspektivisch deformierten Rechtecks

StackOverflow https://stackoverflow.com/questions/1194352

Frage

Gegeben ist ein perspektivisch verzerrtes 2D-Bild eines Rechtecks:

enter image description here

Ich weiß, dass die Form ursprünglich ein Rechteck war, aber ich kenne die ursprüngliche Größe nicht.

Wenn ich die Pixelkoordinaten der Ecken in diesem Bild kenne, wie kann ich dann die ursprünglichen Proportionen berechnen, d. h.der Quotient (Breite/Höhe) des Rechtecks?

(Hintergrund:Das Ziel besteht darin, Fotos von rechteckigen Dokumenten automatisch zu entzerren. Die Kantenerkennung wird wahrscheinlich mit Hough Transform erfolgen.)

AKTUALISIEREN:

Es gibt einige Diskussionen darüber, ob es mit den gegebenen Informationen überhaupt möglich ist, das Breiten-Höhen-Verhältnis zu bestimmen.Mein naiver Gedanke war, dass es möglich sein muss, da mir keine Möglichkeit einfällt, beispielsweise ein 1:4-Rechteck auf das oben abgebildete Viereck zu projizieren.Das Verhältnis scheint eindeutig nahe bei 1:1 zu liegen, daher sollte es eine Möglichkeit geben, es mathematisch zu bestimmen.Ich habe jedoch keinen Beweis dafür, der über meine intuitive Vermutung hinausgeht.

Ich habe die unten dargelegten Argumente noch nicht vollständig verstanden, denke aber, dass es hier eine implizite Annahme geben muss, die uns fehlt und die unterschiedlich interpretiert wird.

Nach stundenlangem Suchen habe ich jedoch endlich einige Artikel gefunden, die für das Problem relevant sind.Ich habe Mühe, die darin verwendete Mathematik zu verstehen, bisher ohne Erfolg.Insbesondere der erste Artikel scheint genau zu besprechen, was ich tun wollte, leider ohne Codebeispiele und sehr umfangreiche Mathematik.

  • Zhengyou Zhang, Li-Wei He, „Whiteboard-Scannen und Bildverbesserung“http://research.microsoft.com/en-us/um/people/zhang/papers/tr03-39.pdf S.11

    „Aufgrund der perspektivischen Verzerrung erscheint das Bild eines Rechtecks ​​wie ein Viereck.Da wir jedoch wissen, dass es sich um ein Rechteck im Raum handelt, können wir sowohl die Brennweite der Kamera als auch das Seitenverhältnis des Rechtecks ​​abschätzen.“

  • ROBERT M.HARALICK „Bestimmung von Kameraparametern aus der perspektivischen Projektion eines Rechtecks“http://portal.acm.org/citation.cfm?id=87146

    „Wir zeigen, wie man die perspektivische 2D-Projektion eines Rechtecks ​​unbekannter Größe und Position im 3D-Raum nutzt, um die Blickwinkelparameter der Kamera relativ zu den Plänen des Rechtecks ​​zu bestimmen.“

War es hilfreich?

Lösung

Hier ist mein Versuch, meine Frage zu beantworten, nachdem ich den Artikel gelesen habe

Ich habe die Gleichungen einige Zeit in SAGE manipuliert und diesen Pseudocode im C-Stil erstellt:


// in case it matters: licensed under GPLv2 or later
// legend:
// sqr(x)  = x*x
// sqrt(x) = square root of x

// let m1x,m1y ... m4x,m4y be the (x,y) pixel coordinates
// of the 4 corners of the detected quadrangle
// i.e. (m1x, m1y) are the cordinates of the first corner, 
// (m2x, m2y) of the second corner and so on.
// let u0, v0 be the pixel coordinates of the principal point of the image
// for a normal camera this will be the center of the image, 
// i.e. u0=IMAGEWIDTH/2; v0 =IMAGEHEIGHT/2
// This assumption does not hold if the image has been cropped asymmetrically

// first, transform the image so the principal point is at (0,0)
// this makes the following equations much easier
m1x = m1x - u0;
m1y = m1y - v0;
m2x = m2x - u0;
m2y = m2y - v0;
m3x = m3x - u0;
m3y = m3y - v0;
m4x = m4x - u0;
m4y = m4y - v0;


// temporary variables k2, k3
double k2 = ((m1y - m4y)*m3x - (m1x - m4x)*m3y + m1x*m4y - m1y*m4x) /
            ((m2y - m4y)*m3x - (m2x - m4x)*m3y + m2x*m4y - m2y*m4x) ;

double k3 = ((m1y - m4y)*m2x - (m1x - m4x)*m2y + m1x*m4y - m1y*m4x) / 
            ((m3y - m4y)*m2x - (m3x - m4x)*m2y + m3x*m4y - m3y*m4x) ;

// f_squared is the focal length of the camera, squared
// if k2==1 OR k3==1 then this equation is not solvable
// if the focal length is known, then this equation is not needed
// in that case assign f_squared= sqr(focal_length)
double f_squared = 
    -((k3*m3y - m1y)*(k2*m2y - m1y) + (k3*m3x - m1x)*(k2*m2x - m1x)) / 
                      ((k3 - 1)*(k2 - 1)) ;

//The width/height ratio of the original rectangle
double whRatio = sqrt( 
    (sqr(k2 - 1) + sqr(k2*m2y - m1y)/f_squared + sqr(k2*m2x - m1x)/f_squared) /
    (sqr(k3 - 1) + sqr(k3*m3y - m1y)/f_squared + sqr(k3*m3x - m1x)/f_squared) 
) ;

// if k2==1 AND k3==1, then the focal length equation is not solvable 
// but the focal length is not needed to calculate the ratio.
// I am still trying to figure out under which circumstances k2 and k3 become 1
// but it seems to be when the rectangle is not distorted by perspective, 
// i.e. viewed straight on. Then the equation is obvious:
if (k2==1 && k3==1) whRatio = sqrt( 
    (sqr(m2y-m1y) + sqr(m2x-m1x)) / 
    (sqr(m3y-m1y) + sqr(m3x-m1x))


// After testing, I found that the above equations 
// actually give the height/width ratio of the rectangle, 
// not the width/height ratio. 
// If someone can find the error that caused this, 
// I would be most grateful.
// until then:
whRatio = 1/whRatio;

Aktualisieren:So wurden diese Gleichungen ermittelt:

Das Folgende ist Code in SALBEI.Es kann online abgerufen werden unter http://www.sagenb.org/home/pub/704/.(Sage ist wirklich nützlich beim Lösen von Gleichungen und kann in jedem Browser verwendet werden, schauen Sie es sich an)

# CALCULATING THE ASPECT RATIO OF A RECTANGLE DISTORTED BY PERSPECTIVE

#
# BIBLIOGRAPHY:
# [zhang-single]: "Single-View Geometry of A Rectangle 
#  With Application to Whiteboard Image Rectification"
#  by Zhenggyou Zhang
#  http://research.microsoft.com/users/zhang/Papers/WhiteboardRectification.pdf

# pixel coordinates of the 4 corners of the quadrangle (m1, m2, m3, m4)
# see [zhang-single] figure 1
m1x = var('m1x')
m1y = var('m1y')
m2x = var('m2x')
m2y = var('m2y')
m3x = var('m3x')
m3y = var('m3y')
m4x = var('m4x')
m4y = var('m4y')

# pixel coordinates of the principal point of the image
# for a normal camera this will be the center of the image, 
# i.e. u0=IMAGEWIDTH/2; v0 =IMAGEHEIGHT/2
# This assumption does not hold if the image has been cropped asymmetrically
u0 = var('u0')
v0 = var('v0')

# pixel aspect ratio; for a normal camera pixels are square, so s=1
s = var('s')

# homogenous coordinates of the quadrangle
m1 = vector ([m1x,m1y,1])
m2 = vector ([m2x,m2y,1])
m3 = vector ([m3x,m3y,1])
m4 = vector ([m4x,m4y,1])


# the following equations are later used in calculating the the focal length 
# and the rectangle's aspect ratio.
# temporary variables: k2, k3, n2, n3

# see [zhang-single] Equation 11, 12
k2_ = m1.cross_product(m4).dot_product(m3) / m2.cross_product(m4).dot_product(m3)
k3_ = m1.cross_product(m4).dot_product(m2) / m3.cross_product(m4).dot_product(m2)
k2 = var('k2')
k3 = var('k3')

# see [zhang-single] Equation 14,16
n2 = k2 * m2 - m1
n3 = k3 * m3 - m1


# the focal length of the camera.
f = var('f')
# see [zhang-single] Equation 21
f_ = sqrt(
         -1 / (
          n2[2]*n3[2]*s^2
         ) * (
          (
           n2[0]*n3[0] - (n2[0]*n3[2]+n2[2]*n3[0])*u0 + n2[2]*n3[2]*u0^2
          )*s^2 + (
           n2[1]*n3[1] - (n2[1]*n3[2]+n2[2]*n3[1])*v0 + n2[2]*n3[2]*v0^2
          ) 
         ) 
        )


# standard pinhole camera matrix
# see [zhang-single] Equation 1
A = matrix([[f,0,u0],[0,s*f,v0],[0,0,1]])


#the width/height ratio of the original rectangle
# see [zhang-single] Equation 20
whRatio = sqrt (
               (n2*A.transpose()^(-1) * A^(-1)*n2.transpose()) / 
               (n3*A.transpose()^(-1) * A^(-1)*n3.transpose())
              )

Die vereinfachten Gleichungen im C-Code wurden bestimmt durch

print "simplified equations, assuming u0=0, v0=0, s=1"
print "k2 := ", k2_
print "k3 := ", k3_
print "f  := ", f_(u0=0,v0=0,s=1)
print "whRatio := ", whRatio(u0=0,v0=0,s=1)

    simplified equations, assuming u0=0, v0=0, s=1
    k2 :=  ((m1y - m4y)*m3x - (m1x - m4x)*m3y + m1x*m4y - m1y*m4x)/((m2y
    - m4y)*m3x - (m2x - m4x)*m3y + m2x*m4y - m2y*m4x)
    k3 :=  ((m1y - m4y)*m2x - (m1x - m4x)*m2y + m1x*m4y - m1y*m4x)/((m3y
    - m4y)*m2x - (m3x - m4x)*m2y + m3x*m4y - m3y*m4x)
    f  :=  sqrt(-((k3*m3y - m1y)*(k2*m2y - m1y) + (k3*m3x - m1x)*(k2*m2x
    - m1x))/((k3 - 1)*(k2 - 1)))
    whRatio :=  sqrt(((k2 - 1)^2 + (k2*m2y - m1y)^2/f^2 + (k2*m2x -
    m1x)^2/f^2)/((k3 - 1)^2 + (k3*m3y - m1y)^2/f^2 + (k3*m3x -
    m1x)^2/f^2))

print "Everything in one equation:"
print "whRatio := ", whRatio(f=f_)(k2=k2_,k3=k3_)(u0=0,v0=0,s=1)

    Everything in one equation:
    whRatio :=  sqrt(((((m1y - m4y)*m2x - (m1x - m4x)*m2y + m1x*m4y -
    m1y*m4x)/((m3y - m4y)*m2x - (m3x - m4x)*m2y + m3x*m4y - m3y*m4x) -
    1)*(((m1y - m4y)*m3x - (m1x - m4x)*m3y + m1x*m4y - m1y*m4x)/((m2y -
    m4y)*m3x - (m2x - m4x)*m3y + m2x*m4y - m2y*m4x) - 1)*(((m1y -
    m4y)*m3x - (m1x - m4x)*m3y + m1x*m4y - m1y*m4x)*m2y/((m2y - m4y)*m3x
    - (m2x - m4x)*m3y + m2x*m4y - m2y*m4x) - m1y)^2/((((m1y - m4y)*m2x -
    (m1x - m4x)*m2y + m1x*m4y - m1y*m4x)*m3y/((m3y - m4y)*m2x - (m3x -
    m4x)*m2y + m3x*m4y - m3y*m4x) - m1y)*(((m1y - m4y)*m3x - (m1x -
    m4x)*m3y + m1x*m4y - m1y*m4x)*m2y/((m2y - m4y)*m3x - (m2x - m4x)*m3y
    + m2x*m4y - m2y*m4x) - m1y) + (((m1y - m4y)*m2x - (m1x - m4x)*m2y +
    m1x*m4y - m1y*m4x)*m3x/((m3y - m4y)*m2x - (m3x - m4x)*m2y + m3x*m4y
    - m3y*m4x) - m1x)*(((m1y - m4y)*m3x - (m1x - m4x)*m3y + m1x*m4y -
    m1y*m4x)*m2x/((m2y - m4y)*m3x - (m2x - m4x)*m3y + m2x*m4y - m2y*m4x)
    - m1x)) + (((m1y - m4y)*m2x - (m1x - m4x)*m2y + m1x*m4y -
    m1y*m4x)/((m3y - m4y)*m2x - (m3x - m4x)*m2y + m3x*m4y - m3y*m4x) -
    1)*(((m1y - m4y)*m3x - (m1x - m4x)*m3y + m1x*m4y - m1y*m4x)/((m2y -
    m4y)*m3x - (m2x - m4x)*m3y + m2x*m4y - m2y*m4x) - 1)*(((m1y -
    m4y)*m3x - (m1x - m4x)*m3y + m1x*m4y - m1y*m4x)*m2x/((m2y - m4y)*m3x
    - (m2x - m4x)*m3y + m2x*m4y - m2y*m4x) - m1x)^2/((((m1y - m4y)*m2x -
    (m1x - m4x)*m2y + m1x*m4y - m1y*m4x)*m3y/((m3y - m4y)*m2x - (m3x -
    m4x)*m2y + m3x*m4y - m3y*m4x) - m1y)*(((m1y - m4y)*m3x - (m1x -
    m4x)*m3y + m1x*m4y - m1y*m4x)*m2y/((m2y - m4y)*m3x - (m2x - m4x)*m3y
    + m2x*m4y - m2y*m4x) - m1y) + (((m1y - m4y)*m2x - (m1x - m4x)*m2y +
    m1x*m4y - m1y*m4x)*m3x/((m3y - m4y)*m2x - (m3x - m4x)*m2y + m3x*m4y
    - m3y*m4x) - m1x)*(((m1y - m4y)*m3x - (m1x - m4x)*m3y + m1x*m4y -
    m1y*m4x)*m2x/((m2y - m4y)*m3x - (m2x - m4x)*m3y + m2x*m4y - m2y*m4x)
    - m1x)) - (((m1y - m4y)*m3x - (m1x - m4x)*m3y + m1x*m4y -
    m1y*m4x)/((m2y - m4y)*m3x - (m2x - m4x)*m3y + m2x*m4y - m2y*m4x) -
    1)^2)/((((m1y - m4y)*m2x - (m1x - m4x)*m2y + m1x*m4y -
    m1y*m4x)/((m3y - m4y)*m2x - (m3x - m4x)*m2y + m3x*m4y - m3y*m4x) -
    1)*(((m1y - m4y)*m3x - (m1x - m4x)*m3y + m1x*m4y - m1y*m4x)/((m2y -
    m4y)*m3x - (m2x - m4x)*m3y + m2x*m4y - m2y*m4x) - 1)*(((m1y -
    m4y)*m2x - (m1x - m4x)*m2y + m1x*m4y - m1y*m4x)*m3y/((m3y - m4y)*m2x
    - (m3x - m4x)*m2y + m3x*m4y - m3y*m4x) - m1y)^2/((((m1y - m4y)*m2x -
    (m1x - m4x)*m2y + m1x*m4y - m1y*m4x)*m3y/((m3y - m4y)*m2x - (m3x -
    m4x)*m2y + m3x*m4y - m3y*m4x) - m1y)*(((m1y - m4y)*m3x - (m1x -
    m4x)*m3y + m1x*m4y - m1y*m4x)*m2y/((m2y - m4y)*m3x - (m2x - m4x)*m3y
    + m2x*m4y - m2y*m4x) - m1y) + (((m1y - m4y)*m2x - (m1x - m4x)*m2y +
    m1x*m4y - m1y*m4x)*m3x/((m3y - m4y)*m2x - (m3x - m4x)*m2y + m3x*m4y
    - m3y*m4x) - m1x)*(((m1y - m4y)*m3x - (m1x - m4x)*m3y + m1x*m4y -
    m1y*m4x)*m2x/((m2y - m4y)*m3x - (m2x - m4x)*m3y + m2x*m4y - m2y*m4x)
    - m1x)) + (((m1y - m4y)*m2x - (m1x - m4x)*m2y + m1x*m4y -
    m1y*m4x)/((m3y - m4y)*m2x - (m3x - m4x)*m2y + m3x*m4y - m3y*m4x) -
    1)*(((m1y - m4y)*m3x - (m1x - m4x)*m3y + m1x*m4y - m1y*m4x)/((m2y -
    m4y)*m3x - (m2x - m4x)*m3y + m2x*m4y - m2y*m4x) - 1)*(((m1y -
    m4y)*m2x - (m1x - m4x)*m2y + m1x*m4y - m1y*m4x)*m3x/((m3y - m4y)*m2x
    - (m3x - m4x)*m2y + m3x*m4y - m3y*m4x) - m1x)^2/((((m1y - m4y)*m2x -
    (m1x - m4x)*m2y + m1x*m4y - m1y*m4x)*m3y/((m3y - m4y)*m2x - (m3x -
    m4x)*m2y + m3x*m4y - m3y*m4x) - m1y)*(((m1y - m4y)*m3x - (m1x -
    m4x)*m3y + m1x*m4y - m1y*m4x)*m2y/((m2y - m4y)*m3x - (m2x - m4x)*m3y
    + m2x*m4y - m2y*m4x) - m1y) + (((m1y - m4y)*m2x - (m1x - m4x)*m2y +
    m1x*m4y - m1y*m4x)*m3x/((m3y - m4y)*m2x - (m3x - m4x)*m2y + m3x*m4y
    - m3y*m4x) - m1x)*(((m1y - m4y)*m3x - (m1x - m4x)*m3y + m1x*m4y -
    m1y*m4x)*m2x/((m2y - m4y)*m3x - (m2x - m4x)*m3y + m2x*m4y - m2y*m4x)
    - m1x)) - (((m1y - m4y)*m2x - (m1x - m4x)*m2y + m1x*m4y -
    m1y*m4x)/((m3y - m4y)*m2x - (m3x - m4x)*m2y + m3x*m4y - m3y*m4x) -
    1)^2))



# some testing:
# - choose a random rectangle, 
# - project it onto a random plane,
# - insert the corners in the above equations,
# - check if the aspect ratio is correct.

from sage.plot.plot3d.transform import rotate_arbitrary

#redundandly random rotation matrix
rand_rotMatrix = \
           rotate_arbitrary((uniform(-5,5),uniform(-5,5),uniform(-5,5)),uniform(-5,5)) *\
           rotate_arbitrary((uniform(-5,5),uniform(-5,5),uniform(-5,5)),uniform(-5,5)) *\
           rotate_arbitrary((uniform(-5,5),uniform(-5,5),uniform(-5,5)),uniform(-5,5))

#random translation vector
rand_transVector = vector((uniform(-10,10),uniform(-10,10),uniform(-10,10))).transpose()

#random rectangle parameters
rand_width =uniform(0.1,10)
rand_height=uniform(0.1,10)
rand_left  =uniform(-10,10)
rand_top   =uniform(-10,10)

#random focal length and principal point
rand_f  = uniform(0.1,100)
rand_u0 = uniform(-100,100)
rand_v0 = uniform(-100,100)

# homogenous standard pinhole projection, see [zhang-single] Equation 1
hom_projection = A * rand_rotMatrix.augment(rand_transVector)

# construct a random rectangle in the plane z=0, then project it randomly 
rand_m1hom = hom_projection*vector((rand_left           ,rand_top            ,0,1)).transpose()
rand_m2hom = hom_projection*vector((rand_left           ,rand_top+rand_height,0,1)).transpose()
rand_m3hom = hom_projection*vector((rand_left+rand_width,rand_top            ,0,1)).transpose()
rand_m4hom = hom_projection*vector((rand_left+rand_width,rand_top+rand_height,0,1)).transpose()

#change type from 1x3 matrix to vector
rand_m1hom = rand_m1hom.column(0)
rand_m2hom = rand_m2hom.column(0)
rand_m3hom = rand_m3hom.column(0)
rand_m4hom = rand_m4hom.column(0)

#normalize
rand_m1hom = rand_m1hom/rand_m1hom[2]
rand_m2hom = rand_m2hom/rand_m2hom[2]
rand_m3hom = rand_m3hom/rand_m3hom[2]
rand_m4hom = rand_m4hom/rand_m4hom[2]

#substitute random values for f, u0, v0
rand_m1hom = rand_m1hom(f=rand_f,s=1,u0=rand_u0,v0=rand_v0)
rand_m2hom = rand_m2hom(f=rand_f,s=1,u0=rand_u0,v0=rand_v0)
rand_m3hom = rand_m3hom(f=rand_f,s=1,u0=rand_u0,v0=rand_v0)
rand_m4hom = rand_m4hom(f=rand_f,s=1,u0=rand_u0,v0=rand_v0)

# printing the randomly choosen values
print "ground truth: f=", rand_f, "; ratio=", rand_width/rand_height

# substitute all the variables in the equations:
print "calculated: f= ",\
f_(k2=k2_,k3=k3_)(s=1,u0=rand_u0,v0=rand_v0)(
  m1x=rand_m1hom[0],m1y=rand_m1hom[1],
  m2x=rand_m2hom[0],m2y=rand_m2hom[1],
  m3x=rand_m3hom[0],m3y=rand_m3hom[1],
  m4x=rand_m4hom[0],m4y=rand_m4hom[1],
),"; 1/ratio=", \
1/whRatio(f=f_)(k2=k2_,k3=k3_)(s=1,u0=rand_u0,v0=rand_v0)(
  m1x=rand_m1hom[0],m1y=rand_m1hom[1],
  m2x=rand_m2hom[0],m2y=rand_m2hom[1],
  m3x=rand_m3hom[0],m3y=rand_m3hom[1],
  m4x=rand_m4hom[0],m4y=rand_m4hom[1],
)

print "k2 = ", k2_(
  m1x=rand_m1hom[0],m1y=rand_m1hom[1],
  m2x=rand_m2hom[0],m2y=rand_m2hom[1],
  m3x=rand_m3hom[0],m3y=rand_m3hom[1],
  m4x=rand_m4hom[0],m4y=rand_m4hom[1],
), "; k3 = ", k3_(
  m1x=rand_m1hom[0],m1y=rand_m1hom[1],
  m2x=rand_m2hom[0],m2y=rand_m2hom[1],
  m3x=rand_m3hom[0],m3y=rand_m3hom[1],
  m4x=rand_m4hom[0],m4y=rand_m4hom[1],
)

# ATTENTION: testing revealed, that the whRatio 
# is actually the height/width ratio, 
# not the width/height ratio
# This contradicts [zhang-single]
# if anyone can find the error that caused this, I'd be grateful

    ground truth: f= 72.1045134124554 ; ratio= 3.46538779959142
    calculated: f=  72.1045134125 ; 1/ratio= 3.46538779959
    k2 =  0.99114614987 ; k3 =  1.57376280159

Andere Tipps

Aktualisieren

Nachdem ich Ihr Update gelesen und mir die erste Referenz (Whiteboard-Scannen und Bildverbesserung) angesehen habe, sehe ich, wo der fehlende Punkt liegt.

Die Eingabedaten des Problems sind ein Vierfach (A, B, C, D), UND die Mitte O des projizierten Bildes.Im Artikel entspricht es der Annahme u0=v0=0.Durch Hinzufügen dieses Punktes wird das Problem ausreichend eingeschränkt, um das Seitenverhältnis des Rechtecks ​​zu ermitteln.

Das Problem wird dann wie folgt umformuliert:Gegeben sei ein Quadrupel (A,B,C,D) in der Z=0-Ebene. Finden Sie die Augenposition E(0,0,h), h>0 und eine 3D-Ebene P, so dass die Projektion von (A,B, C,D) auf P ist ein Rechteck.

Beachten Sie, dass P durch E bestimmt wird:Um ein Parallelogramm zu erhalten, muss P Parallelen zu (EU) und (EV) enthalten, wobei U=(AB)x(CD) und V=(AD)x(BC).

Experimentell scheint es, dass dieses Problem im Allgemeinen eine eindeutige Lösung hat, die einem eindeutigen Wert des B/H-Verhältnisses des Rechtecks ​​entspricht.

alt text alt text

Vorherigen Post

Nein, aus der Projektion lässt sich das Rechteckverhältnis nicht ermitteln.

Im allgemeinen Fall ist ein Quadrupel (A,B,C,D) von vier nicht kollinearen Punkten der Z=0-Ebene die Projektion unendlich vieler Rechtecke mit unendlich vielen Breiten-/Höhenverhältnissen.

Betrachten Sie die beiden Fluchtpunkte U, Schnittpunkt von (AB) und (CD) und V, Schnittpunkt von (AD) und (BC), und den Punkt I, Schnittpunkt der beiden Diagonalen (AC) und (BD).Um als ABCD zu projizieren, muss ein Parallelogramm des Mittelpunkts I auf einer Ebene liegen, die die Linie parallel zu (UV) durch Punkt I enthält.Auf einer solchen Ebene finden Sie viele Rechtecke, die nach ABCD projizieren, alle mit einem unterschiedlichen Breiten-/Höhenverhältnis.

Sehen Sie sich diese beiden mit Cabri 3D erstellten Bilder an.In beiden Fällen bleibt ABCD unverändert (auf der grauen Z=0-Ebene), und die blaue Ebene, die das Rechteck enthält, wird ebenfalls nicht verändert.Die teilweise verdeckte grüne Linie ist die (UV)-Linie und die sichtbare grüne Linie verläuft parallel dazu und enthält I.

alt text alt text

Die Größe ist nicht unbedingt erforderlich, ebenso wenig wie die Proportionen.Und zu wissen, welche Seite oben ist, ist irgendwie irrelevant, wenn man bedenkt, dass er Fotos/Scans von Dokumenten verwendet.Ich bezweifle, dass er die Rückseiten scannen wird.

„Eckenschnittpunkt“ ist die Methode zur Korrektur der Perspektive.Das könnte hilfreich sein:

So zeichnen Sie ein perspektivisch korrektes Raster in 2D

Zur Frage, warum die Ergebnisse h/w statt w/h ergeben:Ich frage mich, ob der Ausdruck der Gleichung 20 oben korrekt ist.Gepostet ist:

       whRatio = sqrt (
            (n2*A.transpose()^(-1) * A^(-1)*n2.transpose()) / 
            (n3*A.transpose()^(-1) * A^(-1)*n3.transpose())
           )

Wenn ich versuche, das mit OpenCV auszuführen, erhalte ich eine Ausnahme.Aber alles funktioniert richtig, wenn ich die folgende Gleichung verwende, die für mich eher wie Gleichung 20 aussieht:Basierend auf Gleichung 20 sieht es jedoch so aus:

        whRatio = sqrt (
            (n2.transpose()*A.transpose()^(-1) * A^(-1)*n2) /
            (n3.transpose()*A.transpose()^(-1) * A^(-1)*n3)
           )

Anhand dieser Antwort können Sie die Breite/Höhe bestimmen Berechnen Sie die 3D-Koordinate eines Rechtecks ​​mit der Koordinate seines Schattens?.Nehmen Sie an, dass sich Ihr Rechteck am diagonalen Schnittpunkt dreht und berechnen Sie dessen Breite und Höhe.Wenn Sie jedoch den Abstand zwischen der angenommenen Schattenebene und der tatsächlichen Schattenebene proportional zum Rechteck ändern, ist dies dasselbe wie bei der berechneten Breite/Höhe!

Es ist unmöglich, die Breite dieses Rechtecks ​​zu kennen, ohne den Abstand der „Kamera“ zu kennen.

Ein kleines Rechteck sieht aus einer Entfernung von 5 Zentimetern genauso aus wie ein riesiges Rechteck aus einer Entfernung von mehreren Metern

Zeichnen Sie ein rechtwinkliges gleichschenkliges Dreieck mit diesen beiden Fluchtpunkten und einem dritten Punkt unterhalb des Horizonts (d. h. auf derselben Seite des Horizonts wie das Rechteck).Dieser dritte Punkt wird unser Ursprung sein und die beiden Linien zu den Fluchtpunkten werden unsere Achsen sein.Nennen Sie den Abstand vom Ursprung zu einem Fluchtpunkt pi/2.Verlängern Sie nun die Seiten des Rechtecks ​​von den Fluchtpunkten zu den Achsen und markieren Sie, wo sie die Achsen schneiden.Wählen Sie eine Achse, messen Sie die Abstände zwischen den beiden Markierungen und dem Ursprung und transformieren Sie diese Abstände:x->tan(x), und die Differenz ist die „wahre“ Länge dieser Seite.Machen Sie dasselbe für die andere Achse.Nehmen Sie das Verhältnis dieser beiden Längen und fertig.

Sie benötigen weitere Informationen, diese transformierte Figur könnte aus jedem Parallelogramm aus einer beliebigen Perspektive stammen.

Ich vermute also, dass Sie zuerst eine Art Kalibrierung durchführen müssen.

Bearbeiten: Für diejenigen, die gesagt haben, dass ich falsch lag, hier der mathematische Beweis, dass es unendlich viele Kombinationen von Rechtecken/Kameras gibt, die zu derselben Projektion führen:

Um das Problem zu vereinfachen (da wir nur das Seitenverhältnis benötigen), nehmen wir an, dass unser Rechteck durch die folgenden Punkte definiert ist: R=[(0,0),(1,0),(1,r),(0,r)] (Diese Vereinfachung ist dasselbe wie die Transformation eines beliebigen Problems in ein äquivalentes Problem in einem affinen Raum.)

Das transformierte Polygon ist definiert als: T=[(tx0,ty0),(tx1,ty1),(tx2,ty2),(tx3,ty3)]

Es existiert eine Transformationsmatrix M = [[m00,m01,m02],[m10,m11,m12],[m20,m21,m22]] das befriedigt (Rxi,Ryi,1)*M=wi(txi,tyi,1)'

Wenn wir die obige Gleichung für die Punkte erweitern,

für R_0 wir bekommen: m02-tx0*w0 = m12-ty0*w0 = m22-w0 = 0

für R_1 wir bekommen: m00-tx1*w1 = m10-ty1*w1 = m20+m22-w1 = 0

für R_2 wir bekommen: m00+r*m01-tx2*w2 = m10+r*m11-ty2*w2 = m20+r*m21+m22-w2 = 0

und für R_3 wir bekommen: m00+r*m01-tx3*w3 = m10+r*m11-ty3*w3 = m20 + r*m21 + m22 -w3 = 0

Bisher haben wir 12 Gleichungen, 14 unbekannte Variablen (9 aus der Matrix, 4 aus der wi, und 1 für das Verhältnis r) und der Rest sind bekannte Werte (txi Und tyi sind gegeben).

Selbst wenn das System nicht unterspezifiziert wäre, werden einige der Unbekannten untereinander multipliziert (r Und mi0 Produkte), wodurch das System nichtlinear wird (Sie könnten es in ein lineares System umwandeln, indem Sie jedem Produkt einen neuen Namen zuweisen, aber Sie erhalten immer noch 13 Unbekannte, von denen 3 zu unendlichen Lösungen erweitert werden).

Wenn Sie einen Fehler in der Argumentation oder der Mathematik finden, lassen Sie es mich bitte wissen.

Dropbox hat in seinem Tech-Blog einen ausführlichen Artikel veröffentlicht, in dem beschrieben wird, wie sie das Problem für ihre Scanner-App gelöst haben.

https://blogs.dropbox.com/tech/2016/08/fast-document-rectification-and-enhancement/

Berichtigung eines Dokuments

Wir gehen davon aus, dass das Eingabedokument in der physischen Welt rechteckig ist. Wenn es jedoch nicht genau der Kamera zugewandt ist, sind die resultierenden Ecken im Bild im Allgemeinen ein konvexes Viereck.Um unser erstes Ziel zu erreichen, müssen wir die durch den Erfassungsprozess angewendete geometrische Transformation rückgängig machen.Diese Transformation hängt vom Blickwinkel der Kamera relativ zum Dokument ab (dies sind die sogenannten extrinsischen Parameter) sowie von Dingen wie der Brennweite der Kamera (den intrinsischen Parametern).Hier ist ein Diagramm des Erfassungsszenarios:

Um die geometrische Transformation rückgängig zu machen, müssen wir zunächst die genannten Parameter bestimmen.Wenn wir von einer schön symmetrischen Kamera ausgehen (kein Astigmatismus, kein Versatz usw.), sind die Unbekannten in diesem Modell:

  • die 3D-Position der Kamera relativ zum Dokument (3 Freiheitsgrade),
  • die 3D-Ausrichtung der Kamera relativ zum Dokument (3 Freiheitsgrade),
  • die Abmessungen des Dokuments (2 Freiheitsgrade) und
  • die Brennweite der Kamera (1 Freiheitsgrad).

Auf der anderen Seite liefern uns die x- und y-Koordinaten der vier erkannten Dokumentecken effektiv acht Einschränkungen.Obwohl es scheinbar mehr Unbekannte (9) als Einschränkungen (8) gibt, sind die Unbekannten keine völlig freien Variablen – man könnte sich vorstellen, das Dokument physisch zu skalieren und weiter von der Kamera entfernt zu platzieren, um ein identisches Foto zu erhalten.Diese Beziehung stellt eine zusätzliche Einschränkung dar, sodass wir ein vollständig eingeschränktes System haben, das gelöst werden muss.(Das tatsächliche Gleichungssystem, das wir lösen, beinhaltet einige andere Überlegungen;Der entsprechende Wikipedia-Artikel gibt eine gute Zusammenfassung: https://en.wikipedia.org/wiki/Camera_resectioning)

Sobald die Parameter wiederhergestellt wurden, können wir die durch den Erfassungsprozess angewendete geometrische Transformation rückgängig machen, um ein schönes rechteckiges Bild zu erhalten.Dies ist jedoch möglicherweise ein zeitaufwändiger Prozess:Man würde für jedes Ausgabepixel den Wert des entsprechenden Eingabepixels im Quellbild nachschlagen.Natürlich sind GPUs speziell für Aufgaben wie diese konzipiert:Rendern einer Textur in einem virtuellen Raum.Es gibt eine Ansichtstransformation – die zufälligerweise die Umkehrung der Kameratransformation ist, die wir gerade gelöst haben! –, mit der man das vollständige Eingabebild rendern und das entzerrte Dokument erhalten kann.(Eine einfache Möglichkeit, dies zu erkennen, besteht darin, zu beachten, dass Sie, sobald Sie das vollständige Eingabebild auf dem Bildschirm Ihres Telefons haben, das Telefon neigen und verschieben können, sodass die Projektion des Dokumentbereichs auf dem Bildschirm für Sie geradlinig erscheint.)

Erinnern Sie sich abschließend daran, dass hinsichtlich des Maßstabs Unklarheiten bestanden:Wir können beispielsweise nicht sagen, ob es sich bei dem Dokument um ein Papier im Letter-Format (8,5 x 11 Zoll) oder um eine Postertafel (17 x 22 Zoll) handelte.Welche Abmessungen sollte das Ausgabebild haben?Um diese Mehrdeutigkeit aufzulösen, zählen wir die Anzahl der Pixel innerhalb des Vierecks im Eingabebild und stellen die Ausgabeauflösung so ein, dass sie dieser Pixelanzahl entspricht.Die Idee ist, dass wir das Bild nicht zu sehr hochskalieren oder herunterskalieren wollen.

Es scheint immer noch einige Verwirrung zu diesem interessanten Problem zu herrschen.Ich möchte eine leicht verständliche Erklärung geben, wann das Problem gelöst werden kann und wann nicht.

Einschränkungen und Freiheitsgrade

Wenn wir mit einem Problem wie diesem konfrontiert werden, müssen wir normalerweise zunächst die Anzahl der unbekannten Freiheitsgrade (DoFs) N und die Anzahl der unabhängigen Gleichungen M ermitteln, die wir zur Einschränkung der unbekannten Freiheitsgrade haben.Es ist unmöglich, das Problem zu lösen, wenn N größer als M ist (was bedeutet, dass es weniger Einschränkungen als Unbekannte gibt).Alle Probleme, bei denen dies der Fall ist, können wir als unlösbar ausschließen.Wenn N M nicht überschreitet, dann ist es Mai Es kann zwar möglich sein, das Problem mit einer eindeutigen Lösung zu lösen, dies ist jedoch nicht garantiert (ein Beispiel finden Sie im vorletzten Absatz).

Lasst uns verwenden P1, P2, P3 und P4, um die Positionen der 4 Ecken der ebenen Oberfläche in Weltkoordinaten anzugeben.Lasst uns verwenden R Und T um die 3D-Rotation und -Translation zu sein, die diese in Kamerakoordinaten umwandelt.Lasst uns verwenden K um die intrinsische 3x3-Kameramatrix zu bezeichnen.Wir werden die Linsenverzerrung vorerst ignorieren.Die 2D-Position des ichDie Ecke im Bild der Kamera ist gegeben durch Qi=f(K(Rpich+T)), wobei f die Projektionsfunktion f(x,y,z)=(x/z,y/z) ist.Mithilfe dieser Gleichung wissen wir, dass jede Ecke im Bild uns zwei Gleichungen liefert (d. h.zwei Einschränkungen) für unsere Unbekannten:eine aus der x-Komponente von Qi und eins aus der y-Komponente.Wir haben also insgesamt 8 Einschränkungen, mit denen wir arbeiten müssen.Der offizielle Name dieser Einschränkungen lautet Einschränkungen bei der Neuprojektion.

Was sind also unsere unbekannten DoFs?Sicherlich R Und T sind unbekannt, da wir die Position der Kamera in Weltkoordinaten nicht kennen.Daher haben wir bereits 6 unbekannte DoFs:3 für R (z.B.Gieren, Nicken und Rollen) und 3 für T.Daher kann es maximal sein zwei Unbekannte in den übrigen Termen (K, P1, P2, P3, P4). 

Verschiedene Probleme

Wir können unterschiedliche Probleme konstruieren, je nachdem, welche zwei Terme in (K, P1, P2, P3, P4) werden wir als unbekannt betrachten.Lassen Sie uns an dieser Stelle aufschreiben K in der üblichen Form: K=(fx, 0, cx;0, fy, cy;0,0,1), wobei fx und fy die Brennweitenterme sind (fx/fy wird normalerweise als Bildseitenverhältnis bezeichnet) und (cx,cy) der Hauptpunkt (das Projektionszentrum im Bild) ist.

Wir könnten ein Problem erhalten, indem wir fx und fy als unsere beiden Unbekannten haben und annehmen (cx, cy, P1, P2, P3, P4) sind alle bekannt.Tatsächlich wird genau dieses Problem in der Kamerakalibrierungsmethode von OpenCV verwendet und gelöst, indem Bilder eines schachbrettartigen planaren Ziels verwendet werden.Dies wird verwendet, um eine erste Schätzung für fx und fy zu erhalten, indem davon ausgegangen wird, dass sich der Hauptpunkt in der Bildmitte befindet (was für die meisten Kameras eine sehr vernünftige Annahme ist).

Alternativ können wir ein anderes Problem erzeugen, indem wir fx=fy annehmen, was wiederum für viele Kameras durchaus sinnvoll ist, und annehmen, dass diese Brennweite (bezeichnet als f) die ist nur unbekannt in K.Deshalb haben wir noch eine Unbekannte übrig, mit der wir spielen können (denken Sie daran, dass wir maximal zwei Unbekannte haben können).Nehmen wir also an, dass wir die Form der Ebene kennen:als Rechteck (was die ursprüngliche Annahme in der Frage war).Daher können wir die Ecken wie folgt definieren: P1=(0,0,0), P2=(0,w,0), P3=(h,0,0) und P4=(h,w,0), wobei h und w die Höhe und Breite des Rechtecks ​​bezeichnen.Da wir nun nur noch 1 Unbekanntes übrig haben, legen wir dies als Seitenverhältnis des Flugzeugs fest:x=B/H.Die Frage ist nun, können wir x, f, R Und T aus den 8 Reprojektionsbeschränkungen?Die Antwort lautet: Ja!Und die Lösung findet sich in Zhangs in der Frage zitiertem Aufsatz.

Die Skalenmehrdeutigkeit

Man könnte sich fragen, ob ein anderes Problem gelöst werden kann:wenn wir davon ausgehen K ist bekannt und die beiden Unbekannten sind h und w.Können sie aus den Reprojektionsgleichungen gelöst werden?Die Antwort lautet „Nein“ und liegt daran, dass eine Unklarheit zwischen der Größe des Flugzeugs und der Tiefe des Flugzeugs zur Kamera besteht.Insbesondere, wenn wir die Ecken skalieren Pich nach s und skalieren T durch s, dann streicht s in den Reprojektionsgleichungen.Daher ist der absolute Maßstab des Flugzeugs nicht wiederherstellbar.

Möglicherweise gibt es andere Probleme mit unterschiedlichen Kombinationen für die unbekannten DoFs, zum Beispiel mit R, T, eine der Hauptpunktkomponenten und die Breite der Ebene als Unbekannte.Allerdings muss man sich überlegen, welche Fälle von praktischem Nutzen sind.Dennoch habe ich noch keinen systematischen Lösungskatalog für alle sinnvollen Kombinationen gesehen!

Mehr Punkte

Wir könnten denken, dass wir mehr als 8 unbekannte DoFs wiederherstellen könnten, wenn wir zusätzliche Punktkorrespondenzen zwischen der Ebene und dem Bild hinzufügen oder die Kanten der Ebene ausnutzen würden.Leider lautet die Antwort nein.Dies liegt daran, dass sie keine zusätzlichen unabhängigen Einschränkungen hinzufügen.Der Grund liegt darin, dass die 4 Ecken beschreiben vollständig die Transformation von der Ebene zum Bild.Dies lässt sich erkennen, indem man anhand der vier Ecken eine Homographiematrix anpasst, die dann die Positionen aller anderen Punkte auf der Ebene im Bild bestimmen kann.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top