1. A three-dimensional object recognition device, comprising: an imaging unit configured to take images of a search area and generate image data; a matching unit configured to compare a three-dimensional object in an image based on the image data with a three-dimensional shape model corresponding to the three-dimensional object to associate correlated feature points with each other by pattern matching; a model updating unit configured to update the three-dimensional shape model based on the feature points associated by the matching unit; a motion estimation unit configured to estimate motion of the three-dimensional object based on a history of the position and attitude of the three-dimensional shape model updated by the model updating unit to estimate a three-dimensional shape model at an arbitrary time in the future; and a validity determination unit configured to compare the feature points associated by the matching unit with the three-dimensional shape model estimated by the motion estimation unit and cause the model updating unit to update the three-dimensional shape model based on only the feature points determined to be valid.