Different representations of images and their purpose

Question

I'm doing a small overview of different image representations used in image processing and computer vision. For every representation, I would like to have (at least) the following information:

• the name of the family of representations
• some basic characteristics of the representation family (what information is retained in the representation)
• what tasks are they typically used for
• what are different concrete types of representation from this family
• references for different representations and references for their usages

In addition to the representations I already know / have information about it (as an answer listed below), I am mostly interested in compressed domain (e.g. Fourier domain, wavelets), but knowing about other representations, e.g. edge-based, or whatever else I don't know about yet would be great.

If at all possible, I would appreciate if you could provide references (e.g. the article that proposed the representation, or a book explaining the representation), as indicated with the reference-request tag.

---

_Disclamer

_{I know list-questions are usually discouraged, but we had something similar about segmentation and thresholding, and it worked well.}

_{If the info I already provided is more suited as an answer, I could edit it out and post it as an answer. Also, I'm thinking maybe this would be a good question for community wiki.}

Answer 1

These are some representations that I already gathered information on, so I'll list them here.

1. Pixel based representation

   • simplest to define, simple neighborhood relations between elements (4,8,6-connectivity (1))
   • only local information for each element
   • big number of elements in the representation (used for displaying the image, applications with a lot of noise/details: e.g. medical imaging)

2. Block-based representations

   • image divided in a set of (rectangular) arrays
   • number of elements slightly smaller than with pixel-based, still only local information
   • both gray-scale and binary images
   • uses in compression ((2), (3), (4)), segmentation ((4), (5)), extracting different image features ((5), (6), (7))

3. Region based (sometime also super-pixels) representations

   • regions not rectangular; formed by grouping similar and connected pixels, usually using over-segmentation
   • adjacency information between regions (usually as RAG (region-adjacency graph (8)) or combinatorial map (9))
   • normalized cuts (10), graph-based segmentation (e.g. by Felzenszwalb and Huttenlocher (11)), watershed-based ((12), (13))
   • number of elements in the representation reduced while accuracy is kept
   • used for object detection and segmentation, but different unions of multiple regions have to be considered

4. Hierarchical representations

   • propose most likely unions of regions of region-based representations
   • image representation at different scales
   • only regions present in the representation have to be examined, can be constricted by scale
   • min-/max-tree ((14), (15)), tree of shapes ((16), (17)), binary partition tree (18), $\alpha$-tree (19), ...
   • used for: object detection (20), video segmentation (21), image segmentation and filtering ((22), (23)), image simplification (24)

Answer 2

You can add Vector graphics representations (as opposed to raster representations, mainly used in computer graphics):

• region outlines and strokes represented by smooth free-form curves (defined by a finite number of control points).

• no pixels.

• conceptually similar to CAD files.

• regions of constant color or color gradients, opaque or transparent.

• typical formats: SVG, PostScript.

• used for resolution-independent, high quality graphics. Relevant for image vectorization.

• proposals to use this representation for photographic images.

Answer 3

You can also classify representations based on their level of abstraction.

Low-level representations

These representations start with pixel based representations, in which pixel brightness or color is used directly.

Why are these representations not enough? In computer vision, we are interested in physical quantities of observed scenes, e.g. distance, albedo, etc., or in recognition of objects. Pixel based representations contain this information in a very indirect form. We should extract desirable invariant quantities from raw images, that is, to transform images to some different representation.

The most direct way to obtain some useful operations on images is to represent them as mathematical objects. There are two common types of mathematical representations of images. They are functional representations and stochastic models. Functional representations can be used for applying spatial transformations (e.g. scaling, rotation, affine, or projective) and for changing the functional basis (Fourier and wavelet transforms, etc.). Stochastic models (e.g. Markov fields) are useful in extracting statistical properties of visual scenes.

Intermediate representations

Unfortunately, it is difficult to achieve invariance w.r.t. complex factors of image changes within mathematical representations. Usually, it is easier to abstract from variable image content. E.g. instead of recovering true reflectance maps of visible surfaces, we can simply use borders of these surfaces as invariant descriptions of images. This leads to contour-level representations. Contours can be extracted locally or globally. In the second case, images will be represented as regions. Contours can also be represented as connected chains or as separated edge points. In addition to some degree of invariance, these representations also help to reduce data dimensionality. That is, if images are 2D signals, then contours are 1D signals.

One can further increase invariance and uniqueness of basic representation elements (pixels->contours->...). Structural representations are the next step of this abstraction. Their basic elements are straight lines, corners, arcs, etc. Complex structural elements can also be constructed including different types of junctions and geometric figures. Vector graphics representations belong to intermediate-level representations, but structural or contours image descriptions are derived from raw images in computer vision, while computer graphics is the reverse process.

However, such abstraction leads to great loss of data. In practice, feature points are used more frequently. They are similar to structural elements (they can stand for corners, centers of blobs or line segments, etc.), but they are not necessarily constructed from contours, and more importantly they are augmented with local features making them more informative.

Semantic (or knowledge-based) representations

Highest level of image representations are semantic representations, in which image regions are labeled with meaningful labels (words). You can also consider intermediate representations as a way to fill the semantic gap between pixel-level and semantic-level representations. Right now, this gap is far from being totally filled though.

There are also two types of multi-level or hierarchical representations. Computer vision system can analyze images on different levels of abstraction or resolution. Multi-resolution representations can be applied to image descriptions on any level of abstraction.

In should be noted that all these representations also have neurophysiologic analogues.

There are also other types of representations (color and textural representations, specific representations for 3D images, etc.).

Some random (and rather old) examples of usage of different representations

Functional representations

Essannouni L., Ibn-Elhaj E., Aboutajdine D. Fast cross-spectral image registration using new robust correlation // J. of Real-Time Image Processing. 2006. V. 1. № 2. P. 123–129.

Lan Z-D., Mohr R., Remagnino P. Robust matching by partial correlation // Proc. 6th British Machine Vision Conference. 1995. P. 651–660.

Goecke R., Asthana A., Pettersson N., Petersson L. Visual vehicle egomotion estimation using the Fourier-Mellin transform // IEEE Trans. Intelligent Vehicles Symposium. 2007. P. 450–455.

Stochastic models

Chan T.F., Shen J., and Vese L. Variational PDE models in image processing // Notice Amer. Math. Soc. 2003. V. 50. P. 14–26.

Zhu S.C., Wu Y.N., Mumford D.B. Filters, random fields, and maximum entropy (FRAME): towards a unified theory for texture modeling // Int’l J. Computer Vision. 1998. V. 27. No. 2. P. 1–20.

Geman S., Geman D. Stochastic relaxation, Gibbs distributions and Bayesian restoration of images // IEEE Trans. PAMI. 1984. V. 6. P. 721–741.

Shen, L., Bai, L.: A review on Gabor wavelets for face recognition // Pattern Analysis and Applications. 2006. V. 9. P. 273–292.

Edges and contours

Olson C.F., Huttenlocher D. Automated target recognition by matching oriented edge pixels // IEEE Trans. on Image processing. 1997. V. 6. No 1. P. 103–113.

Olson C.F. A probabilistic formulation for Hausdorff matching // Proc. IEEE Conf. on Computer Vision and Pattern Recognition. 1998. P. 150–156.

Yang C.H.T., Lai S.H., Chang L.W. Hybrid image matching combining Hausdorff distance with normalized gradient matching // Pattern Recognition. 2007. V. 40. № 4. P. 1173–1181.

** Structural representations **

Parida L., Geiger D., and Hummel R.. Junctions: detection, classification, and reconstruction // IEEE Trans. Pattern Analysis and Machine Intelligence. 1998. V. 20. No. 7. P. 687-698.

Noronha S., Nevatia R. Detection and modeling of buildings from multiple aerial images // IEEE Trans. PAMI. 2001. V. 23. No. 5. P. 501–518.

Lutsiv V., Malyshev I., Potapov A. Hierarchical structural matching algorithms for registration of aerospace images // Proc. SPIE. 2003. V. 5238. P. 164–175.

Efrat A., Gotsman C. Subpixel image registration using circular fiducials // Int. J. Comp. Geom. and Appl. 1994. V. 4, No. 4. P. 403–422.

Lagunovsky D. and Ablameyko S. Straight-line-primitive extraction in grey-scale object recognition // Pattern Recog. Letters. 1999. V. 20. P. 1005–1014.

Keypoints

Lowe D. Object recognition from local scale-invariant features // Proc. Int. Conf. on Computer Vision. 1999. P. 1150–1157.

Baumberg A. Reliable feature matching across widely separated views // Conf. on Computer Vision and Pattern Recognition. 2000. P. 774–781.

// Right now, there are a lot of papers on this topic

Knowledge-based systems

Linying S., Sharp B., Chibelushi C. Knowledge-based image understanding: a rule-based production system for X-ray segmentation // Int. Conf. on Enterprise Information Systems (ICEIS). 2002. P. 530–533.

Liedtke C.-E., Buckner J., Grau O., Growe S., Tonjes R. AIDA: a system for the knowledge based interpretation of remote sensing data // 3d Airborne Remote Sensing Conference and Exhibition. 1997. V. 2. P. 313–320.

Growe S., Tonjes R. A knowledge based approach to automatic image registration // Proc. Int. Conf. on Image Processing. 1997. V. 3. P. 228–231.

Crevier D., Lepage R. Knowledge-based image understanding systems: a survey // Comp. Vision and Image Understanding. 1997. V. 67. № 2. P. 161–185.