Colorization by classifying the prior knowledge

DU Weiwei

(Department of Information Science，Kyoto Institute of Technology，Kyoto，Japan 606－8585)

Colorization by classifying the prior knowledge

DU Weiwei

(Department of Information Science，Kyoto Institute of Technology，Kyoto，Japan 606－8585)

When a one－dimensional luminance scalar is replaced by a vector of a colorful multi－dimension for every pixel of a monochrome image，the process is called colorization.However，colorization is under－constrained.Therefore，the prior knowledge is considered and given to the monochrome image.Colorization using optimization algorithm is an effective algorithm for the above problem.However，it cannot effectively do with some images well without repeating experiments for confirming the place of scribbles.In this paper，a colorization algorithm is proposed，which can automatically generate the prior knowledge.The idea is that firstly，the prior knowledge crystallizes into some points of the prior knowledge which is automatically extracted by downsampling and upsampling method.And then some points of the prior knowledge are classified and given with corresponding colors.Lastly，the color image can be obtained by the color points of the prior knowledge.It is demonstrated that the proposal can not only effectively generate the prior knowledge but also colorize the monochrome image according to requirements of user with some experiments.

colorization;prior knowledge

When a one－dimensional luminance scalar is replaced by a vector of a colorful multi－dimension for every pixel of a monochrome image，the process is called colorization.However，colorization is under－constrained.Consequently，there is more than one result of colorization.In order to solve this problem，some reasonable constraints should be given.

A color image has some reasonable constraints for transferring its colors to the monochrome image.There are several representative algorithms，such as Welsh’s semi－automatic colorization algorithm［1］.It transfers colors originating from a color image to the greyscale image.However，there is no guarantee of the continuity of the colors in space because of a local algorithm.Some types of colorful handwritten scribbles(Fig.4(a))are also considered to be reasonable constraints.Additionally，representative global colorization algorithms exist such as Levin’s algorithm［2］，which is a colorization using optimization one.The basic idea behind this algorithm is that neighboring pixels in space and time which have similar intensities should have similar colors.The indicated colors are propagated in both space and time to produce a fully colorized image.Levin’s algorithm colorizes the monochrome image in the context of not directly segmenting it to various regions.Therefore，it is an effective algorithm for some monochrome images.However，it cannot effectively colorize some images，such as the one seen in the Fig.5(a)，without repeating experiments for confirming the place of scribbles.Moreover，Ref.［3］presented the colorization algorithm based on Ref.［2］，but an example image must also be segmented.

Another area of focus is how to get a colorization algorithm without segmentation of an image and scribbles by the user.A colorization algorithm is proposed which can automatically generate the prior knowledge based on Ref.［4］.Ref.［4］obtained the distance of colors by repeating the Ref.［2］’s method for extracting landmark pixels，while the distance of luminance was obtained by classification of extracting landmark pixels.The proposed algorithm is shown below.First，the prior knowledge crystallizes into several points of the prior knowledge which are automatically extracted by the downsampling and upsampling methods.Then some points of the prior knowledge based on edge information are classified and give the points of the prior knowledge the corresponding colors.Lastly，the color image can be obtained by the color points of the prior knowledge.It is demonstrated that the proposal not only effectively generates the prior knowledge but also colorizes the monochrome image according to requirements of the user through various experiments.

1 A colorization algorithm by classfying the prior knowledge

The prior knowledge is defined as some points of the prior knowledge，and it is extracted from the monochrome image using downsampling，k－means［5］，and upsampling methods.The prior knowledge is made to crystallize into several points.Then the points of the prior knowledge are classified using Ward’s algorithm［6］.Finally，the color image can be obtained by colorizing the points of the prior knowledge of each cluster.

1.1 Generation of the prior knowledge

Let the prior knowledge crystallize into some points of the prior knowledge.In other words，to extract some representative pixels in an image automatically.It will cost much time if the representative pixels are extracted from an original image directly.Therefore，the purpose is to degrade the monochrome image to low resolution image.The initial representative pixels are extracted from the low resolution image using kmeans.And then upgrade the resolution image，and at the same time，raise the number of the representative pixels.Repeat the above process until the result is the same as the resolution of the original image.

