Vários métodos de segmentação não supervisionada de imagens usando grafos, consideram um grafo esparso G(V, E), onde os vértices no conjunto V são os pixels, e as arestas em E são definidas entre pixels vizinhos. Os pesos das arestas são dados por uma função de dissimilaridade entre as características dos pixels vizinhos (ex: magnitude do gradiente de intensidades), ou pela sua noção dual dada por uma função de afinidade/similaridade.
Para um dado grafo derivado da imagem, uma relação binária entre pixels contida no produto cartesiano V \times V que satisfaz as propriedades de reflexividade, simetria e transitividade, induz naturalmente uma segmentação da imagem, pois uma relação de equivalência permite particionar o grafo em classes de equivalência. Por exemplo, para um grafo não direcionado, considere a relação binária a \overset{\kappa}{\leadsto} b tal que existe um caminho interligando os pixels a e b, contendo apenas arestas com pesos abaixo de um dado limiar \kappa. As partições geradas por essa relação binária correspondem aos componentes conexos do grafo, após a remoção de todas as arestas com pesos maiores ou iguais à \kappa. Variando o parâmetro \kappa, é possível construir uma hierarquia das partições.
|
Max-tree com atributo de altura |
Valores de extinção nas folhas |
|
Max-tree com área dos vértices |
Max-tree com atributo de área (acumulada) |
Valores de extinção nas folhas |
|
Max-tree com volume dos vértices |
Max-tree com atributo de volume (acumulado) |
Valores de extinção nas folhas |
Artigos relacionados:
A cada iteração t, os conjuntos S_t e M_t são informados e uma IFT é calculada de forma diferencial/incremental em relação a floresta da iteração anterior t-1. As árvores com pixels em M_t serão removidas e suas regiões disponibilizadas para a nova conquista por parte das raízes restantes e das novas sementes em S_t. Essas raízes são representadas por pixels das árvores não removidas que são adjacentes a pixels das árvores removidas. Estes pixels são denotados pixels de fronteira.
Artigo: Interactive volume segmentation with differential image foresting transforms
Exemplo em filtragem: Para uma dada imagem binária I com ruído e imperfeições, desejamos obter uma imagem filtrada F. Considere a imagem I abaixo.
Os ruídos e imperfeições finas da imagem I resultam em uma elevada quantidade de pixels de borda. Logo, a fim de eliminar os ruídos devemos reduzir o número de transições preto/branco na imagem filtrada F. Isso pode ser formulado pela seguinte energia:
E = \sum_{(a,b)\in E} \lvert F(a) - F(b) \rvert.
A minimização da energia acima possui como soluções triviais imagens filtradas F de brilho constante. Portanto, devemos incluir um segundo termo que penaliza resultados divergentes em relação à imagem I:
E = \kappa \sum_{(a,b)\in E} \lvert F(a) - F(b) \rvert + \lambda \sum_{a \in {\cal D}_I} \lvert I(a) - F(a) \rvert.
A energia acima pode ser minimizada através do algoritmo do fluxo máximo/corte mínimo, utilizando o seguinte grafo no qual:
Variando os pesos \kappa e \lambda dos termos da energia temos diferentes soluções:
 |
 |
 |
 |
