Video scene segmentation plays an important role in video structure analysis. In this paper, we propose a novel coherence signal construction method for scene segmentation based on normalized cut. The normalized cut criterion simultaneously emphasizes the homogeneity between the shots in the same scene and inhomogeneity between the shots in different scenes, hence, the signal constructed based on this criterion well reflects the shot content coherence. Experimental results on different genres of practical video have shown that our coherence signal performs better on scene segmentation than the backward shot coherence signal. �� 2009 Springer-Verlag Berlin Heidelberg.