A monochrome imageI0is given.Build a Gaussian pyramidI0，I1，…，Id，where，I0is the input monochrome image of the original image andIdis the coarsest level in the pyramid.Classify the coarsest level imageIdusing information on the value of each pixel and position of each pixel.K clusters are obtained using k－means.The centroid of each cluster is considered as the initial representative pixels.Let the set of the initial representative pixels beXd.The mean value is substituted for the values of all pixels of each cluster.Let the image be Φd.The residue image is obtained by Eq.(1)wheni=d.

The representative pixelsXd－1can be got from imageEd，Φd－1is obtained by segmentingId－1based on the setXd－1of representative pixels by K－nearest neighbors.The residue imageEd－1can be obtained by Eq.(1)，whenk=d－1.In this way，the representative pixelsX0are extracted from the imageI0.

Fig.1 Flowchart on process of generating the prior knowledge automatically

1.2 Classify the prior knowledge

Every point of the prior knowledge should be given with the corresponding information which is defined by color based on the purpose of this paper.However，many points of the prior knowledge are extracted from a monochrome image so that it is not able to colorize every one.Fortunately，some points of the prior knowl－edge have the same characteristics.So just classify the points of the prior knowledge as their characteristics，it can avoid a lot of trivial work.According to this idea，the points of the prior knowledge are classified into some clusters using Ward’s method based on edge information.That is，the clusters of similarity have the small sum of squares while the clusters of difference have the large sum of squares in Ward’s method based on edge information.Let the points of the prior knowledge of the same cluster have the same information，i.e.color.Just colorize a point of the prior knowledge of the same cluster manually，the same color will be obtained in the cluster from all points of the prior knowledge.

1.3 Colorization by the points of the prior knowledge

How to colorize the monochrome image using the colored points of the prior knowledge?Levin’s method is adopted as the algorithm that requires neither precise image segmentation，nor accurate region tracking.The basic idea of the algorithm is:if neighboring pixels in space and time have similar intensities，they should have similar colors.That is to say，when the monochromatic luminance channel Y are similar，the chrominance channels U and V are similar.YUV color space is used in video.

In a word，it is a process to solve the solution of a quadratic cost function in sparse system of linear equations.The handwritten colored scribbles are conditions of constraints in order to solve the problem of coloization.In this paper，the automatically extracted points of the prior knowledge substitute for the color scribbles as conditions of constraints.The color points of the prior knowledge are more effective than the color scribbles without repeating experiments for confirming the place of scribbles.

2 Steps of our algorithm

Fig.2 shows the process of algorithm.It is carried out according to the following procedure.

Fig.2 Flowchart on process of our proposal

1 Degrade an image to the low resolution image with downsampling method.

2)Classify the low resolution image for initial points of the prior knowledge which are called as representative pixels.

3)Substitute the mean value of each cluster for the values of all pixels and obtain the image Φ.

4)Obtain the residue imageEby‖I－Φ‖.

5)Segment the residue imageEwith small windows so that points of the prior knowledge are added with these windows.

6)Obtain the edges of the original image with Laplacian filter.

7)Classify points of the prior knowledge by Ward’s method.

8)Define the points of the prior knowledge of the same cluster to the same color manually.

9)Colorize the monochrome image by the defined colored points of the prior knowledge.

Repeat from 3)to 5)until the original image is obtained.After that，go ahead to 6)until a color image is obtained.

3 Experiments

The approach is effective based on the experiments of some images.

For reference，the origin image is given in Fig.3.Fig.4(a)shows the monochrome image with scribbles and its result with colorization from Ref.［2］.Draw some colored scribbles to the monochrome image freely like Fig.5(a).The result like Fig.4(b)could not be obtained，instead，F(xiàn)ig.5(b)was obtained.So it is known that it is not easy to get the result like Fig.4(b).Experiments should be done until the result like Fig.3(b)is obtained.Only by appropriately drawing the colored scribbles can Fig.3(b)be obtained.The proposal does not consider the above problem for comparison.The algorithm can generate some prior knowledge automatically like Fig.6(a).Just colorize the prior knowledge of each cluster and then the result like Fig.6(b)could be obtained.Some parameters of our proposal are given on Fig.6(b):the number of the points of the prior knowledge isc=300，threshold isT=20，the number of levels isd=5，the size of a small window ish=20，the number of clusters isn=100.Notice that it is easy to understand，the points of the prior knowledge are enlarged in Fig.6(a).Actually，a pixel expresses a point of the prior knowledge.