| \kappa=1 e \lambda=1 | \kappa=2 e \lambda=1 | \kappa=3 e \lambda=1 | \kappa=5 e \lambda=1 |
Observe que a imagem filtrada resultante não pode ser obtida via filtragem conexa.
Artigo: Oriented Image Foresting Transform Segmentation by Seed Competition
Artigo: Image Segmentation by Oriented Image Foresting Transform: Handling Ties and Colored Images
Artigo: Geodesic Star Convexity for Interactive Image Segmentation
Artigo: Image Segmentation by Oriented Image Foresting Transform with Geodesic Star Convexity
Monografia: Segmentação de imagens utilizando passeios aleatórios em grafos
Artigo: Random Walks for Image Segmentation
Artigo: Relaxed image foresting transforms for interactive volume image segmentation
Numerando os vértices do grafo podemos representá-lo pela sua matriz de afinidade \mathbf{A}.
\mathbf{A} =
\begin{bmatrix}
w_{11} & w_{12} & w_{13} & \dots & w_{1n} \\
w_{21} & w_{22} & w_{23} & \dots & w_{2n} \\
\hdotsfor{5} \\
w_{n1} & w_{n2} & w_{n3} & \dots & w_{nn}
\end{bmatrix} =
\begin{bmatrix}
0 & 2 & 0 & 2 & 0.1 & 0 & 0 & 0 & 0 \\
2 & 0 & 5 & 3 & 0 & 0 & 0 & 0 & 0 \\
0 & 5 & 0 & 2 & 0 & 0 & 0 & 0 & 0 \\
2 & 3 & 2 & 0 & 0 & 0 & 0 & 0 & 0.1 \\
0.1 & 0 & 0 & 0 & 0 & 1 & 3 & 0 & 1 \\
0 & 0 & 0 & 0 & 1 & 0 & 4 & 2 & 0 \\
0 & 0 & 0 & 0 & 3 & 4 & 0 & 2 & 4 \\
0 & 0 & 0 & 0 & 0 & 2 & 2 & 0 & 1 \\
0 & 0 & 0 & 0.1 & 1 & 0 & 4 & 1 & 0
\end{bmatrix} =
Considere o problema de dividir o grafo em grupos de vértices de alta afinidade. Um grupo pode ser especificado por um vetor \mathbf{u} = [u_1 \ldots u_n]^T, no qual u_i representa o grau de pertinência do i-ésimo vértice ao conjunto.
Gostaríamos de maximizar o seguinte funcional de energia:
E(\mathbf{u}) = \mathbf{u}^T \mathbf{A} \mathbf{u} = \sum_i \sum_j u_i w_{ij} u_j
sob a restrição: \mathbf{u}^T \cdot \mathbf{u} = 1 \Rightarrow ||\mathbf{u}|| = 1
Dado que a matriz de afinidade é simétrica (w_{ij} = w_{ji}), ela admite uma base ortonormal (\mathbf{u_1}, \ldots , \mathbf{u_n}) de autovetores.
Logo, podemos reescrever \mathbf{u} na base de autovetores de \mathbf{A}:
\mathbf{u} = \sum_i c_i \mathbf{u_i}
Substituindo na equação, temos:
\mathbf{u}^T \mathbf{A} \mathbf{u} = (\sum_j c_j \mathbf{u_j})^T \mathbf{A} (\sum_i c_i \mathbf{u_i})
= (\sum_j c_j \mathbf{u_j}^T)(\sum_i c_i \mathbf{A} \mathbf{u_i})
= (\sum_j c_j \mathbf{u_j}^T)(\sum_i c_i \lambda_i \mathbf{u_i})
= \sum_j \sum_i (c_j c_i \lambda_i \mathbf{u_j}^T \mathbf{u_i})
Note que:
i \neq j \Rightarrow \mathbf{u_j}^T \cdot \mathbf{u_i} = 0
i = j \Rightarrow \mathbf{u_j}^T \cdot \mathbf{u_i} = 1.
Portanto temos:
\sum_j \sum_i (c_j c_i \lambda_i \mathbf{u_j}^T \mathbf{u_i}) = \sum_i (c_i^2 \lambda_i)
Note que a restrição ||\mathbf{u}|| = 1 pode ser reescrita como \sum c_i^2 = 1
Portanto, a energia corresponde a uma média ponderada dos autovalores da matriz de afinidade, com pesos c_i^2.
Dado que os autovalores são números reais, temos que o máximo valor da energia
é obtido atribuindo-se peso total para o maior autovalor. Logo, a solução
corresponde ao autovetor associado ao maior autovalor.
Artigo: Normalized Cuts and Image Segmentation
Artigo: What Energy Functions Can Be Minimized via Graph Cuts?
Artigo: Globally Optimal Segmentation of Multi-Region Objects
Artigo: Multi-Object Segmentation by Hierarchical Layered Oriented Image Foresting Transform
Artigo: Image Segmentation with Minimum Mean Cut
Artigo: Image segmentation with ratio cut
