清潔機器人覆蓋率分析之研究 A Study of Coverage Analysis for Cleaning Robot 研究生 : 林育昇撰指導教授 : 陳智勇博士樹德科技大學電腦與通訊研究所碩士論文 A Th

樹德科技大學電腦與通訊研究所碩士論文清潔機器人覆蓋率分析之研究 A Study of Coverage Analysis for Cleaning Robot 研究生 : 林育昇撰指導教授 : 陳智勇博士中華民國一百零一年六月

清潔機器人覆蓋率分析之研究 A Study of Coverage Analysis for Cleaning Robot 研究生 : 林育昇撰指導教授 : 陳智勇博士樹德科技大學電腦與通訊研究所碩士論文 A Thesis Submitted to Department of Computer and Communication Shu-Te University In Partial Fulfillment of the Requirements For the Degree of Master of Science June 2012 中華民國一百零一年六月

樹德科技大學碩士班研究生指導教授推薦書本校電腦與通訊研究所林育昇君所提之論文清潔機器人覆蓋率分析之研究係由本人指導撰述, 同意提付審查指導教授 : 一百零一年六月一十二日

樹德科技大學碩 ( 博 ) 士班研究生學位考試審定書 100 學年度第二學期電腦與通訊研究所林育昇君所提之論文題目 : 清潔機器人覆蓋率分析之研究 A Study of Coverage Analysis for Cleaning Robot 經本學位考試委員會審議, 認為符合碩士資格標準召集人委員委員委員委員委員指導教授系所主管中華民國 101 年 6 月 12 日

樹德科技大學電腦與通訊研究所學生 : 林育昇指導教授 : 陳智勇清潔機器人覆蓋率分析之研究摘要本論文目的在於使用電腦視覺方式量測家庭清潔機器人行走路徑資料, 並分析機器人行走之覆蓋率與重複率, 藉以判定機器人清潔的效能首先, 以影片拍攝方式記錄清潔機器人路徑運行過程, 由鏡頭校正演算法將轉換影片畫面, 調校其因鏡頭拍攝時所導致的變形, 再以變形校正演算法將傾斜影像之還原, 最後透過影像處理方式擷取清潔機器人座標位置, 建立完整的清潔機器人行走路徑資料此外本研究使用不同大小的實驗場地以及模擬家庭環境設置障礙物, 設計多樣化的實驗場地分析出清潔機器人在單純或複雜環境中的覆蓋率及重覆率的情形由實驗結果可發現, 本研究所使用之路徑分析方法, 可以有效的得知清潔機器人路徑資料, 對於機器人覆蓋率研究能提供較高的準確性以及可信度關鍵字 : 鏡頭校正變形校正全域覆蓋率重覆率清潔機器人視覺化量測機器人路徑分析 i

Department of Computer and Communication, Shu-Te University A Study of Coverage Analysis for Cleaning Robot Student:Yu-Sheng Lin Advisors:Dr. Chih-Yung Chen ABSTRACT The purpose of this thesis focuses on path analysis, coverage and repetition rate of home cleaning robot using the method of computer vision measurement methods. Firstly, a camera is used to capture the robot motion video, and then a lens calibration algorithm is applied to correct the video sequence to calibrated images. Then, a distortion correction is used to adjust the tilt images to flat image. Finally, image processing methods are used to retrieve the robot location coordinates. Those data can establish the path information of cleaning robot. In addition, variety of simple or complex experimental field with different sizes and environment barriers are used to analyze the coverage and repetition rate of cleaning robots. The experimental results show that the path analysis method used in this study can effectively learn the cleaning robot path information. The approach proposed can provide high accuracy and credibility for research in robot coverage. Keyword:lens calibration, distortion correction, complete coverage path planning, repetition rate, cleaning robot, path analysis and visual measurement. ii

誌謝時光飛逝, 在論文完成的那一刻起, 也代表著研究所生涯即將告一段落這兩年的求學期間最要感謝我的指導教授陳智勇博士無論在專業領域或是處事態度的教導皆讓我獲益良多同時要感謝樹德科技大學電通系顏錦柱教授及義守大學電機系黃瑞初教授, 在百忙之中撥空擔任口試委員, 給予學生寶貴的建議, 使本論文更臻充實完善另外要感謝實驗室的仁賓光正佳運學長, 在研究及論文給我許多的建議, 也要感謝在這兩年的好夥伴奕寰以及學弟霆皓佳鴻碩彥運康等學弟們一起共同分擔實驗室的工作, 讓我感受到團隊合作的力量同時要感謝研究所的同學們和群企業的大學同學們嘉義的朋友們, 感謝你們陪我度過這苦悶的研究生涯, 當然最重要的要感謝每天陪著我聊天聽我抱怨的柔吟, 謝謝妳, 也辛苦妳這兩年的研究生涯, 最大的遺憾是來不及讓阿公阿嬤看到我完成碩士學位, 現在我想跟祢們說恁的孫仔育昇, 已經完成碩士學位矣在此, 我要將我的論文獻給我最親愛的家人, 感謝我的家人, 在這兩年的支持, 有家人的支持是我堅持的原動力, 即使遇到挫折與困難都可以迎刃而解, 才能完成本論文最後, 感謝這一路上曾經幫助過我的人, 謝謝你們, 謝謝林育昇謹誌于樹德科技大學電腦與通訊研究所中華民國一百零一年六月 iii

目錄中文摘要英文摘要致謝目錄表目錄圖目錄... i... ii... iii...iv... vi... vii 第一章緒論...1 1.1 研究背景... 1 1.2 研究動機與目的... 2 1.3 論文架構... 3 第二章文獻探討...4 2.1 清潔機器人發展現況... 4 2.2 清潔機器人介紹... 6 2.3 各式掃地機器人功能參數比較... 11 2.4 全域覆蓋路徑規畫概述... 13 2.4.1 全域覆蓋路徑演算法... 13 2.4.2 機器人避障方法介紹... 14 2.5 鏡頭校正相關研究... 16 第三章清潔機器人運行模式探討...17 3.1 一般清潔機器人行走模式... 17 3.1.1 牛耕 ( 之字形 ) 模式... 18 3.1.2 沿牆模式... 18 3.1.3 隨機模式... 19 3.1.4 螺旋模式... 20 3.1.5 多角形模式... 21 第四章視覺化覆蓋率量測...22 4.1 視覺化覆蓋率量測概述... 22 4.2 鏡頭校正... 22 4.2.1 鏡頭校正原理... 24 4.2.2 二維影像深度計算... 25 iv

4.2.3 相機成像模型... 27 4.2.4 透視投影... 27 4.2.5 相機參數... 29 4.3 變形校正... 32 4.3.1 取得影像邊緣輪廓... 32 4.3.2 Radon Transform... 33 4.3.3 縱橫比計算... 34 4.3.4 變形調校... 37 4.4 機器人路徑分析軟體... 39 4.4.1 數位影像處理定義... 39 4.4.2 鄰域處理 (Neighborhood Processing)... 40 4.4.3 邊緣偵測... 41 4.4.4 二值化概念... 42 4.4.5 形態學影像處理... 43 4.4.6 背景相減法... 48 4.5 覆蓋率計算方式... 49 第五章實驗與模擬結果...50 5.1 視覺化量測實驗結果... 50 5.1.1 鏡頭校正結果... 52 5.1.2 變形校正結果... 55 5.1.3 清潔機器人路徑分析 - 無障礙物環境量測結果... 57 5.1.4 清潔機器人路徑分析 - 模擬家庭環境量測結果... 76 5.2 模擬結果討論... 95 第六章結論與未來研究方向...97 參考文獻... 98 v

表目錄表一 : 清潔機器人功能比較表... 11 表二 : 五平方公尺無障礙環境覆蓋率分析... 58 表三 : 六平方公尺無障礙環境覆蓋率分析... 61 表四 : 七乘五平方公尺無障礙環境覆蓋率分析... 64 表五 : 凹形地圖無障礙環境覆蓋率分析... 67 表六 : 凸形地圖無障礙環境覆蓋率分析... 70 表七 : 梯形地圖無障礙環境覆蓋率分析... 73 表八 : 五平方公尺地圖模擬家庭環境覆蓋率分析... 77 表九 : 六平方公尺地圖模擬家庭環境覆蓋率分析... 80 表十 : 七乘五平方公尺地圖模擬家庭環境覆蓋率分析... 83 表十一 : 凹形地圖模擬家庭環境覆蓋率分析... 86 表十二 : 凸形地圖模擬家庭環境覆蓋率分析... 89 表十三 : 梯形地圖模擬家庭環境覆蓋率分析... 92 表十四 : 無障礙地形平均路徑數據... 95 表十五 : 模擬家庭環境路徑平均數據... 96 vi

圖目錄圖 1 irobot 570 燈塔設置 ( 資料來源 :Vacuum Cleaner Reviews)... 5 圖 2 清潔機器人隨機搜尋示意圖... 5 圖 3 irobot Roomba 570 清潔機器人... 7 圖 4 趴趴走清潔機器人... 7 圖 5 Samsung NaviBot 清潔機器人... 8 圖 6 irobot Create 教學模組機器人... 9 圖 7 AGAMA AiBOT RC520A 清潔機器人... 9 圖 8 AGAiT 易管家 EC MINI 清潔機器人... 10 圖 9 牛耕 ( 之字形 ) 模式... 18 圖 10 沿牆模式... 19 圖 11 隨機模式... 20 圖 12 螺旋模式... 20 圖 13 多角形模式... 21 圖 14 桶狀變形... 23 圖 15 枕狀變形... 24 圖 16 Epipolar 面立體成像圖... 26 圖 17 立體成像幾何圖... 27 圖 18 透視投影示意圖... 28 圖 19 Radon Transform 定義示意圖... 34 圖 20 光學成像數學模型... 35 圖 21 成像區域平面... 35 圖 22 鄰域處理示意圖... 40 圖 23 集合理論... 44 圖 24 大區塊與小區塊對稱結構元素膨脹示意圖... 46 圖 25 大區塊與小區塊對稱結構元素侵蝕示意圖... 46 圖 26 斷開運算示意圖... 47 圖 27 閉合運算示意圖... 47 圖 28 鏡頭校正程式畫面... 51 圖 29 變形校正程式畫面... 51 圖 30 路徑分析軟體程式畫面... 52 圖 31 桶狀變形... 53 圖 32 鏡頭校正後影像... 54 vii

圖 33 鏡頭校正實驗結果... 54 圖 34 變形校正前... 55 圖 35 變形校正後... 56 圖 36 變形校正實驗結果... 56 圖 37 五平方公尺無障礙環境運行路徑... 59 圖 38 五平方公尺無障礙環境機器人覆蓋率... 60 圖 39 六平方公尺無障礙環境中運行路徑... 62 圖 40 六平方公尺無障礙環境各機器人覆蓋率... 63 圖 41 七乘五平方公尺無障礙環境運行路徑... 65 圖 42 七乘五平方公尺無障礙環境機器人覆蓋率... 66 圖 43 凹形地圖無障礙環境運行路徑... 68 圖 44 凹形地圖無障礙環境機器人覆蓋率... 69 圖 45 凸形地圖無障礙環境運行路徑... 71 圖 46 凸形地圖無障礙環境機器人覆蓋率... 72 圖 47 梯形地圖無障礙環境運行路徑... 74 圖 48 梯形地圖無障礙環境各機器人覆蓋率... 75 圖 49 模擬家庭環境設置圖... 76 圖 50 五平方公尺地圖模擬家庭環境運行路徑... 78 圖 51 五平方公尺地圖模擬家庭環境機器人覆蓋率... 79 圖 52 六平方公尺模擬家庭環境地圖運行路徑... 81 圖 53 六平方公尺模擬家庭環境地圖機器人覆蓋率... 82 圖 54 七乘五平方公尺模擬家庭環境地圖運行路徑... 84 圖 55 七乘五平方公尺模擬家庭環境地圖機器人覆蓋率... 85 圖 56 凹形地圖模擬家庭環境運行路徑... 87 圖 57 凹形地圖模擬家庭環境機器人覆蓋率... 88 圖 58 凸形地圖模擬家庭環境運行路徑... 90 圖 59 凸形地圖模擬家庭環境機器人覆蓋率... 91 圖 60 梯形地圖模擬家庭環境運行路徑... 93 圖 61 梯形地圖模擬家庭環境機器人覆蓋率... 94 viii

第一章緒論 1.1 研究背景近年來分析各國研究報告與世界各大機器人廠商所發表的技術藍圖, 機器人無論在理論或應用上都有相當程度的發展, 在各種機器人中, 無論在工業航空軍事及家用服務型等各領域的應用及發展都越來越成熟, 相關技術整合亦不斷提升, 機器人大多從事組裝檢測運輸清潔保全救援數據採集等工作 [1], 其大多具備自主移動的能力, 未來也將朝向智慧化, 整合更多功能的方向前進在未來, 家庭服務型機器人是最具有未來市場潛力, 加上目前智慧型通訊手機已成為市場主流, 結合網路的家庭服務機器人, 更可說是一種居家使用的資訊家電, 使其具備人工智慧與更多人性化的功能, 機器人系統中結合許多理論於實務基礎的產物, 如控制工程人工智慧電力電子機械工程工業設計計算機設計等, 研究領域包含避障功能路徑規畫影像視覺技術語音聲控技術地板清潔防掉落技術回充功能電力系統伺服控制等等這些清潔機器人各種技術正以穩定的速度發展, 而人們對於清潔機器人的需求也將日益漸增, 其中清潔機器人清潔效率以及高覆蓋率路徑亦是當前研發重點目標之一, 如何提升清潔機器人覆蓋率, 減少路徑重覆率也是目前清潔機器人發展中相當關注的功能, 在目前市售清潔機器人皆強調其具有高效率的清潔功能, 卻無任何科學數據足以佐證以及比較 1

