El algoritmo de cortes normalizados es utilizado para la segmentación de imágenes.
La implementacion que realice fue hecha en Java.
A continuación dare una breve explicacion de como el algoritmo funciona.
SI están interesados en mas detalles del algoritmo, pueden visitar el siguiente link:
http://www.cs.berkeley.edu/~malik/papers/SM-ncut.pdf
Descripción del Algoritmo
Para su implementación se plantea a la imagen como un Grafo.
Dado un grafo G y un conjunto de vértices V, donde cada vértice representa un pixel en la imagen, y un conjunto de aristas E, en la que se representa la relación entre los pixeles con un peso W, hay que encontrar un corte que divida al grafo en dos conjuntos, A y B.
El corte se define de la siguiente manera:
Esta partición en dos conjuntos debe cumplir que la asociación entre los pixeles entre A y B sea mínima y la asociación entre los pixeles de cada uno de los conjuntos sea lo mayor posible.
La idea es no considerar sólo el valor de los arcos sino las relaciones entre los pixeles de modo de distinguir entre grupos aislados y poco conectados frente a grupos aislados pero muy conectados.
La descripción queda expresada por la siguiente formula:
Donde assoc(A,V) nos da la conexión total de los nodos pertenecientes al conjunto A con todos los nodos del grafo y assoc(B,V) esta definido de manera similar.De manera similar nosotros podemos definir el total de la asociación de los grupos para una partición dada:
Donde assoc(A,A) y assoc(B,B) son los pesos de las aristas que conectan los nodos de cada conjunto respectivamente.
Nosotros podemos definir un corte en términos de la asociación y disociación ya que están relacionados por:
Con esto, podemos encontrar que el punto optimo de corte esta dado por:
A esto se llega de la siguiente manera:
Ecuación original
Sustituyendo por la ecuación anterior
Acá podemos notar que buscamos un criterio, consiste en minimizar la disociación de los conjuntos y maximizar la asociación entre los conjuntos. En el algoritmo utilizamos este corte normalizado como criterio de partición.
Para poder computar el corte, necesitamos resolver un sistema de eigenvalores dado por:
Donde W se construye como una matriz por la siguiente función:
Y la matriz D se construye como:
Pero primero hay que transformarlo en un sistema de eigenvalores estándar, que esta dado por:
esta dada por:
Entonces hay que resolver el sistema dado por:
Primero hay que checar si la matriz es simétrica, si lo es, entonces procedemos a resolver primero generando una matriz tridiagonal y después resolver por el algoritmo QL que resuelve el sistema y nos regresan los eigenvalores y eigenvectores. Si la matriz no es simétrica se procede a resolver mediante una reducción de la matriz Hessenberg no simétrica una forma Schur.
Una vez resuelto el sistema, elegimos los eigenvectores asociados a los primeros valores de los eigenvalores más pequeños, de tal manera que estos tiendan a cero.
Cada valor del eigenvector esta asociado con un pixel de la imagen, como muestra el siguiente esquema:
Después calculamos con la formula un valor de tal manera que podamos dividir el eigenvector en dos conjuntos y poder dividir la imagen.
Esto se realiza para cada uno de los eigenvectores que se seleccionaron.
Para la división, lo que hacemos es comparar el valor obtenido con el valor i-esimo del iegenvector para saber si el pixel asociado, pertenece al conjunto A o al conjunto B.
Una vez obtenido el conjunto A y el conjunto B, se calcula su Varianza, de tal manera que, el conjunto que tenga la menor Varianza es el conjunto a representar en la imagen.
Este proceso se realizara mientras se soliciten más particiones y mientras tengamos eigenvectores que cumplan el criterio de que su eigenvalor sea cercano a cero.
Acá muestro algunos resultados obtenidos del algoritmo.
Las imágenes utilizadas son de un maximo de 30×30 pixeles.
Si alguien tiene alguna duda acerca de la implementación, puede hacérmelo saber, para poder desarrollar mas la parte que especifiquen, siempre y cuando este en mis posibilidades.
Jorge Rodriguez Blog 