的景點物件, 景點物件盡可能地占滿了整張圖片, 他們不能處理其中包含兩個景點以上的照片或是沒有完整入鏡的景點照片, 在本文中, 我們提出了一種新方法來辨識非單一完

Size: px

Start display at page:

Download "的景點物件, 景點物件盡可能地占滿了整張圖片, 他們不能處理其中包含兩個景點以上的照片或是沒有完整入鏡的景點照片, 在本文中, 我們提出了一種新方法來辨識非單一完"

授回湿满
7 years ago
Views:

1 基於 Gradent Boostng Classfer 的多景點物件辨識系統戴顯權國立成功大學電腦與通信工程研究所論文摘要由於行動裝置的便利性及講求高效率的執行精準度, 近年來景點辨識與定位成為一個重要的問題早期的研究著重在對一完整影像直接做搜尋, 因此能在短時間內搜尋與定位, 我們希望除了能在龐大的物件資料庫中準確辨識目標圖片, 也能夠標出位置本文中, 我們結合兩種演算法 DPM 和色塊分割方法, 利用 gradent boostng 系統對目標圖片進行多物件的搜尋與定位實驗結果顯示我們提出的算法景點辨識上有很高的準確度關鍵詞 : 景點辨識子視窗偵測法 GBC DPM Abstract In recent year, landmark recognton and locaton becomes an mportant ssue due to the convenence of moble devces and requrng hgh effcent performance accuracy. Early researches focus on searchng wth complete pcture, so searchng and locatng can be done n short perod of tme. We hope not only recognze target pcture accurately but also ndcate locaton n massve object database. In ths paper, we combne two algorthms, deformable part model and mage segmentaton method. Make use of gradent boostng system to perform multple-object searchng and locatng. The experment results demonstrate algorthms we propose perform hgh accuracy n landmark recognton. Keywords: Spot Recognton, Chld Wndow Detecton, GBC, DPM 1. 前言在情境感知 (context-aware) 科技日漸成熟下, 可預期許多計算裝置能根據使用者所處的情境資訊 (context nformaton) 適時調整應用程式所提供的服務所謂的情境資訊可歸類為以下兩種, 物理環境情境 (physcal envronment) 和人為情境 (human factor) 物理環境情境包括地點時間或是其他環境因素如天氣溫度聲音或是氣壓 ; 人為情境則是屬於比較個人的, 例如使用者的社交狀態使用者要達成的任務, 甚至是使用者的情緒狀態都是一種情境當然, 處理情境資訊的方法和系統有各式各樣的, 例如 GPS 定位系統網路定位系統感測系統語音控制系統影像資訊系統, 常見的有影像辨識手勢辨識自然景觀辨識等近年, 行動裝置 (moble devce) 與行動網路的蓬勃發展, 探索環境的方式已有全新的方式, 並能夠提供更好的使用者體驗行動裝置的便利性有助於人們立即得到所需的資訊, 這種特性使計算不再侷限於特定位置或環林芳君國立成功大學電腦與通信工程研究所 s @gmal.com 境, 也因此加強了情境感知的概念以導覽系統來說, 在設計一套適性化模組的時候, 若能將景點辨識整合實踐設計, 將為產品的使用經驗大幅加分, 這類應用可延伸至互動遊戲等開發需求, 因此, 景點辨識是一個不斷增長需求的問題之一在行動裝置上的景點辨識通常使用的結構大致分成兩個步驟, 第一步是從拍攝的圖像中抓取特徵, 接下來第二步, 最常見的方法是密集採樣 (dense samplng)[9] 加上局部特徵擷取 (local features extracton), 密集採樣可以產生高準確度, 但這需要很大的計算成本, 並不適用於行動裝置上, 因此, 我們的研究主要集中於提供一個簡單的方法, 以提高景點辨識的準確度然而, 一般的景點辨識系統均假設一張照片包含一個完整的景點物件, 他們不能處理其中包含兩個景點以上的照片或是沒有完整入鏡的景點照片, 在本文中, 我們提出了一種新的方法來識別上述兩種影像, 我們提出的子視窗搜尋法包含以下兩種方法 :Felzenszwalb 等人所提出的可變形部件模型 (deformable part model, DPM)[10] 和區域分割, 然後從候選的子視窗提取各種影像特徵, 並使用梯度提升分類法 (gradent boosted classfer, GBC) 的分類模型, 得到了前 N 個景點物件的候選名單, 實驗結果表明, 該方法可以非常有效地辨識非單一完整景點物件的影像本論文其餘的章節架構安排如下 ; 第二節中, 我們簡單介紹一下景點辨識的問題和一些與 BOW 相關研究方法接著在第三節, 說明本方法的核心技術第四節將討論實驗結果以證明新方法的效益最後, 第五節則是結論以及未來的研究方向 2. 文獻探討景點辨識系統使用行動裝置拍攝景點照片就可得到景點的相關訊息, 這議題有許多相關的研究 [5,7,8,13,15,17-19] 常見的景點辨識系統的總體框架可以主要分為三個步驟, 如圖 1 所示, 第一步人們可以使用他們的智慧手機拍攝有興趣的景點, 第二步, 剛拍攝的相片傳到伺服器進行處理, 其中包含特徵擷取和景點辨識, 最後將查出的景點名稱和相關資料傳回手機中, 根據不同的應用, 所查到的相關資料可能有各式各樣的, 或許可以導航導遊購物或是提供豐富介紹的網站連結, 進一步還可以達成真實物件和虛擬物件的結合, 也就是擴增實境 (augmented realty)[11,14] 然而上述的研究都預設相片中只有一個完整 47

