当前位置：文档库 › 基于广义插值傅里叶方法的先进Radon变换直线检测法英文

基于广义插值傅里叶方法的先进Radon变换直线检测法英文

Advanced Radon transform using generalized interpolated Fourier method for straight line detection

Liying Zheng a ,?,Daming Shi b

a School of Computer Science and Technology,Harbin Engineering University,Harbin,Heilongjiang 150001,China

School of Engineering and Information Sciences,Middlesex University in London,The Burroughs,London NW44BT,UK

a r t i c l e i n f o Article history:

Received 24June 2009

Accepted 16November 2010

Available online 2December 2010

Keywords:

Radon transform

Generalized interpolated Fourier transform Straight line detection

a b s t r a c t

Straight line detection is common in computer vision.The Radon transform has received much attention for its ef?ciency and accuracy compared to the Hough transform.In this paper,a generalized interpolated Fourier transform,hereafter called GIFT,is proposed to speed up the Radon transform.Based on the GIFT,a methodology that can detect straight lines from a gray scale image without any pre-processing is imple-mented.Two contributions can be claimed.First,the recent work by Pan et al.is reinterpreted and imple-mented in a clearer way so the traditional Fourier transform can be interpolated to achieve an accurate sampling in the frequency domain.Second,the interpolated Fourier transform is further generalized with ?exible parameter determination in two dimensions when applied to 2-D images.The experiments dem-onstrate that our proposed methodology outperforms the standard Radon transform with lower compu-tational load and higher accuracy.The experiments also show that the GIFT line detector can compete against the random sample consensus,which is a robust estimator popularly used in the ?eld of com-puter vision.

1.Introduction

Straight line detection of an image is required for many pattern recognition problems,since various natural and man-made objects can typically be identi?ed by their distinct combination of linear features.A number of line detection methods have been described in the literature in the past decades,many of which are based on the standard or variant Hough transforms (HT)[1–9]due to its sta-bility and robustness when applied to images where noise and missing data occur.However,the computational ef?ciency of the HT-based line detectors falls sharply as the image dimensions and/or resolution of the accumulator increase.It is dif?cult to achieve real-time performance with these methods.

The Radon transform (RT)is conceptually the same as the HT but more computationally ef?cient than the HT,so RT-based straight line detectors have received much attention.Deans [10]?rst described how to deduce the HT for ?nding lines in images as a special case of the RT de?ned on 2-D Euclidean space.His work implies the RT is able to transform images with lines into a domain of possible line parameters,where each line in the image will give a peak (bright line)or a valley (dark line)positioned at the corre-sponding line parameters.Subsequently,Murphy proposed an RT-based method for detecting lines in noisy radar images [11].Since then,substantial work has been completed to improve the quality of the RT-based linear feature detectors [12–20].

In most cases,the computational ef?ciency of the RT is achieved based on the projection-slice theorem,in which Cartesian to polar coordinate mapping is a necessary step.Thus,interpolation error in Cartesian to polar coordinate mapping strongly in?uences the ?nal results.Ho et https://www.wendangku.net/doc/e88921661.html,ed a zero padding and cropping technique to de-crease the interpolation error [16,18].According to their method,an input image is padded with zeros increasing the image size from N ?N to (N ?2b )?(N ?2b ),prior to being transformed.Any zero padding is then removed after the stage of 1-D discrete Fourier transform (DFT).Although they have shown this strategy can ef?-ciently eliminate aliasing,it is time consuming.Suppose the size of an image is N ?N ,then the computational complexity of the 2-D DFT required for the fast Fourier transform is O {N 2log(N )}implying that if b is not equal to zero,the computational cost will be dramat-ically increased (a factor of approximately 4b ).In this paper,we propose a generalized interpolated Fourier transform (GIFT)to realize a fast RT.

One point must be highlighted is that we generalize the inter-polated Fourier transform proposed by Pan et al.by adopting dif-ferent scale factors in horizontal and vertical https://www.wendangku.net/doc/e88921661.html,pared with the original uniform parameter for both x -axis and y -axis,the two parameters introduced in this research make the transform more ?exible and practical.In this paper,the term ‘‘interpolated Fourier transform’’is adopted instead of ‘‘multilayer fractional Fourier transform (MLFFT)’’used in the previous papers

?Corresponding author.

E-mail addresses:

heuzhengliying@https://www.wendangku.net/doc/e88921661.html, ,

heuzhengliying@https://www.wendangku.net/doc/e88921661.html, (L.Zheng).

