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. It has applications in computer vision, and it is commonly used in visual correspondence problems such as optical flow calculation and disparity estimation.
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.
Algorithm.
The most common version of the census transform uses a 3x3 window, comparing each pixel formula_1 with all its 8-connected neighbours with a function formula_2 defined as
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.
Similarity between images is determined by comparing the values of the census transform for corresponding pixels, using the Hamming distance. 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).
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 formula_5, defined as
whose result can be encoded with two bits for each neighbour, thus doubling the size of the pattern for each pixel.