1.2 研究動機與目的在全球各家廠牌的清潔機器人中, 大多數強調自身的清潔機器人可以有效率的完成居家清掃工作, 但使用者無法從商品資訊中得知清潔機器人清掃之效率以及效能, 雖然過去的研究 [2][3][4] 中, 利用機器人運作模擬軟體來模擬清潔機器人在家中清潔時之情形, 藉以計算其覆蓋率, 但機器人模擬情況與實際情況會有所差異, 其機械狀態也是軟體模擬無法準確掌握機器人覆蓋率量測至今尚未有較成熟的覆蓋率計算公式及方法日前有多種方法進行機器人運行量測, 如利用影像記錄方式呈現機器人真實情況, 但大多都因攝影器材位置擺放以及鏡頭所造成的畸變變形等問題無法克服, 而無進一步的發展因此本論文研究提出使用影像處理的方式, 以影片格式拍攝, 可隨時掌握機器人目前位置, 進而計算掃地機器人實際的覆蓋率本評估軟體預期將影片拆解為多張影像, 再以鏡頭校正及變形校正演算法將影像修正因鏡頭及拍攝角度的幾何變形, 並辨識機器人所在位置, 還原至直角座標進而取得機器人路徑分析資料視覺化覆蓋率量測架構包含 : 鏡頭校正演算法變形校正演算法以及機器人路徑分析軟體, 透過上述三大架構方法, 達成視覺化覆蓋率量測本論文研究方法可計算出最接近清潔機器人在真實環境運作時實際整體覆蓋率 2

1.3 論文架構本論文主旨於利用影像處理架構下, 透過鏡頭校正變形校正以及路徑分析軟體來達成影像量測, 實現清潔機器人視覺化覆蓋率量測以及覆蓋率分析, 其主要章節敘述如下 : 第一章緒論 : 說明本篇論文之研究背景研究動機研究目的以及論文架構第二章文獻探討 : 說明目前清潔機器人發展現況, 以及關於其關鍵技術介紹, 如全域覆蓋路徑演算法概述機器人避障方法及原理, 以及鏡頭校正相關研究發展第三章清潔機器人運行模式探討 : 探討清潔機器人路徑模式, 分析各機器人路徑模式其優缺點第四章視覺化覆蓋率量測 : 介紹本論文研究所建構之視覺化覆蓋率量測軟體介面, 並說明影像處理之方法第五章實驗模擬結果 : 首先對於鏡頭產生的枕狀變形或桶狀變形進行校正, 對各家廠牌清潔機器人實行視覺化覆蓋率量測實驗, 透過路徑分析軟體得知各廠牌機器人行走模式以及覆蓋率分析, 最後探討計算之結果與討論第六章結論與未來展望 : 說明本篇論文之結論以及未來研究方向 3

第二章文獻探討在第二章文獻探討中, 我們將介紹清潔機器人相關研究可大致上分為全域路徑規畫偵測障礙物避障系統以及清潔模式導航等功能在機器人運作路徑分析與控制的系統設計中, 首要目標為控制機器人可在最短時間或路徑內, 完成全域覆蓋路徑規劃, 且在運作時實現避障功能, 在目前有許多相關研究中, 都將這些功能作為清潔機器人首要達成的功能目標此外在此章節中, 我們也討論目前關於鏡頭校正的相關研究報告, 提供本論文研究更多可參考的研究發展及方法 2.1 清潔機器人發展現況在清潔機器人清掃模式中, 各家清潔機器人廠牌發展出各式清潔模式, 其清潔模式分類如牛耕 (S 形 ) 模式沿牆壁模式隨機行走模式螺旋模式多角形模式等, 使用者可以依據欲清潔區域選擇清潔機器人清掃模式但在清潔機器人運行移動法則中, 無法隨地形自動變換清潔模式, 容易造成清潔機器人在清掃過程中受困死角無法順利運行的情況, 也無法在短時間內有效率完成欲清潔區域的清潔工作, 當機器人清潔效率不佳受困於死角或遺漏未清潔區域時, 還是須依照使用者的經驗法則人工切換其清潔模式, 或者以手動遙控方式來達成清潔效果為有效解決此類問題, 以 irobot 清潔機器人為例, 其使用紅外線發射的方式, 設置電子牆 (Wall Light) 或燈塔 (Light House) 在欲清潔區域, 如下圖 1 所示, 以辨識機器人路徑區域以及記錄清潔區域, 以達成高效率的清潔工作 4

圖 1 irobot 570 燈塔設置 ( 資料來源 :Vacuum Cleaner Reviews) 以建置電子牆或燈塔來記錄清潔機器人所清潔的區域, 雖然可經由記錄來增加其清潔範圍以及提高自動回充電站的可能性, 以機率性的方法解決清潔效率, 但清潔機器人仍使用隨機方式來搜尋使用者所設置的燈塔位置, 當搜尋當中若碰撞到各式障礙物, 即會增加搜尋不到燈塔的機會, 降低其清掃效率, 甚至無法回充電站等問題機器人在未知的環境中, 如果可以獲得自身定位位置以及室內地形配置, 就有可能可提升其清掃效率以及回充電站等問題, 這也是目前在清潔機器人研究發展中相當重要的課題之一如下圖 2 所示, 清潔機器人可能因為碰撞障礙物, 導致無法完成所需清潔的區域清潔區域燈塔障礙物? Robot 圖 2 清潔機器人隨機搜尋示意圖 5

近年來以具有自主行動能力的移動清潔機器人, 其控制方式與行動能力不斷地研究及改良, 在居家清潔機器人研究是未來重要的發展趨勢, 經濟部工業局預估,2010 年台灣機器人產業產值有新台幣 450 億元實力, 至 2015 年可望增至 2500 億元根據國際機器人聯盟 (IFR) 估計,2006 年至 2009 年, 全球人工智慧型的事務型機器人將有近 400 萬台的銷售量, 平均每年 100 萬台, 並穩定高幅度成長 2.2 清潔機器人介紹在目前清潔機器人已是販售中的商品, 在本論文實驗結果的數據中, 使用了六台市面上所販售的清潔機器人以及一台本實驗室所自行研發的清潔機器人, 依照世界各國所設計的清潔機器人來分析其運作原理以及行走方式, 詳細說明可參考文獻 [5], 其摘錄與介紹如下 : irobot Roomba 570 irobot 為美國專業設計機器人的開發公司 [6], 該公司開發出的 Roomba 掃地機已有改版多年的歷史, 除了專利掃刷設計及吸塵機構設計外, 圓型的掃地機型成為了往後的掃地機器人外型的設計的參考典範, 然而避障的方式使用紅外線偵測障礙物的距離, 偵測到物體後並減緩速度行徑, 並確定碰撞的保桿碰觸到障礙物後才判斷是障礙物或牆面, 進行閃避或其他的規劃清掃方式, 依據邏輯計算清掃區域大小並自動計算清掃時間及路徑如下圖 3 所示 6

圖 3 irobot Roomba 570 清潔機器人趴趴走 RV-13 趴趴走 RV-13 如圖 4, 為台灣松藤實業所設計出的吸塵機器人 [7], 松藤實業將智慧行走模式設計於其中, 包含 : 隨機自走式橢圓形走式沿牆巡航遊走式 Z 字型走式方式, 利用紅外線遙控功能, 微調機器人控制方向左右角度, 另外兩側旋轉毛刷增加清潔範圍, 靜電除塵紙也有擦地功能, 還有獨特的回充電站專利, 弱電時或當時間程式走完, 機器人會自動回到充電站充電以持續沿牆的行徑方式找到充電站, 但避障的方式完全依賴前方的防撞保桿, 必須以碰撞的方式得知前方是否有障礙物, 機器人才能繼續規畫清掃路徑圖 4 趴趴走清潔機器人 7

Samsung NaviBot Samsung NaviBot 為韓國三星電子所生產的掃地機器人 [8], 如圖 5 所示, 此機器人加入 Auto Dust Emptying 自動排塵功能, 當集塵盒需要清除積塵時會聰明地回到充電座, 將其集塵袋清空至中央集塵盒, 重新充電並可再次進行清掃動作, 完全自動化在清掃模式方面, 機器人使用導航系統的相機與感應器記憶目前已清掃區域, 所以當充電與自動維護動作完成後, 機器裝置就能夠啟動並完成清掃工作使用內建相機與新一代先進感應器如紅外線偵側, 描繪家中地圖, 以內建相機每秒拍下三十格影像, 繪出家中的地圖, 並規劃最佳路線以覆蓋全範圍, 達成更有效率的清掃模式圖 5 Samsung NaviBot 清潔機器人 irobot Create irobot Create 為 irobot 公司所生產的教學模組, 圖 6 所示, 其不需要任何組裝即可以開始控制機器人, 可由 PC 端發出指令或是增加多功能可程式化的命令模組直接控制其模組內建十個可展示的運行模式動作, 其配件與功能性完全與 irobot Roomba 相容, 包括運行模式充電電池電源供應設備 Home Base 遙控器虛擬牆等配件 8

圖 6 irobot Create 教學模組機器人 AGAMA AiBOT RC520A AiBOT 清潔機器人 [9], 圖 7 所示, 其產品強調機器人掃刷直徑清潔範圍達 32 公分, 具有預約定時啟動清潔工作的功能, 清潔模式有 Z 字型模式沿牆模式螺旋模式隨機模式四種清潔模式, 適合於各種材質地板進行清掃, 如地毯亞麻毯木板磁磚與大理石在避障方面, 跨越障礙設計, 可排除電線及地毯等障礙物, 以紅外線感應裝置可防止機器人在運作時掉落階梯, 並設置抹布功能, 清潔同時可將細微灰塵一併清除圖 7 AGAMA AiBOT RC520A 清潔機器人 9

AGAiT 易管家 EC MINI 易管家清潔機器人是由凌海科技所生產 [10], 如圖 8 所示, 其產品特性為, 沒有過多的彎曲加上超薄的設計, 取代直立吸塵器輕鬆地清潔像床底等無法到達地方, 清潔模式預設為三種人工智能行走模式, 以光電傳感器可以探測防掉落, 加長的雙圓形側刷, 增加清潔面積及效率, 以 One Touch 操作介面, 可以簡單操作, 運行中如遇到障礙物, 機器人卡住時會自動停止, 並發出提示音圖 8 AGAiT 易管家 EC MINI 清潔機器人 10

2.3 各式掃地機器人功能參數比較表一 : 清潔機器人功能比較表功能型號 irobot Roomba 570 趴趴走 RV-13 AGAiT 易管家 Samsung NaviBot AGAMA AiBOT 障礙物偵測紅外線無無紅外線紅外線碰撞感測碰撞保桿碰撞保桿碰撞保桿碰撞保桿碰撞保桿燈塔 / 虛擬牆紅外線燈塔無無感應磁條無越障高度 9 cm 2.5cm 2.5cm 6cm 3cm 清掃行徑隨機 / 螺旋沿邊隨機 / 螺旋隨機 / 螺旋牛耕 / 方型沿邊隨機 / 螺旋沿邊 /Z 字型清掃規劃演算法規劃清掃方式隨機清掃隨機清掃影像辨識區域性規畫隨機清掃其他專利掃刷多項專利價格低廉價格低廉行徑距離影像佈建路徑價格中上由前述章節可以得知, 目前清潔機器人研究發展中, 所遭遇到的問題如下 : (1) 非接觸式避障在目前清潔機器人非接觸式避障技術中, 大部份的機器人都採用紅外線與超音波偵測技術, 但紅外線會因物體反射特性不同而導致紅外線訊號接收失敗, 而超音波偵測部分, 因為音波速度較慢, 在反射物體上會形成回音誤判的現象 (2) 接觸式避障在接觸式避障技術中, 避障緩衝器 (Bumper) 是目前清潔機器人最常使用的接觸式避障感測方法, 但緩衝器為一般機械裝置, 容易因為不當外力或是經常性使用而損壞, 而在接觸障礙物時更容易因為碰撞而推倒家具等物品, 此機構設計雖然 11

簡單, 但因避障緩衝器外型涵蓋機器人前端部分, 也會增加機器人在外型設計上的困難等缺點 (3) 地形因素在目前台灣家庭環境中, 室內空間並不是相當寬闊, 若清潔機器人進入一狹小空間, 只有單一出入口時, 機器人皆是使用隨機模式來離開, 但離開此清潔區域的機會較小, 若無法順利離開而導致受困, 則必須以人工或手動遙控的方式來操作機器人離開該清潔區域 (4) 異物干擾在清潔機器人運行時, 在清潔區域中會有異物干擾機器人前進, 若遇到絞線情況則會導致輪胎空轉清潔機器人會因為這些干擾因素而無法繼續前進或脫困, 導致清潔工作無法順利的完成 (5) 回充電站清潔機器人在低電壓或打掃完畢時, 會自動搜尋充電站進行充電目前市面上大部分清潔機器人所使用的方法為搜尋充電站所發出的紅外線, 機器人會以沿牆壁模式或隨機模式來搜尋紅外線訊號, 但是如所在區域空間過大或障礙物太多時, 會增加搜尋的困難度, 甚至無法達成回充電站的工作 12

