a_fast_hough_transform_for_the_parametri sation_of_ (856994), страница 4
Текст из файла (страница 4)
A ®lter with (de ; di )=(200, 125) has the eectof edge detecting the image and enhancing the structuresin the resulting sinogram. This gives a sharper sinogramthan the one corresponding to (de ; di )=(120, 75). However the edges of the image have also been detectedcausing four spurious maxima points. These have to betaken into account when detecting the peaks in thesinogram.Figure 15 shows the un®ltered (g) and ®ltered (h)sinograms of an 8-bit grayscale image (a), and theun®ltered sinogram (i) obtained from its edge enhancedimage (c). Parameters are (n; b; k)=(512, 1, 1) and(de ; di )=(400, 250) for m=512. Bandpass ®ltering the1D Fourier spectrum of the image (e) has the eect ofdetecting its edges and enhancing the peak structures inthe ®ltered sinogram.
As with the previous example, the126C.W. HO ETAL.Figure 15. Comparison of un®ltered (g) and ®ltered (h) sinograms of a real 8-bit grayscale image (a), with the un®ltered sinogram(i) obtained from the edge enhanced image (c). Parameters are n; b; k=(512, 1, 1) and de ; di =(400, 250) for m=512. Thereconstructed image (b) was obtained by reconstructing the ®ltered sinogram (h) using the inverse Radon transform.edges of the image have also been detected in the ®lteredsinogram. These eects can be seen by comparing theedge detected image (c) and its un®ltered sinogram, withthe reconstructed image (b), which was obtained byreconstructing its sinogram using the inverse Radontransform.ConclusionIn this paper, we have outlined a fast and ecientmethod for the computation of the Hough transform.This was achieved by computing the Hough transformvia the central slice theorem, so that the algorithmbecomes a 2D DFT, an x-y to r- mapping and a 1DDFT.
This can be eciently realized using the fastFourier transform implemented in DSP hardware.By zero supplementing the input function prior totransformation, the 2D Fourier space can be enlarged,reducing the aliasing errors in the sinogram. Due to thediametric Hermitian symmetry of the 2D Fourierspectrum it is only necessary to sample the top half ofthe 2D Fourier spectrum. The missing data can beobtained by conjugate re¯ection to produce the 1DFourier spectrum. The sampling process used is criticalin producing accurate results. A bilinear interpolation ofthe nearest four neighbors was found to produceaccurate results with minimal computational overhead.The number of angular slices taken have to be highA FAST HOUGH TRANSFORM FOR THE PARAMETRISATION OF STRAIGHT LINES USING FOURIER METHODSenough to ensure sucient coverage at high frequencies,where the sample points are relatively far apart.
Insampling the 2D Fourier spectrum up to its corners,pthesinogram produced was scaled by a factor of 2.However sampling the 2D Fourier spectrum up to itssides results in high frequencies being truncated, causingdistortion of edges and other high frequency spatialcomponents.The Hough transform of straight line segmentsproduces butter¯y dispersions around each maximumpoint in the sinogram.
To detect these maxima, the 1DFourier spectrum can be ®ltered using a 1D dierence ofGaussian ®lter to enhance the peak structure of thesinogram by accentuating the high frequency components of the butter¯y distribution. By increasingthe values of the standard deviations of the inhibitoryand excitatory Gaussians, i and e , the ®ltercan be altered to emphasise the higher frequencies ofthe input function.
The algorithm can be ecientlyimplemented in DSP hardware and utilised in machinevision applications to detect straight lines in 2Dimage arrays.References1. Hough, P.V.C. (1962) Method and means for recognisingcomplex patterns. U.S. Patent No. 3,069,654.2. Ballard, D.H. (1981) Generalising the Hough transform todetect arbitrary shapes. Pattern Recog.
Lett., 13:111±122.3. Leavers, V.F. (1992) Shape Detection in Computer Visionusing the Hough Transform. Berlin: Springer-Verlag.4. Deans, S.R. (1993) The Radon Transform and some of itsApplications. Malabar, Florida; Krieger Publishing Company.5. Leavers, V.F. & Boyce, J. (1987) The Radon transformand its application to shape parametrisation in machinevision. Image and Vision Computing, 5:161±166.6. Toft, P.A. & Hansen, K.V. (1994) Fast Hough transformfor detection of seismic re¯ections. In: Signal ProcessingVII ± Theories and Applications. EURASIP EUSIPCO94vol.
I, pp. 229±232.7. Toft, P.A. (1996) Using the generalized Radon transformfor detection of curves in noisy images. In: Proceedings.IEEE ICASSP, vol. 4, pp. 2221±2225.View publication stats1278. Toft, P.A. (1996) The Radon transform: Theory andimplementation. PhD thesis, Department of MathematicalModelling, Technical University of Denmark.9. Illingworth, J.
& Kitter, J. (1988) A survey of the Houghtransform. Computer Vision, Graphics and Image Processing, 44:87±116.10. Li, H., Lavin, M.A. & Le Master, R.J. (1986) Fast Houghtransform: A hierachical approach. Computer Vision,Graphics and Image processing, 36:139±161.11. Kultanen, P., Xu, L. & Oja, E. (1990) Randomized HoughTransform (RHT).
10th IAPR International Conference onPattern Recognition, vol. 1, pp. 631±635.12. KaÈlviaÈinen, H., Hirvonen, P., Xu, L. & Oja, E. (1995)Probabilistic and non-probabilistic Hough transforms:Overview and Comparations. Image and vision computing, 13:239-252.13. Duda, R.O. & Hart, P.E. (1972) Use of Hough transformation to detect lines and curves in pictures. Commun.ACM, 15:11±15.14. Deans, S.R. (1981) Hough transform from the Radontransform. IEEE Trans.
Pattern Anal. Mach. Intell., 3:185±188.15. Radon, J. (1917) UÈber die bestimmung von funcktionendurch ihre integralwerte laÈngs gewisser mannigfaltigkeiten.Ber. SaÈchs. Akad. Wiss. Leipzig., 69:262±278.16. Mersereau, R.M. & Oppenheim, A.V. (1974) Digitalreconstruction of multidimensional signals from theirprojections. Proc. IEEE, 62:1319-1338.17. Easton Jr., R.L.
& Barrett, H.H. (1987) TomographicTransformations in Optical Signal Processing. In: Horner,J.L. (ed), Optical Signal Processing, New York: AcademicPress, pp. 335±386.18. Barrett, H.H. (1982) Optical processing in Radon space.Opt. Lett., 7:248±250.19. Eichmann, G. & Dong, B.Z. (1983) Coherent opticalproduction of the Hough transform. Appl. Opt., 2:830±834.20. Gindi, G.R. & Gmitro, A.F. (1984) Optical featureextraction via the Radon transform.
Opt. Eng., 23:499±506.21. Hanahara, K., Maruyama, T. & Uchiyama, T. (1988) Areal-time processor for the Hough transform. IEEE Trans.Pattern Anal. Mach. Intell., 10:121±125.22. Young, R.C.D., Budgett, D.M. & Chatwin, C.R. (1995)Video Rate Implementation of the Hough Transform. 28thProc. ISATA, Robotics, Motion and Machine Vision in theAutomotive Industries, pp. 35±43.23. Brantner, S., Young, R.C.D., Budgett, D.M. & Chatwin,C.R. (1997) High-speed tomographic reconstruction employing Fourier methods. Real-Time Imaging, 3:255±274.24. Marr, D.
& Hidreth, E. (1980) Theory of edge detection.Proc. R. Soc. Lond. B., 207:187±217..
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
