{'fraction_non_alphanumeric': 0.0330261905954229, 'fraction_numerical': 0.014297160598928339, 'mean_word_length': 4.758217993079585, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Guided Colorization Using Mono-Color Image Pairs

Compared to color images captured by conventional RGB cameras, monochrome images usually have better signal-to-noise ratio (SNR) and richer textures due to its higher quantum efficiency. It is thus natural to apply a mono-color dual-camera system to restore color images with higher visual quality. In this paper, we propose a mono-color image enhancement algorithm that colorizes the monochrome image with the color one. Based on the assumption that adjacent structures with similar luminance values are likely to have similar colors, we first perform dense scribbling to assign colors to the monochrome pixels through block matching. Two types of outliers, including occlusion and color ambiguity, are detected and removed from the initial scribbles. We also introduce a sampling strategy to accelerate the scribbling process. Then, the dense scribbles are propagated to the entire image. To alleviate incorrect color propagation in the regions that have no color hints at all, we generate extra color seeds based on the existed scribbles to guide the propagation process. Experimental results show that, our algorithm can efficiently restore color images with higher SNR and richer details from the mono-color image pairs, and achieves good performance in solving the color bleeding problem.


I. INTRODUCTION
M ODERN digital cameras use a specially arranged color filter array (CFA) to capture color images on a square grid of sensors. Due to the filtering structure, each sensor can only use part of the incoming light to record color information, resulting in low signal-to-noise ratio (SNR) especially in lowlight conditions. Spatial denoising techniques such as image filtering [1], [2], sparse representation [3], [4], and low-rank approximation [5], [6] can be applied to address this problem. However, they tend to over-smooth the details during noise removal. Recently, studies on joint filtering [7], [8] and image fusion [9]- [11] indicate that, a degraded image can be better restored under the guidance of its related images of higher quality. The aforementioned adverse effect can be effectively alleviated.
Compared to RGB cameras, monochrome cameras do not have CFA structures. Hence, they cannot record color information, but can achieve higher quantum efficiency. In other words, images captured by the monochrome cameras usually contain more details and have higher SNR. It's natural that we can take advantage of a pair of related monochrome and color image to generate a color image with lower noise intensity and richer textures.
A dual-camera system can be applied to capture the monocolor image pairs. Since two cameras have different viewing angles, the image pairs have disparity. Conventional image fusion algorithms require images to be well-aligned. Therefore, previous approaches [12], [13] basically follow the scheme that they register the image pairs using stereo matching techniques at first, and then conduct the fusion process. However, when the contents of the image pair are not consistent in terms of noise and details, it's hard to yield an accurate disparity estimate, leading to several artifacts such as color bleeding.
Generally, there are two options to fuse a mono-color image pair. One option is to denoise the color image under the guidance of the monochrome image, while the other one is to colorize the monochrome image with the color one. Due to the inevitable edge smoothing of image denoising, the colorization option can obtain results with richer details. Current methods on image colorization can be categorized into scribble-based [14]- [18] and example-based [19]- [23] ones. Scribble-based methods require users to manually add color hints to the monochrome image, then propagate those hints to the entire image. Example-based methods transfer colors from guidance to the target image, often achieved by feature matching.
In this work, we propose a novel colorization algorithm using mono-color image pairs. Considering the strong correlation between the two images, color scribbles can be created automatically through dense matching. Since our major purpose is colorization, it's actually unnecessary to align the image pair. Motivated by the commonly used assumption that adjacent pixels with similar luminance values are likely to have similar colors [14], we can further assume that adjacent similar structures can have similar color distributions. Hence, to colorize a pixel, we can use patches that contain this pixel and perform block matching to find their similar patches around their adjacent locations in the guidance color image. Based on the aforementioned assumption, we can directly assign the color of the matching result to the target pixel. Compared to conventional stereo matching techniques, block matching here doesn't have to check the left-right consistency, and has higher robustness when the guidance image is degraded.
Two types of outliers may occur during the scribbling process. One is the color-ambiguous pixels. Since luminance and chrominance are not always in one-to-one correspondence, even around adjacent areas, two matched pixels can be similar in luminance but totally different in color, which we define as color ambiguity. Hence, it's essential to assign each pixel multiple color candidates using overlapped patches to judge whether there is color ambiguity. The other one is the occluded pixels caused by the viewing angle difference between two images. In this work, we introduce a new concept of valid match arXiv:2108.07471v1 [cs.CV] 17 Aug 2021 2 for our dense scribbling process. That is, occlusion is directly detected based on the analysis of the color candidates, instead of using conventional methods such as left-right consistency check and ordering constraint. After removing the outliers, the rest color assignments form the initial dense scribbles.
Since we assign multiple color candidates to each pixel, an important issue is to determine how many color candidates are sufficient to produce accurate color estimates. To address this problem, we introduce a patch sampling strategy that can strike a good balance between accuracy and efficiency.
Finally, we propagate the initial scribbles to the entire image. But before propagation, we have to ensure that each region has color hints to avoid color bleeding. For the regions that have no color hints at all after dense scribbling, we generate extra color seeds based on their neighboring information.
In summary, we introduce a guided colorization algorithm to restore color images of better visual quality from the mono-color image pairs without image alignment. The main contributions of this work are as follows: • We introduce a patch-wise dense scribbling strategy with probabilistic concept based patch sampling to efficiently complete the robust color estimation. • We conduct analysis on the reliability of color estimation and discuss the two outliers of the scribbling process including the occluded and the color-ambiguous pixels. • We generate extra color seeds in the sparsely scribbled regions to alleviate color bleeding during color propagation. • Our algorithm outperforms the state-of-the-art colorization and guided restoration algorithms to a large margin on synthetic and realistic mono-color image pairs.

II. RELATED WORK
In this section, we briefly review the current research on image colorization and guided image enhancement.

A. Image Colorization
Generally, image colorization methods can be categorized into scribble-based and example-based ones.
Scribble-based methods [14]- [18] require users to manually add the color hints. By assuming that adjacent pixels with similar luminance values tend to have similar colors, the sparse color hints can be propagated to the entire image. This type of method was first popularized by [14], where colorization is modeled as an optimization problem constructed by a system of linear equations. To reduce color bleeding, [15] uses edge detection to prevent color hints from crossing the object boundaries, while [16] takes geodesic distance into consideration during color propagation. Based on the lowrank property of natural images, [17] performs colorization by solving a matrix completion problem. In [18], Zhang et al. fuse color hints with semantic information through a deep neural network, which improves the colorization quality and also enables its real-time use.
Example-based methods [19]- [23] use a set of userprovided reference images to colorize the grayscale image automatically. The most common way to make the color transfer is to establish feature correspondence between the reference image and the target grayscale image. The features can be pixels [12], [19], [20], [22], super-pixels [21], or even semantic contents [23]. The only customization required is to choose an appropriate reference image. To further reduce manual efforts, [22] introduces a deep neural network that can select the best reference image from a dataset and accomplish colorizing at the same time. Recently, extensive studies on the deep learning theory inspire [24], [25] that colorization can be fully automated even without reference images based on the various image priors learned by neural networks.

B. Guided Image Enhancement
According to the reconstruction target, guided image enhancement can be categorized into fusion methods and restoration methods.
Restoration methods [7], [8], [13], [38]- [45] aim to reconstruct images of higher quality from their degraded observations. In [8], He et al. introduce the guided filter, which is the foundation of many current guided restoration methods. It leverages a local linear model to reconstruct the target image from the guidance, and can be treated as either an edge-preserving smoothing operator or a detail transfer operator. To alleviate halo artifacts and produce better edge reconstruction, [38] modifies the original cost function with an edge-aware weighting, while [39] performs the guided filtering in the gradient domain. In some specific application scenarios such as RGB image guided depth image super-resolution, textures are not supposed to be transferred. Hence, a new type of guided filtering, called as dynamic guided filtering, is introduced to solve the problem [40]- [43]. As opposed to the aforementioned static filtering process, dynamic one conducts filtering iteratively. In each iteration, the guidance image is updated to meet its structural consistency with the target image. Currently, deep learning is also applied to the guided restoration tasks. [44] trains an end-to-end neural network for fast guided filtering, while [45] constructs a spatially variant linear representation model with learnable coefficients.
However, most of the guided restoration algorithms require images to be well-aligned. To handle misaligned image pairs, [7] generates a set of translated guidances, and then performs a weighted average of the filtering results using these different guidance images. Similar to our dual-camera system settings, [13] aligns the mono-color pairs before filtering the noisy RGB image. The misaligned problems can be resolved to a certain extent, but there is still a lack of more in-depth analysis.

III. PROPOSED ALGORITHM
Our algorithm contains two stages: dense scribbling and color propagation. In the dense scribbling stage, we assign monochrome pixels multiple color candidates via block matching and compute their color values by weighted averaging over the candidates. Then, we detect and remove the outliers to form the initial dense scribbles. We also introduce a patch sampling strategy to accelerate the scribbling process. In the propagation stage, we generate color seeds around the regions that have no scribbles at all, and then propagate the color hints to the entire image. The framework of our algorithm is displayed in Fig. 1.

A. Dense Scribbling
Let M ∈ R H×W and C ∈ R H×W ×3 denote the monochrome and the color image captured by a dual-camera system. Their maximum disparity is D. Our goal is to assign colors to every pixel in M. Due to the strong correlation between the image pair, it's natural to assume that, two patches from M and C respectively that are similar in luminance are likely to have similar colors, especially within the range restricted by the maximum disparity and the epipolar constraint. Hence, M can be colorized automatically by searching similar patches in C.
To begin with, we convert C into the CIELAB color space. The lightness channel is denoted as C l , describing the luminance information. Two chrominance channels are denoted as C a and C b . As computations in C a and C b are identical, we refer to C a as the chrominance channel below for brevity.
We divide M into overlapped patches of size S × S. For a monochrome patch p ∈ R S×S , we search for its most similar color patch in C, within a window of size W h × W v . In this work, we set S = 16, the horizontal search range W h = D, and the vertical search range W v = 30. The difference between p and a color patch q ∈ R S×S×3 is measured by their Euclidean distance in luminance, which is computed as where q l is the lightness channel of q. Then, we select q with the smallest distance, and combine its chrominance channel q a with p to assign each monochrome pixel a color candidate. Since all the patches are overlapped, a pixel can be included in different patches, and can thus obtain multiple color candidates through block matching of different patches.
We stack all the color candidates into a 3D tensor U ∈ R H×W ×K , where K is the number of candidates of a pixel and K max = S 2 . Luminance values of the matched pixels are stacked in L ∈ R H×W ×K . A weighted average is then performed across these candidates to obtain the color estimates. The chrominance value of M is thus computed by where W ∈ R H×W ×K is the weight tensor. Based on the assumption that adjacent pixels with similar luminance values are similar in color, we determine the value of each element in W by computing the absolute luminance difference between the target monochrome pixel and the matched pixel, computed as where Z is the normalization matrix that ensures K k=1 W(i, j, k) = 1, and ε is set to a small value to prevent the denominator from being zero.
In addition, random noise in the guidance image can affect the accuracy of dense scribbling, and can also cause noise residue in the colorization results. A simple and fast predenoising on the guidance image can help to alleviate the aforementioned problems directly. In this work, we apply the random redundant DCT (RRDCT) denoising algorithm introduced in [46] for noise suppression, which runs almost in real time. Although our algorithm already has some robustness to random noise due to the patch-wise matching scheme, the pre-denoising step can help to further improve the colorization quality, especially when the noise level is relatively high. Color assignment via block matching still remains two problems to be solved. First, the algorithm can be expensive in both time and space if all the patches are used in block matching, which proves to be unnecessary in Section III-B. Second, patches from the occluded regions may not be able to find their similar matches, resulting in wrong color assignment. In addition, since luminance and chrominance are not always in one-to-one correspondence, color candidates of one pixel may differ from each other, which we describe as color ambiguity. Fig. 2 shows examples of two outliers respectively. Therefore, colors of those outliers should be removed and reestimated. Then, the remaining colors form the initial dense scribbles. Section III-B and III-C will focus on how to address the two problems respectively.

B. Patch Sampling
During block matching, we use patches of size S × S to allocate S 2 color candidates to each pixel. However, it can be time-consuming when the size of image is quite large. A proper sampling strategy is essential to accelerate the scribblegenerating process.
From the perspective of a pixel, patch sampling is equivalent to extracting N colors from the overall S 2 candidates, under a sampling rate of ρ = N/S 2 . If T of them already have similar luminance values to the target pixel, we can assert that it's enough to give an accurate color estimate and can terminate the matching process. To strike a good balance between efficiency and accuracy, the sampling-related values of N and T should be carefully selected, where N determines the sampling rate and T indicates whether the color candidates are sufficient to generate a correct color estimate. For clarity, the main notations and their corresponding meanings used in patch sampling are listed in Table I. Suppose that we extract N values from the S 2 color candidates of pixel p. We denote it as event A r if r of them have similar luminance values to p, measured by their absolute differences. A threshold is required to judge whether two pixels are similar or not. If their absolute luminance difference is lower than the threshold, we can assert that they are similar. In this work, we use the just-noticeable difference (JND) threshold introduced in [47], which is a perceptual threshold computed as where J L (p) is the intensity term and J T (p) is the texture term.
Denoting g as the total number of candidates that are similar to p judged by JND without patch sampling, its prior probability distribution P (g), 1 ≤ g ≤ S 2 , is depicted in Fig. 3 (a), which is a statistical result obtained by massive experiments on the Middlebury datasets [48], [49]. Since most of the image contents are flat, majority of the pixels are likely to obtain similar color candidates. Color information obtained by block matching is quite redundant, proving that using all the patches to generate an accurate color estimate is a thankless job.
We define that p achieves a valid match if r ≥ T . Valid matches do not require extra matching for color estimation. A good sampling strategy should guarantee a high probability of valid matches, otherwise the scribbles may become sparse, which is not conducive to accurate colorization. The probability of valid match is computed by 5 where and C n m denotes the combination function. The second aspect to judge a good sampling strategy is the confidence that a valid match generates a correct color estimate. Due to color ambiguity, the extracted candidates may be correct in luminance but wrong in color. We define event B to describe that the color scribble computed by the weighted average of the color candidates is correct, also judged by JND. The prior distribution of scribbling accuracy P (B|g) is shown in Fig. 3 (c), which is also a statistical result obtained via experiments on the Middlebury datasets. The result shows that color ambiguity occurs more often where color candidates are less consistent in luminance. For computation convenience, the prior distribution P (B|g) can be approximately fitted by a linear model. Thus, the confidence of valid match Φ confidence (N, T ) can be measured by the posteriori probability P (B|A T ), computed as Values of Φ valid match (N, T ) and Φ confidence (N, T ) are visualized in Fig. 3 (b) and (d). We apply these two criteria to determine the values of N and T . A good sampling process should achieve high probability of valid match to generate dense scribbles, and also have high confidence in valid match to compute colors correctly. According to Fig. 3, by setting N = 4 and T = 4, we can get Φ valid match (N, T ) = 0.7920 and Φ confidence (N, T ) = 0.9639, which means 1/64 of the patches are already sufficient to colorize 79.2% of the pixels with confidence 0.9639.
After determining the sampling rate, we extract patches by setting a constant stride. Patches can also be randomly selected through sampling techniques such as Poisson disk sampling [50], [51], which achieves similar colorization results.

C. Outliers Removal
The major reasons that cause wrong color estimation are occlusion and color ambiguity. To yield a colorization result of higher visual quality, it's essential to detect these outliers, remove their initial color estimates, and re-colorize them using their adjacent information.
Occluded pixels can be easily detected in the block matching stage, without conventional left-right consistency check. Using the sampling strategy mentioned above, pixels that fail to achieve valid matches can be recognized as occluded pixels. To check whether a pixel that completes valid match has ambiguous color candidates, we sort its color values in ascend order. If there exists an absolute difference between two adjacent values that is greater than the threshold τ , we can assert that the chrominance values of its color candidates are not consistent. In our work, leveraging a constant τ is enough to give plausible detection results of ambiguous-color pixels. Here, τ is set to 5/255.

D. Seed Generation and Color Propagation
After obtaining the scribbles, we propagate them to the entire image to generate the complete colorization result. Color propagation is one of the key problems in the study of scribble-based colorization algorithms, which basically follow the assumption that adjacent pixels with similar luminance values are likely to have similar colors. Hence, the existed color hints can gradually spread to their adjacent pixels with similar luminance, until all the pixels are colorized. Unlike the sparse, manually created color hints, our scribbles are dense and are less likely to cause color bleeding during propagation. The pioneering work [14] introduced by Levin et al. is already sufficient to propagate colors properly. The only concern lies in the large occluded regions where there are no color hints at all. To further alleviate color bleeding in these regions, we generate extra color seeds to guide the propagation process.
To begin with, the monochrome image is divided into nonoverlapped blocks of size B ×B. In each block, we categorize pixels into several luminance levels. Specifically, we sort their luminance values in ascend order. A level splitter is set where the absolute luminance difference between two adjacent values is greater than the threshold τ l . We have to ensure that each luminance level of pixels has at least one color hint. Otherwise, we select one pixel p from that level as the seed pixel, and search for N p of its most similar pixels in luminance, denoted as q n , 1 ≤ n ≤ N p , in the initial scribbles within a window of size W N × W N . Here, we set B = 20, τ l = 9/255, N p = 3 and W N = 50. The color of p is computed as where q l,n and q a,n denote the luminance value and the chrominance value of pixel p n respectively, and z p denotes the normalization parameter. With the initial dense scribbles and the extra color seeds, we apply the color propagation algorithm [14] to colorize the remaining pixels. Fig. 4 (b) and (d) compare the colorization results with and without color seeds, showing that color seeds help to reduce incorrect color propagation.
In practice, extra color seeds only account for very small part of the total pixels (< 0.05% in the Middlebury dataset), and have little impact on the overall accuracy. To estimate more reliable colors for them, we use a window centered at each seed pixel rather than using just a single pixel for matching. Sometimes the color seeds may be incorrect in the fully occluded regions, but fetching color from neighbors can make the occluded contents locally consistent in chrominance.

IV. EXPERIMENTS
In this section, we first introduce the experimental setup. Then, we validate our algorithm by performing it step-by-step to show the contributions of each stage. Next, comparisons with different methods are conducted on both synthetic and real-world mono-color image pairs. Finally, we have a discussion on several implementation details.

A. Experimental Setup
Our algorithm is implemented in MATLAB R2020b. All of our experiments are conducted on a personal computer with 2.70GHz CPU (Intel Core i5-6400) and 24 GB RAM.
We evaluate our algorithm on the public Middlebury 2005, 2006 datasets [48], [49] and a SceneFlow test set [52]. The Middlebury datasets consist of 30 groups of multi-view color images for stereo matching evaluation. In our experiments, we convert the left view image into the CIELAB color space, and take the lightness channel as the target monochrome image. Its adjacent right view is taken as the guidance image. The original left-view color image is taken as ground truth. The SceneFlow test set contains 120 stereo images, where the synthetic image pairs are generated in the same way. Two common quality metrics, i.e., peak signal-to-noise ratio (PSNR) and structural similarity index (SSIM) [53], are employed to assess the colorization performance.
We also compare our algorithm to the state-of-the-art colorization algorithms and guided restoration algorithms. The colorization algorithms include Jeon16 [12], He18 [22], He19 [23], Jampani17 [54], and Zhang19 [55]. Jeon16 [12] uses stereo matching to register the mono-color image pair before colorization. He18 [22] completes matching and colorization with two separated neural networks. Its following work, Zhang19 [55], is applied to video colorization tasks. He19 [23] is also a deep learning algorithm that transfers color from guidance to target by constructing semantic correspondence. Jampani17 [54] is a video colorization algorithm that aims to propagate colors frame by frame from the reference one. Its application scenario is similar to ours, for the mono-color pairs can be recognized as two adjacent video frames. The guided restoration algorithms include Pan19 [45], Shibata17 [7], and Jung17 [13]. Since their target images are the RGB ones, we only conduct visual comparisons.
To validate our algorithm in real scenes, we set up a dualcamera system and create our own mono-color image pairs. The monochrome camera captures the left-view image, while the color camera captures the right view. Since the image pairs do not have ground truth, we only conduct the visual assessment as well.

B. Performance Assessment
To validate our colorization algorithm, we perform it step by step and show the contributions of each stage to the colorization results. In the dense scribbling stage, block matching allocates each monochrome pixel an initial color value. A shown in Fig. 5 (c), the initial colors are already plausible in most regions, even in some occluded areas. With outliers detection, the wrong colorization areas are effectively located. We remove these incorrect color assignments and obtain the dense scribbling, displayed in Fig. 5 (d). Fig. 5 (e) shows the final colorization result after color propagation.
In the real application scenarios, the resolutions of the monochrome image and the color image can be different. Hence, we evaluate our algorithm in the situation where the color image is smaller than the monochrome image. Before colorization, we up-sample the guidance image using bicubic interpolation to match the size of the target image for block matching. As shown in Fig. 6 (b), the up-sampled guidance image is over-smooth, but we can still achieve good colorization results thanks to the robustness of block matching. Similarly, over-smoothing caused by image denoising on the guidance image also has little adverse effect on the colorization accuracy.  We also capture mono-color image pairs with a dualcamera system to evaluate our algorithm in real scenarios. Due to the filtering structure of RGB cameras, intensities of the color images are lower than the monochrome images. The color image requires to match the intensity level of the monochrome image for accurate feature matching. Let C denote the grayscale version of the color image C obtained by averaging its R, G and B channels. Intensities of C and the monochrome image M have a linear relationship, i.e., M and λC are of the same intensity level. The linear parameter λ is computed as the average luminance ratio between the image pair. Hence, block matching can be performed between M and C = λC for realistic mono-color image pairs. Here, λ can also be computed locally for each search region to achieve higher robustness. It's worth noting that the matching process is conducted on the raw data. To handle non-linear situations in the image signal processing pipeline such as Gamma transformation, the linear model still works well. Fig. 7 (d) shows one of our colorization results. Compared to the guidance image displayed in Fig. 7 (b), whose intensity level has been matched to the target image, our restored color image has lower noise intensities and contains richer textures that conventional denoising algorithms cannot obtain. Fig. 7 (c) is obtained by Jeon16 [12] that registers the image pair via stereo matching and then perform colorization. Its colorization result suffers from the color bleeding problem. One of the reasons is that it's hard to estimate an accurate disparity map when the contents of the image pair are not consistent in terms of noise and textures. In comparison, our algorithm is more robust and can restore color images with better visual quality in terms of less color bleeding, demonstrating that image alignment is not an essential step for accurate colorization using mono-color image pairs.

C. Comparisons to Colorization Algorithms
We quantitatively evaluate our algorithm on the Middlebury 2005, 2006 datasets [48], [49] and the SceneFlow test set [52]. We also compare it to the state-of-the-art example-based colorization algorithms including Jeon16 [12], He18 [22], He19 [23] and Zhang19 [55], as well as the video color propagation algorithm Jampani17 [54]. To simulate image noise in real scenes, we add mixed Poisson-Gaussian noise [56] to the guidance image with noise parameters α, σ 2 ∈ {0, 0.03 2 }, which indicate the noise variance of each pixel in the guidance image:   Results of He18 [22], He19 [23], Zhang19 [55] and Jam-pani17 [54] are obtained by the source codes and network models from the authors' websites, while results of Jeon16 [12] are obtained by our own implementation that follows the exact steps and parameter settings according to the paper. As feature matching can be directly performed between the target image and the lightness channel of the guidance image, decolorization of the guidance image in Jeon16 [12] are not included in the experiments. For fair comparison, deep learning methods are fine-tuned using 15000 image pairs from the SceneFlow train set. In addition, the lightness channel of each colorization result obtained by the compared algorithms is replaced by the target monochrome image as in our algorithm. Table II and Table III lists the average PSNR and SSIM obtained by different algorithms on the 30 mono-color image pairs from the Middlebury dataset. Visual results under noise parameters α = σ 2 = 0.03 2 are shown in Fig. 8. Jeon16 [12] achieves good PSNR and SSIM, and also shows plausible colorization results. It enhances the colorization method in [14] by introducing an additional weight term. The entire image is segmented into super-pixels and the weight term is computed by the median chrominance of each super-pixel. However, restricted by the accuracy of disparity estimation and superpixel segmentation, color bleeding still exists. He18 [22], He19 [23] and Zhang19 [55] obtain results with better visual quality in terms of less color bleeding. However, they do not achieve high PSNR and SSIM values. The main reason is that, they are designed to transfer colors between two dissimilar images. The use of perceptual loss causes the colorization results to be faithful to the overall style rather than the accurate colors of the guidance images. Jampani17 [54] propagates colors between two adjacent video frames where the motions are relatively small. Hence, it can be less effective when handling large disparity situations, as depicted in Fig. 9. In comparison, our algorithm achieves the highest PSNR and SSIM values and also the best visual quality. As shown in Fig. 10, our algorithm basically out-performs other state-ofthe-art algorithms on every image pair from the Middlebury datasets.
The codes of Jeon16 [12] and our algorithm are both implemented in MATLAB R2020b. The average size of the test images from the Middlebury datasets is 555×660. Jeon16 [12] requires several minutes to colorize one monochrome image, which is also mentioned in the author's paper. In comparison, our algorithm only takes about 10.1 seconds per image (5.9 seconds for dense scribbling and 4.2 seconds for color propagation). Using C++ implementation and parallel computing can further reduce the runtime significantly. In comparison, the dense scribbling process without patch sampling takes about 184.1 seconds per image, which is computationally expensive.
In addition, we set up a dual-camera system to evaluate algorithms on real-world image pairs. Fig. 11 displays the colorization results of the scenes captured using mono and RGB cameras with identical settings. Fig. 12 shows the colorization results, where the source images are captured in the low-light environment using a smartphone equipped with the monocolor cameras. In comparison, colorization performance of each algorithm on the real-world data is similar to that on the synthetic image ones. Our algorithm can achieve colorization   [12], He18 [22], He19 [23], Zhang19 [55] and our algorithm, respectively. results with no color bleeding, even around tiny details, and restore colors faithfully according to the guidance image.

D. Comparisons to Guided Restoration Algorithms
As mentioned before, the other option to fuse a monocolor image pair is to denoise the color image under the guidance of the monochrome one. Hence, we also compare our algorithm to the state-of-the-art guided restoration methods. Pan19 [45] performs self-guided denoising, while Jung17 [13] and Shibata17 [7] are designed for restoration with unaligned image pairs. The visual comparison is displayed in Fig. 13. All the guided restoration methods can achieve plausible results. However, the self-guided Pan19 [45] can lead to artifacts, which is also a common issue in single image denoising. Jung17 [13] causes the restoration results to be over-smooth though it contains a detail enhancement step. Shibata17 [7] handles misalignment by shifting the guidance image, but it cannot resolve the misalignment problem caused by occlusion. It also requires a high amount of calculation if the displacement between two images is large. In comparison, the colorization option can produce images of higher visual quality in terms of better detail preservation and artifact control.  E. Discussions 1) How Does Patch Sampling Influence The Accuracy?: In this work, the size of each patch is set to 16 × 16. We also set the sampling parameters N = T = 4 so that 1/64 of the patches are selected for dense scribbling, based on the two criteria Φ valid match (N, T ) and Φ confidence (N, T ). As mentioned, by setting N = T = 4, we obtain Φ valid match (4, 4) = 0.7920 and Φ confidence (4, 4) = 0.9639. To show that 1/64 of the patches are indeed sufficient for reliable color estimation, we perform guided colorization without patch sampling for comparison, which is equivalent to setting N = 256. To colorize a similar number of pixels in dense scribbling, we set T = 214. In this case, we obtain Φ valid match (256, 214) = 0.7987 and Φ confidence (256, 214) = 0.9250, which is close to the situation where N = T = 4. Table IV lists the average PSNR and SSIM [53] values on the image pairs from the Middlebury datasets obtained by our colorization algorithm with and without patch sampling respectively. Their results are similar, but patch sampling obtains them in much shorter time, as reported above. Here, we observe that the PSNR and SSIM values obtained without sampling is slightly higher than those with sampling, but the former confidence value is lower than the latter one. The reason is that, the confidence criterion refers to the probability that a pixel obtains the correct color estimate judged by the JND threshold [47], while PSNR and SSIM measures the similarity between the estimate and the ground truth. If dense scribbling is conducted without patch sampling, more candidates can be averaged to generate a more accurate color estimate, leading to higher PSNR and SSIM values. However, although the color estimate obtained without sampling is closer to ground truth than that obtained with sampling, they are both judged to be correct by JND. In other words, human eyes cannot perceive the difference between the two colorization results, but patch sampling significantly reduces the amount of computation.

