Categorización de objetos basada en la segmentación

El conjunto de puntos en un espacio de características arbitrario se puede representar como un grafo completo no dirigido ponderado G = (V, E), donde los nodos del grafo son los puntos en el espacio de características. El peso${\displaystyle w_{ij}}$de un borde${\displaystyle (i,j)\in E}$es una función de la similitud entre los nodos${\displaystyle i}$y${\displaystyle j}$En este contexto, podemos formular el problema de segmentación de imágenes como un problema de partición de grafos que requiere una partición.${\displaystyle V_{1},\cdots,V_{k}}$del conjunto de vértices${\displaystyle V}$donde, según alguna medida, los vértices en cualquier conjunto${\displaystyle V_{i}}$tienen alta similitud y los vértices en dos conjuntos diferentes${\displaystyle V_{i},V_{j}}$tienen baja similitud.

Sea G = ( V , E , w ) un grafo ponderado.${\displaystyle A}$y${\displaystyle B}$sean dos subconjuntos de vértices.

Dejar:

${\displaystyle w(A,B)=\sum \limits _{i\in A,j\in B}w_{ij}}$

${\displaystyle \operatorname {ncut} (A,B)={\frac {w(A,B)}{w(A,V)}}+{\frac {w(A,B)}{w(B,V)}}}$

${\displaystyle \operatorname {nassoc} (A,B)={\frac {w(A,A)}{w(A,V)}}+{\frac {w(B,B)}{w(B,V)}}}$

En el enfoque de cortes normalizados, ^{[ 2 ]} para cualquier corte${\displaystyle (S,{\overline {S}})}$en${\displaystyle G}$,${\displaystyle \operatorname {ncut} (S,{\overline {S}})}$mide la similitud entre diferentes partes y${\displaystyle \operatorname {nassoc} (S,{\overline {S}})}$Mide la similitud total de los vértices en la misma parte.

Desde${\displaystyle \operatorname {ncut} (S,{\overline {S}})=2-\operatorname {nassoc} (S,{\overline {S}})}$, un corte${\displaystyle (S^{*},{\overline {S}}^{*})}$que minimiza${\displaystyle \operatorname {ncut} (S,{\overline {S}})}$también maximiza${\displaystyle \operatorname {nassoc} (S,{\overline {S}})}$.

Calcular un corte${\displaystyle (S^{*},{\overline {S}}^{*})}$que minimiza${\displaystyle \operatorname {ncut} (S,{\overline {S}})}$es un problema NP-difícil . Sin embargo, podemos encontrar en tiempo polinomial un corte${\displaystyle (S,{\overline {S}})}$de pequeño peso normalizado${\displaystyle \operatorname {ncut} (S,{\overline {S}})}$utilizando técnicas espectrales .

Dejar:

${\displaystyle d(i)=\sum \limits _{j}w_{ij}}$

Además, sea D un${\displaystyle n\times n}$matriz diagonal con${\displaystyle d}$en diagonal, y deja${\displaystyle W}$frijol${\displaystyle n\times n}$matriz simétrica con${\displaystyle w_{ij}=w_{ji}}$.

Tras algunas manipulaciones algebraicas, obtenemos:

${\displaystyle \min \limits _{(S,{\overline {S}})}\operatorname {ncut} (S,{\overline {S}})=\min \limits _{y}{\frac {y^{T}(DW)y}{y^{T}Dy}}}$

sujeto a las restricciones:

• ${\displaystyle y_{i}\in \{1,-b\}}$, por alguna constante${\displaystyle -b}$
• ${\displaystyle y^{t}D1=0}$

Minimizar${\displaystyle {\frac {y^{T}(DW)y}{y^{T}Dy}}}$sujeto a las restricciones anteriores es NP-difícil . Para que el problema sea manejable, relajamos las restricciones en${\displaystyle y}$y permitirle tomar valores reales. El problema relajado se puede resolver resolviendo el problema generalizado de valores propios.${\displaystyle (D-W)y=\lambda Dy}$para el segundo autovalor generalizado más pequeño.

El algoritmo de particionamiento:

1. Dado un conjunto de características, configure un gráfico ponderado.${\displaystyle G=(V,E)}$, calcular el peso de cada arista y resumir la información en${\displaystyle D}$y${\displaystyle W}$.
2. Resolver${\displaystyle (D-W)y=\lambda Dy}$para los autovectores con los segundos autovalores más pequeños.
3. Utilice el vector propio con el segundo valor propio más pequeño para biparticionar el grafo (por ejemplo, agrupando según el signo).
4. Decida si la partición actual debe subdividirse.
5. Dividir recursivamente las partes segmentadas, si es necesario.

Resolver un problema estándar de valores propios para todos los vectores propios (utilizando el algoritmo QR , por ejemplo) lleva${\displaystyle O(n^{3})}$tiempo. Esto no es práctico para aplicaciones de segmentación de imágenes donde${\displaystyle n}$es el número de píxeles de la imagen.

Dado que el algoritmo sin segmentación solo utiliza un vector propio, correspondiente al segundo valor propio generalizado más pequeño, la eficiencia puede mejorarse drásticamente si la resolución del problema de valores propios correspondiente se realiza sin utilizar matrices , es decir, sin manipular explícitamente ni calcular la matriz W, como, por ejemplo, en el algoritmo de Lanczos . Los métodos sin matrices solo requieren una función que realice un producto matriz-vector para un vector dado en cada iteración. Para la segmentación de imágenes, la matriz W suele ser dispersa, con un número de entradas distintas de cero.${\displaystyle O(n)}$, por lo que dicho producto matriz-vector toma${\displaystyle O(n)}$tiempo.

Para imágenes de alta resolución, el segundo valor propio suele estar mal condicionado , lo que provoca una convergencia lenta de los solucionadores iterativos de valores propios, como el algoritmo de Lanczos . El precondicionamiento es una tecnología clave que acelera la convergencia, por ejemplo, en el método LOBPCG sin matriz . Calcular el vector propio utilizando un método sin matriz precondicionado de forma óptima requiere${\displaystyle O(n)}$tiempo, que es la complejidad óptima, ya que el vector propio tiene${\displaystyle n}$componentes.

scikit-learn ^{[ 3 ]} utiliza LOBPCG de SciPy con precondicionamiento multigrid algebraico para resolver el problema de valores propios para el laplaciano del grafo para realizar la segmentación de imágenes a través de la partición espectral del grafo como se propuso por primera vez en ^{[ 4 ]} y se probó en ^{[ 5 ]} y ^{[ 6 ] .}

1. Dada una imagen D, se elige una categoría de objeto, por ejemplo, vacas o caballos.
2. El modelo LPS correspondiente se ajusta a D para obtener las muestras.${\displaystyle \Theta _{1},\cdots ,\Theta _{s}}$
3. La función objetivo dada por la ecuación (2) se determina calculando${\displaystyle E(m,\Theta _{i})}$y utilizando${\displaystyle w_{i}=g(\Theta _{i}|Z)}$
4. La función objetivo se minimiza utilizando una única operación MINCUT para obtener la segmentación m .