line fitting

《line fitting》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、LinefittingJackEltonBresenhamb.1937IBM/WinthropUniversityBresenham'sLineAlgorithm(1962)LineTracingInput:(x0,y0)&(x1,y1)Output:ApproximationofCoordinatesonthatlineLineTracing(x,y)(x+dx,y+dy)LineTracing-Pseudocode(x,y)drawLineP(x,y,x+dx,y+dy)//assumedx,

2、dy>0a=0,b=0whilea<=dxandb<=dydrawPixel(x+a,y+b)ifa/dx<=b/dya++elseb++Worksforpositivedxanddy(x+dx,y+dy)AutonomousMobileRobotsLineExtractionSplitandmergeLinearregressionRANSACHough-TransformZürichAutonomousSystemsLab4b-Perception-Features4b7LineExtract

3、ion:MotivationMapoftheASLhallwaybuiltusinglinesegments©R.Siegwart,D.Scaramuzza,ETHZurich-ASL4b-Perception-Features4b8LineExtraction:MotivationMapoftheASLhallwaybuiltusingorthogonalplanesconstructedfromlinesegments©R.Siegwart,D.Scaramuzza,ETHZurich-A

4、SL4b-Perception-Features4b9LineExtraction:MotivationWhylaserscanner:DenseandaccuraterangemeasurementsHighsamplingrate,highangularresolutionGoodrangedistanceandresolution.Whylinesegment:ThesimplestgeometricprimitiveCompact,requireslessstoragePr

5、ovidesrichandaccurateinformationRepresentsmostoffice-likeenvironment.©R.Siegwart,D.Scaramuzza,ETHZurich-ASL4b-Perception-Features4b10LineExtraction:TheProblemScanpointinpolarform:(ρi,θi)Assumptions:Gaussiannoisewith(0,σ)forρNegligibleangularuncer

6、taintyLinemodelinpolarform:xcosα+ysinα=r-π<α<=πr>=0rα©R.Siegwart,D.Scaramuzza,ETHZurich-ASL4b-Perception-Features4b11LineExtraction:TheProblem(2)Threemainproblems:Howmanylines?Whichpointsbelongtowhichline?•ThisproblemiscalledSEGMENTATIONGivenp

7、ointsthatbelongtoaline,howtoestimatethelineparameters?•ThisproblemiscalledLINEFITTINGTheAlgorithmswewillsee:1.Splitandmerge2.Linearregression3.RANSAC4.Hough-Transform©R.Siegwart,D.Scaramuzza,ETHZurich-ASL4b-Perception-Features4b12Algorithm1:Split-and

8、-Merge(standard)Themostpopularalgorithmwhichisoriginatedfromcomputervision.Arecursiveprocedureoffittingandsplitting.Aslightlydifferentversion,calledIterative-End-Point-Fit,simplyconnectstheendpointsforlinefitting.©R.Siegwart,D.Scaramuzza,ET