Mapeando el tablero: consiguiendo las coordenadas de cada casilla

    Una vez localizadas las esquinas interiores (organizadas por filas y columnas, pero sin saber el orden), lo primero que haremos es ordenarlas para que siempre sigan un orden determinado: ordenadas horizontalmente de izquierda a derecha, de arriba a abajo.

Para poder ordenarlas, necesitamos saber antes que orden están siguiendo. El método utilizado para encontrar el orden sique el siguiente esquema:

 

 

La numeración corresponde a cada caso particular:

0 –> Ordenado verticalmente, de derecha a izquierda, de abajo a arriba
1 –> Ordenado verticalmente, de derecha a izquierda, de arriba a abajo
2 –> Ordenado verticalmente, de izquierda a derecha, de abajo a arriba 3 –> Ordenado verticalmente, de izquierda a derecha, de arriba a abajo
4 –> Ordenado horizontalmente, de derecha a izquierda, de abajo a arriba
5 –> Ordenado horizontalmente, de derecha a izquierda, de arriba a abajo
6 –> Ordenado horizontalmente, de izquierda a derecha, de abajo a arriba
7 –> Ordenado horizontalmente, de izquierda a derecha, de arriba a abajo

Para que se cumplan los ordenados verticalmente, comprobamos a que punto es igual la esquina nº [alto – 1], y para los ordenados horizontalmente, la esquina nº [ancho –1].

0 => esquina[alto – 1] = Esquina Superior Derecha
1 => esquina[alto – 1] = Esquina Inferior Derecha
2 => esquina[alto – 1] = Esquina Superior Izquierda
3 => esquina[alto – 1] = Esquina Inferior Izquierda
4 => esquina[ancho – 1] = Esquina Inferior Izquierda
5 => esquina[ancho – 1] = Esquina Superior Izquierda
6 => esquina[ancho – 1] = Esquina Inferior Derecha
7 => esquina[ancho – 1] = Esquina Superior Derecha

 

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

//    check_order

//

//    Check the order (horizontal/vertical, left/right, top/bottom) of the points

//

//    Parameters:

//        CvPoint2D32f* points -> Pointer to the corners

//        int pointsCount-> Number of corners

//        CvSize cornerSize -> size of the corners [i.e. CvSize(7,7)]

//        CvSize size -> size of the image in px [i.e. CvSize(480,480)]

//

//    Return:

//        0) Ordered vertical, from rigth to left, from bottom to up

//        1) Ordered vertical, from rigth to left, from up to bottom

//        2) Ordered vertical, from left to rigth, from bottom to up

//        3) Ordered vertical, from left to rigth, from up to bottom

//        4) Ordered horizontal, from rigth to left, from bottom to up

//        5) Ordered horizontal, from rigth to left, from up to bottom

//        6) Ordered horizontal, from left to rigth, from bottom to up

//        7) Ordered horizontal, from left to rigth, from up to bottom

//

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

int check_order(CvPoint2D32f *points, int pointsCount, CvSize cornerSize, CvSize size)

{

    CvPoint2D32f top_left = closest_to(points, pointsCount, cvPoint2D32f(0,0));

    CvPoint2D32f top_right = closest_to(points, pointsCount, cvPoint2D32f(size.width, 0));

    CvPoint2D32f bottom_right = closest_to(points, pointsCount, cvPoint2D32f(size.width, size.height));

    CvPoint2D32f bottom_left = closest_to(points, pointsCount, cvPoint2D32f(0, size.height));

    int width = cornerSize.width;

    int height = cornerSize.height;

    if(top_left.x == points[0].x && top_left.y == points[0].y)

        if(top_right.x == points[width - 1].x && top_right.y == points[width - 1].y)

            return 7;

        else if(bottom_left.x == points[height - 1].x && bottom_left.y == points[height - 1].y)

            return 3;

        else

            throw "Error checking order: points start at top_left";

    if(top_right.x == points[0].x && top_right.y == points[0].y)

        if(top_left.x == points[width  - 1].x && top_left.y == points[width - 1].y)

            return 5;

        else if(bottom_right.x == points[height - 1].x && bottom_right.y == points[height - 1].y)

            return 1;

        else

            throw "Error checking order: points start at top_right";

    if(bottom_left.x == points[0].x && bottom_left.y == points[0].y)

        if(bottom_right.x == points[width - 1].x && bottom_right.y == points[width - 1].y)

            return 6;

        else if(top_left.x == points[height - 1].x && top_left.y == points[height - 1].y)

            return 2;

        else

            throw "Error checking order: points start at bottom_left"; 

    if(bottom_right.x == points[0].x && bottom_right.y == points[0].y)

        if(bottom_left.x == points[width - 1].x && bottom_left.y == points[width - 1].y)

            return 4;

        else if(top_right.x == points[height - 1].x && top_right.y == points[height - 1].y)

            return 0;

        else

            throw "Error checking order: points start at bottom_right"; 

    throw "Error checking order: no point start";

}

 

