Content deleted Content added
Description of process used "axis" when "access" was the correct spelling. |
|||
| (3 intermediate revisions by 3 users not shown) | |||
Line 1:
{{Short description|Mathematical operation in signal processing}}
In signal processing, '''multidimensional discrete convolution''' refers to the mathematical operation between two functions ''f'' and ''g'' on an ''n''-dimensional lattice that produces a third function, also of ''n''-dimensions. Multidimensional discrete convolution is the discrete analog of the [[convolution#Domain of definition|multidimensional convolution]] of functions on [[Euclidean space]]. It is also a special case of [[convolution#Convolutions on groups|convolution on groups]] when the [[group (mathematics)|group]] is the group of ''n''-tuples of integers.
==Definition==
Line 68 ⟶ 69:
Convolution in one dimension was a powerful discovery that allowed the input and output of a linear shift-invariant (LSI) system (see [[LTI system theory]]) to be easily compared so long as the impulse response of the filter system was known. This notion carries over to multidimensional convolution as well, as simply knowing the impulse response of a multidimensional filter too allows for a direct comparison to be made between the input and output of a system. This is profound since several of the signals that are transferred in the digital world today are of multiple dimensions including images and videos. Similar to the one-dimensional convolution, the multidimensional convolution allows the computation of the output of an LSI system for a given input signal.
For example, consider an image that is sent over some wireless network subject to electro-optical noise. Possible noise sources include errors in channel transmission, the analog to digital converter, and the [[image sensor]]. Usually noise caused by the channel or sensor creates spatially-independent, high-frequency signal components that translates to arbitrary light and dark spots on the actual image. In order to rid the image data of the high-frequency spectral content, it can be multiplied by the frequency response of a low-pass filter, which based on the convolution theorem, is equivalent to convolving the signal in the time/spatial ___domain by the impulse response of the low-pass filter. Several impulse responses that do so are shown below.<ref>{{Cite web|title = MARBLE: Interactive Vision|url = http://homepages.inf.ed.ac.uk/rbf/CVonline/LOCAL_COPIES/MARBLE/|website = homepages.inf.ed.ac.uk|access-date = 2015-11-12}}</ref>
[[File:Screen Shot 2015-11-11 at 11.18.23 PM.png|none|thumb|311x311px|Impulse Responses of Typical Multidimensional Low Pass Filters]]
In addition to filtering out spectral content, the multidimensional convolution can implement [[edge detection]] and smoothing. This once again is wholly dependent on the values of the impulse response that is used to convolve with the input image. Typical impulse responses for edge detection are illustrated below.
[[File:Screen Shot 2015-11-11 at 11.21.00 PM.png|none|thumb|Typical Impulse Responses for Edge Detection]]
Line 204 ⟶ 205:
# Zero pad the signals <math>h(n_1,n_2)</math> and <math>x(n_1,n_2)</math> such that they are both <math>N_1\times N_2</math> in size
# Compute the DFTs of both <math>h(n_1,n_2)</math> and <math>x(n_1,n_2)</math>
#
# The result of the IDFT of <math>Y(k_1,k_2)</math> will then be equal to the result of performing linear convolution on the two signals
| |||