Colorization based on soft segmentation

Hyung-Il Koo; Nam-Ik Cho

doi:10.1117/1.3565470

1 January 2011 Colorization based on soft segmentation

Hyung-Il Koo, Nam-Ik Cho

Author Affiliations +

J. of Electronic Imaging, 20(1), 010502 (2011). https://doi.org/10.1117/1.3565470

Abstract

This paper proposes a new colorization method based on the chrominance blending. The weights for the blending are computed by using the random walker algorithm, which is a soft segmentation technique that provides sharp probability transition on object boundaries. As a result, the proposed method reduces color bleeding and provides improved colorization performances compared to conventional ones.

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} $C (Ω)$ . 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

1

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

\hat{U} (r) = E {U (r) | Ω} .

Here, we assume that chrominance values are almost constant within the same material and the user provides chrominance of all materials in the picture [i.e., U(r) ∈ C(Ω) for all r]. Then [TeX:] \documentclass[12pt]{minimal}\begin{document}$\hat{U}(r)$\end{document}

\hat{U} (r)

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}

\hat{U} (r) = \sum_{c \in C (Ω)} c \times P [U (r) = c | Ω],

where 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 C (Ω)

. 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.⁵ 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.⁶ 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_{i j} = \exp [- β {[Y (i) - Y (j)]}^{2}],

where β is a constant. Then the random walker algorithm provides the probability 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 [x] = \frac{1}{2} \sum_{e_{i j}} w_{i j} {(x_{i} - x_{j})}^{2}

with the constraints that x_i = 1 for all pixels with label c and x_i = 0 for all pixels whose label is not c (on the defined region). Finally, [TeX:] \documentclass[12pt]{minimal}\begin{document}$\hat{U}(r)$\end{document}

\hat{U} (r)

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

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.

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

References

1. A. Levin, D. Lischinski, and Y. Weiss, “Colorization using optimization,” ACM Trans. Graphics, 23(3) (2004) 10.1145/1186562.1015780. Google Scholar

2. L. Yatziv and G. Sapiro, “Fast image and video colorization using chrominance blending,” IEEE Trans. Image Process. 15(5) 1120–1129 (2006). 10.1109/TIP.2005.864231 Google Scholar

3. Y. Chen and S. Wang, “Image colorization with edge detection and sub-sampling,” in Proc. Int. Congr. on Image and Signal Processing (CISP), 16–18 October 2010, Yantai (2010). Google Scholar

4. V. G. Jacob and S. Gupta, “Colorization of grayscale images and videos using a semiautomatic approach,” in Proc. IEEE Int. Conf. on Image Processing (ICIP), November 2009, Cairo (2009). Google Scholar

5. L. Grady, “Random walks for image segmentation,” IEEE Trans. Pattern Anal. Mach. Intell. 28(11), 1768–1783 (2006). 10.1109/TPAMI.2006.233 Google Scholar

6. J. Wang and M. F. Cohen, “Optimized color sampling for robust matting,” in Proc. Int. Conf. on Computer Vision and Pattern Recognition, June 2007, Minneapolis (2006). Google Scholar

7. L. Grady and A. K. Sinop, “Fast approximate random walker segmentation using eigenvetor precomputation,” in Proc. IEEE Int. Conf. on Computer Vision and Pattern Recognition, 23–28 June 2008, Anchorage (2008). Google Scholar

8. http://www.cs.huji.ac.il/yweiss/Colorization/ Google Scholar

Citation Download Citation

Hyung-Il Koo, Hyung-Il Koo, Nam-Ik Cho, Nam-Ik Cho, } "Colorization based on soft segmentation," Journal of Electronic Imaging 20(1), 010502 (1 January 2011). https://doi.org/10.1117/1.3565470 . Submission:

JOURNAL ARTICLE
3 PAGES

DOWNLOAD PDF + SAVE TO MY LIBRARY