ORDENACIÓN DE LAS ESQUINAS

   Una vez obtenido el orden, rellenamos una matriz de 2 dimensiones (filas x columnas) que va a representar las esquinas del tablero, ordenado horizontalmente, de izquierda a derecha, de arriba a abajo.

[0][0] –> Esquina Superior Izquierda
[0][ancho - 1] –> Esquina Superior Derecha
[alto][0] –> Esquina Inferior Izquierda
[alto][ancho - 1] –> Esquina Inferior Derecha

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

//    ordenate

//

//    Finds all the corners of the checkerboard with the internal corners

//

//    Parameters:

//        CvPoint2D32f *points -> Pointer to the corners

//        int cornerCount -> Number of corners

//        CvSize cornerSize -> Size of the corners [i.e. CvSize(7,7)]

//        CvSize size -> Size of the image [i.e. CvSize(480,480)]

//

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

void ordenate(CvPoint2D32f *points, int cornerCount, CvSize cornerSize,  CvSize size)

{

    int state = check_order(points, cornerCount, cornerSize, size);

    int NUM_V_CORNERS = cornerSize.width;

    int NUM_H_CORNERS = cornerSize.height;

    CvPoint2D32f** temp = (CvPoint2D32f**)malloc(NUM_H_CORNERS * sizeof(CvPoint2D32f*));

    for(int i = 0;i < NUM_H_CORNERS; i++)

        temp[i] = (CvPoint2D32f*) malloc(NUM_V_CORNERS * sizeof(CvPoint2D32f));

    //CvPoint2D32f** temp = new CvPoint2D32f* [NUM_H_CORNERS];

    //for(int i = 0;i < NUM_H_CORNERS; i++)

    //    *(temp+i)=new CvPoint2D32f[NUM_V_CORNERS];

    switch(state)

    {

        case 7:        // Ordered horizontal, from left to rigth, from up to bottom

                    for(int i = 0; i < cornerCount; i++)

                        temp[i / NUM_H_CORNERS][i % NUM_H_CORNERS] = points[i];

                    break;

        case 6:        // Ordered horizontal, from left to rigth, from bottom to up

                    break;

        case 5:        // Ordered horizontal, from rigth to left, from up to bottom

                    break;

        case 4:        // Ordered horizontal, from rigth to left, from bottom to up

                    break;

        case 3:        // Ordered vertical, from left to rigth, from up to bottom

                    break;

        case 2:        // Ordered vertical, from left to rigth, from bottom to up

                    for(int i = 0; i < cornerCount; i++)

                        temp[(NUM_V_CORNERS - 1) - (i % NUM_V_CORNERS)][i / NUM_V_CORNERS] = points[i];

                    break;

        case 1:        // Ordered vertical, from rigth to left, from up to bottom

                    for(int i = 0; i < cornerCount; i++)

                        temp[i % NUM_V_CORNERS][(NUM_H_CORNERS - 1) - i / NUM_V_CORNERS] = points[i];

                    break;

        case 0:        // Ordered vertical, from rigth to left, from bottom to up

                    break;

    }

    for(int i = 0; i < NUM_V_CORNERS; i++)

        for(int j = 0; j < NUM_H_CORNERS; j++)

        {

            points[i * NUM_H_CORNERS + j] = temp[i][j];

            //printf("Corner %d en (%d, %d)\n", i * NUM_H_CORNERS + j, cvRound(points[i * NUM_H_CORNERS + j].x), cvRound(points[i * NUM_H_CORNERS + j].y));

        }

}

 

