Object tracking verification techniques are described as implemented by a computing device. In one example, feature points are selected on and along a boundary of an object to be tracked, e.g., in an initial frame of a digital video, which are referred to as “feature points.” Tracking of the feature points is verified by the computing device between frames. If the feature points have been found to deviate from the object, the feature points are reselected. To verify the feature points, a number of tracked features points in a subsequent frame is compared to a number of feature points used to initiate tracking with respect to a threshold. Based on this comparison, if a number of feature points is “lost” in the subsequent frame that is greater than the threshold, the feature points are reselected for tracking the object in subsequent frames of the video.