Non-local means

Application of non-local means to an image corrupted by Gaussian noise

Non-local means is an algorithm in image processing for image denoising. Unlike "local mean" filters, which take the mean value of a group of pixels surrounding a target pixel to smooth the image, non-local means filtering takes a mean of all pixels in the image, weighted by how similar these pixels are to the target pixel. This results in much greater post-filtering clarity, and less loss of detail in the image compared with local mean algorithms.[1]

If compared with other well-known denoising techniques, non-local means adds "method noise" (i.e. error in the denoising process) which looks more like white noise, which is desirable because it is typically less disturbing in the denoised product.[2] Recently non-local means has been extended to other image processing applications such as deinterlacing,[3] view interpolation,[4] and depth maps regularization.[5]

## Contents

* 1 Definition
* 2 Common weighting functions
* 2.1 Gaussian
* 3 Discrete algorithm
* 4 Efficient implementation
* 5 See also
* 6 References
* 7 External links

## Definition

Suppose Ω is the area of an image, and p and q are two points within the image. Then, the algorithm is:[6]

u(p)=1C(p)∫Ωv(q)f(p,q)dq.

where u(p) is the filtered value of the image at point p, v(q) is the unfiltered value of the image at point q, f(p,q) is the weighting function, and the integral is evaluated ∀q∈Ω.

C(p) is a normalizing factor, given by

C(p)=∫Ωf(p,q)dq.

## Common weighting functions

The purpose of the weighting function, f(p,q), is to determine how closely related the image at the point p is to the image at the point q. It can take many forms.

### Gaussian

The Gaussian weighting function sets up a normal distribution with a mean, μ=B(p) and a variable standard deviation:[7]

f(p,q)=e−|B(q)−B(p)|2h2

where h is the filtering parameter (i.e., standard deviation) and B(p) is the local mean value of the image point values surrounding p.

## Discrete algorithm

For an image, Ω, with discrete pixels, a discrete algorithm is required.

u(p)=1C(p)∑q∈Ωv(q)f(p,q)

where, once again, v(q) is the unfiltered value of the image at point q. C(p) is given by:

C(p)=∑q∈Ωf(p,q)

Then, for a Gaussian weighting function,

f(p,q)=e−|B(q)2−B(p)2|h2

where B(p) is given by:

B(p)=1|R(p)|∑i∈R(p)v(i)

where R(p)⊆Ω and is a square region of pixels surrounding p and |R(p)| is the number of pixels in the region R.

## Efficient implementation

The computational complexity of the non-local means algorithm is quadratic in the number of pixels in the image, making it particularly expensive to apply directly. Several techniques were proposed to speed up execution. One simple variant consists of restricting the computation of the mean for each pixel to a search window centred on the pixel itself, instead of the whole image. Another approximation uses summed-area tables and fast Fourier transform to calculate the similarity window between two pixels, speeding up the algorithm by a factor of 50 while preserving comparable quality of the result.[8]

## See also

* Anisotropic diffusion
* Digital image processing
* Noise reduction
* Nonlocal operator
* Signal processing
* Total variation denoising
* Bounded variation
* Total variation

## References