2) How Does The Pre-denoising
Step Influence The Accuracy?: We use the random redundant DCT (RRDCT) denoising algorithm introduced in [46] to remove the mixed Poisson-Gaussian noise in the guidance image. One of the major reasons we choose RRDCT is that it can runs in almost real time. Here, we give a rough introduction of the denoising process. The noisy image is first divided into multiple overlapped patches. For each patch, hard-thresholding is performed on its DCT coefficients for noise removal, with a threshold related to the noise variance. Noise intensity is approximated to be patch-wisely consistent, computed by the average noise variance of each patch. Finally, the denoised patches are aggregated to construct the complete denoised image.  Fig. 11. Visual comparison of colorization results on the realistic image pairs, obtained by Jeon16 [12], He18 [22], He19 [23], and our algorithm, respectively.  [12], He18 [22], He19 [23], and our algorithm, respectively. obtained by our colorization algorithm with and without denoising on the guidance image, respectively. It's clear that the pre-denoising step helps further improve the accuracy, especially when the noise level is relatively high. The main reason is that noise will affect the accuracy of block matching and cannot be completely eliminated by the weighted average of the color candidates. Spatial denoising is one of the most direct and effective manners to remove the noise of the color candidates. Fig. 14 (c) displays the denoised guidance images under the noise parameters α = σ 2 = 0.03 2 , while Fig. 14 (d) shows the corresponding colorization results. Visually, the denoised images suffer from artifacts and edge smoothing, but our colorization results are not effected by these problems thanks to the robustness of block matching. Hence, RRDCT is already sufficient for robust colorization, and it's not necessary to apply a more complicated denoising algorithm that increases the amount of calculation.

V. CONCLUSIONS
In this work, we propose a guided colorization to restore color images with better quality from the mono-color image pairs. The algorithm is composed of two stages: dense scribbling and color propagation. Dense scribbling applies block matching for robust color estimation. Two types of outliers including occluded and color-ambiguous pixels are detected and then removed from the initial dense scribbles. We also introduce a patch sampling strategy to accelerate the matching process. In the color propagation stage, we generate colors seed in the regions that have no color hints at all, and then propagate colors to the entire image. Experimental results show that, our algorithm is computationally efficient, and achieves good performance in solving the color bleeding problem. 12 (a) Target (b) Guidance (d) Pan19 (e) Jung17 (f) Shibata17 (g) Ours (c) Ground Truth Fig. 13. Visual comparison of results obtained by our colorization algorithm and guided restoration algorithms including Pan19 [45], Jung17 [13], and Shibata17 [7].