Memorias de un hombre de izquierda

Implementación Algoritmo Mean-Shift en OpenCV

Posted in Procesamiento de Señales, Visión por Computadora by unamdsp on junio 26, 2009

En mi primera publicación en la que hablé sobre el algoritmo Mean-Shift, prometí publicar el código de implementación del método en OpenCV. Todavía no soy experto en esta biblioteca de C/C++ pero encontré una función que lo implementa, se que prometí programarla de cuenta propia y lo pienso hacer, sólo que primero preferí hacerlo en Matlab donde la programación me es mucho mas familiar, para luego pasar el mismo concepto a OpenCV.

IplImage* doMeanShiftFilter(IplImage* src)
{
IplImage* dst = cvCreateImage(
cvSize( src->width, src->height ),
src->depth,
src->nChannels
);

CvTermCriteria term = cvTermCriteria(CV_TERMCRIT_ITER+CV_TERMCRIT_EPS,
5,
1);

cvPyrMeanShiftFiltering( src, dst, 20, 40, 2,term);

return(dst);
}

En los ejemplos que utilicé al correr el algoritmo me encontré una posible aplicación adicional del método de segmentación: La correción de apariencia de una imagen distorsionada por aliasing y otros factores como el ruido.

El algoritmo de Mean-Shift sirvió para aplanar la imagen y dividirla en dos categorías los puntos en rojo y los puntos en blanco, eliminando los artefactos de ruido que aparecían.

meanshiftOpenCV

Implementación Algoritmo Mean-Shift en Matlab

Posted in Procesamiento de Señales, Visión por Computadora by unamdsp on junio 25, 2009

En el post anterior mostré una explicación breve del algoritmo de segmentación Mean-Shift, el cual es ampliamente usado en el Procesamiento de Señales para hacer un tipo de digitalización vectorial. Esto significa que podemos tomar muchas dimensiones como pueden ser el color, las propiedades de cercanía o lejanía espacial, el tipo de textura, etc y hacer clasificación de cada elemento de la imagen (pixel) e ir agrupandolos de acuerdo a las propiedades mencionadas.

El algoritmo Mean-Shift es una idea muy sencilla pero su implementación se puede complicar debido a que demanda muchos recursos de computo. Para implementarlo en Matlab es necesario corregir algunos vicios de programación (intrínsecos de la plataforma) debido a que es código no compilado el que en la mayoría de los casos se ejecuta. Es mucho más preferible aprovechar las ventajas del cómputo de matrices que Matlab ofrece y utilizar este tipo de instrucciones siempre que sea posible.

En mi primer experimento hice una clasificación de puntos agrupándolos por su distribución espacial, he aquí los resultados de la clasificación.

Clasificación de Puntos en el Espacio con el Algoritmo de Mean-Shift

Clasificación de Puntos en el Espacio con el Algoritmo de Mean-Shift

El código que elaboré básicamente esta dividido en dos etapas:

1) Encontrar el pico o modo al que cada punto en el espacio dirige: implementado en findpeak.m

2) Agrupar los picos encontrados que se parezcan mucho y mostrar como salida el cluster o grupo al que cada punto en el espacio pertenece. Implementado en meanshift.m

function peak = findpeak(data,idx,r)

conv = 1;
radioSq = r.^2;
criterio = 1e-3 * r;

[nDim,nPuntos] = size(data);

centro = data(:,idx);

while conv
    distancia = sum( (data - repmat(centro,1,nPuntos)).^2 );
    indDentro = find(distancia < radioSq);

    centroAnterior = centro;
    centro = mean(data(:,indDentro),2);
    
    mov = norm(centro - centroAnterior);
    
    if mov < criterio
        conv = 0;
    end
end

peak = centro;

end
function [pertenencia,clusters] = meanshift(data,r)

criterioMezcla = r*0.5;

[numDims,nPuntos] = size(data);

peaks = zeros(numDims,nPuntos);
clusters = [];
numCluster = 1;

for i=1:nPuntos    
    peak = findpeak(data,i,r);      
    
    if(~isempty(clusters))
        distancia = sum( (clusters - repmat(peak,1,size(clusters,2))).^2 );
        indPeaksCerca = find(distancia < criterioMezcla);
    
        if(isempty(indPeaksCerca))
            numCluster = numCluster + 1;
            pertenencia(i) = numCluster;
            clusters = [clusters peak];            
        else
            nuevoPeak = 0.5 * (clusters(:,indPeaksCerca) + peak);
            clusters(:,indPeaksCerca) = nuevoPeak;
            pertenencia(i) = indPeaksCerca;
        end 
    else
        clusters(:,1) = peak;
        pertenencia(i) = numCluster;
        numCluster = numCluster + 1;
    end
