numpyで高速にSoft-NMSを計算する(16倍高速?)

pythonのnumpyで高速化したSoft-NMS(Soft Non-Maximum Suppression)の実装例を紹介します。過去記事で紹介したリスト(list)とfor文を使用した実装よりも16倍高速化できました。

Soft-NMSは、SSDやYOLOといった物体検出AIの後処理で使用されるNMS(Non-Maximum Suppression)の改良型アルゴリズムで、検出性能の向上に寄与します。

ただし、従来NMSよりも演算量が大きい手法となっていて、高速に計算するのは重要だと思います。

この記事でできること

SSDやYOLOといった物体検出AIでは、検出目標の周辺にたくさんの矩形(長方形)が出力されてしまいます。複数の矩形(長方形)から、重複した矩形を消してすっきりさせるアルゴリズムが従来のNMS (Non-Maximum Suppression)です。

この記事で扱うSoft-NMSは、この従来NMSを発展させた改良方式で、次の論文で提案された手法です。

Bodla, N., Singh, B., Chellappa, R., Davis, L.S.: Soft-nms—improving object detection with one line of code. In: 2017 IEEE International Conference on Computer Vision (ICCV). pp. 5562–5570. IEEE (2017).
https://arxiv.org/abs/1704.04503

以前、Soft-NMSのアルゴリズムの説明やサンプルコード、適用例を次の2つの記事で説明しました。
pythonでSoft-NMSを実装する(1)アルゴリズム実装例
pythonでSoft-NMSを実装する(2)Soft-NMS適用例

ただ、Soft-NMSは従来NMSよりも演算量が大きいデメリットがあります。本記事では、Soft-NMSをnumpyのブロードキャスト演算を使って、高速にsoft-NMSを計算するpython実装例を紹介します。

さらに、この記事で紹介する高速なsoft-NMS実装例と、上の過去記事で紹介した従来のsoft-NMS実装例との計算時間を測定し、その比較結果も掲載します。

では、どのくらい高速化できたかというと、結論としては約16倍高速化できました (私の環境での値になります)。ランダムに矩形を生成してSoft-NMSを適用するという処理を100回繰り返し、処理時間を計測しました。

Soft-NMS(Soft Non-Maximum Suppression)とは

押さえておくべきこととしては、soft-NMSは従来NMSとは違って、矩形を直接する消す手法ではないということです。重複する矩形の信頼度(スコア、confidense)を下げる手法になっています。

重複している矩形を消してすっきりさせるには、soft-NMSを適用後に閾値以下の信頼度(スコア、confidense)の矩形を消すという処理が必要となります。ここが従来のNMSとsoft-NMSとで異なるところです。

また、他に注意することとしては、soft-NMSには2つのアルゴリズムがあります。上でも触れた、重複する矩形の信頼度(スコア、confidense)を下げる方法として、2つの関数が用意されています。

線形関数と指数関数の2つの関数なのですが、どちらが良いのか元の論文でも明記していないため、試しながら選択する必要があるようです。

本記事で紹介するサンプルコードは両方に対応しています。これら2つの関数を、スコア更新関数(線形)、スコア更新関数(指数関数)といったように記載しています。

numpyによるsoft-NMSの高速化

この記事ではnumpyを使ってSoft-NMSを高速に計算する方法を紹介します。

numpyのブロードキャスト演算を使用することで、複数の矩形のIoU (Intersection over Union)を一度に計算して高速化を図ります。

pythonではfor文が遅いという特徴があります。一般的に、for文で配列(リスト、list)の要素に逐次アクセスして計算するよりも、numpyのndarrayの演算を使って要素に対する演算を一気に実行することで高速に計算することができます。

従来のNMSを高速化する実装例は下記の記事で紹介しました。

NMSの高速化で重要となる、複数の矩形のIoUをnumpyで一気に演算して高速化する方法は次の記事で紹介しました。

numpyによる高速なSoft-NMSの実装例

では、高速にSoft-NMSを計算するサンプルコードを記載します。


