Capturing image structure with probabilistic index maps

N. Jojic and Y. Caspi

One of the major problems in modeling images for vision tasks is that images 
with very similar structure may locally have completely different appearance, 
e.g., images taken under different illumination conditions, or the case of 
pedestrians with different clothing. While there have been many successful 
attempts to address these problems in application-specific settings, we believe 
that underlying a large set of problems in vision is a representational 
deficiency of intensity-derived local measurements that are the basis of most 
efficient models. We argue that interesting structure in images is better 
captured when the image is defined as a matrix whose entries are discrete 
indices to a separate palette of possible intensities, colors or other features, 
much like the image representation often used to save on storage. In order to 
model the variability in images, we define an image class not by a single index 
map, but by a probability distribution over the index maps, which can be 
automatically estimated from the data, and which we call probabilistic index 
maps. The existing algorithms can be adapted to work with this representation, 
as we illustrate in this paper on the example of transformation-invariant 
clustering and background subtraction. Furthermore, the probabilistic index map 
representation leads to algorithms with computational costs proportional to 
either the size of the palette or the log of the size of the palette, making the 
cost of significantly increased invariance to non-structural changes quite 
bearable.