An image processing apparatus robustly performs segmentation on an image including an object such as a moving person with its deformation. The image processing apparatus includes: an image inputting unit which receives temporally successive images; a motion analyzing unit which calculates motions of blocks using at least two temporally different images and calculates, based on the motions of the blocks, temporal motion trajectories of the blocks in the temporally successive images; a distance calculating unit which calculates a distance indicating a similarity of the motions of the blocks, using a temporal motion trajectory of a block i and a temporal motion trajectory of a block other than the block i calculated by the motion analyzing unit; and a nonlinear space processing unit which projects the distance calculated by the distance calculating unit into a nonlinear space and performs the segmentation on a result of the projection in the nonlinear space.