A technique of encoding video frames allocates an available number of bits to different portions of the video frame. A processing unit identifies a region of interest (ROI) in a video frame, and computes a first and second complexity parameter respectively representing the change in video information in the ROI portions and non-ROI portions in the video frame relative to a reference frame. Bits are allocated to the ROI portion proportional (positive correlation) to the first complexity parameter and a ratio of the area of the ROI to the area of the frame. The remaining available bits are allocated to the non-ROI. In an embodiment, the bits are encoded according to H.264 standard.