The security management of underground utility tunnels is crucial, especially in tracking and recovering intruder trajectories. Traditional trajectory recovery methods rely on GPS data, which are not suitable for underground environments with inferior signals. Due to the city’s widely deployed distributed video surveillance systems, we focus on leveraging them to recover intruders’ trajectories, but there are still challenges. Firstly, the records data generated from videos lacks clear identity labels, leading to ambiguous correspondence between intruders and video records. Secondly, the uneven and incomplete distribution of surveillance cameras results in data sparsity issues. In this paper, we propose a novel two-stage framework, TrajUT, to address these challenges. We introduce the multi-criteria-based trajectory segmentation to segment the raw record sequence into sub-sequences belonging to different groups of intruders, based on the continuity of sequences. In addition, designing a speed-constrained (Hidden Markov Model) HMM-based method to recover the movement trajectory of intruders by leveraging the distance and dynamic speed relationship among records. We conduct experiments using real-world data from Suzhou’s underground utility tunnels, which show our framework’s effectiveness, achieving a 12.9% precision improvement over the best baseline method.