跳到主要內容

臺灣博碩士論文加值系統

(35.172.136.29) 您好!臺灣時間:2021/08/02 18:37
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:周利蔚
研究生(外文):Chou Li-Wei
論文名稱:基於影像偵測之B-spline避障軌跡規劃
論文名稱(外文):Design of B-spline Obstacle Avoidance Trajectory Planning Based on Image Detection
指導教授:蔡樸生
指導教授(外文):Tsai Pu-Sheng
學位類別:碩士
校院名稱:中華技術學院
系所名稱:電子工程研究所碩士班
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2007
畢業學年度:95
語文別:中文
論文頁數:114
中文關鍵詞:路徑規劃邊點序向排列法轉折點偵測法向量內積圓偵測法禁行路徑B-樣條曲線約束最佳化
外文關鍵詞:Path planningBoundary Sequence MethodCorner Detection AlgorithmInner Product DetectionForbidden PathsB-spline CurveConstrained Optimization Algorithm
相關次數:
  • 被引用被引用:5
  • 點閱點閱:530
  • 評分評分:
  • 下載下載:120
  • 收藏至我的研究室書目清單書目收藏:0
本文是以影像處理為基礎來偵測環境中障礙物之分佈模型,以環境模型為基礎,建構一條連接起始點到終點之B-spline平滑軌跡。除了滿足車輛轉彎時最小曲率半徑的限制以及起始點與終點之運動約束外,並可成功地避開障礙物。在障礙物影像偵測方面,提出了邊點序向排列法,將所有物體的邊點座標進行有序排列,除了決定每個邊點之間的鏈結關係外,並且將影像中的物體作個別分類。配合向量內積圓形偵測法以及轉折點偵測法來決定圓形物體中心點、半徑及其外切正六邊形以及多邊形物體的頂點座標,以建立障礙物的分佈模型。並透過Dijkstra’s最短路徑搜尋法,以障礙物的頂點即轉折點為網路節點,最短路徑為代價函數,完成避障路徑設計。在最短路徑搜尋中,我們提出兩種禁行路徑偵測法來判別兩頂點間的連通性,分別為幾何偵測法與影像偵測法兩種。前者是利用直線與凸邊形的特性,後者則運用影像二值化及邊緣之訊息,來決定偵測點是否座落在障礙物範圍內。最後本文推導分段型B-spline曲線來取代傳統的遞迴表示式,採用B-spline解析函數作為平滑路徑的設計,有效地整合約束最佳化之演算法,將曲率限制以及運動約束引入最小路徑的代價函數中,將軌跡規劃的問題轉換成求解約束最佳化求解控制點的問題。為了驗證本文架構的可行性,我們以Matlab程式語言的GUI介面,完成B-spline軌跡規劃模擬軟體。由模擬得知,利用約束最佳化求解B-spline避障軌跡不僅具有可行性,並可獲至良好的效果。
In this thesis, the problem of path planning for autonomous vehicles or mobile robots moving in the exploration of hazardous or complex areas is solved. The purpose is to generate a feasible path with the initial posture and the final one so that no collisions with obstacles would occur and various constraints are satisfied. First, an obstacle distribution model is established in a modeled-based environment by image processing techniques. As for the obstacle detection, the boundary sequence method arranges boundary coordinates for each object in order as well as determines the link relation of each boundary such that the objects are detected and classified. Applying the geometric characteristics of the circumferential angle, the inner product detection is developed to determine whether there are round objects in the image. By adopting the corner detection algorithm, we compare the angles of bordered vector in order to determine the location of corners of each object. Using the corner points of each obstacle object as nodes to create a network, Dijkstra’s method is adopted to search the shortest path. To determine the connectivity between two nodes, geometric detection and image detection are evolved respectively to determine the forbidden paths. The former applies geometric characteristics of straight lines and convex hull, and the latter adopts the information of image binary threshold to judge whether the detecting point is allocated within the range of obstacle area. Finally, the matrix form of divided B-spline curve is derived, which makes it possible to realize the constrained optimization programming. The proposed algorithm is an integrated application of the constrained optimization method and B-spline basis function to generate the control points and to characterize the optimized B-spline curve that the kinematic constraints and curvature restrictions are satisfied. By using Matlab GUI toolbox, simulation results show that the design of B-spline obstacle avoidance trajectory which is based on image detection is applicable and it shows a better result.
中文摘要………………………………………………………………………………i英文摘要 ……………………………………………………………………………ii目次…………………………………………………………………………………iii表目錄……………………………………………………………………………… vi圖目錄………………………………………………………………………………vii符號表 ………………………………………………………………………………xii第一章 緒論…………………………………………………………………………1
第一節 研究動機…………………………………………………………………1
第二節 文獻回顧…………………………………………………………………2
第三節 內容概述與論文架構……………………………………………………7
第二章 圓形偵測與轉折點偵測影像處理演算法………………………………10
第一節 影像處理基本概念……………………………………………………10
壹 灰階轉換…………………………………………………………………10
貳 影像二值化………………………………………………………………10
参 邊緣偵測…………………………………………………………………12
肆 邊點序向排列……………………………………………………………13
第二節 向量內積圓偵測法……………………………………………………16
壹 圓的幾何性質……………………………………………………………16
貳 向量內積圓偵測法………………………………………………………17
參 圓周角門檻值的計算……………………………………………………20
第三節 轉折點偵測……………………………………………………………22
壹 轉折點偵測概念…………………………………………………………22
第四節 模擬結果……………………………………………………………25
壹 向量內積圓偵測法………………………………………………………25
貳 轉折點偵測………………………………………………………………29
第三章 Dijkstra's最短路徑搜尋法………………………………………………32
第一節 環境資訊………………………………………………………………32
壹 環境資訊的定義…………………………………………………………32
貳 凸邊形障礙物模型………………………………………………………33
第二節 禁行路徑判斷…………………………………………………………35
壹 幾何禁行路徑偵測步驟…………………………………………………35
貳 影像禁行路徑之偵測……………………………………………………38
參 邊緣門檻值設定…………………………………………………………39
第¬三節 Dijkstra's最短路徑搜尋法流程………………………………………40
第四節 模擬結果………………………………………………………………43
第四章 B-spline分段曲線之路徑規劃…………………………………………49
第一節 B-spline曲線及其特性………………………………………………49
壹 B-spline曲線 ……………………………………………………………49
貳 曲線特性………………………………………………………………53
第¬二節 分段 B-spline曲線……………………………………………………56
第三節 問題描述………………………………………………………………60
第四節 分段B-spline曲線位置、速度、加速度與控制點的關係…………63
第五節 具有約束條件之B-spline曲線最佳化演算法………………………66
第六節 模擬結果………………………………………………………………70
壹 淚滴線曲線測試…………………………………………………………70
貳 外擺曲線測試……………………………………………………………75
第五章 模擬結果與討論…………………………………………………………80
第一節 B-spline避障軌跡圖形介面…………………………………………80
第二節 向量內積圓形偵測模擬………………………………………………84
第三節 轉折點偵測法偵測模擬………………………………………………85
第四節 Dijkstra’s最短路徑搜尋法模擬………………………………………87
第五節 B-spline分段曲線之路徑規劃………………………………………88
第六節 特殊曲線繪製…………………………………………………………90
壹 繪製淚滴線曲線…………………………………………………………90
貳 繪製外擺曲線……………………………………………………………91
參 繪製心臟線………………………………………………………………92
第七節 討論……………………………………………………………………95
第六章 結論與未來研究方向……………………………………………………96
壹 結論………………………………………………………………………96
貳 未來研究方向……………………………………………………………97
參 結語………………………………………………………………………97
附錄…………………………………………………………………………………98
參考文獻…………………………………………………………………………111
[1].鍾國亮,“影像處理與電腦視覺”。東華書局。
[2].繆紹綱,“數位影像處理 活用-Matlab”。全華科技圖書。
[3].翁慶昌,“線性代數”。高立圖書有限公司。
[4].廖慶榮, “作業研究”。三民書局。
[5].徐曉珮譯,“數位影像處理”。高立圖書。
[6].林信男、黃瑞良譯,“離散數學”。培生教育出版集團。
[7].陳閩雄,“一個應用托勒密定理的隨機圓形偵測演算法”。台北科技大學碩士論文,2002。
[8].王敏,“基于圖象特徵的物體形狀識別方法研究”。機器視覺2004年第8期,2004。
[9].簡忠漢、賴建宏,“智慧型頭部影像追蹤系統”。聖約翰科技大學。【MATLAB® & Simulink ® Tech Forum and Expo】Call for Papers 技術應用論文,2005。
[10].呂國豪,“交通號誌辨識”。元智大學碩士論文,2004。
[11].王精忠,“車牌辨識系統之研究”。大同大學碩士論文,2004。
[12].柳美鈴,“使用K曲率法則於二維物體的分斷點偵測之研究”。朝陽科技大學碩士論文,2000。
[13].洪瑞斌,陳梁軒,“應用電腦視覺系統於工件圓弧之測量”。成功大學碩士論文,1993。
[14].簡卓建,“應用模糊控制於自走車路徑導引避障之整合設計”。國立成功大學碩士論文,2003。
[15].林泰宏,“自走車避障與導航性能之分析與設計”。逢甲大學碩士論文, 2004。
[16].鍾翼能,“雷達追蹤控制系統設計”。大葉大學碩士論文,2003。
[17].李家昇,“模糊理論在機械人即時避障的應用”。國立台灣大學碩士論文,1994.
[18].John Canny, “A Computational Approach to Edge Detection”, IEEE Trans. Pattern Anal. MachineIntell., PAMI-8(6), pp. 679-697, 1986.
[19].J. Illingworth, and J. Kittler, “A survey of the Hough Transform”, Computer Vision, Graphics, and Image Processing, vol. 44, pp. 87-116, 1988.
[20].N. Kiryati, Y. Eldar, and A. M. Bruckstein, “A Probabilistic Hough Transform”, Pattern Recognition, vol. 52, pp. 57-77, 1990.
[21].Y. C. Cheng, and Y. S. Liu, “A new Polling Method and Coaxal Transform for Robust Circle Detection”, Proc. of the 4th Asia Conf. on Computer Vision, pp. 336-340, 2000.
[22].M. A. Fischler, and R. C. Bolles, “Random Sample Consensus: A paradig fitting with application to image analysis and automated cartography”, Communications of ACM, vol. 24, no, 6, pp. 381-396, 1981.
[23].T. C. Chen, K. L. Chung, “An Efficient Randomized Algorithm for Detecting Circles,” Computer Vision and Image Understanding, vol. 63, no. 83, pp. 172-191, 2001
[24].H. C. Liu and M. D.Srinath., “Corner Detection from Chain-Code,” Pattern Recognition, vol. 23, pp. 51-68, 1990.
[25].G. Medioni, and Y. Yasumoto, “Corner Detection and Curve Representation using Cubic B - splines,” Computer Vision,Graphics Image Process, vol. 58, pp. 267-278, 1987.
[26].H. L. Beus, and S. S. H. Tiu, “An Improved Algorithm Based on Chain-Code Plane Curves”, Pattern Recognition, vol. 20, pp. 291-296, 1987.
[27].W. S. Rutkowski, and Rosenfeld, “An Comparison of Corner-Detection Techniques for n Chain-Coded Curves”. Technique Report TR-623, Computer Science Center, University of Maryland, 1978.
[28].A. Rosenfeld, and E. Johnson, “Angle Detection on Digital Curves”, IEEE Trans. Comput., pp. 875-878, 1973.m for model
[29].A. Rosenfeld, and J. S. Weszka, “An Improved Method of Angel Detection on Digital Curves”, IEEE Trans. Comput. vol. 24, pp. 940-941, 1975.
[30].F. Cheng, and W. Hsu, “Parallel Algorithm for Corner Finding on Digital Curves” , Pattern Recognition Lett., vol. 8, pp. 47-53, 1988.
[31].E. Asoudegi, and Z. Pan, “Computer Vision for Quality Control in Automated Manufacturing System”, Computer and Industrial Engineering, vol. 21, pp. 141-145, 1989.
[32].G. Oriolo, G. Ulivi and M. Vendittelli, “Real-Time Map Building and Navigation for Autonomous Robots in Unknown Environments”, IEEE Trans. on Systems, Man, and Cybernetics, Part B: Cybernetics, vol. 28, no.3, pp. 316-333, June, 1998.
[33].K. T. Song and W. H. Tang, “Environment Perception for a Mobile Robot Using Double Ultrasonic Sensors and a CCD Camera”, IEEE Trans. on Industrial Electronics vol. 43, no.3, pp. 372-379, June, 1996.
[34].H. P. Huang and P. C. Lee, “Microprocessor-Based Control of Autonomous Mobile Robots with Obstacle Avoidance”, Proceeding of the 30th Conference on Decision and Control, Brighton, England, December, 1991.
[35].R. A. Hogle and P. P. Bonissone, “A Fuzzy Algorithm for Path Selection in Autonomous Vehicle Navigation”, Proceeding of the 23rd Conference on Decision and Control, Las Vegas, NV, December, 1984.
[36].S. S. Ge, and Y. J. Cui, “New Potential Functions For Mobile Robot Path Planning”, IEEE Trans. on Robots and Automation , vol. 16, no, 5, pp. 615-620, 2000.
[37].E. Palma-Villalon, and P. Dauchez, “World Representation and Path Planning for a Mobile Robot”, Robotica, vol. 6, no. 1, pp. 35-40, 1988.
[38].D. M. Keirsey, E. Koch, J. McKisson, A. M. Meystel, and J. S. B. itchell, “Algorithm of Navigation for a Mobile Robot”, IEEE International Conf. on Robotics and Automation, vol. 1, pp. 574-583, 1984.
[39].E. Lucas, “Recreations Mathematiques”, 4 tomes, Gauthier Villars,. Paris, 1891, 1896, 1893, 1894.
[40].R. C. Prim, “Shortest connection networks and some generalizations”, Bell System Technical Journal. vol. 36, pp. 1389-1401, 1957.
[41].E. W. Dijkstra, “A note on two problems in connexion with graphs”, Numer. Math. vol. 1, pp. 269-71, 1959.
[42].D. B. Johnson, “Efficient algorithms for shortest paths in sparse networks”, Journal of the ACM, pp, 1-13, 1977.
[43].R. W. Floyd, “Algorithm 97: Shortest Path”, Communications of Assoc. Comput. Machinery. pp, 345, 1962.
[44].C. Froissart, and P. Mechler, “On Line Polynomial Path Planning in Cartesian
Space for Robot Manipulators”, Robotica, vol. 11, pp. 245-251, 1993.
[45].W. Nelson, “Continuous Curvature Paths for Autonomous vehicles”, In IEEE Internation Conference on Robotics and Automation, Scottsdale, AZ, 1989.
[46].G. Paolo, and G. Alessandro, “A Technique to Analytically Formulate and to Solve the 2-Dimensional Constrained Trajectory Planning Problem for a Mobile Robot”, Journal of Intelligent and Robotic Systems, vol. 27, pp. 237-262, 2000.
[47].S. Fleury, P. Soueres, J. P. Laumond, and R. Chatila, “Primitives for Smoothing Mobile Robot Trajectories”, IEEE Trans. on Robots and Automation , vol. 11, pp. 441-448, 1995.
[48].C. deBoor, “A practical Guide to Splines”, New York: Springer-Verlag, 1978.
[49].W. J. Gordon, and R. F. Riesenfeld, Computer aided geometric design : “B-spline Curves and Surfaces”, R. E. Barnhill, and R. E. Riesenfeld (Eds.), academic press, 1974.
[50].R. F. Riesenfield, “Applications of B-spline Approximation to Geometric Problems of Computer Aided Design”, Ph. D. thesis, Univ. of Utah, 1973.
[51].Y. G. Leu, W. Y. Wang, and T. T. Lee, “Robust Adaptive Fuzzy-Neural Controllers for Uncertain Nonlinear Systems”, IEEE Trans. on Robotics and Automation, vol. 15, no. 5, pp. 805-817, 1999.
[52].C. H. Wang, W. Y. Wang, T. T. Lee and P. S. Tseng, “Fuzzy B-Spline Membership Function (BMF) and Its Application in Fuzzy-Neural Control”, IEEE Trans. on Systems, Man, and Cybernetics, vol. 25, no. 5, pp. 841-851, 1995.
[53].P. S. Tsai, “Modeling and Control for Wheeled Mobile Robots with Nonholonomic Constraints” , Ph. D. thesis, Univ. of NTU, 2006.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top