2.4 全域覆蓋路徑規畫概述全域覆蓋路徑規劃是清潔機器人必須具備的基本功能, 目的在於以最短路徑最小累積旋轉角度最少重覆路徑與最大覆蓋面積在具有障礙物的清潔環境中, 依照機器人各種全域覆蓋路徑演算法, 達成高效率清潔功能則此功能定義為全域覆蓋路徑規劃 (Complete Coverage Path Planning) 2.4.1 全域覆蓋路徑演算法全域路徑規劃演算法為清潔機器人中最為常見的路徑規劃方法, 目前已有許多應用於此的演算法, 如 Pirzadeh 等人 [11] 使用人造位能場 (Potential Field) 達成地圖空間覆蓋與搜尋問題, 但其缺點為機器人容易產生振盪現象 (oscillation) 或陷入局部最小點 (local minimum point) 中 ;Choset[12][13][14] 提出牛耕式 (Boustrophedon) 格點分解法來覆蓋整個地圖空間, 且可針對非結構性的障礙物周圍清潔, 其方法簡單且容易實現在空曠區域的搜尋覆蓋率為最高, 因此許多機器人區域搜尋的應用都採用此方法 ( 例如 : 水底探測機器人 [15] 六足探測機器人 [16]) 因為此方法容易受到障礙物阻隔而打亂搜尋路線, 而學者 Howie 也提出了改良的牛耕搜尋法 [17];Zelinsky 等人 [18][19] 利用格點分解法 (Cells Decomposition) 與距離轉換法 (Distance Transform) 來進行全域覆蓋路徑規劃, 此演算法可指定機器人起始位置及終點位置, 但其路徑彎曲未能達到最佳化效果 ;Oh 等人 [20][21] 則利用三角格點 (Triangular Cell) 取代矩形格點, 利用移動樣板 (Motion Template) 進行路徑規劃, 使移動方向由 8 種增加為 12 種, 方向增加可縮短行走距離以及避障較為靈活, 但環境複雜度會增加, 演算速度相對也會增加 ;Yang 等人 [22][23][24] 則是提出類神經 13

網路 (Neural Network) 來規劃行進路線, 使用神經網路學習環境特徵, 建立工作環境地圖, 讓機器人在已知環境全域搜尋同時機器人必須使用特定設備, 以採集工作環境的必要資訊 ( 例如 : 全向鏡視覺設備在高處架設攝影機 ), 而此類設備需提高生產成本, 同時神經網路的複雜運算也增加硬體實現的困難度, 因此在實際應用上較困難 ;Juang 等人 [25][26] 提出沿牆搜尋法 (Wall Following Approach) 行徑以牆面為參考, 沿著牆面或障礙物搜尋, 其搜尋法則單純, 容易受困於牆面與障礙物中市售產品大多提供此模式供使用者選擇, 只適用於特定區域清掃 2.4.2 機器人避障方法介紹清潔機器人在運行行徑路線中, 如何避開障礙物的方法已被許多學者提出 [27][28], 避障條件分為已知環境與未知環境兩種居家掃地機器人大部分工作於室內環境, 如客廳廚房臥房等, 這些環境的擺設變動性較高, 在目前市面上的清潔機器人避障技術中, 本論文列舉出數種常用的技術, 乃針對未知的工作環境來設計許多相關研究都建立在已知的環境中, 對於在未知環境中避障, 需探索未知的環境, 並建立座標系統或區域方位, 其相關的避障技術如下 : (1) 影像視覺避障 (Vision-based) 影像視覺避障 [29] 可使用在清潔機器人, 裝置攝影機於機器人上, 由攝影機擷取影像, 經由影像處理技術辨識障礙物的方向與大小, 但因影像易受到光線及其他因素影響, 造成影像處理效果不佳同時影像處理須搭載高效能處理器, 影像處理運算複雜且耗時硬體需求過高, 不符合成本效益, 因此清潔機器人大多不採用此方法為避障技術 14

(2) 超音波 (Ultrasonic) 使用超音波避障利用其感測器接收反射回來的訊號, 計算其發射與接收的時間差來取得前方障礙物體的距離, 但因為超音波特性的關係, 它所發出的訊號會彼此干擾造成距離的誤判學者 Bogdan 提出一個以陣列型是排序的超音波發射器與接收器, 此方法為依循序的方式發送出超音波訊號, 偵測前方障礙物距離以及大小, 同時多感測器的設計方式, 可以由演算法來排除失真訊號 [30] (3) 雷射偵測 (Laser) 使用雷射測距感測器 [31] 來偵測方位角度以及障礙物的距離, 大多用於機器人行進中避障以及環境參數的建立雷射偵測特性其發射束較小, 為準確的偵測全區環境必須耗費相當多的時間, 且雷射感測器建置成本較為昂貴, 但雷射感測器是目前相當準確的測距感測器, 所以輪型機器人研究中常被採用的感測器之一 (4) 紅外線 (Infrared) 紅外線 [32] 避障方法, 利用紅外線反射時間取得障礙物的距離, 依照此距離作為避障策略的輸入參數, 其量測值相當精確但若障礙物顏色是黑色系時, 因紅外線特性, 其紅外線光會被黑色系物體所吸收, 使紅外線無法量測, 因此限制了紅外線避障的發展性, 不過學者 Suolin Duan 為了解決此問題, 提出了整合視覺與紅外線的避障技術 [33], 使得紅外線避障技術有更多的發展性 15

2.5 鏡頭校正相關研究數位影像設備, 如 CCD 照相機攝影機等經常被應用在許多各式關於影像處理的研究領域, 如 Taylor 等人在 1998 年提出的機器人視覺 [34];Hicks 等人在 2005 年提出的電腦視覺 [35];Murray 等人 [36] 1994 年提出的移動物件的偵測與追蹤以及在 2004 年 Lin 等人所提出的立體座標量測 [37] 這些不管是電腦視覺或是移動物件的偵測與追蹤都是需要相當高精密度的應用與檢測, 而影像處理技術中, 鏡頭校正技術在這些研究領域中即佔有相當關鍵的重要技術在鏡頭校正的研究上, 目前有相當多的研究針對克服校正技術上的各種困難以及改善此技術為首要目標而最早提出照相機鏡頭校正是 1971 年由 Abdel[38] 等人提出, 以直接線性轉換方法應用在鏡頭校正, 此轉換方法至今仍有許多工程人員所使用, 但直接線性轉換法所求出的校正參數並不是獨立的,1988 年 Hatze[39] 提出在直接線性轉換法中, 在系統中加入非線性的條件, 可解決直接線性轉換法並非相互獨立的問題而在 1992 年 Weng 等人 [40] 2000 年 Zhang 等人 [41] 以及 2003 年 Ma 等人 [42], 則提出了許多在直接線性轉換法中因考慮透鏡而造成畸變所引起的相關問題 Wang[43][44] 分別在 2004 年與 2005 年, 提出針對多照相機三維座標量測系統提出了校正方法以上提出的研究方法皆以針孔成像模型為基礎, 即以透視投影法來對照相機系統成像進行建模就針孔成像模型, 我們將相機鏡頭設為一個很小的透鏡, 主距離視為定值, 鏡心固定在光學中心, 但就實際相機鏡頭而言, 鏡頭中心與主距離會因鏡頭焦距和入射光線而產生差異, 因此當我們以透視投影法進行光學建模時, 通常會因為成像的誤差而限制了照相機系統在量測應用上的範圍與準確性 16

第三章清潔機器人運行模式探討 3.1 一般清潔機器人行走模式清潔機器人的路徑規畫, 清掃的模式大致上可以分為下列幾種 : (1) 牛耕 (S 形 ) 模式 : 進行狹長地形清潔 ( 開放空間或空曠環境 ) (2) 沿牆壁模式 : 進行牆角家具等邊緣清潔 ( 牆邊較髒的環境 ) (3) 隨機行走模式 : 移動到其他清潔區域 ( 不規則的環境 ) (4) 螺旋模式 : 進行特定區域清潔 ( 開放空間或空曠環境 ) (5) 多角形模式 : 進行特定區域清潔 ( 開放空間或空曠環境 ) (6) 回充電站模式 : 機器人低電量自動啟動此模式而機器人的路徑規畫是需要透過地圖環境資訊, 來規畫出最適合清潔空間的運行模式, 但若是在一個未知的環境地圖時, 即需要人為操作來選擇其清潔模式, 同時感測器輔助來感應周圍環境, 建立更完整的環境地圖資訊, 才能達到最佳化的路徑規畫 17

3.1.1 牛耕 ( 之字形 ) 模式清潔機器人牛耕 ( 之字形 ) 模式, 此模式運行的方式, 當清潔機器人在運行的過程中, 碰到障礙物並且觸發感測器時, 此時機器人會先順時針旋轉 90 度, 接著直走一小段的距離, 此距離必須依照每個機器人的吸塵器吸口的大小來決定行走的距離, 再順時針旋轉 90 度 ; 清潔機器人繼續行走, 直至碰撞到下一個障礙物時, 當碰撞到障礙物時, 機器人會轉向換逆時針旋轉 90 度, 再直走一小段距離後, 同樣的此段距離也是依照吸塵器吸口的大小來決定行走的距離, 再逆時針旋轉 90 度就可以完成牛耕 ( 之字形 ) 路徑的清潔模式從過去研究文獻以及目前市面上各式清潔機器人的運行模式可以得到, 牛耕 ( 之字形 ) 路徑的清潔模式是呈現最佳的清潔效果如下圖 9 為牛耕 ( 之字形 ) 模式示意圖圖 9 牛耕 ( 之字形 ) 模式 3.1.2 沿牆模式沿牆清潔模式適用於一開始清潔機器人在家庭的使用, 由於對居家環境的擺設位置未知, 所以必須先熟悉居家環境, 由沿牆模式可以經由沿牆行走, 將四周 18

的居家環境以及擺設位置建立一個環境地圖資訊, 方便機器人運行時可以馬上做好路徑規畫對一個未知的環境或具有導航功能的清潔機器人而言, 沿牆行走是最基本的清潔模式當啟動清潔機器人時, 起始點可以隨意設置, 機器人會開始搜尋離自己最靠近的一個平面位置, 然後行進到平面位置最近一點, 開始沿牆行走, 在未知的環境下, 須經由感測器測得與平行面的固定距離前進, 持續前進到環繞一周後遇到重覆清潔路徑時, 則沿牆清潔模式結束如下圖 10 為沿牆模式示意圖圖 10 沿牆模式 3.1.3 隨機模式隨機模式, 此模式運行方式為機器人啟動隨機模式後, 將會往直線前進行走, 當碰撞到任何障礙物並且觸發感測器時, 清潔機器人會任意旋轉一個角度, 由於各廠牌的清潔機器人隨機模式所旋轉的角度皆不盡相同, 但大致上可以分為 45 度 90 度 135 度以及 180 度等, 隨機模式在理論上也能完全覆蓋清掃區域, 但是由於過多的重覆路徑導致清潔效率不高如下圖 11 為隨機模式示意圖 19

圖 11 隨機模式 3.1.4 螺旋模式螺旋模式, 清潔機器人會定速螺旋行走, 直走時機器人會有向右偏 30 度, 左輪與右輪的速度不一樣, 並逐漸向外擴張 ; 由於機器人打掃位置並不一定, 螺旋模式可以放置於一定的位置, 或者是要清掃某部分較為髒亂的區域, 為了快速的清掃此髒亂區域, 就可以啟動螺旋模式來清掃如下圖 12 為螺旋模式示意圖圖 12 螺旋模式 20

3.1.5 多角形模式多角形模式, 當啟動多角型模式時, 機器人會先直線行進一小段距離後, 向右轉一個角度, 多角型模式與隨機模式不同的是, 多角形模式會固定行走距離, 轉彎方向與轉彎角度皆是固定不會改變, 其清潔功能模式接近於螺旋模式, 皆可以清掃固定一處較髒亂的地方下圖 13 為多角形模式示意圖圖 13 多角形模式 21

第四章視覺化覆蓋率量測 4.1 視覺化覆蓋率量測概述在目前市售的清潔機器人中, 所強調的產品功能以及產品特色, 多半只強調其清潔效果路徑覆蓋人工智慧或者是清潔效率, 其中清潔效率的部分, 目前為止並沒有一套完整且具有說服力的公式可以計算出清潔效率本論文所探討方法, 即是以視覺化覆蓋率量測的方式來計算機器人整體覆蓋率, 透過鏡頭校正變形校正以及路徑分析軟體, 還原地圖實際環境, 並計算機器人座標中心點位置, 但由於每家廠牌清潔機器人的行走速度不一, 因此我們使用路徑分析軟體計算機器人行走距離, 以相同距離比較各家廠牌清潔機器人覆蓋率本論文方法所取得的機器人覆蓋率數據更精確於模擬軟體, 因模擬軟體無法模擬機器人機械狀態以及在真實環境中所發生的實際情況, 所以本方法可以更有效更精確的取得機器人覆蓋率數據 4.2 鏡頭校正一般市面上的數位相機鏡頭, 不同的鏡頭在拍攝影像時容易產生變形, 其中超廣角鏡頭雖然能創造一般鏡頭無法拍攝出的空間感, 但其嚴重的桶狀變形也是最為人所詬病的除了遠近感上的差異, 在不同焦距的鏡頭成像上還有一種值得一提的差異性, 那就是變形, 其中又以廣角鏡頭的桶狀變形最常被討論鏡頭變形的原因主要來自像差 (Abbreviation), 也就是實際成像與理想影像之間的差異, 是由於透鏡對色光的彎曲能力不同, 使成像點與光軸距離不同, 其側 22

