a_fast_hough_transform_for_the_parametri sation_of_ (856994)

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

Текст из файла

See discussions, stats, and author profiles for this publication at: https://www.researchgate.net/publication/222275232A Fast Hough Transform for the Parametrisation of Straight Lines usingFourier MethodsArticle in Real-Time Imaging · April 2000DOI: 10.1006/rtim.1999.0182 · Source: dx.doi.orgCITATIONSREADS341,5564 authors, including:Rupert C D YoungChris R ChatwinUniversity of SussexUniversity of Sussex297 PUBLICATIONS 2,768 CITATIONS 533 PUBLICATIONS 3,987 CITATIONS SEE PROFILESome of the authors of this publication are also working on these related projects:Journal Paper View projectControl and Monitoring of borders with the aid of multi-sensor UAVs View projectAll content following this page was uploaded by Chris R Chatwin on 05 February 2019.The user has requested enhancement of the downloaded file.SEE PROFILEReal-Time Imaging 6, 113±127 (2000)doi:10.1006/rtim.1999.0182, available online at http://www.idealibrary.com onA Fast Hough Transform forthe Parametrisation of Straight Linesusing Fourier MethodsThe Hough transform is a useful technique in the detection of straight lines and curves in animage.

Due to the mathematical similarity of the Hough transform and the forwardRadon transform, the Hough transform can be computed using the Radon transformwhich, in turn, can be evaluated using the central slice theorem. This involves a two-dimensionalFourier transform, an x-y to r- mapping and a 1D Fourier transform. This can be implementedin specialized hardware to take advantage of the computational savings of the fast Fouriertransform. In this paper, we outline a fast and ecient method for the computation of the Houghtransform using Fourier methods. The maxima points generated in the Radon space,corresponding to the parametrisation of straight lines, can be enhanced with a post transformconvolutional ®lter. This can be applied as a 1D ®ltering operation on the resampled data whilstin the Fourier space, so further speeding the computation. Additionally, any edge enhancement orsmoothing operations on the input function can be combined into the ®lter and applied as a net®lter function.# 2000 Academic Press1Cheyne Gaw Ho , Rupert C.D.

Young, Chris D. Brad®eld and Chris R. ChatwinLaser and Electro-Optics Research Group, School of Engineering, University of Sussex,Brighton, East Sussex BN1 9QT, UK1E-mail: c.g.ho@sussex.ac.ukIntroductionThe Hough transform can be used to determine theparametrisation of straight lines and curves in an image[1]. It can be generalized for di€erent classes of curves[2±4] but is most often used for the detection of straightline segments in 2D image arrays.For the parametrisation of straight lines, each point inthe Cartesian x-y image space is mapped to a sinusoidalcurve in the Hough r- space using the parametricrepresentation: r=x cos ‡ y sin . If the points are colinear, the sinusoids intersect at a point (r; ) corre-1077-2014/00/040113+15 $35.00/0sponding to a parametrisation of the line.

This producesa butter¯y dispersion in the parameter space aroundeach maximum point [5].Many research groups have proposed fast robustalgorithms for the detection of curves and lines in binaryimages using the Hough transform. Toft et al. [6±8] usesa fast curve estimation (FCE) algorithm which identi®escurve parameters by ®rst forming a pre-conditioningmap, which takes into account pixels in the image withzero value (image point mapping), to determine regionsin the parameter space which contain peaks.

A generalized Radon transform is then applied to these regions,#2000 Academic Press114C.W. HO ETAL.thus reducing the computational cost. Illingworth andKittler [9] and Li et al. [10] use a hierarchical Houghtransform, which ®rst quickly transforms the imageusing a coarse sampling interval to isolate areas ofinterest, and then transforms these areas with a slightly®ner sampling interval. The method is repeated withincreasing sampling resolution until the lines have beendetected. Ballard [2] uses a gradient method to estimatethe tangent of curves in the image.

Each point in theimage is then mapped to a point in parameter space,instead of a curve, given by the estimated gradient of theline. However accuracy is dependent upon the gradientoperator used and the noise level in the image. Othergroups such as Kultanen et al. [11] and KaÈlviaÈinen et al.[12] use an iterative algorithm called the random Radontransform, which maps two random non-zero pixelsfrom the image to a common point in the parameterspace. This is repeated until a suitable description of theparameter space has been obtained.Projection Generation and the Central Slice TheoremForward Radon transformThe forward Radon transform is used to transform a 2Dfunction into its projections. For a continuous 2Dfunction f…r† ˆ f…x, y†, a single 1D projection at an angle relative to the x-axis can be derived by integrationalong lines normal to the angle of projection.

