1. A motion vector estimating device which segments an input picture into blocks of a predetermined size and estimates a motion vector of each of the input blocks, with respect to a reference picture through an n-stage pipeline processing where n is a natural number of 2 or more, said device comprising: a first motion vector estimating unit operable to calculate an evaluation value on a per search block basis, based on an amount of distortion and a correction value, and estimate a first motion vector of an input block based on a location of the input block and a location of a search block which provides a smallest evaluation value, the amount of distortion being calculated using each of a plurality of search blocks of the predetermined size in a predetermined search area in the reference picture and the input block, and the correction value being calculated based on a motion vector with respect to each search block, a first prediction vector and a weighting coefficient; a k+1th motion vector estimating unit operable to estimate a k+1th motion vector of the input block based on a location of the input block and a location of the search block which provides a smallest evaluation value, by determining an amount of distortion as an evaluation value, the amount of distortion being calculated, on a per search block basis, using the input block and a plurality of search blocks in a predetermined search area having, as a center, a location identified by a kth motion vector estimated by a kth motion vector estimating unit where k is a natural number between 1 to nâˆ’1 inclusive; and a first prediction vector generating unit operable to generate the first prediction vector based on a first motion vector of another input block which has been previously estimated by said first motion vector estimating unit, and notify said first motion vector estimating unit of the generated first prediction vector.