# 矩形aと、複数の矩形bのIoUを高速に計算
def iou_np(a, b, a_area, b_area):
    # aは1つの矩形を表すshape=(4,)のnumpy配列
    # array([xmin, ymin, xmax, ymax])
    # bは任意のN個の矩形を表すshape=(N, 4)のnumpy配列
    # 2次元目の4は、array([xmin, ymin, xmax, ymax])
    
    # a_areaは矩形aの面積
    # b_areaはbに含まれる矩形のそれぞれの面積
    # shape=(N,)のnumpy配列。Nは矩形の数
    
    # aとbの矩形の共通部分(intersection)の面積を計算するために、
    # N個のbについて、aとの共通部分のxmin, ymin, xmax, ymaxを一気に計算
    abx_mn = np.maximum(a[0], b[:,0]) # xmin
    aby_mn = np.maximum(a[1], b[:,1]) # ymin
    abx_mx = np.minimum(a[2], b[:,2]) # xmax
    aby_mx = np.minimum(a[3], b[:,3]) # ymax
    # 共通部分の幅を計算。共通部分が無ければ0
    w = np.maximum(0, abx_mx - abx_mn + 1)
    # 共通部分の高さを計算。共通部分が無ければ0
    h = np.maximum(0, aby_mx - aby_mn + 1)
    # 共通部分の面積を計算。共通部分が無ければ0
    intersect = w*h
    
    # N個のbについて、aとのIoUを一気に計算
    iou_np = intersect / (a_area + b_area - intersect)
    return iou_np

# スコアの更新関数(線形)
def f_linear_np(ious, iou_threshold=0.5):
    return np.where(ious >= iou_threshold, 1.-ious, 1.)

# スコアの更新関数(指数関数、gauss関数)
def f_gauss_np(ious, sigma=0.5):
    return np.exp(-ious*ious/sigma)

def soft_nms_fast(bboxes, scores, classes, \
             iou_threshold=0.5, sigma=0.5, linear=True):
    if linear == True:
        # 線形のスコア更新関数を使用
        f = f_linear_np
        farg = {"iou_threshold": iou_threshold}
    else:
        # 指数関数のスコア更新関数を使用
        f = f_gauss_np
        farg = {"sigma": sigma}
    
    # bboxesの矩形の面積を一気に計算
    areas = (bboxes[:,2] - bboxes[:,0] + 1) \
             * (bboxes[:,3] - bboxes[:,1] + 1)
    
    # scoreの昇順(小さい順)の矩形インデックスのリストを取得
    sort_index = np.argsort(scores)
    
    # インデックスi=-1(スコア最大)から、スコアが2番目に小さいものまでfor文で回す
    for i in range(-1, -len(scores)+1, -1):
        # スコア最大のインデックスiを取得
        max_scr_ind = sort_index[i]
        # スコア最大以外のインデックスのリストを取得
        ind_list = sort_index[:i]
        # スコア最大の矩形とそれ以外の矩形のIoUを計算
        ious = iou_np(bboxes[max_scr_ind], bboxes[ind_list], \
                     areas[max_scr_ind], areas[ind_list])
        
        # スコアを関数fで更新
        scores[ind_list] = scores[ind_list] * f(ious, **farg)
    
    return bboxes, scores, classes

関数”iou_np()”で1つの矩形と複数の矩形のIoUを一気に計算しています。次の記事で使用した関数と同じです。この記事ではNMSを高速に計算するサンプルコードを書きました。

PythonのnumpyでNMSを高速に演算する(20倍高速?)

関数”f_linear_np()”と関数”f_gauss_np()”は、スコアの更新関数で、それぞれ線形関数と指数関数になっています。これらの関数も、numpy配列を引数として各要素に対して一気に計算しています。

関数”soft_nms_fast()”がNMSを計算するコードの本体です。

引数”bboxes, scores, classes”が、それぞれ矩形の座標、スコア、クラスが格納されたnumpy配列で、”iou_threshold=0.5″が線形関数のスコア更新関数のハイパーパラメータ、”sigma=0.5″が指数関数のスコア更新関数のハイパーパラメータ、 引数”linear”はTrueだと線形関数、Falseだと指数関数をスコア更新関数として選択するフラグです。

サンプルコードの細かい説明は、コード内のコメントを参照して頂くとして省略します。

関数”soft_nms_fast()”の大きな処理の流れとしては、まずスコア更新関数を引数”linear”の値によって選択します。

次に、各矩形の面積”areas”を計算します。矩形座標”bboxes”はnumpy配列で、”bboxes”に格納された矩形の面積をnumpyの演算を使って一気に計算しています。ここで計算した面積”areas”は、後のIoUの計算に使用します。

その次に、scoreを小さい順(昇順)に並べたときのインデックスの番号をnp.argsort関数で計算し、リスト(list)”sort_index”を取得します。

numpy array(配列)のソートの仕方は次の記事で紹介しました。

