a_fast_hough_transform_for_the_parametri sation_of_ (856994), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

The central slice theorem can berepresented in operator notation byF2 ˆ F1 R2…11†Thus if we take the 2D DFT of the image function f …r†,perform a rectangular to polar coordinate transformation and then take the 1D DFT of the resampled 1DFourier ®eld, we obtain the desired projection, l…; †.Application of the Radon transformDDTherefore by comparing Eqns (8) and (9) we can seethat:…9†Figure 4 shows the processes used to generate the Radontransform of a 2D grayscale image f …r† using FourierFigure 3. Central slice theorem: the 1D Fourier transform of a Radon projection at angle is equivalent to the 2D Fouriertransform of the function evaluated along a radial line at angle in the Fourier space.A FAST HOUGH TRANSFORM FOR THE PARAMETRISATION OF STRAIGHT LINES USING FOURIER METHODS117Figure 4. Block diagram of the processing stages in the Fourier evaluation of the Radon transform to produce a peak enhanced®ltered sinogram from a grayscale image f …r†.methods.

To take advantage of the computationalsavings of the fast Fourier transform, powers of 2 wereused wherever possible.sampled to a m n grid, where is m and n are thenumber of radial and angular samples. The missing datacan be obtained by conjugate re¯ection of the resampleddata about the zeroth frequency (Figure 5).To avoid aliasing e€ects, which arise from the x-y to- mapping, the image was padded with zeros, prior tobeing transformed, to increase its size by a factor of4b …b ˆ 0; 1; 2; . .

.† from u v to u…2b † v…2b †. Thisimproves the resolution of its 2D Fourier spectrum,and reduces the sampling increments Px and Py 2b .However this results in an increase in the number ofcomputations, and thus increases the computing timerequired.The 2D Fourier spectrum can be ®ltered toedge enhance or smooth the image. However, since onlythe top half of the Fourier spectrum is sampled, it is notnecessary to apply a 2D ®lter to the 2D Fourierspectrum.

Instead the 1D Fourier spectrum can be®ltered in one operation to both edge enhance andimprove the peak structure of the sinogram. This can bedone before the resampled data is conjugate mirrored.Since the original image is real its 2D Fourierspectrum is symmetric about its origin (diametricHermitian symmetry) and it is therefore only necessaryto sample the top half of the Fourier spectrum. This isTo produce the sinogram, a 1D DFT of the ®lteredand resampled 1D Fourier spectrum is taken along m.Any zero padding is then removed by cropping theimage from size n 2m to produce a n 2u sinogram.Figure 5. Graphical representation of the main processing stages in the Fourier evaluation of the Radon transform to transform animage in Cartesian space (a) to a sinogram in Radon space (d).

Due the diametric Hermitian symmetry of the 2D Fourier spectrum(b), the resampled 1D Fourier spectrum (c) can be obtained by sampling the top half of the 2D Fourier spectrum and mirroring theresampled data by conjugate re¯ection about the zeroth frequency.118C.W. HO ETAL.Figure 6. x-y to - mapping sensor geometry. The top half of the 2D Fourier spectrum (a) of the function is resampled to an m ngrid (b) using the sensor geometry shown. m and n are the number of radial and angular samples and are related to by Eqns(12) and (13).

The sampling density of the x-y to - mapping gets denser as the mapping approaches the centre of the Fourierspectrum. Therefore, at high frequencies, the data samples are further apart and so n has to be suciently high to ensure adequatecoverage in these regions and so prevent high frequency distortion of the image.This is then thresholded to locate the maxima in Radonspace.x-y to n-f mappingThe 2D Fourier spectrum is reordered from a Cartesianx-y grid to a polar - grid of size m n.

This isachieved by computing the location of the each - pixelon the Cartesian grid at p ˆ ^n and interpolating thesurrounding pixels. We found that a combination ofbilinear interpolation of the four nearest neighbors andzero supplementation of the data produced very goodresults. Figure 6 shows the sensor geometry used.The n angular samples span a range from 0 to .Therefore,…12† ˆnÿ1n has to be suciently high to ensure optimum pixelcoverage. It is not necessary for n to be a power of 2since n 1D DFTs of length 2m are taken along m toproduce the sinogram. The radial sampling increment is de®ned as:q p2 ˆ P2x ‡ P2y ˆ b2…13†where Px ˆ Py ˆ 1=2b are the sampling incrementsin the 2D Fourier space.

Enlarging the input image by afactor, b, with zero data causes the Fourier ®eld to beenlarged and to decrease, leading to a more accuratesinogram. This also removes any interperiod artefactspresent. can be further decreased by a factor of2k …k ˆ 0; 1; 2; . . .† to =2k to ensure optimum pixelcoverage for di€erent interpolation methods. Thus them radial samples span a range from =2k to R.Therefore,mˆRˆ …u=2† 2…b‡k†=2k…14†pwhere R ˆ max ˆ …u=2† 2 is de®ned as the ®eld ofview that the mapping covers. A circular visual®eld which totally encloses the 2D Fourier spectrumwas chosen so that the data sampled would not betruncated.