識目標圖片, 也能夠標出位置本文中, 我們結合兩種演算法 DPM 和色塊分割方法, 利用 gradent boostng 系統對目標圖片進行多物件的搜尋與定位實驗結果顯示我們提出的算法景點辨識上有很高的準確度關鍵詞 : 景點辨識子視窗偵

2 的景點物件, 景點物件盡可能地占滿了整張圖片, 他們不能處理其中包含兩個景點以上的照片或是沒有完整入鏡的景點照片, 在本文中, 我們提出了一種新方法來辨識非單一完整景點物件的影像為了要偵測物件在影像中的位置, 最基本解決方案是直接把查詢影像和資料庫中每張影像作樣板比對 (template matchng), 進而找出相近之影像 [16] 樣板比對的一個限制是, 即將要比對的像素的相對位置應予以保留, 微小的位移極可能會導致錯誤的比對結果為了克服這個缺點, 後來提出的方法大多集中在如何有效地偵測特徵點 (key pont)[4,12], 特徵點是指不會受亮度光照旋轉影響的特定點, 可是很多時候同一物體有是由不同花色不同紋理所構成, 可能降低這些方法的準確度, 當然也有一些系統使用其他方法來降低同一物體的內部差異所造成的影響 [2,5,9] 為了解決上述問題, 物件辨識系統發展出高階的影像特徵描述, 這個方法叫做 bag-of-features (BoF) 或是 Bag of Vsual Words (BoW)[2], 這個想法原本是用來解決文件檢索 (text retreval) 問題, 由不同詞彙出現的次數來描述一篇文件, 具體來說, 先根據資料庫中的影像來製作一個以行為單位的編碼簿 (codebook), 每一個影像中的小區塊都轉換為單一的一行視覺詞彙 (vsual word), 然後統計編碼簿中的視覺詞彙在每一張影像出現的次數, 最後生成一個直方圖, 可惜的是這樣的一個直方圖失去了這些視覺詞彙在空間分布的資訊 Spatal Pyramd Matchng (SPM) 以金字塔模型為概念取得特徵值進行模板比對解決了這個缺點 Localtyconstraned Lnear Codng(LLC) 更進一步解開一個特徵只能屬於一個視覺詞彙的束縛, 每個特徵可以歸屬於不同的視覺詞彙在影像分類和景點辨識的現有方法中, 大都以平均分配且密集選出的特徵點來描述影像, 雖然能精準的描述整張圖像, 可是密集採樣需要很大的計算成本, 應用在行動裝置上並不實際為了應付這個問題,A. Vedald 等人提出了結合線性 SVM 區域搜尋和非線性 SVM 分類器的子視窗搜尋法 [6], 在此方法中, 他們發現了使用跳躍性的子視窗搜尋法, 再利用 GBC 來檢驗候選的子視窗, 基本上, 我們就是按照這個思路來確定景點物件的位置 3. 研究方法在本文中, 我們提出了一個景點辨識系統, 在給定一張內含景點物件的照片, 該系統標示出照片中景點的位置, 我們所提出的系統流程圖如圖 1 所示, 輸入一張影像, 首先系統自動偵測景點可能的區域, 在本文中, 我們使用三種類型的偵測器包括 DPM 可變形部分模型 (deformable part model) 區域分割或是整張影像, 接下來, 把三種方法所偵測的可能區域整合在一起, 然後, 該系統從選定的區域中提取圖像特徵, 並由梯度提升決策樹計算出相似度, 最後, 選取相似度最大且高於閾值的景點名稱 3.1 子視窗搜尋法現有的景點辨識系統均假設一張照片包含一個完整的景點物件, 我們為了辨識非單一完整景點物件的影像, 首先, 在提取圖像特徵之前, 我們估計影像中有若干子視窗可能有景點, 我們採用三種子視窗搜尋法, 包含了完整圖像 DPM 和區域分割法圖 2. 景點辨識系統流程圖 48

