During the past decades a significant amount of research has been undertaken to understand human visual perception, which is not a trivial task as the human visual system (HVS) has complex and robust mechanisms to acquire useful information from the environment. In particular, the color appearance of an area is influenced by the chromatic content of the other areas of the scene. This psychophysiological phenomenon is referred to as locality of color perception.
In order to deal with this locality in image appearance, different image processing methods and frameworks have been developed with the intent to exhibit behaviors similar to the HVS, such as Automatic Color Equalization (ACE),1 Spatio-Temporal Retinex-inspired (STRESS),2 image Color Appearance Model (iCAM), and its evolutions,3,4 and the various Retinex implementations, which are the interest of this work.
The original Retinex model of lightness and color perception was proposed by Land and McCann about 50 years ago.5,6 In the light of current developments, there has been a renewed interest in color appearance.7,8 The principal assumption of the Retinex theory is that the sensation of color comes from a comparison among the various areas in the scene. In this comparison performed separately on each of the three color channels, a series of ratios and products among the various parts of the image are computed to calculate each pixel appearance. In this way, the appearance of each pixel depends on what surrounds the pixel; therefore, pixels of the same value can trigger different sensations. This locality of perception is achieved, in the original proposal from Land and McCann, by long paths scanning across the image, accounting for pixel ratio computation in each chromatic channel. The details of the ratio-product-reset Retinex algorithm will be presented later in the paper.
Different implementations and analysis have been developed since this first work, and these can be divided into three major groups, which differ in the way they achieve locality. The first group explores the image using paths or extracting random pixels around the pixel of interest or computing ratios with neighbors in a multilevel framework.910.–11 The second group instead computes values over the image with convolution masks or weighting distances.12,13 The third group uses differential mathematical techniques based on Poisson-type equations and variational approaches (e.g., Refs. 14, 15, 16 and 17).
Recent implementations constructed to investigate the effects of different spatial samplings replace paths with random sprays, for example, two-dimensional point distributions across the image, hence the name Random Spray Retinex (RSR).18 All these algorithms require a high density of samples in order to lower the amount of noise, but they never sample the whole image in order to keep the local effect. Furthermore, the number of sampling points that are needed increases drastically and consequently also the computational time, when increasing the size of the image.
In this work we start from the random path approach of the first group. In particular, we focus on the Brownian motion models.10,19 Here, the idea of the paths is implemented using a swarm intelligence model. Swarm intelligence can be considered a branch of artificial intelligence techniques dealing with the modeling of the collective behavior of simple agents interacting with the environment and among themselves. These models, in general physically or biologically inspired, provide metaheuristics for a wide set of combinatorial optimization problems. There are several families of swarm intelligence, and among them is the ant colony system (ACS),20 upon which we base our work.
The first studies on the development of artificial ants date back to the 1990s and is based on the work of Dorigo et al.20 The idea is derived from the behavior of real ants foraging for food. In this context, the objective is to understand how almost blind animals, such as ants, can manage to establish the shortest path routes from their colony to feeding sources and back. Biological studies have shown that social insects coordinate their activities via stigmergy, a form of indirect communication mediated by modifications of the environment. In the case of ants, the communication among individuals, or between individuals and the environment, is based on the production of a chemical substance called pheromone. Inspired by these behavioral properties of the ants, Dorigo et al. developed the so-called ACS for solving computational problems. Today their pioneering work has been diversified to solve a wider class of numerical problems.21
In this work, we propose a new implementation of Retinex, following the approach of the first group, in particular substituting the Brownian paths with a so-called termite colony exploration of the image, a diversified and tuned model for image processing derived from the ACS for traveling salesman problem (TSP). In daily life, termites are also known as white ants, and as this model attempts an eager exploration in search of the local reference white, we have called our algorithm Termite Retinex (TR).
The rest of this paper is organized as follows. Section 2 briefly describes the ACS system, followed by our proposal TR in Sec. 3. Section 4 presents the method of evaluation, and next, the results are presented and discussed in Sec. 6. Finally, in Sec. 7, conclusions are drawn.
Ant Colony System Model
The basic motivation of the presented work is to implement an alternative way to explore the image, driven by mechanisms different from simple randomness. To this aim, we have chosen a swarm intelligence method. Many of them can be suitable for this purpose; however, in this paper, we are more interested in testing if this approach can be successful rather than choosing the best swarm intelligence method. For this reason, we have chosen the ACS since it is one of the first and for its simplicity.
The following is a brief introduction to the first ACS model proposed by Dorigo et al.20 and the TSP since this is relevant for our proposal. The TSP is an NP-hard problem in combinatorial optimization and theoretical computer science, where given a list of cities and their pairwise distances, the task is to find the shortest possible tour that visits each city exactly once. ACS has been shown to be able to converge to the optimal solution of instances of this problem with short computational time, when cities are on a plane, and a path (edge) exists between each pair of cities (i.e., the TSP graph is completely connected).22
Three ideas from natural ant behavior are transferred to the artificial ant colony.
1. The preference for paths with a high pheromone level,
2. The higher rate of growth of the amount of pheromone on shorter paths,
3. The trail mediated communication among ants.
An artificial ant in city chooses the city to move to among those that do not belong to its working memory by applying the following probabilistic formula:23Ref. 22.
The original Retinex model developed by Land and McCann5,6 is based on computing the relative channel lightness () at a point as the mean value of the relative channel lightnesses () computed along random paths from point to the point (Fig. 1).
The threshold mechanism helps to discount slow varying gradients; however, it has been proven that the algorithm maintains its fundamental properties even without it.24 During the computation of along the path , the value of can become positive. In terms of image, this means that a lighter area is found. In this case, a reset mechanism triggers, forcing the relative lightness to the unitary value, making the average computation restart from this area.
The reset mechanism forces to restart the chain of ratios (sum of logs) from the point of reset by considering the lightness value found at the reset point as the new local reference white. The point can be either along the path, like in the original Retinex, or always at the end of the path, like in the Milano (MI)-Retinex family. This difference is discussed in Ref. 8. We have chosen to implement the Termites using the MI-Retinex approach. This results in higher computational costs but is an easier way to test and control the Termite swarm and the overall behavior.
A Brownian motion method is used to generate these paths,10,19 which has been extensively studied from a theoretical point of view. Brainard and Wandell25 described them formally using stochastic methods: for a large number of very long paths, the method converges; for infinitely long paths, the image tends to the original image globally normalized by its channel maximum values. This limit behavior has no interest since it loses the local behavior. Brownian paths work efficiently for a path-based Retinex (Fig. 2), but the approach has some drawbacks. Its computational complexity is low, , where is the number of pixels, but processing a whole image requires a large amount of memory. Thus, performing as many visits as desirable for each pixel becomes unfeasible when the image is too large.
When attempting to model the human vision system, an important characteristic to consider is the locality of the visual sensation.8,26 The way the image is explored affects the influence that the surrounding pixels have on the final estimate of the visual sensation. The main objective of the use of a colony of termites is to model a novel method by which the image content is explored, and thus the locality of perception, with an alternative mechanism. As consequence, a new set of parameters is created to describe and investigate the local behavior of Retinex.
In order to create TR, ACS requires some modifications, which comprises the following assumptions and constraints:
1. Pixels are considered as cities: a termite can choose to move only to one of the eight neighboring pixels (no jumps). Exploring larger neighborhoods and allowing the termite to jump might lead to not discovering the proper reference white.
2. The choice of a pixel is based on its distance and intensity value: the visibility is substituted with the bilateral distance as defined below, which we will refer to as closeness.
3. There is a higher preference for paths with a low poison, as we want divergence, in order to explore different areas of the image: the poison is the inverse to the amount of pheromone: , which acts as a repulsion force, inverse of the attraction force, pheromone in ACS.
So in our modified model, an artificial termite in pixel chooses to move to the pixel among those that belong to the eight-neighborhood and that do not currently belong to its working memory by applying the following probabilistic formula:
We underline that Eq. (5) uses the same convex combination as Eq. (1) but with a different leading principle: a trade-off between the brightness of a pixel to choose and the quantity of poison found on the pixel. In the case of high values of , a pixel is chosen, even if already visited by another termite. On the contrary, high values of force a termite to choose another direction.
The bilateral distance is defined as follows:
The use of the bilateral distance is known to be a suitable tool for edge-preserving.27 In our model, it is possible to notice from Eq. (8) that when a termite has to choose among eight neighboring pixels with same intensity values, the preference goes to one of the four diagonal pixels with respect to the vertical and horizontal ones. This scheme is motivated and justified by the fact that the presence of halos are reduced in the final image with respect to the simple distance based only in intensity values [Eq. (10)]. An example is shown Fig. 3. This phenomenon of preference for the diagonal pixel gradually disappears with a high number of termites and with the participation of the poison.
In the TSP problem, all the metaheuristics attempt to find the optimal solution. In the field of spatial color algorithms (SCAs),26 the optimal solution depends on the task of the algorithm. In the work that we are presenting, the goal of the filtering is a qualitative emulation of the HVS for an unsupervised image enhancement.
TR is a novel method to explore the image content alternative to Brownian randomness. Tuning the TR parameters properly can make the termites’ paths similar to Brownian method; however, regarding this similarity, we would like to highlight two important points.
1. TR is an MI-Retinex implementation that differs from the original Retinex and also from the version by Montagna and Finlayson19 and does not need to travel across the whole set of pixels in the image.
2. The poison is a feature that prevents the paths from a complete randomness since it affects locality and can be used as a tuning parameter in order to obtain different spatial effects.
In the case of TR, choosing the number of termites and the length of their path is a trade-off between the computational cost of the algorithm and the locality of the filtering. Introducing too many termites and paths that are too long may lead to a higher computational cost. Moreover, as we are interested in finding a local reference white and not the global white of the image, a termite should never touch all the pixels of the image. On the other side, paths that are too short can be a constraint on the locality, and too few termites due to insufficient image sampling can lead to a high chromatic noise. Examples of results using different spatial investigations are shown in Figs. 4 and 5. In general, a large number of termites traveling for a long path (number of pixels ) is needed in order to investigate a wide neighborhood for searching the local reference white. In the examples of Figs. 4 and 5, it can be noticed that overincreasing results in a loss of the local effect, as evidenced by the light background in the details bottom right that is darker than the one above and the one on the left, both with a lower sampling.
The poison and the weight , which control the divergence of the swarm, are also essential for investigation: low values of strongly enforce termites to choose different directions from each other, while high values of make termites converge. An example of the behavior of the swarm with different values of and with constant quantity of poison is shown in Fig. 6, while an example of constant values of and and increasing quantity of poison in steps of a factor of 10 from to 1 is shown in Fig. 7. A preliminary test among few people was run just too quickly preset the value. The presence versus the absence of halos was the chosen criterion that led to the use of value 1. In fact, in Fig. 7, it is easy to notice that low values of introduce halos in the filtered image.
A rule of thumb derived from a small sampling from a previous investigation suggests that of the length of the diagonal of the image results in a good score in observers’ image quality preferences.28,29 Regarding , , and , the suggested starting values are 0.1, 0.9, and 1, respectively. We underline to the reader that the parameters , , and do not change during pixel recomputation; they are kept constant for the whole processing of the image.
As a result of more comprehensive set of experiments, we can confirm this rule of thumb as a starting value for the parameter setting. Since the choice of parameters is affected by the image content, a finer tuning could be necessary. We remind that these settings mean that the poison has very low importance, while the closeness has very high importance. This causes a termite to simply choose a pixel based on its closeness even if it has been previously visited by another termite, resulting in a milder change in contrast.
The computational complexity of the original ACS proposed by Dorigo et al.20 is , where is the number of ant cycles and is the number of cities in an instance of the TSP problem. Despite its higher computational complexity, the ACS reaches the optimal solution of the TSP problem in a shorter computational time than other heuristics.30 In our case, the ant cycle is not necessary because we do not need to converge to an optimal solution, and furthermore, at each pixel recomputation, each termite does not have to touch all the pixels. As a consequence, the computational complexity of the Termite Retinex is given by18 or STRESS,2 which have a computational complexity of , where is the number of iterations, is the number of samples, and is the number of pixels in the image.
As each pixel recomputation is independent from each other, and termites can be seen as autonomous coworkers, TR has been implemented in compute unified device architecture (CUDA) to exploit parallel computing on GPU. This leads to a gain in speed of approximately a factor of 60 with respect to a CPU-based implementation. The performances have been tested on Intel i3-2310M with 4.0 GB of RAM, Windows 7 64 bit and a GeForce GT 540M as GPU. With this configuration, which is just an entry-level configuration for home use, whose performances are very different from a typical high-level laboratory configuration,31 TR takes to process a image with the rule of thumb mentioned above.
TR and Color Constancy
The scientific discussion about color constancy (CC) started in the late 19th century with the study of the appearances of objects in different illuminations. In 1872, Hering wrote: “The approximate constancy of the colors of seen objects, in spite of large quantitative or qualitative changes of the general illumination of the visual field, is one of the most noteworthy and most important facts in the field of physiological optics. Without this approximate constancy, a piece of chalk on a cloudy day would manifest the same color as a piece of coal does on a sunny day, and in the course of a single day it would have to assume all possible colors that lie between black and white.”32 As it can be noticed from this quote, the relation between the physics of light and the visual appearance it produces has a long scientific history.
In digital imaging literature, two main different approaches to CC can be found according to their goal in modeling this phenomenon: computer vision CC (in some scholar work referred as computational CC, but we prefer to refer it as CV CC since both CCs have computational aspects) and human vision CC (HV CC). They have distinct goals, different kind of outcomes are expected, and different measures of performance are required.
CV CC has the goal of separating illuminant from reflectance or alternatively estimating the physical reflectance of objects in different illuminants, or alternatively estimating the illuminant spectral or colorimetric component. Separating reflectance from the illuminant in the color signal (reflectance illumination) is a well-known ill-posed problem;33,34 thus these algorithms need constraints or assumptions on the scene content, illumination, or geometry. In the case of reflectance estimation, the measurement of the error could be the difference at each wavelength between the actual measured surface reflectance and the estimated one, but this is not practical and dependent on the devices involved. Thus, the scaled integrated reflectance or its chromatic coordinates is often used. As well, in the case of illuminant estimation, the correlated color temperature or its chromatic coordinates is used. In any case, CV CC aims to totally cancel the interaction between reflectance and illumination. For a detailed overview on CV CC, the reader can refer to Ref. 35.
In HV CC, illuminant component is not totally canceled; it generates appearances that are close to reflectance, but show significant departures from reflectance. These departures serve as important signatures of the underlying visual mechanisms.8 Algorithms belonging to the Retinex family, and thus TR, share this approach and attempt to mimic the response of human vision.
These two approaches to CC start from the same scientific history and have common points and differences. Both approaches introduce a sort of normalization with regard to the illuminant but can differ in the estimated pixel output according to the use of spatial arrangement of the scene. CV CC aims at computing reflectance and HV CC aims at computing appearance. These two different outputs are sometimes considered identical. This comes from early experiments that proved that appearance correlates with scaled integrated reflectance,36 but this has been found to hold true only for flat surfaces in uniform illumination.37,38 There are many examples in which human appearance does not correlate with reflectance.39 The simplest example is simultaneous contrast: HV CC reports different appearance of grays on white and black surrounds, while CV CC has to report these grays as identical.8 For many years, these two variables, reflectance and appearance, have been treated as a unique correlated feature. This has been the incorrect assumption in many cases of weak differentiation between CV CC and HV CC. Moreover, considering these two approaches as similar has led to simplified assumption about vision, in some cases useful for CV CC, but unrealistic for HV CC.
The first HV CC algorithm has been Retinex by Land and McCann.5 In the original Retinex algorithm and in all its derived versions, the spatial locality of the filtering is dependent on the image content and on the way the image is explored. As presented in the above sections, TR can be regarded as a tool to investigate locality.
In 1983, Land retired as Polaroid Chairman of the Board and presented the first departure from the original Retinex model. He simplified the algorithm and lost some of its most powerful properties. In these latter papers, Land describes two versions: the first was the same as Land and McCann6 but without the reset40 and the second calculates a designator8 driven by the average pixel values.41 The first used a series of paths that began in the surround and traveled to a central pixel of interest. Since each path did not reset, it used the average of pixel values as a way of normalizing the output to the maxima in each waveband. Thus, the calculation became a Gray World comparison, instead of the White Patch behavior of the original Retinex. The paper discussed calculating color appearances found in a flat color Mondrian uniformly illuminated. The designator of the 1986 paper calculates the ratio of a central area to an extended fixed surround. This meant that the threshold operation was replaced by averaging over a large area, and the Gray World average in 1983 was replaced with local-average dependence in 1986. Land emphasized that the designator was still the three-channel Retinex model of color.
These two variants were easier to formalize and consequently simpler to implement; this gave rise to a renewed interest about Retinex, starting from the 1997 work from NASA.42 Following Land 1986 and the derived NASA implementation, this local averaging approach has had a good success, obtaining interesting color normalization results, mainly without dealing with the problem of visual appearance.
HV CC can be of inspiration for CV CC algorithms, such as Ebner’s work.43 This relevant work in the field of CV CC starts with a clear differentiation between the two kinds of CC, while at the same time presenting some similar features. It is based on local space averaging as Land designator, and it addresses the problem of high computational cost with a parallel implementation. Parallel and multilevel implementations are useful ways to get closer to the amazing efficiency of the human vision system. It also differs from the classic CV CC evaluation methods presented above since it uses an object recognition task, a method also used in similar applications of HV CC algorithms.44
Qualitative and quantitative measurements of how accurately HV CC algorithms are able to predict the HVS visual appearance should be the metric for HV CC algorithms.26 For a correct quantitative evaluation, any model of vision has strict requirements concerning calibration of input information; however, calibrating the input image is a delicate process that cannot be done with generic images acquired in unknown conditions. Thus, in many cases, these algorithms are used as image enhancers. Among the many image enhancers available in the literature, the algorithms like TR, inspired by the original Retinex and MI-Retinex models, have some interesting properties. Basically, they behave as edge enhancer and gradient suppressors, whose intensities and localities depend on the chosen parameters. Regarding these algorithms being used as image enhancers, tests have proven that a filtering that goes qualitatively in the direction of the human visual appearance in the major part of the cases increases the user preferences.4546.–47 For this reason and since we present TR as an alternative formalization of RSR and other MI-Retinex implementations, we have tested TR performances as described in the following section.
Test Results and Discussion
Since the perceived quality of two images and the perception of single attributes, such as contrast or noise, are not influenced by the environment in which they are observed,48,49 two experiments in uncontrolled environments with human observers were performed in order to evaluate the quality of TR. A set of nine images displayed in an sRGB color space, chosen following the recommendations from Refs. 50 and 51, were evaluated in a pairwise comparison for both experiments, on a neutral gray background by a total of 20 observers. All the participants were recruited from the computer science field with most of them having knowledge of image processing.
In the first experiment, each image was processed using TR and was compared to its original. Observers were asked to choose one of the images based on their overall preference. No indications of any image quality attribute were given to the participants.52 Most of the participants of this first experiment also performed the second experiment.
In the second experiment, each image processed using TR was compared to the same image processed using RSR. In the first task, the observers were asked to choose the image according to their overall preference, while in the second task, they were asked to choose the image according to their preference only in terms of perceived noise. All the participants for this second experiment performed both the first and second tasks. This second experiment was designed with the purpose of evaluating the path-based sampling mechanism of TR against a spray-based one such as RSR.
Figures 8 and 9 show the nine original images in the middle, the corresponding processed by TR on the right, and the corresponding processed by RSR on the left. Figure 10 shows different details of Fig. 6. Figure 11 shows the preference of the 20 observers on the tested images for the first experiment. It can be noticed that TR succeeds on all the images, with three of them having a preference equal to 100%. A sign-test at 95% confidence interval shows that TR is significantly better than the original. The sign-test is a nonparametric statistical test that is a useful alternative to the familiar two-sample t-test in the case where the data do not follow the normal distribution.
Figure 12 shows the overall preference of the 20 observers in the second experiment, where TR was compared to RSR. TR is preferred for all the nine tested images. Figure 13 shows the preference in terms of perceived noise of the 20 observers for TR and RSR. TR is able to render less noisy scenes for all the images with respect to RSR except for Fig. 2, where the preferences are tied. A sign-test at 95% confidence interval shows that TR is significantly better than RSR. Furthermore, the same test shows that TR is able to process images with higher quality and less noise with respect to RSR. In conclusion, from these tests, we can suggest TR as new effective version of path-based Retinex with the particular novelty of swarm intelligence behavior.
Properties of TR
Retinex is a white patch algorithm8 and TR follows the same behavior. The brighter areas in the image are mapped toward white, and this is performed locally in a way that is edge-preserving. Furthermore, like other SCAs,26 TR tends to produce images whose histograms are flatter than those of the originals. It also performs automatic color correction (Fig. 14) and dynamic range maximization if starting from a low dynamic range image (Fig. 15). In case of high dynamic range images, like other SCAs, TR can be used directly as a local tone-rendering operator. Examples are shown in Fig. 16.
As mentioned in Sec. 4.2, TR has been implemented in CUDA, like it has been done for other SCAs. In this case, another interesting issue to consider is the memory , which affects if a termite can revisit a pixel and then choose another direction. As the memory is a tabu list associated to each termite , memory overhead may occur for a large number of termites and a long path.
A test on the same nine images shows that by disabling the memory , which simply means not recording in the tabu list which pixels the ’th termite has visited and allowing it to walk through them again (Fig. 17), TR renderings are similar to the ones with memory active. An example is shown in Fig. 18. The differences shown in Fig. 18(c) are calculated using the Euclidean color difference formula for small-medium color differences in log-compressed Optical Society of America Uniform Color Space (OSA-UCS) space (),53,54 which reports highest color differences around 4.0, which in terms of image differences are perceptual, but acceptable differences55 to present to the observers. No particular difference was reported from the participants in terms of perceived quality and noise. As benefit, the computational load decreases and a further gain in speed is achieved. However, the memory can be used as a tuning parameter in order to obtain slightly different spatial effects.
We have developed a novel implementation of Retinex, reconsidering the idea of the paths and using an existing swarm intelligence model inspired from a biological process. This new algorithm named TR has been originated from the modification of the ACS model proposed by Dorigo et al.20 In this case, the purpose of TR is not the optimization of some constraints but an exploration of the image content tuned, in particular, by two parameters, and , which weight the relative importance of the so-called poison and of the so-called closeness. Results report low importance of the poison and high importance of the closeness, which causes the termite swarm to concentrate to a particular region of an image.
We have carried out two perceptual experiments in order to evaluate the quality of TR. A first experiment on nine images with 20 observers confirms the efficacy of the method on all the tested images in comparison to the original. A sign-test at 95% confidence interval shows that images processed with TR are significantly better than the original images. A second experiment shows that the overall performance of TR is higher than RSR, and a sign-test at 95% confidence interval confirms this statement.
In conclusion, we have presented a novel effective version of path-based Retinex with the particular novelty of swarm intelligence behavior.
This work has been funded by the Research Council of Norway over the SHP project. The authors would like to thank Marius Pedersen and Jon Yngve Hardeberg (Gjøvik University College) for their useful feedback and suggestions.
Gabriele Simone received his bachelor of information technology in 2005 and master of information science and technology degree in 2007, both at University of Milan, Department of Information Technology, Italy. He is currently pursuing his PhD in color imaging at University of Oslo, and he was a member of The Norwegian Colour and Visual Computing Laboratory at Gjøvik University College and with main research topics contrast measure, image difference metrics, and tone mapping algorithms in HDR images.
Giuseppe Audino received his bachelor of digital communication degree in 2009 and master of information technology for communication degree in 2012, both at University of Milan, Department of Computer Science, Italy. He was a member of the The Norwegian Colour and Visual Computing Laboratory at Gjøvik University College in 2011, and his main research topic is swarm intelligent methods for image processing and code optimization using GPU programming.
Ivar Farup received his MSc degree in physics from the Norwegian University of Science and Technology, Trondheim, Norway, in 1994 and his PhD in applied mathematics from the University of Oslo, Oslo, Norway, in 2000. He is currently a full professor at Gjøvik University College, Norway, mainly focusing on color science and image processing.
Fritz Albregtsen is Cand. Real. from Department of Theoretical Astrophysics, University of Oslo, 1978. He has been with the Department of Informatics, University of Oslo, since 1983, as professor of digital image processing since 1997. He has coauthored more than 150 peer-reviewed research papers. His main research activities are at present analysis medical microscopy images and automatic segmentation of medical images. In addition, he is working on general quantitative metrics for image quality.
Alessandro Rizzi is an associate professor at the Department of Computer Science, University of Milano, teaching fundamentals of digital imaging, multimedia video, and human–computer interaction. He is one of the founders of the Italian Color Group and a member of several program committees of conferences related to color and digital imaging. Since 1990, he is researching in the field of digital imaging and vision. He is particularly interested in the perceptual issues related with digital imaging and lighting.