Cortes Normalizados

universidad Tecnológica de la mixteca |
Cortes Normalizados |
Segmentación de Imágenes |
Descripción del Algoritmo |
Jorge Rodríguez Robles |
05/07/2012 |

|

Descripción delalgoritmo

El algoritmo utilizado es el de cortes normalizados, que se aplica a imágenes digitales para obtener una segmentación de la misma.
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, hayque encontrar un corte que divida al grafo en dos conjuntos, A y B.

cutA,B= u∈A v∈Bw(u,v)

Esta partición en dos conjuntos debe cumplir que la asociación entre los pixeles entre A y B sea mínimay 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 distinguirentre grupos aislados y poco conectados frente a grupos aislados pero muy conectados.
La descripción queda expresada por la siguiente formula

NcutA,B= cut(A,B)assoc(A,V)+cut(A,B)assoc(B,V)

Dondeassoc(A,V) nos da la conexión total de los nodos pertenecientes al conjunto A con todos los nodos del grafo y assoc(A,V) esta definido de manera similar.
De manera similar nosotros podemos definir eltotal de la asociación de los grupos para una partición dada:

NassocA,B= assoc(A,A)assoc(A,V)+ assoc(B,B)assoc(B,V)

Donde assoc(A,A) y assoc(B,B) son los pesos de las aristas que conectan losnodos 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:

cutA,B=assocA,V-assoc(A,A)

Con esto, podemosencontrar que el punto optimo de corte esta dado por

NcutA,B= 2-NassocA,B

A esto se llega de la siguiente manera:
NcutA,B= cutA,BassocA,V+cutA,BassocB,V
Ecuación original

NcutA,B=...