Noisy image block matching based on dissimilarity measure in discrete cosine transform domain

Abstract

In this paper, the problem of image block similarity measuring in noisy environment is considered. In different practical applications often is necessary to find groups of similar image blocks within an ample search area. In such situation, the full search algorithm is very slow; apart, its accuracy is low due to the presence of noise. New algorithms for similar image block matching in noisy environment are presented. The algorithms are based on the dissimilarity measure calculated as the distance between image patches in the discrete cosine transform domain. The proposed algorithms perform the hierarchical search for the similar image blocks and hereby have a reduced complexity in comparison to the full search algorithm. Adjusting the radius of the distance calculation for spectral coefficient matching, the characteristics of the block matching algorithm can easily be adjusted to obtain a better accuracy of the matched block group. A higher accuracy is obtained using the local adaptation of the radius for the distance calculation outperforming the existing algorithms used to find groups of similar blocks in different applications, such as image noise filtering and image clustering. The performance of the different block matching algorithms were evaluated on the base of the proposed accuracy measure that uses as a reference the list of patches obtained with the full search algorithm in the absence of noise.

Keywords

1. Introduction

The problem of image template location in a considered image is very common in different applications such as video compression, image clustering, vector quantization, nonlocal noise reduction [1 –5]. To match templates, various measures of similarity/dissimilarity can be applied [1]. Among them, the most simple and popular measure is square L₂ norm or square Euclidean distance usually calculated as the sum of squared differences of corresponding pixels in two templates or image blocks. Despite its simplicity, the calculation of the square distances can cause significant computational load to find the best block matching in video compression [3] or modern noise suppression algorithm such as BM3D [5] and LPG-PCA [6], image inpainting [7]. The direct computation of all the matching requires O (KMNr²) operations [8], where M × N is the number of image pixels, r² denotes the patch size, K is the maximum offset.

In [3], an ample review of different existing block matching algorithms of reduced complexity are described: techniques based on a reduced set of candidates, techniques based on a reduced-complexity block distortion measure, techniques based on a subsampled block-motion field, hierarchical search techniques, fast full-search techniques. Among them, it was found that the fastest technique is the hierarchical search that usually performs on a mean pyramid calculated applying low-pass filtering and subsampling to the considered image(s) [3].

For many years, the patch matching based on the cross-correlation in Fourier transform domain [9, 12] was a state-of-the-art method [10]. This method requires approximately O (KMN log ₂ (M)) operations [11] that is faster than the exhaustive search when r² > 30 log ₂ (M) [10]. However, when K is much larger than r, the direct method is faster than Fourier transform based method; the transform method is more efficient when r approaches K [11].

A fast method for image block dissimilarity computation of the sum of squared differences of pixel values within the patches is presented in [8]. It based on the integral image calculation [10] that permits to reduce the total time complexity independently from the patch size to O ((M - r) (N - r)) [8] operations at the expense of some flexibility and errors caused by limited numerical precision [8]. Besides, block matching using integral images has limited performance gain with respect to exhaustive block matching for small patch sizes [8].

From other hand, the matched blocks using the aforementioned methods become less similar when the image(s) are contaminated by noise. Obviously, the image data can be previously filtered to provide better matching but it can be inconvenient in some practical situations. For this reason, a similarity/dissimilarity measure robust to noise presence is required to find similar patches in noisy images.

In this paper, the feature vectors are formed as the patches in the discrete cosine transform domain that describe well the considered image blocks to perform fast block matching with the accuracy near to the full search technique or higher in the case of noise presence.

2. Patch dissimilarity measures

There exist a number of similarity/dissimilarity measures that can be applied to image processing. Here, only the simplest and fastest to calculate measures are described.

The standard dissimilarity measure between two image blocks of size r_x, r_y, sum of squared distances (SSD), can be formulated as $\begin{matrix} d (x, y, o_{x}, o_{y}) = \\ \sum_{j = 0}^{r_{y} - 1} \sum_{i = 0}^{r_{x} - 1} {[\begin{matrix} u (x + i, y + j) \\ - u (x + o_{x} + i, y + o_{y} + j) \end{matrix}]}^{2}, \end{matrix}$ (1)

