# Superpixel-based Color Transfer

Rémi Giraud, Vinh-Thong Ta, Nicolas Papadakis

► To cite this version:

Rémi Giraud, Vinh-Thong Ta, Nicolas Papadakis. Superpixel-based Color Transfer. IEEE International Conference on Image Processing (ICIP'17), Sep 2017, Beijing, China. pp.700-704. hal-01519644

HAL Id: hal-01519644

https://hal.science/hal-01519644

Submitted on 13 Mar 2019

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

Public Domain
SUPERPIXEL-BASED COLOR TRANSFER

Rémi Giraud¹,²

Vinh-Thong Ta¹,³

Nicolas Papadakis²

¹Univ. Bordeaux, LaBRI, CNRS, UMR 5800, F-33400 Talence, France.

²Univ. Bordeaux, IMB, CNRS, UMR 5251, F-33400 Talence, France.

³Bordeaux INP, LaBRI, UMR 5800, F-33405 Talence, France.

ABSTRACT

In this work, we propose a fast superpixel-based color transfer method (SCT) between two images. Superpixels enable to decrease the image dimension and to extract a reduced set of color candidates. We propose to use a fast approximate nearest neighbor matching algorithm in which we enforce the match diversity by limiting the selection of the same superpixels. A fusion framework is designed to transfer the matched colors, and we demonstrate the improvement obtained over exact matching results. Finally, we show that SCT is visually competitive compared to state-of-the-art methods.

**Index Terms—** Color transfer, Superpixels

1. INTRODUCTION

Color transfer consists in modifying the color distribution of a target image using one or several reference source images. The produced result must be consistent with the target image structure, and computational time is an important issue to process large images or video sequences.

**Color transfer.** Initiated by [1], many approaches have been proposed to transfer color statistics in different color spaces [2, 3, 4, 5]. Optimal transportation tools have also been intensively studied to match and transfer the whole color distribution [6, 7, 8]. Nevertheless, as underlined in [9], since color distributions between images may be very different, the exact transfer of the color palette may produce visual outliers. Relaxed optimal transport models, that do no exactly match color distributions, have then been proposed to tackle this issue [10], but they rely on time consuming algorithms. Moreover, when the process is only performed in the color space, incoherent colors may be transfered to neighboring pixels. Artifacts such as JPEG compression blocks, enhanced noise or saturation then become visible [11], unless considering object semantic information [8]. In [12], an EM approach is used to estimate a Gaussian mixture model in color and

<figure><img src="image_1.png" /><figcaption>Fig. 1: Example of color transfer with the proposed SCT method.</figcaption></figure>

pixel space, since the pixel location helps to preserve the image geometry. However, a major limitation is the matching of clusters using a greedy approach based on nearest-neighbor criterion, with no control on the selected source colors. In [13], a relaxed optimal transport model is applied to color transfer using superpixel lower-level representation.

**Superpixels.** These decomposition methods reduce the image dimension by grouping pixels into homogeneous areas [14, 15, 16]. They have become widely used to reduce the computational burden of various image processing tasks such as multi-class object segmentation [17], object localization [18] or contour detection [19]. Generally, the irregular geometry of the decompositions makes difficult their use into standard processes. However, for color transfer application, superpixels become particularly interesting since they enable to describe consistent color areas, and matches can be found regardless of the superpixel neighboring structure.

Superpixel-based approaches such as [13, 20] allow a better adaptation to color histograms and image content, but still require important computational cost. Except for tracking applications [21], fast superpixel matching methods have been little investigated. For instance, in [22], the PatchMatch (PM) algorithm [23] that finds approximate nearest neighbor (ANN) patches between images is adapted to graphs, and [24, 25] consider it in the superpixel context.

**Contributions.** In this work, we propose a fast superpixel-based color transfer method (SCT). An example result of SCT is given in Figure 1. To select the color candidates, we use the fast and robust PM algorithm, that we adapt to handle superpixels [25]. Contrary to [12], we propose a method to constrain the ANN search process to limit the selection of the same superpixels in the source image. Throughout the paper, we demonstrate the significant improvement obtained with this constraint, that enables to enforce the match diversity and to capture a larger color palette, similarly to [13]. The

This work has been carried out with financial support of the French State, managed by the French National Research Agency (ANR) in the frame of the GOTMI project (ANR-16-CE33-0010-01) and the Investments for the future Program IdEx Bordeaux (ANR-10-IDEX-03-02) with the Cluster of excellence CPU.
<figure><img src="image_2.png" /><figcaption>Fig. 2: Illustration of propagation step. The superpixel $A_i$ (red) is currently matched to $B_{(i)}$. Its top-left adjacent neighbors $A_j$ (gray) are considered to provide new candidates. A neighbor $A_j$ is matched to $B_{(j)}$, which leads to the candidate $B_k$, the neighbor of $B_{(j)}$ with the most similar relative position to the one between $A_i$ and $A_j$.</figcaption></figure>

selected colors are then transfered by a color fusion approach inspired from the non-local means framework [26]. Finally, we show that SCT produces accurate color transfer in low computational time thanks to the superpixel representation.

# 2. SUPERPIXEL-BASED COLOR TRANSFER METHOD

## 2.1. ANN Superpixel Matching

**PatchMatch algorithm.** The PatchMatch (PM) method [23] computes correspondences between pixel patches of two images A and B. It exploits the assumption that if patches are matched between A and B, then their respective adjacent neighbors should also match well. Such propagation, associated with a random selection of patch candidates, enables the algorithm to have a fast convergence towards good ANN.

PM is based on three steps. The first one randomly assigns to each patch of A, a corresponding patch in B. An iterative refinement process is then performed following a scan order (top left to bottom right) to refine the correspondences with the propagation and random search steps. For a patch $A_i \in A$, the aim is to find the match $B_{(i)} \in B$ that minimizes a distance $D(A_i, B_{(i)})$, for instance the sum of squares differences of color intensities. During propagation, for each patch in A, the two recently processed adjacent patches are considered. Their matches in B are shifted to respect the relative positions in A, and the new candidates are tested for improvement. Finally, the random search selects candidates around the current ANN in B to escape from local minima.

**Adaptation to superpixel matching.** Several issues appear when considering the PM algorithm to the matching of superpixels [25]. Since superpixels decompose the image into irregular areas, there is no fixed adjacency relation between the elements. First, a scan order must be defined to process the superpixels. Then, during propagation, the decomposition geometry being also different in the image B, the shift of the neighbor cannot be directly performed. A solution is to select the candidate with the most similar relative orientation computed with the superpixel barycenters. Figure 2 illustrates the selection of a candidate during propagation. Such adaptation of PM provides a fast superpixel ANN matching algorithm that produces an accurate selection of colors to transfer.

<figure><img src="image_3.png" /><figcaption>Fig. 3: Illustration of matching without ($\epsilon = \infty$) and with ($\epsilon = 1$) constraint on the number of source superpixel selection. Without constraint, all target superpixels match a red one in the source image.</figcaption></figure>

## 2.2. Constraint on Match Diversity

In practice, the ANN search may converge towards exact matching, almost providing the nearest neighbors. The aim of color transfer is to globally capture the source color palette. If the source image contains one or several elements that match well the color set of the target image A, the ANN search may lead to the same match in B. The color transfer would thus provide a result very close to A. Figure 3 illustrates this issue. Since the source image also contains red colors, all superpixels of the target image find a close red match in the source space, leading to no color transfer.

To enforce the match diversity and capture a larger color palette of the source image, we propose to constrain the ANN search and to restrict the number of associations to the same element. To do so, we set a parameter $\epsilon$ that defines the maximum number of selection of the same superpixel. Such constraint requires the number of source elements $|B|$ to be such that $|A| \le \epsilon|B|$. In Figure 3, with $\epsilon = 1$, the target superpixels now capture the global palette of the source image. First, we make sure that the initialization step respects this constraint when randomly assigning the correspondences. Then, during the following iterative process, a superpixel $A_i$ can be assigned to a superpixel $B_k$, only if less than $\epsilon$ superpixels in A are already assigned to $B_k$. If $B_k$ is already matched by $\epsilon$ elements in A, one superpixel $A_j$ assigned to $B_k$ must be sent to another superpixel in B to allow $A_i$ to match $B_k$. We propose to compute the cost of sending a superpixel $A_j$, currently matched with $B_k$, towards $B_{(i)}$, the current correspondence of $A_i$, thus making a switch between the matches, and ensuring the respect of the constraint set by $\epsilon$. For all superpixels $A_j$ matched to $B_{(j)} = B_k$, the switching cost is considered as follows:

$$C(A_i, A_j) = (D(A_i, B_{(j)}) - D(A_i, B_{(i)})) + (D(A_j, B_{(i)}) - D(A_j, B_{(j)})). \quad (1)$$

If a superpixel $A_j$ reduces the global matching distance, i.e., if the cost $C < 0$, we proceed to the following assignments: $\argmin_{A_j}(C(A_i, A_j)) \rightarrow B_{(i)}$ and $A_i \rightarrow B_{(j)} = B_k$.

**Comparison to optimal assignment.** The proposed ANN algorithm with $\epsilon = 1$ approximates the optimal assignment problem, addressed with the Hungarian or Munkres algorithms [27]. Given two sets of elements $\{A_i\}_{i \in \{1, ..., |A|\}}$ and $\{B_j\}_{j \in \{1, ..., |B|\}}$ with $|A| \le |B|$, the aim is to find to each $A_i$, an assignment $B_{(i)}$ that can only be selected once, and to minimize the global distance between the matched elements.
<figure><img src="image_4.png" /><figcaption>Fig. 4: Comparison of optimal assignment using Munkres algorithm [27] and our constrained superpixel ANN matching ($\epsilon = 1$). Target image reconstruction from the matched superpixels average colors ($K \approx 2000$) and performances for several superpixel scales.</figcaption></figure>

In Figure 4, we consider two close images of 1920×800 pixels [28]. We show the target image reconstruction $\tilde{A}$ from the matched superpixels average colors and compare total matching distance and computational time between our approach, optimal resolution [27], and to random superpixel assignments, i.e., the initialization step of our algorithm. Our fast superpixel ANN method provides close results to the optimal resolution while being order of magnitude faster.

## 2.3. Color Fusion Framework

Our matching framework provides an ANN in $B$ to each superpixel of $A$. The aim is then to transfer the color of the matches to compute the color transfer image $A_t$ while preserving the structure of the target $A$. Since the matched superpixels are very likely to have different shapes, there are no direct pixel associations between elements, and source colors cannot be directly transfered to $A$ at the pixel scale. The average colors of superpixels in $B$ can be transfered to the ones in $A$ but it would give a piece-wise color transfer result.

We propose to consider the average colors from the matched superpixels in a non-local means fusion framework [26]. Hence, all matched colors can contribute to the color computation of each pixel in $A_t$. Such approach enables to increase the number of color candidates and leads to new potential ones that adapt well to the target image content. A superpixel $A_i$ is described by the set of positions $X_i$ and colors $C_i$ of the contained pixels $p$, such that $A_i = [X_i, C_i] = [(x_i/N_x, y_i/N_y), (r_i, g_i, b_i)/255]$, with $N_x \times N_y$ the size of image $A$. To compute the new color $A_t(p)$ of a pixel $p$, the weighted fusion of the matched colors is performed based on color and spatial similarity:

$$A_t(p) = \frac{\sum_j \omega(p, A_j) \tilde{C}_{B(j)}}{\sum_j \omega(p, A_j)}, \quad (2)$$

<figure><img src="image_5.png" /><figcaption>Fig. 5: Results of each SCT step. See text for more details.</figcaption></figure>

with $\tilde{C}_{B(j)}$, the average color of the match of $A_j$ in $B$, and $\omega(p, A_j)$ the weight that depends on the distance between the considered pixel $p \in A_i$ and the superpixel $A_j \in A$. This weight is computed similarly to a Mahalanobis distance:

$$\omega(p, A_j) = \exp\left(-\left((p - \bar{A}_j)^T Q_i^{-1} (p - \bar{A}_j) - \sigma(p)\right)\right), \quad (3)$$

where $\sigma(p)$ sets the exponential dynamic and is set such that $\sigma(p) = \min_j \left((p - \bar{A}_j)^T Q_i^{-1} (p - \bar{A}_j)\right)$, and $Q_i$ includes spatial and colorimetric covariances of the pixels in $A_i$:

$$Q_i = Q(A_i) = \begin{pmatrix} \delta_s^2 \mathrm{Cov}(X_i) & 0 \\ 0 & \delta_c^2 \mathrm{Cov}(C_i) \end{pmatrix}. \quad (4)$$

The SCT steps are illustrated in Figure 5. We show the decomposition of images into superpixels with average colors, the matched source colors, and results of color fusion and post-processing with a color regrain [29].

# 3. COLOR TRANSFER RESULTS

## 3.1. Parameter Settings

SCT is implemented with MATLAB using C-MEX code. Superpixel decompositions are computed using [16] such that each superpixel approximately contains 500 pixels. The superpixel matching is performed on normalized cumulative color histogram features and the number of ANN search iterations is set to 20. The covariance parameters in Eq. (4) are set such that $\delta_s=100\delta_c$ and $\delta_c=0.1$ in order to favor spatial consistency. Finally, unless mentioned, $\epsilon$ is set to 3 and the results are slightly refined using a color regrain [29].

Our method produces results in very low computational time due to the use of superpixels, i.e., less than 1s for images of 480×360 pixels. Decompositions are computed with [16] in less than 0.4s, matching is performed in approximately 0.1s and color fusion takes 0.25s to provide the color transfer.
<figure><img src="image_6.png" /><figcaption>**Fig. 6:** Examples of color transfer results are shown for different $\epsilon$ values and compared to the results obtained with no constraint ($\epsilon = \infty$). The maps (bottom row) indicate the number of selection of the source superpixels (black is zero and white is the highest number of selection).</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>**Fig. 7:** Visual comparison to [6], [4] and [5]. SCT provides more visually satisfying or equivalent results to the compared methods.</figcaption></figure>

## 3.2. Influence of Match Diversity

Additionally to Figure 3, we illustrate in Figure 6 the influence of the $\epsilon$ parameter that limits the source superpixel selection. It appears that even fast ANN search may lead to the same best match, as shown with the maps corresponding to the selection of source superpixels. For instance, most target superpixels of the white flower match the only white superpixel in the source image, leading to almost no color transfer. With the proposed method, we select accurate matches while capturing the global color palette of the source image.

## 3.3. Comparison with State-of-the-Art Methods

In this section, we compare the results of SCT to various methods based on optimal transport [6], histogram transfer with a variational model [4] and 3D color gamut mapping [5]. Figure 7 illustrates color transfer examples for all methods.

SCT produces more visually satisfying results than the ones of the compared methods. The colors are relevantly transfered to the target image with respect to the initial grain and exposure. For instance, on the first image (top row), [6], [4] and [5] produce color transfers that strongly modify the il-

lumination of the target image. All compared methods except SCT fail at transferring the blue color from the desert sky into the sea (middle row), and the orange color of the stones to the grass of the moutain (bottom row). Contrary to the compared methods, we consider a selection of the source colors and our fusion model enables to adapt to the target image, preserving its structure and initial exposure. Finally, while SCT results are computed in less than 1s, while other models such as [4] may require prohibitive computational times, up to 120s.

## 4. CONCLUSION

In this work, we propose a novel superpixel-based method for color transfer. Our algorithm is based on a fast ANN search and fusion of source colors in a non-local means framework. We introduce a method to constraint the neighbors diversity in the matching process, to get a large color palette of source superpixels. The colors are globally transfered to the target image with respect to the initial grain and exposure, producing visually consistent results. Finally, the use of superpixels within our framework enables to produce color transfer in very limited computational time. Future works will focus on the adaptation to video color transfer using supervoxels.
## 5. REFERENCES

[1] E. Reinhard, M. Adhikhmin, B. Gooch, and P. Shirley, "Color transfer between images," *IEEE CG&A*, vol. 21, no. 5, pp. 34–41, 2001.

[2] X. Xiao and L. Ma, "Color transfer in correlated color space," in *ACM VRCIA*, 2006, pp. 305–309.

[3] F. Pitié and A. Kokaram, "The linear Monge-Kantorovitch linear colour mapping for example-based colour transfer," in *CVMP*, 2007, pp. 1–9.

[4] N. Papadakis, E. Provenzi, and V. Caselles, "A variational model for histogram transfer of color images," *IEEE TIP*, vol. 20, no. 6, pp. 1682–1695, 2011.

[5] R. Nguyen, S. J. Kim, and M. S. Brown, "Illuminant aware gamut-based color transfer," in *Comput. Graph. Forum*, 2014, vol. 33, pp. 319–328.

[6] F. Pitié, A. C. Kokaram, and R. Dahyot, "Automated colour grading using colour distribution transfer," *CVIU*, vol. 107, no. 12, pp. 123–137, 2007.

[7] J. Rabin, J. Delon, and Y. Gousseau, "Removing artifacts from color and contrast modifications," *IEEE TIP*, vol. 20, no. 11, pp. 3073–3085, 2011.

[8] O. Frigo, N. Sabater, V. Demoulin, and P. Hellier, "Optimal transportation for example-guided color transfer," in *ACCV*, 2014, vol. 9005, pp. 655–670.

[9] T. Pouli and E. Reinhard, "Progressive color transfer for images of arbitrary dynamic range," *Comput. Graph.*, vol. 35, no. 1, pp. 67–80, 2011.

[10] S. Ferradans, N. Papadakis, G. Peyré, and J-F. Aujol, "Regularized discrete optimal transport," *SIIMS*, vol. 7, no. 3, pp. 1853–1882, 2014.

[11] Z. Su, K. Zeng, L. Liu, B. Li, and X. Luo, "Corruptive artifacts suppression for example-based color transfer," *IEEE Trans. Multimedia*, vol. 16, no. 4, pp. 988–999, 2014.

[12] Y.-W. Tai, J. Jia, and C.-K. Tang, "Local color transfer via probabilistic segmentation by expectation-maximization," in *IEEE CVPR*, 2005, pp. 747–754.

[13] J. Rabin and N. Papadakis, "Non-convex relaxation of optimal transport for color transfer," in *NIPS 2014 Workshop on Optimal Transport and Machine Learning*, 2014.

[14] R. Achanta, A. Shaji, K. Smith, A. Lucchi, P. Fua, and S. Süsstrunk, "SLIC superpixels compared to state-of-the-art superpixel methods," *IEEE TPAMI*, vol. 34, no. 11, pp. 2274–2282, 2012.

[15] M. Van den Bergh, X. Boix, G. Roig, B. de Capitani, and L. Van Gool, "SEEDS: Superpixels extracted via energy-driven sampling," in *ECCV*, 2012, pp. 13–26.

[16] R. Giraud, V.-T. Ta, and N. Papadakis, "SCALP: Superpixels with contour adherence using linear path," in *ICPR*, 2016, pp. 2374–2379.

[17] J. Tighe and S. Lazebnik, "SuperParsing: Scalable non-parametric image parsing with superpixels," in *ECCV*, 2010, pp. 352–365.

[18] B. Fulkerson, A. Vedaldi, and S. Soatto, "Class segmentation and object localization with superpixel neighborhoods," in *IEEE ICCV*, 2009, pp. 670–677.

[19] P. Arbelaez, M. Maire, C. Fowlkes, and J. Malik, "Contour detection and hierarchical image segmentation," *IEEE TPAMI*, vol. 33, no. 5, pp. 898–916, 2011.

[20] J. Liu, W. Yang, X. Sun, and W. Zeng, "Photo stylistic brush: Robust style transfer via superpixel-based bipartite graph," *arXiv preprint arXiv:1606.03871*, 2016.

[21] S. Wang, H. Lu, F. Yang, and M. H. Yang, "Superpixel tracking," in *IEEE ICCV*, 2011, pp. 1323–1330.

[22] S. Gould and Y. Zhang, "PatchMatchGraph: Building a graph of dense patch correspondences for label transfer," in *ECCV*, 2012, pp. 439–452.

[23] C. Barnes, E. Shechtman, A. Finkelstein, and D. B. Goldman, "PatchMatch: A randomized correspondence algorithm for structural image editing," *ACM TOG*, vol. 28, no. 3, 2009.

[24] S. Gould, J. Zhao, X. He, and Y. Zhang, "Superpixel graph label transfer with learned distance metric," in *ECCV*, 2014, pp. 632–647.

[25] R. Giraud, V.-T. Ta, A. Bugeau, P. Coupé, and N. Papadakis, "SuperPatchMatch: An algorithm for robust correspondences using superpixel patches," *IEEE TIP*, 2017.

[26] A. Buades, B. Coll, and J.-M. Morel, "A non-local algorithm for image denoising," in *IEEE CVPR*, 2005, vol. 2, pp. 60–65.

[27] J. Munkres, "Algorithms for the assignment and transportation problems," *SIAM*, vol. 5, no. 1, pp. 32–38, 1957.

[28] S. Korman and S. Avidan, "Coherency sensitive hashing," in *IEEE ICCV*, 2011, pp. 1607–1614.

[29] F. Pitié, A. Kokaram, and R. Dahyot, "Towards automated colour grading," in *CVMP*, 2005.