并行Shi-Tomasi圖像角點(diǎn)特征檢測(cè)算法

李雨嫣 陳華

摘 要：在大規(guī)模圖像的處理中，串行角點(diǎn)檢測(cè)算法存在著運(yùn)算量大、耗時(shí)長(zhǎng)的問(wèn)題?；贏PI、OpenMP及PPL多核CPU技術(shù)，提出了三種改進(jìn)的并行角點(diǎn)檢測(cè)算法。實(shí)驗(yàn)結(jié)果顯示，三種并行算法對(duì)不同尺寸的圖片均具有較好的加速效果。此外，實(shí)驗(yàn)采取不同的線程數(shù)量進(jìn)行測(cè)試?；贏PI的并行檢測(cè)算法加速比在四線程情況下平均可達(dá)3.02，在八線程情況下平均可達(dá)3.85?；贠penMP的并行檢測(cè)算法加速比在四線程情況下平均可達(dá)2.26，在八線程情況下平均可達(dá)3.30?；贏PI和OpenMP的并行檢測(cè)算法均具有良好的多核可擴(kuò)展性。三種并行算法中，基于API的并行檢測(cè)算法具有最高最穩(wěn)定的加速效果。

關(guān)鍵詞：Shi-Tomasi; 角點(diǎn)檢測(cè); API; OpenMP; PPL

中圖分類(lèi)號(hào)：TP391? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2022）06-0100-05

開(kāi)放科學(xué)（資源服務(wù)）標(biāo)識(shí)碼（OSID）：

圖像中關(guān)鍵區(qū)域的形狀由角點(diǎn)所決定，角點(diǎn)能夠反應(yīng)圖像中重要的特征信號(hào)，因而成為圖像的重要局部特征之一[1]。角點(diǎn)在影像重建[2-3]、圖像配準(zhǔn)[4]和目標(biāo)跟蹤[5-6]等多種計(jì)算機(jī)視覺(jué)處理任務(wù)中均有著廣泛的應(yīng)用。

對(duì)角點(diǎn)的定義一般可以分為三種，即圖像邊界曲線具有極大曲率值的點(diǎn)、圖像中梯度值和梯度變化率很高的點(diǎn)和圖像邊界方向變化不連續(xù)的點(diǎn)[7]。針對(duì)不同的定義，目前存在不同的角點(diǎn)檢測(cè)算法[8]。

1988年，Chris Harris和Mike Stephens兩人在H.Moravec算法的基礎(chǔ)上，應(yīng)用鄰近像素點(diǎn)灰度差值的概念對(duì)角點(diǎn)進(jìn)行判斷，提出了基于自相關(guān)矩陣的角點(diǎn)提取算法，稱(chēng)為Harris算法[9]。1993年，Jianbo Shi和Carlo Tomasi兩人對(duì)Harris算法中的分?jǐn)?shù)公式進(jìn)行了改進(jìn)，提出了Shi-Tomasi角點(diǎn)檢測(cè)算法[10]。Shi-Tomasi角點(diǎn)檢測(cè)算法是基于圖像灰度的一種檢測(cè)方法，該方法通過(guò)計(jì)算每個(gè)像素點(diǎn)的曲率以及梯度進(jìn)行角點(diǎn)檢測(cè)，可以有效地避免由圖像邊緣編碼帶來(lái)的分割和邊緣提取問(wèn)題，是目前常用的角點(diǎn)檢測(cè)算法之一。

為了解決傳統(tǒng)串行算法中針對(duì)大規(guī)模圖像運(yùn)算耗時(shí)長(zhǎng)的問(wèn)題，肖漢等[11]提出了一種基于多GPU的Harris角點(diǎn)檢測(cè)并行算法。郭志全[12]提出基于數(shù)據(jù)并行和任務(wù)并行的兩種Harris角點(diǎn)檢測(cè)算法的并行設(shè)計(jì)思路，并通過(guò)SMT-PAAG仿真器進(jìn)行實(shí)現(xiàn)。王俊超[13]采用對(duì)圖像進(jìn)行網(wǎng)格化分塊的方法，使用OpenMP對(duì)Shi-Tomasi角點(diǎn)檢測(cè)算法進(jìn)行了并行化設(shè)計(jì)。朱超[14]等分別基于CPU和GPU對(duì)Harris角點(diǎn)檢測(cè)算法進(jìn)行了并行化設(shè)計(jì)。

