1. A person tracking device comprising: a person region information extraction unit that detects a person region where a person appearing in a video belongs, and generates person region information describing information of the person region; an accompanying person determination unit that identifies at least one accompanying person accompanying a tracking target person among persons included in the person region information based on the person region information and information specifying a tracking target person, and generates accompanying person information describing the at least one accompanying person; a distinctive person selection unit that selects a distinctive person having a salient feature using the person region information and feature saliency information among the at least one accompanying person specified by the accompanying person information, and generates distinctive person information describing the distinctive person, the feature saliency information representing a degree of saliency of a value obtained as each feature representing a distinctive feature of a person; and a person tracking unit that calculates a distinctive person tracking result being a tracking result for the distinctive person based on the person region information and the distinctive person information.