Daniel Gómez M. [Página personal]

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 :
Preprocesamiento :
Segmentación :
Medición :
Interpretación :

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