1. A video processing apparatus, the apparatus comprising: a feature database that stores features of objects, the objects associated with each other; a memory storing instructions; and a processor configured to execute the instructions to: extract an image in an image region used as an index of image degradation from a video and estimate a degree of image degradation in the image region; extract a feature of an object to be a search target from the video; and change matching processing between the extracted feature and the stored features in accordance with the estimated degree of image degradation, when searching for the object from the video.