并行Shi-Tomasi圖像角點特征檢測算法

李雨嫣 陳華

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

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

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

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

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

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

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

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

為了解決傳統串行算法中針對大規模圖像運算耗時長的問題，肖漢等[11]提出了一種基于多GPU的Harris角點檢測并行算法。郭志全[12]提出基于數據并行和任務并行的兩種Harris角點檢測算法的并行設計思路，并通過SMT-PAAG仿真器進行實現。王俊超[13]采用對圖像進行網格化分塊的方法，使用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）進行移動后，產生的灰度差值E（x，y，u，v）為：

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

（1） 式中，[S]是移動窗口的區域，w（x，y）是高斯加權函數。使用泰勒展開公式對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的二階函數，根據其特征值的不同，可以將像素點分為角點、直線和平面三種情況。若該點是角點，則因其移動窗口朝任意方向移動都會導致窗口內灰度產生較大的變化，故M矩陣的兩個特征值都較大。

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

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

2 并行算法設計

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

輸入：圖像

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

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

偽代碼如下：

讀取圖像;

圖像灰度化;

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

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

啟動計時器;

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

結束計時器;

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

啟動計時器;

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

結束計時器;

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

計算并輸出加速比;

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

輸入：圖像

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

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

偽代碼如下：

讀取圖像;

圖像灰度化;

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

啟動計時器;

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

結束計時器;

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

啟動計時器;

#pragma omp parallel sections

{

#pragma omp section

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

#pragma omp section

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

#pragma omp section

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

#pragma omp section

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

}//創建從線程，分配計算任務

結束計時器;

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

計算并輸出加速比;

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

輸入：圖像

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

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

偽代碼如下：

讀取圖像;

圖像灰度化;

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

啟動計時器;

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

結束計時器;

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

啟動計時器;

task_group tasks;//構造task_group對象

parallel_invoke（

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

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

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

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

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

tasks.wait（）;//同步

結束計時器;

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

計算并輸出加速比;

3 實驗測試與結果分析

3.1 實驗環境

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

軟件：操作系統：Windows 10

使用工具：Visual Studio2013

3.2 實驗測試用例

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

3.3 實驗結果

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

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

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

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

3.4 結果分析

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

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

4 結束語

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

參考文獻：

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

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

[3] 楊佳豪，袁彤，姚艷.基于三維場景重建的角點檢測方法[J].計算機與網絡，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] 郭志全.計算機視覺關鍵算法的并行化實現[D].西安：西安郵電大學，2016.

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

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

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

【通聯編輯：唐一東】