その後、for文で、インデックスi=-1(スコア最大)の矩形から、スコアが2番目に小さい矩形まで1つずつ選び、選んだ矩形よりも小さいスコアの矩形とのIoUを計算して、スコア更新関数でスコアを更新しています。

スコアが2番目に小さい矩形までfor文で選ぶ理由は、スコアを更新する対象とする矩形は、選んだ矩形よりも小さいスコアの矩形だからです。スコアが2番目に低い矩形を選んだ時は、最小の矩形のみがスコアの更新対象の矩形となります。

numpyによる高速なSoft-NMSの適用例

上で紹介した関数”soft_nms_fast()”の使用したサンプルコードを紹介します。

高速なSoft-NMSの適用に使用したコードと画像

関数”soft_nms_fast()”の使用例は次の通りです。

if __name__ == '__main__':
    import random
    import time
    
    iou_threshold = 0.3
    # 顔の矩形リスト
    bboxes = [[161,50,260,161], 
              [318,135,418,243], 
              [46,267,142,373], 
              [181,244,275,352], 
              [340,351,440,455], 
              [500,257,598,371], 
              [648,33,742,146]]
    classes = ["woman", "woman", "man", "man", "woman", "man", "man"]
    # 信頼度の値は適当
    scores = [0.91, 0.92, 0.93, 0.94, 0.95, 0.96, 0.97]
    random.seed(314)
    
    time_list = [] # 処理時間を格納するリスト(list)
    for dmy in range(100): # 100回Soft-NMSを実行
        # Soft-NMSを計算するための矩形をランダムに生成
        rnd_bboxes, rnd_scores, rnd_classes = \
            random_rects(bboxes, scores, classes)
        # リスト(list)をnumpy配列(ndarray)に変換
        bboxes_np = np.array(rnd_bboxes)
        scores_np = np.array(rnd_scores)
        classes_np = np.array(rnd_classes)
        start = time.perf_counter() # 時間計測の関数
        # 高速なSoft-NMSを実行
        nms_bboxes, nms_scores, nms_classes = \
            soft_nms_fast(bboxes_np, scores_np, classes_np, 
                     iou_threshold=iou_threshold, linear=True)
        nms_time = time.perf_counter() - start # 時間計測の関数
        # 計測した時間(秒)を1000倍して単位をミリ秒をして、time_listに追加
        time_list.append(nms_time*1000)
    
    # 処理時間の平均を取得し表示
    print ("Soft-NMS (linear) time: {0}".format(sum(time_list)/len(time_list)) + " [msec]")

このサンプルコードでは、まず複数の矩形とそれに対応するスコア(信頼度)とクラスをスクリプト内に直書きし、リストbboxes, scores, classesに格納します。

次に、高速なNMSの記事「PythonのnumpyでNMSを高速に演算する(20倍高速?)」と同じように、関数”random_rects()”でbboxesの各矩形に対してランダムに矩形を100個ずつ生成しています。その次に、矩形とスコアとクラスのリスと”bboxes, scores, classes”をnumpy配列に変換するという流れです。

関数”random_rects()”は「PythonのnumpyでNMSを高速に演算する(20倍高速?)」で記述した関数になっています。

このように、ランダムに矩形を生成して関数”soft_nms_fast()”でSoft-NMSを実行という処理がfor文内で実行されており、for文では100回繰り返すとしました。繰り返している理由は後述しますが、計算時間を測定するためです。

100回実行した各回の計算時間は、ミリ秒(msec)単位としリスト”time_list”に格納しました。関数”time.perf_counter()”は計算時間の計測をするための関数で、秒単位の時間をfloatで返し、小数点以下がミリ秒(とそれ以下の単位の時間)となっています。

高速なSoft-NMSを適用した画像の例(beforeとafter)

上のサンプルコードの実行例を画像で示します。

次の画像は、いらすとやの「人脈・コネがない人のイラスト」に対して関数”random_rects()”で矩形をランダムに100個ずつ顔に付与した画像です。

Soft-NMS適用前の画像です。

Soft-NMS適用前のランダムに付与した矩形画像
Soft-NMS適用前のランダムに付与した矩形画像

矩形を100個も重畳すると大変なことになっていますが、これに対してSoft-NMSを適用した結果を画像化すると次のようになります。ただし、Soft-NMSを適用した後、スコアを閾値0.8以下の矩形を消去した画像になります。

