[發(fā)明專利]用于檢測(cè)數(shù)字圖像中的圓的方法和系統(tǒng)

有效

• 申請(qǐng)?zhí)枺?/td>: 201310628827.2
• 申請(qǐng)日: 2013-11-29
• 公開(kāi)（公告）號(hào): CN103854279B
• 公開(kāi)（公告）日: 2017-11-07
• 發(fā)明（設(shè)計(jì)）人: B·波伊勒;A·M·斯里帕達(dá)拉奧
• 申請(qǐng)（專利權(quán)）人: 美國(guó)亞德諾半導(dǎo)體公司
• 主分類號(hào): G06T7/13
• 分類號(hào): G06T7/13;G06T7/60;G06T7/66
• 代理公司: 中國(guó)國(guó)際貿(mào)易促進(jìn)委員會(huì)專利商標(biāo)事務(wù)所11038
• 代理人: 金曉

技術(shù)領(lǐng)域

本發(fā)明大致涉及用于檢測(cè)圖像中的圓的系統(tǒng)和方法，且更具體地涉及用于圓的霍夫變換。

背景技術(shù)

圓形物體的檢測(cè)對(duì)于許多實(shí)際應(yīng)用很重要。例如，其用于諸如自動(dòng)裝配和檢驗(yàn)的工業(yè)應(yīng)用中，其中許多組件的形狀是圓的。此外，其可用于自動(dòng)檢測(cè)在多數(shù)歐洲和亞洲國(guó)家是圓形的交通標(biāo)志。圓檢測(cè)還可用于生物計(jì)量應(yīng)用中，所述應(yīng)用用于虹膜識(shí)別以定位虹膜的內(nèi)邊界和外邊界。

一種流行的用于圓檢測(cè)的圖像分析技術(shù)是用于圓的霍夫變換。霍夫變換產(chǎn)生圖像中線的參數(shù)表示；其將實(shí)際空間中的圖像（其通常以笛卡爾空間坐標(biāo)為函數(shù)指定圖像值（例如，亮度和色彩））映射至被適于關(guān)注線或曲線的參數(shù)橫跨的霍夫空間。例如，二維圖像中的直線可被映射至二維參數(shù)空間上，指定其從坐標(biāo)系原點(diǎn)的方向和距離且二維圖像中的圓可被映射至三維參數(shù)空間上，指定圓的中心坐標(biāo)和半徑。

在用于圓的霍夫變換（也被稱作標(biāo)準(zhǔn)霍夫變換或SHT）的簡(jiǎn)單實(shí)施中，維持被圓心（x_c,y_c）和半徑r橫跨的霍夫空間的三維累加器陣列，且對(duì)應(yīng)于邊緣（即，圖像參數(shù)（諸如亮度、色彩或深度）經(jīng)歷離散變化的線）的實(shí)際空間圖像中的像素被解析以通過(guò)使針對(duì)各自元素存儲(chǔ)的計(jì)數(shù)器遞增而給累加器陣列的元素“投票”。在最簡(jiǎn)單的實(shí)施方案中，各邊緣像素給對(duì)應(yīng)于包括所述像素的潛在圓的所有累加器陣 列元素“投票”：例如，查找具有范圍從r_min至r_max的半徑的圓，具有坐標(biāo)（x,y）的邊緣像素給滿足等式(x-x_c)²+(y-y_c)²=r²（其中r_min≤r≤r_max）的累加器陣列中的所有元素（x_c,y_c,r）投票。每個(gè)邊緣像素因此將被映射至霍夫參數(shù)空間中的錐形截面上。對(duì)于位于實(shí)際空間中（即，原始圖像中）的相同圓上的邊緣點(diǎn)，這些錐形截面在單個(gè)點(diǎn)上相交。因此可通過(guò)查找累加器陣列中的局部最大值而識(shí)別圓。

