A video stream encoding apparatus and method therefore is herein described. The video stream encoding apparatus includes a divider for dividing a frame in a video stream into a plurality of processing units, each processing unit including a plurality of macro-blocks; and an encoder for encoding the plurality of macro-blocks in each processing unit in parallel. The same quantization parameters are used for respective macro-blocks in the same processing unit in the quantization of the encoder. By the apparatus and the method of the invention, dependencies between macro-blocks are broken, and the precision of high rate controlling is kept while encoding the respective macro-blocks in parallel.