We characterize ``visual textures'' as realizations of a stationary, ergodic, Markovian process, and propose using its approximate minimal sufficient statistics for compressing texture images. We propose inference algorithms for estimating the ``state'' of such process and its ``variability''. These represent the encoding stage. We also propose a non-parametric sampling scheme for decoding, by synthesizing textures from their encoding. While these are not faithful reproductions of the original textures (so they would fail a comparison test based on PSNR), they capture the statistical properties of the underlying process, as we demonstrate empirically. We also quantify the tradeoff between fidelity (measured by a proxy of a perceptual score) and complexity.