Color Orchestra: Ordering Color Palettes for Interpolation and Prediction
Huy~Q.~Phan
% ~Hongbo~Fu
% ~and~Antoni~B.~Chan% <-this % stops a space \IEEEcompsocitemizethanks{ \IEEEcompsocthanksitem H Q. Phan is with the Deparment of Computer Science
University of Bath
UK. \IEEEcompsocthanksitem A. B. Chan is with the Department of Computer Science
City University of Hong Kong
Hong Kong. \IEEEcompsocthanksitem H. Fu is with the School of Creative Media
City University of Hong Kong
Hong Kong.
....lastname \thanks{...
~ \input{abstract %Although researchers have proposed various theories and methodologies to capture the characteristics of color harmony, few of them have been widely accepted as a standard method to generate harmonious color combinations. Recently, statistical methods were used to analyze color harmony from a data-driven point of view. Although promising experimental results were found, it is still difficult translate them to practical applications due to the computationally demanding nature and the requirement of data labeling. A natural statistical approach to understanding color harmony would be to model the probability density function of a selected palette dataset, in which a high likelihood palette can be viewed as a set of harmonious colors. It is, however, not straightforward to directly apply density modeling methods on the dataset as the palettes usually come as unordered sets of colors. In this paper, we introduce a lightweight yet powerful method to model the density of palette data, which opens up an abundance of practical applications such as photo-style exploration, real-time color suggestion, and enriched gray-scale photo colorization. By observing that artists often prefer their personal set of color palettes \---\, causing these palettes to appear more frequently in their paintings \---\ we intend to capture color harmony by modeling the density of local palettes extracted from small patches sampled from the paintings. We developed a divide-and-conquer sorting algorithm to rearrange the colors in the dataset in a semantically coherent order, which allows meaningful interpolation between color palettes. We then applied state-of-the-art density modeling methods to interpolate and/or predict color palettes in real-time. To quantitatively confirm the performance of our model, we also conducted experiments on datasets of digitized paintings collected from the Internet, which yielded favorable results.
abstract.tex
Color theme or color palette can deeply influence the quality and the feeling of a photograph or a graphical design. Although color palettes may come from different sources such as online crowd-sourcing, photographs and graphical designs, in this paper, we consider color palettes extracted from fine art collections, which we believe to be an abundant source of stylistic and unique color themes. We aim to capture color styles embedded in these collections by means of statistical models and to build practical applications upon these models. As artists often use their personal color themes in their paintings, making these palettes appear frequently in the dataset, we employed \emph{density estimation} to capture the characteristics of palette data. Via density estimation, we carried out various predictions and interpolations on palettes, which led to promising applications such as photo-style exploration, real-time color suggestion, and enriched photo recolorization. It was, however, challenging to apply density estimation to palette data as palettes often come as unordered sets of colors, which make it difficult to use conventional metrics on them. To this end, we developed a divide-and-conquer sorting algorithm to rearrange the colors in the palettes in a coherent order, which allows meaningful interpolation between color palettes. To confirm the performance of our model, we also conducted quantitative experiments on datasets of digitized paintings collected from the Internet and received favorable results.
applications.tex
\vspace{-10pt}
\section{Applications}\label{sec:apps}
In this section, we introduce various applications that were based on our palette interpolation and completion methods. 

%\begin{figure}[ht]
%\centering
%\begin{tabular}{cc}
%%\hline
%\includegraphics[width=0.37\linewidth]{images/image_47_annotations.png} & \includegraphics[width=0.4\linewidth]{images/image_48_annotations.png} \\
%%\hline
%\end{tabular}
%\vspace{-5pt}
%\caption{New colors suggested by our method were assigned to different pixels in the destination images. The backgrounds were intentionally desaturated for visibility. In the recolorization process, color images were used as the input (the first column in Figure~\ref{fig:colorization}).}\label{fig:recolorizaton_ann}
%\vspace{-10pt}
%\end{figure}

\subsection{Photo Recolorization}\label{sec:photo_recolorization}
Our method can suggest colors for photo recolorization. Different from traditional color transfer methods, which copy lightness, hue, and saturation from one photo to another, our method summarizes color characteristics of a set of source photos (image patches), and then actively examines regions in the destination photo to infers a \textit{set of colors} for each region. This makes our method different from that of \cite{huang2014learning,wang2010data}, which only give a single color to an image region (segment). The advantage of this approach is that local shades are preserved instead of being erased like in the cases of \cite{wang2010data,huang2014learning}. More details about our recolorization method is provided in the supplementary.

Figure \ref{fig:colorization} (Top) shows examples of photo recolorization with color styles learned from different artists. Observe how the vivid blues in Luce set and the strong oranges in Cezanne set are well captured by our method. For the case of Chase set, one might notice the dominance of fire/canary yellows and crimson reds. The results from Raphael set are less vibrant and bear the classic style of the artist. \huy{Additionally, we show the results produced with the Beach set in Fig. \ref{fig:context_specific}. Notice how the colors of sand, sunset sky and blue sky have been transferred to objects in the source images.}

\begin{figure}
\centering
\includegraphics[width=1.0\linewidth]{images/colorization/comparison_new.pdf} 
\caption[SmartPalette: Comparing recolorization results.]{Recolorization results obtained by our method and the method in \cite{wang2010data}. (A) an (B) are the user input palettes. The palettes predicted by our method are shown next to each result.}\label{smarpalette:fig:compare_colorization}
\vspace{-10pt}
\end{figure}

% More precisely, we performed image recolorization as follows. First, we segmented the destination image into super-pixel regions using SLIC \cite{achanta2012slic}. Second, we extracted palettes (color themes) from these regions and used them as the queries for GPLVM palette prediction. Colors in the query palettes were aligned to the training palettes using the same matching method described in \ref{smartpalette:sec:binarysortalgo}. Thus, if the $i^{\text{th}}$ color in the query palette was matched with the $j^{\text{th}}$ color in the training palettes, then all the pixels from the destination image, which have index $i$, will be recolored to the $j^{\text{th}}$ color in the predicted palette. In this way, we assigned pixels in the destination image with new colors jointly inferred from the manifold. In practice, we only chose a few pixels from a region in the destination image to do theme extraction and new color assignment. Pairs of old and new pixels were used to recolorize the entire image with the technique in \cite{chen2012manifold}. Figure \ref{fig:recolorizaton_ann} shows two images along with the new colors, annotated with the colored circles. Note that although we used segmentation at the beginning to assist palette extraction, multiple colors were assigned to a single segment. 


To see how recommending multiple palettes instead of one global palette would affect visual quality of the results, we compared our recolorization method with the method introduced in \cite{wang2010data}. Figure ~\ref{smarpalette:fig:compare_colorization} shows our recolorization results given the same input image and the target themes (A) and (B). To perform recolorization with an input palette as the constraint, we first applied the input theme to each segment in the destination image and then used the same steps as in the standard method.
%using \cite{chen2012manifold} and then extracted local palettes from each segment. The next steps were identical to the recolorization method discussed above. 
We used the models trained separately on 3 sets to suggest colors: Chase, Gogh and Renoir. One might notice that for the input palette (A), our method produce much cleaner results, as compared with the result from \cite{wang2010data}, and still resembling the spirit of the input. At small scales, as our method suggests multiple colors for a single region \---\ the mountain, for instance \---\ we can observe a wider range of colors exists in each region, creating a richer look for the image. We call this approach to photo recolorization \emph{enriched photo recolorization}. Similar results can be seen in the case of the input (B). Note that, as the artists rarely used such vibrant colors in their paintings, images in (B) are less saturated than the input palette. Depending on the application, one can prepare a more appropriate dataset to achieve desirable results.
 
\begin{figure*}[ht]
\centering
\includegraphics[width=0.8\linewidth]{images/colorization/recolorization_new_new.pdf}
\vspace{-10pt}
\caption[SmartPalette: Image recolorization and multi-style painting results.]{Image recolorization and multi-style painting results. (Top) Recolored images with palettes suggested by models trained on Chase, Cezanne, Luce, Raphael and Beach sets. (Bottom) Paintings made by two users using colors suggested by 3 models (Cezanne, Luce and Renoir). A pair of images were used as guidance (template). The grayscale image was shown to help the users with object shading and the line sketch with color spots was used to indicate the object boundaries and to guide the users on which color to use.}\label{fig:colorization}
\vspace{-10pt}
\end{figure*}
\begin{figure}[ht]
\centering
\includegraphics[width=0.85\linewidth]{images/explorer.pdf}
\caption[Photo-style Explorer interface.]{Photo-style Explorer interface.  (Left) the space of color palettes where each point corresponds to a complete 7-color palette. Key points are annotated with the associated palettes and the red circle indicates the location of the mouse pointer. (Right) Image viewer, displaying the recolorized result in real-time.}\label{fig:explorer_interface}
\vspace{-10pt}
\end{figure}
\vspace{-5pt}
\subsection{Photo-style Explorer}\label{smartpalette:sec:photoexplorer}
Photo stylization applications  like Lightroom offer users with a set of pre-defined filters and let them combine these filters to achieve a certain effect. It is, however, required that users know exactly what they want (a blurry photo in black and white, for instance). 
Inexperienced users often do not have such a clear picture of the final results but rather want to see different results and pick one that they prefer. We present an application called Photo-style Explorer, in which the user is allowed to freely surf through an infinite space of color styles and intuitively refine the result just by dragging the mouse. Figure \ref{fig:explorer_interface} shows the interface of the explorer and Figure \ref{fig:explorer_results} displays the representative results for two palette manifolds ``Luce'' and ``Raphael''. The colorization technique involved here was identical to the one described in Section~\ref{sec:photo_recolorization} except that we cached intermediate values to make the application works in real-time. 

\begin{figure*}[ht]
\centering
\begin{tabular}{cc}
%\hline 
\includegraphics[width=0.50\linewidth]{images/exploration_urbino.pdf} & \includegraphics[width=0.41\linewidth]{images/exploration_luce.pdf} \\ 
%\hline 
\end{tabular} 
\caption[Exploration of the palette manifold.]{Exploration of the palette manifold learned from the ``Raphael'' set (Left) and the ``Luce'' set (Right). Red dots indicate the locations where the color palettes were selected for recolorization.  The original image (top-left corner) was designed by Freepik.com. }\label{fig:explorer_results}
\vspace{-10pt}
\end{figure*}
\vspace{-5pt}
\subsection{Adaptive Color Palette}
\begin{figure}[ht]
\centering
\includegraphics[width=0.7\linewidth]{images/smartpalette.png}
\caption{SmartPalette interface. Please refer to the accompanying video for painting with real-time suggested palettes. The user may choose different artistic styles via the combo box at the top.   
}\label{fig:smartpalette}
\vspace{-10pt}
\end{figure}

To present the color combinations suggested by our method to the user, we designed a novel color picking interface, called ``SmartPalette'' interface. SmartPalette has been integrated into MyPaint~\cite{mypaint2015}, an open-source painting software written in Python. As shown in Figure~\ref{fig:smartpalette},
we chose the half-disk design that allows the colors to be shown in the order of their density in a patch.  Each 60-degree slice (1/3 of the half-disk) presents a set of colors (7 colors in our implementation). We sorted the colors by their brightness so that they will not ``jump'' around every time a new prediction is made. The colors were arranged into the slice in left-to-right and outer-inner orders. Different color suggestions were given by changing the order of the given colors (see the accompanying video). Different from previous methods~\cite{o2011color,lin2013probabilistic}, which considered only suggestion over a whole painting, our tool adaptively checked the regions being painted and performed palette prediction. We sampled the pixels from a 200x200 pixels patch using the same method described in Section \ref{sec:dataset}. The result was instantly presented to the user. The whole prediction process took less than half a second on an ordinary PC (Core 2 Duo 2.4 ghz, 8GB memory). 

Since our learning method is unsupervised, it is easy for professional painters/designers to train their own SmartPalette and use it to improve productivity. With GPLVM, the system does not require a lot of examples. Tens of example paintings are sufficient. Similarly, a design team can also make use of SmartPalette to constrain the use of colors so that their products will have consistent color themes. Figure \ref{fig:suggestions} shows different suggestions provided by SmartPalette in an incremental manner.  Here we used models trained on 3 different sets: Cezanne, Gogh and Raphael sets.
First, the user commits an initial brush stroke (red), which results in suggestions with reds and other predictably compatible colors. By changing the artist, the user can obtain different suggestions that bear the style of that artist. Second, the user commits a second brush stroke (yellow), the palettes now contain both reds and yellows and other colors. The interaction is repeated throughout the design process. One might notice that the variability of colors in Raphael set is not very large. This is because Raphael was a painter in the Classical period and he mainly used black, red, dirt yellow in his paintings.
\begin{figure}[ht]
\centering
\includegraphics[width=0.9\linewidth]{images/sample_predictions.pdf}
\caption{Sample suggestions from SmartPalette. The left-most column shows the query strokes. The remaining columns are the suggestions from different artist sets.}\label{fig:suggestions}
\vspace{-15pt}
\end{figure}
%\vspace{-10pt}
\paragraph*{\textbf{Multi-style painting and User Study}}
To see how SmartPalette works in real-life scenarios, we asked two users with art backgrounds to paint using our color suggestion tool. The traditional HSV wheel was also shown for selecting initial colors. The users were provided a line sketch along with a grey-scale photo of the same scene for reference. Color suggestions were based on the Cezanne, Luce, or Raphael sets. Figure \ref{fig:colorization} (bottom) shows the paintings produced with the palettes from the three artists. Note that, the paintings bear resemblance in color styles with the painting sets. For instance, the painting of User 1 that used suggestions from Luce set has ocean blue shadows like in original paintings. The paintings made with suggestions from Raphael set are less vibrant and are more brownish.


To quantitatively assess our Adaptive Color Palette, we replicated the above experiment with 4 users with experiences in digital painting, and recorded relevant information. There was no time limit for the test but it normally took about 8 minutes for each user to complete the test. We recorded the number of times the user chose a color from either our palette or the HSV wheel, the number of times these colors were actually painted and the number of times the users manually requested for color suggestions from our method. \huy{We did not run the test with just the HSV wheel as it might be subject to unaccountable factors such as painting skill and test timing. For instance, professional designers may perform just as good with or without our tool.  However, the tool will still be useful if it learns from their own painting collection}.

The results show that, the users preferred the colors from our method 81\% of the times on average. 84\% of the total painting time was done with colors from our suggestions. Each user manually requested for suggestions for 1.4 times per minute during the test. We also asked the users to rate different aspects of our method (from 1 to 5, the higher the better). The users agreed that they will use our tool frequently (4.3/5), the tool was easy to use (4.0/5) and most people can learn to use it quickly (4.3/5). Some users suggested that SmartPalette should display similar and novel colors in separate sections and the software should keep a history of suggested palettes.



body.tex
\begin{document}
%
% paper title
% Titles are generally capitalized except for words such as a, an, and, as,
% at, but, by, for, in, nor, of, on, or, the, to and up, which are usually
% not capitalized unless they are the first or last word of the title.
% Linebreaks \\ can be used within to get better formatting as desired.
% Do not put math or special symbols in the title.
\title{Color Orchestra: Ordering Color Palettes for Interpolation and Prediction}
% Color Orchestra: Modeling Palette Density for Photo-style Exploration and Color Suggestion

%
%
% author names and IEEE memberships
% note positions of commas and nonbreaking spaces ( ~ ) LaTeX will not break
% a structure at a ~ so this keeps an author's name from being broken across
% two lines.
% use \thanks{} to gain access to the first footnote area
% a separate \thanks must be used for each paragraph as LaTeX2e's \thanks
% was not built to handle multiple paragraphs
%
%
%\IEEEcompsocitemizethanks is a special \thanks that produces the bulleted
% lists the Computer Society journals use for "first footnote" author
% affiliations. Use \IEEEcompsocthanksitem which works much like \item
% for each affiliation group. When not in compsoc mode,
% \IEEEcompsocitemizethanks becomes like \thanks and
% \IEEEcompsocthanksitem becomes a line break with idention. This
% facilitates dual compilation, although admittedly the differences in the
% desired content of \author between the different types of papers makes a
% one-size-fits-all approach a daunting prospect. For instance, compsoc 
% journal papers have the author affiliations above the "Manuscript
% received ..."  text while in non-compsoc journals this is reversed. Sigh.

\author{Huy~Q.~Phan,%
        ~Hongbo~Fu,%
        ~and~Antoni~B.~Chan% <-this % stops a space
\IEEEcompsocitemizethanks{
\IEEEcompsocthanksitem H Q. Phan is with the Deparment of Computer Science, University of Bath, UK.
\IEEEcompsocthanksitem A. B. Chan is with the Department of Computer Science, City University of Hong Kong, Hong Kong.
\IEEEcompsocthanksitem H. Fu is with the School of Creative Media, City University of Hong Kong, Hong Kong.}% <-this % stops an unwanted space
}
% \thanks{Manuscript received April 19, 2005; revised August 26, 2015.}

% note the % following the last \IEEEmembership and also \thanks - 
% these prevent an unwanted space from occurring between the last author name
% and the end of the author line. i.e., if you had this:
% 
% \author{....lastname \thanks{...} \thanks{...} }
%                     ^------------^------------^----Do not want these spaces!
%
% a space would be appended to the last name and could cause every name on that
% line to be shifted left slightly. This is one of those "LaTeX things". For
% instance, "\textbf{A} \textbf{B}" will typeset as "A B" not "AB". To get
% "AB" then you have to do: "\textbf{A}\textbf{B}"
% \thanks is no different in this regard, so shield the last } of each \thanks
% that ends a line with a % and do not let a space in before the next \thanks.
% Spaces after \IEEEmembership other than the last one are OK (and needed) as
% you are supposed to have spaces between the names. For what it is worth,
% this is a minor point as most people would not even notice if the said evil
% space somehow managed to creep in.



% The paper headers
\markboth{IEEE Transactions on Visualization and Computer Graphics, March~2017}%
{Phan \MakeLowercase{\textit{et al.}}: Color Orchestra: Modeling Palette Density for Photo-style Exploration and Color Suggestion}
% The only time the second header will appear is for the odd numbered pages
% after the title page when using the twoside option.
% 
% *** Note that you probably will NOT want to include the author's ***
% *** name in the headers of peer review papers.                   ***
% You can use \ifCLASSOPTIONpeerreview for conditional compilation here if
% you desire.



% The publisher's ID mark at the bottom of the page is less important with
% Computer Society journal papers as those publications place the marks
% outside of the main text columns and, therefore, unlike regular IEEE
% journals, the available text space is not reduced by their presence.
% If you want to put a publisher's ID mark on the page you can do it like
% this:
%\IEEEpubid{0000--0000/00\$00.00~\copyright~2015 IEEE}
% or like this to get the Computer Society new two part style.
%\IEEEpubid{\makebox[\columnwidth]{\hfill 0000--0000/00/\$00.00~\copyright~2015 IEEE}%
%\hspace{\columnsep}\makebox[\columnwidth]{Published by the IEEE Computer Society\hfill}}
% Remember, if you use this you must call \IEEEpubidadjcol in the second
% column for its text to clear the IEEEpubid mark (Computer Society jorunal
% papers don't need this extra clearance.)



% use for special paper notices
%\IEEEspecialpapernotice{(Invited Paper)}


% for Computer Society papers, we must declare the abstract and index terms
% PRIOR to the title within the \IEEEtitleabstractindextext IEEEtran
% command as these need to go into the title area created by \maketitle.
% As a general rule, do not put math, special symbols or citations
% in the abstract or keywords.
\IEEEtitleabstractindextext{%
\begin{abstract}~
\input{abstract}


%Although researchers have proposed various theories and methodologies to capture the characteristics of color harmony, few  of them have been widely accepted as a standard method to generate harmonious color combinations. Recently, statistical methods were used to analyze color harmony from a data-driven point of view. Although promising experimental results were found, it is still difficult translate them to practical applications  due to the computationally demanding nature and the requirement of data labeling.  A natural statistical approach to understanding color harmony would be to model the \emph{probability density function} of a selected palette dataset, in which a high likelihood palette can be viewed as a set of harmonious colors. It is, however, not straightforward to directly apply density modeling methods on the dataset as the palettes usually come as unordered sets of colors. In this paper, we introduce a lightweight yet powerful method to model the density of palette data, which opens up an abundance of practical applications such as photo-style exploration, real-time color suggestion,  and enriched gray-scale photo colorization. By observing that artists often prefer their personal set of color palettes \---\, causing these palettes to appear more frequently in their paintings \---\ we intend to capture color harmony by modeling the density of local palettes extracted from small patches sampled from the paintings. We developed a divide-and-conquer sorting algorithm to rearrange the colors in the dataset in a semantically coherent order, which allows meaningful interpolation between color palettes. We then applied state-of-the-art density modeling methods to  interpolate and/or predict color palettes in real-time. To quantitatively confirm the performance of our model, we also conducted experiments on datasets of digitized paintings collected from the Internet, which yielded favorable results. 
\end{abstract}

% Note that keywords are not normally used for peerreview papers.
\begin{IEEEkeywords}
Image color analysis, Machine learning, Color palette, Colorization.
\end{IEEEkeywords}}


% make the title area
\maketitle


% To allow for easy dual compilation without having to reenter the
% abstract/keywords data, the \IEEEtitleabstractindextext text will
% not be used in maketitle, but will appear (i.e., to be "transported")
% here as \IEEEdisplaynontitleabstractindextext when the compsoc 
% or transmag modes are not selected <OR> if conference mode is selected 
% - because all conference papers position the abstract like regular
% papers do.
\IEEEdisplaynontitleabstractindextext
% \IEEEdisplaynontitleabstractindextext has no effect when using
% compsoc or transmag under a non-conference mode.



% For peer review papers, you can put extra information on the cover
% page as needed:
% \ifCLASSOPTIONpeerreview
% \begin{center} \bfseries EDICS Category: 3-BBND \end{center}
% \fi
%
% For peerreview papers, this IEEEtran command inserts a page break and
% creates the second title. It will be ignored for other modes.
\IEEEpeerreviewmaketitle

 \input{intro}
 \input{related_work}
\input{methodology}
 \input{applications}
 \input{evaluation}
 \input{limitation_conclusion}

% Can use something like this to put references on a page
% by themselves when using endfloat and the captionsoff option.
\ifCLASSOPTIONcaptionsoff
  \newpage
\fi

% trigger a \newpage just before the given reference
% number - used to balance the columns on the last page
% adjust value as needed - may need to be readjusted if
% the document is modified later
%\IEEEtriggeratref{8}
% The "triggered" command can be changed if desired:
%\IEEEtriggercmd{\enlargethispage{-5in}}

% references section

% can use a bibliography generated by BibTeX as a .bbl file
% BibTeX documentation can be easily obtained at:
% http://mirror.ctan.org/biblio/bibtex/contrib/doc/
% The IEEEtran BibTeX style support page is at:
% http://www.michaelshell.org/tex/ieeetran/bibtex/
\bibliographystyle{IEEEtran}
% argument is your BibTeX string definitions and bibliography database(s)
\bibliography{main}
%
% <OR> manually copy in the resultant .bbl file
% set second argument of \begin to the number of references
% (used to reserve space for the reference number labels box)
% \begin{thebibliography}{1}

% \bibitem{IEEEhowto:kopka }
% H.~Kopka and P.~W. Daly, \emph{A Guide to \LaTeX}, 3rd~ed.\hskip 1em plus
%  0.5em minus 0.4em\relax Harlow, England: Addison-Wesley, 1999.

% \end{thebibliography}

% biography section
% 
% If you have an EPS/PDF photo (graphicx package needed) extra braces are
% needed around the contents of the optional argument to biography to prevent
% the LaTeX parser from getting confused when it sees the complicated
% \includegraphics command within an optional argument. (You could create
% your own custom macro containing the \includegraphics command to make things
% simpler here.)
\vspace{-20pt}
\begin{IEEEbiography}[{\includegraphics[width=1in,height=1.25in,clip,keepaspectratio]{images/people/huy.png}}]{Huy Q. Phan}
is an postdoctoral researcher at the University of Bath. He received his B.Sc in Computer Science from the Vietnam National University in 2009 and attained a PhD from the City University of Hong Kong in 2016, under supervisions of Prof. Hongbo Fu and Prof. Antoni B. Chan. In 2015, he was a research intern at Adobe Systems in San Jose city.
\end{IEEEbiography}
\vspace{-20pt}
\begin{IEEEbiography}[{\includegraphics[width=1in,height=1.25in,clip,keepaspectratio]{images/people/hb.png}}]{Hongbo Fu}
is an Associate Professor in the School of Creative Media, City University of Hong Kong. He received the PhD degree in computer science from the Hong Kong University of Science and Technology in 2007 and the BS degree in information sciences from Peking University, China, in 2002. His primary research interests fall in the fields of computer graphics and human computer interaction. He was the Program Chair or Co-chair of CAD/Graphics 2013, SIGGRAPH Asia 2013 (Emerging Technologies), SIGGRAPH Asia 2014 (Workshops) and CAD/Graphics 2015. He is the Conference Chair for SIGGRAPH Asia 2016. He also serves as an Associate Editor of The Visual Computer (TVC), Computers \& Graphics (C\&G), and Computer Graphics Forum (CGF).
\end{IEEEbiography}
\vspace{-20pt}
\begin{IEEEbiography}[{\includegraphics[width=1in,height=1.25in,clip,keepaspectratio]{images/people/abc.png}}]{Antoni B. Chan}
received the B.S. and M.Eng. degrees in electrical engineering from Cornell University, Ithaca, NY, USA, in 2000 and 2001, respectively, and the Ph.D. degree in electrical and computer engineering from University of California at San Diego (UCSD), La Jolla, CA, USA, in 2008. He was a Visiting Scientist with the Vision and Image Analysis Laboratory, Cornell University, from 2001 to 2003, and a Post-Doctoral Researcher with the Statistical Visual Computing Laboratory, UCSD, in 2009. In 2009 he joined the Department of Computer Science, City University of Hong Kong, Hong Kong, and is currently an Associate Professor. His research interests include computer vision, machine learning, pattern recognition, eye-gaze analysis, and music analysis. Dr. Chan received the National Science Foundation Integrative Graduate Education and Research Training Fellowship from 2006 to 2008, and an Early Career Award from the Research Grants Council of the Hong Kong Special Administrative Region, China, in 2012.
\end{IEEEbiography}

% or if you just want to reserve a space for a photo:

%\begin{IEEEbiography}{Huy Q. Phan}
%Biography text here.
%\end{IEEEbiography}

% if you will not have a photo at all:
%\begin{IEEEbiographynophoto}{Hongbo Fu}
%Biography text here.
%\end{IEEEbiographynophoto}

% insert where needed to balance the two columns on the last page with
% biographies
%\newpage

%\begin{IEEEbiographynophoto}{Antoni B. Chan}
%Biography text here.
%\end{IEEEbiographynophoto}

% You can push biographies down or up by placing
% a \vfill before or after them. The appropriate
% use of \vfill depends on what kind of text is
% on the last page and whether or not the columns
% are being equalized.

%\vfill

% Can be used to pull up biographies so that the bottom of the last one
% is flush with the other column.
%\enlargethispage{-5in}



% that's all folks
\end{document}



evaluation.tex
\vspace{-10pt}
\section{Evaluation and Results}\label{sec:evals}
We evaluated our sorting algorithm by comparing it to a baseline method and then quantitatively assessed the predictive performance of the learning models, which operate on our feature vector.
%\subsection{Colorization Quality}

\subsection{Palette Sort Comparisons}\label{smartpalette:sec:evalsort}
\begin{figure*}[ht]
\centering
\includegraphics[width=0.9\linewidth]{images/binary_sort/multi_comparison1.pdf}
\caption[SmartPalette: Ordering performance for multiple palettes.]{Ordering performance is demonstrated with the recolorization results. We show the corresponding palette datasets at the middle. The palettes sorted with our method are annotated with semantic labels (Rose, Sky, Dirt and Background \---\ BG), indicating the objects that get the colors from the rows.}\label{fig:alignmentcomparison}
\vspace{-15pt}
\end{figure*}
%\subsubsection{Results and Comparison with Other Methods}
We chose simple palette ordering methods, which are based on brightness and hue, as the baselines to evaluate our method. In the experiments, we conveniently call these methods \emph{Brightness Sort} and \emph{Hue Sort}. As colors in paintings often follow certain shading rules, brightness and hue can be basic cues for aligning them~\cite{mollica2013color}. 
%\huy{We did not use other cues such as hue as they produced much worse performance, as compared to Brightnes Sort's in all the experiments}.
These simple methods, however, failed when the palettes to be ordered do not have strong contrast or hue, which is the case of our datasets. 
%Figure \ref{fig:comparesort} shows the sorting results obtained by various methods: (A) Binary Palette Sort (BPS), (B) brightness-based ordering (Brightness Sort) and (C) Unordered. As highlighted with dotted red boxes, one might observe that our method yields smoother transitions between corresponding colors in the palettes, in contrast to the results obtained by applying a simple brightness-based sort.  
%\vspace{-10pt}
\begin{figure}[ht]
\centering
\includegraphics[width=0.8\linewidth]{images/binary_sort/vary_palette_size.pdf}
\caption[Palette ordering with different methods.]{Palette ordering with different methods: Hue Sort, Brightness Sort and BPS.}\label{fig:vary_palette_size}
\vspace{10pt}
\end{figure}
\vspace{-10pt}
\subsubsection{Ordering Performance}\label{smartpalette:sec:eval_ordering}
To measure the ordering performance, we computed the mean distance between the colors in two consecutive palettes, averaged over all palettes in a dataset. Since we are interested in ordering colors in the palettes so that similar palettes have better correspondences, we pre-ordered the palettes with KPCA before the experiment (see Section~\ref{smartpalette:sec:binarysortalgo}). In  Figure~\ref{fig:vary_palette_size}, we plot the distance against the palette size. For each palette size $K$, we randomly selected a dataset of size $20 \times K$ (20 palettes) out of a dataset of size $20 \times 40$ and then ordered it with 3 methods: BPS, Brightness Sort and Hue Sort. Each experiment was repeated 5 times and the results were averaged over all 17 sets. As shown in the figure, Hue Sort has the worst error rates, comparing to BPS and Brightness Sort. Thus, we will not further consider it in the later sections. On the other hand, Brightness Sort only produces comparable performance to BPS when $K \leq 8$. As $K$ increases, BPS increasingly outperforms Brightness Sort. Note that, the color distance appears to inversely proportional with the size of palette. This is because there are more correspondences in a more complete dataset. To visually assess the ordering performance, we carried out a toy experiment as follows.


First, we chose two source images and extracted one 10-color palette per image. Next, we selected a set of 8 palettes from the Prendergast and the Luce set and then used them for recolorization. To make the correspondences between the extracted palettes and the selected palettes more visible to the reader, we used MHD to choose palettes that are similar to the extracted palettes.
%The palettes were chosen so that there were obvious correspondences between them and the palettes extracted from the source images. 
Next, we sorted the palette set with BPS and Brightness Sort.  The motivation for having two input images is to demonstrate the localization property of our method. 
% We show in Figure \ref{fig:alignmentcomparison} the ordering performance of our method by showing recolorization results generated by directly applying the sorted palettes to regions in the source images.
As shown in Figure \ref{fig:alignmentcomparison}, there are two distinctive groups of palettes in the palette set ([1-4] and [5-8]), each group resembles an input palette. As Binary Palette Sort aligns the palettes from local to global, we can observe clear correspondences for both groups of palettes. For example, the blues, representing the sky, and the reds, representing the rose, have consistent indices across the palettes. This demonstrates a case of \emph{context localization}, an natural behavior of our method. As discussed in Section~\ref{sec:reordering}, our sorting algorithm is able to localize the painting contexts embedded in a palette dataset. By assuming that similar palettes should describe similar objects or regions, our algorithm partitions and sorts these palettes together. The algorithm creates correspondences in color between nearby palettes, and thus helps preserving the context of each color locally.


To see how different color palettes may affect recolorization, we applied the sorted palettes to recolor the same source image (the same as in Figure~\ref{fig:alignmentcomparison}). Colors with the same indices were applied to the same regions in the source image (the first color went to the background, the second color went to the small flowers, etc.). The sorted palettes were matched with the palette extracted from the source image by using the same technique discussed in \ref{smartpalette:sec:binarysortalgo}. We used the recolorization technique introduced in ~\cite{levin2004colorization}. Note that, the recolorization method used in this section is different from the one in Section~\ref{sec:photo_recolorization}. As the purpose was only to visualize the differences between color palettes and we had only one palette to recolorize the image, the technique in ~\cite{levin2004colorization} was more appropriate. As a result of correct alignment, our recolorization results remain consistent across different palettes. For example, the rose stays red and the sky stays blue in all the images. In contrast, the results produced with Brightness Sort appear to be quite inconsistent as the blues and reds keep switching regions. 


 To further confirm the superiority of our method, we conducted a user study to 
compare the consistency among the results produced by our method and Brightness Sort. We followed the same procedure discussed above but with 10 source images. We chose the source images in a way that ensures distinctiveness between colors in each source image. The full set of test images can be found in the supplementary documents for this paper. We generated a set of 6 images for each pair of sorting method and source image. The resulting sets for the two methods and the source image were displayed side-by-side for comparison and the order of appearance is counter-balanced. 15 users were asked to pick a set that has better consistency. \huy{Concretely, we instructed the user to look at each image set as a whole and to examine the color consistency within each set. We provided examples of consistent and inconsistent sets if the user is still unclear about the task. We also informed the user that they should not care about the aesthetic quality of the images as it is irrelevant to the test. The results show that the users preferred our method 127/150 of the times $(\chi^2=74.9, p<0.0001)$}.
% r = np.array([7, 9, 8, 9, 9, 9, 8,   9, 8, 9, 8, 9, 9, 8, 8])
% chisquare([sum(r), 150 - sum(r)])

\vspace{-5pt}
\subsubsection{Interpolation Performance}\label{smartpalette:sec:eval_interpolation}
\begin{figure*}[ht]
\centering
\includegraphics[width=0.95\linewidth]{images/density_estimation/manifold_sampling/palette_interpolation_gplvm.pdf}
\caption{Palettes sampled from GPLVM's latent space were applied to the same input image in Figure~\ref{fig:alignmentcomparison}. The training palettes are at the bottom, each column is a 10-color palette.}\label{fig:gplvm_sampling}
\end{figure*}

We demonstrate the interpolation performance of BPS by comparing it to the baseline method.
We performed interpolation on the low dimensional space induced by PCA or GPLVM and then projected the interpolated points back to the palette space. We also visualized the color palettes by applying the interpolated palettes to the same source image, as in Section~\ref{smartpalette:sec:eval_ordering}. Figure \ref{fig:gplvm_sampling} shows recolorization results with the palettes sampled along an evenly spaced grid from the latent space induced by GPLVM. The sampled palettes are placed under each recolorized image. Under each set of recolorization results, we show the corresponding palettes used for training the model.  When the palettes are correctly ordered with Binary Palette Sort, we obtain better palette interpolations as the colors stay ``clean'' and consistent across the interpolated palettes \---\ e.g., the rose stays red in all cases. 
%From the palettes at the bottom of the figure, we observe that red colors have been organized mainly in the first row, corresponding to the rose in the images.
With brightness-based ordering, the interpolated colors turn brown as they are just the averages of the misaligned palettes (top row, Brightness Sort). In the last row of Brightness Sort, the roses are colored green, as a result of interpolating between misaligned colors (reds and greens). The results in the Unordered case appear to be unusable as the colors  jump arbitrarily from one place to another. The results produced with PCA are shown in the supplementary.

% Similarly, we used PCA to project the same sets of palettes onto a 2D space and then evenly sampled from this space. We then projected the samples back to the palette space using PCA inverse transform. The results for Binary Palette Sort and Brightness Sort are shown in Figure \ref{smartpalette:fig:pca_sampling}. The results obtained with Binary Palette Sort are still noticeably better than the ones from Brightness Sort as the colors are consistent across the images. One might observe that, compared to GPLVM's results, the interpolated palettes appear to be less diverse.


%\begin{figure}
%\centering
%\includegraphics[width=0.9\linewidth]{images/density_estimation/manifold_sampling/palette_interpolation_pca.pdf}
%\caption{Interpolation results with PCA, given the same training data shown in Figure~\ref{fig:gplvm_sampling}. }\label{smartpalette:fig:pca_sampling}
%\vspace{-10pt}
%\end{figure}

\subsection{Quantitative Comparison}
%\begin{table}
%\centering 
%\begin{tabular}{|l|cccc|}
%\hline
%No. Missing Colors & 4 & 3 & 2 & 1 \\
%\hline
%
%(1) GPLVM + SPF & 0.077 & 0.057 & 0.040 & 0.022 \\
%(2) GPLVM + Brightness & 0.078 & 0.057 & 0.040 & 0.022 \\
%(3) GPLVM + None & 0.100 & 0.069 & 0.045 & 0.024 \\
%(4) GMM + SPF & 0.080 & 0.059 & 0.042 & 0.023 \\
%(5) GMM + None & 0.111 & 0.07 & 0.044 & 0.021 \\
%(6) Retrieval + SPF & 0.105 & 0.080 & 0.060 & 0.048 \\
%(7) Retrieval + None & 0.107 & 0.086 & 0.070 & 0.059 \\
%(8) Color Compat. &  &  &  & 0.039 \\ 
%(9) Color By Numbers & 0.160 & 0.102 & 0.060 & 0.032 \\
%(10) Mean & 0.169 & 0.080 & 0.045 & 0.020 \\
%
%\hline
%\end{tabular}
%\vspace{0.1pt}
%\caption{Comparing theme completion performance. The shown numbers are the average MHD distance between predicted themes and ground-truth themes. The smaller, the better.
%}\label{tab:compare_pred}
%\vspace{-10pt}
%\end{table}
\begin{figure}[H]
\centering
\includegraphics[width=0.9\linewidth]{images/palette_completion_comparison.pdf}
\caption{\huy{Comparing theme completion performance. Prediction error are measured by the average MHD distance between predicted themes and ground-truth themes. The smaller, the better}}\label{smartpalette:fig:palette_pred_comparison}
\vspace{-10pt}
\end{figure}
We assessed the quality of the proposed model quantitatively by applying it to the task of color prediction. %We also performed qualitative evaluation to visually examine the quality of the suggestions produced by our method.
In this experiment, datasets were divided into training and testing sets with the training ratio of 0.6 (60\% of the whole set used for training). We conducted the experiment on 3 sets: Renoir, De Gas and Chase and reported the averaged results. Each set contained roughly from 500 to 600 5-color palettes.  Given 4, 3, 2 and 1 colors from an \emph{unordered} palette, the task was to predict/reconstruct the original palette (5 colors). Each experiment was repeated 5 times on random splits. We experimented with different methods for palette prediction. From now on, we refer to the vectorized ordered palettes produced by our Binary Palette Sort as Sorted Palette Features (SPF). 
\begin{enumerate}
\item GPLVM + SPF: GPLVM on SPF (introduced in Section \ref{sec:density}).
\item GPLVM + Brightness: GPLVM with Brightness Sort.
\item GPLVM + None: GPLVM on the original palette data.
\item GMM + SPF:  Gaussian Mixture Regression with SPF.
\item GMM + None: GMM on the original palette data.
\item Retrieval + SPF: We retrieved the most similar palette to the given colors. Since the palettes were already sorted, we used Euclidean distance to measure the similarity  between the given colors and colors with the same indices in the dataset.
\item Retrieval + None: This method is similar to the above method but the original (unordered) palette data was used.
\item Color Compatibility \cite{o2011color}: One of the first data-driven methods for color harmony discovery and palette rating prediction. Due to the slow implementation, we could only try it on the single color prediction case. The implementation was taken from the authors.
\item Color by Numbers \cite{lin2013probabilistic}: A method that relies on unitary, pairwise and global color functions connected by a factor graph to predict harmonious color combinations. The global function was taken from \cite{o2011color}. To apply the method to our data, we used raw patches extracted from the images as input to the system. We used the implementation provided by the authors of the paper. 
\item Mean: A simple method that takes the average of all provided colors as prediction. We used it as a baseline for other methods.

\end{enumerate}

For the case of GMM, GPLVM and Retrieval we first ran the Binary Palette Sort algorithm on the training set to obtain the SPF vectors. Then, for each given set of observed colors, we found a few similar palettes with MHD (3 palettes in our experiment) in the training set and then aligned the input set to these examples using the same technique used  to sort a pair of palette sets in Binary Palette Sort (see Section \ref{sec:reordering}). Even though the observed set might have missing colors, the matching algorithm still works as it only needs the pairwise distances between the colors.
The missing colors in the palettes were then predicted using the technique described in Section \ref{sec:palette_completion}. Since the predicted results were still unordered (except for the 1-color case), we again used MHD to measure the distance between the predicted theme and the ground-truth. Since MHD is simply an average distance between pairs of colors, we visualize the relative differences between colors in Figure~\ref{smartpalette:fig:color_scale}. A change of 0.05 in either ``L'' channel or ``a'' channel can produce visible differences. The reported numbers are the average distance between all predictions and ground-truths.
\begin{figure}
\centering
\includegraphics[width=0.7\linewidth]{images/color_scale.pdf}
\caption{Color scales for ``L'' and ``a'' channels in CIE*Lab space. The numbers are the relative distances to the first color.}\label{smartpalette:fig:color_scale}
\vspace{-10pt}
\end{figure}
% \huy{The Brightness Sort method, which was studied in Section \ref{smartpalette:sec:evalsort}, yields very similar results to our method and will not be discussed further in this section}.

% Table \ref{tab:compare_pred} shows the performance of the methods on different image sets and different numbers of missing colors. 
Fig. \ref{smartpalette:fig:palette_pred_comparison} shows the average error of the methods with different numbers of missing colors. One might notice that methods Color by Numbers (9) and Color Compatibility (8) are not suitable for the task of palette completion, since their error rates appear to be higher than other methods.
We run an independent t-test to test the difference between our method (1) and (9) and get $\text{t-statistic}=-2.47, \text{p-value}=0.02$, which means that our method is significantly better in predicting colors (smaller error rates). We also found via t-test that the learning-based methods with SPF (1) and (4) are significantly better than the retrieval-based methods (6) and (7). This result justifies our choice of using learning approaches for predicting color palettes. In contrast, the learning-based methods without SPF (3) and (5) are not significantly better than any of the retrieval-based methods. The Brightness Sort method, which was studied in Section \ref{smartpalette:sec:evalsort}, yields very similar results to our method in this test. This can be explained by the fact that brightness is the most important factor in visual data. In fact, many computer vision algorithms only need gray-scale data as the cue for predictions.
 
 GPLVM-based methods are generally better than GMM-based ones for both types of data (sorted and unordered). For this reason, we chose GPLVM for the applications introduced in Section \ref{sec:apps}. For both prediction methods, we observe a boost in performance when the SPF vectors are used. 
% The reason for this improvement has been intuitively discussed in Section \ref{sec:density} and visualized in Figure \ref{fig:gmm_gplvm_density}. 
 It is worth noting that the mean predictor (Mean) works best for the case of 1 missing color. This can be explained by looking at our dataset. Since we gathered color themes from local patches, there were many patches that contain different shades of the same color. Thus, the missing colors in those cases are fairly similar to the average of the other colors in the same theme.  The t-test results, however, did not confirm the significance of the difference in error rate between (1), (3), (4), (5) and (10). In Section \ref{smartpalette:sec:evalsort}, we visually evaluated these methods.
 %In Figure \ref{fig:predictive_perf}, we plotted the data in Table \ref{tab:compare_pred} to make it easier for the reader to interpret the data.
%In Table \ref{tab:crossdata}, we show the results of this experiment. One should notice that, GPLVM-SPF (B) did not perform as good as GPLVM-SPF (A), especially for the case of cross-dataset prediction and when the number of missing colors was large (greater than 2). This indicates the importance of the latent location optimization step. This step can be thought as an ``interpolation'' step, which generates new palettes that balance two conditions: (a) have high probability, (b) similar to the observed palette (given colors). Cross-dataset prediction is interesting because in applications such as color suggestion or photo recolorization the observed colors may not come from the same source, as they are provided by the user. Suggestions that are totally different from the input colors are not very useful since the user would like to keep their intended colors to some degree. Another remarkable point is, when the number of missing color is 1, the ``mean'' predictor gives the best results. This is because of the nature of our dataset, which contains local palettes extracted from image patches. Thus, there are many palettes that come from relatively smooth patches. It is very likely that the average of the observed colors will be a good prediction in these cases. Figure \ref{fig:compare_pred} shows sample predictions made by different methods for the case of number of missings color is 3.
%\begin{table}
%\tabcolsep=0.05cm
%\begin{tabular}{|c|c|c|c|}
%\hline
%Method & Renoir - Luce & Renoir - Chase & Renoir - Rafael \\
%\hline
%GPLVM-SPF (A) & 0.087 & 0.070 & 0.083 \\
%\hline
%GPLVM-SPF (B) & 0.089 & 0.072 & 0.086 \\
%\hline
%GMM-SPF & 0.090 & 0.072 & 0.084 \\
%\hline
%\end{tabular}
%\caption{Cross-dataset prediction results for number of missing colors = 3. 
%In the 2nd-4th columns, the names on the left indicate the training sets and the right ones the testing sets. The smaller the better.
 %GPLVM-SPF (A) is GPLVM on Sorted Palette Feature with latent location optimization. GPLVM-SPF (B) is the same as (A) without optimization. GMM-SPF is Gaussian Mixture Regression with SPF feature.
%}\label{tab:crossdata}
%\end{table}
%\begin{figure}[ht]
%\centering
%\includegraphics[width=3.0in]{images/compare_pred.pdf}
%\caption{Sample predictions. (A) the provided colors (black cell indicates missing colors), (B) the ground-truth, (C) predicted by GPLVM-SPF (A), (D) predicted by GMM-SPF, and (E) predicted by Color-by-Numbers.}\label{fig:compare_pred}
%\end{figure}
intro.tex
\section{Introduction}\label{smartpalette:sec:intro}
\begin{figure*}
\includegraphics[height=1.9in]{images/teaser.pdf}
\caption[SmartPalette: An overview]{An overview of our work. We first extracted color palettes (themes) from image patches, which were uniformly sampled from paintings of one or more artists. Second, our Binary Palette Sort algorithm sorted unordered color palettes. Third, GPLVM was used for palette interpolation and prediction. The last columns show two applications of our method:  photo-style exploration and adaptive palette.}\label{fig:teaser}
\vspace{-10pt}
\end{figure*}
Color is a topic that lies in the intersection of art and science. A large body of literature has been devoted to study color from very different perspectives. Computer scientists have been working on topics such as color transfer, color harmony, grey-scale photo colorization, and color picking interfaces. A relatively new trend in color harmony study is to discover harmonious color combinations from existing color themes, for example, through data-driven approaches. O'Donovan et al.~collect large datasets of color themes along with their ratings and train a regressor to predict ratings for novel color themes~\cite{o2011color}. Lin et al.~later integrate this regressor into a factor graph, which is capable of suggesting interesting colorings for segmented patterns~\cite{lin2013probabilistic}. Huang et al.~employ a similar factor graph for image recolorization~\cite{huang2014learning}. Wang et al.~introduce techniques to enhance color themes with data~\cite{wang2010data,wang2011example}.

% previous work didn't consider density estimation
% why density & interpolation are useful
Interestingly, few of these works have attempted to model the \textit{density} of palette data, which tells how frequently a certain palette appears in the data. One of the main challenges to modeling palette density is that palette datasets are available as sets of \textit{unordered colors}, making it difficult to directly apply traditional density estimation methods. Representative features introduced in \cite{o2011color} might be used for density estimation but one will lose the ability to interpolate new color palettes. Palette interpolation is potentially useful for applications such as example-based color suggestion and image recolorization (see Section \ref{sec:apps}). When the number of examples is limited, interpolation helps extending the range of available choices possibly infinitely. 

% (*) It is reasonable to do density estimation & interpolation on palettes extracted from the paintings.
% (*) how density and color harmony are related
A key observation behinds our approach is that color palettes extracted from an art collection often conform to a certain aesthetic style, which can be revealed by their density distribution. This can be observed from paintings of the world-renowned painters such as Paul Cezanne, Vincent van Gogh,  Pierre-Auguste Renoir. It is commonly known that there are certain rules of using colors in fine art~\cite{mollica2013color}. For instance, to color an object, one should use warm colors for illuminated regions and cold colors for shaded regions. Although artists have  their own choices of colors, basic rules are usually respected as they help ensuring that the paintings are perceived properly (e.g., a morning scene should be understood as in a morning time).  On the other hand, distinguished artists often prefer  to use their favorite color combinations over the actual colors of the objects being painted. This is because a repeated use of some sets of colors will eventually make their paintings stand out. For instance, Maximilien Luce used strong blues and yellows to shade objects (Figure~\ref{fig:luce_matisse}); Henri Matisse often used deep reds and greens in his paintings. These observations suggest that high frequency color themes can represent the style of a palette dataset, and with the help of interpolation, we can generate more color palettes with the same style by sampling from a palette density.
\begin{figure}[ht]
\centering
\includegraphics[width=0.85\linewidth]{images/luce_matisse.pdf}
\caption{(Left) Maximilien Luce's paintings. (Right) Henri Matisse's paintings.}\label{fig:luce_matisse}
\vspace{-15pt}
\end{figure}

To perform palette density estimation and palette interpolation, we impose an order on the colors in a palette dataset so that the Euclidean distance between the palettes correctly reflects the difference between them, and corresponding colors in the palettes are aligned. Our approach achieves this by globally sorting the colors in the dataset so that the total distance between all pairs of color palettes is minimized. The sorting algorithm \---\ called Binary Palette Sort \---\ is one of our main contributions as it greatly improves the performance of many applications introduced in our work. We have thoroughly evaluated its performance with both quantitative and qualitative experiments (see Section~\ref{sec:evals}).
The order of the colors allows us to apply conventional  techniques to estimate the density of color palettes and to interpolate among them. Furthermore, given a palette with missing colors, we can predict compatible colors by sampling from data points that simultaneously have high likelihood and are similar to the input palette. In our implementation, we used Gaussian process latent variable models (GPLVM) to estimate the density of color palettes and to interpolate new palettes. 
% and Gaussian mixture models (GMM) to estimate the density of color palettes and to predict missing colors. New palettes were interpolated via Principal Component Analysis (PCA) and GPLVM.

% Applications
Based on palette density estimation and palette interpolation, we developed various applications that would only be possible with these techniques. We introduce a novel application called Photo-style Explorer, which acts like an ``Instagram'' filter but in a continuous design space (Figure~\ref{fig:teaser}). That is, instead of choosing among a few predefined themes, one can freely surf a continuous space of possible photo colorizations to pick a preferred theme. Since the space of color themes is usually of high dimensionality, we utilize dimensionality reduction (GPLVM) to represent it with a familiar 2-D interface. By moving around regions with high likelihood, the user can easily obtain beautiful recolorized photos with the dedicated style of a particular artist. 

Another application of palette interpolation is photo recolorization with multiple local palettes. Conventional recolorization techniques only apply a single set of colors to an entire image via hue adjustment, which leads to unnatural recolorization.  Since an object does not simply contain the same color with different intensities, manual work is required to add more variations to these regions. For example, a tree is generally green but it can also contain blue-like or yellow-like variations of green. By taking the input colors and diversifying them with variations sampled from the palette density, we were able to produce results with more realistic colors (see Section~\ref{sec:photo_recolorization}).
%We call this approach to photo recolorization \emph{enriched photo recolorization}
Additionally, we developed an adaptive color palette that changes with the content being painted. The idea is, since selecting colors is time consuming and requires expertise in color mixing, it would be useful to have a palette that automatically presents to the user with compatible color themes, which fit well to the current content (Figure~\ref{fig:teaser}). For example, as a tree is being painted, the palette will suggest different variations of green (for the leaves) and variations of brown (for the branches). All of the mentioned applications are shown in the video accompanied with this work.

Finally, we carried out quantitative evaluation to measure the performance of our approach with relevant techniques. We conducted an experiment on the task of predicting the missing colors of a palette using GPLVM and other relevant methods. More specifically, given a number of observed colors (e.g., 4, 3, 2, or 1) in the palettes, we predicted the remaining colors of a 5-color palette. The experimental results show that our method yields satisfactory accuracy and is significantly better than previous methods such as ~\cite{o2011color,lin2013probabilistic}. 
\paragraph*{\textbf{Terminology}} The term ``palette''  used in our work is the same as ``color theme'' that appears in previous works.  We use both terms interchangeably.
limitation_conclusion.tex
\vspace{-10pt}
\section{Limitations and Future Work}
Our approach still suffers a number of limitations. First of all, our algorithm does not guarantee perfect alignment between distant palettes. This is due to the fact that we aligned nearby palettes first while distant palettes were implicitly aligned via set alignment (see Section~ \ref{sec:reordering}). In Figure \ref{fig:failed_alignment}, we intentionally include a palette and its brightness-shifted version (palettes in red boxes) into the set. Because the latter is shifted, the two palettes are separated from each other, which causes a slight misalignment (the yellow and the light pink swapped positions). A possible way to improve this is to replace the MHD kernel in the KPCA sorting step (Section \ref{sec:reordering}) with a more advanced kernel, which also considers the structure of the palettes instead of raw distances between colors. Another limitation of our work is, although the photo-style exploration can be potentially useful for real-world use cases, we have not yet evaluated it with user studies. Due to the subjectivity of aesthetic evaluation, it is not straightforward to judge the quality of the stylized results. 
\begin{figure}[ht]
\centering
\includegraphics[width=0.6\linewidth]{images/binary_sort/failed.pdf}
\caption{A case when distant palettes are not perfectly aligned.}\label{fig:failed_alignment}
\vspace{-10pt}
\end{figure}
%\vspace{-10pt}
%In the future, we would like to study more the user-interaction side of this interface and conduct more thorough experiments to better understand its usefulness in real use cases. 
In the future, we would like to study how our model would work on context-specific photo recolorization problems. That is, given a training set containing images of similar scenes such as beach, mountain, summer, etc. would it be possible to make use of our model to recolorize novel images in a consistent way. In Figure~\ref{fig:context_specific}, we show some preliminary results for a particular case of beach scene. We used the same technique discussed in Sec \ref{smartpalette:sec:photoexplorer}. The results look quite promising because areas in the source image have been recolorized with meaningful colors (the sand turns yellow and sky turns indigo).
\begin{figure}[ht]
\centering
\includegraphics[width=0.9\linewidth]{images/context_specific.pdf}
\caption{\huy{Context-specific recolorization. (A) Original image. (B) Training set. (C) Various results.}}\label{fig:context_specific}
\vspace{-5pt}
\end{figure}

\huy{Another possible future work is to study how different segmentation affect the recolorization results. Since our method suggests color palettes based on input colors extracted from segments, a bad segmentation can result in less distinctive results. For example, if the input palette is just shades of the same color (due to a color-based segmentation, for example), the output is likely to be the same because there are indeed many similar palettes in the training set. Thus, in our recolorization pipeline, a good segmentation should partition image into objects and meaningful regions. A similar effect can be seen when comparing the results in Fig. \ref{fig:colorization} and Fig. \ref{fig:explorer_results}. Due to the real-time constraint, the photo-explorer use input palettes extracted globally, which are more distinctive, thus produces more varying results at the cost of local shades. In contrast, the results in Fig.  \ref{fig:colorization} is produced with local input palettes, resulting in richer shades. Depending on the application, one might want to choose one approach or combine them to achieve desirable results.}

\vspace{-5pt}
\section{Conclusion}
We have introduced a novel method for interpolating and summarizing palette data. Palette datasets are often available as unordered sets of colors, making it difficult to directly apply traditional methods to analyze the data. We designed an effective palette ordering method (Binary Palette Sort) that makes use of kernel-based dimensionality reduction to reorder colors in palettes in a meaningful way, allowing us to apply state-of-the-art interpolation techniques on palette data. The palette density provided a mean to develop numerous interesting applications such as real-time adaptive palette, photo-style exploration, enriched photo recolorization. We have conducted both quantitative and qualitative experiments to assess the performance of our method, and favorable results were obtained. In the future, we would like to study in depth how the user interacts with SmartPalette and Photo-style Explorer, possibly through crowd-sourcing and online survey.
main.tex

%% bare_jrnl_compsoc.tex
%% V1.4b
%% 2015/08/26
%% by Michael Shell
%% See:
%% http://www.michaelshell.org/
%% for current contact information.
%%
%% This is a skeleton file demonstrating the use of IEEEtran.cls
%% (requires IEEEtran.cls version 1.8b or later) with an IEEE
%% Computer Society journal paper.
%%
%% Support sites:
%% http://www.michaelshell.org/tex/ieeetran/
%% http://www.ctan.org/pkg/ieeetran
%% and
%% http://www.ieee.org/

%%*************************************************************************
%% Legal Notice:
%% This code is offered as-is without any warranty either expressed or
%% implied; without even the implied warranty of MERCHANTABILITY or
%% FITNESS FOR A PARTICULAR PURPOSE! 
%% User assumes all risk.
%% In no event shall the IEEE or any contributor to this code be liable for
%% any damages or losses, including, but not limited to, incidental,
%% consequential, or any other damages, resulting from the use or misuse
%% of any information contained here.
%%
%% All comments are the opinions of their respective authors and are not
%% necessarily endorsed by the IEEE.
%%
%% This work is distributed under the LaTeX Project Public License (LPPL)
%% ( http://www.latex-project.org/ ) version 1.3, and may be freely used,
%% distributed and modified. A copy of the LPPL, version 1.3, is included
%% in the base LaTeX documentation of all distributions of LaTeX released
%% 2003/12/01 or later.
%% Retain all contribution notices and credits.
%% ** Modified files should be clearly indicated as such, including  **
%% ** renaming them and changing author support contact information. **
%%*************************************************************************


% *** Authors should verify (and, if needed, correct) their LaTeX system  ***
% *** with the testflow diagnostic prior to trusting their LaTeX platform ***
% *** with production work. The IEEE's font choices and paper sizes can   ***
% *** trigger bugs that do not appear when using other class files.       ***                          ***
% The testflow support page is at:
% http://www.michaelshell.org/tex/testflow/


\documentclass[10pt,journal,compsoc]{IEEEtran}
%
% If IEEEtran.cls has not been installed into the LaTeX system files,
% manually specify the path to it like:
% \documentclass[10pt,journal,compsoc]{../sty/IEEEtran}





% Some very useful LaTeX packages include:
% (uncomment the ones you want to load)


% *** MISC UTILITY PACKAGES ***
%
%\usepackage{ifpdf}
% Heiko Oberdiek's ifpdf.sty is very useful if you need conditional
% compilation based on whether the output is pdf or dvi.
% usage:
% \ifpdf
%   % pdf code
% \else
%   % dvi code
% \fi
% The latest version of ifpdf.sty can be obtained from:
% http://www.ctan.org/pkg/ifpdf
% Also, note that IEEEtran.cls V1.7 and later provides a builtin
% \ifCLASSINFOpdf conditional that works the same way.
% When switching from latex to pdflatex and vice-versa, the compiler may
% have to be run twice to clear warning/error messages.




% \usepackage[noadjust]{cite} nocompress

% *** CITATION PACKAGES ***
%
\ifCLASSOPTIONcompsoc
  % IEEE Computer Society needs nocompress option
  % requires cite.sty v4.0 or later (November 2003)
  \usepackage[noadjust]{cite}
\else
  % normal IEEE
  \usepackage[noadjust]{cite}
\fi
% cite.sty was written by Donald Arseneau
% V1.6 and later of IEEEtran pre-defines the format of the cite.sty package
% \cite{} output to follow that of the IEEE. Loading the cite package will
% result in citation numbers being automatically sorted and properly
% "compressed/ranged". e.g., [1], [9], [2], [7], [5], [6] without using
% cite.sty will become [1], [2], [5]--[7], [9] using cite.sty. cite.sty's
% \cite will automatically add leading space, if needed. Use cite.sty's
% noadjust option (cite.sty V3.8 and later) if you want to turn this off
% such as if a citation ever needs to be enclosed in parenthesis.
% cite.sty is already installed on most LaTeX systems. Be sure and use
% version 5.0 (2009-03-20) and later if using hyperref.sty.
% The latest version can be obtained at:
% http://www.ctan.org/pkg/cite
% The documentation is contained in the cite.sty file itself.
%
% Note that some packages require special options to format as the Computer
% Society requires. In particular, Computer Society  papers do not use
% compressed citation ranges as is done in typical IEEE papers
% (e.g., [1]-[4]). Instead, they list every citation separately in order
% (e.g., [1], [2], [3], [4]). To get the latter we need to load the cite
% package with the nocompress option which is supported by cite.sty v4.0
% and later. Note also the use of a CLASSOPTION conditional provided by
% IEEEtran.cls V1.7 and later.





% *** GRAPHICS RELATED PACKAGES ***
%
\ifCLASSINFOpdf
  \usepackage[pdftex]{graphicx}
  % declare the path(s) where your graphic files are
  \graphicspath{{../images/}{../figs/}}
  % and their extensions so you won't have to specify these with
  % every instance of \includegraphics
  \DeclareGraphicsExtensions{.pdf,.jpeg,.png}
\else
  % or other class option (dvipsone, dvipdf, if not using dvips). graphicx
  % will default to the driver specified in the system graphics.cfg if no
  % driver is specified.
  % \usepackage[dvips]{graphicx}
  % declare the path(s) where your graphic files are
  % \graphicspath{{../eps/}}
  % and their extensions so you won't have to specify these with
  % every instance of \includegraphics
  % \DeclareGraphicsExtensions{.eps}
\fi
% graphicx was written by David Carlisle and Sebastian Rahtz. It is
% required if you want graphics, photos, etc. graphicx.sty is already
% installed on most LaTeX systems. The latest version and documentation
% can be obtained at: 
% http://www.ctan.org/pkg/graphicx
% Another good source of documentation is "Using Imported Graphics in
% LaTeX2e" by Keith Reckdahl which can be found at:
% http://www.ctan.org/pkg/epslatex
%
% latex, and pdflatex in dvi mode, support graphics in encapsulated
% postscript (.eps) format. pdflatex in pdf mode supports graphics
% in .pdf, .jpeg, .png and .mps (metapost) formats. Users should ensure
% that all non-photo figures use a vector format (.eps, .pdf, .mps) and
% not a bitmapped formats (.jpeg, .png). The IEEE frowns on bitmapped formats
% which can result in "jaggedy"/blurry rendering of lines and letters as
% well as large increases in file sizes.
%
% You can find documentation about the pdfTeX application at:
% http://www.tug.org/applications/pdftex






% *** MATH PACKAGES ***
%
\usepackage{amsmath}
\usepackage{amssymb}
% A popular package from the American Mathematical Society that provides
% many useful and powerful commands for dealing with mathematics.
%
% Note that the amsmath package sets \interdisplaylinepenalty to 10000
% thus preventing page breaks from occurring within multiline equations. Use:
%\interdisplaylinepenalty=2500
% after loading amsmath to restore such page breaks as IEEEtran.cls normally
% does. amsmath.sty is already installed on most LaTeX systems. The latest
% version and documentation can be obtained at:
% http://www.ctan.org/pkg/amsmath





% *** SPECIALIZED LIST PACKAGES ***
%
\usepackage{algorithm}
\usepackage{algpseudocode}
%\usepackage{algorithmic}
% algorithmic.sty was written by Peter Williams and Rogerio Brito.
% This package provides an algorithmic environment fo describing algorithms.
% You can use the algorithmic environment in-text or within a figure
% environment to provide for a floating algorithm. Do NOT use the algorithm
% floating environment provided by algorithm.sty (by the same authors) or
% algorithm2e.sty (by Christophe Fiorio) as the IEEE does not use dedicated
% algorithm float types and packages that provide these will not provide
% correct IEEE style captions. The latest version and documentation of
% algorithmic.sty can be obtained at:
% http://www.ctan.org/pkg/algorithms
% Also of interest may be the (relatively newer and more customizable)
% algorithmicx.sty package by Szasz Janos:
% http://www.ctan.org/pkg/algorithmicx




% *** ALIGNMENT PACKAGES ***
%
%\usepackage{array}
% Frank Mittelbach's and David Carlisle's array.sty patches and improves
% the standard LaTeX2e array and tabular environments to provide better
% appearance and additional user controls. As the default LaTeX2e table
% generation code is lacking to the point of almost being broken with
% respect to the quality of the end results, all users are strongly
% advised to use an enhanced (at the very least that provided by array.sty)
% set of table tools. array.sty is already installed on most systems. The
% latest version and documentation can be obtained at:
% http://www.ctan.org/pkg/array


% IEEEtran contains the IEEEeqnarray family of commands that can be used to
% generate multiline equations as well as matrices, tables, etc., of high
% quality.




% *** SUBFIGURE PACKAGES ***
%\ifCLASSOPTIONcompsoc
%  \usepackage[caption=false,font=footnotesize,labelfont=sf,textfont=sf]{subfig}
%\else
%  \usepackage[caption=false,font=footnotesize]{subfig}
%\fi
% subfig.sty, written by Steven Douglas Cochran, is the modern replacement
% for subfigure.sty, the latter of which is no longer maintained and is
% incompatible with some LaTeX packages including fixltx2e. However,
% subfig.sty requires and automatically loads Axel Sommerfeldt's caption.sty
% which will override IEEEtran.cls' handling of captions and this will result
% in non-IEEE style figure/table captions. To prevent this problem, be sure
% and invoke subfig.sty's "caption=false" package option (available since
% subfig.sty version 1.3, 2005/06/28) as this is will preserve IEEEtran.cls
% handling of captions.
% Note that the Computer Society format requires a sans serif font rather
% than the serif font used in traditional IEEE formatting and thus the need
% to invoke different subfig.sty package options depending on whether
% compsoc mode has been enabled.
%
% The latest version and documentation of subfig.sty can be obtained at:
% http://www.ctan.org/pkg/subfig




% *** FLOAT PACKAGES ***
%
%\usepackage{fixltx2e}
% fixltx2e, the successor to the earlier fix2col.sty, was written by
% Frank Mittelbach and David Carlisle. This package corrects a few problems
% in the LaTeX2e kernel, the most notable of which is that in current
% LaTeX2e releases, the ordering of single and double column floats is not
% guaranteed to be preserved. Thus, an unpatched LaTeX2e can allow a
% single column figure to be placed prior to an earlier double column
% figure.
% Be aware that LaTeX2e kernels dated 2015 and later have fixltx2e.sty's
% corrections already built into the system in which case a warning will
% be issued if an attempt is made to load fixltx2e.sty as it is no longer
% needed.
% The latest version and documentation can be found at:
% http://www.ctan.org/pkg/fixltx2e


%\usepackage{stfloats}
% stfloats.sty was written by Sigitas Tolusis. This package gives LaTeX2e
% the ability to do double column floats at the bottom of the page as well
% as the top. (e.g., "\begin{figure*}[!b]" is not normally possible in
% LaTeX2e). It also provides a command:
%\fnbelowfloat
% to enable the placement of footnotes below bottom floats (the standard
% LaTeX2e kernel puts them above bottom floats). This is an invasive package
% which rewrites many portions of the LaTeX2e float routines. It may not work
% with other packages that modify the LaTeX2e float routines. The latest
% version and documentation can be obtained at:
% http://www.ctan.org/pkg/stfloats
% Do not use the stfloats baselinefloat ability as the IEEE does not allow
% \baselineskip to stretch. Authors submitting work to the IEEE should note
% that the IEEE rarely uses double column equations and that authors should try
% to avoid such use. Do not be tempted to use the cuted.sty or midfloat.sty
% packages (also by Sigitas Tolusis) as the IEEE does not format its papers in
% such ways.
% Do not attempt to use stfloats with fixltx2e as they are incompatible.
% Instead, use Morten Hogholm'a dblfloatfix which combines the features
% of both fixltx2e and stfloats:
%
% \usepackage{dblfloatfix}
% The latest version can be found at:
% http://www.ctan.org/pkg/dblfloatfix




%\ifCLASSOPTIONcaptionsoff
%  \usepackage[nomarkers]{endfloat}
% \let\MYoriglatexcaption\caption
% \renewcommand{\caption}[2][\relax]{\MYoriglatexcaption[#2]{#2}}
%\fi
% endfloat.sty was written by James Darrell McCauley, Jeff Goldberg and 
% Axel Sommerfeldt. This package may be useful when used in conjunction with 
% IEEEtran.cls'  captionsoff option. Some IEEE journals/societies require that
% submissions have lists of figures/tables at the end of the paper and that
% figures/tables without any captions are placed on a page by themselves at
% the end of the document. If needed, the draftcls IEEEtran class option or
% \CLASSINPUTbaselinestretch interface can be used to increase the line
% spacing as well. Be sure and use the nomarkers option of endfloat to
% prevent endfloat from "marking" where the figures would have been placed
% in the text. The two hack lines of code above are a slight modification of
% that suggested by in the endfloat docs (section 8.4.1) to ensure that
% the full captions always appear in the list of figures/tables - even if
% the user used the short optional argument of \caption[]{}.
% IEEE papers do not typically make use of \caption[]'s optional argument,
% so this should not be an issue. A similar trick can be used to disable
% captions of packages such as subfig.sty that lack options to turn off
% the subcaptions:
% For subfig.sty:
% \let\MYorigsubfloat\subfloat
% \renewcommand{\subfloat}[2][\relax]{\MYorigsubfloat[]{#2}}
% However, the above trick will not work if both optional arguments of
% the \subfloat command are used. Furthermore, there needs to be a
% description of each subfigure *somewhere* and endfloat does not add
% subfigure captions to its list of figures. Thus, the best approach is to
% avoid the use of subfigure captions (many IEEE journals avoid them anyway)
% and instead reference/explain all the subfigures within the main caption.
% The latest version of endfloat.sty and its documentation can obtained at:
% http://www.ctan.org/pkg/endfloat
%
% The IEEEtran \ifCLASSOPTIONcaptionsoff conditional can also be used
% later in the document, say, to conditionally put the References on a 
% page by themselves.




% *** PDF, URL AND HYPERLINK PACKAGES ***
%
\usepackage{url}
% url.sty was written by Donald Arseneau. It provides better support for
% handling and breaking URLs. url.sty is already installed on most LaTeX
% systems. The latest version and documentation can be obtained at:
% http://www.ctan.org/pkg/url
% Basically, \url{my_url_here}.





% *** Do not adjust lengths that control margins, column widths, etc. ***
% *** Do not use packages that alter fonts (such as pslatex).         ***
% There should be no need to do such things with IEEEtran.cls V1.6 and later.
% (Unless specifically asked to do so by the journal or conference you plan
% to submit to, of course. )

%\usepackage{named}
\usepackage{color}
\newcommand{\huy}[1]{\textcolor{black}{#1}}
\newcommand{\huya}[1]{\textcolor{black}{#1}}

%\newcommand{\hongbo}[1]{\textcolor{red}{#1}}
%\newcommand{\hongbon}[1]{\textcolor{red}{[Hongbo: #1]}}
%\newcommand{\abc}[1]{\textcolor{blue}{#1}}
%\newcommand{\abcnote}[1]{\textcolor{blue}{[NOTE: #1]}}

% correct bad hyphenation here
\hyphenation{op-tical net-works semi-conduc-tor}
\input{body}
methodology.tex
\section{Methodology}
As illustrated in Figure~\ref{fig:teaser}, our method for modeling the density of color palettes can be divided into 3 steps: 
\begin{itemize}
\item \textbf{Data Collection and Preprocessing}: We collected images of different artists and extracted color themes from local regions.
\item \textbf{Palette Ordering}: We ordered the colors in each palette in a consistent way.
\item \textbf{Learning and Inference}: We applied density estimation techniques and performed interpolation on palette data.
\end{itemize}
\vspace{-10pt}
\subsection{Data Collection and Preprocessing}\label{sec:dataset}
As partially shown in Figure~\ref{smartpalette:fig:dataset} (Top), we collected 40 paintings for each of 17 well-known artists such as Pierre-Auguste Renoir (Renoir), Vincent Willem van Gogh, Raffaello Sanzio da Urbino (Raphael), Maximilien Luce (Luce), Paul C\'{e}zanne (Cezanne), Hilaire-Germain-Edgar De Gas (De Gas), and William Merritt Chase (Chase). All the paintings were rescaled so that the larger dimension is 500 pixels. As explained in Section~\ref{smartpalette:sec:intro}, instead of treating a whole painting as a single palette,  we extracted palettes from local patches from the paintings, which capture the local contexts. Specifically, we extracted patches of 200x200 pixels from the paintings using a sliding window with a step-size of 100 pixels. 
Next, we selected 1000 pixels from each patch by randomly sampling from the patch. Subsequently, we applied K-Means in the CIE*Lab space to cluster the pixels in each patch to obtain $K$ clusters (Figure \ref{smartpalette:fig:dataset} (Mid)), thus forming one color palette per patch.  We randomly selected 400 palettes per artist and aggregated them together to form a dataset of color palettes \---\ one dataset per artist. We call our palette datasets the \emph{Artistic Palette Datasets}. For quantitative study, we chose $K=5$, which follows previous works~\cite{o2011color,lin2013probabilistic}. Our methodology is, however, independent from the size of the palette. Thus, the number of colors can be chosen arbitrarily, depending on the application. For some applications, such as photo recolorization and multi-style painting, which often need more colors, we used $K=7$ (Figure \ref{smartpalette:fig:dataset} (Bottom)). We also used $K=10$ for demonstration purpose in Section ~\ref{sec:evals}. Please refer to Section~\ref{smartpalette:sec:eval_ordering} for more discussions about $K$.
\begin{figure}[ht]
  \centering
  \includegraphics[width=0.8\linewidth]{images/datasets_renoir.png}
  \includegraphics[width=0.8\linewidth]{images/themes_renoir.png}
  \includegraphics[width=0.8\linewidth]{images/themes_renoir_10cols.png}
  \caption{Our dataset contains a set of 40 images from each of 17 well-known artists. (Top) paintings from Renoir set. (Mid) 5-color palettes extracted from the set. (Bottom) 7-color palettes extracted from the set. Each column is a color palette.}\label{smartpalette:fig:dataset}
\vspace{-10pt}
\end{figure}
\subsection{Palette Ordering}\label{sec:reordering}
In this section, we discuss the palette ordering problem and our solution. We also show comparisons with some other methods in Section~\ref{smartpalette:sec:evalsort}.
\subsubsection{Problem Statement}
\begin{figure}[ht]
\centering
\includegraphics[width=0.8\linewidth]{images/correspondence.pdf}
\caption{Palettes extracted from similar patches often have correspondences. The extracted palettes were ordered with Binary Palette Sort.}\label{smartpalette:fig:correspondence}
\vspace{-15pt}
\end{figure}
The goal of palette ordering is to order the colors in each palette, so that linear interpolation between ordered palettes yields meaningful results \---\ i.e., the colors that describe the same objects should have the same indices. The intuition is, the palette dataset might contain palettes that come from the same context, and thus there are always semantic correspondences between the colors. Figure \ref{smartpalette:fig:correspondence} shows an example, in which both patches contain sky scene and one can observe the correspondences between cloud colors and between sky colors. It is, however, too costly to manually annotate all semantic regions as an image might contain hundreds of regions. We overcome this difficulty by assuming that patches containing similar sets of colors should have similar contexts. Our algorithm can guarantee that similar palettes are optimally aligned. Very different palettes are only roughly aligned via palette set ordering, as described in Section~\ref{smartpalette:sec:binarysortalgo}.

Formally, given a palette dataset $X=\{\mathbf{P}_1, ... , \mathbf{P}_N\}$, with $N$ is the number of palettes. We have the palette $\mathbf{P}_n = \left[ \mathbf{p}_n^1, \hdots,  \mathbf{p}_n^K \right]^T $ , where $\mathbf{p}_n^k$ is a color (a 3D vector).  
% The algorithm is, however, independent from the color space being used. 
The goal is to solve the following optimization problem, which minimizes the pairwise distances between the palettes:
\begin{equation}\label{smartpalette:eqn:globaopt}
\mathrm{argmin}_{\mathbf{g}} \sum_{n=1}^{N} \sum_{m=1}^{N} \sum_{k=1}^{K} \lVert \mathbf{p}_{n}^{g_n(k) } - \mathbf{p}_{m}^{g_m(k) } \rVert, 
\end{equation}
 where $g_n: \mathbb{K} \rightarrow \mathbb{K},~\mathbb{K} = \{ 1, \hdots, K \} $ is a bijection that maps an index $k$ to another index $k'$. Solving the palette ordering problem thus has the complexity $\mathcal{O}( (K!)^N )$, which grows exponentially with the number of palettes.
 
Given that each dataset in our Artistic Palette Datasets contains 400 hundred palettes, it is not feasible to solve the problem ~(\ref{smartpalette:eqn:globaopt}) with brute-force. To this end, we introduce the Binary Palette Sort algorithm (BPS) \---\ an ordering algorithm that uses a divide-and-conquer strategy to achieve a reasonable solution for~(\ref{smartpalette:eqn:globaopt}). 
 \begin{figure}[ht]
\centering
\includegraphics[width=1.0\linewidth]{images/binary_sort/binary_vs_lightness_new.pdf}
\caption{\huy{Example of palette ordering with our method. (A) Binary Palette Sort and (B) Unordered. Each column is a paletete. The red dot boxes in (A) highlight the rows in which colors are smoothly arranged.}}\label{fig:comparesort}
\end{figure}

We motivate the strategy of BPS by showing a typical palette dataset in Figure~\ref{fig:comparesort} (B). As a palette dataset might contain color palettes that are very different from each other, it is less important to align such palettes, comparing to the similar ones. For instance, the first palette (first column) in Figure~\ref{fig:comparesort} (B) represents a sky and thus aligning it to the last palette (last column), which comes from a tree, does not make sense. This is the key observation that motivates our sorting algorithm. We prioritize the matching between nearby palettes over distant palettes. Distant palettes are still roughly aligned via set alignment, which will be discussed later.
 
  \begin{figure}[ht]
\centering
\includegraphics[width=0.95\linewidth]{images/binary_sort/binary_sort.pdf}
\vspace{-10pt}
\caption{Example of palette arrangement with Binary Palette Sort. The unordered palettes were partitioned by considering the similarities between palettes.}\label{fig:binarysort}
\vspace{-15pt}
\end{figure}
\subsubsection{The Binary Palette Sort Algorithm}\label{smartpalette:sec:binarysortalgo}
Intuitively, BPS recursively partitions the dataset $X$ into two subsets until there is only one palette left in each subset and then works the way back to the first call by aligning and merging each pair of subsets into an ordered list. The result is a set of sorted palettes (see Figure \ref{fig:binarysort}).  Our BPS algorithm is similar to Merge Sort~\cite{thomas2001introduction} in strategy but has a different merging method and a different objective. In our context, the objective of Merge Sort would be to rearrange a list of color palettes while the objective of Binary Palette Sort is to rearrange the colors in each palette, while the order of the palettes is fixed. BPS has a complexity  of $\mathcal{O}(N K^4)$, which is feasible to solve. At each level of recursion, we solve a sorting sub-problem that aligns two sets of color palettes, where each set can have a different number of palettes (see the description of \emph{Sort} below).

Given the palette dataset $X$, our algorithm to approximate the solution for~(\ref{smartpalette:eqn:globaopt}) is expressed recursively as
\begin{multline}
\mathrm{Sort}(X) = \mathrm{Merge}( \mathrm{Sort}(\mathrm{Partition}_{l}(X)), \\
\mathrm{Sort}(\mathrm{Partition}_{r}(X)) ),
\end{multline}
where we use subscripts $l$ and $r$ to denote the two partitions produced by the subroutine $Partition$. Each subroutine is given in details below.
% and Algorithm ~\ref{alg:binary_sort} summarizes the algorithm in pseudo-code. 
\paragraph*{\textbf{Sort}} The sort subroutine takes a palette dataset $X$ and returns a new palette dataset $X'$, whose each member palette is aligned.  The routine starts from the lowest level of the tree, solving a case of \emph{linear assignment problem} (LAP), in which both $P'$ and $Q'$ are singletons, merging the aligned sets together and moving up to the higher level. If a leaf node does not have a ``partner'' to match (the rightmost leaf nodes in Figure \ref{fig:binarysort}), the routine just passes it to the upper level. At the upper level, the subroutine repeats the assigning and merging processes that have been done at the lower level. Note that now each set may contain a different number of palettes (see Figure \ref{fig:binarysort} (Right)). 

To align two sets of palettes, we need to solve a linear assignment problem as follows:  Given two sets of color palettes $P =\{\mathbf{P}_n \}_{n=1}^{N}$ and $Q =\{\mathbf{Q}_n\}_{n=1}^{M}$, where $N, M$ are the numbers of palettes, we have the color palettes $\mathbf{P}_n=\left[\mathbf{p}_n^1, \hdots, \mathbf{p}_n^K \right]^T, \mathbf{Q}_n=\left[\mathbf{q}_n^1, \hdots, \mathbf{q}_n^K \right]^T$, where $K$ is the number of colors in each palette and $\mathbf{q}_n^k, \mathbf{p}_n^k$ are the colors. 

By grouping corresponding colors in the palettes in each set together, we obtain matrices $\mathbf{P}^k = \left[ \mathbf{p}_1^k, \hdots, \mathbf{p}_N^k  \right]^T$ and $\mathbf{Q}^k = \left[ \mathbf{q}_1^k, \hdots, \mathbf{q}_M^k  \right]^T$ which can also be viewed as color palettes. In Figure~\ref{fig:binarysort}, $\mathbf{P}_n$ and $\mathbf{Q}_n$ are the matrices (blocks of colors), each column is a palette. $\mathbf{P}^k$ is the k-th row in the color matrix, which will form the corresponding colors. We want to match the rows of $\mathbf{P}_n$ and $\mathbf{Q}_n$ so that they are aligned well according to the distance $d$ (see below). The problem is stated as:
\begin{equation}\label{smartpalette:eqn:newopt}
\mathrm{argmin}_{g}\sum_{k=1}^K f(\mathbf{P}^k, \mathbf{Q}^{g(k)} ),
\end{equation} where $f$ is the distance between sets of colors and $g$ is similar to that of (\ref{smartpalette:eqn:globaopt}). In our implementation, $g$ is found with the Hungarian algorithm~\cite{kuhn1955hungarian} and $f$ is given below.
 Since the palettes $\mathbf{P}^k$ and $\mathbf{Q}^k$ have different lengths, we cannot apply conventional metrics for vectors such as the Euclidean distance. Instead, we utilize the modified Hausdorff distance (MHD) introduced in~\cite{dubuisson1994modified}. The MHD between two palettes of different lengths $\mathbf{P}^k$ and $\mathbf{Q}^h, ~\text{for } h=g(k)$ is calculated as follows:
\[ \max(d(\mathbf{P}^k, \mathbf{Q}^h), d(\mathbf{Q}^k, \mathbf{P}^h))
, \]
where 
\[
d(\mathbf{P}^k , \mathbf{Q}^h) = \frac{1}{N} \sum_{i=1}^{N} \min_{j \in 1:M} \lVert \mathbf{p}_i^k - \mathbf{q}_j^h \rVert.
\] $d(\mathbf{Q}^h, \mathbf{P}^k)$ can be defined similarly. 
The process is repeated until all the palettes in the dataset are merged into a single set. At this point, we have already obtained a sorted set of  palettes where the colors in the same row are close to each other. 
\paragraph*{\textbf{Merge}}
The $Merge$ subroutine merges two sets of color palettes into a new set, in which the palettes are aligned with the indices $g(k)$ is taken from (\ref{smartpalette:eqn:newopt}). Figure~\ref{fig:binarysort} (Right) gives an example of this step.
\begin{equation}\label{smartpalette:eqn:merge}
    \mathrm{Merge}(P,~Q) = 
    \begin{cases}
     	P ,~\text{for } Q = \emptyset \\
     	Q ,~\text{for } P = \emptyset \\
     	P \cup
     	\left\lbrace
     	\left[
		\begin{matrix}
		\mathbf{q}_1^{g(1)}      \\
		\vdots \\
		\mathbf{q}_1^{g(K)} 
		\end{matrix}
		\right]
		, \hdots ,
     	\left[
		\begin{matrix}
		\mathbf{q}_M^{g(1)}      \\
		\vdots \\
		\mathbf{q}_M^{g(K)} 
		\end{matrix}
		\right]
		\right\rbrace
   \end{cases}.
\end{equation}
\paragraph*{\textbf{Partition}}
This subroutine divides the set $X$ into two subsets $X_l, X_r, X_l \cap X_r = \emptyset $ while minimizing the total distance from the data points in each subset to the center of the subset. The goal is to ensure that palettes in each subset are close to each other.
\begin{equation}\label{smartpalette:eqn:partition}
\mathrm{argmin}_{\gamma, \mu_l, \mu_r} 
\sum_{n=1}^{N} \gamma(\mathbf{P}_n) \bigl \lVert   \mathbf{P}_n -  \mu_l \bigr  \rVert + 
\sum_{n=1}^{N} (1 - \gamma(\mathbf{P}_n)) \bigl \lVert   \mathbf{P}_n -  \mu_r   \bigr \rVert ,
\end{equation} where $\mu_l,~\mu_r$ are the centers of each subset and $\gamma$ is: 
\[
\gamma(\mathbf{P}_n) = 
\begin{cases}
0, \forall \mathbf{P}_n \not\in X_l \\
1, \forall \mathbf{P}_n \in X_l
\end{cases}.
\] 
We then have 
\begin{align}\label{smartpalette:eqn:partition_a}
X_l & = \{ \mathbf{P}_n | \forall \mathbf{P}_n \in X, \gamma(\mathbf{P}_n) = 1 \}, \nonumber \\
X_r & = \{ \mathbf{P}_n | \forall \mathbf{P}_n \in X, \gamma(\mathbf{P}_n) = 0 \}.
\end{align}
This process is repeated until each subset contains only a single palette, resulting in a tree in which each node is a set of palettes and the leaf nodes are singletons. Although there are solutions such as the K-medoids algorithm for the problem (\ref{smartpalette:eqn:partition}), it could be costly to apply them in practice. To speed up the algorithm, we present an alternative partition method that has comparable performance and is much faster. Intuitively, the new partition method projects the palettes onto a line and then orders the palettes according to the projected coordinates. The dataset is then partitioned by the palettes' indices. Specifically, we used kernel principal component analysis (KPCA)~\cite{Scholkopf:1999}, which can operate on sets, to project our palettes. The kernel used was derived from the MHD distance introduced above (MHD kernel). Although there are other powerful kernels like the pyramid match kernel (PMK)~\cite{grauman2005pyramid}, which work on sets, we found that the MHD-based kernel is sufficiently accurate and is the fastest method, allowing it to work in real-time. In fact, as PMK was designed for matching large sets, it did not perform well on our palette data and was also too slow for our applications. The left side of Figure \ref{fig:binarysort} demonstrates this process.

\begin{figure}[ht]
\centering
\includegraphics[width=0.8\linewidth]{images/density_estimation/fig.pdf} 
\vspace{-10pt}
\caption{A sample palette density produced by GPLVM. Gray values indicate the likelihoods of the palettes.}\label{fig:gmm_gplvm_density}
\vspace{-10pt}
\end{figure}
\subsection{Learning and Inference}\label{sec:density}
Prior to learning and inference, we directly concatenated colors in an ordered palette to form a vector of dimensionality 15 (for 5 colors), 21 (for 7 colors) and 30 (for 10 colors). Given the concatenated dataset, we performed \emph{palette interpolation}, \emph{density estimation}, and \emph{color prediction}. Although there are many possible approaches to our problems such as neural networks~\cite{hinton2006reducing} and latent Dirichlet allocation~\cite{blei2003latent}, we chose a standard method named Gaussian process latent variable models (GPLVM)~\cite{lawrence2004gaussian} for its ability to deal with small datasets, which is the case of our work.
\vspace{-5pt}
\subsubsection{Palette Interpolation}\label{smartpalette:sec:palette_interpolation}
GPLVM was first introduced by Lawrence et al. for the purpose of nonlinear dimensionality reduction (NLDR) and visualization~\cite{lawrence2004gaussian}. It shares the same objective function with popular dimensionality reduction methods such as KPCA, Probabilistic PCA, and Multidimensional Scaling (MDS)~\cite{kruskal1964multidimensional}.  The main advantage of GPLVM over other methods is the non-linear mapping from latent space to observed space. This means that it is suitable for non-linear data interpolation, which is the case of our work. We interpolated new palettes by sampling data points from the low dimensional space induced by GPLVM. GPLVM provides a mechanism to project these latent points back to the palette space via Gaussian Processes (GPs). The main computation for training a GPLVM is the nonlinear minimization of the negative log-likelihood function with respect to the kernel parameters and the latent points~\cite{lawrence2004gaussian}. This minimization was done with a gradient-based optimizer, the scaled conjugate gradient method (SCG).
\paragraph*{\textbf{Manifold learning}}
A concept related to NLDR is \emph{manifold learning}~\cite{ma2011manifold}, one common approach to NLDR. Manifold learning aims to find an embedded non-linear topological manifold in a high dimensional space. By projecting data onto a low dimensional manifold, one can visualize complex data in an understandable manner. In our work, we are interested in the inverse projection that maps the low dimensional data points back to the original space. The idea is to let the user interact with palette data in a low dimensional space \---\ 2D, in our case \---\ and to observe the results of these interaction in the palette space.
\vspace{-5pt}
\subsubsection{Density Estimation}\label{smartpalette:sec:density_estimation}
GPLVM assigns likelihoods to data points in the latent space, which can be interpreted as a \textit{density}. In our implementation, GPLVM was trained with the Radial Basis Function (RBF) kernel~\cite{vert2004primer}, and the number of latent dimensions was 4.  In Figure \ref{fig:gmm_gplvm_density}, we show an example of palette density, induced by GPLVM. The two most significant dimensions were chosen for visualization. The palettes were taken from 4 datasets: De Gas, Luce, Gogh and Raphael. For demonstration purpose, we chose the number of colors to be 10.

To justify our choice of the learning model, we also experimented with principal component analysis (PCA) for dimensionality reduction and Gaussian mixture models (GMM) for density estimation.The experiments show that GPLVM, as a non-linear method can produce more diverse results than PCA-GMM, which is a desired characteristic in our applications (see sample results for both methods in Section~\ref{smartpalette:sec:eval_interpolation}). In addition, the quantitative experiment in Section \ref{sec:evals} shows that GPLVM is slightly more accurate in predicting colors.

\vspace{-5pt}
\subsubsection{Predicting Compatible Colors}\label{sec:palette_completion}

To recover the missing colors with GPLVM, we first projected the partially observed palette $\mathbf{y}_*^o$ onto the latent space using the technique described in \cite{lawrence2004gaussian}. This technique involves the selection of an initial position for the latent point $\mathbf{x}_*$ by finding a similar point in the input space (palette space). The latent point is found by minimizing the same objective function as in the training step with respect to $\mathbf{x}_*$ while $\mathbf{y}_*^o$ and other parameters are fixed. GPLVM handles the missing dimensions by setting the corresponding noise variances to infinity. The likeliness between the predicted palette and the query palette can be controlled by setting the number of iterations in the minimization step. To recover the palette, we used a standard GPs prediction that maps data points from the latent space to input space. Both of the mentioned methods (PCA-GMM and GPLVM) are fast and can be used for real-time prediction.
related_work.tex
\vspace{-5pt}
\section{Related Work}\label{sec:related_works}
%In this section, we review different techniques for color harmonization and color picking.
In this section, we discuss major research fields related to the color and theme studies.
\vspace{-10pt}
\subsection{Color Harmony}
%talk about color hamorny
Color is a popular research topic in many fields of arts and sciences. In psychology, for instance, various models have been proposed to capture the harmony of color combinations~\cite{schloss2011aesthetic,ou2006colour}.
These models often aim at deriving common ``laws'' of color compatibility by conducting psychological experiments on human perception. On the other hand, the graphics community is more interested in modeling color harmony for design and visualization. Cohen Or et al.~\cite{cohen2006color} directly apply harmony templates derived from classic color theories to the task of color harmonization.  Nishiyama et al.~\cite{Nishiyama2011} make use of color harmony to assess the quality of photographs.  Sauvaget et al.~\cite{sauvaget2010segmented} use color harmony for segmented photo colorization.  O'Donovan et al.~\cite{o2011color} take a data-driven approach by learning to predict color ratings from large datasets. They show interesting applications such as color suggestion, theme extraction, and theme optimization. Later the same authors propose a collaborative filtering approach to capture user preference of color combinations~\cite{o2014collaborative}. Recently, Lin et al.~\cite{lin2013probabilistic} incorporate the rating regression model in a factor graph that assigns harmonious colors to 2D patterns. Similar to our method, their work also performs palette interpolation but relies on a computationally expensive inference technique \---\ the Markov chain Monte Carlo method  (MCMC) \---\ which is unsuitable for real-time applications. Besides, the function that actually deals with input data only considers pair-wise relationships between colors in the palettes, while the global compatibility function is not trained on the input data. In contrast, our compatibility prediction comes from the probability density function, which is trained on the input data.
 In our color prediction experiment, we show that our method produces more accurate prediction than the methods introduced in~\cite{o2011color,lin2013probabilistic}. Moreover, our method is also fast enough to be integrated into real-time applications such as photo-style explorer and real-time color suggestion (see Section~\ref{sec:apps}).
\vspace{-10pt}
\subsection{Image Recolorization and Stylization}
Our work is also related to the problem of image recolorization and stylization. Color transfer is a standard approach for image colorization \cite{reinhard2001color}. The basic idea is to map the color distribution from a reference image to a given image. To model the color distribution, one can first extract color themes from reference images and then perform transferring~\cite{bonneel2013example,reinhard2001color,wang2010data}. Alternatively, histograms can be used to directly map the colors between images \cite{Neumann:2005}.  The method of Liu et al.~\cite{CGF:CGF12409} automatically discovers styles in a collection of user images via a clustering approach. The major difference between this work and ours to image recolorization is that, instead of clustering the photo collections, we applied \emph{manifold learning}~\cite{ma2011manifold} on palette data to interpolate color palette on demand. The interpolation allows us to generate variations of the existing color themes, thus providing the user with a wider range of color choices. 

Chang et al.~\cite{chang2015palette} provide an intuitive interface to recolorize an image by manually modifying a global color palette representing the image. Our work also introduces a method to recolorize an image with palettes. However, instead of letting the user modify the palettes, we automatically generate them from the palette manifold. 
% Moreover, we use multiple local palettes instead of one global palette for each image.
Since our focus is to generate reasonable palettes rather than the recolorization technique itself, we do not provide comparative study with conventional methods in the field.  Chia et al.~\cite{chia2011semantic} introduce an interesting approach to grey-scale image colorization by retrieving semantically similar photographs from the Internet. Nguyen et al.~\cite{nguyen2015data} also retrieve images of an object and model a color manifold for that object.  Note that our method models the manifold of \textit{color palettes} rather than \textit{colors}, which is more complicated since we need correspondences between colors. Consequently, our method is specifically designed for the purpose of color suggestion and color compatibility prediction.
%In other words, we study compatibility of colors in a palette, not just color variations of a single object. 
%These two studies and the works of \cite{wang2010data,wang2011example,bonneel2013example,lin2013probabilistic,huang2014learning} are examples of using data-driven approaches for image colorization and stylization.
\vspace{-10pt}
\subsection{Color Picking and Recommendation}
Color picking is an essential component of all design software. 
Basic color pickers provide a wheel-like interface, where the user drags the pointer around the gamuts to find the right color, or a slider-like interface that allows the user to adjust color components individually. More advanced tools, like Adobe Color CC~\cite{adobecolor2015} or Coolorus~\cite{coolorus2015}, help the user to choose harmonious color combinations by using harmony templates, which are derived from classic color theories~\cite{itten1970elements,matsuda1995color,tokumaru2002color}. Another strategy is to clip the color gamut to limit the color choices to ``harmonious groups''~\cite{coolorus2015}. For people who are acquainted with physical palettes, Corel Painter~\cite{corelpainter2015} and MyPaint~\cite{mypaint2015} provide color mixer pads that simulate real-world color mixing. Gradient mixer~\cite{meier2004interactive} is another tool that displays gradients between colors to add more variations to the current palette. Our model allows interpolation between palettes, thus, at some points on the manifolds, one can find ``in-between'' colors similar to  the gradient mixer. Palette breeder~\cite{meier2004interactive} is an interesting tool that uses a genetic algorithm to ``breed'' palettes and generates new ones. Wijffelaars et al.~\cite{wijffelaars2008generating} suggest an intuitive interface that uses curves to represent color harmony parameters. Using color names is another way to select color~\cite{heer2012color}. 

Nguyen et al.~\cite{nguyen2015data} use a color manifold and apply dimensionality reduction to ease the task of changing colors of an object. Our user interface also provides a mechanism for the user to continuously surf through variations of colorizations. As we also model the density of color themes, our interface assists users by displaying the probabilities associated with the variations, assisting them in browsing the theme space. The work of Shapira et al.~\cite{shapira2009image} suggests a promising parametric interface for browsing possible appearance of an image but does not provide recommendations to the user and is not data-driven. Similarly, Marks et al.~\cite{marks1997design} introduce a framework called Design Galleries that displays variations of a parametric graphical object in a reasonable way (e.g. images, animations...). Their method is not data-driven and their focus is to present an object's variations rather than to recommend variations, as in our work.
\vspace{-10pt}
\subsection{Object Arrangement and Browsing}
Our palette arrangement is close to the more generic problem of object arrangement. The objective is to arrange a set $A=\{a_1,...,a_N\} \in X $ of objects into a set $B=\{b_1, ...,b_N\} \in Y$ of locations so that the pairwise distances between objects in $A$ are preserved  as much as possible after being aligned into $B$. A popular solution for this problem is the ``kernelized sorting'' technique introduced in ~\cite{quadrianto2009kernelized}, in which the authors utilize kernels and a learned centering matrix to make distances in $X$ and $Y$ comparable. More recently, Fried et al. elaborate a method to match a set of objects with a layout called IsoMatch~\cite{fried2015isomatch}. Although our method is similar to IsoMatch in a spirit, the goals of the two methods are different. While IsoMatch aims at arranging N objects to N locations, our problem is to solve a set of M such problems, which are interdependent.
% In fact, IsoMatch can be integrated into our sorting scheme to support a wider range of objects. 


main.bbl
% Generated by IEEEtran.bst, version: 1.14 (2015/08/26)
\begin{thebibliography}{10}
\providecommand{\url}[1]{#1}
\csname url@samestyle\endcsname
\providecommand{\newblock}{\relax}
\providecommand{\bibinfo}[2]{#2}
\providecommand{\BIBentrySTDinterwordspacing}{\spaceskip=0pt\relax}
\providecommand{\BIBentryALTinterwordstretchfactor}{4}
\providecommand{\BIBentryALTinterwordspacing}{\spaceskip=\fontdimen2\font plus
\BIBentryALTinterwordstretchfactor\fontdimen3\font minus
  \fontdimen4\font\relax}
\providecommand{\BIBforeignlanguage}[2]{{%
\expandafter\ifx\csname l@#1\endcsname\relax
\typeout{** WARNING: IEEEtran.bst: No hyphenation pattern has been}%
\typeout{** loaded for the language `#1'. Using the pattern for}%
\typeout{** the default language instead.}%
\else
\language=\csname l@#1\endcsname
\fi
#2}}
\providecommand{\BIBdecl}{\relax}
\BIBdecl

\bibitem{o2011color}
P.~O'Donovan, A.~Agarwala, and A.~Hertzmann, ``Color compatibility from large
  datasets,'' in \emph{ACM Transactions on Graphics (TOG)}, vol.~30,
  no.~4.\hskip 1em plus 0.5em minus 0.4em\relax ACM, 2011, p.~63.

\bibitem{lin2013probabilistic}
S.~Lin, D.~Ritchie, M.~Fisher, and P.~Hanrahan, ``Probabilistic
  color-by-numbers: Suggesting pattern colorizations using factor graphs,''
  \emph{ACM Transactions on Graphics (TOG)}, vol.~32, no.~4, p.~37, 2013.

\bibitem{huang2014learning}
H.-Z. Huang, S.-H. Zhang, R.~Martin, and S.-M. Hu, ``Learning natural colors
  for image recoloring,'' in \emph{Computer Graphics Forum}.\hskip 1em plus
  0.5em minus 0.4em\relax Wiley Online Library, 2014.

\bibitem{wang2010data}
B.~Wang, Y.~Yu, T.-T. Wong, C.~Chen, and Y.-Q. Xu, ``Data-driven image color
  theme enhancement,'' \emph{ACM Transactions on Graphics (TOG)}, vol.~29,
  no.~6, p. 146, 2010.

\bibitem{wang2011example}
B.~Wang, Y.~Yu, and Y.-Q. Xu, ``Example-based image color and tone style
  enhancement,'' in \emph{ACM Transactions on Graphics (TOG)}, vol.~30,
  no.~4.\hskip 1em plus 0.5em minus 0.4em\relax ACM, 2011, p.~64.

\bibitem{mollica2013color}
P.~Mollica, \emph{Color Theory: An essential guide to color-from basic
  principles to practical applications}.\hskip 1em plus 0.5em minus 0.4em\relax
  Walter Foster Pub, 2013.

\bibitem{schloss2011aesthetic}
K.~B. Schloss and S.~E. Palmer, ``Aesthetic response to color combinations:
  preference, harmony, and similarity,'' \emph{Attention, Perception, \&
  Psychophysics}, vol.~73, no.~2, pp. 551--571, 2011.

\bibitem{ou2006colour}
L.-C. Ou and M.~R. Luo, ``A colour harmony model for two-colour combinations,''
  \emph{Color Research \& Application}, vol.~31, no.~3, pp. 191--204, 2006.

\bibitem{cohen2006color}
D.~Cohen-Or, O.~Sorkine, R.~Gal, T.~Leyvand, and Y.-Q. Xu, ``Color
  harmonization,'' \emph{ACM Transactions on Graphics (TOG)}, vol.~25, no.~3,
  pp. 624--630, 2006.

\bibitem{Nishiyama2011}
M.~Nishiyama, T.~Okabe, I.~Sato, and Y.~Sato, ``Aesthetic quality
  classification of photographs based on color harmony,'' in \emph{Proceedings
  of the 2011 IEEE Conference on Computer Vision and Pattern Recognition}, ser.
  CVPR '11, 2011.

\bibitem{sauvaget2010segmented}
C.~Sauvaget, S.~Manuel, J.-N. Vittaut, J.~Suarez, and V.~Boyer, ``Segmented
  images colorization using harmony,'' in \emph{Signal-Image Technology and
  Internet-Based Systems (SITIS), 2010 Sixth International Conference
  on}.\hskip 1em plus 0.5em minus 0.4em\relax IEEE, 2010, pp. 153--160.

\bibitem{o2014collaborative}
P.~O'Donovan, A.~Agarwala, and A.~Hertzmann, ``Collaborative filtering of color
  aesthetics,'' in \emph{Proceedings of the Workshop on Computational
  Aesthetics}.\hskip 1em plus 0.5em minus 0.4em\relax ACM, 2014, pp. 33--40.

\bibitem{reinhard2001color}
E.~Reinhard, M.~Ashikhmin, B.~Gooch, and P.~Shirley, ``Color transfer between
  images,'' \emph{IEEE Computer graphics and applications}, vol.~21, no.~5, pp.
  34--41, 2001.

\bibitem{bonneel2013example}
N.~Bonneel, K.~Sunkavalli, S.~Paris, and H.~Pfister, ``Example-based video
  color grading.'' \emph{ACM Trans. Graph.}, vol.~32, no.~4, p.~39, 2013.

\bibitem{Neumann:2005}
L.~Neumann and A.~Neumann, ``Color style transfer techniques using hue,
  lightness and saturation histogram matching,'' ser. Computational
  Aesthetics'05, 2005.

\bibitem{CGF:CGF12409}
Y.~Liu, M.~Cohen, M.~Uyttendaele, and S.~Rusinkiewicz, ``Autostyle: Automatic
  style transfer from image collections to users' images,'' \emph{Computer
  Graphics Forum}, 2014.

\bibitem{ma2011manifold}
\BIBentryALTinterwordspacing
Y.~Ma and Y.~Fu, \emph{Manifold Learning Theory and Applications}.\hskip 1em
  plus 0.5em minus 0.4em\relax CRC Press, 2011. [Online]. Available:
  \url{https://books.google.com.vn/books?id=6pr1txA0\_yMC}
\BIBentrySTDinterwordspacing

\bibitem{chang2015palette}
H.~Chang, O.~Fried, Y.~Liu, S.~DiVerdi, and A.~Finkelstein, ``Palette-based
  photo recoloring,'' \emph{ACM Transactions on Graphics (TOG)}, vol.~34,
  no.~4, p. 139, 2015.

\bibitem{chia2011semantic}
A.~Y.-S. Chia, S.~Zhuo, R.~K. Gupta, Y.-W. Tai, S.-Y. Cho, P.~Tan, and S.~Lin,
  ``Semantic colorization with internet images,'' \emph{ACM Transactions on
  Graphics (TOG)}, vol.~30, no.~6, p. 156, 2011.

\bibitem{nguyen2015data}
C.~H. Nguyen, T.~Ritschel, and H.-P. Seidel, ``Data-driven color manifolds,''
  \emph{ACM Transactions on Graphics (TOG)}, vol.~34, no.~2, p.~20, 2015.

\bibitem{adobecolor2015}
``Adobe color cc,'' \url{https://color.adobe.com}.

\bibitem{coolorus2015}
``Coolorus,'' \url{http://www.coolorus.com}.

\bibitem{itten1970elements}
J.~Itten, \emph{The elements of color}.\hskip 1em plus 0.5em minus 0.4em\relax
  John Wiley \& Sons, 1970, vol.~4.

\bibitem{matsuda1995color}
Y.~Matsuda, ``Color design,'' \emph{Asakura Shoten}, vol.~2, no.~4, 1995.

\bibitem{tokumaru2002color}
M.~Tokumaru, N.~Muranaka, and S.~Imanishi, ``Color design support system
  considering color harmony,'' in \emph{Fuzzy Systems, 2002. FUZZ-IEEE'02.
  Proceedings of the 2002 IEEE International Conference on}, vol.~1.\hskip 1em
  plus 0.5em minus 0.4em\relax IEEE, 2002, pp. 378--383.

\bibitem{corelpainter2015}
``Corel painters,''
  \url{http://www.painterartist.com/us/product/paint-program/}.

\bibitem{mypaint2015}
``Mypaint,'' \url{http://mypaint.intilinux.com}.

\bibitem{meier2004interactive}
B.~J. Meier, A.~M. Spalter, and D.~B. Karelitz, ``Interactive color palette
  tools,'' \emph{Computer Graphics and Applications, IEEE}, vol.~24, no.~3, pp.
  64--72, 2004.

\bibitem{wijffelaars2008generating}
M.~Wijffelaars, R.~Vliegen, J.~J. Van~Wijk, and E.-J. Van Der~Linden,
  ``Generating color palettes using intuitive parameters,'' in \emph{Computer
  Graphics Forum}, vol.~27, no.~3.\hskip 1em plus 0.5em minus 0.4em\relax Wiley
  Online Library, 2008, pp. 743--750.

\bibitem{heer2012color}
J.~Heer and M.~Stone, ``Color naming models for color selection, image editing
  and palette design,'' in \emph{Proceedings of the SIGCHI Conference on Human
  Factors in Computing Systems}.\hskip 1em plus 0.5em minus 0.4em\relax ACM,
  2012, pp. 1007--1016.

\bibitem{shapira2009image}
L.~Shapira, A.~Shamir, and D.~Cohen-Or, ``Image appearance exploration by
  model-based navigation,'' in \emph{Computer Graphics Forum}, vol.~28,
  no.~2.\hskip 1em plus 0.5em minus 0.4em\relax Wiley Online Library, 2009, pp.
  629--638.

\bibitem{marks1997design}
J.~Marks, B.~Andalman, P.~A. Beardsley, W.~Freeman, S.~Gibson, J.~Hodgins,
  T.~Kang, B.~Mirtich, H.~Pfister, W.~Ruml \emph{et~al.}, ``Design galleries: A
  general approach to setting parameters for computer graphics and animation,''
  in \emph{Proceedings of the 24th annual conference on Computer graphics and
  interactive techniques}.\hskip 1em plus 0.5em minus 0.4em\relax ACM
  Press/Addison-Wesley Publishing Co., 1997, pp. 389--400.

\bibitem{quadrianto2009kernelized}
N.~Quadrianto, L.~Song, and A.~J. Smola, ``Kernelized sorting,'' in
  \emph{Advances in neural information processing systems}, 2009, pp.
  1289--1296.

\bibitem{fried2015isomatch}
O.~Fried, S.~DiVerdi, M.~Halber, E.~Sizikova, and A.~Finkelstein, ``Isomatch:
  Creating informative grid layouts,'' in \emph{Computer Graphics Forum},
  vol.~34, no.~2.\hskip 1em plus 0.5em minus 0.4em\relax Wiley Online Library,
  2015, pp. 155--166.

\bibitem{thomas2001introduction}
T.~H. Cormen, C.~E. Leiserson, R.~L. Rivest, and C.~Stein, \emph{Introduction
  to algorithms}.\hskip 1em plus 0.5em minus 0.4em\relax MIT press Cambridge,
  2001, vol.~6.

\bibitem{kuhn1955hungarian}
H.~W. Kuhn, ``The hungarian method for the assignment problem,'' \emph{Naval
  research logistics quarterly}, vol.~2, no. 1-2, pp. 83--97, 1955.

\bibitem{dubuisson1994modified}
M.-P. Dubuisson and A.~K. Jain, ``A modified {H}ausdorff distance for object
  matching,'' in \emph{Pattern Recognition, 1994. Vol. 1-Conference A: Computer
  Vision and Image Processing., Proceedings of the 12th IAPR International
  Conference on}, vol.~1.\hskip 1em plus 0.5em minus 0.4em\relax IEEE, 1994,
  pp. 566--568.

\bibitem{Scholkopf:1999}
B.~Sch\"{o}lkopf, A.~J. Smola, and K.-R. M\"{u}ller, ``Advances in kernel
  methods,'' B.~Sch\"{o}lkopf, C.~J.~C. Burges, and A.~J. Smola, Eds.\hskip 1em
  plus 0.5em minus 0.4em\relax Cambridge, MA, USA: MIT Press, 1999, ch. Kernel
  Principal Component Analysis, pp. 327--352.

\bibitem{grauman2005pyramid}
K.~Grauman and T.~Darrell, ``The pyramid match kernel: Discriminative
  classification with sets of image features,'' in \emph{Computer Vision, 2005.
  ICCV 2005. Tenth IEEE International Conference on}, vol.~2.\hskip 1em plus
  0.5em minus 0.4em\relax IEEE, 2005, pp. 1458--1465.

\bibitem{hinton2006reducing}
G.~E. Hinton and R.~R. Salakhutdinov, ``Reducing the dimensionality of data
  with neural networks,'' \emph{Science}, 2006.

\bibitem{blei2003latent}
D.~M. Blei, A.~Y. Ng, and M.~I. Jordan, ``Latent dirichlet allocation,''
  \emph{Journal of machine Learning research}, 2003.

\bibitem{lawrence2004gaussian}
N.~D. Lawrence, ``Gaussian process latent variable models for visualisation of
  high dimensional data,'' \emph{Advances in neural information processing
  systems}, vol.~16, pp. 329--336, 2004.

\bibitem{kruskal1964multidimensional}
J.~B. Kruskal, ``Multidimensional scaling by optimizing goodness of fit to a
  nonmetric hypothesis,'' \emph{Psychometrika}, vol.~29, no.~1, pp. 1--27,
  1964.

\bibitem{vert2004primer}
J.-P. Vert, K.~Tsuda, and B.~Sch{\"o}lkopf, ``A primer on kernel methods,''
  \emph{Kernel Methods in Computational Biology}, pp. 35--70, 2004.

\bibitem{levin2004colorization}
A.~Levin, D.~Lischinski, and Y.~Weiss, ``Colorization using optimization,'' in
  \emph{ACM Transactions on Graphics (TOG)}, vol.~23, no.~3.\hskip 1em plus
  0.5em minus 0.4em\relax ACM, 2004, pp. 689--694.

\end{thebibliography}
