JEI Letters

Colorization based on soft segmentation

[+] Author Affiliations
Hyung-Il Koo, Nam-Ik Cho

Seoul National University, Department of EECS, Seoul, Republic of Korea

J. Electron. Imaging. 20(1), 010502 (March 22, 2011). doi:10.1117/1.3565470
History: Received May 09, 2010; Accepted February 10, 2011; Revised February 04, 2011; Published March 22, 2011; Online March 22, 2011
Text Size: A A A

Open Access Open Access

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.

Figures in this Article

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.14 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 approaches13 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.

Graphic Jump LocationF1 :

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

Let us denote the set of user's scribbles as Ω, and the set of scribble chrominance as

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.2 If we consider the colorization as an minimum mean square error estimation problem, the estimated chrominance value at r is given by Display Formula
1Û(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 Û(r) in Eq. 1 is given by the weighted sum of the user-provided chrominance values: Display Formula
2Û(r)=cCΩc×P[U(r)=c|Ω],
where P[U(r) = c|Ω] means the probability that the chrominance value at a pixel r is cCΩ. 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.

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,56 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 Display Formula

3wij=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 Display Formula
4D[x]=12eijwij(xixj)2
with the constraints that xi = 1 for all pixels with label c and xi = 0 for all pixels whose label is not c (on the defined region). Finally, Û(r) for each pixel is obtained from Eq. 2 by using P[U(r) = c|Ω] = xr.

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

Graphic Jump LocationF2 :

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

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.

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. UNSPECIFIED NIPA-2010-(C1090-1011-0003) ).

Levin  A., , Lischinski  D., , and Weiss  Y., “ Colorization using optimization. ,” ACM Trans. Graphics. , 23, (3 ) ((2004)).
Yatziv  L., and Sapiro  G., “ Fast image and video colorization using chrominance blending. ,” IEEE Trans. Image Process.. 15, (5 ) 1120–1129  ((2006)).
Chen  Y., and Wang  S., “ Image colorization with edge detection and sub-sampling. ,” in  Proc. Int. Congr. on Image and Signal Processing (CISP). , 16–18 October 2010, Yantai ((2010)).
Jacob  V. G., and Gupta  S., “ Colorization of grayscale images and videos using a semiautomatic approach. ,” in  Proc. IEEE Int. Conf. on Image Processing (ICIP). , November 2009, Cairo ((2009)).
Grady  L., “ Random walks for image segmentation. ,” IEEE Trans. Pattern Anal. Mach. Intell.. 28, (11 ), 1768–1783  ((2006)).
Wang  J., and Cohen  M. F., “ Optimized color sampling for robust matting. ,” in  Proc. Int. Conf. on Computer Vision and Pattern Recognition. , June 2007, Minneapolis ((2006)).
Grady  L., and Sinop  A. K., “ 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)).
© 2011 SPIE and IS&T

Citation

Hyung-Il Koo and Nam-Ik Cho
"Colorization based on soft segmentation", J. Electron. Imaging. 20(1), 010502 (March 22, 2011). ; http://dx.doi.org/10.1117/1.3565470


Figures

Graphic Jump LocationF2 :

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

Graphic Jump LocationF1 :

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.

Tables

References

Levin  A., , Lischinski  D., , and Weiss  Y., “ Colorization using optimization. ,” ACM Trans. Graphics. , 23, (3 ) ((2004)).
Yatziv  L., and Sapiro  G., “ Fast image and video colorization using chrominance blending. ,” IEEE Trans. Image Process.. 15, (5 ) 1120–1129  ((2006)).
Chen  Y., and Wang  S., “ Image colorization with edge detection and sub-sampling. ,” in  Proc. Int. Congr. on Image and Signal Processing (CISP). , 16–18 October 2010, Yantai ((2010)).
Jacob  V. G., and Gupta  S., “ Colorization of grayscale images and videos using a semiautomatic approach. ,” in  Proc. IEEE Int. Conf. on Image Processing (ICIP). , November 2009, Cairo ((2009)).
Grady  L., “ Random walks for image segmentation. ,” IEEE Trans. Pattern Anal. Mach. Intell.. 28, (11 ), 1768–1783  ((2006)).
Wang  J., and Cohen  M. F., “ Optimized color sampling for robust matting. ,” in  Proc. Int. Conf. on Computer Vision and Pattern Recognition. , June 2007, Minneapolis ((2006)).
Grady  L., and Sinop  A. K., “ 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)).

Some tools below are only available to our subscribers or users with an online account.

Related Content

Customize your page view by dragging & repositioning the boxes below.

Related Book Chapters

Topic Collections

PubMed Articles
Advertisement
  • Don't have an account?
  • Subscribe to the SPIE Digital Library
  • Create a FREE account to sign up for Digital Library content alerts and gain access to institutional subscriptions remotely.
Access This Article
Sign in or Create a personal account to Buy this article ($20 for members, $25 for non-members).
Access This Proceeding
Sign in or Create a personal account to Buy this article ($15 for members, $18 for non-members).
Access This Chapter

Access to SPIE eBooks is limited to subscribing institutions and is not available as part of a personal subscription. Print or electronic versions of individual SPIE books may be purchased via SPIE.org.