1.

Introduction

Colorization is a process to assign three dimensional color values to gray pixels, and this technique enables the conversion of black and white image and films into colored ones.^{1, 2, 3, 4} However the design of such a mapping is ambiguous in nature, and an interactive system was proposed in Ref. 1. In this approach, users are required to provide colors to some regions, and colors on the other regions are estimated by solving an optimization problem. Based on the same scenario, an algorithm using chrominance blending was proposed in Ref. 2. It shows similar or even better visual quality with less computations (see Fig. 1 to see the input and the output of this scenario). However, color bleeding is sometimes observed in these approaches probably due to the lack of global considerations. In other words, conventional approaches^{1, 2, 3} are based on the assumption of locality, which can be summarized as “homogeneity of luminance indicates homogeneity of chrominance.” Therefore they have difficulties in handling points distant from scribbles, and the users need to provide a sufficient number of scribbles not only to detailed regions but also to relatively homogeneous regions in order to prevent color bleeding.

Fig. 1

Experimental results on a real image. (a) Input image with scribbles, (b) result of Ref. 1, (c) result of Ref. 2, (d) result of the proposed method.

In this paper, rather than depending on the locally valid assumption, we propose a new colorization method based on a well-developed soft segmentation method. That is, we blend chrominance values where the blending weights are determined by the random walker algorithm.⁵ Since the random walker method considers image structure and works well (with large probability transition) even for weak and noisy boundaries, the proposed colorization provides sharp color changes on object boundaries even if they are far from scribbles.

2.

Chrominance Blending

Let us denote the set of user's scribbles as Ω, and the set of scribble chrominance as [TeX:] \documentclass[12pt]{minimal}\begin{document}$\mathcal {C} \left( \Omega \right)$\end{document}$\mathcal{C}\left(\Omega \right)$. Also, let Y(r) be a given luminance value of a pixel r, and U(r) be a nonexistent chrominance value of r that has to be estimated based on the Y(r) and user scribbles. For example, U(r) can be Cb or Cr component in the YCbCr color space.² If we consider the colorization as an minimum mean square error estimation problem, the estimated chrominance value at r is given by

3.

Soft Segmentation Using the Random Walker Algorithm

For better colorization performance, it is desired that P[U(r) = c|Ω] reaches 0 or 1 in a coherent region, and sharp changes occur across object boundaries. Since the random walker algorithm for soft segmentation has these properties,^{5, 6} we adopt the method for colorization. Specifically, P[U(r) = c|Ω] is defined as the probability that a random walker starting from r reaches one of the user-provided points whose chrominance is c. Fortunately, there is an analytic and efficient method to find these probabilities.^{5, 7} Note that the random walker algorithm was also used in estimating optimized parameters in alpha matting, which is a similar problem as colorization in that the blending weight is estimated.⁶ In our approach, the pixels are considered as nodes and the weight of the edge that connects two neighboring pixels (i and j) is defined as

4.

Experimental Results

Figure 1 shows an experimental result on a natural image. The input image and user scribbles are available in Ref. 8. If we use all scribbles provided in Ref. 8, the results of three algorithms^{1, 2} are almost the same. Hence, to compare the robustness of the colorization algorithms, we remove some scribbles as in Fig. 1. With Fig. 1 as the input, the existing algorithms show some color bleeding as observed in Figs. 1 and 1 (see bottom right of each image and the boy's chin), whereas the proposed method still works robustly as can be seen in Fig. 1. The enlarged results are shown in Fig. 2. The result images and other examples that show the robustness of our method can be found at http://ispl.snu.ac.kr/hikoo/colorization/.

Fig. 2

Enlarged results of Fig. 1. (a) Result of Ref. 1, (b) result of Ref. 2, (c) result of the proposed method.

5.

Conclusion

In this paper, we have presented a new colorization method based on a soft segmentation technique. Although conventional methods show satisfying results when a user makes a sufficient number of scribbles, they sometimes have shown color bleeding in the regions distant from the scribbles. This problem is alleviated by employing the random walker method, which considers image structures.