A similarity computation unit (130) derives a first probability P indicating that a first moving body appearing in the first video is the same as a second moving body appearing in the second video on the basis of similarity of feature value of the moving bodies. A non-appearance probability computation unit (140) derives a second probability Q indicating that the first moving body is not the same as the second moving body on the basis of an elapsed time after the first moving body exits from the first video. A person determination unit (150) determines whether the first moving body is the same as the second moving body by comparing the probability P and Q.