向放大率亦隨之不同所造成變形分為有兩種, 分別為桶狀變形枕狀變形 : (1) 桶狀變形 (Barrel Distortion) 亦可稱作負變形或者負形扭曲 (Negative Distortion), 此種變形是影像成像缺陷, 常隨著廣角鏡頭的使用而產生, 造成影像有球面或膨脹的感覺桶狀變形的影像, 其影像點會隨著中心點的距離增大而移位, 整體影像會變小影像中直線的中段會向外彎曲, 兩端則像中心彎曲, 變成曲線方形物體影像會變形四角往內收縮, 邊緣中段的直線則會向外凸出, 影像成像區域就會像一個木桶形狀, 因此被稱之為桶狀變形如下圖 14 圖 14 桶狀變形 (2) 枕狀變形 (Pincushion Distortion) 亦可稱作為正變形或者正形扭曲 (Negative Distortion), 枕狀變形較常發生於使用長焦段鏡頭或者是變焦鏡的望遠端時此種變形也是影像成像缺陷, 其效果會造成影像中間有夾縮的感覺, 枕狀變形的影像, 影像中直線的中段會向內彎曲, 兩端則外彎曲, 變成曲線方形物體影像會變形四個角往外擴張, 邊緣中段的直 23

線則會向內凹, 影像成像區域就會像一個枕頭形狀, 因此被稱之為枕狀變形枕狀變形是以參考線彎曲程度和圖形的高的百分比來衡量以大多數的相機, 枕狀變形機率比桶狀變形機率來的較低如下圖 15 圖 15 枕狀變形 4.2.1 鏡頭校正原理照相機鏡頭校正是為了利用二維影像重建三維環境的步驟, 由於單一的照相機鏡頭能夠獲得的影像侷限在二維座標, 所以無法由後續的影像處理及運算來求得三維座標和物體深度照相機鏡頭校正的首要步驟, 它是定義世界座標系與影像座標系間幾何關係的重要技術在照相機校正法中是利用針孔成像理論來進行成像建模, 以相機鏡頭中心當作針孔, 作為針孔成像的轉換, 其目的是在於求得相機系統的內部參數與外部參數, 可減少相片產生的形變及還原當時拍攝實物體與相機的三維空間環境在現在的數位變焦鏡頭中, 鏡頭內部參數會因焦點的改變而有所不同, 而外部參數則是將相機座標系統轉換成參考座標系統關於相機參數的在之後章節會有更詳細的介紹, 因此在此不多加論述另外透過透視投影 24

法作為系統成像, 進而組成投影矩陣, 將物點世界座標經由投影矩陣, 換算成相對應的影像座標投影矩陣可三維空間中的座標轉換為二維圖片上的座標, 當改善三維空間模型時即會使用到 4.2.2 二維影像深度計算當三維空間座標投影至二維影像平面後, 就會失去影像深度資訊, 亦即一個影像平面上的點是無法取得三維空間的座標, 我們可利用立體成像技術取得失去的深度資訊首先我們假設兩個相機座標系統已經過校正對準且平行架設, 其相機座標系統與世界座標系統是一致的, 則影像 XY 平面就會與世界座標系統 XY 平面重合一般來說, 我們可以利用雷達和三角定位法, 在三角定位法中, 可根據兩個相似三角形, 如圖 16 所示, 在物體上目標點 A 和左相機中心焦點 B 以及右相機中心焦點 C 所形成的三角平面稱作為極線面極線面與左右影像交集出兩段線則稱之為 Epipolar 線左影像上成像 E 點即是 A 點, 右影像則成像在 F 點,F 點與 E 點稱為共軛配對, 點的距離則為視差, 在圖 17 中, 兩個相似三角形比例關係 FCD FAH 與 GEI GBH 可得, x z x f l x b z x f l (4.1) (4.2) 在 4.1 式與 4.2 式中, 設兩部相機相距 b, 可進一步推得 25