ALGORITMO DE RECONSTRUCCIÓN

    Ahora que disponemos de las casillas ordenadas siempre igual (horizontalmente, de izquierda a derecha, de arriba a abajo), ya simplemente nos queda aplicar el algoritmo de reconstrucción: estimar la posición de las esquinas “no interiores”. Es importantes resaltar que ahora estamos trabajando con la proyección sobre el PH, por lo que tenemos la imagen sin distorsión. Esto nos simplifica muchísimo la complejidad del algoritmo de reconstrucción:

Para la estimación de puntos en una imagen real (la de la izquierda), vemos que para estimar habría que calcular el punto de fuga, y hacer una relación de proporcionalidad para estimar los puntos.

Para la estimación de puntos en la imagen proyectada sobre el PH, simplemente tenemos que sumarle una distancia constante.

Esta vez, en principio, el código no lo vamos a adjuntar. Este algoritmo es un poco confuso a la hora de tomar los índices de las matrices (imaginarios como sería para una imagen real o para una sobre el PH con los puntos desordenados… y ahora para una real con los puntos desordenados!!!)

 

FORMANDO LAS CASILLAS

Ahora que tenemos todas las esquinas (tanto interiores como exteriores) y ordenadas, ya simplemente tenemos que formar rectángulos con ellas.

El proceso seguido es bastante intuitivo:  creamos un array con todas las casillas, y por cada una escogemos las 4 esquinas correspondientes.
El tema de los índices no es tan confuso como en el algoritmo de reconstrucción, pero aún así hay que tener cuidado.

 

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

//

//    Finds all the corners of the checkerboard with the internal corners

//

//    Parameters:

//        CvPoint2D32f* corners -> Pointer to the corners

//        CvSize patternSize -> Board Size in squares (width, height)

//

//    Return:

//        CvSquare* -> Pointer to the squares of the board

//

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

CvSquare* findSquaresFromCorners(CvPoint2D32f* corners, CvSize patternSize)

{

    int NUM_H_SQUARES = patternSize.width;

    int NUM_V_SQUARE = patternSize.height;

    CvSquare* squares = new CvSquare[NUM_H_SQUARES * NUM_V_SQUARE];

    for(int i = 0; i < NUM_V_SQUARE; i++)

    {

        for(int j = 0; j < NUM_H_SQUARES; j++)

        {

            double bottom_left_x = corners[(i+1) * (NUM_H_SQUARES + 1) + j].x;

            double bottom_left_y = corners[(i+1) * (NUM_H_SQUARES + 1) + j].y;

            CvPoint2D32f bottom_left = cvPoint2D32f(bottom_left_x, bottom_left_y);

            double bottom_right_x = corners[(i+1) * (NUM_H_SQUARES + 1) + j + 1].x;

            double bottom_right_y = corners[(i+1) * (NUM_H_SQUARES + 1) + j + 1].y;

            CvPoint2D32f bottom_right = cvPoint2D32f(bottom_right_x, bottom_right_y);

            double top_left_x = corners[ i * (NUM_H_SQUARES + 1) + j].x;

            double top_left_y = corners[ i * (NUM_H_SQUARES + 1) + j].y;

            CvPoint2D32f top_left = cvPoint2D32f(top_left_x, top_left_y);

            double top_right_x = corners[ i * (NUM_H_SQUARES + 1) + j + 1].x;

            double top_right_y = corners[ i * (NUM_H_SQUARES + 1) + j + 1].y;

            CvPoint2D32f top_right = cvPoint2D32f(top_right_x, top_right_y);

            CvPoint2D32f* points = new CvPoint2D32f[4];

            points[0] = bottom_left;

            points[1] = bottom_right;

            points[2] = top_right;

            points[3] = top_left;

            squares[i * NUM_H_SQUARES + j].points = points;

            printf("Square %d (%d,%d) - (%d,%d) - (%d,%d) - (%d,%d)\n", i * NUM_H_SQUARES + j, cvRound(bottom_left.x), cvRound(bottom_left.y), cvRound(bottom_right.x), cvRound(bottom_right.y), cvRound(top_right.x), cvRound(top_right.y), cvRound(top_left.x), cvRound(top_left.y));

        }

    }

    return squares;

}

Y el resultado lo podemos comprobar en la siguiente imagen

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