Localizando las coordenadas con precisión: Recurriendo al Plano Horizontal

Pedimos disculpas por no haber publicado ninguna nueva entrada desde hace 1 mes, pero hemos preferido tener todo el tema del reconocimiento de jugadas terminado para publicar nuevas entradas. Con esto pretendemos publicar un blog más enfocado a ayudar y compartir técnicas de procesado de imagen que a nuestras experiencias del día a día.

Empezamos con una pequeña introducción sobre el sistema diédrico:

El sistema diédrico es un método de representación geométrico de los elementos del espacio tridimensional sobre un plano, es decir, la reducción de las tres dimensiones del espacio a las dos dimensiones del plano, utilizando una proyección ortogonal sobre dos planos que se cortan perpendicularmente.

Si nosotros proyectamos el tablero en el Plano Horizontal (PH a partir de ahora), conseguiremos tener una vista sin ningún tipo de distorsión del tablero, ya que estaremos viendo el tablero a vista de pájaro.*

*Nota: También se podía haber recurrido a poner la cámara encima del tablero, a una cierta altura, para tener esta imagen sin necesidad de realizar un procesado de la misma. Pero si se quiere diseñar un sistema real (como lo vería una persona que estuviera jugando), la proyección sobre el PH es imprescindible para evitar las distorsiones provocadas por el espacio tridimensional.

¿Cómo abatimos la imagen sobre el PH con OpenCV?

Acudiendo al mundo de las matemáticas, nos encontramos con las transformaciones proyectivas:

Una proyectividad en una aplicación invertible h de P2 en P2 tal que tres puntos x1, x2, y x3 están alineados si y solo si h(x1), h(x2) y h(x3) lo están.

Una transformación proyectiva entre planos es una transformación lineal* sobre una 3-tupla de vectores homogéneos x, representada por una matriz 3x3 H, x’= Hx.

Si los sistemas coordenados de ambos planos son Euclídeos entonces la transformación se llama de perspectiva

*Nota: Según el libro de OpenCV de O´Reilly, una transformación perspectiva no es una transformación lineal porque se necesita realizar la división por una dimensión, por lo que se pierde una dimensión en el proceso. Si nos fijamos bien, no hay ninguna contradicción entre una y otra interpretación. El texto de O´Reilly simplemente está considerando la transformación perspectiva como el proceso de la pérdida de una dimensión más la aplicación lineal.

¿Entonces, la transformada perspectiva es una transformación lineal o no? Pues depende de tu dominio y de tu imagen. Si defines la transformación perspectiva como una función de f: R3 –> R2, es no lineal. Si la defines como f: R2 –> R2, es lineal.

Sin entrar más en detalle sobre las transformaciones perspectivas (esto lo comentaremos más a fondo en la memoria, que seguramente será accesible públicamente), volvemos al mundo de la programación con OpenCV.

Para poder aplicar la transformada perspectiva y obtener nuestra imagen proyecta en el PH, primero tenemos que encontrar la matriz de cambio de perspectiva (la H anterior). Pero OpenCV nos simplifica las cosas, y nos de proporciona una función donde, dados 4 puntos de la imagen, y sus 4 puntos transformados (es decir, los puntos donde deberían estar esos 4 puntos de la imagen), te devuelve la matriz de cambio de perspectiva.

CvMat* cvGetPerspectiveTransform(

    const CvPoint2D32f* pts_src,

    const CvPoint2D32f* pts_dst,

    CvMat* map_matrix

);

¿Y qué puntos le pasamos?

Lo mejor que podemos hacer es pasarle las 4 esquinas del tablero, y asignarle las 4 esquinas del tablero. Pero, como era de esperar, la cosa no iba a ser tan fácil. Ahora es buen momento para recodar que nosotros tenemos las esquinas interiores del tablero, y que pueden estar en cualquier orden (siempre por filas y columnas, pero pueden empezar en cualquier esquina).

Para encontrar las 4 esquinas el tablero, creamos un método para encontrar el punto (de un conjunto de puntos) más cercano a uno dado. Por tanto, buscaremos el punto más cercano a (0,0), (ancho,0), (ancho, alto), (0, alto). El conjunto de puntos será siempre la lista de las esquinas interiores encontradas:

