An encoder for receiving a video frame and performing encoding processes to generate an encoded bitstream includes: a fidelity enhancement block, for performing a fidelity enhancement technique on the video frame utilizing a quad-tree partition, and generating fidelity enhancement information including a parameter associated with the quad-tree partition structure; and an entropy coding block, coupled to the fidelity enhancement block, for encoding the fidelity enhancement information, and embedding the encoded fidelity enhancement information into the encoded bitstream.