[發明專利]用來從抽樣數據抽取整合直方圖的計算機實施方法

無效

• 申請號: 200680001019.1
• 申請日: 2006-02-03
• 公開（公告）號: CN101069192A
• 公開（公告）日: 2007-11-07
• 發明（設計）人: 法蒂·M.·波利克力
• 申請（專利權）人: 三菱電機株式會社
• 主分類號: G06K9/46
• 分類號: G06K9/46;G06T7/00;G06F17/18
• 代理公司: 中國國際貿易促進委員會專利商標事務所
• 代理人: 黨建華

技術領域

本發明一般涉及表示和搜索真實信號的數據樣本，并且更具體地說，涉及借助于從數據樣本抽取的直方圖表示和搜索以檢測對象。

背景技術

如圖1中所示，直方圖100是‘條帶(bin)’101的陣列。每個條帶與抽樣數據集的值的范圍102相對應。條帶‘計數’在特定范圍中樣本值出現的頻率103。換句話說，直方圖表示在數據集中樣本的頻率分布。

例如，抽樣彩色圖像的直方圖‘計數’在每個條帶中具有相同顏色值的象素的數量。因而，直方圖是從抽樣數據集到非負實數集+R的映像。

從概率的觀點看，直方圖的標準化生成模擬數據集的概率密度的離散函數。直方圖可用來確定數據集的統計性質，如分布、散布、及分離。

直方圖用在多種計算機視覺應用程序中，如基于對象的索引和檢索，C.Carson，M.Thomas，S.Belongie，J.M.Hellerstein和J.Malik，“Blobworld：A?system?for?region-based?image?indexing?and?retrieval”，Proceedings?of?ICVS，1999和J.Huang，S.Kumar，M.Mitra，W.J.Zhu、和R.Zabih，“Image?indexing?using?color?correlograms”，Proceedings?of?CVPR，1997；圖像分段，D.A.Forsyth和J.Ponce.“Computer?Vision：A?Modern?Approach”，Prentice?Hall，2002和S.Ruiz-Correa，L.G.Shapiro、和M.Meila，“A?new?paradigm?forrecognizing?3-D?object?shapes?from?range?data”，Proceedings?ofCVPR，2003；對象檢測，C.Papageorgiou，M.Oren、和T.Poggio，“Ageneral?framework?for?object?detection”，Proceedings?of?ICCV，1998；及對象跟蹤，D.Comaniciu，V.Ramesh和P.Meer，“Real-timetracking?of?nonrigid?objects?using?mean?shift”，Proceedings?of?CVPR，2000。

一種臉部檢測器由P.Viola和M.Jones描述，“Robust?real-timeface?detection”，Proceedings?of?ICCV，第II頁，744，2001。如由Viola等描述那樣，有可能確定在線性時間中在圖像上掃描的矩形窗口內的強度值之和，而對于每個可能窗口不重復求和算子。對于每個矩形和，要求恒定數量的運算，以確定對于分立矩形的和多次。這定義累計或積分強度圖像，其中每個象素保持在象素左邊和上方的所有值之和，該所有值包括象素本身的值。對于整個圖像借助于每象素僅四次算術運算，可確定積分強度圖像。人們從在圖像的左上角象素中的窗口開始掃描，首先向右并且然后向下。函數把在積分圖像中的當前象素值確定為是在當前象素上方和左邊的所有象素強度之和減去左上的象素值。對于在邊界處的適當修改，借助于另外四次算術運算可確定在矩形中的圖像函數之和。因而，借助于線性量的運算，在線性時間內可確定對于任何矩形的圖像函數之和，以建造積分圖像。

不幸的是，抽取和搜索傳統直方圖是耗時的。只有窮盡搜索能提供全局最佳。次最佳搜索，如梯度下降和應用程序專用約束條件，可加速搜索。然而，依賴于最優解的計算機視覺應用程序，如對象檢測和跟蹤，要求直方圖抽取的理論突破。

在傳統上，窮盡搜索要求測量在具體直方圖與所有可能目標區域的直方圖之間的所有距離。這個過程要求用于對中在每個可能點處的區域，例如象素，的直方圖的產生。在其中在不同標度，即不同目標區域標度(尺寸)，下進行搜索的情況下，過程重復與標度數量一樣多的次數。

圖2表示傳統直方圖搜索的偽代碼200。至今，這種傳統方法是保證找到用于基于直方圖的搜索的全局最佳的唯一已知方案。希望把直方圖抽取和搜索直方圖的速度改進幾個數量級。

發明內容

本發明提供一種用來從笛卡爾(Cartesian)抽樣數據空間中的可能目標區域抽取整合直方圖(integral?histogram)、和搜索抽取的直方圖的方法。