where u (x, y) is the image pixel at the coordinate x, y, o_x, o_y ∈ K denote the shift between the compared image blocks in the horizontal and vertical directions, respectively. The best matching is the minimum of the SSD found within the search window: $u_{bestmatch} (x, y) = arg \min_{o_{x} o_{y}, \in K} {d (x, y, o_{x}, o_{y})},$ (2)

where the search area K = K_x · K_y is limited by offsets K_x, K_y in the horizontal and vertical directions, respectively. Often, the task is to find the set of the l best matched patches; this task is common in patch based filtering algorithms [5, 6]. Usually, it requires to calculate SSD (1) between all the blocks within the offset K, sort them and store the shortest block distances and their coordinates in the list p (x, y) = [d₁, x₁, y₁; …; d_l, x_l, y_l] ^T of the matched patches. The number of operations to find p may be large; for example, for the r² = 8 ×8 pixels block and the search window K = 20 × 20, at least O (Kr²) = 25600 sums and multiplications are required for each image pixel in (M - r) × (N - r) range. The simplest but not accurate way to speed up the calculations is find the distances between the means of the patches or even between the block central pixel values [7]. And the efficient block matching algorithm based on integral images requires O (4K) = 1600 operations for each pixel apart from the integral image calculation, but some errors caused by limited numerical precision might be introduced.

The number of operations to find p with a modification of a hierarchical search: firstly, the image is smoothed by some low-pass filter and then, distances are evaluated using only 4 pixels of the smoothed r² = 8 ×8 image blocks (without subsampling): $\begin{matrix} d_{s} (x, y, o_{x}, o_{y}) = {[u_{s} (x, y) - u_{s} (x + o_{x}, y + o_{y})]}^{2} \\ + {[u_{s} (x + 4, y) - u_{s} (x + o_{x} + 4, y + o_{y})]}^{2} \\ + {[u_{s} (x, y + 4) - u_{s} (x + o_{x}, y + o_{y} + 4)]}^{2} \\ + {[u_{s} (x + 4, y + 4) - u_{s} (x + o_{x} + 4, y + o_{y} + 4)]}^{2} \end{matrix}$ (3)

where d_s denotes SSD calculated on the smoothed image u_s.

The image smoothing can be performed in spatial domain applying a low pass filter or in a transform domain. Such filtering apart from the complexity reduction introduces some robustness to the noise present in the contaminated images that improves the accuracy of block matching when searching for the minimum (2) or forming the list of patches p.

In this paper, for the low pass filtering is performed in discrete cosine transform (DCT) and consists in zeroing high frequency coefficients. Or similarly, one can take the first DCT coefficients that represent signal low frequencies and these coefficients can be efficiently used to calculate the dissimilarities between the image patches. Recall that 2D DCT for small r can be performed efficiently by matrix multiplications: $u_{T} (x, y) = A \cdot u (x, y) \cdot A^{T}$ (4)

