To detect a moving vector without increasing the calculation quantity by replacing a reference vector when a candidate vector indicates a similar pattern and outputting the most similar reference vector when not.

In a reference vector evaluation step 101, similarity to a reference block is evaluated at the position where a block in an object image is referred to. In a candidate vector prediction step 102, a candidate vector to be searched for next is predicted from the reference vector and evaluated value. In a candidate vector evaluation step 103, similarity to the reference block is evaluated at the position where the block in the object image is moved by the candidate vector. In a reference vector update step 104, the reference vector is updated by referring to the candidate vector and evaluated value or the moving vector is outputted. When the candidate vector indicates a pattern which is more similar than the reference vector, an advance to the reference vector prediction step 102 is made, but when not, the most similar reference vector is outputted as a moving vector.