计算机视觉课件(1)

*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,Course 8 Contours,Course 8 Contours,Def:edge list,-ordered set of edge point or fragments.,Def:contour,-an edge list or expression that is used to represent the curve.,A contour can be open or closed.,Digital Curve.,(1)Curve length:,(2)K-slope:the(angle)direction vector between points with k edge points apart.,(3)K-curvature:the difference between left k-slope and right k-slope at a digital curve point:,2.Curve Representations,1)Chain code,Chain code quantities a space to 8 directions and encodes a contour at each edge point with the directions in an ordered sequence.,-Chain code has compact description.,-Chain code cannot express branched curves.,plot:,For a digital curve,compute curve length and,slope from a beginning edge point.Then plot the,obtained curve length and slop in space.,-Line segment in curve;horizontal line in plot.,-Circular arc in curve;line segment of some direction in space.,-Using plot can easily segment a curve at discontinuous point of plot.,Graph representation:,Establish topology relations among edge list points.,Each edge point is a graph node.,Struct,Node,int,node_number;,int,curve_number;,int,x,y;/position,char type;,int,link8;/link relation,int,link_direction8;/heading or ending,char flag;/process flag,node;,-Digital description of curve.,-Can handle branched curves.,-Easy in operation.,-Use more memories,but it can be simplified.,e.g.to remove nodes that have,type=2,.,Struct link,int curve_number;,int link_length;,int node_list;,char flag;/process flag,link;,3.Polyline representation,Represent an edge list by a set of joined line segments.The edge data not being the joint point will be neglected.,1).Recursive splitting method:,Consider a curve with endpoint A and B,connect end-points A and B,along the curve ,compute normalized distance,to chord .find the edge point say c with maximum .,(c),if ,the preset threshold,insert a vertex at edge point c.,The curve is then subdivided into two curves.,(d),For each curve,repeat the process a)c)until no vertex can be inserted.,2).Sequential method:,(a),Starting with an endpoint of a curve tracing the curve,calculate the distance between the curve and the chord from the starting point to moving point.,(b),If the distance is greater than a preset threshold,put a vertex there.,(c),Take the vertex as a,new starting point.,Repeat the operation a)and,(d),until it complete the curve.,3).Area based sequential method:,The same as the above method.But the criteria to insert a vertex is,where is the area between the curve and chord.,is the length of chord.,4).Break-point detection:,Sequential polyline methods have advantage of easy and fast operations.But they are error-based operations,Corner positions usually cannot accurately located.One way to solve the problem is to detect break point first.Then polylinelize the curve piecewise.,To detect break point:,Calculate K-curvature along a curve.,Plot the curves curvatures in plane.,Where -curvature,s,-curve length.,Do Gaussian smooth to the plot to remove noise of the plot.,Corners of original curve will correspond to peaks in plot,arcs to plateaus,threshold the value,in plot will get break points.,5).Hop-Along algorithm:,Hop-along method approximate a contour by a sequence of line segments,doing split and merge in short subsets of edge points.,a),Start with the first K edge points from edge list.,b),Fit line segment(say,using least-square method)between the first and the last edge points of the sub list.,c),I,f normalized maximum error is too large,shorten the sub list at the point of maximum error.Return step b).,d),If the line fit succeeds,compare the orientation of the current line segment with that the previous line segments.If two line segments have similar orientation,replace the two line segments with a single line segment.,e)Make the current line segment the previous line segment and advance the window of edges so that there are K edge points in the sub list.Return to step b).,3.Curve fitting,Curve fitting is trying to find a smooth curve expression of mathematic form from curves polyline expression.,Conic sections:,To determine a conic section is to determine parameters a,b,c,d,e,f from 3 edge points,although there are classic method.We will introduce a“guided form method.,Select knot position from each,polyline,segment.,where,b)Form lines of guided frame:,K,i,V,i+1,:,V,i+1,K,i+1,:,K,i,K,i+1,:,Then:the conic intersection is:,where is control parameter.,2)Cubic Spline:,Cubic spline represents a curve piecewise by 3,rd,-order polynomials joined smoothly at knots of the curve.,Between two knots:,where,There are 8 parameters and need 8 constraints to determine the 8 parameters.,Positions of first and last edge points give 4,constraints.,The continuity of the curve with its neighboring curves gives another 2 constraints.,Orientation of edge at knot provides one constraint.,or,where ,tangent direction at knot introduces two equations and one additional unk