# Can Normalized Cut be used to find connected components in binary images?

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.

• Are you trying to resolve overlapping objects? – A_A Jan 10 '19 at 15:41

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.
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.