A retinex model based on absorbing Markov Chains

The Retinex algorithm, developed by Land and McCann, provides an abstract model of the mechanism of color sensation in the Human Vision System. At the basis of model lies the fact that the color appearance of a point does not depend only on its color value, but rather on the comparison among itself and other pixels. According to the model, separately for each chromatic channel, an image pixel receives suitably filtered information about the brightness of other image regions, based on which its own brightness is eventually re-scaled. The original formulation [17] uses a path-based sampling approach: the information is transported by memoryless random walks, starting from randomly chosen points; along the path the information is filtered – based on the brightness of the travelled regions – by a specific path function, computed through chains of ratios of pixel intensities. Such a function is path-dependent and retains the value of the brightest point found along the path. The overall correction to a pixel depends on the specific realizations of two sampling processes: the starting-point sampling process and the path-sampling process. As a consequence of the sampling, this algorithm is known to be intrinsically noisy. This draw-back can be overcome by passing from the path-sampling algorithm to the probabilistic representation of the corresponding diffusion process. In this paper we start from the random path simulative model of Retinex, we respell the standard path-based sampling process representation of the Retinex model, as formalized in [34], we show that, despite the overall path-dependence, the model can be given a representation in terms of Absorbing Markov Chains, by means of the embedding into a suitable state-space. We derive the corresponding analytic model, accounting for the combined effects of path-function, path sampling process and starting-point sampling process. Finally we provide a numerical algorithm for working out its solution. Using such a model, the output brightness of a pixel can be computed based on the solution of a simple sparse linear system. We show that the output of the random walk sampling algorithm and the Markov Chain based algorithm agree to an extent that can be controlled by few model parameters. We have found also that the Markov Chain based algorithm is more efficient than the basic random path sampling in obtaining noise free images. Those analytic probabilistic models and simulative models can be used as complementary tools for studying the Retinex mechanism and for identifying and comparing variants.