We present a newly developed scheme for automatically partitioning videos into scenes. A scene is generally referred to as a group of shots taken place in the same site. In this paper, we first propose a motion annotation algorithm based on the analysis of spatio-temporal image volumes. The algorithm characterizes the motions within shots by extracting and analyzing the motion trajectories encoded in the temporal slices of image volumes. A motion-based key frame computing and selection strategy is thus proposed to compactly represent the content of shots. With these techniques, we further present a scene change detection algorithm by measuring the similarity of the representative key frames in shots.