這個缺點, 後來提出的方法大多集中在如何有效地偵測特徵點 (key pont)[4,12], 特徵點是指不會受亮度光照旋轉影響的特定點, 可是很多時候同一物體有是由不同花色不同紋理所構成, 可能降低這些方法的準確度, 當然也有一些系

3 最簡單的子視窗搜尋法是整張照片視為一個子視窗, 現有的景點辨識系統一般都是使用這個方法, 而且它們假定一張照片僅包含一個景點項目, 而且希望相片中景點物件占滿整張照片, 但不適用於包含多種景點物件的照片另外, 我們使用了由 Felzenszwalb 等人提出的可變形部件模型 (deformable part model, DPM) [10] 作為主要的偵測器,DPM 是一個兩層的結構, 它由一個覆蓋整個目標的主模型 (root flter) 和幾個子模型 (part model) 組成, 模型就是一個權重向量, 所謂模型的得分就是此權重向量與 HoG 向量的內積, 而檢測窗口的得分是根據主模型的得分加上子模型的分數總和, 每個子模型的分數是子模型在各個空間位置的最高得分, 每個子模型的空間位置得分是子模型在該子窗口上的得分減去變形成本為了偵測物體的區域,DPM 採用滑動視窗法 (sldng wndow), 並且採用了特徵金字塔, 即在不同倍率下提取 HoG 特徵, 利用線性 SVM 來降低計算成本, 在 [10] 中提出了 Latent SVM 方法, 將 DPM 的學習問題轉換為分類問題最後, 我們的區域分割法建立在 Felzenszwalb 和 Huttenlocher 所提出的影像分割技術 [1], 目標是將相似外觀的像素分為同一區域, 相似性是基於顏色的差異, 合併顏色相近的像素區域, 而且分割區塊的數目是可以設置的參數, 在實驗中, 設區塊數目為特徵擷取僅使用 SIFT 和顏色來辨識景點並不夠力, 因此, 在本文中, 結合了種影像特徵, 並使用 GBC 辨識子視窗中的景點物件, 在本節中, 我們將介紹在本文中所使用的影像特徵, 包括具有空間金字塔的 bag-of-features (SP-BoF) 方向梯度直方圖 (hstogram of orented gradent, HoG) 和賈柏濾波器 (Gabor flter) BoF[2] 最近在物件辨識的研究中受注目, 因為它可以簡單地表達圖像內容, 應用於物件分類和辨識, 在 BoF 的流程中, 首先, 擷取一組特徵點並由尺度不變特徵 (scale nvarant feature transform, SIFT) 計算每個特徵點的描述子 (descrptor), 接下來將描述子向量量化為編碼簿中的視覺詞彙, 視覺詞彙在每一張影像出現的次數來表達圖像的內容, 和文件檢索問題中由不同詞彙出現的次數來描述一篇文件的想法有異曲同工之妙, 在實驗中, 設置編碼簿的視覺詞彙數目為 1024 個由於 BoF 沒有考慮 SIFT 描述子的空間分佈, 我們使用空間金字塔表示法 [5] 把空間信息納入考慮, 在空間金字塔表示法中, 子視窗化分為一層一層的網格, 提取的 BoF 向量從每個網格連結成一個長長的向量, 在本文中, 使用三階層的金字塔, 分別是 1*1 2*2 和 3*3 網格, 如圖 3 第一層的 BoF 向量是 1000 維, 第二層的 BoF 向量是 4000 維第三層的 BoF 向量是 9000 維, 最後產生一維的 SP-BoF 向量方向梯度直方圖 (HoG) 由 N. Dalal 等人提出 [3], 它和 SIFT 很類似, 一樣是區域性地描述方向直方圖,HoG 和 SIFT 之間的不同之處在於使用 BoF 完全忽略特徵點的位置訊息, 而 HoG 保存粗略的特徵點位置訊息, 建構每個網格的直方圖並連結成一個長長的特徵向量, 在實驗中, 子視窗將分成 8*8 塊賈柏濾波器可以表示該區域在不同倍率和方向上的紋理圖案, 在本文中, 我們使用的 24 個賈柏濾波器包含四個倍率和六個方向, 首先把某一子視窗分成 8*8 塊, 對每一塊使用 24 個賈柏濾波器然後取平均, 即可獲得 24 維的賈伯特徵向量, 最後將各塊的向量串聯成一個 1536 維的向量 3.3 梯度提升分類法 (GBC) 擷取出每個子視窗的特徵向量後, 使用訓練好的模型來計算出子視窗和各景點物件的相似度, 我們採用 GBC 模擬景點物件的模型, GBC 由 Fredman 提出進一步改進 boostng 分類法, GB 內建一個損失函數 (loss functon) 描述模型的出錯程度, 如果我們的模型能夠讓損失函數持續的下降, 則說明我們的模型在不停的改進, 而最好的方法就是讓損失函數在其梯度 (gradent) 的方向上下降, 下面的內容就是描述 GBC 的演算法 : Algorthm 1. 梯度提升分類演算法 1. N 0 ( x) arg mn L( y, ) 1 f 2. For m = 1 to M 3. (a) For = 1, 2,..., N r m L( y, ( )) f x f ( x )) f f m 1 (b) Ft a regresson tree to the targets r m gvng termnal regons R jm, j = 1, 2,..., J m. 6. (c) For j = 1, 2,..., J m 49