高速なsoft-NMS適用後の矩形画像
高速なsoft-NMS適用後の矩形画像

かなりすっきりしました。

上の画像のように、画像に対して矩形(長方形)を描画したり”woman”や”0.93″といったクラス名やスコア(信頼度)の文字を描画したりする方法は次で紹介しましたので参考にしてみてください。

Soft-NMSの処理時間の計測結果

上述のサンプルコードでは計算時間の計測もしています。

pythonでの処理時間の計測方法の詳細は下記の記事を参照ください。

高速なSoft-NMSの計算時間の計測

上で紹介したサンプルコードでは100回のSoft-NMSを計算し、計算時間をリスト”time_list”に格納した後、平均処理時間をprint文で出力するようにしています。

私の環境では次のような平均計算時間となりました。スコア更新関数は線形関数を使用しています。

Soft-NMS (linear) time: 31.4089219999999 [msec]

Soft-NMS 1回あたり約31ミリ秒となりました。

過去の記事「pythonでSoft-NMSを実装する(1)アルゴリズム実装例」で紹介した、for文を使用した高速でないSoft-NMSの実装例でも同様に計算時間を測定しましたが、次のようになりました。

Soft-NMS (linear) time: 510.1117740000003 [msec]

Soft-NMS 1回あたり約510ミリ秒となりました。今回紹介した高速なSoft-NMS計算方法で約16倍高速化できたことがわかります。

ただし、高速化の度合いはPC環境やSoft-NMSで計算する矩形(長方形)によって変わりますのでご注意ください。また、計測した計算時間は関数”soft_nms_fast()”のみで、numpy配列への変換や、スコアが閾値以下の矩形消去などの処理の時間は含みません。

高速なSoft-NMSの計算時間のヒストグラム

100回実行した処理時間をヒストグラム化してみました。

pythonのmatplotlibライブラリを用いたヒストグラムの作成方法は次の記事で紹介しています。

今回は次のようなコードでヒストグラムを生成しました。

 # ヒストグラムの横軸。5刻み50~800の範囲の配列(リスト)
 bin_list1 = [i*5.0 for i in range(161)]

 plt.hist(time_list, bins=bin_list1) # ヒストグラム生成
 plt.savefig("soft_nms_fast/histogram_time1_soft_nms_fast.png") # 画像として出力
 plt.clf() # 図をクリア

生成されたヒストグラムが次の画像です。横軸が処理時間[ミリ秒(msec)]で、橙色の棒グラフが今回記事で紹介した高速なSoft-NMSのコード、青色の棒グラフが以前紹介した高速でない従来のコードでの処理時間となります。

高速なSoft-NMSと従来Soft-NMSを100適用した時のヒストグラム
100回soft-NMSを実行したときの計算時間のヒストグラム (横軸ミリ秒 [msec])
橙色が高速なsoft-NMS、青色が従来のsoft-NMS

従来のSoft-NMSは510ミリ秒(msec)近辺、高速なNMSは約30ミリ秒(msec)周辺に分布していることがわかります。

この記事で紹介した高速なSoft-NMSは、あまりばらつきなく安定的に高速化されていることがわかります。

スコア更新関数を指数関数とした時の処理時間

上ではスコア更新関数として線形関数とした場合の計算時間を記載しましたが、指数関数とした場合の処理時間も見てみます。

スコア更新関数を指数関数とするには、関数”soft_nms_fast()”の引数を次のようにすればOKです。

sigma = 0.5
nms_bboxes, nms_scores, nms_classes = \
    soft_nms_fast(bboxes_np, scores_np, classes_np, 
                  sigma=sigma, linear=False)

計測した平均処理時間は次のようになりました。上で線形のスコア関数を計測したのと同様に、100回の平均です。

Soft-NMS (exp.) time: 30.94376199999985 [msec]

Soft-NMSを1回あたり約31ミリ秒で、線形のスコア更新関数とほぼ同じような結果となりました。

おわりに

SSDやYOLOといった物体検出AIの後処理として使用される、重複した矩形をマージするアルゴリズムSoft-NMSの高速計算方法を紹介しました。

Soft-NMSは従来のNMSよりも高性能な手法ではありますが、演算量はNMSよりも増大します。

この記事では、numpyを使ってSoft-NMSを高速化し、numpyを使わずにリスト(list)とfor文を使用する実装と比べて約16倍に高速化できました。(高速化の度合いは環境や適用する矩形などによって変わります)

コメント

タイトルとURLをコピーしました