Image Anal Stereol 2001;20:53-57 Original Research Paper NEW METHOD FOR FAST IMAGE EDGE DETECTION BASED ON SUBBAND DECOMPOSITION Chongyang Hao1, Min Qi2, U. Heute2 and C. Moraga3 1Institute of Electronic & Information Engineering, Northwestern Polytechnical University, Xi’an 710072, China, 2Christian Arbrechts University, 24143 Kiel, Germany, 3University Dortmund, 44221 Dortmund, Germany (Accepted February 14, 2001) ABSTRACT A new method of detection the edges of an image is presented in this article. The method uses a kind of two-dimensional subband spectrum analysis (2D-SSA) filter that is based on subband decomposition, and it is very convenient to get the edge frequency spectrum of an image after certain preprocessing. Comparing with spatial methods, the method is less sensitive to noise. It is also superior to the conventional frequency methods. In conventional frequency methods, the bandwidth and central frequency of filter are fixed, and it needs to transform the whole image into frequency domain. While in this method, the bandwidth and central frequency can be adjusted flexibly, and it only uses a few pixels to implement FFT. So this method is a fast way to extract the edges of an image. The simulation results show its efficiency. Keywords: edge detection, subband decomposition, 2D-SSA filter. INTRODUCTION Edge detection is an indispensable step in the computer vision and object recognition, because the most fundamental characteristic for image recognition is the edges of an image. Traditional edge detection methods in spatial domain are very sensitive to the noise due to using the differential operation. The edges of an image also belong to high frequencies, and they can be extracted by highpass filters. The conventional highpass filter methods have some shortcomings. First, once the design of a filter is finished, the central frequency and bandwidth of the filter cannot be adjusted freely. So it is difficult to cover the edge spectrum of the image optimally. Second, the highpass filter method is feasible only after the whole image is converted into frequency domain by Fourier Transform. It is well known that it needs a large amount of calculation and memory. Subband Spectrum Analysis algorithm presented in this paper is derived from Subband Decomposition DFT(SD-DFT), and it is more flexible and general than SD-DFT. In this paper, the 2D-SSA is extended from the one-dimensional SSA and is successfully applied to the edge detection. Although the 2D-SSA filter method belongs to a kind of metamorphic method in frequency domain, its theory and performance are more advanced than the conventional frequency methods. The central frequency and bandwidth can be changed during decomposition, so it is convenient to adjust the 2D-SSA filter. Especially the 2D-SSA filter does not need to transform the original image into frequency domain directly. Instead, it simply preprocesses the image pixels in spatial domain by the means of frequency movement and arithmetic mean, and then the amount of pixels that are used in DFT and edge detection are reduced largely. This method drastically decreases the calculation of image transform and uses less amount of memory. In short, 2D-SSA filter method is a feasible way to detect and extract the edge of an image. Unlike the traditional spatial methods, it is less sensitive to noise. It is also more advanced than conventional methods in frequency domain, because of avoiding a lot of computing works. So it is explicit in conception and can be easily implemented. TWO DIMENSIONAL SUBBAND DECOMPOSITION DFT The fundamental idea of the SD-DFT is to do the Fourier Transforms of some short sequences to get the whole spectrum of the signal through some arithmetical operations in spatial domain. The whole frequency band is divided into two outputs of subband filters: highpass filter and lowpass filter. x (n) is a sequence of N points (n=0,1,……,N-1, N =2V), its SD-DFT expression is: 53 Hao Cy et al: Fast image edge detection based on subband decomposition N-1 X(k) = z.,x(n) WN = (1 + WN)Gl(k) + (1 -WN)Gh(k) k = 0,1,---, N-1 (1) n=0 Where WN = e j 2k /N Gl (k) andGh (k) are the DFT of the new sequences with the length of N/2 demonstrated in Eq. 2 respectively. 1 gl (n) = —[x(2n) + x(2n +1)] 2 1 [ ] g h (n) = ~ x(2n) - x(2n - 1) n = 0,1,2,'",------1 2 (2) 2 In Eq. 1, (1 + WNk )Gl(k) and (1-WNk)Gh(k) represent the outputs of the lowpass filter and highpass filter, respectively. These two filters are in parallel connection. Their frequency responses have been explained by Hossen (1993) and Mitra (1990a). Eq. 1 means that the spectrum of X(k) is divided into a lower subband and a higher subband. Eq. 2 means the butterfly computation of two adjacent pixels and the sampling with the factor of 2, which produce two subsequences corresponding to the lowpass filter and X(k) ~ (1 + WNk)Gl highpass filter. So from Eq. 1, we can draw a conclusion: the N-point DFTs of the sequence x(n) can be transformed into the computation of two N/2-point DFTs of two subsequences. From Eq. 1, we can obtain multi-order subband decomposition structure, and this is called SD-DFT. Its most important feature, or the most outstanding difference to FFT, is that it can get the desired subband independently. If k< hWn'/ Wn N/2-1 N/2-1 GLH(k,l)= 2_i zLSLH(m'nWN/2^I N/2—1 N/2—1 GHL(k,l)= 2_i z!, Shl (m> hWn'/ Wh =0 H=0 N / 2-1N / 2-1 GHH(k,l)= 2_i z!, Shh (m>nWN/2IVN =0 H=0 THE THEORY OF 2D-SSA a fast partial spectrum analysis method. If the energy of a signal is concentrated in a certain band, or the By improving the 1D SD-DFT, Hossen (1994) frequency spectrum that we are interested in is not in proposes a Subband Spectrum Analysis (SSA) , low frequency band, the Mth SD-DFT can be method. It is based on subband decomposition and is expressed as follows according to SSA theory: M X(k)~Y\(1 + W^2 )Q(k) k = 0,1,2, ,N — 1 (6) i=1 where N/P-1 Q(k)= ^T q(r)W^r/P k =0,1,2, J^f/P-1N/P = 2M (7) 1 - k r q(r) = — elN 0" {jt(Pr) + Jt(Pr+1) + --- + Jt[Pr+(P-1)]} r = 0,1,2, ,N/P-1 (8) Eq. 8 means some preprocessing for the original computation is represented by the multiplication time sequence is done in the spatial domain in order to get approximatively, the amount of computation in the the subsequence q(r) before Fourier Transform and the SSA method is about 2M times less than that of the preprocessing works include frequency movement and FFT If the desirable spectrum is relatively narrow, mathematical mean etc. Q(k) is the approximation of the influence of the noise is very little. X(k) which is the full spectrum of signal x(n). P is the sampling factor. Like FFT, the amount of From 1D-SSA, we can get the 2D-SSA: X(k, I) ~ TT (1 + W^2 )(1 + W^2 ) G(k, I) kJ = 0,1,2, N -1 (9) N/P-1N/P-1 G(kJ)=Jj X g(r,sWΘ/PK/P V = 0,1,2, ,N/P-1 (10) r=0 s=0 g{r,s) = — e " J^x{Pr+u,Ps + v) r,s = 0,1,2, ,N/P-\ (11) r u=0 v=0 here k0 and l0 are the parameters representing the amount of frequency shift in the direction of r and s. 55 Hao Cy et al: Fast image edge detection based on subband decomposition THE EDGE DETECTION BY 2D-SSA FILTER The bandwidth of the edge spectrum of an image is usually very narrow, so it is suitable for using 2D-SSA filter. Generally an image has large amounts of data, and one needs a long time to process it. In the fast recognition of a target image, it is very important to reduce the processing time. All these possibilities and requirements make the 2D-SSA method valuable in fast edge detection. The parameters which are needed to be regulated are M, k0 and l0. M represents the times of decomposition, and it determines the bandwidth and central frequency of 2D-SSA lowpass filter. k0, l0 are the amounts of frequency shift respectively. A group optimum value of M, k0 and l0 can be got through regulating. The larger the parameter M, the narrower the filter’s bandwidth, and more information of the image will be lost. k0 and l0 are determined by the distance between the central frequency of 2D-SSA filter and the location of the edges in frequency domain. Fig. 1 is an original image with 128 128 pixels and 256 gray levels. Through the regulation of 2D-SSA filter, the best output of the image is obtained when M = 1 and k0 = 63, l0 = 63, which is demonstrated in Fig. 2. Fig. 3 is the edge detection result of the image when M = 2. Comparing Fig. 3 with Fig. 2, although the amounts of frequency shift do not change, it is obvious that some edge information of the image in Fig. 3 has been lost. So the result is not good comparing with Fig. 2. Fig. 4 is the result of the edge detection by using the wavelet transformation method. Comparing the 2D-SSA method with the wavelet transformation method, the real-time characteristic of the former is better than that of the latter. In the experiment, the time consumed by 2D-SSA is only 60% of that used by wavelet transformation method. The SSA method is derived from the SD-DFT, and it is an improvement of the SD-DFT. So we can use the error analysis method presented by Mitra (1990b) to calculate the error of the image processing of 2D-SSA. 2D-SSA method is very economical in time consumption, time is reduced by 2MΧ2M. At the same time, the error of this method in image processing is also bearable, and this is verified by the example. Fig.1. The original image. Fig. 2. Edge extraction when M = 1, k0 = 63, l0 = 63. Fig. 3. Edge extraction when M = 2, k0 = 63, l0 = 63. Fig. 4. Edge extraction by wavelet method. 56 Image Anal Stereol 2001;20:53-57 CONCLUSION A kind of 2D-SSA filter and its application in image edge detection are presented in this article. Considering from the aspects of processing speed and sensitivity to noise synthetically, the 2D-SSA method is optimum. Though the article only discusses its application in image edge detection, it can also be applied to image texture extraction and segmentation. REFERENCE Hossen AN, Heute U (1993). Fully Adaptive Evaluation of Subband DFT. Chicago: Proc. of IEEE ISCAS, 655-8. Hossen AN, Heute U (1994). Two-Dimensional Sub-Band DFT Algorithm. NOPRSIG 94:163-7. Mitra SK, Petraglia MR, Shentov OV (1990a). DFT Calculation via Subband Decomposition. Barcelona: Proc. EUSIPCO, 501-4. Mitra SK, Shentov OV, Petraglia MR (1990b). A Method for Fast Approximate Computation of Discrete Time Transforms. Albuquerque, New Mexico: Proc. CASSP, 2025-8. 57