This invention provides a video processing apparatus for suppressing a decrease in search accuracy of an object of a search target based on a feature extracted from a degraded image in a video. The video processing apparatus includes an image degradation estimator that extracts an image in an image region used as an index of image degradation from a video and estimates a degree of image degradation in the image region, a feature extractor that extracts a feature of an object of a search target from the video, a feature database that stores the feature of the object of the search target, and a matcher that controls matching between the extracted feature and the stored feature based on the degree of image degradation estimated by the image degradation estimator, when searching for the object from the video.