  Spectral graph theory is well known and widely used in computer vision. In
this paper, we analyze image segmentation algorithms that are based on spectral
graph theory, e.g., normalized cut, and show that there is a natural connection
between spectural graph theory based image segmentationand and edge preserving
filtering. Based on this connection we show that the normalized cut algorithm
is equivalent to repeated iterations of bilateral filtering. Then, using this
equivalence we present and implement a fast normalized cut algorithm for image
segmentation. Experiments show that our implementation can solve the original
optimization problem in the normalized cut algorithm 10 to 100 times faster.
Furthermore, we present a new algorithm called conditioned normalized cut for
image segmentation that can easily incorporate color image patches and
demonstrate how this segmentation problem can be solved with edge preserving
filtering.