end

end

Segmentación de Imágenes con el Algoritmo de Mean-Shift

Posted in Procesamiento de Señales, Visión por Computadora by unamdsp on junio 19, 2009

No llevo tanto tiempo que empecé a trabajar con el Procesamiento de Imágenes y mucho menos cona la Visión por Computadora (casi toda mi experiencia en el Procesamiento de Señales había sido de Audio), pero sí puedo ver cuando una técnica es digna de reconocércele algo. El algoritmo de Mean-Shift es una idea tan simple y sencilla de explicar que prácticamente no requiere fórmula alguna. La implementación por lo que he visto sí es costosa y eso hay que tomarlo en cuenta para alguna implementación en tiempo real. Los resultados son asombrosos:

Resultados de la segmentación

Resultados de la segmentación

Explicando la segmentación de imágenes en términos muy llanos, podríamos decir que es básicamente el proceso que hacemos mentalmente cuando en una fotografía tratamos de separar cada uno de los diferentes tipos de objetos que pueden estar presentes: cielo, mar, tierra, pasto, arboles, personas, edificios, etc. Es un mecanismo trivial para nosotros, tan trivial que ni sabemos cómo es que lo hacemos. De ahí la dificultad de explicarle a un procesador que sólo sabe hacer operaciones matemáticas, movimientos de datos de un registro a otro, por decir algunos ejemplos que tiene que hacer.

La idea de la segmentación es encontrar los picos o “modos” que representan los centros o valores ejemplares de cada tipo de segmento, determinar cuantos son y agrupar o etiquetar los pixels según el centro al que se parezcan más.