本文研究的目的是采用API，OpenMP和PPL三種并行CPU加速技術(shù)，改善Shi-Tomasi角點(diǎn)檢測(cè)算法耗時(shí)長(zhǎng)的問(wèn)題。

1 串行算法描述

1.1 Shi-Tomasi角點(diǎn)檢測(cè)算法原理

將一個(gè)窗口置于圖像之上，對(duì)其進(jìn)行移動(dòng)。設(shè)圖像I（x，y）在點(diǎn)（x，y）處以偏移量（u，v）進(jìn)行移動(dòng)后，產(chǎn)生的灰度差值E（x，y，u，v）為：

[Ex，y，u，v=x，y∈Swx，yIx+u，y+v-Ix，y2]? ? ?（1）

（1） 式中，[S]是移動(dòng)窗口的區(qū)域，w（x，y）是高斯加權(quán)函數(shù)。使用泰勒展開(kāi)公式對(duì)I（x+u，y+v）進(jìn)行近似，得到下式：

[Ix+u，y+v=Ix，y+?I?xu+?I?yv+Ou2，v2]? ? ?（2）

將（2）式代入（1）式當(dāng)中可得：

[Ex，y，u，v=u，vx，y∈Swx，yI2xIxIyIxIyI2yuv]? ? ?（3）

設(shè)[M]矩陣為：

[M=x，y∈Swx，yI2xIxIyIxIyI2y]? ? ? ? ? ? （4）

代入可得：

[Ex，y，u，v=u，vMuv]? ? ? ? ?（5）

（5） 式中，M矩陣是關(guān)于x和y的二階函數(shù)，根據(jù)其特征值的不同，可以將像素點(diǎn)分為角點(diǎn)、直線和平面三種情況。若該點(diǎn)是角點(diǎn)，則因其移動(dòng)窗口朝任意方向移動(dòng)都會(huì)導(dǎo)致窗口內(nèi)灰度產(chǎn)生較大的變化，故M矩陣的兩個(gè)特征值都較大。

在Shi-Tomasi算法當(dāng)中，采用一個(gè)角點(diǎn)響應(yīng)值R作為判斷角點(diǎn)質(zhì)量的依據(jù)。當(dāng)R值大于設(shè)定的閾值時(shí)，判斷該像素點(diǎn)為一個(gè)角點(diǎn)[9]。

[R=minλ1，λ2]? ? ? ? ? ? ? ? （6）

2 并行算法設(shè)計(jì)

算法1 基于Windows API的Shi-Tomasi并行算法

輸入：圖像

輸出：標(biāo)記出角點(diǎn)的特征圖像

算法描述：采取數(shù)據(jù)并行的思想，將輸入圖像切割為n等分的子區(qū)域，每一個(gè)區(qū)域由一個(gè)線程進(jìn)行處理。每一個(gè)線程完成所分配區(qū)域的初始化、梯度值計(jì)算、相關(guān)矩陣M的計(jì)算、角點(diǎn)響應(yīng)值R的計(jì)算、極大值抑制、Shi-Tomasi角點(diǎn)響應(yīng)的判斷及角點(diǎn)標(biāo)記。定義結(jié)構(gòu)體picture存儲(chǔ)子區(qū)域的相關(guān)信息，用于主線程向從線程傳遞參數(shù)，使用CreateThread指令創(chuàng)建從線程。以四線程為例，該方法的并行計(jì)算流程如圖1所示。

偽代碼如下：

讀取圖像;

圖像灰度化;

分割原始圖像和灰度圖像;

定義picture結(jié)構(gòu)體變量pi，并將分割子區(qū)域信息存儲(chǔ)到結(jié)構(gòu)體中;

