1. A moving object detection apparatus which detects a moving object in a video sequence by extracting a region corresponding to a whole or a part of an image of the moving object, said moving object detection apparatus comprising: an image receiving unit configured to receive a set of images included in the video sequence; a motion analysis unit configured to calculate movement trajectories, each of the movement trajectories being calculated by: detecting a motion of the image between a pair of images included in the set of images, for each pair of blocks included in the pair of images, each block having one or more pixels; and concatenating motions detected from all pairs of images included in the set of images; a segmentation unit configured to perform segmentation so that the movement trajectories are divided into subsets, and to set a part of the movement trajectories as a common point shared by the subsets; a distance calculation unit configured to calculate a distance representing a similarity between a pair of movement trajectories, for each of the subsets; a geodesic distance calculation unit configured to transform the distance calculated by said distance calculation unit into a geodesic distance; an approximate geodesic distance calculation unit configured to calculate an approximate geodesic distance bridging over the subsets, by integrating geodesic distances including the common point, among the geodesic distances obtained by said geodesic distance calculation unit; and a region extraction unit configured to extract at least one region from the video sequence, by performing clustering using the calculated approximate geodesic distance so that blocks having similar movement trajectories are classified into one region.