where u (x, y) is the image block at the coordinate x, y, u_T (x, y) is DCT transform of the image block at the coordinate x, y, and A is the DCT transformation matrix whose elements a_i,j are defined as [11] $\begin{matrix} a_{i, j} = β (i) \sqrt{\frac{2}{n}} cos (\frac{π \cdot i \cdot (2 j + 1)}{2 n}), \\ β (i) = {\begin{matrix} \frac{1}{\sqrt{2}}, & i = 1 \\ 1 & otherwise \end{matrix} \end{matrix}$ (5)

The distances between the different patches in DCT domain may be calculated as $\begin{matrix} d_{DCT} (x, y, o_{x}, o_{y}) = \\ \sum_{ω_{y} = 0}^{r_{ω}} \sum_{ω_{x} = 0}^{r_{ω}} {[\begin{matrix} u_{T} (x, y, ω_{x}, ω_{y}) \\ - u_{T} (x + o_{x}, y + o_{y}, ω_{x}, ω_{y}) \end{matrix}]}^{2}, \end{matrix}$ (6)

where u_T (x, y, ω_x, ω_y) is the ω_x, ω_y-th spectral coefficient of the image DCT patch u_T (x, y) at the coordinate x, y, o_x, o_y ∈ K denote the spatial shift between the compared image DCT patches in the horizontal and vertical directions, respectively, r_ω is the radius of the first spectral coefficients that participate in the distance calculation. Due to the energy compacting property of DCT, one can expect the distances calculated on the first DCT coefficients of the DCT patches, Equation (4), represent better the dissimilarities of the respective image blocks than d_h calculated on the smoothed image u_s. Obviously, when r = r_ω all spectral coefficient are participate in the distance calculation and the distance calculated with Equation (6) is equal to Equation (1)d_DCT (x, y, o_x, o_y) = d (x, y, o_x, o_y) because of energy normalization in Equation (5).

A simple modification of the distance Equation (6) is $\begin{matrix} d_{absDCT} (x, y, o_{x}, o_{y}) = \\ \sum_{ω_{y} = 0}^{r_{ω}} \sum_{ω_{x} = 0}^{r_{ω}} {[\begin{matrix} | u_{T} (x, y, ω_{x}, ω_{y}) | \\ - | u_{T} (x + o_{x}, y + o_{y}, ω_{x}, ω_{y}) | \end{matrix}]}^{2} \end{matrix}$ (7)

The distance Equation (7) may be useful, for example, to find the image clusters of homogeneous regions and edges, and is expected to be useful for deriving the spectral/statistical properties of the considered image blocks to improve the noise suppression of the modern noise suppression algorithms, such as BM3D or LG-PCA [5, 6].

In this paper, the distance Equation (6) is used to form the list p of matched patches when few DCT coefficients are involved in the distance calculation, r_ω = 2.7.

3. Practical DCT-based dissimilarity measure calculation algorithms

As shown below in Section 4, the properties of the measure Equation (6) are sometimes insufficient to determine with more precision the list p of matched patches, especially when noise is high and/or the considered image has texture areas; for these reasons, it must be improved.

To this end, the hierarchical approach may be useful: firstly, the algorithm searches for a rough approximation of the final list; secondly, a more exact search is performed over the provisional list found at the previous step.

3.1. Simple hierarchical search algorithm

In this paper, the following simple hierarchical algorithm that consists of two stages is used for comparative purposes.

At the first stage, the patches of the reduced size by subsampling of the image smoothed by an antialiasing filter are formed; their differences Equation (1) with the reference patch in the list are calculated: $\begin{matrix} d_{h 1} (x, y, o_{x}, o_{y}) = \\ \sum_{j = 0}^{\frac{r_{y} - 1}{2}} \sum_{i = 0}^{\frac{r_{x} - 1}{2}} {[\begin{matrix} u_{s} (x + 2 i, y + 2 j) \\ - u_{s} (x + o_{x} + 2 i, y + o_{y} + 2 j) \end{matrix}]}^{2}, \end{matrix}$ (8)

where u_s (x, y) denotes the x, y-th pixel of the smoothed image. The list of the sorted in ascending order differences is formed: $d_{h 1} (x, y, o_{x}, o_{y}) = \underset{K}{Δ} d_{h 1} (x, y, o_{x}, o_{y}), o_{x}, o_{y} \in K$ (9)

where $\underset{K}{Δ}$ denotes the operator of the sorting in ascending order the differences d_h1 (x, y, o_x, o_y) within the offset K. The coordinates (x, y, o_x, o_y) of first 8l_NN patches having the minimal differences with the reference patch form the provisional extended list p_ex of matched patches.

At the second stage, the patches of the original image patches in the list p_ex are matched to the current image block according to Euclidean distance Equation (1) to form the ordered list $d (x, y) = \underset{8 l_{NN}}{Δ} d (x, y, o_{x}, o_{y}),$ (10)

and the first l_NN patches nearest to the considered image block with the coordinates (x, y) are included in the final list p_h of the matched image blocks.

3.2. Algorithm of the hierarchical search in DCT domain

The idea of the hierarchical search can easily be implemented in DCT domain. The simple (but not the best) algorithm of hierarchical search in DCT domain (DCTBM algorithm) can be formulated as follows.

Firstly, the provisional extended list p_ex of matched patches is found with few DCT coefficients used in the distance calculation r_ω1 = 4 of the full size r patches (r² = 8 ×8 in our experiments) $\begin{matrix} d_{DCT 1} (x, y, o_{x}, o_{y}) \\ = \sum_{ω_{y} = 0}^{r_{ω 1} - 1} \sum_{ω_{x} = 0}^{r_{ω 1} - 1} {[\begin{matrix} u_{T} (x, y, ω_{x}, ω_{y}) \\ - u_{T} (x + o_{x}, y + o_{y}, ω_{x}, ω_{y}) \end{matrix}]}^{2}, \\ o_{x}, o_{y} \in K \end{matrix}$ (11)

and the list of the differences sorted in ascending order is formed: $d_{DCT 1} (x, y, o_{x}, o_{y}) = \underset{K}{Δ} d_{DCT 1} (x, y, o_{x}, o_{y}) .$ (12)

As in the case of the simple hierarchical search, the coordinates (o_x, o_y) of first 8l_NN patches having the minimal differences with the reference patch form the provisional extended list p_ex of the matched patches.

At the second stage, the patches in the list p_ex are matched to the current image block using r_ω2 = 5 and according to the distance $\begin{matrix} d_{DCT 2} (x, y, o_{x}, o_{y}) \\ = \sum_{ω_{y} = 0}^{r_{ω 2} - 1} \sum_{ω_{x} = 0}^{r_{ω 2} - 1} {[\begin{matrix} u_{T} (x, y, ω_{x}, ω_{y}) \\ - u_{T} (x + o_{x}, y + o_{y}, ω_{x}, ω_{y}) \end{matrix}]}^{2}, \\ o_{x}, o_{y} \in p_{ex} \end{matrix}$ (13)

to form the ordered list of patches $d (x, y) = \underset{k}{Δ} d_{DCT 2} (x, y, o_{x}, o_{y})$ , and the first k = l_NN patches are included in the final list p_DCTBM of the matched image blocks.

3.3. Adaptive algorithm of the hierarchical search in DCT domain

By experiments, it was found that the performance of the DCTBM algorithm is not always satisfactory and need to be modified according to different signal/noise ratios. The following modified algorithm ADCTBM of the DCT-based dissimilarity measure performs better on the noisy images with different noise variance.

As it is shown below in Section 4, the accuracy of a DCT-based block matching algorithm depends on the signal/nose ratio and radius r_ω in Equation (6). When the noise variance is high, the DCT-based block matching algorithm DCTBM, Equations (11 –13), performs satisfactory because it consider only the low frequencies where the signal energy is high and does not take into account high spatial components where noise energy is greater than the signal energy. And when the noise variance is low, the signal energy in higher frequencies is greater than of the noise, and more calculations must be used to form the lists of patches at both stages. These relations between signal and noise components also depend on image type: for plain regions, lower values of r_ω are better; contrary, for textural images the radius r_ω has to be shorter.

Taking into account these observations, a locally adaptive block matching algorithm ADCTBM is proposed. The algorithm take into account the local data activity and compare it to the noise variance; if the data activity is greater than a threshold, the radius r_ω is longer, else a shorter radius is taken. This way, the base DCTBM algorithm is modified as:

Firstly, the local data activity is estimated and compared to the noise variance to make the decision about the length of the radius r_ω: $\begin{matrix} S (x, y) = \sum_{ω_{y} = 0}^{r - 1} \sum_{ω_{x} = 0}^{r - 1} {[u_{T} (x, y, ω_{x}, ω_{y})]}^{2}, \\ α (x, y) = {\begin{matrix} 1, & if S (x, y) > 9 \cdot σ^{2} r^{2} \\ 0, & otherwise \end{matrix} \end{matrix}$ (14)

Secondly, the length of the radiuses r_ω1, r_ω2 for the first and the second stage of the base algorithm DCTBM, Equations 13) are selected: $\begin{matrix} r_{ω 1} = {\begin{matrix} r / 4 & if α (x, y) = 0 \\ r / 2 & if α (x, y) = 1 \end{matrix}, \\ r_{ω 2} = {\begin{matrix} r / 2 & if α (x, y) = 0 \\ r & if α (x, y) = 1 \end{matrix} . \end{matrix}$ (15)

Additionally, the number of patches in the list p_ex also adjusted: k = 8l_NN when α (x, y) = 1, otherwise k = 11l_NN.

3.4. Improving block matching by DCT coefficient weighting

To improve the performance of the described DCT-based block matching algorithms, the use of weighted DCT coefficients is proposed. According to Wiener filtering theory [9, 12], the frequency response of the optimal filter in the transform domain is $H (ω) = \frac{P_{s} (ω)}{P_{s} (ω) + P_{n} (ω)},$ (16)

where P_s (ω) is the power spectral density of a noise-free data and P_n (ω) is the power spectral density of noise. Assuming noise in white Gaussian, P_n (ω) is equal to the noise variance, σ². In practice, noise variance is known or can be easily estimated; in such conditions, the DCT coefficients can be weighted as $u_{W} (ω_{x}, ω_{y}) = u_{T} (ω_{x}, ω_{y}) \cdot \frac{{[u_{T} (ω_{x}, ω_{y})]}^{2}}{{[u_{T} (ω_{x}, ω_{y})]}^{2} + σ^{2}}$ (17)

Of course, Equation (17) is not the best way to remove noise from patches because the noisy data [u_T (ω_x, ω_y)] ² are used as a signal spectral density estimate instead of exact P_s (ω) values. However, the weighting (16) is considered to be sufficient to improve the results of block matching on noisy images.

The weighted according to Equation (17) DCT coefficients u_W (ω_x, ω_y) can substitute the non-weighted coefficients u_T (ω_x, ω_y) in block matching algorithms DCTBM and ADCTBM, Equations (11 –15); such improved algorithms are named as WDCTBM and WADCTBM.

4. Results on noisy data dissimilarity evaluation

In this Section the results of quantitative evaluation of the performance of different block matching algorithms described in Section 3 are presented.

To evaluate the results of dissimilarity calculation applied to block matching problem, the measure of similarity between two lists of the matched blocks p₁ and p₂ is introduced: the lists are more similar when more coordinates in p₁ are included in p₂ independently from the their positions in p₁ and p₂: C (k, m) = card (p_k ∩ p_m). When both lists contain the same coordinates of the image patches, it means they are equal for non-local image filtering; as a result, the restored image fragments will not differ. And with the more different patches in the lists the image filtering result will be more different.

Additional measure of similarity/dissimilarity between two lists may be the distance between the patches with the same coordinates; and if the image restoration algorithm takes into account these distances for weighting, it affects the filtering results. Here, it is assumed that the non-local filtering algorithm does not use any weighting depending on the distances between the patches and does not take into account the values of these distances because the weighting may vary depending on the filtering algorithm.

Taking into account these observations, a measure for direct evaluation of the performance of different block matching algorithms is proposed. The algorithm ability to find similar block can be expressed in terms of a mean number of the coincided coordinates in the lists of the matched blocks p (x, y) and p_ref (x, y) for all image pixels, normalized on the cardinality of the list p_ref and the total number of lists of the matched blocks: $μ = \frac{\sum_{y = 1}^{N - r} \sum_{x = 1}^{M - r} card (p (x, y) \cap p_{ref} (x, y))}{card (p_{ref}) (M - r) (N - r)} .$ (18)

where p_ref (x, y) denotes the reference list of patches, p (x, y) is the list of patches to compare.

Figures 1 and 2 illustrate the typical behavior of the accuracy of the block matching based on the distance Equation (6) in dependence of the radius r_ω and the noise variance. These results were obtained for the test image “Lenna” and “Baboon” for image block size r² = 8 ×8. As one can observe from these figures, the accuracy is decreased when the variance is growing for all radius lengths. However, the accuracy can be increased with the shorter r_ω for high noise levels. This increasing depends on the image data: for an image with plain areas, such as “Lenna” image, the results can be improved selecting r_ω = 3 for the noise variance σ² > 100. Contrary, for textural images, such as “Baboon”, the improvement is observed only for r_ω = 5, r_ω = 6. And only when the variance is greater 225, the results can be improved selecting r_ω = 4. This is due to the fact that the textural images contain high spatial frequencies, and suppressing these features with short r_ω results in a reduced accuracy of the block matching. In other words, the choice of the radius r_ω length depends on the local image block signal/noise ratio at the spatial frequencies that might be suppressed with a short r_ω.

Fig. 1.

Behavior of the accuracy Equation (18) of the simple block matching based on the distance Equation (6) depending on the radius r_ω and the noise variance for the test image “Lenna”, image block size is 8×8, search area K = 21×21.

Fig. 2.

Behavior of the accuracy Equation (18) of the simple block matching based on the distance Equation (6) depending on the radius r_ω and the noise variance for the test image “Baboon”, image block size is 8×8, search area K = 21×21.

A special case is when the radius r_ω = r and the size of the image block is equal to the size of DCT patch. In such conditions, the accuracy of the block matching based on the distance Equation (6) calculation is equal to the accuracy obtained with the Euclidean distance Equation (1), i.e., the performance is identical to the performance of the full search block matching, μ = 1.

To evaluate quantitatively and compare the accuracy of the of the proposed known image block matching algorithm to the known algorithms in noisy environment, their performance according to criterion Equation (18) was tested on the standard 512 × 512 test images “Lena”, “F-16”, “Peppers”, “Aerial”, “Baboon” and “Bridge” in the absence and presence of white additive Gaussian noise of different variance. The simulation results were obtained for image block size r² = 8 ×8 and the search area K = 21 × 21. As a reference, the lists of the matched blocks calculated by the full search algorithm on the noise free test images p_ref = p_FS were used. The obtained results are presented in the Table 1. Analyzing these results, one can conclude:

The proposed algorithms DCTMB, WDCTBM, ADCTBMandWADCTBM outperform the known algorithms (full search, integral image, hierarchical search) in the presence of noise in data;

The best results are obtained with the locally adaptive algorithms ADCTBMandWADCTBM, only in the case of the test image “Bridge” the non-adaptive proposed algorithm WDCTBM that uses weighting of the spectral coefficients according to the Equation (17) produced a slightly better results than the adaptive algorithms;

The spectral coefficient weighting only slightly improves the accuracy of the block matching and not always;

The worst result in all cases were obtained with the hierarchical algorithm, Equation (10);

When the noise is absent, the full search algorithm is the best, but very slow; in such conditions, the proposed algorithms has a reduced complexity because they perform a hierarchical search but the best accuracy comparing to the integral image algorithm [10].

Table 1

Accuracy, Equation (18), of the proposed algorithms DCTBM, WDCTBM, ADCTBM and WADCTBM block matching algorithms for different noise levels and images, when compared with known methods. The best results are marked as bold

Image	Noise variance	Technique
		Full	Integral	Hierarchical	DCTBM	WDCTBM	ADCTBM	WADCTBM
		search	Image (10)	Search (10)	(11–13)	(11–(13, 17)	(14, 15)	(14, 15, 17)
Lenna	0	1	0.9666	0.9541	0.7673	0.7673	0.9923	0.9923
	25	0.4940	0.4837	0.5023	0.5390	0.5476	0.5433	0.5494
	100	0.3427	0.3358	0.3548	0.4178	0.4268	0.4291	0.4338
	225	0.2639	0.2589	0.2773	0.3485	0.3568	0.3651	0.3675
	400	0.2145	0.2106	0.2286	0.3030	0.3104	0.3228	0.3235
F-16	0	1	0.9880	0.9639	0.8462	0.8462	0.9949	0.9949
	25	0.4673	0.4639	0.4788	0.5554	0.5542	0.5713	0.5661
	100	0.3537	0.3508	0.3660	0.4540	0.4516	0.4730	0.4649
	225	0.2880	0.2856	0.3010	0.3958	0.3932	0.4164	0.4069
	400	0.2425	0.2403	0.2561	0.3557	0.3529	0.3782	0.3674
Peppers	0	1	0.9757	0.9353	0.6584	0.6584	0.9877	0.9877
	25	0.5053	0.4966	0.5134	0.5038	0.5127	0.5146	0.5198
	100	0.3453	0.3397	0.3576	0.3946	0.4079	0.4118	0.4197
	225	0.2677	0.2639	0.2813	0.3313	0.3443	0.3516	0.3588
	400	0.200	0.2172	0.2341	0.2889	0.3008	0.3110	0.3169
Aerial	0	1	0.9678	9717	0.8829	0.8829	0.9989	0.9989
	25	0.7473	0.7254	0.7436	0.7484	0.7490	0.7629	0.7641
	100	0.5851	0.5680	0.5895	0.6303	0.6324	0.6285	0.6281
	225	0.4673	0.4535	0.4781	0.5412	0.5440	0.5397	0.5371
	400	0.3808	0.3693	0.3963	0.4730	0.4757	0.4781	0.4736
Baboon	0	1	0.9892	0.9029	0.7008	0.7008	0.9914	0.9914
	25	0.7491	0.7443	0.7111	0.6272	0.6267	0.7413	0.7398
	100	0.5699	0.5670	0.5565	0.5330	0.5331	0.5677	0.5656
	225	0.4451	0.4430	0.4465	0.4574	0.4575	0.4299	0.4265
	400	0.3536	0.3517	0.3650	0.3970	0.3977	0.3775	0.3724
Bridge	0	1	0.9803	0.9617	0.8054	0.8054	0.9989	0.9989
	25	0.7901	0.7778	0.7818	0.7300	0.7318	0.7789	0.7810
	100	0.6101	0.6015	0.6143	0.6235	0.6286	0.6107	0.6140
	225	0.4679	0.4614	0.4815	0.5316	0.5394	0.5221	0.5244
	400	0.3638	0.3584	0.3839	0.4601	0.4687	0.4628	0.4643

5. Conclusions

New algorithms for similar image block matching in noisy environment have presented. The algorithms are based on the dissimilarity measure calculated as the distance between image patches in the discrete cosine transform domain. The algorithms perform the hierarchical search for the similar image blocks and hereby have a reduced complexity in comparison to the full search algorithm. Adjusting the radius of the distance calculation for spectral coefficient matching, the characteristics of the block matching algorithm can easily be adjusted to obtain a better accuracy of the matched block group. A higher accuracy is obtained using the local adaptation of the radius for the distance calculation outperforming the existing algorithms used to find groups of similar blocks. The performance of the different block matching algorithms were evaluated on the base of the proposed accuracy measure that uses as a reference the list of patches obtained with the full search algorithm in the absence of noise. The proposed locally adaptive algorithms ADCTBM, WADCTBM may be useful in different applications, such as image noise filtering, clustering and vector quantization. The evaluation of the proposed algorithm performance in such applications may be the subject of a future work.

Footnotes

Acknowledgments

This work has been partly supported supported by Instituto Politécnico Nacional as a part of the research project SIP 20180878.

References

Brunelli , Template matching techniques in computer vision: Theory and practice, Wiley (2009). DOI: 10.1002/9780470744055

A.A.

Goshtasby , Similarity and Dissimilarity Measures. In: Image Registration: Principles, Tools and Methods Advances in Computer Vision and Pattern Recognition Springer, London, 2012. DOI: 10.1007/978-1-4471-2458-0_2

M.E.

Al-Mualla ,

C.N.

Canagarajah and

D.R.

Bull , Video Coding for Mobile Communications. Efficiency, Complexity, and Resilience. Academic Press, Orlando, FL, USA, 2002, p. 225.

Linde ,

Buzo and

Gray , An algorithm for vector quantizer design, IEEE Transactions on Communications28(1) (1980), 84–95. DOI: 10.1109/TC0M.1980.1094577

Dabov ,

Foi ,

Katkovnik and

Egiazarian , Image denoising by sparse 3D transform-domain collaborative filtering, IEEE Transactions on Image Processing16(8) (2007), 2080–2095. DOI: 10.1109/TIP.2007.901238

Zhang ,

Dong ,

Zhang and

Shi , Two-stage image denoising by principal component analysis with local pixel grouping, Pattern Recognition43 (2010), 1531–1549. DOI: 10.1016/j.patcog.2009.09.023

Ram ,

Elad and

Cohen , Image processing using smooth ordering of its patches, IEEE Transactions on Image Processing22(7) (2013), 2764–2774. DOI: 10.1109/TIP.2013.2257813

Facciolo ,

Limare and

Meinhardt , Integral images for block matching, Image Processing On Line4 (2014), 344–369. DOI: 10.5201/ipol.2014.57

R.C.

Gonzalez and

R.E.

Woods , Digital Image Processing (4th Edition). Pearson, 2017, p. 1168.

10.

Viola and

M.J.

Jones , Robust real-time face detection, International Journal of Computer Vision57(2) (2004), 137–154. DOI: 10.1023/B:VISI.0000013087.49260.fb

11.

J.P.

Lewis , Fast template matching. In: Vision Interface95, Canadian Image Processing and Pattern Recognition Society, 1995, pp. 120–123.

12.

A.K.

Jain , Fundamentals of digital image processing.Prentice-Hall, Inc. Upper Saddle River, NJ, USA, 1989.