1、機(jī)器人控制理論與技術(shù)（4）,2,問題,魚能知道物體的遠(yuǎn)近嗎？,3,問題,魚能知道物體的遠(yuǎn)近嗎？,4,The wedding of Giovanni Arnolfini J. Van Eyck 1366-1426,5,6,Distortion in Paintings,Anamorphosis,7,全景視覺系統(tǒng),全景視覺系統(tǒng)是由一個(gè)可以獲得360度范圍內(nèi)景象的視覺系統(tǒng)。 常見的全景視覺系統(tǒng)有三種： Compound-eye camera Panoramic cameras Omnidirectional cameras,8,Omnidirectional cameras,PAL Panorami

2、c Annular lens,Catadioprtic Sensor,Two folded mirror sensor,Cons:- Blindspot- Low resolution,Pros: - Single image,9,An omnidirectional camera view,Panoramic Cylinder (from Centre for Machine Perception, Praha),Omnidirectional image,10,Compound-eye cameras,The Ringcam at Microsoft Research,ViewplusSo

3、ftpia Japan expensive,Ladybug PointGrey,11,Panoramic cameras,Cirkut Camera,Panning camera,Swing lens,Roundshot,Pros: - High resolution per viewing angle,Cons: slow acquisition; No dynamic scene expensive,12,全景視覺自主控制機(jī)器人,身高：39cm 體重：2.2kg 全景攝像機(jī)： 25萬(wàn)像素,13,如何從點(diǎn)陣中提取出線段呢？,從點(diǎn)陣中提取直線,從點(diǎn)陣中提取出直線 三個(gè)主要問題： 點(diǎn)陣?yán)锎嬖诙嗌?/p>

4、條直線? 哪個(gè)點(diǎn)屬于哪條直線 ? 如何從點(diǎn)集中提取出線段的參數(shù) ? 直線提取算法:1. Split-and-merge2. RANSAC3. Hough-Transform,14,直線提取 | split-and-merge (standard),Originates from Computer Vision. A recursive procedure of fitting and splitting. A slightly different version, called Iterative end-point-fit, simply connects the end points fo

5、r line fitting.,15,Initialize set S to contain all points Split Fit a line to points in current set S Find the most distant point to the line If distance threshold split set & repeat with left & right sets Merge If two consecutive segments are close/collinear enough, obtain thecommon line and find t

6、he most distant point If distance = threshold, merge both segments,直線提取 | split-and-merge (standard),Originates from Computer Vision. A recursive procedure of fitting and splitting. A slightly different version, called Iterative end-point-fit, simply connects the end points for line fitting.,16,Init

7、ialize set S to contain all points Split Fit a line to points in current set S Find the most distant point to the line If distance threshold split set & repeat with left & right sets Merge If two consecutive segments are close/collinear enough, obtain thecommon line and find the most distant point I

8、f distance = threshold, merge both segments,直線提取 | split-and-merge (standard),Originates from Computer Vision. A recursive procedure of fitting and splitting. A slightly different version, called Iterative end-point-fit, simply connects the end points for line fitting.,17,Initialize set S to contain

9、 all points Split Fit a line to points in current set S Find the most distant point to the line If distance threshold split set & repeat with left & right sets Merge If two consecutive segments are close/collinear enough, obtain thecommon line and find the most distant point If distance = threshold,

10、 merge both segments,直線提取 | split-and-merge (standard),Originates from Computer Vision. A recursive procedure of fitting and splitting. A slightly different version, called Iterative end-point-fit, simply connects the end points for line fitting.,18,Initialize set S to contain all points Split Fit a

11、 line to points in current set S Find the most distant point to the line If distance threshold split set & repeat with left & right sets Merge If two consecutive segments are close/collinear enough, obtain thecommon line and find the most distant point If distance = threshold, merge both segments,直線

12、提取 | split-and-merge (standard),Originates from Computer Vision. A recursive procedure of fitting and splitting. A slightly different version, called Iterative end-point-fit, simply connects the end points for line fitting.,19,Initialize set S to contain all points Split Fit a line to points in curr

13、ent set S Find the most distant point to the line If distance threshold split set & repeat with left & right sets Merge If two consecutive segments are close/collinear enough, obtain thecommon line and find the most distant point If distance = threshold, merge both segments,Split-and-Merge | iterati

14、ve end-point-fit,Iterative end-point-fit: simply connects the end points for line fitting.,20,直線提取 | RANSAC,RANSAC = RANdom SAmple Consensus. A generic & robust fitting algorithm of models in the presence of outliers(i.e. points which do not satisfy a model) Applicable to any problem where the goal

