0
$\begingroup$

I'm unsure whether Normalized Cut can or can't be used to find connected components in binary images. I would argue that it could, but could not validate this argument.

$\endgroup$
  • $\begingroup$ Are you trying to resolve overlapping objects? $\endgroup$ – A_A Jan 10 at 15:41
0
$\begingroup$

Lamar, first welcome to StackExchange. Laplacian of a graph has very strong links to the topological properties such as connected components. For simple scenarios, the graph Laplacian, $L=I-D^{\frac{-1}{2}}AD^{\frac{-1}{2}}$ constructed using the degree matrix $D$ and the adjacency matrix $A$, can be processed to result in connected components. First, the number of connected components in the graph is the dimension of the nullspace of the Laplacian and the algebraic multiplicity of the $0$-eigenvalue. Then, for a graph with multiple connected components, $L$ is a block diagonal matrix, where each block is the respective Laplacian matrix for each component, possibly after reordering the vertices.

Simply look at the eigenvalues of the Laplacian matrix and identify clusters (e.g. Spectral clustering). This will give you the individual components if you form the graph with correct adjacency matrix and degrees.

I'm not sure, but if you directly like to use normalized cuts for finding the CC: Simply form the graph ($1$s are adjacent and $0$s are adjacent in themselves). Run the NC and select the segments which do not belong to the background. These should be the connected components.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.