A method comprises dividing a largest coding unit (LCU) of a picture into a plurality of motion estimation regions (MERs) having size equal to or less than a predetermined size. For one or more MERs of the plurality of MERs, a number of first motion searches are performed for determining a first quad-tree based on a cost function associated with a first plurality of prediction units (PUs) of the one or more MERs. A number of second motion searches are performed for the LCU, for determining a second quad-tree, based on the cost function associated with a second plurality of PUs of the LCU. The first quad-tree or the second quad-tree is selected for performing encoding of the picture based on a comparison of a first cost of the first quad-tree with a second cost of the second quad-tree.