啟動(dòng)計(jì)時(shí)器;

Shitomasi_demo（原始圖像，灰度圖像，輸出窗口句柄，角點(diǎn)個(gè)數(shù)）;//Shi-Tomasi角點(diǎn)檢測(cè)函數(shù)

結(jié)束計(jì)時(shí)器;

計(jì)算并輸出串行算法時(shí)間;

啟動(dòng)計(jì)時(shí)器;

hThread[i] = CreateThread（0， 0， threadHarris， （LPVOID）&pi， 0， NULL）;//創(chuàng)建從線程

結(jié)束計(jì)時(shí)器;

計(jì)算并輸出并行計(jì)算時(shí)間;

計(jì)算并輸出加速比;

算法2 基于OpenMP的Shi-Tomasi并行算法

輸入：圖像

輸出：標(biāo)記出角點(diǎn)的特征圖像

算法描述：本文在FOLK/JOIN模型的基礎(chǔ)上進(jìn)行設(shè)計(jì)。采取數(shù)據(jù)并行的思想，將輸入圖像切割為n等分的子區(qū)域，每一個(gè)區(qū)域由一個(gè)線程進(jìn)行處理。每一個(gè)線程完成所分配區(qū)域的初始化，梯度值計(jì)算，相關(guān)矩陣M的計(jì)算，角點(diǎn)響應(yīng)值R的計(jì)算，極大值抑制，Shi-Tomasi角點(diǎn)響應(yīng)的判斷以及角點(diǎn)標(biāo)記。使用sections和section指令創(chuàng)建多線程，將每個(gè)子區(qū)域分配到不同的線程中并行執(zhí)行。以四線程為例，該方法的并行計(jì)算流程如圖2所示。

偽代碼如下：

讀取圖像;

圖像灰度化;

分割原始圖像和灰度圖像;

啟動(dòng)計(jì)時(shí)器;

Shitomasi_demo（原始圖像， 灰度圖像， 輸出窗口句柄， 角點(diǎn)個(gè)數(shù)）;//Shi-Tomasi角點(diǎn)檢測(cè)函數(shù)

結(jié)束計(jì)時(shí)器;

計(jì)算并輸出串行算法時(shí)間;

啟動(dòng)計(jì)時(shí)器;

#pragma omp parallel sections

{

#pragma omp section

Shitomasi_demo（原圖像分割區(qū)域1， 灰度圖像分割區(qū)域1， 輸出窗口句柄， 角點(diǎn)個(gè)數(shù)/4）;

#pragma omp section

Shitomasi_demo（原圖像分割區(qū)域2， 灰度圖像分割區(qū)域2， 輸出窗口句柄， 角點(diǎn)個(gè)數(shù)/4）;

#pragma omp section

Shitomasi_demo（原圖像分割區(qū)域3， 灰度圖像分割區(qū)域3， 輸出窗口句柄， 角點(diǎn)個(gè)數(shù)/4）;

#pragma omp section

Shitomasi_demo（原圖像分割區(qū)域4， 灰度圖像分割區(qū)域4， 輸出窗口句柄， 角點(diǎn)個(gè)數(shù)/4）;

}//創(chuàng)建從線程，分配計(jì)算任務(wù)

結(jié)束計(jì)時(shí)器;

計(jì)算并輸出并行計(jì)算時(shí)間;

計(jì)算并輸出加速比;

算法3? 基于PPL的Shi-Tomasi并行算法

輸入：圖像

輸出：標(biāo)記出角點(diǎn)的特征圖像

算法描述：采取數(shù)據(jù)并行的思想，將輸入圖像切割為n等分的子區(qū)域，每一個(gè)區(qū)域由一個(gè)線程進(jìn)行處理。每一個(gè)線程完成所分配區(qū)域的初始化、梯度值計(jì)算、相關(guān)矩陣M的計(jì)算、角點(diǎn)響應(yīng)值R的計(jì)算、極大值抑制、Shi-Tomasi角點(diǎn)響應(yīng)的判斷以及角點(diǎn)標(biāo)記。使用task_group和parallel_invoke指令[15]將計(jì)算任務(wù)分給不同的線程。以四線程為例，該方法的并行計(jì)算流程如圖3所示。

