第6卷第6期 智能系统学报 Vol.6 No.6 2011年12月 CAAI Transactions on Intelligent Systems Dec.2011 doi:10.3969/j.issn.16734785.2011.06.012 Colorization by classifying the prior knowledge DU Weiwei Department of Information Science,Kyoto Institute of Technology,Kyoto,Japan 606-8585) Abstract: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-con- strained.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 coloriza- tion 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 down- sampling 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 mono- chrome image according to requirements of user with some experiments. Keywords:colorization;prior knowledge CLC Number:TP18 Document code:A Article ID:1673-4785(2011)06-0556-05 When a one-dimensional luminance scalar is re-Levin's algorithm colorizes the monochrome image in placed by a vector of a colorful multi-dimension for ev- the context of not directly segmenting it to various re- ery pixel of a monochrome image,the process is called gions.Therefore,it is an effective algorithm for some colorization.However,colorization is under-constrain- monochrome images.However,it cannot effectively ed.Consequently,there is more than one result of col- colorize some images,such as the one seen in the Fig. orization.In order to solve this problem,some reason- 5(a),without repeating experiments for confirming the able constraints should be given. place of scribbles.Moreover,Ref.[3]presented the A color image has some reasonable constraints for colorization algorithm based on Ref.[2],but an exam- transferring its colors to the monochrome image.There ple image must also be segmented. are several representative algorithms,such as Welsh's Another area of focus is how to get a colorization semi-automatic colorization algorithm.It transfers algorithm without segmentation of an image and scrib- colors originating from a color image to the greyscale bles by the user.A colorization algorithm is proposed image.However,there is no guarantee of the continui- which can automatically generate the prior knowledge ty of the colors in space because of a local algorithm. based on Ref.[4].Ref.[4 ]obtained the distance of Some types of colorful handwritten scribbles (Fig.4 colors by repeating the Ref.[2]'s method for extrac- (a))are also considered to be reasonable constraints. ting landmark pixels,while the distance of luminance Additionally,representative global colorization algo- was obtained by classification of extracting landmark rithms exist such as Levin's algorithm,which is a pixels.The proposed algorithm is shown below.First, coloriation using optimization one.The basic idea be the prior knowledge crystallizes into several points of hind this algorithm is that neighboring pixels in space the prior knowledge which are automatically extracted and time which have similar intensities should have by the downsampling and upsampling methods.Then similar colors.The indicated colors are propagated in some points of the prior knowledge based on edge infor- both space and time to produce a fully colorized image. mation are classified and give the points of the prior Received Data:2011-08-15. knowledge the corresponding colors.Lastly,the color Corresponding Author:DU Weiwei.E-mail:duweiwei@dit.ac.jp. image can be obtained by the color points of the prior
第6期 DU Weiwei:Colorization by classfying the prior knowledge ·557. knowledge.It is demonstrated that the proposal not on- pixel is set to a window in the coarsest level image.c is ly effectively generates the prior knowledge but also colorizes the monochrome image according to require- he number of the representative pixels.Atmos ments of the user through various experiments. N presentative pixels will be added to small win- 1 A colorization algorithm by class- dows.k is the number of degrade/upgrade level in the fying the prior knowledge image.Based on the idea,h can be got by Eq.(2) The prior knowledge is defined as some points of the and Eg.(3).Set the same threshold to every small prior knowledge,and it is extracted from the mono- window.The value of the pixel should be memorized, chrome image using downsampling,k-means(3],and if the mean value of pixel of the small window is larger upsampling methods.The prior knowledge is made to than the threshold.Based on the experiments,the crystallize into several points.Then the points of the threshold is set at 30 when the number of representative prior knowledge are classified using Ward's algo- pixels is larger than 300,while the threshold is set at rithms.Finally,the color image can be obtained by 20 when the number of representative pixels is smaller colorizing the points of the prior knowledge of each than 300.It is difficult to get the representative pixels, cluster. if the threshold is too large.Otherwise,it will cost 1.1 Generation of the prior knowledge much time in order to extract many representative pix- els. Let the prior knowledge crystallize into some points of the prior knowledge.In other words,to ex- ∑MxN 台2h×2h=c, X (2) tract some representative pixels in an image automati- cally.It will cost much time if the representative pixels =1 h= (3) are extracted from an original image directly.There- fore,the purpose is to degrade the monochrome image The representative pixels X-1 can be got from image to low resolution image.The initial representative pix- E,is obtained by segmenting I-based on the els are extracted from the low resolution image using k- set X-of representative pixels by K-nearest neigh- means.And then upgrade the resolution image,and at bors.The residue image Ea-can be obtained by the same time,raise the number of the representative Eq.(1),when k=d-1.In this way,the representa- tive pixels Xo are extracted from the image /o. pixels.Repeat the above process until the result is the same as the resolution of the original image. A monochrome image lo is given.Build a Gaussi- an pyramid o,I,,I,where,lo is the input mono- chrome image of the original image and I is the coar- sest level in the pyramid.Classify the coarsest level image Ia using information on the value of each pixel and position of each pixel.K clusters are obtained u- sing k-means.The centroid of each cluster is consid- ered as the initial representative pixels.Let the set of the initial representative pixels be X.The mean value Fig.1 Flowchart on process of generating the prior is substituted for the values of all pixels of each clus- knowledge automatically ter.Let the image be Pa.The residue image is ob- 1.2 Classify the prior knowledge tained by Eq.(1)when i=d. Every point of the prior knowledge should be giv- E:=|1-Φ1. (1) en with the corresponding information which is defined Divide E into small windows like Fig.1.The size of by color based on the purpose of this paper.However, each window is h x h pixels.Suppose the size of the many points of the prior knowledge are extracted from a input image is Mx N pixels.Build a Gaussian pyramid monochrome image so that it is not able to colorize ev- with a scale factor 2.Suppose that one representative ery one.Fortunately,some points of the prior knowl-
.558. 智能系统学报 第6卷 edge have the same characteristics.So just classify the basic idea of the algorithm is:if neighboring pixels in points of the prior knowledge as their characteristics,it space and time have similar intensities,they should can avoid a lot of trivial work.According to this idea, have similar colors.That is to say,when the mono- the points of the prior knowledge are classified into chromatic luminance channel Y are similar,the chro- some clusters using Ward's method based on edge in- minance channels U and V are similar.YUV color formation.That is,the clusters of similarity have the space is used in video. small sum of squares while the clusters of difference In a word,it is a process to solve the solution of a have the large sum of squares in Ward's method based quadratic cost function in sparse system of linear equa- on edge information.Let the points of the prior knowl- tions.The handwritten colored scribbles are conditions edge of the same cluster have the same information, of constraints in order to solve the problem of coloiza- i.e.color.Just colorize a point of the prior knowledge tion.In this paper,the automatically extracted points of the same cluster manually,the same color will be of the prior knowledge substitute for the color scribbles obtained in the cluster from all points of the prior as conditions of constraints.The color points of the pri- knowledge. or knowledge are more effective than the color scribbles 1.3 Colorization by the points of the prior knowl- without repeating experiments for confirming the place edge of scribbles. Howtocorithe monochrome g uing the colored points of the prior knowledge?Levin's method 2 Steps of our algorithm is adopted as the algorithm that requires neither precise Fig.2 shows the process of algorithm.It is carried image segmentation,nor accurate region tracking.The out according to the following procedure. Input a monochrome image Downsample the Upsample the image Classify all points image by d times of the prior knowledge N Classify clusters Define a color with the similar d times prior knowledge Equalize at each cluster Colorization by the priorknowledge Extract points of the prior knowloedge from the residue Output the color image image Fig.2 Flowchart on process of our proposal 1 Degrade an image to the low resolution image 6)Obtain the edges of the original image with with downsampling method. Laplacian filter. 2)Classify the low resolution image for initial 7)Classify points of the prior knowledge by points of the prior knowledge which are called as repre- Ward's method. sentative pixels. 8)Define the points of the prior knowledge of the 3)Substitute the mean value of each cluster for same cluster to the same color manually. the values of all pixels and obtain the image 9)Colorize the monochrome image by the defined 4)Obtain the residue image E by‖I-Φ‖. colored points of the prior knowledge. 5)Segment the residue image E with small win- Repeat from 3)to 5)until the original image is dows so that points of the prior knowledge are added obtained.After that,go ahead to 6)until a color im- with these windows. age is obtained
第6期 DU Weiwei:Colorization by classfying the prior knowledge .559. 3 Experiments Fig.9(b):the number of the points of the prior knowl- edge is c=700,threshold is T=20,the number of The approach is effective based on the experi- levels is d=4,the size of a small window is h=13, ments of some images. the number of clusters as the prior knowledge is n= For reference,the origin image is given in Fig.3. 25. Fig.4(a)shows the monochrome image with scribbles Some experiments were carried out to other images and its result with colorization from Ref.[2].Draw Fig.10(a)and Fig.11(a).Their results are shown in some colored scribbles to the monochrome image freely Fig.10(b)and Fig.11(b). like Fig.5(a).The result like Fig.4(b)could not be obtained,instead,Fig.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 com- parison.The algorithm can generate some prior knowl- edge automatically like Fig.6(a).Just colorize the Fig.3 The origin images of a child 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 is c=300,threshold is T=20,the number of levels is d=5,the size of a small window is h=20,the number of clusters is n= 100.Notice that it is easy to understand,the points of (a)The monochrome child image (b)The result of the color child the prior knowledge are enlarged in Fig.6(a).Actual- with scribbled colors as image Levin's method ly,a pixel expresses a point of the prior knowledge. Fig.7（a）shows the monochrome image with FIg.4 The child images with scribbled colors 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 en- larged part of Fig.8(a).The result like Fig.7(b) could not be obtained,instead,Fig.8(b)was ob- tained.So it can be known that it is not easy to get the (a)The monochrome child image (b)The result of the color result like Fig.7(b).Experiments should be done un- with scribbled colors at random child image til the result like Fig.7(b)is obtained.Only by ap- Fig.5 The child images with scribbled colors at random propriately 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.Mo- reover,as many colored scribbles need to be given (a)The monochrome child (b)The result of the color manually,the error place is set easily such as on the image with the prior child image knowledge left corner of Fig.7(a)while the problem did not hap- pen in the proposal such as on the left corner of Fig.9 Fig.6 The child images with the prior knowledge (b).Some parameters of the proposal are given on
·560 智能系统学报 第6卷 4 Conclusions This paper presents an effective colorization algo- rithm by automatically generating the priori knowledge (a)The monochrome waterfall (b)The result of the color from an image.A user can obtain a colorful image di- image waterfall image rectly without repeatedly generating the prior knowl- Fig.7 The waterfall images with scribbled colors edge.However,in this proposal a color has to be de- fined 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 re- search. References: (a)The monochrome waterfall (b)The result of the color image with scribbled colors waterfall image [1]WELSH T,ASHIKHIMIN M,MUELLER K.Transferring at random color to greyscale images[J].ACM Transactions on Graph- Fig.8 The waterfall images with scribbled colors at random ics,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:689694. [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. (a)The monochrome waterfall (b)The result of the colo image waterfall image [4]HUANG T W,CHEN H T.Landmark-based sparse color representation for color transfer[C]//The 12th Computer Fig.9 The waterfall images with prior knowledge 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 Proba- bility.[S.1.],1967:281-297 [6]JOE H W.Hierarchical grouping to optimize an objective function[J].Joumal of the American Statistical Associa- ion,1963,58:236-244. [7]JACK K.Video demystified[M].3rd ed.Elsevier Science and Technology,2001:35-47. (a)The monochrome candle image (b)The result of the color candle image [8]BURT P J,ADELSON E H.The Laplacian pyramid as a compact image code[J].IEEE Trans Commun,1983,31 Fig.10 The candle images with the prior knowledge (4):532-540 About the authors: DU Weiwei was born in 1978.She received PhD degree from Kyushu Univer- sity in 2008,and now she is an asstistant professor at Kyoto Institute of Technology. Her current interests include fuzzy clusters (a)The monochrome building (b)the result of the color building image and graph-spectral algorithms,and she image with the prior knowledge has authored or co-authored several technical articles in jourals Fig.11 The building images with the prior knowledge and conference proceedings