数字图像处理-第七章2014

数字图像处理-第七章2014第一页，共97页。edgeFirstderivativeSecondderivative第二页，共97页。输出二值化的图像，判断为边缘的像素为1，其它为0。

基本步骤：滤波：

改善与噪声有关的边缘检测器的性能；一般滤波器降导致了边缘的损失；增强边缘和降低噪声之间需要折衷。

边缘计算函数：

将邻域强度值有显著变化的点突显出来。一阶或二阶变化。

检测：

一阶或二阶阈值。

(二阶阈值可子像素分辨率上估计)。7.1EdgeDetection第三页，共97页。梯度是向量概念；偏微分，可以用差分代替。差分需要定义，可以用相邻像元的灰度差,也可以用一定跨度像元的灰度差。涉及到尺度问题。边缘有强弱，也有尺度。不一定要用梯度计算，但是可以用类似的差分计算，以照顾到尺度问题。第四页，共97页。7.1.1常见的一阶边缘检测算子算子名称计算方法卷积模板优缺点Roberts算子梯度幅值阈值优点：边缘定位准、计算快（四个像素的）；缺点：对噪声敏感（模板小）Sobel算子/Prewitt算子梯度幅值阈值优点：平滑部分噪声；即使较弱边缘也可以产生较高的输出（相对Roberts算子）缺点：计算较慢Canny算子梯度幅值双阈值Gx=Gy=优点：减少噪声影响（双阈值），连续边缘；缺点：计算较慢-11-1111-1-1第五页，共97页。7.1.1常见的一阶边缘检测算子Gradient:Thederivativetoxandydirections第六页，共97页。Gradientimage第七页，共97页。Directgradientthreshold=54NoclosingboundaryPost-processingneeded第八页，共97页。Boundarybymarker-controlledwatershedComparisonwithwatershedresult第九页，共97页。(a)Robertsgradient(b)SobelgradientRoberts和Sobel的比较第十页，共97页。Canny算子：TheCannyoperatorwasdesignedtobeanoptimaledgedetector：根据对信噪比与定位乘积进行测度得到最优化逼近算子。

第十一页，共97页。（1）图像与高斯平滑滤波器卷积；（2）计算梯度幅值和相角；（3）非极大值抑制non-maximalsuppression（NMS）：细化幅值图像中的屋脊带，即只保留幅值局部变化最大的点．保证单像素边缘。（4）双域值提取边缘：取高低两个阈值作用在幅值图，t1=2t2，得到两个边缘图，高阈值和低阈值边缘图。跟踪高阈值边缘图，出现断点时，在低阈值边缘图中的8邻域中搜寻边缘下一边缘点。

Canny算子：第十二页，共97页。Usually,theuppertrackingthresholdcanbesetquitehigh,andthelowerthresholdquitelowforgoodresults.Settingthelowerthresholdtoohighwillcausenoisyedgestobreakup.Settingtheupperthresholdtoolowincreasesthenumberofspuriousandundesirableedgefragmentsappearingintheoutput.OneproblemwiththebasicCannyoperatoristodowithY-junctionsi.e.placeswherethreeridgesmeetinthegradientmagnitudeimage.Suchjunctionscanoccurwhereanedgeispartiallyoccludedbyanotherobject.Thetrackerwilltreattwooftheridgesasasinglelinesegment,andthethirdoneasalinethatapproaches,butdoesn'tquiteconnectto,thatlinesegment.第十三页，共97页。Gaussiankernelwithstandarddeviation

1.0andupperandlowerthresholdsof255and1.Gaussiankernelwithstandarddeviation

1.0andupperandlowerthresholdsof255and220.Gaussiankernelwithstandarddeviation

