Automated detection and approximation of objects in a video, including: (a) sampling a provided digital video, to obtain a set of sampled frames; (b) applying an object detection algorithm to the sampled frames, to detect objects appearing in the sampled frames; (c) based on the detections in the sampled frames, applying an object approximation algorithm to each sequence of frames that lie between the sampled frames, to approximately detect objects appearing in each of the sequences; (d) applying a trained regression model to each of the sequences, to estimate a quality of the approximate detection of objects in the respective sequence; (e) applying the object detection algorithm to one or more frames in those of the sequences whose quality of the approximate detection is below a threshold, to detect objects appearing in those frames.