15、is to identifythe inliers which satisfy a predefined model. Typical applications in robotics are: line/plane extraction, feature matching, structure from motion, RANSAC is iterative and non-deterministic the probability to find a set free of outliers increases as more iterations are used Drawback: A

16、 non-deterministic method, results are different between runs.,21,RANSAC | how it works,22,RANSAC | how it works,23,Select sample of 2 points at random,RANSAC | how it works,24,Select sample of 2 points at random Calculate model parameters that fit the data in the sample,RANSAC | how it works,25,Sel

17、ect sample of 2 points at random Calculate model parameters that fit the data in the sample Calculate error function for eachdata point,RANSAC | how it works,26,Select sample of 2 points at random Calculate model parameters that fit the data in the sample Calculate error function for eachdata point

18、Select data that supports currenthypothesis,RANSAC | how it works,27,Select sample of 2 points at random Calculate model parameters that fit the data in the sample Calculate error function for eachdata point Select data that supports currenthypothesis Repeat sampling,RANSAC | how it works,28,Select

19、sample of 2 points at random Calculate model parameters that fit the data in the sample Calculate error function for eachdata point Select data that supports currenthypothesis Repeat sampling,RANSAC | how it works,29,Select sample of 2 points at random Calculate model parameters that fit the data in

20、 the sample Calculate error function for eachdata point Select data that supports currenthypothesis Repeat sampling Set with the maximum number of inliers obtained within k iterations,RANSAC | how many iterations?,We cannot know in advance if the observed set contains the max. no. inliers ideally: c

21、heck all possible combinations of 2 points in a dataset of N points. No. all pairwise combinations: N(N-1)/2 computationally infeasible if N is too large. example: laser scan of 360 points need to check all 360*359/2= 64620 possibilities! Do we really need to check all possibilities or can we stop R

22、ANSAC after iterations? Checking a subset of combinations is enough if we have a rough estimate of the percentage of inliers in our dataset This can be done in a probabilistic way,30,RANSAC | how many iterations?,N := tot. no. data points w := number of inliers / Nw : fraction of inliers in the data

23、set w = P(selecting an inlier-point from the dataset) Let p := P(selecting a minimal set of points free of outliers) Assumption: the 2 points necessary to estimate a line are selected independently P(both selected points are inliers)=? P(at least one of these two points is an outlier)=?,31,RANSAC |

24、how many iterations?,w := number of inliers / NN := tot. no. data pointsw : fraction of inliers in the dataset w = P(selecting an inlier-point from the dataset) Let p := P(selecting a minimal set of points free of outliers) Assumption: the 2 points necessary to estimate a line are selected independe

25、ntly P(both selected points are inliers)=w2 P(at least one of these two points is an outlier)=1 - w2 Let k := no. RANSAC iterations executed so far P(RANSAC never selects two points that are both inliers)= ?,32,RANSAC | how many iterations?,w := number of inliers / NN := tot. no. data pointsw : frac

26、tion of inliers in the dataset w = P(selecting an inlier-point from the dataset) Let p := P(selecting a minimal set of points free of outliers) Assumption: the 2 points necessary to estimate a line are selected independently P(both selected points are inliers)=w2 P(at least one of these two points i

27、s an outlier)=1 - w2 Let k := no. RANSAC iterations executed so far P(RANSAC never selects two points that are both inliers)=(1-w2)k 1-p = (1-w2)k,33,In practice we need only a rough estimate of w. More advanced variants of RANSAC estimate the fraction of inliers & adaptively set it on every iterati

28、on.,直線提取 | Hough-transform,Edges vote for plausible line locations Map image space into Hough parameter space Hough space parameterizes coordinate space w.r.t line characteristics In practice, its a discretized accumulator array (comprising of voting bins),34,Image Space,Hough Parameter Space,Hough-

29、Transform | Hough space,A line in the image corresponds to a point in Hough space,35,Image Space,Hough Parameter Space,What does a point (x0, y0) in the image space map to in the Hough space?,Hough-Transform | Hough space,What does a point (x0, y0) in the image space map to in the Hough space?,36,Im

30、age Space,Hough Parameter Space,Where is the line that contains both (x0, y0) and (x1, y1)? At the intersection of: b = x0m + y0 and b = x1m + y1,Hough-Transform | how it works,Each point in image space, votes for line-parameters in Hough parameter space,37,Image Space,Hough Parameter Space,直線提取 | H

