Two dimensional window design
Windowing is a process where an index limited sequence has its maximum energy concentrated in a finite frequency interval. This can be extended to an N-dimension where the N-D window has the limited support and maximum concentration of energy in a separable or non-separable N-D passband. The design of an N-dimensional window particularly a 2-D window finds applications in various fields such as spectral estimation of multidimensional signals, design of circularly symmetric and quadrantally symmetric non-recursive 2D filters,[1] design of optimal convolution functions, image enhancement so as to reduce the effects of data-dependent processing artifacts, optical apodization and antenna array design.[2]
Two dimensional window
Due to the various applications of multi-dimensional signal processing, the various design methodologies of 2-D windows is of critical importance in order to facilitate these applications mentioned above, respectively.
Consider a two-dimensional window function (or window array) [math]\displaystyle{ w(n_1,n_2) }[/math] with its Fourier transform denoted by [math]\displaystyle{ W(w_1,w_2) }[/math]. Let [math]\displaystyle{ i(n_1,n_2) }[/math] and [math]\displaystyle{ I(w_1,w_2) }[/math] denote the impulse and frequency response of an ideal filter and [math]\displaystyle{ h(n_1,n_2) }[/math] and [math]\displaystyle{ H(w_1,w_2) }[/math] denote the impulse and frequency response of a filter approximating the ideal filter, then we can approximate [math]\displaystyle{ I(w_1,w_2) }[/math] by [math]\displaystyle{ h(n_1,n_2) }[/math]. Since [math]\displaystyle{ i(n_1,n_2) }[/math] has an infinite extent it can be approximated as a finite impulse response by multiplying with a window function as shown below
[math]\displaystyle{ h(n_1,n_2) = i(n_1,n_2)w(n_1,n_2) }[/math]
and in the Fourier domain
[math]\displaystyle{ H(w_1,w_2) = \frac{1}{(2\pi)^2}[I(w_1,w_2)**W(w_1,w_2)] }[/math][2]
The problem is to choose a window function with an appropriate shape such that [math]\displaystyle{ H(w_1,w_2) }[/math] is close to [math]\displaystyle{ I(w_1,w_2) }[/math] and in any region surrounding a discontinuity of [math]\displaystyle{ I(w_1,w_2) }[/math], [math]\displaystyle{ H(w_1,w_2) }[/math] shouldn't contain excessive ripples due to the windowing.
2-D window function from 1-D function
There are four approaches for generating 2-D windows using a one-dimensional window as a prototype.[3]
Approach I
One of the methods of deriving the 2-D window is from the outer product of two 1-D windows, i.e., [math]\displaystyle{ w(n_1,n_2) = w_1(n_1)w_2(n_2). }[/math] The property of separability is exploited in this approach. The window formed has a square region of support and is separable in the two variables. In order to understand this approach,[4] consider 1-D Kaiser window whose window function is given by
[math]\displaystyle{ w[n] = \left\{ \begin{matrix} \frac{I_0\left(\pi \alpha \sqrt{1 - \left(\frac{2n}{N-1}-1\right)^2}\right)} {I_0(\pi \alpha)}, & 0 \leq n \leq N-1 \\ \\ 0 & \mbox{otherwise} \\ \end{matrix} \right. }[/math]
then the corresponding 2-D function is given by
- [math]\displaystyle{ w(n_1,n_2) = \left\{ \begin{matrix} \frac{I_0\left(\alpha \sqrt{1-(\frac{n_1}{a})^2}\right)I_0\left(\alpha \sqrt{1-(\frac{n_2}{a})^2}\right)}{I_0^2(\alpha)}, & |n_1| \leqslant a, |n_2| \leqslant a \\ 0 & \mbox{otherwise} \\ \end{matrix} \right. }[/math]
where:
- [math]\displaystyle{ r = \sqrt{n_1^2+n_2^2} }[/math]
- N is the length of the 1-D sequence,
- I0 is the zeroth-order modified Bessel function of the first kind,
- α is an arbitrary, non-negative real number that determines the shape of the window. In the frequency domain, it determines the trade-off between main-lobe width and side lobe level, which is a central decision in window design.
The Fourier transform of [math]\displaystyle{ w(n_1,n_2) }[/math] is the outer product of the Fourier transforms of [math]\displaystyle{ w_1(n_1)\ and \ w_2(n_2) }[/math]. Hence [math]\displaystyle{ W(w_1,w_2) = W_1(w_1)W_2(w_2) }[/math].[5]
Approach II
Another method of extending the 1-D window design to a 2-D design is by sampling a circularly rotated 1-D continuous window function.[2] A function is said to possess circular symmetry if it can be written as a function of its radius, independent of [math]\displaystyle{ \theta }[/math] i.e. [math]\displaystyle{ f(r,\theta) = f(r). }[/math]
If w(n) denotes a good 1-D even symmetric window then the corresponding 2-D window function[2] is
[math]\displaystyle{ w(n_1,n_2) = w(\sqrt{n_1^2+n_2^2}) }[/math] for [math]\displaystyle{ |\sqrt{n_1^2+n_2^2}| \leqslant a }[/math] (where [math]\displaystyle{ a }[/math] is a constant)
and
[math]\displaystyle{ w(n_1,n_2) = 0 }[/math] for [math]\displaystyle{ |\sqrt{n_1^2+n_2^2}| \gt a }[/math]
The transformation of the Fourier transform of the window function in rectangular co-ordinates to polar co-ordinates results in a Fourier-Bessel transform expression which is called as Hankel transform. Hence the Hankel transform is used to compute the Fourier transform of the 2-D window functions.
If this approach is used to find the 2-D window from the 1-D window function then their Fourier transforms have the relation
[math]\displaystyle{ \frac{1}{2\pi}H(w_1,w_2)**W(w_1,w_2) =H(w)*W(w) }[/math][2]
where:
[math]\displaystyle{ H(w) = \left\{ \begin{matrix} 1, & w\geq0 \\ 0, & w\lt 0 \\ \end{matrix} \right. }[/math] is a 1-D step function
and
[math]\displaystyle{ H(w_1,w_2) =
\left\{
\begin{matrix}
1,
& w_1\geq0\ and\ all\ w_2\\
0, & w_1\lt 0\ and \ all\ w_2 \\
\end{matrix}
\right. }[/math] is a 2-D step function.
In order to calculate the percentage of mainlobe constituted by the sidelobe, the volume under the sidelobes is calculated unlike in 1-D where the area under the sidelobes is used.
In order to understand this approach, consider 1-D Kaiser window then the corresponding 2-D function can be derived as
[math]\displaystyle{ w(n_1,n_2)=\left\{ \begin{matrix} \frac{I_0\left(\alpha \sqrt{1-\frac{\sqrt{n_1^2+n_2^2}}{a^2}}\right)}{I_0(\alpha)}, & |r| \leqslant a \\ 0 & \mbox{otherwise} \\ \end{matrix} \right. }[/math]
This is the most widely used approach to design the 2-D windows.
2-D filter design by windowing using window formulations obtained from the above two approaches will result in the same filter order. This results in an advantage for the second approach since its circular region of support has fewer non-zero samples than the square region of support obtained from the first approach which in turn results in computational savings due to reduced number of coefficients of the 2-D filter. But the disadvantage of this approach is that the frequency characteristics of the 1-D window are not well preserved in 2-D cases by this rotation method.[3] It was also found that the mainlobe width and sidelobe level of the 2-D windows are not as well behaved and predictable as their 1-D prototypes.[4] While designing a 2-D window there are two features that have to be considered for the rotation. Firstly, the 1-D window is only defined for integer values of [math]\displaystyle{ n }[/math] but [math]\displaystyle{ \sqrt{n_1^2+n_2^2} }[/math] value isn't an integer in general. To overcome this, the method of interpolation can be used to define values for [math]\displaystyle{ w(n_1,n_2) }[/math] for any arbitrary [math]\displaystyle{ w(\sqrt{n_1^2+n_2^2}). }[/math] Secondly, the 2-D FFT must be applicable to the 2-D window.
Approach III
Another approach is to obtain 2-D windows by rotating the frequency response of a 1-D window in Fourier space followed by the inverse Fourier transform.[6] In approach II, the spatial-domain signal is rotated whereas in this approach the 1-D window is rotated in a different domain (e.g., frequency-signal).
Thus the Fourier transform of the 2-D window function is given by
[math]\displaystyle{ W_2(w_1,w_2) = W_1(\sqrt{(w_1^2+w_2^2)}) }[/math].
The 2-D window function [math]\displaystyle{ w_2(n_1,n_2) }[/math] can be obtained by computing the inverse inverse Fourier transform of [math]\displaystyle{ W_2(w_1,w_2) }[/math].
Another way to show the type-preserving rotation is when the relation [math]\displaystyle{ W_1(w_1) = W_2(w_1,w_2)\ at\ w_2 = 0 }[/math] is satisfied. This implies that a slice of the frequency response of 2-D window is equal to that of the 1-D window where the orientation of [math]\displaystyle{ (w_1,w_2) }[/math] is arbitrary. In spatial domain, this relation is given by [math]\displaystyle{ w_1(n) = \int_{-\infty}^\infty \!w_2(n_1,n_2)\,dn_2 }[/math]. This implies that a slice of the frequency response [math]\displaystyle{ W_2(w_1,w_2) }[/math] is the same as the Fourier transform of the one-directional integration of the 2-D window [math]\displaystyle{ w_2(n_1,n_2) }[/math].
The advantage of this approach is that the individual features of 1-D window response [math]\displaystyle{ W_1(w_1) }[/math] are well preserved in the obtained 2-D window response [math]\displaystyle{ W_2(w_1,w_2) }[/math]. Also, the circular symmetry is improved considerably in a discrete system. The drawback is that it's computationally inefficient due to the requirement of 2-D inverse Fourier transform and hence less useful in practice.[3]
Approach IV
A new method was proposed to design a 2-D window by applying the McClellan transformation to a 1-D window.[7] Each coefficient of the resulting 2-D window is the linear combination of coefficients of the corresponding 1-D window with integer or power of 2 weighting.
Consider a case of even length, then the frequency response of the 1-D window of length N can be written as
[math]\displaystyle{ W_1(w) = \sum_{n=1}^{N/2} w(n)cos[(n-0.5)w] }[/math] .
Consider the McClellan transformation:
[math]\displaystyle{ cos(w) = 0.5cos(w_1) + 0.5cos(w_2) + 0.5cos(w_1)cos(w_2)-0.5 }[/math]
which is equivalent to
[math]\displaystyle{ cos(0.5w)=cos(0.5w_1)cos(0.5w_2) }[/math] for [math]\displaystyle{ 0\leq\ w\leq\pi,0\leq\ w_1\leq\pi,0\leq\ w_2\leq\pi. }[/math]
Substituting the above, we get the frequency response of the corresponding 2-D window
[math]\displaystyle{ W_2(w_1,w_2) = \sum_{n_1=1}^{N/2}\sum_{n_2=1}^{N/2}w_2(n_1,n_2)cos[(n_1-0.5)w_1]cos[(n_2-0.5)w_2] }[/math] .
From the above equation, the coefficients of the 2-D window can be obtained.
To illustrate this approach, consider the Tseng window. The 1-D Tseng window of [math]\displaystyle{ 2N }[/math] weights can be written as
[math]\displaystyle{ W(w)= exp(-jw/2)\sum_{n=1}^N2w_ncos((n-\frac{1}{2})w) }[/math].
By implementing this approach, the frequency response of the 2-D McClellan-transformed Tseng window is given by
[math]\displaystyle{ W(w_1,w_2)= exp(-j(w_1+w_2)/2)\sum_{n_1=1}^N\sum_{n_2=1}^N4w(n_1,n_2)cos((n_1-\frac{1}{2})w_1)cos((n_2-\frac{1}{2})w_2) }[/math]
where [math]\displaystyle{ w(n_1,n_2) }[/math] are the 2-D Tseng window coefficients.
This window finds applications in antenna array design for the detection of AM signals.[8]
The advantages include simple and efficient design, nearly circularly symmetric frequency response of the 2-D window, preserving of the 1-D window prototype features. However, when this approach is used for FIR filter design it was observed that the 2-D filters designed were not as good as those originally proposed by McClellan.
2-D window functions
Using the above approaches, the 2-D window functions for few of the 1-D windows are as shown below. When Hankel transform is used to find the frequency response of the window function, it is difficult to represent it in a closed form. Except for rectangular window and Bartlett window, the other window functions are represented in their original integral form. The two dimensional window function is represented as [math]\displaystyle{ w(r) }[/math] with a region of support given by [math]\displaystyle{ |r| \lt a }[/math] where the window is set to unity at origin and [math]\displaystyle{ w(r) = 0 }[/math] for [math]\displaystyle{ |r| \gt a. }[/math] Using the Hankel transform, the frequency response of the window function is given by:
[math]\displaystyle{ W(f) = \int_0^\infty \!r w(r) J_0(fr)\,dr }[/math].[9]
where [math]\displaystyle{ J_0 }[/math] is Bessel function identity.
Rectangular window
The two dimensional version of a circularly symmetric rectangular window is as given below[9]
- [math]\displaystyle{ w(r) = \left\{ \begin{array}{ll} 1, & |r| \leqslant a \\ 0, & |r| \gt a \\ \end{array} \right. }[/math]
The window is cylindrical with the height equal to one and the base equal to 2a. The vertical cross-section of this window is a 1-D rectangular window.
The frequency response of the window after substituting the window function as defined above, using the Hankel transform, is as shown below
[math]\displaystyle{ W(f) = \int_0^\infty \!r J_0(fr)\,dr }[/math]
Bartlett window
The two dimensional mathematical representation of a Bartlett window is as shown below[9]
- [math]\displaystyle{ w(r) = \left\{ \begin{array}{ll} 1 -\frac{|r|}{a}, & |r| \leqslant a \\ 0, & |r| \gt a \\ \end{array} \right. }[/math]
The window is cone-shaped with its height equal to 1 and the base is a circle with its radius 2a. The vertical cross-section of this window is a 1-D triangle window.
The Fourier transform of the window using the Hankel transform is as shown below
[math]\displaystyle{ W(f) = \int_0^\infty \!r(1 -\frac{|r|}{a})J_0(fr)\,dr }[/math]
Kaiser window
The 2-D Kaiser window is represented by[9]
- [math]\displaystyle{ w(r) = \left\{ \begin{array}{ll} \frac{I_0\left(\alpha \sqrt{1-((\frac{r}{a})^2}\right)}{I_0(\alpha)}, & |r| \leqslant a \\ 0, & \mbox{otherwise} \\ \end{array} \right. }[/math]
The cross-section of the 2-D window gives the response of a 1-D Kaiser Window function.
The Fourier transform of the window using the Hankel transform is as shown below
[math]\displaystyle{ W(f) = \int_0^\infty \!r (\frac{I_0\left(\alpha \sqrt{1-((\frac{r}{a})^2}\right)}{I_0(\alpha)})J_0(fr)\,dr }[/math]
References
- ↑ Antoniou, A.; Lu, W.-S. (August 1990). "Design of 2-D nonrecursive filters using the window method". IEE Proceedings G - Circuits, Devices and Systems 137 (4): 247–250. doi:10.1049/ip-g-2.1990.0038. ISSN 0956-3768.
- ↑ 2.0 2.1 2.2 2.3 2.4 Huang, T. (March 1972). "Two-dimensional windows". IEEE Transactions on Audio and Electroacoustics 20 (1): 88–89. doi:10.1109/TAU.1972.1162331. ISSN 0018-9278.
- ↑ 3.0 3.1 3.2 PEI, SOO-CHANG; JAW, SY-BEEN (Sep 1987). "A Novel 2-D Window for Spectral Estimation". IEEE Transactions on Circuits and Systems 34 (9): 1112–1115. doi:10.1109/TCS.1987.1086250. ISSN 0098-4094. Bibcode: 1987ITCS...34.1112P.
- ↑ 4.0 4.1 Speake, Theresa C.; Mersereau, Russell M. (Feb 1981). "A Note on the Use of Windows for Two-Dimensional FIR Filter Design". IEEE Transactions on Acoustics, Speech, and Signal Processing 29 (1): 125–127. doi:10.1109/TASSP.1981.1163515. ISSN 0096-3518.
- ↑ Dudgeon, D. E.; Mersereau, R. M. (1984). Multidimensional Digital Signal Processing. Englewood Cliffs, NJ: Prentice-Hall.
- ↑ Kato, Haruo; Furukawa, Tomozo (Aug 1981). "Two-Dimensional Type-Preserving Circular Windows". IEEE Transactions on Acoustics, Speech, and Signal Processing 29 (4): 926–928. doi:10.1109/TASSP.1981.1163655. ISSN 0096-3518.
- ↑ Yu, Tian-Hu; Mitra, Sanjit K. (Aug 1985). "A New Two-Dimensional Window". IEEE Transactions on Acoustics, Speech, and Signal Processing 33 (4): 1058–1061. doi:10.1109/TASSP.1985.1164668. ISSN 0096-3518.
- ↑ Choi, S.; Sarkar, T.K. (June 1989). "Design of 2-D Tseng window and its application to antenna array synthesis". Antennas and Propagation Society International Symposium, 1989. AP-S. Digest: 1638–1641. doi:10.1109/APS.1989.135042.
- ↑ 9.0 9.1 9.2 9.3 Wulang, Widada (December 1979). TWO DIMENSIONAL WINDOW FUNCTIONS (Master's thesis). Naval Postgraduate School, Monterey, CA. hdl:10945/18901.
 |