偽代碼如下：

讀取圖像;

圖像灰度化;

分割原始圖像和灰度圖像;

啟動(dòng)計(jì)時(shí)器;

Shitomasi_demo（原始圖像， 灰度圖像， 輸出窗口句柄， 角點(diǎn)個(gè)數(shù)）;//Shi-Tomasi角點(diǎn)檢測(cè)函數(shù)

結(jié)束計(jì)時(shí)器;

計(jì)算并輸出串行算法時(shí)間;

啟動(dòng)計(jì)時(shí)器;

task_group tasks;//構(gòu)造task_group對(duì)象

parallel_invoke（

[&]{ tasks.run（[&]{ Harris_Demo（原圖像分割區(qū)域1， 灰度圖像分割區(qū)域1， 輸出窗口句柄， 角點(diǎn)個(gè)數(shù)/4）; }）; }，

[&]{ tasks.run（[&]{ Harris_Demo（原圖像分割區(qū)域1， 灰度圖像分割區(qū)域1， 輸出窗口句柄， 角點(diǎn)個(gè)數(shù)/4）; }）; }，

[&]{ tasks.run（[&]{ Harris_Demo（原圖像分割區(qū)域1， 灰度圖像分割區(qū)域1， 輸出窗口句柄， 角點(diǎn)個(gè)數(shù)/4）; }）; }，

[&]{ tasks.run（[&]{ Harris_Demo（原圖像分割區(qū)域1， 灰度圖像分割區(qū)域1， 輸出窗口句柄， 角點(diǎn)個(gè)數(shù)/4）; }）; }

）;//創(chuàng)建從線程，將任務(wù)添加到task_group對(duì)象中并等待

tasks.wait（）;//同步

結(jié)束計(jì)時(shí)器;

計(jì)算并輸出并行計(jì)算時(shí)間;

計(jì)算并輸出加速比;

3 實(shí)驗(yàn)測(cè)試與結(jié)果分析

3.1 實(shí)驗(yàn)環(huán)境

硬件：CPU（4核）：Intel（R） Core（TM） i5-8300H CPU @ 2.30GHz

軟件：操作系統(tǒng)：Windows 10

使用工具：Visual Studio2013

3.2 實(shí)驗(yàn)測(cè)試用例

部分測(cè)試用例如圖4、圖5所示：

3.3 實(shí)驗(yàn)結(jié)果

為了保證實(shí)驗(yàn)結(jié)果的可靠性，以下加速數(shù)值均取10次測(cè)試的平均值。

3.3.1 基于Windows API的角點(diǎn)檢測(cè)并行算法

3.3.2 基于OpenMP的角點(diǎn)檢測(cè)并行算法

3.3.3? 基于PPL的角點(diǎn)檢測(cè)并行算法

3.4 結(jié)果分析

從上述表格可以看出，基于API和OpenMP的并行算法相較于串行算法具有良好的加速效果。隨著圖片尺寸的增大，基于API的并行算法加速比也隨之增加，由此可見(jiàn)，此種并行方法在處理數(shù)據(jù)量較大的圖像矩陣時(shí)，其加速效果良好。同時(shí)，可能由于受到CPU核數(shù)的限制，在進(jìn)程數(shù)大于CPU數(shù)量時(shí)，雖然這兩種并行算法的加速比依然在增加，但是加速效率有所下降。

相比于基于API與OpenMP的并行算法而言，基于PPL的并行算法的加速比很不穩(wěn)定，尤其是對(duì)于一些尺寸不大的圖片而言。雖然它的平均值與上面兩種方法相近，但上面兩種方法加速比的極差較小。而基于PPL的角點(diǎn)檢測(cè)算法的加速比有時(shí)可高達(dá)接近6，有時(shí)僅有1～2。