權重向量, 所謂模型的得分就是此權重向量與 HoG 向量的內積, 而檢測窗口的得分是根據主模型的得分加上子模型的分數總和, 每個子模型的分數是子模型在各個空間位置的最高得分, 每個子模型的空間位置得分是子模型在該子窗口

4 7. 8. jm arg mn L ( y, f 1( x ) ) (d) Update m x R jm m J m f ( x) f ( x) m1 jm jm) j1 I( x R 割, 此外, 我們也和 Oxford buldng 所提供的正確物件位置 (Ground truth boundng boxes, GTBB) 比較, 結果顯示我們提出的方法是具有物件偵測能力的 9. Output f ˆ ( x) f M ( x). L(y,f(x)) 為損失函數, 用來衡量樣本預測值 f(x) 與目標值 y 之間的差異,GBC 通常會利用不同的損失函數 L(y,f(x)) 來解決不一樣的問題, 第 1 行 f 0 可以看做初始的預測值, 這個時候只有建立一棵決策樹,GBC 的學習過程就是多棵決策樹的構建過程, 第 2 行代表需要學習 1~M 個模型, 第 3 4 行算出損失函數的梯度向量, 通過梯度向量用來衡量損失函數的減少程度, 當模型越接近梯度向量, 這個模型越好, 重覆了 M 次, 也訓練了 M 個模型 4. 研究結果在實驗中, 我們使用 Oxford Buldngs 資料庫 [20], 由 5062 張圖片構成 11 個景點, 每張圖片都是 1024*768 的尺寸, 照片包含室內和室外的景點不一樣的光照條件和不一樣的視角, 裡面有些照片可能因為豐富的背景導致難以辨認出景點, 資料庫都是建築物也增加了辨識的困難度, 圖 4 為資料庫中的幾張範例影像圖張 Oxford buldng 圖庫中的 ground truth 範例圖 (GTBB) 為了評價景點辨識系統的性能, 我們定義了景點物件分類率 CR, 公式如下所示 : 在實驗中, 我們提出的方法和只使用單個子視窗搜尋法做比較, 包括完整圖像 DPM 區域分圖 5. 不同方法的 CR 比較圖圖 5 顯示了取相似度前 n 個景點下各個方法的分類率, 包含完整影像區域分割 DPM GTBB 還有我們所提出的方法, 目的是為了了解 DPM 和我們提出方法的差異, 可以看出將區域分割和完整圖像提供的子視窗納入考慮, 能夠提升圖像中景點定位的準確度, 取出相似度前八名的景點, 我們實現了 53.8% 的分類率, 雖然只有五成的辨識能力, 但是與 GTBB 所達到的分類率 58.9% 是相當接近的, 可見透過多種子視窗搜尋法可以加強物件的辨識, 這證明了所提出的方法, 做為一種偵測景點的系統可以提高辨識準確度, 我們推測因為測試資料庫中的影像背景十分複雜, 若是沒有透過子視窗搜尋法, 可能無法辨認出影像中的景點接下來, 我們比較不同的分類方法, 包括梯度提升分類 GBC 支持向量機 (support vector machne, SVM) 以及隨機森林 (random forest, RF) 表 1 顯示出單個分類演算法與其花費時間, 這裡使用 F 度量 (F-measure), 同時兼顧查準率 (precson) 與查全率 (recall) 的度量方式, 最高的 F 度量與最低的 F 度量只有 2% 的差異, 可是所需要的資料量卻差了快 2000 張實驗使用環境為 Wndows 7(64-bt), CPU 為 Intel(R) Core(TM) K CPU 3.4GHz, 記憶體 64GB 表 1. 分類器比較表分類器 F 度量計算時間 (sec) 模型所需的圖片數 SVM RF GBC 計算時間顯示,RF 比 GBC 和 SVM 有效的多, 然而, 計算時間指是訓練兩種分類所需要的時間, 如果需要三種以上的分類,SVM 需要大量時間才能發現快速收斂的參數, 至於 RF 會強迫訓練數據收斂, 這也是它比其他分類器較快的原因, 然而, 它需要較多的訓練數據, 這可能會影響到我們 50

L(y,f(x)) 為損失函數, 用來衡量樣本預測值 f(x) 與目標值 y 之間的差異,GBC 通常會利用不同的損失函數 L(y,f(x)) 來解決不一樣的問題, 第 1 行 f 0 可以看做初始的預測值, 這個時候只有建立一棵決策樹,GBC 的學習過程就是多棵

5 的應用, 因此,GBC, 也就是我們選擇的分類器, 是比較實用的結論與討論在本文中, 我們提出兩步驟的方法來偵測影像中的景點物件, 在實驗中, 取出相似度前八名的景點, 我們可以達到 53.8% 的結果, 比原本只用整張圖片有更強的辨識準確度, 而 GBC 可以降低影像所需的個數, 不需要輸入數千張影像即可構建強大的判別模型, 以上結果展現出此方法的有效性對於未來的研究中, 我們需要引入景點之間共同出現的機率來提高辨識的準確率參考文獻 [1] P. Felzenszwalb and D. Huttenlocher, Effcent graph-based mage segmentaton, n IJCV, 59(2), 2004, pp. 1, 2, 3. [2] Fe-Fe, L., Perona, P., A Bayesan Herarchcal Model for Learnng Natural Scene Categores n Computer Vson and Pattern Recognton, 2005, pp [3] N. Dalal, B. Trggs, I. Rhone-Alps, and F. Montbonnot, Hstograms of orented gradents for human detecton, n Proc. of IEEE Computer Vson and Pattern Recognton, 2005, pp [5] Lazebnk, S., Schmd, C., Ponce, J., Beyond bags of features: Spatal pyramd matchng for recognzng natural scene categores n Computer Vson and Pattern Recognton, CVPR, 2006, pp [4] Nst er, D., Stew enus, H., Lnear Tme Maxmally Stable Extremal Regons n Forsyth, D., Torr, P., Zsserman, A. (eds.) ECCV 2008, Part II. LNCS, vol. 5303, pp [5] Zheng Y-T, Zhao M, Song Y, Adam H, Buddemeer U, Bssacco A, Brucher F, Chua T-S, Neven H, Tour the world: Buldng a webscale landmark recognton engne n Proc. IEEE Int Conf Comput Vs Pattern Recognt, 2006, pp [6] A. Vedald, V. Gulshan, M. Varma, and A. Zsserman, Multple kernels for object detecton n Proc. of IEEE Internatonal Conference on Computer Vson, 2009, pp [7] Yap K-H, Chen T, L Z, Wu K, A comparatve study of moblebased landmark recognton technques n IEEE Intell Syst., vol. 25, no.1, 2010, pp [8] Zamr AR, Shah M, Accurate mage localzaton based on Google Maps street vew n Proc. Eur Conf Comput Vson, 2010, pp [9] Wang, J., Yang, J., Yu, K., Lv, F., Huang, T., Gong, Y., Localty-constraned lnear codng for mage classfcaton n Conference on Computer Vson and Pattern Recognton, CVPR, San Francsco, CA, 2010, pp [10] P.F. Felzenszwalb, R.B. Grshck, D. McAllester, and D. Ramanan, Object detecton wth dscrmnatvely traned part-based models n IEEE Transactons on Pattern Analyss and Machne Intellgence, vol. 32, no. 9, 2010, pp [11] Shn, C., Km, H., Kang, C., Jang, Y., Cho, A., Woo, W., Unfed Context-Aware Augmented Realty Applcaton Framework for User-Drven Tour Gudes n Internatonal Symposum on Ubqutous Vrtual Realty, ISUVR, Gwangju, 2010, pp [12] Rosten, E., Porter, R., Drummond, T., Faster and Better: A Machne Learnng Approach to Corner Detecton n IEEE Transactons on Pattern Analyss and Machne Intellgence, vol.33, no.1, 2010, pp [13] Chen T, Yap K-H, Chau L-P, Integrated content and context analyss for moble landmark recognton n IEEE Trans. Crcuts Syst. Vdeo Technol., vol. 21, no. 10, 2010, pp [14] Chen, D., Tsa, S., Hsu, C.-H., Sngh, J. P., Grod, B., Moble augmented realty for books on a shelf n Internatonal Conference on Multmeda and Expo, ICME, Barcelona, 2011, pp [15] Bhattacharya P, Gavrlova M, A survey of landmark recognton usng the bag-of-words framework n Intellgent Computer Graphcs 2012: Studes n Computatonal Intellgence, vol. 441, 2013, pp [16] Da-Duong, T., Chau-Sang, N., Vnh-Tep, N., Mnh-Tret, T., Anh-Duc, D., Realtme arbtrary-shaped template matchng process n 12th Internatonal Conference on Control Automaton, Robotcs and Vson, 2012, pp [17] Lee Y, Km C, Km Y, Whangbo T, Facal landmarks detecton usng mproved actve shape model on androd platform n Multmed Tools Applcatons, 2013, do: /s y. [18] Bobek S, Nalepa GJ, Lge za A, Adran WT, Kaczor K, Moble context-based framework for threat montorng n urban envronment wth socal threat montor n Multmed Tools Appl, 2014, do: /s [19] Chen T, Yap K-H, Dscrmnatve BoW framework for moble landmark recognton n IEEE Trans. Cybern, vol. 44, no. 3, 2014, pp [20] The Oxford Buldngs Dataset, vgg/data/oxbuldngs/ 51

提高辨識的準確率參考文獻 [1] P. Felzenszwalb and D. Huttenlocher, Effcent graph-based mage segmentaton, n IJCV, 59(2), 2004, pp. 1, 2, 3. [2] Fe-Fe, L., Perona, P.

6-1-1極限的概念

6-1-1極限的概念選修數學 (I-4 多項式函數的極限與導數 - 導數與切線斜率定義. f ( 在的導數 : f ( h 對實函數 f ( 若極限存在 h h 則稱 f ( 在點可微分而此極限值稱為 f ( 在的導數以 f ( 表示 f ( f ( 函數 f ( 在的導數也可以表成 f ( 註 : 為了

的 景 點 物 件, 景 點 物 件 盡 可 能 地 占 滿 了 整 張 圖 片, 他 們 不 能 處 理 其 中 包 含 兩 個 景 點 以 上 的 照 片 或 是 沒 有 完 整 入 鏡 的 景 點 照 片, 在 本 文 中, 我 們 提 出 了 一 種 新 方 法 來 辨 識 非 單 一 完

的景點物件, 景點物件盡可能地占滿了整張圖片, 他們不能處理其中包含兩個景點以上的照片或是沒有完整入鏡的景點照片, 在本文中, 我們提出了一種新方法來辨識非單一完