For eachset of integration lines at di€erent angles relative to thex-axis, a di€erent projection is derived. The complete setof 1D projections of the function is called a sinogram,since a point in Cartesian space maps to a sinusoid inDue to the mathematical similarity of the Houghtransform and the forward Radon transform [8,13±14]the Hough transform can be equivalently computedusing the Radon transform [15], which can be veryeciently evaluated using the central slice theorem[16,17]. This involves a two dimensional Fourier transform (DFT), an x-y to r- mapping and a 1D DFTwhich can be computed optically [18±20] or in hardware[21±23] using specialized digital signal processing (DSP)chipsets to take advantage of the computational savingsof the fast Fourier transform (FFT).Levers and Boyce [5] propose a convolution ®lterwhich, when applied to the sinogram, generates a muchmore consistent peak structure by detecting the butter¯ydistributions in the sinogram corresponding to continuous straight-line segments, and discriminating againstthose associated with discontinued colinearities.

Thiscan be applied as a ®ltering operation on the resampled1D Fourier space prior to a 1D DFT being taken.Additionally, any edge enhancement or smoothingoperations on the input function can be combined intothe ®lter and applied as a net ®lter function to the 1DFourier space.In this paper we outline an algorithm for computingthe Radon transform of a real grayscale image usingFourier methods.

The interpolation method and the®ltering processes used on the 1D resampled Fourierspectrum will also be discussed.Figure 1. Illustration of projection generation (a) and thecentral slice theorem (b). The value of the function at r0 isprojected to 0 ˆ r0 :^n. The 1D Fourier transform of theprojection at angle is a central section of the 2D Fouriertransform of the function, orthogonal to the projectiondirection.A FAST HOUGH TRANSFORM FOR THE PARAMETRISATION OF STRAIGHT LINES USING FOURIER METHODSRadon space, and contains all the information in theoriginal function.We can obtain projections by integration over linesparallel to the y0 axis in a system of coordinates [x0 , y0 ]rotated at angle relative to the original [x, y] axes(Figure 1).

0 xxcos sin ˆ…1†0ÿ sin cos yyTherefore for a point (x, y) which lies a distance alongthe x0 axis: ˆ x cos ‡ y sin …2†Thus a 1D projection can be formed by integration ofthe image intensity f…x; y† along a line, L, that isperpendicular distance from the origin and at angle from the x-axis:Zf…x; y†dl…3†l…; † ˆLwhere l…; † is a 1D projection of the function f…x; y†at angle .The projection can also be de®ned as a 2D integralfunction using a 1D Dirac delta function:Z Zf…x; y†…p ÿ x cos ÿ y sin † dx dyl…; † ˆD…4†115where D is the space spanned by the variables ofintegration. For a continuous 2D function can belimited to the region …0 ) since if…ÿ1 1†; l…; † ˆ l…ÿ; ‡ † (Figure 2).Equation (2) can also be expressed in vector notation:p ˆ r cos cos ‡ r sin sin ˆ r cos… ÿ † ˆ r:^n…5†where r ˆ …x; y† ˆ jrj€ ˆ ‰ r cos ; r sin Š is the positionvector of a point in Cartesian space.

^n ˆ 1€ ˆ‰cos ; sin Š is the unit vector orthogonal to thedirection of projection.Therefore Eqn (4) can be rewritten as:Z Zl…p; † ˆf …r†…p ÿ r:^n† dxdy…6†DThe projection operator can also be expressed inoperator notation:R2 ‰ f …r†Š ˆ l…; †…7†where R2 is the Radon transform operator, whichtransforms the 2D function f…r† with axes ‰x; yŠ toRadon space with axes …; †. The subscript 2 denotesthe dimensionality of the function being transformed.Central slice theoremThe central slice theorem [16,17] states that the Fouriertransform of an …n ÿ 1† dimensional projection is aFigure 2. Mapping of a point at r ˆ jrj€ in Cartesian spacep(a) to a sinusoid in Radon space (b).

The locus of all vectors jpj€corresponding to the point at r is a sinusoid of amplitude jrj 2 and phase . Since is bipolar, l…; † ˆ l…ÿ; ‡ †. Therefore can be limited to the region …0 †:116C.W. HO ETAL.central section of the n-dimensional Fourier transformof the object, orthogonal to the projection direction.The 2D DFT of a 2D function f…r† gives:Z Zf …r†eÿj2p:r dxdyF2 ‰ f…r†Š F…p† ˆD…v; † ˆ F…p†jp ˆ ^nv : ˆ F…^nv†…8†where F2 is the 2D DFT operator, which transforms the2D function f…r† with axes ‰x; yŠ to 2D Fourier spacewith axes ‰Px ; Py Š.The 1D DFT of the Radon projections l…; † gives:F1 ‰l…; †Š …v; †Z Z Zf…r† …p ÿ r:^n† dxdy eÿj2v dˆDZZ Zf …r† dxdy …p ÿ r:^n†eÿj2v dˆZ Zˆf…r† eÿj2^nv:r dxdy…10†Thus, the 1D DFT of a Radon projection at angle relative to the x-axis gives a line through the origin ofthe 2D Fourier transform of the function f …r† relative tothe Px -axis (Figure 3).

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

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

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