In this paper, we study a perceptual scale space by constructing a so-called sketch pyramid which augments the Gaussian and Laplacian pyramid representations in traditional image scale space theory. Each level of this sketch pyramid is a generic attributed graph — called the primal sketch which is inferred from the corresponding image at the same level of the Gaussian pyramid. When images are viewed at increasing resolutions, more details are revealed. This corresponds to perceptual transitions which are represented by topological changes in the sketch graph in terms of a graph grammar. We compute the sketch or perceptual pyramid by Bayesian inference upwards-downwards the pyramid using Markov Chain Monte Carlo reversible jumps. We show two example applications of this perceptual scale space: (1) motion tracking of objects over scales, and (2) adaptive image displays which can efficiently show a large high-resolution image in a small screen (of a PDA for example) through a selective tour of its image pyramid. Other potential applications include super-resolution and multi-resolution object recognition.