Los criterios usados para la segmentación pueden ser muchos:

  • Si es una imagen en tonos de gris podemos usar el brillo como criterio, en ese caso una imagen (que es bidimensional por sus coordenadas X y Y) es separada en segmentos (un proceso muy parecido a la discretización) según un parámetro unidimensional que es el brillo.
  • Para una imagen en colores el proceso es muy parecido, ahora la discretización la hacemos de forma vectorial (tenemos ahora tres parámetros en el caso de RGB: rojo, verde y azul)
  • Otro criterio posible a utilizar es el tipo de textura: para determinar los tipos de texturas podemos usar un banco de filtros que detecte la presencia de cada tipo de estructura en una textura (obteniendo así un vector de coeficientes de correlación de las texturas con las diferentes estructuras usadas en el banco de filtros)
  • Existen muchos otros más ejemplos de parámetros de clasificación de los segmentos de las imágenes, los anteriores sólo son algunos. A su vez, los algoritmos utilizados para hacer la segmentación son muchos, uno de los más usados es el famoso K-Means también usado en el reconocimiento de palabras y en otras muchas áreas del Procesamiento de Señales, también existen modelos probabilísticos que miden la probabilidad de que un pixel en particular pertenezca a una burbuja (que puede ser multidimensional) Gaussiana y con ello deciden.

    La razón principal por la que decidí hablar del algoritmo de Mean-Shift es que me asombró la calidad de sus resultados y la sencillez de la idea básica para su funcionamiento. No es que el algoritmo de K-Means sea algo complicado de entender, o incluso los métodos probabilísticos usados tamoco requieren a un experto en Probabilidad y Estadística, pero es que el algoritmo de Mean-Shift puede explicarse prácticamente sin usar una sola ecuación.

    La idea es seleccionar una región de interés y pasarla por una ventana:

    Incio del Algoritmo

    Incio del Algoritmo

    En la región de interés que seleccionamos buscamos el valor medio y movemos el centro de nuestra región de interés hasta este punto.

    Incio del Algoritmo

    Movimiento del centro del área de interés hacia el valor medio obtenido

    El algoritmo debe proseguir hasta encontrar una convergencia del área de interés. Ahora bien, debemos suponer que todo pixel que nos dirija hacia el mismo máximo local de convergencia forma parte de la misma región. Por ello hacemos el mismo proceso en paralelo barriendo la imagen y encontrando cuantos máximos locales o modos existen. A partir de esto etiquetamos a la imagen según al modo al que pertenezca cada pixel.

    Regiones segmentadas que dirijen hacia dos diferentes modos

    Regiones segmentadas que dirijen hacia dos diferentes modos

    Espero haber podido explicar el algoritmo de una manera entendible, en poco tiempo tendré lista la programación de este algoritmo en OpenCV (quizás exista ya alguna función que lo implemente), pero creo que de cualquier forma la programaré. Estoy un poco impaciente por ver como se ven los videos segmentados (creo que se van a ver así como en el inicio de la película de Juno).

    Si quieren encontrar más ejemplos e información de los creadores del algoritmo visiten este enlace.

    Bien, todavía creo no tener un solo lector pero agradezco comentarios.

    Visión por Computadora y la importancia de utilizarla en México

    Posted in Procesamiento de Señales, Visión por Computadora by unamdsp on junio 17, 2009

    Me imagino que empezar a escribir un blog siempre es dificil porque uno debe buscar que publicaciones le puedan interesar a la gente.

    Hace como un año recibí un correo supuestamente escrito por el Dr. Rene Drucker Collin un afamado y notable investigador de nuestra UNAM, en el que criticaba el exceso de atención que prestamos a la selección mexicana de futbol, la enorme lista de decepciones que tenemos con ella y en cambio lo indiferentes que somos antes los logros de otros mexicanos que merecerían mayor caso.

    Creo que desgraciadamente en México admiramos más a la persona que logra comprarse la nueva iPhone y no tanto a quienes fueron capaces de desarrollar la tecnología con la que funciona. A veces olvidamos que ese partido de la Champions que estamos viendo no sólo es gracias al talento de Messi que lo podemos ver, sino a quien inventó los satélites, las cámaras, los codificadores, etc.

    Recuerdo la sorpresa que representó el MP3 cuando supe de él, no podía estar más agradecido con los genios del Instituto Fraunhofer que lo inventaron (en algún otro post hablaré de cuanto odio las iPod). Iba en la preparatoria, sólo pocos de mis compañeros conociamos que eran, como bajarlos (todavía Napster no existía) y sobretodo la manera de pasarlos a WAV para quemarlos en un CD de música. También recuerdo las buenas fiestas en Xochimilco escuchando la música argentina que en México jamás habíamos oido para ese entonces o al menos muy poco.

    Pero me estoy desviando, en la primera publicación lo quise decir pero en realidad no sé si quedo claro. Lo que quiero hacer de este blog es un espacio principalmente para mi, para registrar mis ideas.

    ¿Porqué publicar mis ideas en lugar de simplemente guardarlas para mi?

    Porque lo que me interesa es conocer si hay más gente de habla hispana que piense como yo y que le interese trabajar en las áreas en las que yo trabajo. Mi filosofía es ser abierto en cuanto al conocimiento, amo los sistemas de software libre y trataré de mostrar siempre lo que haga esperando recibir una realimentación de quien me lea (que todavía creo es nadie).

    Bien, después de esta larga introducción me dispongo a empezar a hablar de mi área. Soy un joven deseoso de adentrarme en la investigación, mi área de trabajo es el Procesamiento de Señales. Por el momento la especialidad que me interesa dentro del Procesamiento de Señales es la Visión por Computadora.

    ¿Cuales son las aplicaciones de la Visión por Computadora?

    Esa fue la primera pregunta que me ha hecho mucha gente cuando le platico del área. En realidad lo que más me gusta del Procesamiento de Señales es que es un trabajo casi artesanal. Cada aplicación debe ser hecha a la medida y bajo las limitaciones que el usuario del sistema va a enfrentar. Por ello se vuelve un área muy abierta a la creatividad y en donde un problema nunca esta resuelto de forma general. Respondiendo la pregunta, la aplicación más conocida de la Visión por Computadora son los sistemas de vigilancia, por ello no pocos ingenieros o científicos en cómputo pierden el interés (la verdad a mi tampoco me interesan tanto los sistemas de vigialancia, no pienso ayudar a crear al Gran Hermano), pero en realidad se omiten muchas aplicaciones que pueden ser muy nobles, por ejemplo: mejorar los sistemas de resonacia magnética para encontrar problemas de salud, análisis de células para detectar y diagnosticar algunos tipos de cancer, mucha gente se sorprendería al saber que Google Earth fue posible gracias a los sistemas de ajuste y calibración de camaras brindados por la visión por computadora, etc. Otra aplicación muy recurrente y que debemos buscar implementar en las industrias mexicanas es el monitoreo de la calidad de los productos utlizando técnicas de visión artificial.

    Por cierto, para los que todas estas aplicaciones les resultaron aburridas, se sorprenderían al ver que también existen aplicaciones para la producción de videojuegos.

    Para los que les interesó les sugiero adentrarse en el tema, hay muchas cosas que no se requiere haber estudiado en una carrera que se pueden hacer como hobbie y que son divertidas. Una forma gratuita de hacerlo es bajarse la librería openCV de Intel y empezar a adentrarse en ese mundo.

    Seguir

    Recibe cada nueva publicación en tu buzón de correo electrónico.