A transcoding apparatus and method, and target bit-allocation and picture complexity estimation units and methods used for the same are provided. The transcoding apparatus includes: a video decoding unit which receives a compressed bitstream and performs decoding thereof to output decoded pictures; a complexity estimation unit which estimates complexity of a current picture among the decoded pictures to encode the current picture; a target bit-allocation unit which performs desired bit-allocation using the complexity information of the current picture; a bit-rate control unit which controls bit-rate using bit-allocation information and state information from memory, which outputs an encoded bitstream; and a video encoding unit which encodes the decoded pictures on the basis of the bit-allocation and state information of the bit-rate control unit. Therefore, an effect exists for transcoding that improves image quality.