用于圓的SHT需要針對(duì)霍夫累加器陣列的大量執(zhí)行時(shí)間和大存儲(chǔ)器，其通常妨礙陣列存儲(chǔ)在微處理器或微控制器的內(nèi)部存儲(chǔ)器中。此外，其需頻繁隨機(jī)存取累加器陣列，阻礙將直接存儲(chǔ)器存取（DMΑ）及緩存用于典型的嵌入式微控制器和數(shù)字信號(hào)處理器（DSP）。因此，已提出減小處理和存儲(chǔ)器要求的對(duì)SHT的不同修改。例如，利用對(duì)圖像中邊緣方向的了解，邊緣像素所投票的累加器陣列元素的數(shù)量可減至對(duì)應(yīng)于垂直于邊緣的線上（或在所述線周圍的區(qū)域中，以考慮邊緣方向的不準(zhǔn)確估計(jì)）的圓心的那些元素。此外，取代使用三維累加器陣列，可連續(xù)使用二維或更低維度陣列。例如，一些技術(shù)分兩個(gè)步驟來(lái)檢測(cè)圓：第一步驟是識(shí)別可能的中心且第二步驟是估計(jì)每個(gè)中心的半徑。雖然這些修改可改進(jìn)霍夫變換算法的性能，但是其通常不足以促進(jìn)在本地存儲(chǔ)器中緩沖累加器陣列。此外，當(dāng)圖像中存在同心圓或弧時(shí)，如現(xiàn)有技術(shù)中使用的兩步驟算法無(wú)法高效運(yùn)行。因此，亟需進(jìn)一步減小存儲(chǔ)器要求和/或執(zhí)行時(shí)間的穩(wěn)健技術(shù)。

發(fā)明內(nèi)容

本發(fā)明提供用于圓和/或弧的基于霍夫變換的檢測(cè)的系統(tǒng)和方法，其減少或消除對(duì)累加器陣列的隨機(jī)存取并且由此縮短執(zhí)行時(shí)間。不同實(shí)施方案采用兩步驟方法，其中第一步，確定圓的中心坐標(biāo)且第二步，估計(jì)對(duì)應(yīng)于每個(gè)中心的半徑。與現(xiàn)有技術(shù)方法不同，第一步驟無(wú)需解析所有邊緣像素（例如，以所有邊緣像素存儲(chǔ)在邊緣像素緩沖區(qū)中的順序）及針對(duì)每個(gè)像素確定所述像素所投票的二維累加器陣列中的元素，投票將需要連續(xù)存取累加器陣列中的隨機(jī)位置。而且，其 涉及針對(duì)潛在的中心候選者逐條線搜索圖像。識(shí)別特定線中的中心候選者可包括識(shí)別對(duì)所述特定線（其數(shù)量通常明顯比圖像中的總線數(shù)少）投票的邊緣像素的線、解析所識(shí)別的邊緣像素線以對(duì)可能的中心的一維累加器陣列投票并及確定對(duì)應(yīng)于中心候選者的一維累加器陣列的最大值。在許多實(shí)施方案中，一維累加器陣列適于本地存儲(chǔ)器（例如，緩存）并且可被再使用于連續(xù)的中心像素線。

在一些實(shí)施方案中，投票步驟之前是過(guò)濾步驟，其共同分析邊緣像素線（不考慮個(gè)別邊緣像素）以確定其中的邊緣像素總數(shù)并且基于這個(gè)總數(shù)消除未超過(guò)指定閾值的中心像素線；這個(gè)步驟可顯著減小投票步驟中的計(jì)算總數(shù)。過(guò)濾步驟和投票步驟都可利用不同的各自邊緣方向的柱條（bin）中邊緣像素的存儲(chǔ)及/或利用x坐標(biāo)的單獨(dú)緩沖區(qū)中邊緣像素坐標(biāo)的表示和每條線中的邊緣像素的數(shù)量。這些特征可提供附加效率增益并且進(jìn)一步減小存儲(chǔ)器要求。