/*

|| We suppose we have this variables

|| internalCorners -> pointer to the array of internal corners

|| internalCornersCount -> number of internal corners

|| img -> img we get from the camera

*/

//We get img size (widht & height)

int width = cvGetSize(img).width;

int height = cvGetSize(img).height;

CvPoint2D32f* imgPts = (CvPoint2D32f*)malloc(4 * sizeof(CvPoint2D32f));

imgPts[0] = closest_to(internalCorners, internalCornersCount, cvPoint2D32f(0,0));

imgPts[1] = closest_to(internalCorners, internalCornersCount, cvPoint2D32f(width,0));

imgPts[2] = closest_to(internalCorners, internalCornersCount, cvPoint2D32f(width,height));

imgPts[3] = closest_to(internalCorners, internalCornersCount, cvPoint2D32f(0,height));

///////////////////////////////////////////////////////////////////////////////

//    closest_to

//

//    Find the closest point of an array of points to a reference point

//

//    Parameters:

//        CvPoint2D32f* points -> Array of points

//        CvPoint2D32f reference -> Reference point

//

//    Return:

//        CvPoint2D32f -> Closest point

//

///////////////////////////////////////////////////////////////////////////////

CvPoint2D32f closest_to(CvPoint2D32f* points, int numPoints, CvPoint2D32f reference)

{

    CvPoint2D32f point;

    int i, best_i = -1;

    float dx, dy, d, best_dist = 10e9;

    for(i = 0; i < numPoints; i++)

    {

        point = points[i];

        dx = point.x - reference.x;

        dy = point.y - reference.y;

        d = dx*dx + dy*dy;

        if (d < best_dist)

        {

            best_dist=d;

            best_i=i;

        }

    }

    return points[best_i];

}

Una vez obtenidos los puntos de las esquinas interiores, tenemos que calcular las coordenadas de los puntos reales. Si fueran todas las esquinas, estos puntos serían (0,0), (ancho,0), (ancho, alto), (0, alto). Pero al ser esquinas interior, hay que estimar los puntos. Para la estimación, nos basamos en:

La parte de la imagen menos deformada es la más cercana a la cámara

Las esquinas encontradas tienen un formato de 7x7

Las casillas del tablero tienen el mismo ancho y alto (corner_height = corner_width)

double corner_width = (imgPts[2].x - imgPts[3].x)/7;

double corner_height = corner_width;

double real_left_x = 0 + corner_width;

double real_right_x = 0 + 9 * corner_width;

double real_top_y = 0 + corner_height;

double real_bottom_y = 0 + 9 * corner_height;

CvPoint2D32f* realPts = (CvPoint2D32f*)malloc(4 * sizeof(CvPoint2D32f));

realPts[0] = cvPoint2D32f(real_left_x, real_top_y);

realPts[1] = cvPoint2D32f(real_right_x, real_top_y);

realPts[2] = cvPoint2D32f(real_right_x, real_bottom_y);

realPts[3] = cvPoint2D32f(real_left_x, real_bottom_y);

Otra opción es poner el ancho y el alto de las casillas manualmente (mediante un define, por ejemplo). Sustituyendo las 2 primeras líneas de código, el resto se puede dejar igual :)

Una vez tenemos el conjunto de puntos de la imagen y los de sus correspondientes en la realidad:

CvMat *H = cvCreateMat( 3, 3, CV_32F);

cvGetPerspectiveTransform( realPts, imgPts, H);

Con la matriz de transformación de perspectiva (H), realizamos la transformación perspectiva:

/*

|| We suppose we have this variables

|| img -> img we get from the camera

|| H -> matrix of transformation perspective

*/

cvWarpPerspective(img, img2, H, (CV_INTER_LINEAR | CV_WARP_INVERSE_MAP | CV_WARP_FILL_OUTLIERS), cvScalarAll(0));

Los resultados de aplicar la transformación perspectiva son:

Imagen del tablero

Imangen del tablero proyectado en el PH