Any pixels outside the Cartesian grid were setto zero.pR ˆp…u=2†2, the sinogram will be expanded bypSince2 to 2R 2 n i.e. 2u n. Due to the Fouriersimilarity theorem an expansion in the spatial domainresults in a contraction in the corresponding FourierA FAST HOUGH TRANSFORM FOR THE PARAMETRISATION OF STRAIGHT LINES USING FOURIER METHODSlength of the line in the Cartesian space and theparameters (n, b, k).domain:ZF1 ‰ f …ax†Š F…a!† ˆ1ÿ1f …ax†eÿj2!x dxZ 11f …ax†eÿj2…ax†…!=a† d…ax†ˆjaj ÿ11 !…15†ˆ Fjaj awherea ˆ R=m ˆˆ 1=2b‡k119p b‡k2=2pfor R ˆ …u=2† 2for R ˆ u=2Therefore if 2b‡k > 1; a51 and so the sinogrampproduced in Radon space will be expanded by 2b‡k 2and will need to be cropped to 2u n if m > u: m isdependent on the size of the image and the parameters band k. However, if b and k are both zero, a > 1 and sothe sinogram produced will be of size u n and will betruncated in the Radon space.

Thus and can becalculated by the number of angular samples, n, thespatial enlargement factor, b, and the radial samplingenlargement factor, k.The sampling process is critical in producing accurateresults. The x-y to - mapping has a sampling densityin Cartesian space that gets denser as the mappingapproaches the centre of the 2D Fourier spectrum.Towards the origin, there will be a dense collection ofsamples and interpolation errors will be small.

At theedges the samples are relatively far apart and interpolation errors will be large if n is not suciently high toensure optimum pixel coverage for the interpolationmethod used. This will result in distortion of edges andother high frequency spatial components.ResultsIn this section we will examine the e€ect of theparameters …n; b; k† on the sinogram. Figure 7 showsthe Radon transform of a single straight line segmentorientated at 458 from the center of the image withparameters …n; b; k†=(256, 0, 1). Each point on the linemaps to a sinusoid in Radon space, which intersect at apoint corresponding to the parametrisation of the line.Due to the Fourier similaritytheorem this maximumppoint lies at a distance 2 greater than the parametrisation distance r in Cartesian space.

The sinusoids in thesinogram exhibits a butter¯y dispersion around themaxima points, whose distribution is determined by theThe length of the resampled 1D Fourier spectrum, m,along which the n 1D DFTs are taken, is dependent onthe values of b and k and the size of the original image.Figure 8 shows the e€ect of decreasing the radialsampling increment by 2k from to =2k . With noFourier enlargement …b ˆ 0† aliasing e€ects occur fromthe high contrast pixels near the side of the image, whichcause shadows to appear near the opposite side of thesinogram. The sinogram produced when b and k areboth zero, [Figure 8(b)], is truncated since m ˆ u=2.Increasing k results in a decrease in =2k and producesa more accurate sinogram with slightly less aliasinge€ects. However, this increases m by 2k and increases thecomputation time required.

If m > u the sinogram willhave to be cropped to 2u n to remove any zeropadding. Increasing k beyond 2 does not yield anysigni®cant improvement and results in oversampling ofthe data present in the Fourier domain. This can beincreased by increasing the amount of zero padding ofthe input image in order to reduce the Fourier domainsampling increments, Px and Py .Figure 9 shows sinograms of the image in Figure 8(a),with di€erent spatial enlargement factors, b. Thealiasing e€ects and interperiod artefacts in the sinogramare reduced with b ˆ 1.

Higher values of b result in agreater improvement in the sinogram, but result in anincrease in the size of the Fourier ®eld and in thecomputing time required. We found that values of b ˆ 1and k ˆ 1 gave the best results with minimal increase incomputation time. The number of radial samples, n, hasto be suciently high so as to ensure that enough data isstored in the sinogram for proper reconstruction. Also,since the sampling density of the x-y to - mappinggets less dense as the mapping approaches the edges ofthe Fourier spectrum, n has to be suciently high toensure sucient coverage in these regions, so that highfrequency components of the input image are notdistorted where the data samples are further apart.Accuracy can be further improved using higher orderinterpolation functions, such as cubic splines, whichinvolve more than the immediate neighbors of theFourier spectrum to be interpolated.

However, we foundthat a bilinear interpolation of the four nearestneighbors produced accurate results with minimalcomputational overhead. Accuracy can further beimproved by bandlimiting the projections prior to, orafter, interpolation. This can be incorporated into the120C.W. HO ETAL.Figure 7.

Характеристики

Список файлов книги