The structure of locally orderless images

We propose a representation of images in which a global, but not a local topology is defined. The topology is restricted to resolutions up to the extent of the local region of interest (ROI). Although the ROI's may contain many pixels, there is no spatial order on the pixels within the ROI, the only information preserved is the histogram of pixel values within the ROI's. This can be considered as an extreme case of a textel (texture element) image: The histogram is the limit of texture where the spatial order has been completely disregarded. We argue that locally orderless images are ubiquitous in perception and the visual arts. Formally, the orderless images are most aptly described by three mutually intertwined scale spaces. The scale parameters correspond to the pixellation ("inner scale"), the extent of the ROI's ("outer scale") and the resolution in the histogram ("tonal scale"). We describe how to construct locally orderless images, how to render them, and how to use them in a variety of local and global image processing operations.