This paper proposes a novel region-based weighted prediction (WP) algorithm to encode scenes with complex brightness variations. It facilitates the use of multiple WP parameter sets in a single reference frame by utilizing the framework of multiple reference frame motion estimation (MRF-ME). With this arrangement, different macroblocks in the current frame can use different WP parameter sets even when they are predicted from the same reference frame. To support this, a region partitioning process is designed to divide the current frame into different regions where each one has some degree of uniformity in its brightness variation. Multiple sets of region-based WP parameters can then be estimated accurately. Consequently, the proposed algorithm can improve prediction in scenes with different degrees of brightness variations in different regions of the same picture. Results show that the region-based algorithm can achieve significant coding gains of scenes with complex brightness variations.