ENGLISH  |   聯絡我們  |   中央研究院
首頁 簡介 徵求授權對象 制式契約 研發人員專頁 相關網站 育成暨萌芽中心 聯絡我們
  首頁 -> 徵求授權對象 列印本頁 網站更新日期: 
快速全域最佳樣板比對演算法

本院覽號:05A- 870910

創作人:洪一平、陳永昇

智財權:獲證專利 TW 127850; US 6,360,013B1

摘要:

在電腦視覺、影像處理及圖形識別等領域中,也許多樣板比對的問題,如區塊運動估測、立體對應、圖形比對等等。這類問題是要在某一搜尋範圍內,找出與指定的樣版最接近、誤差最小的一個樣本。在此,樣版與樣本之間的距離通常定義成平方差的和或絕對值差的和。為了要找到誤差最小的樣本,必須在指定的搜尋範圍內做全域搜尋,若搜尋範圍 s、樣板的維度(即樣板大小)為 d,則計算量為 O(sd)。過去幾十年來,不斷有新的研究根據不同的應用還做各式各樣的簡化,藉以減低計算量。例如在視訊壓縮裡,可以利用梯度下降法 (gradient descent),如著名的 the three-step search,或利用鄰近區塊的運動向量來預估,以減小其搜尋範圍;也可以再累加平方差或絕對值差的過程中,藉由及早跳出法來提前結束累加,以減少所需計算的樣版維度 d。這些方法雖然有效率,但是都不能保證找到全域最小誤差的樣本。在此我們提出一個全新的演算法,能在保證找到全域最家樣綁的前提下減少非常大量的計算。在計算樣本與樣板之間的距離時,由於大部分的樣本再累加幾個維度的距離以後,就會大於全域最佳樣本與樣板之間的距離,因此不需再繼續累加其餘為度的距離。我們的演算法可以簡述如下:首先根據樣本與樣板間第一為的距離將搜尋範圍內所有樣本做排序,然後取出最小距離的樣本再累加其與樣板間第二維的距離並記錄其目前累加的維度。接著根據此時的距離和 (sum of distance) 重新排序,然後取出最小距離樣本再累加旗下一為度的距離並重新紀錄其累加為度。之後再重新排序,一直重複這些步驟直到最小距離和的樣綁已經累加完所有維度。本演算法所增加的額外計算—排序,可以藉由資料結構的設計使得第一次排序以後每次排序的計算量不會超過 log s。根據我們在區塊運動估測的實驗,本厭算法可以減少運算量約達 90% 至 99%以上。

可能的應用範圍:

應用在影像比對。

此項發明的優點:

減少大量的計算。

智財技轉處聯絡人:翁嘉煌 chweng@gate.sinica.edu.tw 02-27872509

95年度中央研究院最佳網站
資訊科學研究所
中文新聞語料庫
InfoMap知識管理及推理系統
生醫文獻相關之語意庫
準則式語言模型
中研院台語語音資料庫(twASIS2017)
雲端字體服務系統
增進手寫輸入效率之方法
讀者喜好文章深度偵測技術
中文剖析系統
Micro Air Pollution Sensing System (MAPS)
中文知識表達系統-廣義知網
補助審查專案管理系統
臺北歷史地圖散步
國際電腦漢字及異體字知識庫
Bounty Workers - 線上微型案件媒合平台
次世代定序線上分析平台1.0版
中文詞知識庫
中文分詞語料庫
快速全域最佳樣板比對演算法
用於自然語言事件辨識的方法跟電腦程式產品
個人化的網頁瀏覽系統
自半結構化主文中摘取資料之系統及方法
結合即時視訊與螢幕展示的同步遠距教學系統
數位化浮水印
電腦系統主要圖框處理裝置
視訊資料之編碼與解碼
XML文件編輯器
資料庫檢索方法與系統
行動網路代理器
可容忍幾何處理的數位影像赫序方法與系統
供多人共同操作單一電腦螢幕之主動是操作控制權轉移裝置及方法
非對稱數位影像浮水印技術
檢索輸入法
基於中文字型架構之反向人機辨識碼之辨識方法
建立迴路電力資訊模型之方法
電腦輔助影像故事創作系統
影像放大方法
高速列車用移動路由器系統及其無縫換手控制方法
基於高斯多項組合模型之音樂標籤自動標記技術
基於同質段落偵測與分類器集成之音樂標籤自動標記技術
使用LIBOR Market Model與Proportional Hazard Model的雙因子Monte Carlo評價法
客製化並納入專家觀點的投資組合建議模組
金融商品評價模組
中文句結構樹資料庫
語意分析暨文件分類技術
「應用群體運算之位置感知服務平台」(PLASH)
SQLMR 雲端資料庫管理系統
紀錄片穩定化技術
視訊監控系統
ASQA 中研院開放式中文問答系統
資料隱私保護軟體 Cellsecu
數位典藏影音資料庫
中文電腦缺字解決方案(漢字構形資料庫)
具有新詞辨識能力的中文斷詞系統
漢語平衡語料庫
線上會議註冊管理系統
多媒體及文件辨識、檢索與管理系統
多媒體及文件辨識、檢索與管理系統

  智財技轉處  Copyright © 2005 智財技轉處 版權所有
  11529 台北市南港區研究院路二段128號  |  電話:+886-2-2787-2554  |  傳真:+886-2-2651-8049  |