Universidad
publicado en junio 2005
reconocimiento de la imagen de un tablero de go

Proyecto de Reconocimiento de Patrones

Este es el proyecto para el curso CC61K: taller de reconocimiento de patrones. A partir de la foto de un tablero de Go, la idea es reconocer la posición de cada una de las piedras, obteniendo una matriz de 9x9, que indique la ubicación exacta de cada una de estas.


  • Etapas del Reconocimiento de Patrones.
    • Adquisición Imagen :
    • Recolección de fotos de los tableros (muestras).
    • Preprocesamiento :
    • Ajuste de tamaño y aplicación de filtros (estirar histograma).
    • Segmentación :
    • Identificación de los objetos (división de la imagen en zonas).
    • Medición :
    • Extracción de caracteristicas (nivel de gris de subconjuntos de puntos de la imagen).
    • Interpretación :
    • Clasificación (piedras negras, blancas, o vacío).




    El proyecto consiste en un programa realizado en Scilab, utilizando la librería SIP, para el procesamiento de imágenes. Además, se utiliza el algoritmo de Harris, que permite detectar esquinas en una imagen. Las imágenes (fotos) utilizadas, fueron fotografías de un tamaño 160x121 pixeles, tomadas desde la perspectiva habitual que percibe un jugador de Go. El programa consiste en el archivo go.sci, junto a las funciones harris.sci, trans.sci, submatrix.sci, meanbox.sci.

    Aparte del desarrollo del programa, una parte importante del proyecto constitió en la etapa de aprendizaje (el ajuste, manual, de los parámetros). Existe un conjunto de valores que fueron ajustados a medida que se probaban los ejemplos: los argumentos de la función harris, los valores de la deformación de la perspectiva, el umbral de discriminación (quizas el parámetro más importante).

    El proceso de identificación de la posición, se compone de las siguientes etapas:

  • Identificar geometría de la vista:
  • Utilizando el algoritmo de Harris, el programa estima la posición de las cuatro esquinas del tablero. Esto se consigue utilizando un contraste adecuado entre el tablero y el fondo. Los parámetros utilizados (para harris) fueron estimados mediante ensayo y error, obteniendo entre 4 a 8 puntos. Sin embargo, obteniendo los primeros y los últimos dos pares de puntos, se consiguen los puntos buscados : las esquinas del tablero. (esto es posible, hasta un cierta deformación del tablero en la imagen).

  • Cálculo de la geometría de la imagen
  • A partir de los puntos que definen la posición del tablero, se calcula la transformación del plano del tablero, sobre la imagen. La idea es mapear puntos en el intervalo [0..1, 0..1], sobre el cuadrado deformado que se observa en la imagen. Este cálculo lo realiza la función trans, y se ejecuta para cada punto a analizar. Además, se calcula la deformación de la perspectiva (la deformación hacia el fondo de la imagen).

  • Recorrer cada una de las posibles posiciones de piedras.
  • La siguiente etapa, consiste en realizar el barrido sobre todas las intersecciones donde se quiere analizar si existe una piedra (blanca/negra) o esta vacío. Este es un ciclo sobre una matriz de 9x9, que barre en dos dimensiones un cuadrado de lado 1, y transformando cada punto a su correspondiente punto dentro de la imagen. Cada uno de estos puntos (candidato a piedra), se marca con una cruz sobre la imagen original.

  • Analizar segmentos de la imagen (clasificación)
  • Para cada punto identificado, se obtiene la submatriz de puntos de su entorno (de 2x2, en principio), y mediante la función meanbox se obtiene un valor ''representante'' de este segmento de imagen. Ese valor es la mediana, que indica cual es el tipo de pixels que más se repite (oscuro, neutro o claro). A partir de este dato, se determina si se trata de una piedra (negra/blanca) o de una intersección vacía.

  • Representación del resultado
  • Finalmente, se grafica la matriz obtenida en el paso anterior, dibujando las piedras (posiblemente) identificadas, en los puntos correspondientes.





    Downloads:
    - codigo fuente
    - librería SIP
    - ejemplos:
    tablero00.jpg, tablero01.jpg, tablero02.jpg, tablero03.jpg



    Notas:

    - Para probar diversas imágenes, se debe cambiar el nombre de la imagen a utilizar, dentro del código fuente (tablero01.jpg), o renombrar el archivo de imagen a probar.

    - Las imágenes de prueba utilizadas, son imágenes de 160x121 pixeles. Cada una debiera ser pre-procesada, estirando el histograma (ajuste de contraste) de la foto original. Para una mayor resolución, sería necesario aumentar el tamaño de memoria utilizado por el programa.

    - El programa está hecho para un tablero de 9x9, sin embargo, debiera ser posible utilizar un tamaño mayor, ajustando el parámetro correspondiente (esta posibilidad no ha sido aún probada).

    - Los tableros considerados, pueden tener hasta un cierto grado de distorsión, a partir de la vista superior del tablero. Deformaciones mayores (de perspectiva), producirían resultados erróneos.

    - El problema más importante es el ruido que pueda aparecer en la imagen, básicamente en la forma de sombras y brillos. Esto puede hacer aparecer piedras ''fantasmas'' en lugares donde no existen piedras reales.

    - El programa admite varias mejoras. Con entrenamiento se pueden ajustar aún más los valores de algunos parámetros, para mejorar su comportamiento. Mientras que el problema del ruido, representa el principal desafío para una siguiente etapa del proyecto.


    Código Fuente:
    programa
    // GO - Programa que reconoce la posicion de las piedras de un tablero de go.
    

    getf('submatrix.sci'); getf('meanbox.sci'); getf('trans.sci'); // parametros // IMAGE : imagen a cargar. // THRESHOLD : umbral para discriminar piedra blanca o negra. // N : numero de puntos del tablero (9, 13, 19). // F : factor de perspectiva para distorcion hacia el fondo. // Z : tama~no del cuadrado a analizar (la vecindad de cada punto) IMAGE = 'tablero01.jpg'; THRESHOLD = 0.2; N = 9; F = 0.13; Z = 2;

    // cargar imagen img = gray_imread(IMAGE);

    // detectar esquinas xset("window",0); [cim, r, c] = harris(img, 3, 0.01, 15, %t);

    // tomamos las 4 esquinas (los primeros y ultimos 2 pares) s = size(r); points = s(2); p1 = [c(1), r(1)]; p2 = [c(points), r(points)]; p3 = [c(points-1), r(points-1)]; p4 = [c(2), r(2)]; board = [p1; p2; p3; p4];

    // calcular distorsion hacia el fondo factor = ((p4(1)-p1(1))/(p4(2)-p1(2)))*F; n = N+1; dif = (factor * 2) / n; inc = ((1/n)+factor) - (dif/2);

    // iterar sobre cada posible ubicacion de piedras col = []; matriz = []; x = 0; y = 0; for i = 0:n for j = 0:n if i>0 & j>0 & i
    // dibujar resultados xset("window", 1); xs = [10; 90; 90; 10; 10]; ys = [10; 10; 90; 90; 10]; xpoly(xs, ys); for i = 0:n for j = 0:n plot2d(j*10, i*10, -1); if i>0 & j>0 & i 0.7 xarc(j*10-3, i*10+3, 6, 6, 0, 360*64); end; end; end; end "Done"
    function harris
    // HARRIS - [cim, r, c] = harris(im, sigma, thresh, radius, disp)
    // im     - image to be processed.
    // sigma  - standard deviation of smoothing Gaussian.
    // thresh - threshold (optional). Try a value ~1000.
    // radius - radius of region considered in non-maximal suppression (optional).
    // disp   - optional flag (0 or 1) indicating to display corners
    

    function [cim, r, c] = harris(im, sigma, thresh, radius, disp) [nargout,nargin]=argn(0); dx = [-8 8 8; -8 0 8; -8 -8 8]; // derivative masks dy = dx'; Ix = imconv(im, dx, 'same'); // image derivatives Iy = imconv(im, dy, 'same');

    Ix2 = gsm2d(Ix.^2,sigma); // generate Gaussian filter Iy2 = gsm2d(Iy.^2, sigma); Ixy = gsm2d(Ix.*Iy, sigma);

    // Compute the Harris corner measure. cim = (Ix2.*Iy2 - Ixy.^2)./(Ix2 + Iy2 + 1e-6); if nargin > 2 sze = 2*radius+1; // extract local maxima mx = my_dilate(cim,radius); cim = bool2s((cim==mx)&(cim>thresh)); // find maxima. [r,c] = find(cim==1); // find row,col coords. r = size(cim,'r')-r+1 if nargin==5 & disp // overlay corners on original image imshow(im,[]) xset("colormap",[xget("colormap"); 1 0 0]) xset("foreground",257); plot2d(c,r,-1), xtitle('corners detected'); end else // leave cim as a corner strength image and make r and c empty. r = []; c = []; end

    function cim = my_dilate(im,rad) [r,c] = size(im) cim = zeros(r,c) for i=1:r; for j=1:c mx = max(im(max(i-rad,1):min(i+rad,r),max(j-rad,1):min(j+rad,c))) cim(i,j) = 2*im(i,j)-mx end; end
    function trans
    function [a, b] = trans(corners, x, y)
        P00 = corners(1,:); P10 = corners(2,:); 
        P11 = corners(3,:); P01 = corners(4,:);
        deltaXdw = P10(1) - P00(1);
        deltaXup = P11(1) - P01(1);
        deltaYdr = P11(2) - P10(2);
        deltaYiz = P01(2) - P00(2);
        a = (y*P01(1)+(1-y)*P00(1)) + (y*deltaXup+(1-y)*deltaXdw)*x;
        b = (x*P10(2)+(1-x)*P00(2)) + (x*deltaYdr+(1-x)*deltaYiz)*y;
    
    function submatrix
    // retorna una submatriz de tamano [size x size], centrada en (i,j)
    function aux = submatrix(m, i, j, siz)
        n = size(m);
        mid = (siz-1)/2;
        if i>n(1) | i+siz>n(1)
            i=n(1)-siz;
        end
        if j>n(2) | j+siz>n(2)
            j=n(2)-siz;
        end
        if i-siz<0
            i = siz;
        end
        if j-siz<0
            j = siz;
        end;
        aux = m([i-mid:i+mid],[j-mid:j+mid])
    
    function meanbox
    // Para una matriz cuadrada, entrega la mediana(representante) de sus valores
    function [val, meanv] = meanbox(m, n, threshold)
        patterns = [0, 0, 0]; // negra(b), blanca(w), vacio(_)
        for i = 1:n
        for j = 1:n
            if m(i,j) < (threshold-0.05) then patterns(1) = patterns(1) + 1;
            elseif m(i,j) > 1-(threshold+0.0) then patterns(2) = patterns(2) + 1;
            else  patterns(3) = patterns(3) + 1;
            end
        end; end;
        [mval, k] = maxi(patterns);
        intensity = [0, 1, 0.5];
        // devuelvo al representante de esta submatriz
        val = intensity(k);
        meanv = median(m);
    


    0 comentarios

    no hay comentarios.



    nombre *

    e-mail *

    web

    2 x 4 = *





    Mi paso por la Universidad de Chile marca la etapa más importante de mi vida. Primero fue arquitectura en la FAU, luego fueron 8 años de ingeniería, en Beauchef: más de 60 ramos, largas horas de estudio, controles, tareas, cátedras, ayudantías... largas horas de chess en la chacra y computadores en el cec, en el dcc... Aquí he reunido algunos de los proyectos que realicé durante la carrera de ingeniería civil en computación.