李雨嫣 陳華

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

關鍵詞：Shi-Tomasi; 角點檢測; API; OpenMP; PPL

中圖分類號：TP391? ? ? ? 文獻標識碼：A

文章編號：1009-3044（2022）06-0100-05

開放科學（資源服務）標識碼（OSID）：

圖像中關鍵區(qū)域的形狀由角點所決定，角點能夠反應圖像中重要的特征信號，因而成為圖像的重要局部特征之一[1]。角點在影像重建[2-3]、圖像配準[4]和目標跟蹤[5-6]等多種計算機視覺處理任務中均有著廣泛的應用。

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

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

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

本文研究的目的是采用API，OpenMP和PPL三種并行CPU加速技術，改善Shi-Tomasi角點檢測算法耗時長的問題。

1 串行算法描述

1.1 Shi-Tomasi角點檢測算法原理

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

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

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

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

將（2）式代入（1）式當中可得：

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

設[M]矩陣為：

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

代入可得：

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

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

在Shi-Tomasi算法當中，采用一個角點響應值R作為判斷角點質量的依據(jù)。當R值大于設定的閾值時，判斷該像素點為一個角點[9]。

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

2 并行算法設計

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

輸入：圖像

輸出：標記出角點的特征圖像

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

偽代碼如下：

讀取圖像;

圖像灰度化;

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

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

啟動計時器;

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

結束計時器;

計算并輸出串行算法時間;

啟動計時器;

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

結束計時器;

計算并輸出并行計算時間;

計算并輸出加速比;

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

輸入：圖像

輸出：標記出角點的特征圖像

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

偽代碼如下：

讀取圖像;

圖像灰度化;

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

啟動計時器;

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

結束計時器;

計算并輸出串行算法時間;

啟動計時器;

#pragma omp parallel sections

{

#pragma omp section

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

#pragma omp section

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

#pragma omp section

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

#pragma omp section

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

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

結束計時器;

計算并輸出并行計算時間;

計算并輸出加速比;

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

輸入：圖像

輸出：標記出角點的特征圖像

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

偽代碼如下：

讀取圖像;

圖像灰度化;

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

啟動計時器;

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

結束計時器;

計算并輸出串行算法時間;

啟動計時器;

task_group tasks;//構造task_group對象

parallel_invoke（

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

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

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

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

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

tasks.wait（）;//同步

結束計時器;

計算并輸出并行計算時間;

計算并輸出加速比;

3 實驗測試與結果分析

3.1 實驗環(huán)境

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

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

使用工具：Visual Studio2013

3.2 實驗測試用例

部分測試用例如圖4、圖5所示：

3.3 實驗結果

為了保證實驗結果的可靠性，以下加速數(shù)值均取10次測試的平均值。

3.3.1 基于Windows API的角點檢測并行算法

3.3.2 基于OpenMP的角點檢測并行算法

3.3.3? 基于PPL的角點檢測并行算法

3.4 結果分析

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

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

4 結束語

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

參考文獻：

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

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

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

[4] 杜亞鵬.圖像拼接的關鍵技術研究[D].成都：電子科技大學，2020.

[5] 金釗，伍雪冬，龔昊，等.一種改進Harris角點檢測的目標跟蹤方法[J].湖南科技大學學報（自然科學版），2018，33（3）：86-92.

[6] 儲琪.基于深度學習的視頻多目標跟蹤算法研究[D].合肥：中國科學技術大學，2019.

[7] 黃曉浪.基于灰度變化的角點檢測算法研究[D].撫州：東華理工大學，2019.

[8] 章為川，孔祥楠，宋文.圖像的角點檢測研究綜述[J].電子學報，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角點檢測并行算法[J].武漢大學學報·信息科學版，2012，37（7）：876-881.

[12] 郭志全.計算機視覺關鍵算法的并行化實現(xiàn)[D].西安：西安郵電大學，2016.

[13] 王俊超.圖像特征點的快速檢測與匹配方法研究[D].西安：西安科技大學，2019.

[14] 朱超，吳素萍.并行Harris特征點檢測算法[J].計算機科學，2019，46（S2）：289-293.

[15] 陳華.多核并行計算[M].青島：中國石油大學出版社，2018：153-155.

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