The current explosion in multimedia applications and services has been primarily enabled by the significant recent advances in image and video compression technology, e.g., JPEG for still images and MPEG for video, which have become household and marketing terms. Digital HDTV is on the horizon, and will be based on the MPEG-2 standard. Does this mean that image/video coding has reached a state of saturation where more research on compression is unlikely to yield significant improvements? This research tries to shed light on this by investigating the fundamental performance bounds on image and video compression. A primary goal is to uncover the performance gaps between existing commercial systems and the theoretical performance optimally attainable, and to guide the generation of improved compression algorithms in the future. The main focus of this research is to derive fundamental rate--distortion bounds for realistic classes of image and video models. This enables the generation of reliable estimates of the gap between the optimal performance theoretically attainable for these models and that of specific coding algorithms based on them. The analytical approach of this research contains the following key components: (1) a hierarchy of increasingly complex and realistic image/video models; (2) derivation of rate-distortion bounds for these models; (3) analysis of model parameter identifiability and estimation accuracy; (4) compression based on universal spectrum-blind spatio-temporal sampling techniques, and (5) model validation on real images/video based on high-performance practical algorithms.