## 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.

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.^{5} 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.^{2} If we consider the colorization as an minimum mean square error estimation problem, the estimated chrominance value at *r* is given by

## 1

[TeX:] \documentclass[12pt]{minimal}\begin{document} \begin{equation} \hat{U}(r) = \mathbf {E} \lbrace U(r) | \Omega \rbrace . \end{equation} \end{document}$$\widehat{U}\left(r\right)=\mathbf{E}\left\{U\left(r\right)\right|\Omega \}.$$*U*(

*r*) ∈

*C*(Ω) for all

*r*]. Then [TeX:] \documentclass[12pt]{minimal}\begin{document}$\hat{U}(r)$\end{document}$\widehat{U}\left(r\right)$ in Eq. 1 is given by the weighted sum of the user-provided chrominance values:

## 2

[TeX:] \documentclass[12pt]{minimal}\begin{document} \begin{equation} \hat{U}(r) = \sum _{ c \in \mathcal {C} \left( \Omega \right) } c \times P[ U(r) = c | \Omega ], \end{equation} \end{document}$$\widehat{U}\left(r\right)=\sum _{c\in \mathcal{C}\left(\Omega \right)}c\times P[U\left(r\right)=c|\Omega ],$$*P*[

*U*(

*r*) =

*c*|Ω] means the probability that the chrominance value at a pixel

*r*is [TeX:] \documentclass[12pt]{minimal}\begin{document}$c \in \mathcal {C} \left( \Omega \right)$\end{document}$c\in \mathcal{C}\left(\Omega \right)$. In this formulation, the colorization problem is equivalent to compute

*P*[

*U*(

*r*) =

*c*|Ω]. In Ref. 2, the probability was computed based on the minimum intrinsic distance (on the luminance image) between

*r*and user scribbles. Although this approach works well, the performance degrades as user scribbles are distant from

*r*. Precisely, it cannot distinguish two distances of a long path passing low contrast region and a short path passing high contrast boundary, although the former is more likely to be the path in the same region. This ambiguity brings color bleeding in the regions distant from user's scribbles. In order to address this problem, we present a new colorization approach based on a soft segmentation technique, i.e., we compute

*P*[

*U*(

*r*) =

*c*|Ω] with the random walker algorithm.

^{5}Since our approach can consider image structures, it can provide visually pleasing results with less scribbles. Also, due to the nature of soft segmentation, the method can handle complex regions naturally as illustrated in Sec. 4.

## 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.^{6} 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

## 3

[TeX:] \documentclass[12pt]{minimal}\begin{document} \begin{equation} w_{ij} = \exp [ -\beta \left[Y(i) - Y(j) \right]^2], \end{equation} \end{document}$${w}_{ij}=\mathrm{exp}[-\beta {\left[Y\left(i\right)-Y\left(j\right)\right]}^{2}],$$*P*[

*U*(

*r*) =

*c*|Ω] for all

*r*in the image by minimizing

## 4

[TeX:] \documentclass[12pt]{minimal}\begin{document} \begin{equation} D[x] = \frac{1}{2} \sum _{e_{ij}} w_{ij} (x_i - x_j)^2 \end{equation} \end{document}$$D\left[x\right]=\frac{1}{2}\sum _{{e}_{ij}}{w}_{ij}{({x}_{i}-{x}_{j})}^{2}$$*x*

*= 1 for all pixels with label*

_{i}*c*and

*x*

*= 0 for all pixels whose label is not*

_{i}*c*(on the defined region). Finally, [TeX:] \documentclass[12pt]{minimal}\begin{document}$\hat{U}(r)$\end{document}$\widehat{U}\left(r\right)$ for each pixel is obtained from Eq. 2 by using

*P*[

*U*(

*r*) =

*c*|Ω] =

*x*

*.*

_{r}## 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/.

## 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.

## Acknowledgments

This research was supported by The Ministry of Knowledge Economy, Korea, under the Information Technology Research Center support program supervised by the National IT Industry Promotion Agency (Grant No. NIPA-2010-(C1090-1011-0003)).