[19,20],since the term of fractional Fourier transform is not quite appropriate and can be confused with the traditional fractional Fourier transform(FrFT)that is intimately related to time–frequency distribution of a signal.However,either the MLFFT in [19]or the GIFT in this paper provides no spatial information but only frequency information when applied to an image.

The remainder of this paper is organized as follows.Section2 gives the technical details of the GIFT.In Section3,the implemen-tation of the proposed GIFT algorithm is clari?ed.The experimental results and analyses are given in Section4,followed by conclusions in Section5.

2.Generalized interpolated Fourier transform(GIFT)

The DFT of{f(n)|n=àN/2,...,0,...N/2à1}is de?ned as

FekT?

N=2à1

n?àN=2

fenTexpeàj2p kn=NTe1T

where exp(á)is the exponential function and j?

???????

à1

.Note that the

N frequencies of F(k)are distributed uniformly in[àp,p].

The following equation can be obtained from Eq.(1),

F aekT?

N=2à1

n?àN=2

fenTexpeàj2p kn a=NTe2T

where0

Based on Eq.(2),Pan et al.[19]proposed the following2-D transform which they called‘‘multilayer fractional Fourier trans-form’’(MLFFT)

F aek1;k2T?

N=2à1

n1?àN=2

N=2à1

n2?àN=2

fen1;n2Texpeàj2pen1a k1tn2a k2T=NTe3T

where f fen1;n2TjàN=26n1;n26N=2à1g is a2-D discrete signal. The N?N frequencies of F aek1;k2Tare scattered in ?àa p;a p ??àa p;a p .

It is easy to prove that

F aek1;k2T?Fea k1;a k2T;for0

Further,we noticed that the distribution of the interpolation grid obtained by Eq.(3)is limited due to the uniform scale factors of x-axis and y-axis.For example,if k1={à2,à1,0,1,2}and k2={à2,à1,0,1,2},then the frequency at(0.2,0.3)cannot be computed directly.According to Eq.(4),one can select a?f0:2;0:3g or some other values and perform two transforms to get frequencies at(0.2,0.2)and(0.3,0.3),and then compute the frequency at(0.2,0.3)with some interpolation method,such as nearest interpolation or bilinear interpolation.

To address the above problem,we propose the following gener-alized interpolated Fourier transform(GIFT):

F a1;a2ek1;k2T?

N=2à1

n1?àN=2

N=2à1

n2?àN=2

fen1;n2Texpeàj2pen1a1k1tn2a2k2T=NT

e5T

where0

Similar to the MLFFT,the resolution of the grid of the GIFT de-pends on two parameters:the number of approaching layers,L, and the approximating set,Cut,which is de?ned as:

Cut?fea1i;a2iTj i?1;...L;0

e6TThe interpolation grid on the frequency domain is de?ned as

t?1

P ie7TP i?fea i1k1;a i2k2TjàN=26k1;k26N=2à1;ea i1;a i2T2Cute8T

Since the GIFT has two adjustable parameters a1and a2besides L,it is more?exible than MLFFT.Fig.1illustrates how a three-layer interpolated grid is constructed through a3-layer GIFT.

The GIFT described above has the following important properties.

(1)When a1i=a2i for i=1,2,...L,it is degraded to the original

MLFFT.

(2)When a1=a2=1,it is equivalent to the traditional2-D DFT.

(3)When0

N?N frequencies that are scatted uniformly in ?àa1p;a1p ??àa2p;a2p in the frequency domain.

(4)For0

According to properties(3)and(4)as well as Eqs.(7)and(8), combining the GIFT with different a1and a2results in a high-resolution grid(see Fig.1).Property(4)means that one can compute the frequencies of any coordinate grid.Thus,with some special steps,an accurate Fourier spectrum can be obtained.

3.Straight line detection based on the GIFT

3.1.Projection-slice theorem

The RT of a2-D function f(x,y)is de?ned as the integral projec-tion of the function onto an axis,making angle h with the x-axis [10]:

keq;hT?RDN h?fex;yT eqT

feq cos hày0sin h;q sin hty0cos hTdy0

Z Z

fex;yTdeqàx cos hày sin hTdxdye9T

L.Zheng,D.Shi/Computer Vision and Image Understanding115(2011)152–160153

where RDN is the Radon operator and d (á)is the 1-D Dirac delta function.To obtain the full transformation,it is understood that h and q vary so that k is determined for arbitrary values of h and q .Let SLC h be the operator of the slice of 2-D function f (x ,y )at an-gle h through the relationship

SLC h ?f ex ;y T ex 0T?f ex 0cos h ;x 0sin h T