1.0andupperandlowerthresholdsof128and1.第十四页，共97页。13X13高斯滤波模板问题思考：增加高斯核尺度会对边缘梯度强度有什么作用？这意味着当这个尺度增加时必须对跟踪器的阈值做出什么改变？7X7高斯滤波模板尺度问题第十五页，共97页。问题思考：什么情况下你会选择canny算子而不选Roberts算子？什么情况下不会？去噪能力Gaussiannoisewithastandarddeviationof15Cannywithastandarddeviationof1.0Sobelwithathresholdof150第十六页，共97页。7.1.2二阶边缘检测算子LaplacianEdgeDetectionedgeFirstderivativeSecondderivativeZero-crossing第十七页，共97页。Ifanoise-freeimagehassharpedges,theLaplaciancanproduceclosed,connectedcontoursbyathreshold.Whennoisesexisting,alowpassfilteringisrequired.LaplacianofGaussian(LOG)第十八页，共97页。LOGwiththresholdof0Howtoextractthecontoursofthepearsaccordingtothisresult?第十九页，共97页。Zerocrossingpointsoftenoccurat`edges'inimages---i.e.pointswheretheintensityoftheimagechangesrapidly,buttheyalsooccuratplacesthatarenotaseasytoassociatewithedges.Itisbesttothinkofthezerocrossingdetectorassomesortoffeaturedetectorratherthanasaspecificedgedetector.第二十页，共97页。第二十一页，共97页。ThesimplestistosimplythresholdtheLoGoutputatzero,toproduceabinaryimagewheretheboundariesbetweenforegroundandbackgroundregionsrepresentthelocationsofzerocrossingpoints.Tolocateallboundarypoints,wesimplyhavetomarkeachforegroundpointthathasatleastonebackgroundneighbor.Theproblemwiththistechniqueisthatwilltendtobiasthelocationofthezerocrossingedgetoeitherthelightsideoftheedge,orthedarksideoftheedge,dependingonwhetheritisdecidedtolookfortheedgesofforegroundregionsorfortheedgesofbackgroundregions.Abettertechniqueistoconsiderpointsonbothsidesofthethresholdboundary,andchoosetheonewiththelowestabsolutemagnitudeoftheLaplacian,whichwillhopefullybeclosesttothezerocrossing.Amoreaccurateapproachistoperformsomekindofinterpolationtoestimatethepositionofthezerocrossingtosub-pixelprecision.第二十二页，共97页。边缘检测的困难：尺度问题边缘的类型：阶跃式、屋脊式，选择怎样的算子？或者比较一下两种形式下各个算子的计算结果（考试题目）第二十三页，共97页。思想：用某个解析函数如分段线性或高阶样条曲线来拟合边缘。称为边缘拟合。无论边缘点是连续的还是稀疏的。方法：常根据图象一小块区域来建立拟合模型。常用方法有：7.3Curvefitting(Modelfitting)第二十四页，共97页。7.2.1DivideandConquerGiven:BoundaryliesbetweenpointsAandBTask:FindBoundaryConnectAandBwithLineFindstrongestedgealonglinebisectorUseedgepointasbreakpointRepeat第二十五页，共97页。7.2.2Linefitting(LeastSquares)Given:ManypairsFind:ParametersMinimize:Averagesquaredistance:Using:Note:

第二十六页，共97页。7.2.3CurveFittingFindPolynomial:thatbestfitsthegivenpointsMinimize:Using:

第二十七页，共97页。Thepartialderivatives(againdroppingsuperscripts)areTheseleadtotheequations第二十八页，共97页。第二十九页，共97页。第三十页，共97页。Example:Origin软件提供了多种非线性拟合工具高阶多项式容易出现的问题：X很大时发散。处理：1、加大多项式中小数点后的位数，从而保证精度；2、适当降低多项式的阶数，将高次项的影响降低，从而得到合理的曲线。第三十一页，共97页。

用第二种方式,降低阶数拟合:第三十二页，共97页。7.2.4HoughTransformElegantmethodfordirectobjectrecognition

EdgesneednotbeconnectedCompleteobjectneednotbevisibleKeyIdea:EdgesVOTEforthepossiblemodel第三十三页，共97页。思想：Hough变换是对图象进行坐标变换，使之在另一个坐标空间的特定位置出现峰值。原理：点-线的对偶性（duality）。第三十四页，共97页。ImageandParameterSpacesEquationofLine:Find:Considerpoint:

ImageSpaceParameterSpaceParameterspacealsocalledHoughSpace第三十五页，共97页。LineDetectionbyHoughTransformParameterSpace1111112111111Algorithm:QuantizeParameterSpaceCreateAccumulatorArraySetForeachimageedgeincrement:Ifliesontheline:Findlocalmaximain第三十六页，共97页。BetterParameterizationNOTE: LargeAccumulator MorememoryandcomputationsImprovement: Lineequation: HereGivenpoints find(FiniteAccumulatorArraySize)ImageSpaceHoughSpace?HoughSpaceSinusoid第三十七页，共97页。1.Findallofthedesiredfeaturepointsintheimage.2.Foreachfeaturepoint,3. Foreachpossibilityiintheaccumulatorthatpassesthroughthe featurepoint.4. Incrementthatpositionintheaccumulator5.Findlocalmaximaintheaccumulator.6.Ifdesired,mapeachmaximaintheaccumulatorbacktoimagespace.ThealgorithmfortheHoughtransform第三十八页，共97页。ImagespaceVotesHorizontalaxisisθ,verticalisrho.第三十九页，共97页。Imagespacevotes第四十页，共97页。第四十一页，共97页。MechanicsoftheHoughtransformDifficultieshowbigshouldthecellsbe?(toobig,andwemergequitedifferentlines;toosmall,andnoisecauseslinestobemissed)Howmanylines?CountthepeaksintheHougharrayTreatadjacentpeaksasasinglepeakWhichpointsbelongtoeachline?SearchforpointsclosetothelineSolveagainforlineanditerate第四十二页，共97页。Fewervoteslandinasinglebinwhennoiseincreases.第四十三页，共97页。Addingmoreclutterincreasesnumberofbinswithfalsepeaks.第四十四页，共97页。RealWorldExampleOriginalEdgeDetectionFoundLinesParameterSpace第四十五页，共97页。FindingCirclesbyHoughTransformEquationofCircle:Ifradiusisknown:AccumulatorArray(2DHoughSpace)第四十六页，共97页。FindingCirclesbyHoughTransformEquationofCircle:Ifradiusisnotknown:3DHoughSpace!UseAccumulatorarrayWhatisthesurfaceinthehoughspace?第四十七页，共97页。UsingGradientInformationGradientinformationcansavelotofcomputation:EdgeLocationEdgeDirectionNeedtoincrementonlyonepointinAccumulator!!Assumeradiusisknown:第四十八页，共97页。RealWorldCircleExamplesCrosshairindicatesresultsofHoughtransform,boundingboxfoundviamotiondifferencing.第四十九页，共97页。FindingCoinsOriginalEdges(notenoise)第五十页，共97页。FindingCoins(Continued)PennyQuarters第五十一页，共97页。FindingCoins(Continued)Coinfindingsampleimagesfrom:VivekKwatraNotethatbecausethequartersandpennyaredifferentsizes,adifferentHoughtransform(withseparateaccumulators)wasusedforeachcirclesize.第五十二页，共97页。Squarefitting，location，orientation，sidelength，四个参数的。以日本项目为例第五十三页，共97页。HoughTransform:CommentsWorksonDisconnectedEdgesRelativelyinsensitivetoocclusionEffectiveforsimpleshapes(lines,circles,etc)Trade-offbetweenworkinImageSpaceandParameterSpaceHandlinginaccurateedgelocations:IncrementPatchinAccumulatorratherthanasinglepoint第五十四页，共97页。7.3ShapedescriptionRectangularityCircularitySmoothnessCompactnessBoundaryenergyAveragedistanceSpectraltransformInvariantmoments第五十五页，共97页。RectangularityAO:theobject’sareaandAR:theareaoftheobject’sminimalenclosingrectangle(MER).1.0forrectangularobjects;Pi/4forcircularobjects;Smallerforslender,curvedobjects.RatioofwidthtolengthoftheMER.Candistinguishslenderobjectsfromroughlysquareorcircularobjects.第五十六页，共97页。CircularityRatioofperimetersquaredtoarea,minimizedbythecircularshape.Reflectingthecomplexityoftheboundarybeingmeasured.第五十七页，共97页。BoundaryenergyThecurvaturefunctionatpointpisTheaverageenergyForfixedarea,thecirclehasminimumboundaryenergy第五十八页，共97页。ContourdistanceAveragedistancefromaninteriorpointtotheboundaryobject.Xiisthedistancefromthei’thpixeltothenearestboundarypointinanobjectofNpoints.TheshapemeasureisForcirclesandregularpolygons,theshapemeasuregivesthesamevalueas.Howeveritsdiscriminatorypowermaybesuperiorforthecomplexshapes.第五十九页，共97页。MPEG-7hassetseveralprinciplestomeasureashapedescriptor,thatis,goodretrievalaccuracy,compactfeatures,generalapplication,lowcomputationcomplexity,robustretrievalperformanceandhierarchicalcoarsetofinerepresentation.好的识别精度：

要平移、比例、旋转、仿射不变。Compactrequirement->indexingandonlineretrieval鲁棒性：对噪声的容许程序；普适性：应适应尽量多的形状而不是只针对某种形状；低计算复杂度：效率，同时也意味着清晰和稳定；可分为基于轮廓的和基于区域的表达；都可以进而分为全局的和结构的；以及空域的和变换域的；简单的那些算子通常只能识别形状差异较大的，用来限制错误形状，或与其他算子一起使用。第六十页，共97页。(a)的偏心率等于1，但事实上它不能正确地描绘该形状。它更应该称作长条形形状。(b)和(c)的圆度相等，但是显然它们并不相像。这时用偏心率更能区分。第六十一页，共97页。Shapesignature形状标志用一个由边界轮廓点得到的一维函数来描述一个形状。包括centroidalprofile,complexcoordinates,centroiddistance(如图所示),tangentangle,cumulativeangle,curvature,areaandchord-length.Boundarymoments边界矩可用来减少边界表达的维数。假设形状用shapesignaturez(i)表示,则r阶矩和中心矩可以用下式估计第六十二页，共97页。scalespacesignature尺度空间表达通过跟踪系列高斯滤波后的轮廓上的影响点得到。当高斯宽度增加时，那些不太重要的影响点会消失，轮廓会变得平滑（如图所示）。保留下来的影响点表达了重要的对象特征。平滑的过程得到了一个intervaltree，叫做“指纹”。从高到低尺度检测树枝的峰值。解释为corner,smoothjoint,end,crank,bump/dent。第六十三页，共97页。Chaincoderepresentation-structuremethodByencodingrelative,ratherthanabsolutepositionofthecontour,therepresentationistranslationinvariant.Wecanmatchboundariesbycomparingtheirchaincodes,butwiththefollowingproblems:•Wehavetohavethesamestartingpoint.Ifthestartingpointsaredifferent,wehavetorotatethecodetodifferentstartingpoints.•Smallvariationsinthecontourgivedifferentcodes.Matchingchaincodeforslightlynoisyversionsofthesameobjectcanbeverydifficult.•Therepresentationisnotrotationallyinvariant.(1)Thebasicchaincode第六十四页，共97页。Thiscanbecomputedbysubtractingeachelementofthechaincodefromthepreviousoneandtakingtheresultmodulon,wherenistheconnectivity.Thisdifferencingallowsustorotatetheobjectin90-degreeincrementsandstillcomparetheobjects,butitdoesn’tgetaroundtheinherentsensitivityofchaincodestorotationonthediscretepixelgrid.(2)Thedifferentialchaincode第六十五页，共97页。(3)ShapeNumbersIfwerollann-elementcodesothatithasthesmallestvaluewhenviewedasann-digitinteger,thatwouldbeinvarianttotheselectionofthestartingpoint.Suchanormalizeddifferentialchaincodeiscalledashapenumber.第六十六页，共97页。Ithasbeencontourtracedtogivethesequenceofsymbols:

444444444444444464464464666668686886888888888888a888a8aa8aaacacaccaccccccccccccccccccccccccccaccccccccccccccccacccccccccc020020200244242202202020202020020202020222242424424442Thenormalizedformis

0020200244242202202020202020020202020222242424424442444444444444444464464464666668686886888888888888a888a8aa8aaacacaccaccccccccccccccccccccccccccaccccccccccccccccacccccccccc02第六十七页，共97页。Example:CharactersoftheHarborTheboundarybetweenthequaysandthewatershowsawtoothshape.Thenumberofquaysisnotcertain，andisrelevantwithparticularobject.Theorientationsandanglesofthesawteethareuncertain.Thesizesofthesawteetharealsouncertain.第六十八页，共97页。PrimitiveofharborcontourControlpoints:thelocalmaximaofthecurvatureRecognitingtheprimitivesinthecontrolpoints

第六十九页，共97页。DetectionofthecontrolpointsTransformingthechaincodeofthecontourintotheanglefunction.chaincodeofacontour:

343333322122223223232323322322332323323211133333333333211

第七十页，共97页。DetectionofthecontrolpointsAdaptivesmoothing.DetectionofthecontrolpointsDifferentialchaincode第七十一页，共97页。Recognitionofharbor第七十二页，共97页。Spectraltransform谱描绘子克服了空域描绘子对噪声的敏感问题。包括傅里叶描绘子(FD)和小波描绘子(WD),它们是从1D形状标志的频谱变换得来的。FD开始只针对封闭曲线的，后来越来越多的改进使它可以处理开放的形状，出现了仿射不变的FD。第七十三页，共97页。(1)ComplexFourierdescriptorThismethodwasfirstintroducedbyGranlundin1972.TheshapeisnowdescribedbyasetofNvertices{z(i):i=1,…,N}correspondingtoNpointsoftheoutline.TheFourierdescriptors{c(k):k=-N/2+1,…,N/2}arethecoefficientsoftheFouriertransformofz:TheFourierDescriptor代表了轮廓的频率性质（低频到高频的成分含量）。可以重构和压缩形状。第七十四页，共97页。第七十五页，共97页。K=0，c(k)代表了轮廓的重心。但是重心对描述轮廓形状是没用的。去掉它，描绘子才可以是平以不变的。K=1，c(k)表示的是形状的尺寸。将其他系数设为0的话，形状恢复出来就是个圆。可以用它来归一化描绘子，得到homothety（相似扩大）不变的描绘子。封闭轮廓的近似轮廓也是封闭的。不能保证一个只有单环的轮廓还能近似为单环轮廓，有可能出现交叉。第七十六页，共97页。FromFouriertheory,thegeneralformfortheFouriercoefficientsofacontourgeneratedbytranslation,rotation,scalingandchangeofstartpointfromanoriginalcontourisgivenby:|bn|

isinvarianttotranslation,rotation,scalingandchangeofstartpoint.ThesetofmagnitudesofthenormalizedFouriercoefficientsoftheshape{bn,0<n<=N}cannowbeusedasshapedescriptors,denotedas{FDn,0<n<=N}.Fourierdescriptorsshouldstayconstantnomatteroneofthefollowingtransformations:translationorrotationoftheshape,changeofscaleoroforigin.第七十七页，共97页。(2)TransformtotangentspaceThismethodwasfirstintroducedbyZahnandRoskiesin1972Theoutlineoftheshapeisseenasaclosedcurve,describedbyitsarclengthsfromanoriginA.

Wenormalizethisparametersothatitssumoverthewholecurveisequalto2.Pi.Wedefineafunctionoft,calledPhi,thatgivestheangularvariationbetweenthetangentattheoriginAandthetangentatpositions.TheFourierDescriptors第七十八页，共97页。第七十九页，共97页。Thisfunctionisreal,continuous,andperiodicalwithaperiod2.Pi.Therefore,itcanbedescribedbyaFourierseries:Foranyabovederived1Dsignaturefunctionu(t),itsdiscreteFouriertransformisgivenby

ThisresultsinasetofFouriercoefficients{an},whichisarepresentationoftheshape.第八十页，共97页。第八十一页，共97页。Theprototypecentroiddistancecurvesforeachclass.Thecentroidcontourdistance:

第八十二页，共97页。TheprototypeFourierdescriptorsforeachclass.Classification:UsingTimeWarpDistance,theclosestclassischosenastheleaftype.第八十三页，共97页。TheadvantagesofFDovermanyothershapedescriptorsare(i)simpletocompute;(ii)eachdescriptorhasspeci1cphysicalmeaning;(iii)simpletodonormalization,makingshapematchingasimpletask;(iv)capturesbothglobalandlocalfeatures.Withsufficientfeaturesforselection,FDovercomestheweakdiscriminationabilityofthosesimpleglobaldescriptors.FDalsoovercomesthenoisesensitivityanddifficultnormalizationintheshapesignaturerepresentations.第八十四页，共97页。InvariantmomentsGeometricMoments:Thesetofmomentsofaboundedfunctionf(x,y)isdefinedbyj,ktakesonanynonnegativeintegervalues.{Mjk}f(x,y)Forshapedescriptivepurposes,supposef(x,y)takesonthevalue1insidetheobjectand0elsewhere.Theparameterj+kiscalledtheorderofthemoment.Momentsofordersupto2allowtoapproximatetheregionbyanellipseThisellipsewillhavethesamemomentsofordersupto2astheoriginalregion第八十五页，共97页。CentralizedmomentsThecoordinatesofthecenterofgravityofanobjectPrincipleAxes_usedinordertodistinguishtheposture.Thecentralizedmomentsaretranslationinvariant.第八十六页，