A video processing apparatus is directed to appropriately associating a plurality of objects in an image. A target detection unit detects a position of a region of a tracking target included in a video image. A specific object detection unit detects a position of a specific object included in the video image. The specific object has a predetermined feature. An association unit associates the region of the tracking target with the specific object based on a relative position between the position of the region of the tracking target detected by the target detection unit and the position of the specific object detected by the specific object detection unit.