Encontrar las esquinas de un rectángulo deformado

Question

Estoy tratando de hacer un programa que corrige automáticamente la perspectiva de un rectángulo. Logré obtener la silueta del rectángulo y el código para corregir la perspectiva, pero no puedo encontrar las esquinas. El mayor problema es que, debido a que ha sido deformada, no puedo usar el siguiente "código":

c1 = min(x), min(y) 
    c2 = max(x), min(y) 
    c3 = min(x), max(y) 
    c4 = max(x), max(y) 

Esto no funcionaría con esta situación (X representa una esquina):

X0000000000X 
.00000000000 
..X000000000 
.....0000000 
........0000 
...........X 

¿Alguien sabe cómo hacer esto?

Answer 1

El punto más alejado del centro le dará una esquina. El punto más alejado de la primera esquina le dará otra esquina, que puede ser adyacente u opuesta a la primera. El punto más alejado de la línea entre esas dos esquinas (un poco más intensivo en matemáticas) le dará una tercera esquina. Utilizaría la distancia desde el centro como desempate. Para encontrar la cuarta esquina, será el punto fuera del triángulo formado por las primeras 3 esquinas que haya encontrado, lo más lejos posible de la línea más cercana entre esas esquinas.

Esta es una manera muy lenta de hacerlo, y nunca lo he intentado, pero debería funcionar.

Answer 2

Puede intentar usar un algoritmo de escaneo - Para cada línea del polígono (entonces y = min (y) .. max (y)), obtenga l = min (x) yr = max (x). Calcule la pendiente izquierda/derecha (deltax) y compárela con la pendiente de la línea anterior. Si cambió (use algo de tolerancia aquí), se encuentra en una esquina del rectángulo (o cerca de él). Eso no funcionará para todos los casos, ya que la pendiente no puede ser tan exacta debido a la baja resolución, pero para rectángulos grandes y pendientes no muy similares, esto debería funcionar.

Al menos, funciona bien para su ejemplo:

X0000000000X l = 0, r = 11 
.00000000000 l = 1, r = 11, deltaxl = 1, deltaxr = 0 
..X000000000 l = 2, r = 11, deltaxl = 1, deltaxr = 0 
.....0000000 l = 5, r = 11, deltaxl = 3, deltaxr = 0 
........0000 l = 8, r = 11, deltaxl = 3, deltaxr = 0 
...........X l = 11, r = 11, deltaxl = 3, deltaxr = 0 

Se empieza con la parte superior del rectángulo donde se obtienen dos valores diferentes de L y R, por lo que ya tiene dos de las esquinas. En el lado izquierdo, para las primeras tres líneas obtendrá deltax = 1, pero después de eso, obtendrá deltax = 3, por lo que hay una esquina en (3, 3). En el lado derecho, nada cambia, deltax = 0, por lo que solo obtiene el punto al final.

Tenga en cuenta que está "recogiendo" esquinas aquí, por lo que si no tiene 4 esquinas al final, las pendientes son demasiado similares (o si tiene una imagen de un triángulo) y puede cambiar a una diferente (más exacto) algoritmo o simplemente dar un error. Lo mismo si tiene más de 4 esquinas o alguna otra cosa extraña como agujeros en el rectángulo. Parece que hay algún tipo de detección de imagen involucrada, por lo que estos casos pueden ocurrir, ¿no?

Hay casos en los que un simple deltax = (x - LASTx) no va a funcionar bien, vean este ejemplo para el lado izquierdo de un rectángulo:

xxxxxx 
xxxxx deltax = 1 dy/dx = 1/1 = 1 
xxxxx deltax = 0 dy/dx = 2/1 = 2 
    xxxx deltax = 1 dy/dx = 3/2 = 1.5 
    xxxx deltax = 0 dy/dx = 4/2 = 2 
    xxx deltax = 1 dy/dx = 5/3 = 1.66 

veces deltax es 0, a veces es 1 . Es mejor usar la pendiente de la línea desde el punto real al punto superior izquierdo/derecho (deltay/deltax). Al usarlo, igual tendrá que seguir con una tolerancia, pero sus valores serán más exactos con cada nueva línea.

Answer 3

Parece un problema convexo del casco.

http://en.wikipedia.org/wiki/Convex_hull

Su problema es más simple, pero la misma solución debería funcionar.

Answer 4

Puede usar una transformada de hough para encontrar las 4 líneas más destacadas en la imagen enmascarada. Estas líneas serán los lados del cuadrilátero. Las líneas se cruzan en hasta 6 puntos, que son las 4 esquinas y los 2 puntos de fuga de perspectiva.

Estos son fáciles de distinguir: elija cualquier punto dentro del cuadrángulo y compruebe si la línea desde este punto a cada uno de los 6 puntos de intersección cruza cualquiera de las líneas. Si no, entonces ese punto de intersección es una esquina.

Esto tiene la ventaja de que funciona bien incluso para imágenes ruidosas o parcialmente obstruidas, o si su segmentación no es exacta.

en.wikipedia.org/wiki/Hough_transform

Example CImg Code

estaría muy interesado en sus resultados. He estado pensando en escribir algo como esto yo mismo, para corregir fotos de hojas de papel tomadas en ángulo. Actualmente estoy luchando para pensar en una forma de corregir la perspectiva si se conocen los 4 puntos

p.s.

También puedes ver Zhengyou Zhang, Li-Wei, "la exploración Pizarra y mejora de la imagen" http://research.microsoft.com/en-us/um/people/zhang/papers/tr03-39.pdf una solución más avanzada para la detección cuadrilátero

he hecho una pregunta relacionada, que trata de resolver el transformación de perspectiva: proportions of a perspective-deformed rectangle