A trajectory linking apparatus capable of linking a trajectory having a feature value with a trajectory having no feature value is provided. The trajectory linking apparatus includes a feature-including trajectory linking unit and an interpolation unit. The feature-including trajectory linking unit receives trajectory information for each time segment. The trajectory information represents a plurality of trajectories indicating respective movement paths of a plurality of objects detected from image data of a respective time segment, and also indicating whether or not each of the trajectories has a feature for object re-identification. The feature-including trajectory linking unit generates a linked trajectory having a feature by linking a first trajectory having a feature with a second trajectory. The interpolation unit generates an interpolated trajectory by linking a third trajectory to the first and second trajectories.