4 結(jié)束語(yǔ)

本文針對(duì)Shi-Tomasi角點(diǎn)檢測(cè)算法，在處理大規(guī)模圖像時(shí)面臨的耗時(shí)長(zhǎng)、效率低等問(wèn)題，對(duì)串行算法分別基于API、OpenMP和PPL提出三種多核CPU并行算法進(jìn)行改進(jìn)。實(shí)驗(yàn)結(jié)果表明，三種并行算法均具有良好的加速效果和數(shù)據(jù)可擴(kuò)展性，且基于API和OpenMP的并行算法具有良好的多核可擴(kuò)展性。

參考文獻(xiàn)：

[1] 范娜，俞利，徐伯夏.角點(diǎn)檢測(cè)算法綜述[A].中國(guó)高科技產(chǎn)業(yè)化研究會(huì)信號(hào)處理專(zhuān)家委員會(huì).第六屆全國(guó)信號(hào)和智能信息處理與應(yīng)用學(xué)術(shù)會(huì)議論文集[C].中國(guó)高科技產(chǎn)業(yè)化研究會(huì)信號(hào)處理專(zhuān)家委員會(huì)：中國(guó)高科技產(chǎn)業(yè)化研究會(huì)，2012：4.

[2] 董楊.多視角視頻時(shí)空四維重建理論與方法研究[D].鄭州：戰(zhàn)略支援部隊(duì)信息工程大學(xué)，2020.

[3] 楊佳豪，袁彤，姚艷.基于三維場(chǎng)景重建的角點(diǎn)檢測(cè)方法[J].計(jì)算機(jī)與網(wǎng)絡(luò)，2019，45（5）：43.

[4] 杜亞鵬.圖像拼接的關(guān)鍵技術(shù)研究[D].成都：電子科技大學(xué)，2020.

[5] 金釗，伍雪冬，龔昊，等.一種改進(jìn)Harris角點(diǎn)檢測(cè)的目標(biāo)跟蹤方法[J].湖南科技大學(xué)學(xué)報(bào)（自然科學(xué)版），2018，33（3）：86-92.

[6] 儲(chǔ)琪.基于深度學(xué)習(xí)的視頻多目標(biāo)跟蹤算法研究[D].合肥：中國(guó)科學(xué)技術(shù)大學(xué)，2019.

[7] 黃曉浪.基于灰度變化的角點(diǎn)檢測(cè)算法研究[D].撫州：東華理工大學(xué)，2019.

[8] 章為川，孔祥楠，宋文.圖像的角點(diǎn)檢測(cè)研究綜述[J].電子學(xué)報(bào)，2015，43（11）：2315-2321.

[9] Harris C，Stephens M.A combined corner and edge detector[C]//Proceedings ofthe Alvey Vision Conference 1988.Manchester.Alvey VisionClub，1988.

[10] Shi J B，Tomasi.Good features to track[C]//Proceedings of IEEE Conference on Computer Vision and Pattern Recognition CVPR-94.June15-17，1993.Seattle，WA，USA.IEEEComput.Soc.Press，1994.

[11] 肖漢，周清雷，張祖勛.基于多GPU的Harris角點(diǎn)檢測(cè)并行算法[J].武漢大學(xué)學(xué)報(bào)·信息科學(xué)版，2012，37（7）：876-881.

[12] 郭志全.計(jì)算機(jī)視覺(jué)關(guān)鍵算法的并行化實(shí)現(xiàn)[D].西安：西安郵電大學(xué)，2016.

[13] 王俊超.圖像特征點(diǎn)的快速檢測(cè)與匹配方法研究[D].西安：西安科技大學(xué)，2019.

[14] 朱超，吳素萍.并行Harris特征點(diǎn)檢測(cè)算法[J].計(jì)算機(jī)科學(xué)，2019，46（S2）：289-293.

[15] 陳華.多核并行計(jì)算[M].青島：中國(guó)石油大學(xué)出版社，2018：153-155.

【通聯(lián)編輯：唐一東】