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...

Full description

Bibliographic Details
Main Authors: Izumi Ito, Karen Egiazarian
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