[[alternative]]Evolution-based object tracking and localization based on tilt photographing

碩士[[abstract]]機器人的定位(Localization)，其用意在於得知障礙或目標的座標資訊，進而規劃路徑達到避障以及追蹤的效果，本論文為了摒除多感測器在資料整合上花費較多時間處理的缺點，以及提升機器人對於擬人化的發展與需求，將以CCD為主要的感測器在追蹤演算法及傾斜定位上提供不同以往的研究內容。其中追蹤演化法的研究中，考量到粒子濾波器(PF)所得到的結果會因環境因素而無法進行追蹤，因此本文提出了一種以粒子群聚最佳化(PSO)為搜尋主體並結合單體演算法(NM)的複合式(Hybrid)追蹤演算法則，在此法則下本文除了克服NM於影像中容易落於區域最佳解的缺陷，並成功的以此複合式演算法增加了處理資料量以及追蹤成功率。同時文中於傾斜定位上詳細描述藉由已知CCD架設的高度以及推算出各像素的照射角度，來完成已知目標物影像座標下的空間定位以及量測原理，並可結合地標(Landmark)完成傾斜角的自我量測，使機器人能達到多種傾斜角的定位。[[abstract]]This thesis investigates two important issues of robot navigation: object tracking and localization. In the object tracking system, we propose a hybrid evolutionary algorithm incorporating NM simplex method and particle swarm optimization to improve tracking performance in terms of processing speed and successful rate in comparison to particle filter (PF) tracking for complex environment. As for the problem of robot localization, this thesis provides an image-based localization method based on tilt photographing of a single CCD camera. Image captured by the CCD camera is pre-processing to locate the target object in the picture in terms of pixel count deviation from the CCD camera. By using an established formula based on relationship between tilt angle of the CCD camera and distance, coordinate of the target object can be calculated.[[tableofcontents]]中文摘要.........................................................................................................I 英文摘要.......................................................................................................II 目錄................................................................................................................III 圖目錄........................................................................................................VI 表目錄...........................................................................................................IX 第一章 序論..................................................................................................1 1.1 研究背景及動機.......................................................................................1 1.2 研究目的與方法....................................................................................3 1.3 論文架構....................................................................................................4 第二章 使用PF及PSO之追蹤..............................................................5 2.1 PF為基礎的影像追蹤................................................................................5 2.2 PSO為基礎的影像追蹤............................................................................7 2.3 PF與PSO於動態影像追蹤的驗證比較.............................................12 第三章 複合式追蹤演算法.............................................................20 3.1 NM於靜態照片下之追蹤.......................................................................20 3.2 結合PSO、NM的複合式追蹤演算法......................................................23 3.3 改良複合式追蹤演算法..........................................................................28 3.3.1 複合式追蹤演算法改良後性能驗證...........................................31 3.4 實驗環境及影像特徵......................................................................34 3.4.1 追蹤演算法的實驗環境..........................................................34 3.4.2 影像特徵...................................................................................37 3.5 追蹤演算法的實驗結果與討論.............................................................38 第四章 單CCD於傾斜照射下之定位................................................42 4.1 平行面的定位法則......................................................................42 4.2 傾斜照射的定位法則......................................................................44 4.2.1 傾斜定位基礎 ..........................................................46 4.2.2 x-axis, y-axis定位法則.................................................48 4.3 雷射輔助傾斜角量測.............................................................................51 4.4 機器人定位流程.............................................................................53 4.5 定位量測結果與討論.............................................................................55 4.5.1 座標定位實驗結果..........................................................57 4.5.2 距離量測實驗結果……......................................................58 第五章 結論與未來研究方向................................................................61 5.1 結論..........................................................................................................61 5.2 未來研究方向..........................................................................................62 參考文獻.......................................................................................................64 圖2.1 粒子濾波器的追蹤流程圖……………………………………………5 圖2.2 PSO的影像追蹤流程圖……………………………………………8 圖2.3 靜態追蹤的軟體介面………….…………..……..………………..10 圖2.4 PSO追蹤結果表示……………………………..…………………11 圖2.5 PSO R追蹤表示圖………………………………………………..12 圖2.6 PF於光源不足追蹤的環境圖……………………………………..13 圖2.7 PF於光源不足的追蹤結果………….…………………………….13 圖2.8 PF模擬環境追蹤的環境表示圖…………..…..…………………..14 圖2.9 PF於模擬環境的追蹤結果…..……………………………………14 圖2.10 PF於不同移動速度下追蹤的環境表示圖……..……...………...15 圖2.11 PF於移動週期10.65s下之追蹤結果……………….………..……15 圖2.12 PF於移動週期5.35s下之追蹤結果……………………………….16 圖2.13 PF於移動週期3.52s下之追蹤結果………………………………16 圖2.14 PSO於模擬現實環境的追蹤結果……………….……………….17 圖2.15 PSO於移動週期5.89s下之追蹤結果………………………………17 圖2.16 PSO於移動週期3.16s下之追蹤結果………………………………18 圖3.1 NM追蹤演算法之流程圖……………………………..……………21 圖3.2 NM靜態追蹤結果(擷取失敗)……….…………………………….22 圖3.3 NM靜態追蹤結果(擷取成功)……………………………………..22 圖3.4 結合PSO與NM的追蹤流程圖……………………………………..23 圖3.5 NM粒子產生範圍示意圖…………………………….…………….24 圖3.6 複合式演算法於白色背景下追蹤的成功張數……………………27 圖3.7 複合式演算法於白色背景下追蹤的成功率………………………27 圖3.8 NM於50點粒子選擇最好3點的示意圖…………………..……..29 圖3.9 PSO+NM(50->3)的追蹤流程圖…………………………..……..29 圖3.10 PSO+NM(50->3)+PSO R的追蹤流程圖…………..……………30 圖3.11 改善後複合式演算法於白色背景追蹤的成功張數…………….33 圖3.12 改善後複合式演算法於白色背景追蹤的成功率………………..33 圖3.13 動態追蹤的實驗環境示意圖……………………………………..34 圖3.14 物體移動的軟體介面……………………………………………..35 圖3.15 物體移動的軌跡…………………………………………………..35 圖3.16 動態追蹤的軟體介面……………………………………………..36 圖3.17 追蹤演算法綜合比較的成功張數…………………………………41 圖3.18 追蹤演算法綜合比較的追蹤成功率………………..……………..41 圖4.1 影像系統之光學幾何模型……………………………..……………42 圖4.2 平行面上定位示意圖…………………………………..……………44 圖4.3 CCD感測器在傾斜攝影距離之示意圖………………..……………45 圖4.4 推導 的幾何圖形…………………….……………..……………46 圖4.5 像素於y軸的空間投影示意圖………………………………………48 圖4.6 傾斜攝影時像素的投影空間…………………………..……………50 圖4.7 傾斜攝影時定位示意圖……………….……………….……………51 圖4.8 傾斜角量測示意圖………..…………….……………..……………52 圖4.9 機器人定位流程圖………..…………….……………..……………53 圖4.10 機器人定位示意圖……….…………….……………..……………54 圖4.11 機器人全方位定位流程圖…………………………………………55 圖4.12 量測傾斜角藉由距離p值…………………..………………………56 圖4.13 座標定位示意圖……………………………………………………57 圖4.14 兩點間距離量測……………………………………………………59 圖5.1 特徵分析範圍改善示意圖……………..……………………………63 表2.1 PSO靜態追蹤的效果…………………….…….…………………11 表2.2 PF與PSO追蹤結果比較……………….…………………………19 表3.1 複合式演算法於白色背景下追蹤，週期=10.28s…………………25 表3.2 複合式演算法於白色背景下追蹤，週期=5.89s…………………25 表3.3 複合式演算法於白色背景下追蹤，週期=3.16s…………………26 表3.4 複合式演算法於白色背景下追蹤，週期=2.27s.…………………26 表3.5 複合式演算法改善後在白色背景追蹤，週期=9.63s………………31 表3.6 複合式演算法改善後在白色背景追蹤，週期=5.25s………………32 表3.7 複合式演算法改善後在白色背景追蹤，週期=3.5s……..…………32 表3.8 蹤演算法綜合比較，週期=9.77s………….…………………………38 表3.9 蹤演算法綜合比較，週期=5.33s………….…………………………38 表3.10 蹤演算法綜合比較，週期=3.56s………….………………………39 表3.11 蹤演算法綜合比較，週期=2.68s……….…………………………39 表3.12 蹤演算法綜合比較，週期=1.79s………….………………………40 表4.1 座標定位的實驗結果………………………………………………58 表4.2 長度的量測…………………………………………………………59 表4.3 寬度的量測………………………………….………………………60 表4.4 兩點間距離量測………………………………………………………60[[note]]學號: 696450690, 學年度: 9