Content deleted Content added
10.1109/tpami.1980.4767017 |
m Journal cites:, |
||
Line 257:
The overlap and save method is very similar to the overlap and add methods with a few notable exceptions. The overlap-add method involves a linear convolution of discrete-time signals, whereas the overlap-save method involves the principle of circular convolution. In addition, the overlap and save method only uses a one-time zero padding of the impulse response, while the overlap-add method involves a zero-padding for every convolution on each input component. Instead of using zero padding to prevent time-___domain aliasing like its overlap-add counterpart, overlap-save simply discards all points of aliasing, and saves the previous data in one block to be copied into the convolution for the next block.
In one dimension, the performance and storage metric differences between the two methods is minimal. However, in the multidimensional convolution case, the overlap-save method is preferred over the overlap-add method in terms of speed and storage abilities.<ref>{{Cite journal|url = |title = High-Speed Multidimensional Convolution|last = Kim|first = Chang|date = May 1980|journal = IEEE Transactions on Pattern Analysis and Machine Intelligence|doi = 10.1109/tpami.1980.4767017 |last2 = Strintzis|first2 = Michael|volume=PAMI-2|pages=269–273}}</ref> Just as in the overlap and add case, the procedure invokes the two-dimensional case but can easily be extended to all multidimensional procedures.
===Breakdown of Procedure===
Line 347:
===Approximation by FIR Filter===
Gaussian convolution can be effectively approximated via implementation of a [[Finite impulse response]] (FIR) filter. The filter will be designed with truncated versions of the Gaussian. For a two-dimensional filter, the transfer function of such a filter would be defined as the following:<ref name=":0">{{cite journal|last1=Getreuer|first1=Pascal|title=A Survey of Gaussian Convolution Algorithms|journal=Image Processing On Line|date=2013|pages=286–310|doi=10.5201/ipol.2013.87|volume=3}}</ref>
<math>H(z_1,z_2)=\frac{1}{s(r_1,r_2)} \sum_{n_1=-r_1}^{r_1}\sum_{n_2=-r_2}^{r_2}G(n_1,n_2){z_1}^{-n_1}{z_2}^{-n_2}</math>
Line 363:
<math>H(z)=\frac{1}{2r+1} \frac{z^r-z^{-r-1}}{1-z^-1}</math>
Typically, recursive passes 3, 4, or 5 times are performed in order to obtain an accurate approximation.<ref name=":0" /> A suggested method for computing ''r'' is then given as the following:<ref>{{Cite journal|title = Efficient synthesis of Gaussian filters by cascaded uniform filters|last = Wells|first = W.M.|date = 1986|journal = IEEE Transactions on Pattern Analysis and Machine Intelligence|doi = 10.1109/TPAMI.1986.4767776|pmid =
<math>\sigma^2=\frac{1}{12}K((2r+1)^2-1)</math> where ''K'' is the number of recursive passes through the filter.
| |||