Two-Dimensional Orthonormal Tree-Structured Haar Transform for Fast Block Matching
The goal of block matching (BM) is to locate small patches of an image that are similar to a given patch or template. This can be done either in the spatial domain or, more efficiently, in a transform domain. Full search (FS) BM is an accurate, but computationally expensive procedure. Recently intro...
Main Authors: | , |
---|---|
Format: | Article |
Language: | English |
Published: |
MDPI AG
2018-11-01
|
Series: | Journal of Imaging |
Subjects: | |
Online Access: | https://www.mdpi.com/2313-433X/4/11/131 |
_version_ | 1818198679291428864 |
---|---|
author | Izumi Ito Karen Egiazarian |
author_facet | Izumi Ito Karen Egiazarian |
author_sort | Izumi Ito |
collection | DOAJ |
description | The goal of block matching (BM) is to locate small patches of an image that are similar to a given patch or template. This can be done either in the spatial domain or, more efficiently, in a transform domain. Full search (FS) BM is an accurate, but computationally expensive procedure. Recently introduced orthogonal Haar transform (OHT)-based BM method significantly reduces the computational complexity of FS method. However, it cannot be used in applications where the patch size is not a power of two. In this paper, we generalize OHT-based BM to an arbitrary patch size, introducing a new BM algorithm based on a 2D orthonormal tree-structured Haar transform (OTSHT). Basis images of OHT are uniquely determined from the full balanced binary tree, whereas various OTSHTs can be constructed from any binary tree. Computational complexity of BM depends on a specific design of OTSHT. We compare BM based on OTSHTs to FS and OHT (for restricted patch sizes) within the framework of image denoising, using WNNM as a denoiser. Experimental results on eight grayscale test images corrupted by additive white Gaussian noise with five noise levels demonstrate that WNNM with OTSHT-based BM outperforms other methods both computationally and qualitatively. |
first_indexed | 2024-12-12T02:09:42Z |
format | Article |
id | doaj.art-8099b110de3b4c9d8c0f435e5e781857 |
institution | Directory Open Access Journal |
issn | 2313-433X |
language | English |
last_indexed | 2024-12-12T02:09:42Z |
publishDate | 2018-11-01 |
publisher | MDPI AG |
record_format | Article |
series | Journal of Imaging |
spelling | doaj.art-8099b110de3b4c9d8c0f435e5e7818572022-12-22T00:41:57ZengMDPI AGJournal of Imaging2313-433X2018-11-0141113110.3390/jimaging4110131jimaging4110131Two-Dimensional Orthonormal Tree-Structured Haar Transform for Fast Block MatchingIzumi Ito0Karen Egiazarian1School of Engineering, Tokyo Institute of Technology, Tokyo 152-8552, JapanSignal Processing Laboratory, Tampere University of Technology, Tampere 33720, FinlandThe goal of block matching (BM) is to locate small patches of an image that are similar to a given patch or template. This can be done either in the spatial domain or, more efficiently, in a transform domain. Full search (FS) BM is an accurate, but computationally expensive procedure. Recently introduced orthogonal Haar transform (OHT)-based BM method significantly reduces the computational complexity of FS method. However, it cannot be used in applications where the patch size is not a power of two. In this paper, we generalize OHT-based BM to an arbitrary patch size, introducing a new BM algorithm based on a 2D orthonormal tree-structured Haar transform (OTSHT). Basis images of OHT are uniquely determined from the full balanced binary tree, whereas various OTSHTs can be constructed from any binary tree. Computational complexity of BM depends on a specific design of OTSHT. We compare BM based on OTSHTs to FS and OHT (for restricted patch sizes) within the framework of image denoising, using WNNM as a denoiser. Experimental results on eight grayscale test images corrupted by additive white Gaussian noise with five noise levels demonstrate that WNNM with OTSHT-based BM outperforms other methods both computationally and qualitatively.https://www.mdpi.com/2313-433X/4/11/131Haar transformorthogonal transformtree-structured transformblock matchingdenoising |
spellingShingle | Izumi Ito Karen Egiazarian Two-Dimensional Orthonormal Tree-Structured Haar Transform for Fast Block Matching Journal of Imaging Haar transform orthogonal transform tree-structured transform block matching denoising |
title | Two-Dimensional Orthonormal Tree-Structured Haar Transform for Fast Block Matching |
title_full | Two-Dimensional Orthonormal Tree-Structured Haar Transform for Fast Block Matching |
title_fullStr | Two-Dimensional Orthonormal Tree-Structured Haar Transform for Fast Block Matching |
title_full_unstemmed | Two-Dimensional Orthonormal Tree-Structured Haar Transform for Fast Block Matching |
title_short | Two-Dimensional Orthonormal Tree-Structured Haar Transform for Fast Block Matching |
title_sort | two dimensional orthonormal tree structured haar transform for fast block matching |
topic | Haar transform orthogonal transform tree-structured transform block matching denoising |
url | https://www.mdpi.com/2313-433X/4/11/131 |
work_keys_str_mv | AT izumiito twodimensionalorthonormaltreestructuredhaartransformforfastblockmatching AT karenegiazarian twodimensionalorthonormaltreestructuredhaartransformforfastblockmatching |