1. An information processing apparatus comprising: a detection unit which detects an object included in an image as a tracking candidate by image processing; a corresponding degree calculation unit which calculates a corresponding degree representing a probability that the tracking candidate detected by the detection unit corresponds to a tracking target registered as an object to be tracked; and a decision unit which deletes a registration of the object to be tracked with respect to the relevant tracking target in a case of determining that it is unnecessary to track the tracking target based on an evaluation value which is calculated by using the calculated corresponding degree, and is also a value which is used to determine whether or not the relevant tracking target is needed to be tracked continuously.