Fig.7(a)shows the monochrome image with scribbles and its result with colorization from Ref.［2］.Draw some colored scribbles to the monochrome image freely like Fig.8(a).Notice that the waterfall is given with light blue in Fig.7(a)which is shown at the enlarged part of Fig.8(a).The result like Fig.7(b)could not be obtained，instead，F(xiàn)ig.8(b)was obtained.So it can be known that it is not easy to get the result like Fig.7(b).Experiments should be done until the result like Fig.7(b)is obtained.Only by appropriately drawing the colored scribbles can Fig.7(b)be obtained.The proposal does not consider the above problem for comparison.The algorithm can generate some prior knowledge automatically like Fig.9(a).Just colorize the prior knowledge of each cluster and then the result like Fig.9(b)could be obtained.Moreover，as many colored scribbles need to be given manually，the error place is set easily such as on the left corner of Fig.7(a)while the problem did not happen in the proposal such as on the left corner of Fig.9(b).Some parameters of the proposal are given on Fig.9(b):the number of the points of the prior knowledge isc=700，threshold isT=20，the number of levels isd=4，the size of a small window ish=13，the number of clusters as the prior knowledge isn=25.

Some experiments were carried out to other images Fig.10(a)and Fig.11(a).Their results are shown in Fig.10(b)and Fig.11(b).

Fig.3 The origin images of a child

FIg.4 The child images with scribbled colors

Fig.5 The child images with scribbled colors at random

Fig.6 The child images with the prior knowledge

Fig.7 The waterfall images with scribbled colors

Fig.8 The waterfall images with scribbled colors at random

Fig.9 The waterfall images with prior knowledge

Fig.10 The candle images with the prior knowledge

Fig.11 The building images with the prior knowledge

4 Conclusions

This paper presents an effective colorization algorithm by automatically generating the priori knowledge from an image.A user can obtain a colorful image directly without repeatedly generating the prior knowledge.However，in this proposal a color has to be defined in the prior knowledge of each cluster manually.Therefore，automatically defining a color in the prior knowledge of each cluster is the subject of future research.

［1］WELSH T，ASHIKHIMIN M，MUELLER K.Transferring color to greyscale images［J］.ACM Transactions on Graphics，2002，21(3):277－280.

［2］LEVIN A，LISCHINSKI D，WEISS Y.Colorization using optimization［C］//Proceedings of ACM SIGGRAPH 2004.Los Angeles，USA，2004:689－694.

［3］IRONY R，COHEN－OR D，LISCHINSKI D.Colorization by example［C］//Proceedings of Eurographics Symposium on Rendering 2005.Aire－la－Ville，Switzerland，2005:201－210.

［4］HUANG T W，CHEN H T.Landmark－based sparse color representation for color transfer［C］//The 12th Computer Vision.Kyoto，Japan，2009:199－204.

［5］MCQUEEN J.Some methods for classification and analysis of multivariate observations［C］//Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability. ［S.l.］，1967:281－297.

［6］JOE H W.Hierarchical grouping to optimize an objective function［J］.Journal of the American Statistical Association，1963，58:236－244.

［7］JACK K.Video demystified［M］.3rd ed.Elsevier Science and Technology，2001:35－47.

［8］BURT P J，ADELSON E H.The Laplacian pyramid as a compact image code［J］.IEEE Trans Commun，1983，31(4):532－540.

About the authors:

DU Weiwei was born in 1978.She received PhD degree from Kyushu University in 2008，and now she is an asstistant professor at Kyoto Institute of Technology.Her current interests include fuzzy clusters and graph－spectral algorithms， and she has authored or co－authored several technical articles in journals and conference proceedings.

TP18

A

1673－4785(2011)06－0556－05

10.3969/j.issn.1673－4785.2011.06.012

Data:2011－08－15.

DU Weiwei.E－mail:duweiwei@dit.ac.jp.