1. ↑ Buades, Antoni (20–25 June 2005). "A non-local algorithm for image denoising". 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05). 2. 60–65. doi:10.1109/CVPR.2005.38. ISBN 978-0-7695-2372-9.
2. ↑ Buades, Antoni. "On image denoising methods". http://123seminarsonly.com/Seminar-Reports/029/42184313-10-1-1-100-81.pdf.
3. ↑ Dehghannasiri, R.; Shirani, S. (2012). "A novel de-interlacing method based on locally-adaptive Nonlocal-means". 2012 Conference Record of the Forty Sixth Asilomar Conference on Signals, Systems and Computers (ASILOMAR). pp. 1708–1712. doi:10.1109/ACSSC.2012.6489324. ISBN 978-1-4673-5051-8.
4. ↑ Dehghannasiri, R.; Shirani, S. (2013). "A view interpolation method without explicit disparity estimation". 2013 IEEE International Conference on Multimedia and Expo Workshops (ICMEW). pp. 1–4. doi:10.1109/ICMEW.2013.6618274. ISBN 978-1-4799-1604-7.
5. ↑ Martinello, Manuel; Favaro, Paolo. "Depth Estimation From a Video Sequence with Moving and Deformable Objects". IET Image Processing Conference. http://www.manemarty.com/Publications_files/Martinello_DepthSingleVideo.pdf.
6. ↑ Buades, Antoni (2011). "Non-Local Means Denoising". Image Processing on Line 1: 208–212. doi:10.5201/ipol.2011.bcm_nlm. http://www.ipol.im/pub/art/2011/bcm_nlm/.
7. ↑ Buades, Antoni. "On image denoising methods (page 10)". http://123seminarsonly.com/Seminar-Reports/029/42184313-10-1-1-100-81.pdf.
8. ↑ Wang, Jin; Guo, Yanwen; Ying, Yiting; Liu, Yanli; Peng, Qunsheng (2006). "Fast non-local algorithm for image denoising". pp. 1429–1432.

## External links

* Recent trends in denoising tutorial
* Non-local image denoising, with code and online demonstration
* Patents citing 2005 IEEE paper where NLM was claimed as a new technique

* v
* t
* e

Noise (physics and telecommunications)

General|

* Acoustic quieting
* Distortion
* Noise cancellation
* Noise control
* Noise measurement
* Noise power
* Noise reduction
* Noise temperature
* Phase distortion

Noise in...|

* Audio
* Buildings
* Electronics
* Environment
* Government regulation
* Human health
* Images
* Radio
* Rooms
* Ships
* Sound masking
* Transportation
* Video

Class of noise|

* Additive white Gaussian noise (AWGN)
* Atmospheric noise
* Background noise
* Brownian noise
* Burst noise
* Cosmic noise
* Flicker noise
* Gaussian noise
* Grey noise
* Jitter
* Johnson–Nyquist noise (thermal noise)
* Pink noise
* Quantization error (or q. noise)
* Shot noise
* White noise
* Coherent noise
* Value noise
* Gradient noise
* Worley noise

Engineering
terms|

* Channel noise level
* Circuit noise level
* Effective input noise temperature
* Equivalent noise resistance
* Equivalent pulse code modulation noise
* Impulse noise (audio)
* Noise figure
* Noise floor
* Noise shaping
* Noise spectral density
* Noise, vibration, and harshness (NVH)
* Phase noise
* Pseudorandom noise
* Statistical noise

Ratios|

* Carrier-to-noise ratio (C/N)
* Carrier-to-receiver noise density (C/kT)
* dBrnC
* Eb/N0 (energy per bit to noise density)
* Es/N0 (energy per symbol to noise density)
* Modulation error ratio (MER)
* Signal, noise and distortion (SINAD)
* Signal-to-interference ratio (S/I)
* Signal-to-noise ratio (S/N, SNR)
* Signal-to-noise ratio (imaging)
* Signal to noise plus interference (SNIR)
* Signal-to-quantization-noise ratio (SQNR)
* Contrast-to-noise ratio (CNR)

Related topics|

* List of noise topics
* Acoustics
* Colors of noise
* Interference (communication)
* Noise generator
* Radio noise source
* Spectrum analyzer
* Thermal radiation

Denoise
methods|

| General|

* Low-pass filter
* Median filter
* Total variation denoising
* Wavelet denoising

|

2D (Image)|

* Gaussian blur
* Anisotropic diffusion
* Bilateral filter
* Non-local means
* Block-matching and 3D filtering (BM3D)
* Shrinkage Fields
* Denoising autoencoder (DAE)
* Deep Image Prior

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Non-local means. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Non-local_means&oldid=203396"
*[v]: View this template
*[t]: Discuss this template
*[e]: Edit this template