31、ough-Transform,Problems with the (m,b) space: Unbounded parameter domain Vertical lines require infinite m Alternative: polar representation,38,Each point in image space will map to asinusoid in the (,) parameter space,直線提取 | relative merits,Split-and-merge: fastest Deterministic & makes use of the

32、sequential ordering of raw scan points(: points captured according to the rotation direction of the laser beam) If applied on randomly captured points onlyRANSAC and Hough-Transform would segmentall lines. RANSAC and Hough-Transform: more robust to outliers,39,邊緣檢測(cè),Edge contours in the image corresp

33、ond to important scene contours. Ultimate goal of edge detection: an idealized line drawing. Edges correspond to sharp changes of intensity Change is measured by 1st order derivative in 1D,40,Big intensity change magnitude of derivative is large Or 2nd order derivative is zero.,邊緣檢測(cè) | 1D edge detect

34、ion,Image intensity shows an obvious change,41,邊緣檢測(cè) | solution: smooth first,Edges occur at maxima/minima of s(x),42,邊緣檢測(cè) | derivative theorem of convolution,43,邊緣檢測(cè) | zero-crossings,44,邊緣檢測(cè) | 2D Edge detection,45,Harris角點(diǎn)檢測(cè),How do we identify corners? Key: around a corner, the image gradient has tw

35、o ormore dominant directions Shifting a window in any direction should give a largechange in intensity in at least 2 directions,46,Harris角點(diǎn)檢測(cè),47,Harris角點(diǎn)檢測(cè),48,Harris角點(diǎn)檢測(cè),49,Harris角點(diǎn)檢測(cè),50,Harris detector: probably the most widely used & known corner detector The detection is invariant to Rotation Lin

36、ear intensity changes note: to make the matching invariant to these we need a suitable descriptor and matching criterion (e.g. SSD on patches is not rotation- or affine- invariant) The detection is NOT invariant to Scale changes Geometric affine changes: an image transformation which distorts the ne

37、ighborhood of the corner, can distort its “cornerness” response,問題,本書出現(xiàn)在場(chǎng)景中了嗎？,51,SIFT 特征提取,52,SIFT: Scale Invariant Feature Transform SIFT features are reasonably invariant to changes in: rotation, scaling, small changes in viewpoint, illumination Very powerful in capturing + describing distinctive

38、 structure, but also computationally demandingMain SIFT stages: 1. Extract keypoints + scale 2. Assign keypoint orientation 3. Generate keypoint descriptor,Point Features | SIFT detector (keypoint location + scale),53,Keypoint detection 1. Scale-space pyramid: subsample and blur original image 2. Di

39、fference of Gaussians (DoG) pyramid: subtract successive smoothed images 3. Keypoints: local extrema in the DoG pyramid,Point Features | SIFT orientation and descriptor,54,Keypoint orientation (to achieve rotation invariance) Sample intensities around the keypoint Compute a histogram of orientations

40、 of intensity gradients Keypoint orientation = histogram peak Keypoint descriptor SIFT descriptor: 128-long vector Describe all gradient orientations relative to the Keypoint Orientation Divide keypoint neighborhood in 44 regions & compute orientation histograms along 8 directions SIFT descriptor: c

41、oncatenation of all 448 (=128) values,問題,本書出現(xiàn)在場(chǎng)景中了嗎？,55,http:/www.cs.ubc.ca/lowe/keypoints/,Most of the Books keypoints appear in the Scene,Answer: the Book is present in the Scene,問題,本書出現(xiàn)在場(chǎng)景中了嗎？,56,Most of the Books keypoints appear in the Scene,Answer: the Book is present in the Scene,目標(biāo)識(shí)別,在一幅圖像里找

42、到一個(gè)物體 在一組圖像里找到一個(gè)物體 在一組圖像里找到多個(gè)物體,57,地點(diǎn)識(shí)別,Extension to scene/place recognition: Is this image in my database? Robot: Have I been to this place before? loop closure problem, kidnapped robot problem Use analogies from text retrieval: Visual Words Vocabulary of Visual Words “Bag of Words” approach,58,構(gòu)建可

43、視化地點(diǎn)數(shù)據(jù)庫(kù),59,詞典樹,We can describe a scene as a collection of words and look up in the database for images with a similar collection of words What if we need to find an object/scene in a database of millions of images? Build Vocabulary Tree via hierarchical clustering Use the Inverted File system: a way of efficient in