An apparatus and a concomitant method for performing hierarchial block-based motion estimation with a high degree of scalability is disclosed. The present invention decomposes each of the image frames within an image sequence into an M-ary pyramid. Different dynamic ranges for representing the pixel values are used for different levels of the M-ary pyramid, thereby generating a plurality of different “P-bit” levels, i.e., a plurality of different M-ary pyramid architectures. The present scalable hierarchical motion estimation provides the flexibility of switching from one M-ary pyramid architecture to another M-ary pyramid architecture according to the available platform resources and/or user's choice.