Block-matching and 3D filtering (BM3D) is a 3-D

block-matching algorithm A Block Matching Algorithm is a way of locating matching macroblocks in a sequence of digital video frames for the purposes of motion estimation. The underlying supposition behind motion estimation is that the patterns corresponding to objects and ...

used primarily for noise reduction in images. It is one of the expansions of the non-local means methodology. There are two cascades in BM3D: a hard-thresholding and a Wiener filter stage, both involving the following parts: grouping,

collaborative filtering Collaborative filtering (CF) is a technique used by recommender systems.Francesco Ricci and Lior Rokach and Bracha ShapiraIntroduction to Recommender Systems Handbook Recommender Systems Handbook, Springer, 2011, pp. 1-35 Collaborative filtering ...

, and aggregation. This algorithm depends on an augmented representation in the transformation site.

Method

Grouping

Image fragments are grouped together based on similarity, but unlike standard

k-means clustering ''k''-means clustering is a method of vector quantization, originally from signal processing, that aims to partition ''n'' observations into ''k'' clusters in which each observation belongs to the cluster with the nearest mean (cluster centers o ...

and such

cluster analysis Cluster analysis or clustering is the task of grouping a set of objects in such a way that objects in the same group (called a cluster) are more similar (in some sense) to each other than to those in other groups (clusters). It is a main task of ...

methods, the image fragments are not necessarily disjoint. This

is less computationally demanding and is useful later on in the aggregation step. Fragments do however have the same size. A fragment is grouped if its dissimilarity with a reference fragment falls below a specified threshold. This grouping technique is called block-matching, it is typically used to group similar groups across different frames of a digital video, BM3D on the other hand may group

macroblocks The macroblock is a processing unit in image and video compression formats based on linear block transforms, typically the discrete cosine transform (DCT). A macroblock typically consists of 16×16 samples, and is further subdivided into transform ...

within a single frame. All image fragments in a group are then stacked to form 3D cylinder-like shapes.

Collaborative filtering

Filtering is done on every fragments group. A

d+1

dimensional linear transform is applied, followed by a transform-domain shrinkage such as

Wiener filtering In signal processing, the Wiener filter is a filter used to produce an estimate of a desired or target random process by linear time-invariant ( LTI) filtering of an observed noisy process, assuming known stationary signal and noise spectra, and ...

, then the linear transform is inverted to reproduce all (filtered) fragments.

Aggregation

The image is transformed back into its two-dimensional form. All overlapping image fragments are weight-averaged to ensures that they are filtered for noise yet retain their distinct signal.

Extensions

Color images

RGB images can be processed much like grayscale ones. A luminance-chrominance transformation should be applied to the RGB image. The grouping is then completed on the luminance channel which contains most of the useful information and a higher SNR. This approach works because the noise in the chrominance channels is strongly correlated to that of the luminance channel, and it saves approximately one-third of the computing time because grouping takes up approximately half of the required computing time.

Deblurring

The BM3D algorithm has been extended (IDD-BM3D) to perform decoupled deblurring and denoising using the

Nash equilibrium In game theory, the Nash equilibrium, named after the mathematician John Nash, is the most common way to define the solution of a non-cooperative game involving two or more players. In a Nash equilibrium, each player is assumed to know the equ ...

balance of the two objective functions.

Convolutional neural network

An approach that integrates a

convolutional neural network In deep learning, a convolutional neural network (CNN, or ConvNet) is a class of artificial neural network (ANN), most commonly applied to analyze visual imagery. CNNs are also known as Shift Invariant or Space Invariant Artificial Neural Netwo ...

has been proposed and shows better results (albeit with a slower runtime).

MATLAB MATLAB (an abbreviation of "MATrix LABoratory") is a proprietary multi-paradigm programming language and numeric computing environment developed by MathWorks. MATLAB allows matrix manipulations, plotting of functions and data, implementa ...

code has been released for research purpose.

Implementations

* Reference implementation in

and Python released under an

open-source Open source is source code that is made freely available for possible modification and redistribution. Products include permission to use the source code, design documents, or content of the product. The open-source model is a decentralized sof ...

proprietary license
BM3D
* Well documented C-based implementation released under the

GPLv3 The GNU General Public License (GNU GPL or simply GPL) is a series of widely used free software licenses that guarantee end users the four freedoms to run, study, share, and modify the software. The license was the first copyleft for general u ...

bm3d
*

CUDA CUDA (or Compute Unified Device Architecture) is a parallel computing platform and application programming interface (API) that allows software to use certain types of graphics processing units (GPUs) for general purpose processing, an approach ...

and C++ based implementation released under the

bm3d-gpu

References

{{Noise, state=uncollapsed Image noise reduction techniques