Census transform
The census transform (CT) is an image operator that associates to each pixel of a grayscale image a binary string, encoding whether the pixel has smaller intensity than each of its neighbours, one for each bit. It is a non-parametric transform that depends only on relative ordering of intensities, and not on the actual values of intensity, making it invariant with respect to monotonic variations of illumination, and it behaves well in presence of multimodal distributions of intensity, e.g. along object boundaries.[1] It has applications in computer vision, and it is commonly used in visual correspondence problems such as optical flow calculation and disparity estimation.[2]
The census transform is related to the rank transform, that associates to each pixel the number of neighbouring pixels with higher intensity than the pixel itself, and was introduced in the same paper.[3]
Algorithm
The most common version of the census transform uses a 3x3 window, comparing each pixel [math]\displaystyle{ p }[/math] with all its 8-connected neighbours with a function [math]\displaystyle{ \xi }[/math] defined as
- [math]\displaystyle{ \xi(p,p')=\begin{cases} 0 & \text{if }p \gt p' \\ 1 & \text{if }p \le p' \\ \end{cases}. }[/math]
The results of these comparisons are concatenated and the value of the transform is an 8-bit value, that can be easily encoded in a byte.
- [math]\displaystyle{ \begin{array}{|c|c||c|} \hline 124 & 74 & 32\\ \hline 124 & 64 & 18\\ \hline 157 & 116 & 84\\ \hline \end{array} \longrightarrow \begin{array}{|c|c|c|} \hline 1 & 1 & 0\\ \hline 1 & x & 0\\ \hline 1 & 1 & 1\\ \hline \end{array} \longrightarrow 11010111 }[/math]
Similarity between images is determined by comparing the values of the census transform for corresponding pixels, using the Hamming distance.[3] Several variations of the algorithm exist, using different size of the window, order of the neighbours in the pattern (row-wise, clockwise, counterclockwise), comparison operator (greater, greater or equal, lesser, lesser or equal).[4]
An extension of the algorithm uses a three-way comparison that allows to represent similar pixels, whose intensity difference is smaller than a tolerance parameter [math]\displaystyle{ \epsilon }[/math], defined as[5]
- [math]\displaystyle{ \xi(p,p')=\begin{cases} 0 & \text{if }p - p' \gt \epsilon\\ 1 & \text{if }|p - p'| \le \epsilon\\ 2 & \text{if }p' - p \gt \epsilon \end{cases} }[/math]
whose result can be encoded with two bits for each neighbour, thus doubling the size of the pattern for each pixel.
- [math]\displaystyle{ \begin{array}{|c|c||c|} \hline 124 & 74 & 32\\ \hline 124 & 64 & 18\\ \hline 157 & 116 & 84\\ \hline \end{array} \longrightarrow \begin{array}{|c|c|c|} \hline 2 & 1 & 0\\ \hline 2 & x & 0\\ \hline 2 & 2 & 2\\ \hline \end{array} \longrightarrow 21020222 }[/math]
See also
References
- ↑ Zabih and Woodfill (1994), p. 152.
- ↑ Hafner et al. (2013).
- ↑ 3.0 3.1 Zabih and Woodfill (1994), p. 153.
- ↑ "Census Transform Algorithm Overview". Intel. https://software.intel.com/en-us/sample-census-transform-census-transform-algorithm-overview.
- ↑ Stein (2004).
- Hafner, David; Demetz, Oliver; Weickert, Joachim (2013). "Why is the census transform good for robust optic flow computation?". pp. 210–221. https://www.mia.uni-saarland.de/Publications/hafner-ssvm13.pdf.
- Stein, Fridtjof (2004). "Efficient computation of optical flow using the census transform". pp. 79–86. https://www.researchgate.net/publication/221113496.
- Zabih, Ramin; Woodfill, John (1994). "Non-parametric local transforms for computing visual correspondence". pp. 151–158. http://www.cs.duke.edu/courses/spring06/cps296.1/handouts/Zabih%20Woodfill%201994.pdf.
 |  |