e10T

Then we have

RDN h ?f ex ;y T eq Texp eàj 2p q v Td q ?Z Z Z f ex ;y Td eq àx cos h ày sin h T

?exp eàj 2p q m Td q dxdy

?Z Z

f ex ;y TZ d eq àx cos h ày sin h Texp eàj 2p q v Td q dxdy ?Z Z f ex ;y TTexp ?àj 2p ex v cos h ty v sin h T dxdy

?SLC h

Z Z f ex ;y TTexp ?àj 2p ex v ty v T dxdy

ev Te11T

Let F 1and F 2be 1-D and 2-D Fourier operators,respectively,then Eq.(11)can be rewritten as

F 1RDN h ?f ex ;y T f gev T?SLC h F 2?f ex ;y T el ;g Tf gev T

e12T

Eq.(12)is the projection-slice theorem:The 1-D Fourier transform of the integral projection at angle h is equal to the slice of the 2-D Fourier transform at the same angle.In order to compute the RT,it is therefore necessary to perform the following three steps [11]:(1)Compute the 2-D Fourier transform of f (x ,y ).

(2)Interpolate the 2-D Fourier transform to obtain a set of func-tions f K ev ;h T?F 1?k eq ;h T g ,each de?ned in the frequency domain along a radial line orientated at an angle h .

(3)Compute the inverse Fourier transform of each function

K (v ,h )along v ,resulting in a set of projection functions k (q ,h )that together constitute the RT of the image.Based on the above three steps,Ho et al.described the details of implementing straight line detection by using the RT [16].They adopted a strategy of zero padding and cropping to solve the prob-lem of interpolation error.Accordingly,the input image is ?rst pad-ded with zeros to avoid aliasing effects;then a Cartesian to polar coordinate transformation is carried out to get the 1-D Fourier transformation of k eq ;h T.After that,a 1-D ?ltering is performed to enhance the edges and to improve the peak structure in the sinogram.The resampled data are then conjugate mirrored before a 1-D inverse DFT of the ?ltered and resampled 1-D Fourier spectrum is obtained.Any zero padding is then removed and the maxima in the Radon space are located from the cropped data.Finally straight lines corresponding to the maxima are detected.One advantage of the RT-based line detector over the conceptu-ally similar HT approach is the increase in computational ef?ciency that it affords.Another one is that some image enhancement operations can be easily completed in the Fourier domain prior to the 1-D inverse Fourier transform of K ev ;h T.As mentioned,how-ever,the procedures of zero padding and cropping result in a huge increase in computing time,so it is necessary to adopt a substitute technique to further accelerate the RT-based straight line detector.3.2.GIFT algorithm for straight line detection

Fig.2summarizes the major stages required for the GIFT-based straight line detector.The original input image is a gray scale im-age.A 2-D accurate Fourier spectrum of size s 0?r 0(s 0and r 0are

related to the approximating set Cut )is obtained by applying an

L -layer GIFT to the input image.Note that the zero padding opera-tion is omitted.The top half of the 2-D accurate Fourier spectrum is then converted from a Cartesian x –y grid to a polar v –h grid of size m ?n (here,we assume m =0.5r )by computing the location of each v –h pixel on the Cartesian grid at ex ?v cos h ;y ?v sin h Tand interpolating from surrounding pixels.

Obviously,for the application of straight line detection,the pre-cision of the interpolation in high frequencies is more important than in other frequencies,because the edges are more important than other parts.Thus at the stages of GIFT and Cartesian to polar mapping,the following steps are employed:

(1)Set the adjustable parameters L and Cut of GIFT.Since high

frequencies are more important,we assume

Cut ?fea 1i ;a 2i Tj 0:5

(2)Perform the L -layer GIFT to get an accurate Fourier

spectrum.

(3)Let h ={h ,D h ,2D h ,...,p },D h =p /(n à1),where n must be

high to ensure optimum pixel coverage.(4)Let v ?0;D v ;2D v ;...?????????r 2ts

2p 2

.(5)Use an interpolation scheme,such as nearest or bilinear

interpolation,to compute the frequency at position (x =v cos h ,y =v sin h ).After above ?ve steps,m ?n resampled Fourier spectrum K (v ,h )is obtained.Next,a 1-D ?ltering is performed to enhance the edges.Here,the 1-D difference of Gaussian (DOG)?lter given in Eq.(13)is adopted,since it is both an edge detector and a peak structure enhancer [16].

K h ev ;h T?exp eàv 2=d 2

e Tàexp eàv 2=d 2