Methods and apparatus are provided for texture compression using patch-based sampling texture synthesis. An apparatus includes an encoder for encoding texture for a picture by synthesizing the texture. The encoder performs texture synthesis using a patch-based sampling method, thus determining “displacement vectors” indicating positions of patches in an input sample texture which are to be synthesized. At the encoder, both the input sample texture and information representing the “displacement vectors” are coded. At the decoder, the new patches are generated by directly using the “displacement vectors”.