zx x f ( zxl bf ) x f l (4.3) (4.4) 再利用 zx l zx bf, 可推得 r z bf x x l r bf s (4.5) 其中 s x l x ) 為視差值, 視差值 s 是可以被求出來的, 透過量測與焦距經由 ( r 內部參數校正後可以求出 b, 即可利用 4.5 公式計算出深度值 z A 目標點極線面 Epipolar 線左影像 D E 右影像 B 左邊相機焦點 C 右邊相機焦點圖 16 Epipolar 面立體成像圖 26

A B H x r C D E I x l f F b 圖 17 立體成像幾何圖 G 4.2.3 相機成像模型在擷取影像資訊時, 必須先了解影像如何在相機中成像, 為了能取得影像的三維資訊, 我們使用透視投影法的幾何關係, 來建立簡易的模型, 藉以求出現實空間中投影至二維影像上的投影關係矩陣以下章節將介紹電腦視覺的透視投影法成像原理以及相機內外部參數 4.2.4 透視投影在電腦視覺中一般最常見的投影法為透視投影, 也就是針孔成像模型原理, 是由相機透過針孔成像將實景投影至投影面上, 是為了模擬人類視網膜成像原理, 27

將三維座標轉投影到二維影像平面上如圖 18 所示, 其中 f 為焦距, Z 為相機光軸方向, 對應相機座標表式為 P ( X, Y, Z), 相機座標為 X, Y, Z ), 三維空間中的 P 點座標投影至影像平面上一點 p, 其座標為 p ( x, y) ( c c c c Y c P( X, Y, Z) X c y p( x, y) x Z c f 影像平面圖 18 透視投影示意圖因為透過三角幾何, 影像平面座標我們將會另外表示為 f f p ( x, y) ( X, Y ) Z Z (4.6) 在利用透視投影法之後, 相機的投影並不是相當理想的投影在影像平面上這是因為相機內部參數無法得知, 若想獲得相機內外部參數必須使用具高精密度特殊用途的影像裝置本論文所使用的相機為一般較為普遍的類單眼相機, 相機製造商並未提供使用者相機參數, 因此必須使用影像修正技術來求出相機內外部參數, 透過所獲得的相機內外部參數進行校正調整和補償 28

4.2.5 相機參數在三度空間中物體透過相機的成像畫面, 會因為相機擺設位置拍攝角度問題或者是相機本身所組成元件的不同, 而產生不同的成像畫面相機的成像幾何模型決定物體在三度空間座標與影像平面座標的對應關係, 此幾何模型的參數一般稱作相機參數, 相機參數校正中包含許多數學式與光學模式, 相機校正主要分為兩個主要的要素 : 可以分為內部參數與外部參數, 為各相機鏡頭模組中座標系統相互轉換的關係 (1) 內部參數 (Intrinsic parameters): 相機內部參數屬於相機本身光學特徵和幾何模型的問題, 如焦距 (Focal length) 影像中心 (Image center) 像素尺寸 (Pixel size) 鏡頭扭曲系數 (Lens distortion) 以及影像歪斜 (Skew) 等透過透視投影示意圖所示, 則影像平面點 p 可以用齊次座標來表示三維空間中的點投影到影像平面上的關係 : fx f ~ P fy 0 Z 0 0 f 0 0 0 1 X 0 Y 0 Z 0 1 (4.7) 理論上成像中心點會落在 z 軸方向的光軸上, 但是受到扭曲系數影響, 每一個像素點並非為正方形, 且投射至影像座標點的成像平面位置時, 會使得中心點偏移原本光軸中心點而成像在影像座標 C, ), 此座標點即稱為影像中心, 所以投 ( C x y 影成像時會將位移部分做補償另外, 由於每一個相機的 x 軸與 y 軸比例皆不盡相 29

同, 因此我們焦距的 x 軸以 f x 表示, y 軸以 f y 做表示根據這些參數可將 4.6 式表示成三維相機座標 f x X f xy ( x, y, z) s( Cx Cy f ) Z Z (4.8) 因此齊次座標 4.8 式可表示為 f ~ P f x X Z Y Z y Z cx cy f 0 0 0 f 0 c c x y 1 X 0 Y 0 Z 0 1 (4.9) 相機中還包含了歪斜系數, 表示影像平面 x 軸與 y 軸夾角對於直角的歪斜程度, 但一般相機中的歪斜系數通常很小, 甚至近似於零, 因此可忽略, 並且假設系數為零, 完整的內部參數矩陣可表示為 M int f 0 0 0 f 0 cx c y 1 (4.10) 相機內部參數是相機本身成像關係式, 所以內部參數矩陣並不會隨著外部環境變化而有所改變, 只要實體焦距固定, 此內部參數矩陣即可重覆使用 (2) 外部參數 (Extrinsic parameter) 外部參數為相機座標系統和參考座標間轉換系數, 是表示相機外部絕對座標 30

與相機位置的空間關係式, 它可以用位移矩陣 (Translation matrix) 以及旋轉矩陣 (Rotation matrix) 來表示首先利用旋轉矩陣將相機座標及參考座標兩個不同座標系統的方向軸旋轉成一致的方向軸 ; 再經由平移矩陣將參考座原點平移至影像座標的原點, 可以用齊次座標表示為 Xc Y c R Z c 0 1 3x3 T 3x1 1 X Y Z 1 w w w (4.11) 其中 R 為旋轉矩陣,T 為平移矩陣, 如圖所示 ( 外部參數矩陣 ) 利用相機內外部參數來取得空間中三維座標投影至影像平面上的位置, 其投影公式可表示為 X X f x 0 cx r11 r12 r13 t1 Y s Y 0 f y cy r 21 r22 r23 t2z 1 0 0 1 r31 r32 r33 t3 1 s~ p M int M ext ~ P (4.12) (4.13) 表示影像平面和參考空間的齊次座標分別表示為 p ~ 和 P ~ s 為比例係數, 將內外參數矩陣定義為投影矩陣即可將 (4.13) 公式表示為 s~ p M p P ~ (4.14) 完成上述推導攻勢以及光學模式, 即可求出左右相機其內外部參數 31

4.3 變形校正在現在使用數位相機拍攝景物文件資料的頻率越來越高, 但由於拍攝的角度以及距離的關係, 如大樓名片或者是文件資料時, 通常都會產生幾何變形, 由其是拍攝長方形或正方形物體時, 其幾何變形的情形更是明顯例如使用數位相機拍攝名片文件資料時, 拍到的數位影像原本應該是方形的物體, 但從相片檢視上來看會變成任意四邊形的形狀, 產生這些幾何變形可能會導致讀取資料時無法得知正確資訊本論文研究針對現有的技術不足, 提出一幾何變形自動校正的方法對於景物名片及文件資料等容易產生幾何變形的物體, 首先我們利用自動閥值選取與形態學, 針對我們所要校正的物體進行邊緣檢測, 檢測出其物體的任意四邊形的邊緣輪廓, 並且利用 Radon transform 解析出任意四邊形的邊緣直線方程式, 即可求得任意四邊形的四個頂點座標 ; 然後建立一光學成像的數學模型, 數學模型中有我們所要校正物體的縱橫比參數方程組, 接著利用先前求得的頂點座標與縱橫比求出校正後的頂點座標, 變形校正矩陣是利用這兩組座標值所求出, 即可進行變形校正 4.3.1 取得影像邊緣輪廓在使用數位相機拍攝物體時, 通常都會把被拍攝物放置在成像區域中央或者是中央附近, 首先我們需要將所要校正的物體與其背景分離開來, 因此我們在此採用 Otsu 演算法,Otsu 演算法是建立在進行圖像分割以及進化規劃原理的基礎上, 是一種自動閥值選取的圖像分割演算法, 利用其進化規劃與快速計算的特點, 找 32

出一個用於圖像分割的最佳閥值, 將物體與背景分離開後, 結果是一幅二值圖 ; 使用形態學填充操作, 可以在得到新的二值圖, 假設原來二值圖為 BW, 新的二值圖則為 BW 1 兩圖相減 B( BW ) BW BW1, 即可得到邊界輪廓二值圖 4.3.2 Radon Transform 在取得邊緣輪廓二值圖上, 其物體的任意四邊形的四條邊界值線為白色, 其餘皆為黑色, 接著利用 Radon Transform 來檢測直線, 可以將四條直線的方程式解析出來以數學方式來描述投影量的方法即為 Radon Transform Radon Transform 可以在任意空間定義, 其表示方法如下 : 假設 f ( x, y) 是一個物體, 以二維函數表示其所在 X Y 平面上, 通過 f ( x, y) 的直線, 稱為射線 (ray), 這個射線的線積分表示光線穿透物體投射到平面 D 的總量, 定義成投影量因此我們可以寫成如公式 4.15 R (, ) f ( x, y) ( xcos ysin ) dxdy D (4.15) 公式中 D 為整個圖像 xy 的平面 ; f ( x, y) 為圖像點 ( x, y) 的灰度 ; 為座標原點到直線距離 ; 為 x 軸與距離的夾角, 為狄拉克函數它使 f ( x, y) 沿直線 xcos ysin 進行積分, 如圖 19 所示 33

y O x 圖 19 Radon Transform 定義示意圖 Radon Transform 可以解釋為圖像在空間的投影, 空間的每一個點對應圖像空間的一條直線, 而 Radon Transform 是圖像像素中每條直線上的積分, 也可以解釋為圖像順時針旋轉角度後在 x 軸上的投影因此圖像中每條直線會在空間形成一個亮點, 直線檢測則轉換為空間轉換域對亮點的檢測在前一個步驟中, 得到的四條直線, 分別對應轉換域 Radon Transform 圖中四個亮點, 座標 (, ) 可在圖中讀出每一個亮點表示一條直線, 由已知的座標 (, ), 根據公式 xcos ysin 可將四條直線的方程式解析出來利用每兩條的直線方程式作聯立方程式運算, 求出四個頂點座標這四個頂點座標則稱作為輸入點 4.3.3 縱橫比計算首先建立一個光學成像的數學模型, 如下圖 20 所示 x O O z 成像區域 y 成像透鏡成像屏 34

圖 20 光學成像數學模型 O x y 圖 21 成像區域平面其中成像平面區域如圖 21 所示, 成像模型的透鏡中心 O 與成像屏及成像區域中心 O 三點共線, 建立座標系其中, 透鏡中心與成像區域中心距離為 D, 透鏡光軸與成像區域平面夾角為 o, 拍攝時, 成像模型的透鏡焦距為 f, 成像模型光學系數為 k o 假設物體為矩形, 長為 l, 寬為 m, 矩形的中心在成像區域座標系為 x, y ), 相對於座標軸, 矩形旋轉, 計算公式如下 : ( o o R 1 2 2 2 m 2 (4.16) 1 2 arctan arctan m l l m (4.17) (4.18) 經上列公式運算後, 圖 21 所示的座標系中, 矩形的四個座標頂點座標可以分別表示出來利用四個頂點座標通過透鏡後, 折射到成像屏的兩條光線, 就可以 35

求出成像屏四個頂點座標這兩條直線, 一條為通過透鏡中心的直線, 方向不變 ; 另外一條則為平行於光軸的直線, 通過透鏡折射, 經過焦點後落在成像屏根據這兩條直線方程式就可以求出成像點座標求得四個座標頂點所對應的像點在圖 21 所示的 XY 座標系中表示出來再利用 Radon Transform 中所求得圖像中四邊形的四個頂點座標作聯立方程式, 如公式 4.19~4.26 所示 f R cos x0 D f R sin cos y f R sin D f R sin f R sin D f R sin f R cos D f R sin f R sin D f R sin f R cos D f R sin f R cos D f R sin f R sin D f R sin 1 1 1 1 1 1 1 1 1 s k x1 0 sin 2 1 sin y0 t k y1 cos y0 sin 2 1 x0 s k x2 cos y0 sin 2 2 sin y0 t k y2 cos y0 sin 2 2 x0 s k x3 cos y0 sin 2 2 sin y0 t k y3 cos y0 sin 2 1 x0 s k x4 cos y0 sin 2 1 sin y0 t k y4 cos y0 sin 2 (4.19) (4.20) (4.21) (4.22) (4.23) (4.24) (4.25) (4.26) ( 2 y2 其中, k 是成像屏與圖像之間的縮放系數, s 和 t 是圖像矩陣維數 x, ), ( 1 y1 x, ), x, ), x, ) 是由 Radon Transform 中所計算出圖像白色四邊形四個頂 ( 3 y3 ( 4 y4 點座標 ( 輸入點 ) 座標公式 19~26 中, 共有八個未知數 ( 焦距 f, s,t 已知 ), 八個方程式未知數可以分別解出, l 與 m 的縱橫比可求出 ( 假設所求得的縱橫比為 ) 36

4.3.4 變形調校本變形調校方法是採用變形校正矩陣, 針對幾何變形圖像進行校正在求出變形校正矩陣前, 必須先求出校正之後四個頂點座標任意四邊形經過校正後變成矩形, 並且校正後的矩形縱橫比為根據矩形四個頂點座標之間的幾何關係和縱橫比, 以及校正前四個頂點的座標, 將可以很清楚將校正之後的四個頂點座標求出假設校正前四個頂點座標為 x, ), x, ), x, ), x, ), 校正之後四 ( 1 y1 ( 2 y2 ( 3 y3 ( 4 y4 個頂點座標為 x, ), x, ), x, ), x, ), 其中, 校正前四個頂點座標 ( 1 y1 ( 2 y2 ( y 3 3 為輸入點, 校正後四個頂點座標為基準點 ( 4 y4 令變形校正矩陣 H, 帶入中間參數 h ij, 如公式 4.27 4.28 所示 h H h h 11 21 31 h h h 12 22 32 h h h 13 23 33 (4.27) h h h h h h h h h h T 11 21 31 12 22 32 13 23 33 (4.28) 利用投影關係與座標轉換公式, 可以得到下面的公式 4.29: 37

38 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 33 23 13 32 22 12 31 21 11 4 4 4 4 4 4 4 4 4 4 4 4 4 4 3 3 3 3 3 3 3 3 3 3 3 3 3 3 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 h h h h h h h h h y y y x y y x x y x x x y x y y y x y y x x y x x x y x y y y x y y x x y x x x y x y y y x y y x x y x x x y x (4.29) 只要帶進輸入點以及基準點的座標, 通過上述公式 4.29 即可求出 ij h, 即可求出變形校正矩陣 H 利用變形校正矩陣就可以對原圖像進行校正, 校正之後的圖像, 圖像變為矩形, 並且保持原始的縱橫比, 還原圖像資料

4.4 機器人路徑分析軟體由鏡頭校正演算法調整影片拍攝時, 因鏡頭參數所造成的畸變及利用變形校正演算法將所拍攝的場地還原後, 現在透過機器人路徑分析軟體, 可更準確的找到清潔機器人的真實位置以及座標位置, 進而利用其座標位置即可分析出清潔機器人路徑規劃覆蓋率及重覆率 4.4.1 數位影像處理定義數位影像處理是現今是常被運用以及不可或缺的技術之一, 無論在機器人醫療建築影視衛星等, 都是需要使用影像處理技術在現實生活空間中, 可以表示為一個三維函數 f ( x, y, z), 而數位影像透過各式鏡頭將物體投影至投影面上產生一個二維影像, 定義為一個二維函數 f ( x, y), 其中 x 與 y 是空間座標, f 的大小則為座標軸 ( x, y) 的相對值, 稱該點為強度或灰階當 x y 與 f 的值皆是有限的離散量時, 就是我們俗稱的數位影像在數位影像中, 彩色影像每點都有 RGB 三個顏色的強度值,R 為紅色 G 為綠色 B 為藍色,RGB 空間是以這三種顏色調和為任一顏色另外影像取樣點越多則越接近真實的影像, 但其資訊量會相當龐大, 影像取樣點的數量會決定 x y 值, 取樣點的多寡則稱之為解析度, 數位影像的品質及大小則以解析度決定而數位影像處理則是使用電腦來處理, 數位影像中, 每個元素皆有特定的數值與位置, 構成數位影像的元素稱為像素照片元素或影像元素, 可經由程式與設定各種控制參數, 還可以運用許多不同的影像處理演算法, 來達成所希望獲得的影像呈現或影像資料 39

4.4.2 鄰域處理 (Neighborhood Processing) 鄰域處理技術經常被使用在影像處理中, 如圖 22 所示, 對像素值執行特定函數運算來修正影像, 將像素鄰域部分納入執行函數運算考量, 鄰域範圍由遮罩決定, 在處理過程中必須先定義出遮罩 (mask) 的中心點以及形狀, 在遮罩的中心點周遭區域即是鄰域範圍, 將遮罩區域內所有元素值與影像對應像素值帶入函式中進行計算產生響應, 產生響應後即移動遮罩中心點位置至下一點產生新的鄰域進行運算, 重覆此步驟直到整張數位影像完成處理, 其中遮罩與函式運算為濾波處理遮罩相乘遮罩與鄰域乘積像素鄰域目前像素輸出像素所有乘積總和圖 22 鄰域處理示意圖使用者可以自行設計遮罩大小及形狀, 不同的形狀大小的遮罩會呈現出不同的處理效果, 因此可自行選擇符合需求設計的遮罩, 常見的遮罩皆以 n n 的形式, 40

最為常見的遮罩 n 是為奇數, 使遮罩中心點成對稱, 許多濾波器均使用 3 3 的遮罩, 但以 Dithering 技術則是使用 n 為偶數的遮罩 4.4.3 邊緣偵測邊緣檢測是影像處理和電腦視覺中常用到的一種技術, 邊緣檢測的目的主要是找出影像中圖形的邊緣, 標示出圖像中亮度變化的點, 在前述 4.4.2 節中, 鄰域處理可以進行簡單的邊緣偵測, 但本論文中未使用其技術, 在此不多論述邊緣檢測分別有 Canny 演算法 Sobel 演算法以及 Laplace 演算法, 其中 Canny 演算法是目前最常被使用的邊緣檢測的演算法在 Canny 演算法中, 其偵測方式還需有兩個閥值決定, 第一個閥值為門檻值, 當邊緣受到雜訊影響時會產生出波峰, 若將所有波峰的所在位置當為邊緣時, 誤判的情況將會產生, 所以第一個門檻值就是避免在邊緣偵測時產生誤判, 當某一波的波峰值大於所設定的門檻值時才是真正的邊緣, 其餘波峰則皆為雜訊而第二個閥值則是當雜訊影響到其中一條邊緣時, 可能會使其邊緣斷成好幾節, 解決的方式為一種遞回式的方法, 觀察影像中每一個點其八個方向的鄰點是否有邊緣點的存在, 如果有邊緣點的存在且其值大於門檻值, 即可判斷此鄰點與此點為同一條線段, 即可將此鄰點加入同一條線段中, 爾後對影像中的每一個點做偵測與判斷, 即可將影像中被截斷的線連結起來 41

4.4.3.1 Canny 邊緣偵測 Canny 邊緣偵測法是於 1986 年 Canny[45] 所提出的方法, 首先使用高斯濾波器平滑影像降低雜訊干擾, 在高斯濾波器中會先得到灰階影像 f ( x, y), 平滑影像即為 g( x, y) f ( x, y) W ( x, y, ), 每點都計算梯度向量 g( x, y) 及梯度向量大小與 G 方向, 邊緣偵測器的大小會根據高斯濾波器參數來決定, 依照適當的參數值來決定得到邊緣偵測的程度雜訊干擾多寡以及邊緣偵測定位與準確性, 最後弱邊緣像素的周遭將會被併入強邊緣像素, 完成邊緣連結 4.4.4 二值化概念在數位影像處理中, 二值化的方法概念中可達成, 利用降低數位影像的資訊量來達成節省系統資源辨識速度加快以及提高辨識率在灰階影像中可取得 0 到 255 的灰階度值, 根據灰階影像的分布範圍, 可透過灰階臨界值將影像分割出背景與目標物, 但經過二值化處理後的數位影像, 會呈現失真的現象, 為降低失真的程度, 二值化的方法也陸續被提出, 針對不同的分法目的樣本設計等結果也不盡相同, 在二值化方法的應用上則視需求選擇適當方法, 取得適合目標灰階影像的二值化臨界值 4.4.4.1 影像二值化將我們所需的影像載入之後, 因其明暗變化較為複雜, 在影像分析上比較困 42

難, 所以我們必須先將影像二值化, 也就是只有明和暗 (0 和 255), 二值化的步驟非常重要, 是影像處理的第一個步驟, 經過二值化的處理後, 我們即可將影像的所需的圖形以及背景分離開來, 針對圖形作我們所要的處理二值化也稱為灰度分劃, 即設定一個灰度值, 只要影像本身灰度大於灰度值的便為亮點, 反之低於設定值的則為暗點, 經過此步驟即可得到一個二元影像在影像處理中, 凡須去除影像中不需要的細節, 留下需要的基礎要素或顯示影像中隱藏的特性, 皆可利用影像二值化, 在影像二值化中每一個像素點的灰階值都以 0 和 1 來表示, 這樣即可將影像簡化成前景與背景, 特徵值即是前景, 背景就是我們不需要的影像在本研究論文中, 此處的二值化門檻值以能夠取得清潔機器人在場地中的特徵值為原則, 因此所設的二值化門檻值較高, 由於場地大小形狀以及障礙物的不同, 也會依據其場地情況進而調整其二值化門檻值 4.4.5 形態學影像處理形態學影像處理方法是一種非線性的影像分析技術, 此影像處理技術來自 1960 年分析地質學和醫學的二元化影像處理, 當時即推廣運用於配合布林邏輯的細胞組織自動型態辨識的工作,1970 年代晚期此技術延伸到灰階影像處理,1980 年代中期, 形態學影像處理和其他非線性濾鏡成為影像處理的主流, 最後它則被一般化, 成為不限方形的結構元素也能執行此影像處理, 如今, 型態學方法已演進為一門及理論概念應用系統寬廣設計性方法及非線性濾鏡的概念, 此形態學方法具有倫理制度在特定硬體上容易施行具效率的演算法及於形狀方位問題皆適用等優點 43

形態學通常是指研究動物和設備形狀與結構所得名影像是由像素所組成, 又可歸納為二維結構, 我們可對像素進行數學運算, 加強其結構特性, 達到辨認或計數的目的形態學影像處理主要是透過遮罩及集合理論對影像作型態上處理, 如膨脹或是侵蝕, 集合理論為形態學的基礎, 因此首先須了解即合理論,A 為一集合 B 為另一集合如圖 23(1) 所示,(2)A 與 B 集合之聯集,(3)A 與 B 集合之交集,(4)A 與 B 集合之差集,(5)A 集合之補集 A B A B A B (1) (2) (3) A B A (4) (5) 圖 23 集合理論在形態學中, 我們使用侵蝕與膨脹對影像進行平滑處理侵蝕運算是利用在遮罩中所有點像素灰度大小中, 排序最小的灰度值, 膨脹運算則是找出在遮罩中所有點像素灰度大小中, 排序最大的灰度值侵蝕運算執行後該點像素灰度值為其鄰近八接點的中的最小值, 當影像為亮點時, 執行侵蝕運算會造成物體蝕刻縮小的結果膨脹運算執行後該點像素灰度值為其鄰近八接點的中的最大值, 當影 44

像為亮點時, 執行膨脹運算會造成物體擴張膨脹的結果從侵蝕與膨脹運算中發展出斷開與閉合運算斷開運算執行時先進行侵蝕運算, 再作影像膨脹運算, 其處理效果在於可除去一些小面積的高頻雜訊, 將影像結構外型變的平滑, 透過斷開的運作可將圖形中細微的連結部分有效的分開閉合運算執行時先進行影像膨脹運算, 再作影像侵蝕運算, 其處理效果在於可將影像中的小洞填補起來及將一些斷線連接起來 ; 斷開與閉合是形態學中兩個重要運算, 是由膨脹與侵蝕組合的復合運算在斷開與閉合的影像運算中, 影像先作侵蝕運算, 再作膨脹運算的結果和先作影像膨脹運算在作侵蝕運算的結果是不一樣的透過斷開與閉合的合併使用, 可有效抑制二值化影像中的雜訊以下敘述為就侵蝕膨脹斷開及閉合的運算方式與效果 : 4.4.5.1 形態學影像處理 - 侵蝕 (Erosion) 侵蝕運算是當邊緣檢測後, 多出來的邊緣或經二值化後多出的點將其消除, 或是在因物體膨脹後, 為了讓分析特徵值結果更為準確, 避免物體膨脹過大而分析結果不準確, 而再進行一次侵蝕侵蝕方法是逐點掃描, 並且是由上而下的方式進行, 如找到為物體的暗點時, 再判斷鄰近的八點, 如其中有一點為背景時, 即將此點改為亮點, 如此一來物體的暗點就少一點, 等掃描完整張圖時, 物體會少一圈暗點, 這就是影像侵蝕在圖 24 中, 虛線為被正方形結構元素所侵蝕的狀況, 所以當區塊侵蝕後的大小, 亦 45

會受到結構元素大小的影響圖 24 大區塊與小區塊對稱結構元素膨脹示意圖 4.4.5.2 形態學影像處理 - 膨脹 (Dilation) 當圖形經過二值化後, 邊緣會呈現不平或有凹洞的情形, 此時可將圖形膨脹, 以改善邊緣不平或凹洞的情形此方法是當尋找到背景亮點時, 判斷周圍是否為背景或物體, 再判斷鄰近的八點, 如其中物體暗點時, 則將此點改為暗點, 等掃描完整張圖時, 物體會多一圈暗點, 就會呈現物體膨脹的情形在圖 25 中, 虛線為被正方形結構元素所膨脹的狀況, 所以當區塊膨脹後的大小, 亦會受到結構元素大小的影響圖 25 大區塊與小區塊對稱結構元素侵蝕示意圖 46

4.4.5.3 形態學影像處理 - 斷開 (Opening) 斷開是膨脹之後所延伸的方法, 首先對影像進行侵蝕後再膨脹, 這即為斷開運算此演算可以平滑大影像的邊界對面積改變時表現不明顯分開連結的影像像素以及消除雜訊或較小的影像點等優點如圖 26 為斷開運算圖 26 斷開運算示意圖 4.4.5.4 形態學影像處理 - 閉合 (Closing) 閉合為侵蝕之後所延伸的方法首先先對影像進行膨脹後再收縮, 這即為閉合運算具有在不明顯改變面積的情況平滑邊界連結鄰近影像像素以及填充影像內細小的空洞等作用而閉合也有平滑輪廓的部分, 不過與斷開相反, 為先膨脹後侵蝕如圖 27 圖 27 閉合運算示意圖 47

4.4.6 背景相減法本論文研究中使用背景相減法取得機器人中心點座標位置, 首先使用背景相減法必須先建立一背景模型, 當機器人進入此畫面時, 此背景模型會造成明顯的亮度變化並且作一對一的像素亮度值相減, 藉此偵測出機器人物件像素, 最後即可準確且快速的求出移動物的座標位置此方法除了可擷取物件的形狀及坐標位置, 對雜訊也有較高的容忍度, 可減少因移動物所造成的陰影影響背景相減法是利用靜態的影像擷取裝置, 建立好的影像背景, 在影像擷取裝置不移動的情況下, 拍攝擷取多張連續的影像, 再將擷取到的多張連續影像與先前建立好的影像背景作相減動作, 會得到背景影像與連續影像在相同的影像平面空間中的影像差異值, 倘若兩者影像皆為背景影像部分, 則影像差異值會低於門檻值或者為零, 而若影像相減後, 影像差異值大於門檻值, 則會保留影像差益的部分, 即是物件所在的座標位置 48

4.5 覆蓋率計算方式目前在清潔機器人技術中, 清潔機器人如何在一個未知的環境中準確的計算出其清潔的覆蓋率, 因此覆蓋率與重覆率的計算亦是相當重要的研究方向之一,, 在目前相關清潔機器人覆蓋率的研究中, 多半都是採用以電腦模擬的方式來呈現機器人的覆蓋率, 但是以模擬的方式無法呈現機器人的真實環境中的實際情況, 例如機器人真實的機械狀態碰撞障礙物的實際反應地形的實際情形地板的材質等相當多的因素, 是電腦模擬無法做出的本論文研究中, 以影像處理技術, 可完整準確掌握機器人路徑, 並且可計算出清潔機器人在真實情境所呈現的覆蓋率清潔覆蓋率的計算, 以固定時間固定面積固定障礙物以及固定的行走長度下來計算, 因各家廠牌清潔機器人所行走的速度不一, 故本論文以機器人所行走距離來計算其覆蓋率, 清潔模式以機器人自動隨機模式運行, 如此一來即可得到最接近機器人在真實環境中的覆蓋率 49

第五章實驗與模擬結果此章節中將介紹本論文實驗流程以及結果, 在實驗流程中, 首先利用鏡頭校正演算法修正因鏡頭所造成的變形, 接著使用變形校正演算法轉換成我們所需的影像畫面, 再來影像處理路徑分析軟體會進行影像處理, 擷取出清潔機器人在影像中的座標位置, 分析出機器人路徑覆蓋率以及重覆率 5.1 視覺化量測實驗結果本論文研究實驗數據, 是以影片拍攝方式, 錄製清潔機器人運行影片, 接著利用影片拆解, 將影片轉換為圖片, 並透過鏡頭校正軟體變形校正軟體以及路徑分析軟體分析清潔機器人的路徑座標位置本論文所使用的影片拍攝器材為 SONY 公司所生產的 NEX-5 類單眼相機所拍攝, 並且利用影像拆解軟體將影片轉換為圖片影像處理方面是利用 Microsoft Visual C# 2010 做為程式編輯軟體, 配合由 Intel 開發的 OpenCV(Open Source Computer Vision Library), 並引用 OpenCV 影像處理與電腦視覺演算法函式庫, 完成影像處理的部分下圖 28 圖 29 圖 30 則是本論文所撰寫的影像處理程式畫面 50

圖 28 鏡頭校正程式畫面圖 29 變形校正程式畫面 51

圖 30 路徑分析軟體程式畫面 5.1.1 鏡頭校正結果在鏡頭校正的部分, 我們使用一般類單眼相機拍攝照片時, 會發現拍攝照片的影像會有桶狀變形的現象發生, 為避免變形校正後, 所擷取的數據錯誤, 我們使用鏡頭校正軟體將產生桶狀變形的照片修正完成如下圖 31 為影像拍攝時發生嚴重桶狀變形相片 52

圖 31 桶狀變形透過圖 31 可以發現, 紅線區域應為原本磁磚線區域, 但因拍攝時產生桶狀變形, 所以我們必須以鏡頭校正軟體將桶狀變形調整為正常影像 53

圖 32 鏡頭校正後影像經過我們所撰寫的鏡頭校正軟體調整後, 由上圖 32 我們可以發現原本地上的磁磚線已經和我們所畫的紅線重疊, 由此可證明, 本論文鏡頭校正研究方法是可以有效的將影像所產生的變形調整回原本所應呈現的影像如下圖 33 圖 33 所示鏡頭校正前圖 33 鏡頭校正實驗結果鏡頭校正後 54

5.1.2 變形校正結果透過鏡頭校正調整桶狀變形完後, 接著開始進行變形校正, 變形校正是將我們拍攝的影像還原成正面, 讓路徑分析軟體可以利用影像處理方法, 將我們的機器人所在位置的中心座標點找出下圖 34 為我們所拍攝的影像畫面, 這裡我們以凸形地形為例, 並在地形中擺設十二張與機器人大小一致的黑色原紙圖 34 變形校正前 55

透過變形校正後, 如下圖 35 我們可以看到原本的影像還原我們所需要的正面圖, 透過所擺設的十二張黑色原紙證明還原後, 影像中的物品方位仍然在我們所擺放的位置, 證明此方法可以有效的還原, 並且不會因為還原而產生變形或失真圖 35 變形校正後變形校正前圖 36 變形校正實驗結果變形校正後 56

5.1.3 清潔機器人路徑分析 - 無障礙物環境量測結果本論文實驗場地為樹德科技大學圖資三樓, 以 PVC 水管分別製作五平方公尺六平方公尺七乘五平方公尺凹形地圖凸形地圖以及梯形地圖, 以 SONY NEX-5 數位類單眼相機拍攝清潔機器人部分共有六台, 分別以實驗機器人一 ~ 五編號以及本實驗室所研發自製清潔機器人以下簡稱為 IIIT-Robot 清潔機器人無障礙覆蓋率計算公式 5.1 如下 : 機器人直線距離掃刷寬度 100% 地形總面積 (5.1) 清潔機器人模擬家庭環境覆蓋率計算公式 5.2 如下機器人直線距離掃刷寬度 100% ( 地形總面積障礙物面積 ) (5.2) 清潔機器人重覆率計算公式 5.3 如下 : ( 總座標數 -覆蓋座標數 ) 100% 機器人總座標數 (5.3) 57

5.1.3.1 五平方公尺量測結果表二為視覺化量測數據路徑分析結果, 地圖大小為無障礙物五平方公尺表二 : 五平方公尺無障礙環境覆蓋率分析機器人數據覆蓋率重覆率實驗機器人一 69.8% 29% 實驗機器人二 86.1% 14% 實驗機器人三 95.3% 19% 實驗機器人四 69.6% 20% 實驗機器人五 84.6% 34% IIIT-Robot 61.6% 31% 58

圖 37 中, 為各機器人在五平方公尺無障礙環境中運行路徑實驗機器人 ( 一 ) 路徑圖實驗機器人 ( 二 ) 路徑圖實驗機器人 ( 三 ) 路徑圖實驗機器人 ( 四 ) 路徑圖實驗機器人 ( 五 ) 路徑圖 IIIT-Robot 路徑圖圖 37 五平方公尺無障礙環境運行路徑 59

圖 38 為五平方公尺無障礙環境各機器人覆蓋率情形 : 實驗機器人 ( 一 ) 路徑覆蓋圖實驗機器人 ( 二 ) 路徑覆蓋圖實驗機器人 ( 三 ) 路徑覆蓋圖實驗機器人 ( 四 ) 路徑圖實驗機器人 ( 五 ) 路徑圖 IIIT-Robot 路徑圖圖 38 五平方公尺無障礙環境機器人覆蓋率 60

5.1.3.2 六平方公尺量測結果表三為視覺化量測數據路徑分析結果, 地圖大小為無障礙物六平方公尺表三 : 六平方公尺無障礙環境覆蓋率分析機器人數據覆蓋率重覆率實驗機器人一 59.2% 21% 實驗機器人二 80.7% 9% 實驗機器人三 69.7% 23% 實驗機器人四 46.5% 23% 實驗機器人五 67.4% 65% IIIT-Robot 72.7% 31% 61

圖 39 中, 為各機器人在六平方公尺無障礙環境中運行路徑實驗機器人 ( 一 ) 路徑圖實驗機器人 ( 二 ) 路徑圖實驗機器人 ( 三 ) 路徑圖實驗機器人 ( 四 ) 路徑圖實驗機器人 ( 五 ) 路徑圖 IIIT-Robot 路徑圖圖 39 六平方公尺無障礙環境中運行路徑 62

圖 40 為六平方公尺無障礙環境各機器人覆蓋率情形 : 實驗機器人 ( 一 ) 路徑覆蓋圖實驗機器人 ( 二 ) 路徑覆蓋圖實驗機器人 ( 三 ) 路徑覆蓋圖實驗機器人 ( 四 ) 路徑覆蓋圖實驗機器人 ( 五 ) 路徑覆蓋圖 IIIT-Robot 路徑覆蓋圖圖 40 六平方公尺無障礙環境各機器人覆蓋率 63

5.1.3.3 七乘五公尺量測結果尺表四為視覺化量測數據路徑分析結果, 地圖大小為無障礙物七乘五平方公表四 : 七乘五平方公尺無障礙環境覆蓋率分析機器人數據覆蓋率重覆率實驗機器人一 54% 32% 實驗機器人二 50% 8% 實驗機器人三 66% 22% 實驗機器人四 52.7% 16% 實驗機器人五 60.8% 23% IIIT-Robot 87.4% 15% 64

圖 41 中, 為各機器人在七乘五平方公尺無障礙環境中運行路徑實驗機器人 ( 一 ) 路徑圖實驗機器人 ( 二 ) 路徑圖實驗機器人 ( 三 ) 路徑圖實驗機器人 ( 四 ) 路徑圖實驗機器人 ( 五 ) 路徑圖 IIIT-Robot 路徑圖圖 41 七乘五平方公尺無障礙環境運行路徑 65

圖 42 為七乘五平方公尺無障礙環境各機器人覆蓋率情形 : 實驗機器人 ( 一 ) 路徑覆蓋圖實驗機器人 ( 二 ) 路徑覆蓋圖實驗機器人 ( 三 ) 路徑覆蓋圖實驗機器人 ( 四 ) 路徑覆蓋圖實驗機器人 ( 五 ) 路徑覆蓋圖 IIIT-Robot 路徑覆蓋圖圖 42 七乘五平方公尺無障礙環境機器人覆蓋率 66

5.1.3.4 凹形地圖量測結果表五為視覺化量測數據路徑分析結果, 地圖大小為無障礙物凹形地圖表五 : 凹形地圖無障礙環境覆蓋率分析機器人數據覆蓋率重覆率實驗機器人一 73% 74% 實驗機器人二 84.4% 16% 實驗機器人三 87.1% 23% 實驗機器人四 73% 23% 實驗機器人五 44% 30% IIIT-Robot 90% 21% 67

圖 43 中, 為各機器人在凹形地圖無障礙環境中運行路徑實驗機器人 ( 一 ) 路徑圖實驗機器人 ( 二 ) 路徑圖實驗機器人 ( 三 ) 路徑圖實驗機器人 ( 四 ) 路徑圖實驗機器人 ( 五 ) 路徑圖 IIIT-Robot 路徑圖圖 43 凹形地圖無障礙環境運行路徑 68

圖 44 為凹形地圖無障礙環境各機器人覆蓋率情形 : 實驗機器人 ( 一 ) 路徑覆蓋圖實驗機器人 ( 二 ) 路徑覆蓋圖實驗機器人 ( 三 ) 路徑覆蓋圖實驗機器人 ( 四 ) 路徑覆蓋圖實驗機器人 ( 五 ) 路徑覆蓋圖 IIIT-Robot 路徑覆蓋圖圖 44 凹形地圖無障礙環境機器人覆蓋率 69

5.1.3.5 凸形地圖量測結果表六為視覺化量測數據路徑分析結果, 地圖大小為無障礙物凸形地圖表六 : 凸形地圖無障礙環境覆蓋率分析機器人數據覆蓋率重覆率實驗機器人一 59% 28% 實驗機器人二 87% 14% 實驗機器人三 72% 26% 實驗機器人四 52% 27% 實驗機器人五 66% 23% IIIT-Robot 70% 17% 70

圖 45 中, 為各機器人在凸形地圖無障礙環境中運行路徑實驗機器人 ( 一 ) 路徑圖實驗機器人 ( 二 ) 路徑圖實驗機器人 ( 三 ) 路徑圖實驗機器人 ( 四 ) 路徑圖實驗機器人 ( 五 ) 路徑圖 IIIT-Robot 路徑圖圖 45 凸形地圖無障礙環境運行路徑 71

圖 46 為凸形地圖無障礙環境各機器人覆蓋率情形 : 實驗機器人 ( 一 ) 路徑覆蓋圖實驗機器人 ( 二 ) 路徑覆蓋圖實驗機器人 ( 三 ) 路徑覆蓋圖實驗機器人 ( 四 ) 路徑覆蓋圖實驗機器人 ( 五 ) 路徑覆蓋圖 IIIT-Robot 路徑覆蓋圖圖 46 凸形地圖無障礙環境機器人覆蓋率 72

5.1.3.6 梯形地圖量測結果表七為視覺化量測數據路徑分析結果, 地圖大小為無障礙物梯形地圖表七 : 梯形地圖無障礙環境覆蓋率分析機器人數據覆蓋率重覆率實驗機器人一 86.1% 36% 實驗機器人二 100% 18% 實驗機器人三 100% 17% 實驗機器人四 92% 28% 實驗機器人五 98% 20% IIIT-Robot 100% 7% 73

圖 47 中, 為各機器人在梯形地圖無障礙環境中運行路徑實驗機器人 ( 一 ) 路徑圖實驗機器人 ( 二 ) 路徑圖實驗機器人 ( 三 ) 路徑圖實驗機器人 ( 四 ) 路徑圖實驗機器人 ( 五 ) 路徑圖 IIIT-Robot 路徑圖圖 47 梯形地圖無障礙環境運行路徑 74

圖 48 為梯形地圖無障礙環境各機器人覆蓋率情形 : 實驗機器人 ( 一 ) 路徑覆蓋圖實驗機器人 ( 二 ) 路徑覆蓋圖實驗機器人 ( 三 ) 路徑覆蓋圖實驗機器人 ( 四 ) 路徑覆蓋圖實驗機器人 ( 五 ) 路徑覆蓋圖 IIIT-Robot 路徑覆蓋圖圖 48 梯形地圖無障礙環境各機器人覆蓋率 75

5.1.4 清潔機器人路徑分析 - 模擬家庭環境量測結果在模擬家庭環境中, 本論文使用大小不一的障礙物模擬家庭環境中, 清潔機器人運作時可能會遭遇到的情形, 如下圖 49 所示, 在各地形環境中, 搭配各地形環境設置障礙物的大小以及位置, 以模擬最真實的家庭中實際情況五平方公尺六平方公尺七乘五平方公尺凹形地圖梯形地圖凸形地圖圖 49 模擬家庭環境設置圖 76

5.1.4.1 五平方公尺量測結果地圖表八為視覺化量測數據路徑分析結果, 地圖大小為五平方公尺模擬家庭環境表八 : 五平方公尺地圖模擬家庭環境覆蓋率分析機器人數據覆蓋率重覆率實驗機器人一 72% 45% 實驗機器人二 97% 24% 實驗機器人三 88% 34% 實驗機器人四 70% 49% 實驗機器人五 87% 31% IIIT-Robot 95% 29% 77

圖 50 中, 為各機器人在五平方公尺模擬家庭環境地圖中運行路徑實驗機器人 ( 一 ) 路徑圖實驗機器人 ( 二 ) 路徑圖實驗機器人 ( 三 ) 路徑圖實驗機器人 ( 四 ) 路徑圖實驗機器人 ( 五 ) 路徑圖 IIIT-Robot 路徑圖圖 50 五平方公尺地圖模擬家庭環境運行路徑 78

圖 51 為五平方公尺模擬家庭環境地圖各機器人覆蓋率情形 : 實驗機器人 ( 一 ) 路徑覆蓋圖實驗機器人 ( 二 ) 路徑覆蓋圖實驗機器人 ( 三 ) 路徑覆蓋圖實驗機器人 ( 四 ) 路徑覆蓋圖實驗機器人 ( 五 ) 路徑覆蓋圖 IIIT-Robot 路徑覆蓋圖圖 51 五平方公尺地圖模擬家庭環境機器人覆蓋率 79

5.1.4.2 六平方公尺量測結果地圖表九為視覺化量測數據路徑分析結果, 地圖大小為六平方公尺模擬家庭環境表九 : 六平方公尺地圖模擬家庭環境覆蓋率分析機器人數據覆蓋率重覆率實驗機器人一 55% 34% 實驗機器人二 65% 34% 實驗機器人三 63% 38% 實驗機器人四 39% 48% 實驗機器人五 63% 33% IIIT-Robot 60% 35% 80

圖 52 中, 為各機器人在六平方公尺模擬家庭環境地圖中運行路徑實驗機器人 ( 一 ) 路徑圖實驗機器人 ( 二 ) 路徑圖實驗機器人 ( 三 ) 路徑圖實驗機器人 ( 四 ) 路徑圖實驗機器人 ( 五 ) 路徑圖 IIIT-Robot 路徑圖圖 52 六平方公尺模擬家庭環境地圖運行路徑 81

圖 53 為六平方公尺模擬家庭環境地圖各機器人覆蓋率情形 : 實驗機器人 ( 一 ) 路徑覆蓋圖實驗機器人 ( 二 ) 路徑覆蓋圖實驗機器人 ( 三 ) 路徑覆蓋圖實驗機器人 ( 四 ) 路徑覆蓋圖實驗機器人 ( 五 ) 路徑覆蓋圖 IIIT-Robot 路徑覆蓋圖圖 53 六平方公尺模擬家庭環境地圖機器人覆蓋率 82

5.1.4.3 七乘五公尺量測結果表十為視覺化量測數據路徑分析結果, 地圖大小為七乘五平方公尺模擬家庭環境地圖表十 : 七乘五平方公尺地圖模擬家庭環境覆蓋率分析機器人數據覆蓋率重覆率實驗機器人一 62.2% 33% 實驗機器人二 83% 21.4% 實驗機器人三 43.3% 35.3% 實驗機器人四 58% 31.1% 實驗機器人五 58% 36% IIIT-Robot 76% 30.1% 83

圖 54 中, 為各機器人在七乘五平方公尺模擬家庭環境地圖中運行路徑實驗機器人 ( 一 ) 路徑圖實驗機器人 ( 二 ) 路徑圖實驗機器人 ( 三 ) 路徑圖實驗機器人 ( 四 ) 路徑圖實驗機器人 ( 五 ) 路徑圖 IIIT-Robot 路徑圖圖 54 七乘五平方公尺模擬家庭環境地圖運行路徑 84

圖 55 為七乘五平方公尺模擬家庭環境地圖各機器人覆蓋率情形 : 實驗機器人 ( 一 ) 路徑覆蓋圖實驗機器人 ( 二 ) 路徑覆蓋圖實驗機器人 ( 三 ) 路徑覆蓋圖實驗機器人 ( 四 ) 路徑覆蓋圖實驗機器人 ( 五 ) 路徑覆蓋圖 IIIT-Robot 路徑覆蓋圖圖 55 七乘五平方公尺模擬家庭環境地圖機器人覆蓋率 85

5.1.4.4 凹形地圖量測結果圖表十一為視覺化量測數據路徑分析結果, 地圖大小為凹形模擬家庭環境地表十一 : 凹形地圖模擬家庭環境覆蓋率分析機器人數據覆蓋率重覆率實驗機器人一 80% 35% 實驗機器人二 90% 23% 實驗機器人三 94% 45% 實驗機器人四 66% 39% 實驗機器人五 62% 50% IIIT-Robot 80% 35% 86

圖 56 中, 為各機器人在凹形地圖模擬家庭環境中運行路徑實驗機器人 ( 一 ) 路徑圖實驗機器人 ( 二 ) 路徑圖實驗機器人 ( 三 ) 路徑圖實驗機器人 ( 四 ) 路徑圖實驗機器人 ( 五 ) 路徑圖 IIIT-Robot 路徑圖圖 56 凹形地圖模擬家庭環境運行路徑 87

圖 57 為凹形模擬家庭環境地圖各機器人覆蓋率情形 : 實驗機器人 ( 一 ) 路徑覆蓋圖實驗機器人 ( 二 ) 路徑覆蓋圖實驗機器人 ( 三 ) 路徑覆蓋圖實驗機器人 ( 四 ) 路徑覆蓋圖實驗機器人 ( 五 ) 路徑覆蓋圖 IIIT-Robot 路徑覆蓋圖圖 57 凹形地圖模擬家庭環境機器人覆蓋率 88

5.1.4.5 凸形地圖量測結果圖下表十二為視覺化量測數據路徑分析結果, 地圖大小為凸形模擬家庭環境地表十二 : 凸形地圖模擬家庭環境覆蓋率分析機器人數據覆蓋率重覆率實驗機器人一 77% 48.4% 實驗機器人二 62% 28% 實驗機器人三 70% 43% 實驗機器人四 57% 42.1% 實驗機器人五 64% 37% IIIT-Robot 76% 31% 89

圖 58 中, 為各機器人在凸形模擬家庭環境地圖中運行路徑實驗機器人 ( 一 ) 路徑圖實驗機器人 ( 二 ) 路徑圖實驗機器人 ( 三 ) 路徑圖實驗機器人 ( 四 ) 路徑圖實驗機器人 ( 五 ) 路徑圖 IIIT-Robot 路徑圖圖 58 凸形地圖模擬家庭環境運行路徑 90

圖 59 為凸形模擬家庭環境地圖各機器人覆蓋率情形 : 實驗機器人 ( 一 ) 路徑覆蓋圖實驗機器人 ( 二 ) 路徑覆蓋圖實驗機器人 ( 三 ) 路徑覆蓋圖實驗機器人 ( 四 ) 路徑覆蓋圖實驗機器人 ( 五 ) 路徑覆蓋圖 IIIT-Robot 路徑覆蓋圖圖 59 凸形地圖模擬家庭環境機器人覆蓋率 91

5.1.4.6 梯形地圖量測結果圖表十三為視覺化量測數據路徑分析結果, 地圖大小為梯形模擬家庭環境地表十三 : 梯形地圖模擬家庭環境覆蓋率分析機器人數據覆蓋率重覆率實驗機器人一 81% 38% 實驗機器人二 95% 35% 實驗機器人三 90% 50% 實驗機器人四 75% 37% 實驗機器人五 84% 32% IIIT-Robot 95% 28% 92

圖 60 中, 為各機器人在梯形模擬家庭環境地圖中運行路徑實驗機器人 ( 一 ) 路徑圖實驗機器人 ( 二 ) 路徑圖實驗機器人 ( 三 ) 路徑圖實驗機器人 ( 四 ) 路徑圖實驗機器人 ( 五 ) 路徑圖 IIIT-Robot 路徑圖圖 60 梯形地圖模擬家庭環境運行路徑 93

圖 61 為梯形模擬家庭環境地圖各機器人覆蓋率情形 : 實驗機器人 ( 一 ) 路徑覆蓋圖實驗機器人 ( 二 ) 路徑覆蓋圖實驗機器人 ( 三 ) 路徑覆蓋圖實驗機器人 ( 四 ) 路徑覆蓋圖實驗機器人 ( 五 ) 路徑覆蓋圖 IIIT-Robot 路徑覆蓋圖圖 61 梯形地圖模擬家庭環境機器人覆蓋率 94

5.2 模擬結果討論本節主要討論所有清潔機器人於真實環境中運行的結果分析, 此路徑分析數據, 是依據清潔機器人在各地形運行時所得到的平均值, 首先對於清潔機器人在無障礙環境中各地形的路徑數據, 從表十四中可以得知, 實驗機器人二實驗機器人三以及 IIIT-Robot 機器人在覆蓋率方面, 平均值皆有 80% 以上, 若從重覆率來分析, 實驗機器人二重覆率 13%, 由此即可以得到, 實驗機器人二有高覆蓋率以及低重覆率的特性, 從這兩項數據來分析, 我們可以判斷實驗機器人二的清潔效率覆蓋率以及重覆率是本論文實驗中表現最佳的表十四 : 無障礙地形平均路徑數據數據機器人覆蓋率重覆率實驗機器人一 68% 36% 實驗機器人二 81% 13% 實驗機器人三 81% 21% 實驗機器人四 64% 22% 實驗機器人五 70% 32% IIIT-Robot 80% 20% 另外在模擬家庭環境, 我們在地圖環境中設置不同的障礙物, 對於清潔機器人在模擬家庭環境中各地形的路徑數據, 從表十五中可以得到, 覆蓋率在 80% 以上的清潔機器人只剩下實驗機器人二與 IIIT-Robot, 但從重覆率來看, 實驗機器人二的重覆率仍然是最低的 27%, 這顯示實驗機器人二無論在無障礙環境地形或者是模擬家庭環境地形中, 所得的數據都是高覆蓋率以及低重覆率的數值, 這顯示若單純以數據比較, 實驗機器人二無論在全域覆蓋路徑的規畫以及清潔路徑的重覆次數上都是優於其他五台清潔機器人 95

表十五 : 模擬家庭環境路徑平均數據數據機器人覆蓋率重覆率實驗機器人一 72% 38% 實驗機器人二 82% 27% 實驗機器人三 74% 40% 實驗機器人四 60% 41% 實驗機器人五 69% 36% IIIT-Robot 80% 31% 透過上述所言以及數據顯示, 可證實本論文研究方法, 以影像處理方式分析清潔機器人路徑覆蓋率, 是確實可以依據清潔機器人所行走的路徑, 擷取其座標點位置, 分析出清潔機器人在任何環境中的路徑資料, 相對於電腦模擬機器人路徑資料來說, 本論文研究可提供準確且更接近真實環境中機器人路徑數據資料 96

第六章結論與未來研究方向本論文主要試探討清潔機器人路徑覆蓋率分析, 利用影像處理的方式, 提出結合鏡頭校正演算法變形校正演算法以及路徑分析軟體達成視覺化量測機器人路徑位置, 試圖解決目前有關於機器人覆蓋率量測技術上的穩定性與準確性等除此之外, 基於以影像記錄方式來量測機器人路徑位置, 以攝影技術以及器材擺放位置, 在現實環境中都會受到鏡頭變形或者是須架設大量攝影器材提高實驗成本本研究利用影像處理技術, 設法改善當影像記錄時鏡頭所造成的變形問題, 以及如何不須架設大量攝影器材以及成本的前提之下紀錄機器人影像位置在本論文研究方法中, 可即時記錄清潔機器人運作情形, 改善攝影器材設置問題經實驗結果證實, 清潔機器人的覆蓋率以及重複率量測, 是可以利用電腦視覺化的方法達成此研究相對於電腦軟體所模擬出來的覆蓋率, 可提供較高準確性以及可信度而清潔機器人清掃模式中, 牛耕與隨機模式是具有較高的覆蓋率, 而隨機模式是具有記憶性, 因此有最高覆蓋率以及最低重複率的優點本論文中, 由於本實驗室機器人無外型設計, 因此在座標點擷取時會產生誤差, 影像處理方面還有改善空間在影片的擷取, 此次實驗為每秒擷取兩張圖片, 其呈現數據為離散型, 在往後研究將影像擷取技術提升, 讓數據可以以連續型積分的方式產生, 在覆蓋率分析上將更加準確透過本次研究讓我們更加熟悉機器人路徑以及覆蓋率特性, 雖然此次本實驗式機器人分析數據不差, 但仍有加強空間, 在未來我們將藉由此次的研究成果, 研發出最佳化路徑清潔機器人 97

參考文獻 [1] E. Garcia, M. A. Jimenez, P. Gonzalez De Savtos, and M. Armada, The evolution of robotics research from industrial robotics to field and service robotics, IEEE Robotics & Automation Magazine, pp. 2-15, 2007. [2] 陳朝陽,2005, 智慧型居家清潔機器人之研發, 國立成功大學, 碩士論文 [3] 林宗德,2005, 居家清潔機器人之全域覆蓋路徑規畫與實現, 國立成功大學, 碩士論文 [4] 吳豐成,2009, 運用 ADAMS 模擬自動清掃機器人控制與清掃效率分析, 國立高雄第一科技大學, 碩士論文 [5] M. Cong, L. G. Jin, and B. Fang, Intelligent robot moxers: a review, ROBOT, vol. 29, no. 4, pp. 407-416, 2007. [6] irobot Roomba, http://resources.irobot.com/index.php/howitworks/us/3881236/. 2011. [7] RV-13, http://papago.twcom.net/. 2011. [8] Navibot,http://www.samsung.com/sec/consumer/living-appliances/vacuumcleane rs/robot/vc-rl87v/. 2011. [9] AGAMA AiBOT RC520A, http://www.agamazone.com/products_rc_520a.html. 2011. [10] AGAi 易管家 EC MINI, http://www.agaitech.com/user/list.jsp?id1=125&id2=677, 2011 [11] A. Pirzadeh and W. Snyder, A Unified Solution to Coverage and Search in Explored and and Unexplored Terrains using Indirect Control, Proc.of the IEEE Int. Conf. on Robotics Automation, Vol.3, pp. 2113-2119, 1990. [12] E. U. Acar, H. Choset, and J. Y. Lee, Sensor-based coverage with extended range detectors, IEEE Trans. Robotics, vol. 22, issue 1, pp. 189-198, 2006. [13] H. Choset and P. Pignon, Coverage path planning: the boustrophedon cellular decomposition, In Proceedings of the International Conf. on Field and Service Robotics, Canberra, Australia, 1997. [14] H. Choset, Coverage for robotics-a survey of recent results, Annals of Mathematics and Artificial Intelligence, vol. 31, no. 1-4, pp. 113-126, 2001. [15] P. M. Lee, B. H. Jun, K. Kim, J. Lee, T. Aoki, and T. Hyakudome, Simulation of 98

an inertial acoustic navigation system with range aiding for an autonomous underwater vehicle, IEEE J. Oceanic Engineering, vol. 32, no. 2, pp. 327-345, 2007. [16] J. A. Cobano, J. Estremera, and P. G. Gonzalez de Santos, Accurate tracking of legged robots on natural terrain, Autonomous Robots, vol. 28, issue 2, pp. 231-244, 2010. [17] I. Rekleitis, A. P. New, E. S. Rankin and H. Choset Efficient boustrophedon multi-robot coverage: An algorithmic approach, Ann. Math. Artif. Intell., vol. 52, no. 24, pp. 109-142, 2008. [18] A. Zelinsky, A Mobile Robot Exploration Algorithm, IEEE Transactions on Robotics and Automation, Vol.8,pp.707-717,1992. [19] A. Zelinsky, R. A. Javis, J. C. Byarne, and S. Yuta, Planning Paths of Complete Coverage of an Unstructured Environment by a Mobile Robot, Proceedings of the IEEE International Conference on Robotics Automation, pp.533-538, 1993. [20] J. S. Oh, Y. H. Choi, J. B. Park, and Y. F. Zheng, Complete coverage navigation of cleaning robots using triangular-cell-based map, IEEE Transactions on Industrial Electronics, Vol.51, No.3, 2004. [21] J. S. Oh, Y. H. Choi, J. B. Park, and Y. F. Zheng, Navigation of Cleaning Robots Using Triangular-Cell Map for Complete Coverage, Proceedings of the IEEE International Symposium on Robotics and Automation, Vol.2, pp.2006-2011, 2003. [22] A. Zhu and S. X. Yang, A neural network approach to task assignment of multi-robots, IEEE Trans. Neural Netw., vol. 17, no. 5, pp. 1278-1287, 2006. [23] A. Arleo, F. Smeraldi, and W. Gerstner, Cognitive navigation based on nonuniform Gabor space sampling, unsupervised growing networks, and reinforcement learning, IEEE Trans. Neural Netw., vol. 15, no. 3, pp. 639-652, 2004. [24] E. U. Acar, H. Choset, and J. Y. Lee, Sensor-based coverage with extended range detectors, IEEE Trans. Robotics, vol. 22, issue 1, pp. 189-198, 2006. [25] C. F. Juang and C. H. Hsu, Reinforcement ant optimized fuzzy controller for mobile-robot wall-following control, IEEE Trans. on Industrial Electronics, vol. 56, issue 10, pp. 3931-3940, 2009. [26] M. Katsev, A. Yershova, B. Tovar, R. Ghrist, and S.M. LaValle, Mapping and Pursuit-Evasion Strategies For a Simple Wall- Following Robot, IEEE Trans. on Robotics, vol. 27, no. 1, pp.113-128, 2011. [27] D. E. Swihart, A. F. Barfield, E. M. Griffin, R. C. Lehmann, S. C. Whitcomb, B. 99

Flynn, M. A. Skoog, and K. E. Processor, Automatic ground collision avoidance system design, integration, & flight test, IEEE Aerospace and Electronic Systems Magazine, vol. 26, no. 5, pp. 4-11, 2011. [28] S.J. Yoo, Adaptive tracking and obstacle avoidance for a class of mobile robots in the presence of unknown skidding and slipping, Control Theory & Applications, IET, vol. 5, no. 14, pp. 1597-1608, 2011. [29] S. Bota and S. Nedevschi, Vision based obstacle tracking in urban traffic environments, Intelligent Computer Communication and Processing, pp. 231-238, 2011. [30] M. R. Strakowski, B. B. Kosmowski, R. Kowalik, and P. Wierzba, An ultrasonic obstacle detector based on phase beamforming principles, Sensors J. IEEE, vol. 6, no. 1, pp. 179-186, 2006. [31] Z. Liang, S. Zhu, Cooperative Distributed Sensors for Mobile Robot Localization College of Automation, Nanjing University of Posts and Telecommunications, Nanjing, China, February 22, 2010. [32] A. Apatean, C. Rusu, A. Rogozan, and A. Bensrhair, Visible-infrared fusion in the frame of an obstacle recognition system, 2010 IEEE International Conf. on Automation Quality and Testing Robotics, vol. 1, pp.1-6, 2010. [33] S. Duan, Y. Li, S. Chen, L. Chen, J. Min, L. Zou, Z. Ma, and J. Ding, Research on obstacle avoidance for mobile robot based on binocular stereo vision and infrared ranging, 2011 9th World Congress on Intelligent Control and Automation, pp. 1024-1028, 2011. [34] C. J. Taylor and D. J. Kriegman, Vision-Based Motion Planning and Explortion Algorithms for Mobile Rbots IEEE Trans. on Robotics and Automation, 14 (3) pp.417-426,1998. [35] R. A. Hicks and R. K. Perline, Equiresolution Catadioptric Sensors, Appl. Opt., 44 (29) pp. 6108-1114, 2005. [36] D. Murray and A. Basu, Motion Tracking with an Active Camera, IEEE Transactions on Pattern Analysis and Machine Intelligence, 16 (5) pp. 449-459, 1994. [37] P. D. Lin, and T. T. Liao, A new model of binocular stereo coordinate measurement system based on skew ray tracing, ASME Journal of Dynamics, Measurement and Control, 126(1) pp.102-114, 2004. [38] Y.I. Abdel-Aziz, and H.M. Karara, Direct Linear Transformation from Comparator Coordinates into Object Space Coordinates in Close-Range Photogrammetry, Proceedings of the Symposium on Close-Range Photogrammetry (pp.1-18), Falls Church, VA: American Society of 100

Photogrammetry,1971. [39] H. Hatze, High-Precision Three-Dimensional Photogrammetric Calibration and Object Space Reconstruction Using a Modified DLT-Approach, J. Biomech 21 pp.533-538,1988. [40] J. Weng, P. Cohen, and M. Herniou, Camera Calibration with Distortion models and accuracy evaluation, IEEE Trans. Pattern Analysis and Machine Intelligence, 14, (10) pp.965-980,1992 [41] Z. Zhang, A Flexible New Technique for Camera Calibration, IEEE Transactions on Pattern Analysis and Machine Intelligence, 22 (11) pp.1330-1334, 2000. [42] L. Ma, Y. Q. Chen, and K. L. Morre, Flexible Camera Calibration Using a New Analytical Radial Undistortion Formula with Application to Mobile Robot Localization, Proceedings of the IEEE International Symposium on Intelligence Control, pp.799-804, 2003. [43] F. Y. Wang, A Simple and Analytical Procedure for Calibrating extrinsic Camewra Parameters, IEEE Trans. Robotics and Automation, 20,(1) pp.121-124,2004 [44] F. Y. Wang, An Effecient Coordinate Frame Calibration Method for 3-D Measurement by Multiple Camera Systems, IEEE Trans. Systems, Man, and Cybernetics: Part C, 35 (5), 2005. [45] C. John, A computational approach to edge detection. Pattern Analysis and Machine Intelligence, IEEE Transactions on, PAMI-8(6):679 698, Nov. 1986. 101

清 潔 機 器 人 覆 蓋 率 分 析 之 研 究 A Study of Coverage Analysis for Cleaning Robot 研 究 生 : 林 育 昇 撰 指 導 教 授 : 陳 智 勇 博 士 樹 德 科 技 大 學 電 腦 與 通 訊 研 究 所 碩 士 論 文 A Th

清潔機器人覆蓋率分析之研究 A Study of Coverage Analysis for Cleaning Robot 研究生 : 林育昇撰指導教授 : 陳智勇博士樹德科技大學電腦與通訊研究所碩士論文 A Th