JP7089179B2 - 画像認識装置、画像認識方法および画像認識プログラム - Google Patents

Description

本発明は画像認識装置、画像認識方法および画像認識プログラムに関する。

入力画像の中から物体が写った位置と物体の種類とを検出する画像認識の技術がある。画像認識には、予め学習しておいた畳み込みニューラルネットワークなどのニューラルネットワークを使用することがある。例えば、Ｒ－ＣＮＮ（Regions with Convolutional Neural Network）やＦａｓｔ Ｒ－ＣＮＮなどの技術が提案されている。

なお、入力画像に写った移動物や静止物の数を算出する視覚装置が提案されている。提案の視覚装置は、入力画像からエッジ情報を抽出し、エッジ情報によって区切られる領域を背景から分離し、分離した各領域のサイズおよび位置に基づいて、物体が写った領域を判定してカウントする。また、入力画像の中から重要性の高い顕著領域を検出する顕著性情報取得装置が提案されている。提案の顕著性情報取得装置は、入力画像に複数の候補領域を設定し、局所的情報に基づいてピクセル毎のローカル特徴量を算出し、入力画像全体に対する各候補領域の特徴を示すグローバル特徴量を算出する。顕著性情報取得装置は、ローカル特徴量とグローバル特徴量に基づいて各候補領域を評価する。

特開２００１－１４８０２３号公報 特開２０１７－４４８０号公報

Ross Girshick, Jeff Donahue, Trevor Darrell and Jitendra Malik, "Rich feature hierarchies for accurate object detection and semantic segmentation", Proceedings of the 2014 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp.580-587, June 2014 Ross Girshick, "Fast R-CNN", Proceedings of the 2015 IEEE International Conference on Computer Vision (ICCV), pp.1440-1448, December 2015 Shaoqing Ren, Kaiming He, Ross Girshick and Jian Sun, "Faster R-CNN: Towards Real-Time Object Detection with Region Proposal Networks", Proceedings of the Advances in Neural Information Processing Systems 28 (NIPS 2015), pp.91-99, December 2015

画像認識の過程では、物体が写っている可能性のある多数の候補領域を抽出し、各候補領域の評価値を算出し、評価値が高い候補領域を選択するという領域選択を行うことがある。その際、候補領域を示すデータ要素を評価値の順にソート（整列）することがある。候補領域が多い場合、候補領域のソート処理は負荷の高い処理となる。

一方、画像認識には、多数の演算部を有しており多数のスレッドを並列に実行可能なＧＰＵ（Graphics Processing Unit）やＧＰＧＰＵ（General Purpose Graphics Processing Unit）などの画像処理用演算処理装置を使用することがある。しかし、ＣＰＵ（Central Processing Unit）が実行する少数のスレッドのもとで総計算量を低減することを重視する伝統的なソートアルゴリズムでは、画像処理用演算処理装置を活用して候補領域のソート処理を高速化することが難しいという問題がある。

１つの側面では、本発明は、画像認識を高速化できる画像認識装置、画像認識方法および画像認識プログラムを提供することを目的とする。

１つの態様では、複数の演算部を含む演算処理装置と、画像の中から検出された複数の候補領域に対応して、それぞれが候補領域の位置および評価値を示す複数のデータ要素を記憶する記憶部とを有する画像認識装置が提供される。演算処理装置は、複数のデータ要素それぞれのソート後の順位を示すインデックスを、当該データ要素の評価値および少なくとも一部の他のデータ要素の評価値を参照して、複数の演算部を用いて並列に算出し、インデックスの算出後、複数の演算部を用いて、インデックスに基づいて複数のデータ要素を並列に移動させることで、複数のデータ要素をソートする。演算処理装置は、ソート後の複数のデータ要素の順序に基づいて、複数の候補領域の中から一部の候補領域を選択する。また、１つの態様では、画像認識装置が実行する画像認識方法が提供される。また、１つの態様では、コンピュータに実行させる画像認識プログラムが提供される。

１つの側面では、画像認識を高速化できる。

第１の実施の形態の画像認識装置の例を説明する図である。 画像認識装置のハードウェア例を示すブロック図である。 ＧＰＵのハードウェア例を示すブロック図である。 画像認識の流れの例を示す図である。 認識結果の例を示す図である。 画像認識装置の機能例を示すブロック図である。 画像認識の手順例を示すフローチャートである。 物体候補領域選択の手順例を示すフローチャートである。 スコア付き位置データのソート例を示す図である。 第１段階ソートの例を示す図である。 第２段階ソートの例を示す図である。 グループ内のソート例を示す図である。 グループ間のソート例を示す図である。 第１段階ソートのスレッド実行例を示す図である。 第２段階ソートのスレッド実行例を示す図である。 ＧＰＵにおけるメモリ使用例を示す図である。 ＧＰＵにおけるメモリ使用例を示す図（続き）である。 物体候補領域ソートの手順例を示すフローチャートである。 物体候補領域ソートの手順例を示すフローチャート（続き）である。 第２段階ソートの第１の変形例を示す図である。 第２段階ソートの第２の変形例を示す図である。 スコア付き位置データのＮＭＳ処理例を示す図である。 ＮＭＳ処理の逐次実行の手順例を示すフローチャートである。 ビットマップの例を示す図である。 重複判定のスキップ例を示す図である。 ビットマップの集計例を示す図である。 ＮＭＳ処理の並列実行の手順例を示すフローチャートである。 ＮＭＳ処理の並列実行の手順例を示すフローチャート（続き）である。 ソートとＮＭＳ処理の実行時間例を示すグラフである。 画像認識の実行時間例を示すグラフである。

以下、本実施の形態を図面を参照して説明する。
［第１の実施の形態］
第１の実施の形態を説明する。

図１は、第１の実施の形態の画像認識装置の例を説明する図である。
第１の実施の形態の画像認識装置１０は、画像を受け付け、受け付けた画像の中から物体が写った位置と物体の種類とを検出する。画像認識装置１０は、携帯情報端末や車載装置などのクライアント装置でもよいし、遠隔の撮像装置やクライアント装置や他のサーバ装置などとネットワークを介して通信するサーバ装置でもよい。分析対象の画像は、直前に撮像されたものでもよいし蓄積されたものでもよい。

画像認識装置１０は、演算処理装置１１および記憶部１２を有する。
演算処理装置１１は、演算部１１－１～１１－８を含む複数の演算部を有する。演算部１１－１～１１－８は、並列にスレッドを実行可能な演算コアである。好ましくは、演算処理装置１１は、数千個以上の多数のスレッドを並列に実行可能である。例えば、演算部１１－１～１１－８は、ＧＰＵに含まれる演算コアである。なお、パイプライン処理技術などにより１つの演算部が２以上の論理スレッドを実行することもある。

記憶部１２は、データ要素１３－１～１３－８を含む複数のデータ要素を記憶する。データ要素１３－１～１３－８は、レコードやエントリや単位データなどと言うこともできる。記憶部１２は、例えば、半導体メモリであり、ＧＰＵに含まれてもよい。データ要素１３－１～１３－８は、画像の中から抽出された候補領域に対応する。異なるデータ要素は異なる候補領域に対応している。候補領域は、検出すべき物体が写っている可能性がある画像領域である。例えば、画像の中から候補領域が抽出され、抽出された候補領域の評価値が画像の特徴情報に基づいて算出される。

データ要素１３－１～１３－８はそれぞれ、候補領域の位置および評価値を含む。位置は、画像の中の候補領域の場所を示す。候補領域が矩形である場合、例えば、位置は左上の頂点のＸ座標およびＹ座標と右下の頂点のＸ座標およびＹ座標とによって表現できる。また、例えば、位置は左上の頂点のＸ座標およびＹ座標と幅と高さとによって表現できる。評価値は、スコアや指標値と言うこともできる。例えば、評価値が大きいほど、候補領域の評価が高く、検出すべき物体が写っている可能性が高いことを示す。

データ要素１３－１～１３－８が生成された時点では、データ要素１３－１～１３－８は評価値の順にソートされていない。一方、１つの画像からは数千個以上の多数の候補領域が抽出される可能性があり、数千個以上の多数のデータ要素が記憶部１２に格納される可能性がある。そこで、演算処理装置１１は、後の画像認識処理において候補領域を絞り込むため、データ要素１３－１～１３－８を評価値の順にソート（整列）する。例えば、演算処理装置１１は、評価値の高い順（降順）にデータ要素をソートする。

データ要素１３－１～１３－８のソートにあたり、演算処理装置１１は、演算部１１－１～１１－８を用いて並列にインデックス１４－１～１４－８を算出する。インデックス１４－１～１４－８は、データ要素１３－１～１３－８のソート後の順位を示す。インデックス１４－１～１４－８を位置情報と言うこともできる。あるデータ要素のインデックスは、当該データ要素の評価値と少なくとも一部の他のデータ要素の評価値との比較に基づいて算出される。異なるデータ要素のインデックスを、異なる演算部のスレッドによって算出することも可能である。ただし、１つの演算部が数個の論理スレッドによって数個のインデックスを算出することもある。すなわち、演算部とデータ要素の関係は、１対１であってもよいし１対多であってもよい。

例えば、データ要素の集合の中で、データ要素１３－１は現在１番目である。データ要素１３－２は２番目であり、データ要素１３－３は３番目であり、データ要素１３－４は４番目であり、データ要素１３－５は５番目であり、データ要素１３－６は６番目であり、データ要素１３－７は７番目であり、データ要素１３－８は８番目である。

演算部１１－１は、データ要素１３－１の評価値と他のデータ要素の評価値との比較により、データ要素１３－１に対応するインデックス１４－１として「７」を算出する。インデックス１４－１の算出は、例えば、データ要素１３－１よりも評価値が高い他のデータ要素をカウントすることにより実現される。

演算部１１－２は、データ要素１３－２に対応するインデックス１４－２として「６」を算出する。演算部１１－３は、データ要素１３－３に対応するインデックス１４－３として「３」を算出する。演算部１１－４は、データ要素１３－４に対応するインデックス１４－４として「２」を算出する。演算部１１－５は、データ要素１３－５に対応するインデックス１４－５として「１」を算出する。演算部１１－６は、データ要素１３－６に対応するインデックス１４－６として「５」を算出する。演算部１１－７は、データ要素１３－７に対応するインデックス１４－７として「４」を算出する。演算部１１－８は、データ要素１３－８に対応するインデックス１４－８として「０」を算出する。なお、インデックス１４－１～１４－８は０から始まる整数である。

インデックス１４－１～１４－８の算出が終わるまで、データ要素１３－１～１３－８は実際には移動されない。インデックス１４－１～１４－８が算出された後、演算処理装置１１は、演算部１１－１～１１－８を用いて、インデックス１４－１～１４－８に基づいてデータ要素１３－１～１３－８を並列に移動させる。すなわち、ソート後の順位を算出するフェーズとデータ要素を移動するフェーズとが分離され、各フェーズ内では異なるデータ要素の処理が複数の演算部により並列に実行される。

その結果、ソート後のデータ要素の集合の中で、データ要素１３－８は１番目になる。データ要素１３－５は２番目になり、データ要素１３－４は３番目になり、データ要素１３－３は４番目になり、データ要素１３－７は５番目になり、データ要素１３－６は６番目になり、データ要素１３－５は７番目になり、データ要素１３－１は８番目になる。なお、データ要素１３－１～１３－８の移動は、ソート前のデータ要素１３－１～１３－８が記憶されていた記憶領域に一斉に上書きすることで行ってもよい。また、データ要素１３－１～１３－８の移動は、ソート前のデータ要素１３－１～１３－８とは異なる記憶領域に保存して元の記憶領域のデータ要素を削除することで行ってもよい。

データ要素１３－１～１３－８がソートされると、演算処理装置１１は、ソート後のデータ要素１３－１～１３－８の順序に基づいて、複数の候補領域の中から一部の候補領域を選択する。例えば、演算処理装置１１は、評価値が大きい方から所定数の候補領域を選択して、画像認識処理における次段の処理に渡す。次段の処理には、例えば、２つの候補領域の重なりが大きい場合に評価値が小さい方の候補領域を削除する重複除去が含まれる。画像認識装置１０は、最終的に少数の領域を選択して各領域に写った物体の種類を判定し、認識結果を出力する。例えば、画像認識装置１０は、領域を示す図形および物体の種類を示す文字列を元の画像にマッピングし、認識結果付き画像を表示させる。

第１の実施の形態の画像認識装置１０によれば、画像認識の過程において、画像から検出された候補領域の位置および評価値を示す複数のデータ要素に対して、ソート後の順位を示すインデックスが複数の演算部を用いて並列に算出される。インデックスが算出されると、算出されたインデックスに基づいてそれら複数のデータ要素が、複数の演算部を用いて一斉に移動される。そして、ソート後の複数のデータ要素の順序に基づいて、画像から検出された複数の候補領域のうちの一部の候補領域が選択される。

これにより、ＧＰＵなど多数のスレッドを並列実行可能な演算処理装置を活用して、候補領域を示すデータ要素のソートを実行することができる。よって、画像認識の中で比較的負荷の高いソート処理を高速化でき、画像認識を高速化することができる。

［第２の実施の形態］
次に、第２の実施の形態を説明する。
第２の実施の形態の画像認識装置１００は、ニューラルネットワークを用いて、入力画像の中から物体の位置および種類を判定する画像認識を行う。画像認識装置１００は、例えば、カメラ映像の中から車両や歩行者を検出する交通監視システムや都市監視システムなどに用いることが可能である。画像認識装置１００を情報処理装置やコンピュータと言うこともできる。画像認識装置１００は、クライアント装置でもサーバ装置でもよい。

図２は、画像認識装置のハードウェア例を示すブロック図である。
画像認識装置１００は、バスに接続されたＣＰＵ１０１、ＲＡＭ（Random Access Memory）１０２、ＨＤＤ（Hard Disk Drive）１０３、ＧＰＵ１０４、画像信号処理部１０５、入力信号処理部１０６、媒体リーダ１０７および通信インタフェース１０８を有する。画像認識装置１００は、第１の実施の形態の画像認識装置１０に対応する。

ＣＰＵ１０１は、プログラムの命令を実行するプロセッサである。ＣＰＵ１０１は、ＨＤＤ１０３に記憶されたプログラムやデータの少なくとも一部をＲＡＭ１０２にロードし、プログラムを実行する。ＲＡＭ１０２は、ＣＰＵ１０１が実行するプログラムやＣＰＵ１０１が演算に使用するデータを一時的に記憶する揮発性の半導体メモリである。ＣＰＵ１０１は、ＧＰＵ１０４を利用するプログラムに従って、ＲＡＭ１０２からＧＰＵ１０４に入力データを転送させ、ＧＰＵ１０４にデータ処理を実行させ、ＧＰＵ１０４からＲＡＭ１０２に結果データを転送させることがある。

ＨＤＤ１０３は、ＯＳ（Operating System）やミドルウェアやアプリケーションソフトウェアなどのソフトウェアのプログラム、および、データを記憶する不揮発性記憶装置である。なお、画像認識装置１００は、フラッシュメモリやＳＳＤ（Solid State Drive）など他の種類の記憶装置を備えてもよく、複数の記憶装置を備えてもよい。

画像信号処理部１０５は、ＣＰＵ１０１からの命令に従って、画像認識装置１００に接続されたディスプレイ１１１に画像を出力する。ディスプレイ１１１としては、ＣＲＴ（Cathode Ray Tube）ディスプレイ、液晶ディスプレイ（ＬＣＤ：Liquid Crystal Display）、有機ＥＬ（ＯＥＬ：Organic Electro-Luminescence）ディスプレイなど、任意の種類のディスプレイを使用することができる。

入力信号処理部１０６は、画像認識装置１００に接続された入力デバイス１１２から入力信号を受信する。入力デバイス１１２として、マウス、タッチパネル、タッチパッド、キーボードなど、任意の種類の入力デバイスを使用できる。また、画像認識装置１００に複数の種類の入力デバイスが接続されてもよい。

媒体リーダ１０７は、記録媒体１１３に記録されたプログラムやデータを読み取る読み取り装置である。記録媒体１１３として、例えば、フレキシブルディスク（ＦＤ：Flexible Disk）やＨＤＤなどの磁気ディスク、ＣＤ（Compact Disc）やＤＶＤ（Digital Versatile Disc）などの光ディスク、光磁気ディスク（ＭＯ：Magneto-Optical disk）、半導体メモリなどを使用できる。媒体リーダ１０７は、例えば、記録媒体１１３から読み取ったプログラムやデータをＲＡＭ１０２またはＨＤＤ１０３に格納する。

通信インタフェース１０８は、ネットワーク１１４に接続され、ネットワーク１１４を介して他の情報処理装置と通信を行うインタフェースである。通信インタフェース１０８は、スイッチやルータなどの有線通信装置に接続される有線通信インタフェースでもよいし、基地局やアクセスポイントに接続される無線通信インタフェースでもよい。

図３は、ＧＰＵのハードウェア例を示すブロック図である。
ＧＰＵ１０４は、グローバルメモリ１２３、スケジューラ１２４、および、複数のストリーミングマルチプロセッサ（ＳＭ：Streaming Multi-Processor）であるストリーミングマルチプロセッサ１２１－１，１２１－２，…，１２１－ｎを有する。

グローバルメモリ１２３は、ストリーミングマルチプロセッサ１２１－１，１２１－２，…，１２１－ｎによって共有される揮発性の半導体メモリである。ＣＰＵ１０１の命令に従い、ＲＡＭ１０２からグローバルメモリ１２３に入力データが転送され、グローバルメモリ１２３からＲＡＭ１０２に結果データが転送される。また、グローバルメモリ１２３からストリーミングマルチプロセッサ１２１－１，１２１－２，…，１２１－ｎにデータが読み込まれ、ストリーミングマルチプロセッサ１２１－１，１２１－２，…，１２１－ｎからグローバルメモリ１２３にデータが書き出される。

スケジューラ１２４は、ストリーミングマルチプロセッサ１２１－１，１２１－２，…，１２１－ｎによるスレッドの実行をスケジュールする。スケジューラ１２４は、グローバルメモリ１２３に記憶されたデータをブロックと呼ばれる単位に分割し、１つのブロックに１つのストリーミングマルチプロセッサを割り当てる。スケジューラ１２４は、ストリーミングマルチプロセッサ１２１－１，１２１－２，…，１２１－ｎに担当のブロックを読み込ませ、複数のスレッドにより担当のブロックを処理させる。

ストリーミングマルチプロセッサ１２１－１は、複数のスレッドを起動し、これら複数のスレッドを用いてブロック内のデータを並列に処理するマルチプロセッサである。ストリーミングマルチプロセッサは、複数のストリーミングプロセッサ（ＳＰ：Streaming Processor）および共有メモリ１２２－１を有する。ストリーミングマルチプロセッサ１２１－２，…，１２１－ｎも同様のハードウェアを有する。

ストリーミングプロセッサは、スレッドを実行するプロセッサコアである。ストリーミングマルチプロセッサ１２１－１のストリーミングプロセッサは、共有メモリ１２２－１からデータを読み出し、データを処理し、共有メモリ１２２－１にデータを書き込む。

第２の実施の形態では、ストリーミングマルチプロセッサ１２１－１，１２１－２，…，１２１－ｎはそれぞれ１０２４個のスレッドを並列に実行できるものとする。ただし、最大スレッド数は５１２や２０４８など他の数字であってもよい。各ストリーミングプロセッサはパイプライン処理を行うことから、ここで言うスレッド数は論理スレッド数であり、ストリーミングマルチプロセッサ１２１－１が有するストリーミングプロセッサの数は最大スレッド数である１０２４より少なくてよい。すなわち、１つのストリーミングプロセッサが２個以上の数個のスレッドを実行することがある。

共有メモリ１２２－１は、ストリーミングマルチプロセッサ１２１－１が有する複数のストリーミングプロセッサによって共有される揮発性の半導体メモリである。共有メモリ１２２－１は、ストリーミングマルチプロセッサ１２１－１のローカルメモリであり、グローバルメモリ１２３よりも記憶容量が少なくてよい。ストリーミングマルチプロセッサ１２１－１は、担当のブロックをグローバルメモリ１２３から共有メモリ１２２－１に読み込み、処理結果を共有メモリ１２２－１からグローバルメモリ１２３に書き出す。

次に、画像認識の流れについて説明する。
図４は、画像認識の流れの例を示す図である。
画像認識装置１００が使用する画像認識モデルは、畳み込みニューラルネットワーク層（ＣＮＮ層）３３、物体領域予測ネットワーク層（ＲＰＮ（Region Proposal Network）層）３５および高速Ｒ－ＣＮＮ層３７を含む。画像認識装置１００は、入力画像に対して前処理３１を行い、前処理後の入力画像３２をＣＮＮ層３３に入力する。画像認識装置１００は、ＣＮＮ層３３が出力する特徴マップ３４をＲＰＮ層３５に入力する。画像認識装置１００は、ＲＰＮ層３５が出力する物体候補領域３６と上記の特徴マップ３４を高速Ｒ－ＣＮＮ層３７に入力する。これにより認識結果３８が得られる。

前処理３１は、入力画像のサイズや輝度を調整して、ＣＮＮ層３３に入力可能な入力画像３２を生成する。例えば、前処理３１は、５００×３７５ピクセルの入力画像を８００×６００ピクセルに変換し、画像全体の平均輝度を引き下げる。前処理３１が出力する入力画像３２は、例えば、幅８００ピクセル×高さ６００ピクセルのサイズをもち、ＲＧＢ（Red Green Blue）３チャネルをもつカラー画像である。

ＣＮＮ層３３は、予め重みが学習された畳み込みニューラルネットワークを用いて、入力画像３２から特徴マップ３４を生成する。ＣＮＮ層３３は、１３個の畳み込み層と４個のプーリング層と３個の全結合層を含むディープニューラルネットワークをもつ。畳み込み層は、所定のフィルタを用いてエッジなどの特徴情報を抽出する。プーリング層は、画像の一辺の長さを半分にして画像サイズを縮小する。全結合層は、畳み込み層やプーリング層の出力を集約して特定の変数の値を算出する。特徴マップ３４は、例えば、幅５０ピクセル×高さ３８ピクセルのサイズをもち、５１２チャネルをもつ。

ＲＰＮ層３５は、特徴マップ３４を用いて、入力画像３２の中から検出すべき物体が存在する可能性のある画像領域である物体候補領域３６を検出する。ＲＰＮ層３５は、入力画像３２上で位置やサイズの異なる多数の矩形領域を物体候補領域として設定し、特徴マップ３４に基づいて各物体候補領域のスコアを算出する。スコアは評価値や信頼度と言うこともできる。スコアは物体候補領域に所望の物体が写っている確率を示し、所望の物体が写っている可能性が高いほどスコアが高くなる。ＲＰＮ層３５は、まず６０００個を超える多数の物体候補領域を抽出し、スコアが高い上位６０００個の物体候補領域を選択し、重複度が大きい物体候補領域を除去し、最終的に３００個の物体候補領域を出力する。

高速Ｒ－ＣＮＮ層３７は、特徴マップ３４および物体候補領域３６に基づいて、各物体候補領域に写っている物体の種類を判定し、判定結果の信頼度を示すスコアを算出する。高速Ｒ－ＣＮＮ層３７は、スコアが十分に高い少数の画像領域を選択する。高速Ｒ－ＣＮＮ層３７が出力する認識結果３８は、選択した画像領域の位置と、判定した物体の種類と、写っている物体が当該種類である可能性を示すスコアとを含む。

画像認識装置１００は、認識結果３８を元の入力画像にマッピングしてディスプレイ１１１に表示することも可能である。例えば、画像認識装置１００は、入力画像３２上での矩形領域を、前処理３１を行う前の元の入力画像上での矩形領域に変換し、矩形領域を囲む枠線と物体の種類およびスコアを示す文字列とを元の入力画像に重ねて表示する。

図５は、認識結果の例を示す図である。
画像４１は、ＲＰＮ層３５が出力する物体候補領域を示す枠線を、入力画像に重ねて表示したものである。ＲＰＮ層３５は１枚の入力画像に対して３００個の物体候補領域を出力するが、図５の例では理解を容易にするため少数の物体候補領域のみを表示している。画像４１には、検出対象となる物体として自動車、犬、馬および２人の人間が写っている。なお、図５の例では地面や森林などの背景を省略している。画像４１では、検出対象となる物体を正確に切り出す矩形領域である正解の物体候補領域に加えて、その周辺に位置やサイズの異なる複数の物体候補領域が抽出されている。ＲＰＮ層３５の中では、このような物体候補領域に加えて、スコアの小さい多数の物体候補領域も一時的に抽出される。

画像４２は、高速Ｒ－ＣＮＮ層３７が出力する認識結果３８を、入力画像に重ねて表示したものである。画像４２に表示された枠線は、画像４１に表示された物体候補領域の枠線のうちスコアが高い一部の物体候補領域の枠線である。各枠線の近くには、判定された物体の種類およびスコアを示す文字列が表示される。図５の例では、自動車、犬、馬および２人の人間が正しく検出されている。自動車のスコアは１．０００、犬のスコアは０．９５８、馬のスコアは０．９９９、手前に写っている人間のスコアは０．９９９、奥に写っている人間のスコアは０．９８８と算出されている。

次に、画像認識装置１００の機能について説明する。画像認識装置１００は、できる限りＧＰＵ１０４を活用して一連の画像認識処理を行う。
図６は、画像認識装置の機能例を示すブロック図である。

画像認識装置１００は、画像記憶部１３１、中間データ記憶部１３２、前処理部１３３、特徴マップ生成部１３４、物体候補領域生成部１３５、物体推定部１３６および認識結果表示部１３７を有する。画像記憶部１３１および中間データ記憶部１３２は、ＲＡＭ１０２またはＧＰＵ１０４のグローバルメモリ１２３を用いて実現される。前処理部１３３、特徴マップ生成部１３４、物体候補領域生成部１３５、物体推定部１３６および認識結果表示部１３７は、ＣＰＵ１０１またはＧＰＵ１０４のストリーミングマルチプロセッサ１２１－１，１２１－２，…，１２１－ｎが実行するプログラムを用いて実現される。

画像記憶部１３１は、入力画像を記憶する。入力画像は、画像認識装置１００に接続された撮像装置によって撮像されたものでもよい。また、入力画像は、ユーザによって画像認識装置１００に入力されたものでもよいし、ネットワーク１１４を介して画像認識装置１００が他の情報処理装置から受信したものでもよい。中間データ記憶部１３２は、画像認識の過程で使用する中間データを記憶する。後述するように、中間データには、物体候補領域の位置およびスコアを示すスコア付き位置データが含まれる。また、中間データには、重複度の大きい物体候補領域を検出するためのビットマップが含まれる。

前処理部１３３は、前述の前処理３１を実行する。前処理部１３３は、画像記憶部１３１に記憶された入力画像のサイズや輝度を補正する。特徴マップ生成部１３４は、前述のＣＮＮ層３３に対応する。特徴マップ生成部１３４は、前処理を行った入力画像を、予め学習しておいた畳み込みニューラルネットワークに入力し、特徴マップを生成する。

物体候補領域生成部１３５は、前述のＲＰＮ層３５に対応する。物体候補領域生成部１３５は、スコア算出部１３８および選択部１３９を有する。
スコア算出部１３８は、入力画像から複数の物体候補領域を抽出し、各物体候補領域のスコアを算出する。選択部１３９は、複数の物体候補領域に対応する複数の要素を有し、各要素は物体候補領域の位置およびスコアを含むスコア付き位置データを組み立てる。選択部１３９は、物体候補領域を絞り込む。選択部１３９は、スコア付き位置データの要素をスコアの高い順（降順）にソートし、スコアの高い方から６０００個の要素を選択する。選択部１３９は、ＮＭＳ（Non-Maximum Suppression）処理により、重なりが大きい２以上の物体候補領域のうちの１つを残して他を削除する。選択部１３９は、残った要素のうちスコアの高い方から３００個の要素を選択して出力する。

物体推定部１３６は、前述の高速Ｒ－ＣＮＮ層３７に対応する。物体推定部１３６は、物体候補領域生成部１３５が出力するスコア付き位置データと特徴マップ生成部１３４が出力する特徴マップとに基づいて、物体が写った矩形領域と物体の種類を判定し、判定の信頼度を示すスコアを算出する。物体推定部１３６は、スコアに基づいて矩形領域を絞り込み、矩形領域の位置と物体の種類とスコアを示す認識結果を出力する。認識結果表示部１３７は、物体推定部１３６が出力する認識結果をディスプレイ１１１に表示する。例えば、認識結果表示部１３７は、入力画像に認識結果をマッピングし、検出した領域を囲む枠線と物体の種類およびスコアを示す文字列とを入力画像に重ねて表示する。

図７は、画像認識の手順例を示すフローチャートである。
（Ｓ１０）前処理部１３３は、入力画像を前処理する。前処理には、入力画像の幅のピクセル数および高さのピクセル数を、畳み込みニューラルネットワークの仕様に合わせて変更することが含まれる。また、前処理には、入力画像の平均輝度が一定になるように、入力画像の各ピクセルの輝度を全体的にシフトさせる。

（Ｓ１１）特徴マップ生成部１３４は、ステップＳ１０で前処理した入力画像を畳み込みニューラルネットワークに入力し、入力画像の特徴を示す特徴マップを生成する。畳み込みニューラルネットワークの中の重みはサンプル画像を用いて予め学習されている。

（Ｓ１２）物体候補領域生成部１３５のスコア算出部１３８は、検出対象の物体が写っている可能性のある物体候補領域を入力画像の中から抽出する。スコア算出部１３８は、特徴マップを用いて、抽出した物体候補領域のスコアを算出する。例えば、スコア算出部１３８は、入力画像の中に１６ピクセル間隔で５０×３８個の基準点を配置し、基準点毎に当該基準点を中心としてサイズの異なる９個の矩形をアンカーとして配置し、合計で１７１００個のアンカーを得る。スコア算出部１３８は、特徴マップに基づいて、アンカーを微調整して物体候補領域とすると共に、各物体候補領域のスコアを算出する。

（Ｓ１３）物体候補領域生成部１３５の選択部１３９は、ステップＳ１２で抽出された物体候補領域を、スコアおよび相互の位置関係に基づいて３００個に絞り込んで選択する。物体候補領域選択の詳細は後述する。

（Ｓ１４）物体推定部１３６は、ステップＳ１１で生成された特徴マップとステップＳ１３で選択された物体候補領域から、物体の位置と種類を推定する。この際、推定の信頼度を示すスコアが算出される。物体の位置は、選択された物体候補領域の何れかである。

（Ｓ１５）認識結果表示部１３７は、物体の位置と種類とスコアを含む認識結果を表示する。例えば、認識結果表示部１３７は、物体の位置を示す枠線と物体の種類およびスコアを示す文字列を、元の入力画像に重ねてディスプレイ１１１に表示する。

図８は、物体候補領域選択の手順例を示すフローチャートである。
物体候補領域選択は、上記のステップＳ１３で実行される。
（Ｓ２０）選択部１３９は、スコア付き位置データを組み立てる。スコア付き位置データは、ステップＳ１２で抽出された複数の物体候補領域に対応する複数の要素を含み、各要素は物体候補領域の位置座標とスコアを含むデータ集合である。この時点では、スコア付き位置データの要素はまだソートされていない。

（Ｓ２１）選択部１３９は、入力画像の端周辺にある物体候補領域について入力画像の外側に出ている部分が存在する場合、その部分の領域をクリッピングする。すなわち、選択部１３９は、入力画像の外側に突出している部分を物体候補領域から削る。選択部１３９は、クリッピングに伴い位置座標を再計算してスコア付き位置データを更新する。

（Ｓ２２）選択部１３９は、小さ過ぎる辺をもつ物体候補領域を検索し、該当する物体候補領域を示す要素をスコア付き位置データから削除する。該当する物体候補領域は、長細い形状の矩形領域であり、幅または高さが閾値以下のものである。ただし、スコア付き位置データからの要素の削除は、要素が無効であることを示す所定の値をスコアに設定することによって行うことができる。所定の値として、例えば、ｆｌｏａｔ型の最小値を用いる。これにより、スコア付き位置データの要素がその都度移動することを抑制できる。ステップＳ２１，Ｓ２２の処理は、スコア付き位置データの要素毎に独立しているため、ＧＰＵ１０４を用いて、１つの要素に１つのスレッドを割り当てて並列化できる。

（Ｓ２３）選択部１３９は、スコア付き位置データに含まれる複数の要素をスコアの高い順（降順）にソートする。ソート処理の詳細は後述する。
（Ｓ２４）選択部１３９は、ソート後のスコア付き位置データから、６０００位より後の要素を削除する。上位６０００個の要素の選択は、６０００位より後の要素を無視するだけでよい。これにより、スコアの高い６０００個の物体候補領域が選択される。

（Ｓ２５）選択部１３９は、上位６０００個の物体候補領域に対してＮＭＳ処理を行う。ＮＭＳ処理は、ある物体候補領域に対して、当該物体候補領域と重複する部分領域の面積が大きく当該物体候補領域よりもスコアの小さい他の物体候補領域が存在する場合、当該他の物体候補領域を削除する処理である。このような他の物体候補領域は、物体が写った正しい矩形領域から若干ずれた矩形領域であることが多いため削除する。選択部１３９は、該当する物体候補領域を示す要素をスコア付き位置データから削除する。ただし、スコア付き位置データからの要素の削除は、要素が無効であることを示す所定の値をスコアに設定することによって行うことができる。ＮＭＳ処理の詳細は後述する。

（Ｓ２６）選択部１３９は、スコア付き位置データの中に無効化された要素が含まれている場合、すなわち、スコアの値が無効を示している要素が存在する場合、無効な要素の記憶領域を詰めていくパッキングを行う。これにより、有効な要素がスコア順に連続して記憶される。ある要素のパッキング後の位置は、現在位置と当該要素より前に存在する無効な要素の数とから算出できる。そこで、パッキングは、ＧＰＵ１０４を用いて、１つの要素に１つのスレッドを割り当てて並列化することができる。ＧＰＵ１０４の複数のスレッドが各要素のパッキング後の位置を示すインデックスを計算し、インデックスの計算が終わってから複数の要素を一斉に移動させる。そして、選択部１３９は、スコア付き位置データから３００位より後の要素を削除する。上位３００個の要素の選択は、３００位より後の要素を無視するだけでよい。これにより、３００個の物体候補領域が選択される。

次に、ステップＳ２３のソート処理の効率化について説明する。
図９は、スコア付き位置データのソート例を示す図である。
スコア付き位置データ１４１は、物体候補領域を示す要素の集合であり、中間データ記憶部１３２に記憶される。要素はレコードやエントリや単位データなどと言うこともできる。スコア付き位置データ１４１に含まれる各要素は、スコア、最小Ｘ座標、最小Ｙ座標、最大Ｘ座標および最大Ｙ座標を含む。最小Ｘ座標は、矩形の物体候補領域の左上の頂点のＸ座標である。最小Ｙ座標は、左上の頂点のＹ座標である。最大Ｘ座標は、右下の頂点のＸ座標である。最大Ｙ座標は、右下の頂点のＹ座標である。ただし、要素は物体候補領域の位置を特定できればよく、最小Ｘ座標、最小Ｙ座標、最大Ｘ座標および最大Ｙ座標に代えて、最小Ｘ座標、最小Ｙ座標、幅および高さなどを用いてもよい。

物体候補領域生成部１３５の選択部１３９は、スコア付き位置データ１４１の要素をスコアの高い順にソートする。図９の例において、ソート前のスコア付き位置データ１４１では、スコアが０．９の要素、０．０１の要素、０．０２の要素、０．７の要素のように複数の要素がスコアと無関係な順序で並んでいる。これに対して、ソート後のスコア付き位置データ１４１では、スコアが０．９の要素、０．７の要素、０．０２の要素、０．０１の要素のように複数の要素がスコアの高い順に並んでいる。

選択部１３９は、ＧＰＵ１０４が並列に実行する多数のスレッドを利用してスコア付き位置データの要素をソートする。ソートアルゴリズムは第１段階と第２段階を含む。
図１０は、第１段階ソートの例を示す図である。

選択部１３９は、スコア付き位置データの要素集合をブロックに分割する。１つのブロックは、１つのストリーミングマルチプロセッサが並列実行可能なスレッドの数に相当する個数の要素を含む。よって、１つの要素に１つのスレッドを割り当てることになる。第２の実施の形態のＧＰＵ１０４の場合、１つのブロックは１０２４個の要素を含む。スコア付き位置データの要素数が１０２４で割り切れない場合、選択部１３９は、スコアが０のダミー要素を追加することで各ブロックの要素数を１０２４に揃える。要素数をｎ、ブロック数をＮとすると、Ｎ＝（（ｎ－１）／１０２４）＋１である。

第１段階では、各ストリーミングマルチプロセッサがブロック内で１０２４個の要素をソートする。ここでは、あるストリーミングマルチプロセッサを用いてブロック１４２をソートすることを考える。第１段階では、選択部１３９は、ブロック１４２を最小のグループに分割してグループ内で要素をソートし、ソート済みの隣接する２つのグループを連結する（マージする）ことをグループの要素数が１０２４になるまで繰り返す。

第２の実施の形態では、最小のグループの要素数を８とする。最小のグループの要素数が少ないほど最初のステップの計算量が少なくなる一方、２つのグループを連結していくステップ数が増える。最小のグループの要素数が多いほど最初のステップの計算量が多くなる一方、２つのグループを連結していくステップ数が減る。本出願の発明者は、ブロックサイズが１０２４のもとで、最小のグループの要素数を８とするのが最適と判断した。

そこで、選択部１３９は、ブロック１４２を１２８個のグループに分割する。１つのグループに属する要素は、ブロック１４２の中で連続している８個の要素である。選択部１３９は、ブロック１４２の先頭から順に８個ずつ要素を選択していけばよい。また、選択部１３９は、同一のストリーミングマルチプロセッサで並列実行される１０２４個のスレッドを、ブロック１４２に含まれる１０２４個の要素に１対１に割り当てる。選択部１３９は、１０２４個のスレッドを用いて並列に、１２８個のグループそれぞれの中で８個の要素をスコアの高い順にソートする。グループ内ソートの詳細は後述する。

８要素グループのソートが終わると、選択部１３９は、隣接する２つの８要素グループを連結して６４個の１６要素グループを形成する。形成される１６要素グループは、１６個の要素がスコアの高い順にソートされたものである。１２８個の８要素グループの連結は、グループ内ソートと同様に、上記の１０２４個のスレッドを用いて並列に行われる。２つのソート済みグループを連結するグループ間ソートの詳細は後述する。

１６要素グループが形成されると、選択部１３９は、隣接する２つの１６要素グループを連結して３２個の３２要素グループを形成する。形成される３２要素グループは、３２個の要素がスコアの高い順にソートされたものである。６４個の１６要素グループの連結は、上記の１０２４個のスレッドを用いて並列に行われる。選択部１３９は、上記を繰り返してソート済みの１０２４要素グループを形成する。これにより、１つのストリーミングマルチプロセッサにおいてブロック１４２がソートされる。

図１１は、第２段階ソートの例を示す図である。
第２段階では、１つのストリーミングマルチプロセッサが、ソート済みのＮ個のブロックを連結して、１０２４要素×６ブロック＝６１４４個のソート済みの要素列を形成する。ソート処理の後段で選択部１３９は上位６０００個の要素を選択することから、要素数ｎに関係なくスコアが高い６ブロック分の要素を抽出できればよい。ここでは、あるストリーミングマルチプロセッサを用いて、ソート済みのブロック１４２－１～１４２－７を連結して上位６１４４個のソート済み要素列を形成することを考える。

第２段階では、選択部１３９は、バブルソート方式によりスコアが高い要素から順に確定していく。選択部１３９は、２つのブロックを連結してソート済みの２０４８個の要素を形成する。選択部１３９は、２０４８個の要素のうちの上位１０２４個の要素を切り出し、他のブロックと連結してソート済みの２０４８個の要素を形成する。これを未処理のブロックがなくなるまで繰り返すことで、スコアの最も高い１０２４個の要素が抽出される。残りの要素群に対してもこれを繰り返すことで、スコアの高い順に１０２４要素ずつ確定していき、６回の繰り返しにより６１４４個のソート済みの要素列が完成する。

１つのストリーミングマルチプロセッサは１０２４個のスレッドを並列実行することができる。そこで、２つのブロックを連結するときは、選択部１３９は、一方のブロックに含まれる１０２４個の要素に１０２４個のスレッドを１対１に割り当て、これとは別に他方のブロックに含まれる１０２４個の要素に１０２４個のスレッドを１対１に割り当てる。そして、１０２４個のスレッドを２セット実行させる。

例えば、選択部１３９は、ブロック１４２－６，１４２－７を連結してソート済みの２０４８個の要素を形成する。選択部１３９は、この２０４８個の要素のうち下位１０２４個の要素を後に使用するブロックとして退避しておき、上位１０２４個の要素を抽出する。選択部１３９は、抽出した上位１０２４個の要素とブロック１４２－５とを連結してソート済みの２０４８個の要素を形成する。選択部１３９は、この２０４８個の要素のうち下位１０２４個の要素を後に使用するブロックとして退避しておき、上位１０２４個の要素を抽出する。以降、ブロック１４２－４、ブロック１４２－３、ブロック１４２－２と順に連結していき、ブロック１４２－１を連結して形成された２０４８個の要素のうち上位１０２４個の要素が、最もスコアの高い上位１０２４個の要素となる。

よって、選択部１３９は、ブロック１４２－１～１４２－７の７個のブロックに対して、２つのブロックを連結することを６回繰り返すことで上位１０２４要素を確定する。選択部１３９は、退避しておいた６個のブロックに対して同様の処理を行い、２つのブロックを連結することを５回繰り返すことで次の１０２４要素を確定する。このようにして、選択部１３９は、スコアが高い６ブロック分の要素を確定させる。

図１２は、グループ内のソート例を示す図である。
グループ内ソートは、第１段階ソートにおいて同一グループ内の８個の要素をソートするときに行われる。ここでは、要素１４３－１～１４３－８の８個の要素が順に並んでいるとする。要素１４３－１～１４３－８に対して８個のスレッドが１対１に割り当てられる。各スレッドは要素１４３－１～１４３－８の全てを参照することができる。グループ内ソートは、インデックス計算と要素移動の２段階を含む。インデックス計算も要素移動も要素間で独立に実行できるため、並列化することができる。

インデックス計算では、各スレッドは、担当の要素のスコアと他の要素のスコアとを１つずつ比較していき、担当の要素よりもスコアの大きい他の要素をカウントする。ただし、担当の要素とスコアが同じ他の要素が存在する場合、担当の要素より前方に存在するものについてはカウントに含め、担当の要素より後方に存在するものについてはカウントに含めないようにする。これにより、スコアが同じ要素の間で順位の整合性を図る。担当の要素よりもスコアの大きい他の要素の数が、ソート後のインデックスになる。インデックスは、担当の要素の順位を示しており、０から始まる整数である。

例えば、要素１４３－２のスレッドは、要素１４３－３～１４３－８のスコアが要素１４３－２より大きいと判定し、インデックスを６と算出する。要素１４３－３のスレッドは、要素１４３－４，１４３－５，１４３－８のスコアが要素１４３－３より大きいと判定し、インデックスを３と算出する。なお、要素１４３－７のスコアは要素１４３－３と同じであるが、要素１４３－３の後方にあるためカウントに含めない。要素１４３－７のスレッドは、要素１４３－４，１４３－５，１４３－８のスコアが要素１４３－７より大きく、前方に存在する要素１４３－３のスコアが要素１４３－７と同じであると判定し、インデックスを４と算出する。これにより、要素１４３－１～１４３－８のインデックスが７，６，３，２，１，５，４，０と算出される。

全てのスレッドのインデックス計算が終了すると要素移動に遷移する。要素移動では、各スレッドは、先に計算したインデックスが示す記憶領域に担当の要素を一斉に移動させる。異なるスレッドが同じ記憶領域に書き込むことはないため、あるスレッドが他のスレッドの要素移動を待ち合わせなくてよい。例えば、要素１４３－２のスレッドは、インデックスが６であるため、要素１４３－７が記憶されていた７番目の記憶領域に要素１４３－２を上書きする。また、要素１４３－３のスレッドは、インデックスが３であるため、要素１４３－４が記憶されていた４番目の記憶領域に要素１４３－３を上書きする。これにより、要素１４３－８，１４３－５，１４３－４，１４３－３，１４３－７，１４３－６，１４３－２，１４３－１のようにスコアの大きい順にソートされる。

なお、要素移動では、ソート前の要素１４３－１～１４３－８が記憶されていた記憶領域にソート後の要素１４３－１～１４３－８を上書きする代わりに、他の記憶領域にソート後の要素１４３－１～１４３－８を格納するようにしてもよい。

図１３は、グループ間のソート例を示す図である。
グループ間ソートは、第１段階ソートにおいてソート済みグループを連結するときや、第２段階ソートにおいてソート済みブロックを連結するときに行われる。ここでは、ソートされた要素１４４－１～１４４－８の８要素グループと、ソートされた要素１４５－１～１４５－８の８要素グループとを連結することを考える。要素１４４－１～１４４－８，１４５－１～１４５－８に対して１６個のスレッドが１対１に割り当てられる。各スレッドは要素１４４－１～１４４－８，１４５－１～１４５－８の全てを参照することができる。グループ間ソートも、インデックス計算と要素移動の２段階を含む。インデックス計算も要素移動も要素間で独立に実行できるため、並列化することができる。

インデックス計算では、各スレッドは、担当の要素が属する要素集合（自データセット）での現在のインデックス（自インデックス）を確認する。自インデックスは、自データセットにおける担当の要素の順位を示す。また、各スレッドは、自データセットと連結する他の要素集合（他データセット）のうち担当の要素よりスコアが大きい要素の数（他インデックス）を算出する。他インデックスは、仮に担当の要素を他データセットに挿入する場合の挿入位置を示している。他データセットはソート済みであるため、他データセットの全要素と比較しなくてよく、二分探索により他インデックスを算出できる。

二分探索では、担当の要素のスコアと他データセットの中央の要素のスコアとを比較する。前者の方が大きい場合、担当の要素のスコアと前半区間の中央の要素のスコアとを比較し、後者の方が大きい場合、担当の要素のスコアと後半区間の中央の要素のスコアとを比較する。これを繰り返すことで担当の要素の挿入位置を判定できる。なお、担当の要素とスコアが同じ要素が存在する場合、２つのデータセットのうち特定の一方のデータセットに存在するものについてはカウントに含め、他方のデータセットに存在するものについてはカウントに含めないようにする。これにより、スコアが同じ要素の間で順位の整合性を図る。例えば、要素１４４－１～１４４－８側についてはカウントに含め、要素１４５－１～１４５－８側についてはカウントに含めないようにする。

各スレッドは、自インデックスと他インデックスの合計を、連結ソート後の担当の要素の位置を示すインデックスとする。インデックスは、連結する２つのデータセットの中で担当の要素よりスコアの大きい要素の数を示しており、０から始まる整数である。例えば、要素１４４－２の自インデックスが１であり、他インデックスが１と算出されたとする。すると、要素１４４－２のインデックスは２になり、連結ソート後の要素１４４－２の順位が３位と判定される。また、要素１４５－２の自インデックスが１であり、他インデックスが２と算出されたとする。すると、要素１４５－２のインデックスは３になり、連結ソート後の要素１４５－２の順位が４位と判定される。

全てのスレッドのインデックス計算が終了すると要素移動に遷移する。要素移動では、各スレッドは、先に計算したインデックスが示す記憶領域に担当の要素を一斉に移動させる。異なるスレッドが同じ記憶領域に書き込むことはないため、あるスレッドが他のスレッドの要素移動を待ち合わせなくてよい。例えば、要素１４４－２のスレッドは、インデックスが２であるため、要素１４４－３が記憶されていた３番目の記憶領域に要素１４４－２を上書きする。また、要素１４５－２のスレッドは、インデックスが３であるため、要素１４４－４が記憶されていた４番目の記憶領域に要素１４５－２を上書きする。これにより、要素１４４－１～１４４－８，１４５－１～１４５－８がソートされる。

なお、要素移動では、ソート前の要素１４４－１～１４４－８，１４５－１～１４５－８が記憶されていた記憶領域にソート後の要素を上書きする代わりに、他の記憶領域にソート後の要素を格納するようにしてもよい。

図１４は、第１段階ソートのスレッド実行例を示す図である。
ここでは、ストリーミングマルチプロセッサ１２１－１がスレッド１６１－１～１６１－１０２４の１０２４個のスレッドを実行して、同じブロックに属する要素＃１～＃１０２４の１０２４個の要素をソートすることを考える。

まず、スレッド１６１－１～１６１－１０２４は８要素グループの中でのグループ内ソートを行う。スレッド１６１－１～１６１－１０２４も実質的に８個ずつにグループ化されることになる。スレッド１６１－１は、要素＃１～＃８の中で要素＃１のインデックスを算出して移動する。スレッド１６１－２は、要素＃１～＃８の中で要素＃２のインデックスを算出して移動する。スレッド１６１－３は、要素＃１～＃８の中で要素＃３のインデックスを算出して移動する。スレッド１６１－１０２４は、要素＃１０１７～＃１０２４の中で要素＃１０２４のインデックスを算出して移動する。

次に、スレッド１６１－１～１６１－１０２４は隣接する８要素グループの間でグループ間ソートを行う。スレッド１６１－１～１６１－１０２４も実質的に１６個ずつにグループ化されることになる。スレッド１６１－１は、要素＃１～＃１６の中で要素＃１のインデックスを算出して移動する。スレッド１６１－２は、要素＃１～＃１６の中で要素＃２のインデックスを算出して移動する。スレッド１６１－３は、要素＃１～＃１６の中で要素＃３のインデックスを算出して移動する。スレッド１６１－１０２４は、要素＃１００９～＃１０２４の中で要素＃１０２４のインデックスを算出して移動する。

次に、スレッド１６１－１～１６１－１０２４は隣接する１６要素グループの間でグループ間ソートを行う。スレッド１６１－１～１６１－１０２４も実質的に３２個ずつにグループ化されることになる。スレッド１６１－１は、要素＃１～＃３２の中で要素＃１のインデックスを算出して移動する。スレッド１６１－２は、要素＃１～＃３２の中で要素＃２のインデックスを算出して移動する。スレッド１６１－３は、要素＃１～＃３２の中で要素＃３のインデックスを算出して移動する。スレッド１６１－１０２４は、要素＃９９３～＃１０２４の中で要素＃１０２４のインデックスを算出して移動する。

以下同様にして、スレッド１６１－１～１６１－１０２４は隣接する３２要素グループの間でグループ間ソートを行う。スレッド１６１－１は、要素＃１～＃６４の中で要素＃１のインデックスを算出して移動する。次に、スレッド１６１－１～１６１－１０２４は隣接する６４要素グループの間でグループ間ソートを行う。スレッド１６１－１は、要素＃１～＃１２８の中で要素＃１のインデックスを算出して移動する。次に、スレッド１６１－１～１６１－１０２４は隣接する１２８要素グループの間でグループ間ソートを行う。スレッド１６１－１は、要素＃１～＃２５６の中で要素＃１のインデックスを算出して移動する。次に、スレッド１６１－１～１６１－１０２４は隣接する２５６要素グループの間でグループ間ソートを行う。スレッド１６１－１は、要素＃１～＃５１２の中で要素＃１のインデックスを算出して移動する。最後に、スレッド１６１－１～１６１－１０２４は２つの５１２要素グループの間でグループ間ソートを行う。スレッド１６１－１は、要素＃１～＃１０２４の中で要素＃１のインデックスを算出して移動する。

図１５は、第２段階ソートのスレッド実行例を示す図である。
ここでは、ストリーミングマルチプロセッサ１２１－１がスレッド１６１－１～１６１－１０２４の１０２４個のスレッドを実行して、バブルソート方式により２つのブロックの連結と上位ブロックの抽出とを繰り返すことを考える。

ストリーミングマルチプロセッサ１２１－１は、１つのブロックを要素＃１～＃１０２４として読み込み、他の１つのブロックを要素＃１０２５～＃２０４８として読み込む。
スレッド１６１－１は、要素＃１～＃２０４８の中で要素＃１のインデックスを算出する。スレッド１６１－２は要素＃２のインデックスを算出し、スレッド１６１－３は要素＃３のインデックスを算出し、スレッド１６１－１０２４は要素＃１０２４のインデックスを算出する。また、スレッド１６１－１は、要素＃１～＃２０４８の中で要素＃１０２５のインデックスを算出する。スレッド１６１－２は要素＃１０２６のインデックスを算出し、スレッド１６１－３は要素＃１０２７のインデックスを算出し、スレッド１６１－１０２４は要素＃２０４８のインデックスを算出する。

そして、スレッド１６１－１～１６１－１０２４は、要素＃１～＃２０４８を一斉に移動する。これにより要素＃１～＃２０４８がソートされる。ストリーミングマルチプロセッサ１２１－１は、ソート後の上位１０２４個の要素を新たな要素＃１～＃１０２４として保持する。また、ストリーミングマルチプロセッサ１２１－１は、ソート後の下位１０２４個の要素をグローバルメモリ１２３に書き出す。下位１０２４個の要素は、要素＃１～＃１０２４として読み込んだブロックに上書きされる。ストリーミングマルチプロセッサ１２１－１は、他の１つのブロックを要素＃１０２５～＃２０４８として読み込む。

同様にして、スレッド１６１－１～１６１－１０２４は、要素＃１～＃２０４８の中で要素＃１～＃１０２４のインデックスを算出し、要素＃１０２５～＃２０４８のインデックスを算出し、要素＃１～＃２０４８を一斉に移動する。ストリーミングマルチプロセッサ１２１－１は、ソート後の上位１０２４個の要素を新たな要素＃１～＃１０２４として保持し、下位１０２４個の要素をグローバルメモリ１２３に書き出す。これを繰り返すことで、Ｎ個のブロックの中から上位１０２４個の要素を抽出できる。

ここで、第２段階ソートにおける共有メモリ１２２－１の使用方法について説明する。
図１６は、ＧＰＵにおけるメモリ使用例を示す図である。
ここでは説明を簡単にするため、３個のブロックに対して第２段階ソートを行うことを考える。ストリーミングマルチプロセッサ１２１－１が有する共有メモリ１２２－１には、区画１４６－１（区画Ａ）と区画１４６－２（区画Ｂ）が確保される。グローバルメモリ１２３には、３個のブロックを記憶する区画１４７－１～１４７－３が確保される。

まず、ストリーミングマルチプロセッサ１２１－１は、区画１４７－２に記憶されたブロックを区画１４６－１に読み込み、区画１４７－３に記憶されたブロックを区画１４６－２に読み込む。ストリーミングマルチプロセッサ１２１－１は、区画１４６－１，１４６－２に記憶された２０４８個の要素に対して連結ソートを行う。すると、区画１４６－１には上位１０２４個の要素がブロックとして格納され、区画１４６－２には下位１０２４個の要素がブロックとして格納される。ストリーミングマルチプロセッサ１２１－１は、区画１４６－２のブロックを区画１４７－３に上書き保存する。

次に、ストリーミングマルチプロセッサ１２１－１は、区画１４７－１に記憶されたブロックを区画１４６－２に読み込む。ストリーミングマルチプロセッサ１２１－１は、区画１４６－１，１４６－２に記憶された２０４８個の要素に対して連結ソートを行う。すると、区画１４６－１には上位１０２４個の要素がブロックとして格納され、区画１４６－２には下位１０２４個の要素がブロックとして格納される。

図１７は、ＧＰＵにおけるメモリ使用例を示す図（続き）である。
ストリーミングマルチプロセッサ１２１－１は、区画１４６－２のブロックを区画１４７－２に上書き保存する。また、区画１４６－１に記憶されたブロックは最終的なソート結果の先頭ブロックとして確定するため、ストリーミングマルチプロセッサ１２１－１は、区画１４６－１のブロックを区画１４７－１に上書き保存する。

次に、ストリーミングマルチプロセッサ１２１－１は、区画１４７－３に記憶されたブロックを区画１４６－１に読み込む。区画１４６－２には区画１４７－２に記憶されたブロックを読み込むことになるが、ここでは既に読み込まれた状態になっているため省略することができる。ストリーミングマルチプロセッサ１２１－１は、区画１４６－１，１４６－２に記憶された２０４８個の要素に対して連結ソートを行う。すると、区画１４６－１には上位１０２４個の要素がブロックとして格納され、区画１４６－２には下位１０２４個の要素がブロックとして格納される。

ストリーミングマルチプロセッサ１２１－１は、区画１４６－２のブロックを区画１４７－３に上書き保存する。また、区画１４６－１に記憶されたブロックは最終的なソート結果の２番目のブロックとして確定するため、ストリーミングマルチプロセッサ１２１－１は、区画１４６－１のブロックを区画１４７－２に上書き保存する。これにより３つのブロックのソートが完了し、区画１４７－１～１４７－３にソート結果が格納される。

このように、１つのストリーミングマルチプロセッサを用いて第２段階ソートを行うことで、転がし方式により、２つのブロックを連結する連結ソート毎に１回のブロック読み込みと１回のブロック書き出しを行えばよい。よって、共有メモリ１２２－１とグローバルメモリ１２３の間のブロック転送を削減することができる。

次に、第２の実施の形態で使用するソートアルゴリズムの性質について説明する。
グループ内ソートにおいて、ｋ個の要素を含むグループをソートする場合、スコア同士を比較する比較回数はｋ^２である。グループ間ソートにおいて、ｋ個の要素を含むデータセットをｋ個の要素を含む他のデータセットと連結する場合、当該データセットについてスコア同士を比較する比較回数はｋ×（ｌｏｇ（ｋ）＋１）である。ただし、ｋ個の要素の処理は並列化されるため、グループ内ソートの比較回数は実質的にｋであり、グループ間ソートの比較回数は実質的にｌｏｇ（ｋ）＋１である。

また、グループ内ソートでもグループ間ソートでも、インデックス計算後に一斉に要素移動が行われるため、スレッド間の同期待ちが少ない。グループ内ソートでの要素の移動回数はｋであるが、スレッドの同期待ちは１回となる。また、グループ間ソートでも要素の移動回数はｋであるが、スレッドの同期待ちは１回となる。

他のソートアルゴリズムとして選択ソートがある。選択ソートは、未ソートの要素の中から最もスコアの大きいものを１つずつ選択していくものである。選択ソートを改良したものとしてヒープソートや図書館ソートもある。選択ソートの比較回数はｋ×（ｋ－１）／２であり、最悪計算時間はＯ（ｋ^２）である。選択ソートは並列化が難しい。

また、他のソートアルゴリズムとして挿入ソートがある。挿入ソートは、要素を前方から１つずつ選択していき、選択した要素を、当該要素より前方の範囲のうちスコアに応じた位置に挿入するものである。挿入ソートを改良したものとしてシェルソートもある。挿入ソートの比較回数はｋ×（ｋ－１）／２であり、最悪計算時間はＯ（ｋ^２）である。挿入ソートは、ソート済みの前方の範囲を参照するため並列化が難しい。

また、他のソートアルゴリズムとしてクイックソートがある。クイックソートは、未ソートの要素の中からランダムに１つをピボットとして選択し、ピボットよりスコアが大きい要素を前方に移動し、それ以外の要素を後方に移動する。ピボットを基準とした範囲分割を階層的に行うことでソートを実現するものである。クイックソートの平均計算時間はＯ（ｋ×ｌｏｇ（ｋ））であり、最悪計算時間はＯ（ｋ^２）である。クイックソートは、移動先のインデックスの計算を要素間で並列化することが難しい。

また、他のソートアルゴリズムとしてマージソートがある。マージソートは、ソート対象の要素を小領域に分割し、隣接する２つのソート済みの小領域を段階的にマージするものである。ソート済みの２つの小領域をマージする際には、２つの小領域の先頭要素のスコアを比較し、スコアの大きい要素を１つずつ抽出していく。マージソートの最悪計算量はＯ（ｋ×ｌｏｇ（ｋ））である。マージソートは、先頭要素のスコアの比較と移動を繰り返すものであるため並列化が難しい。

また、他のソートアルゴリズムとして奇遇転置ソートがある。奇遇転置ソートは、奇数番目の要素とその次の要素とを比較してスコアの大きい方が前方になるように要素を入れ替え、偶数番目の要素とその次の要素とを比較してスコアの大きい方が前方になるように要素を入れ替えることを繰り返すものである。奇遇転置ソートはバブルソートを改良したものである。奇遇転置ソートの最悪計算時間はＯ（ｋ^２）である。奇遇転置ソートは、要素の入れ替え回数が多く同期待ちの頻度が高くなる。

また、他のソートアルゴリズムとしてバイトニックソートがある。バイトニックソートは、所定のソーティングネットワークに従って、特定の位置にある２つの要素を比較してスコアの大きい方が前方になるように要素を入れ替えることを繰り返すものである。バイトニックソートの計算時間はＯ（ｋ×ｌｏｇ（ｋ））である。バイトニックソートは、要素の入れ替え回数が多く同期待ちの頻度が高くなる。

次に、物体候補領域ソートの処理手順を説明する。
図１８は、物体候補領域ソートの手順例を示すフローチャートである。
物体候補領域ソートは、前述のステップＳ２３で実行される。

（Ｓ３０）選択部１３９は、ｎ個の要素を含むスコア付き位置データを、ＧＰＵ１０４のグローバルメモリ１２３にロードする。ｎが１０２４で割り切れない場合は、スコアが０のダミー要素をスコア付き位置データに含めておく。

（Ｓ３１）選択部１３９は、スコア付き位置データをそれぞれ１０２４個の要素を含むＮ個のブロックに分割する。選択部１３９は、Ｎ個のストリーミングマルチプロセッサを選択し、異なるブロックを異なるストリーミングマルチプロセッサにロードする。

（Ｓ３２）選択部１３９は、各ストリーミングマルチプロセッサ内で１０２４個の要素を８要素グループに分割する。選択部１３９は、異なる要素に異なるスレッドを割り当て、８要素グループ内のソート後のインデックスを並列に算出する。Ｎ個のストリーミングマルチプロセッサにより１０２４×Ｎ個のスレッドが並列に実行され、ダミー要素を含む１０２４×Ｎ個の要素のインデックスが並列に算出される。

（Ｓ３３）選択部１３９は、各ストリーミングマルチプロセッサにおいて、ステップＳ３２で算出したインデックスに基づいて８要素グループ内で要素を並列に移動する。Ｎ個のストリーミングマルチプロセッサにより１０２４×Ｎ個のスレッドが並列に実行され、ダミー要素を含む１０２４×Ｎ個の要素が並列に移動される。

（Ｓ３４）選択部１３９は、各ストリーミングマルチプロセッサにおいて、隣接する２つのグループの連結ソート後のインデックスを並列に算出する。Ｎ個のストリーミングマルチプロセッサにより１０２４×Ｎ個のスレッドが並列に実行され、ダミー要素を含む１０２４×Ｎ個の要素のインデックスが並列に算出される。

（Ｓ３５）選択部１３９は、各ストリーミングマルチプロセッサにおいて、ステップＳ３４で算出したインデックスに基づいて隣接２グループの中で要素を並列に移動する。Ｎ個のストリーミングマルチプロセッサにより１０２４×Ｎ個のスレッドが並列に実行され、ダミー要素を含む１０２４×Ｎ個の要素が並列に移動される。

（Ｓ３６）選択部１３９は、連結後のグループの要素数が１０２４に達したか、すなわち、ブロック内のソートが完了したか判断する。要素数が１０２４に達した場合はステップＳ３７に処理が進み、１０２４に達していない場合はステップＳ３４に進む。

（Ｓ３７）選択部１３９は、Ｎ個のストリーミングマルチプロセッサからグローバルメモリ１２３にソート後のブロックを書き出す。
図１９は、物体候補領域ソートの手順例を示すフローチャート（続き）である。

（Ｓ３８）選択部１３９は、ＧＰＵ１０４の１つのストリーミングマルチプロセッサを選択する。ここでは、ストリーミングマルチプロセッサ１２１－１を選択したとする。選択部１３９は、変数ｊの値をｊ＝１に初期化する。

（Ｓ３９）選択部１３９は、変数ｉの値をｉ＝Ｎに初期化する。
（Ｓ４０）選択部１３９は、グローバルメモリ１２３からストリーミングマルチプロセッサ１２１－１にブロックｉをロードする。ブロックｉは、連続するＮ個の記憶領域のうち先頭からｉ番目の記憶領域に記憶されたブロックである。

（Ｓ４１）選択部１３９は、変数ｉの値をｉ＝ｉ－１に更新する。
（Ｓ４２）選択部１３９は、グローバルメモリ１２３からストリーミングマルチプロセッサ１２１－１にブロックｉをロードする。

（Ｓ４３）選択部１３９は、ストリーミングマルチプロセッサ１２１－１にロードされたブロックｉ，ｉ＋１の連結ソート後のインデックスを並列に算出する。ストリーミングマルチプロセッサ１２１－１により１０２４個のスレッドが並列に実行され、１０２４×２個の要素のインデックスが１０２４個ずつ２セットで算出される。

（Ｓ４４）選択部１３９は、ストリーミングマルチプロセッサ１２１－１において、ステップＳ４３で算出したインデックスに基づいて２ブロック内で要素を並列に移動する。
（Ｓ４５）選択部１３９は、ソートした２０４８個の要素のうち下位１０２４個の要素を抽出し、ストリーミングマルチプロセッサ１２１－１からグローバルメモリ１２３にブロックｉ＋１として書き出す。例えば、抽出した下位１０２４個の要素が、連続するＮ個の記憶領域のうち先頭からｉ＋１番目の記憶領域に上書きされる。また、選択部１３９は、ソートした２０４８個の要素のうち上位１０２４個の要素を、ブロックｉとしてストリーミングマルチプロセッサ１２１－１に保持させる。

（Ｓ４６）選択部１３９は、変数ｉの値と変数ｊの値を比較しｉ＝ｊであるか判断する。ｉ＝ｊの場合はステップＳ４７に進み、ｉ≠ｊの場合はステップＳ４１に進む。
（Ｓ４７）選択部１３９は、ストリーミングマルチプロセッサ１２１－１が保持しているブロックｉをグローバルメモリ１２３に書き出す。例えば、１０２４個の要素が、連続するＮ個の記憶領域のうち先頭からｉ番目の記憶領域に上書きされる。

（Ｓ４８）選択部１３９は、ソート済みのブロックの合計要素数が６０００を超えたか、すなわち、１０２４×ｊ＞６０００を満たすか判断する。条件を満たす場合は物体候補領域ソートが終了し、条件を満たさない場合はステップＳ４９に進む。

（Ｓ４９）選択部１３９は、変数ｊの値をｊ＝ｊ＋１に更新する。これにより、ソート範囲が１ブロックだけ縮小する。そして、ステップＳ３９に進む。
このように、第２段階ソートは、１つのストリーミングマルチプロセッサを用いてバブルソート方式によりＮ個のブロックの要素をソートする。ただし、他の方法で第２段階ソートを行うこともできる。そこで、第２段階ソートの変形例を説明する。

図２０は、第２段階ソートの第１の変形例を示す図である。
前述の第２段階ソートでは、ブロック＃Ｎからブロック＃１に向かってスコアの高い要素を収集する第１パスを通じてブロック＃１を確定し、その後にブロック＃Ｎからブロック＃２に向かってスコアの高い要素を収集する第２パスを通じてブロック＃２を確定する。これに対し、第１の変形例では、複数のストリーミングマルチプロセッサを用いて異なるパスを部分的に重複して実行できるようにする。すなわち、第１パスが通過したブロックについて第１パスの完了を待たずに第２パスを開始するようにする。

例えば、ブロック＃１～＃６の６個のブロックに対して第２段階ソートを行うことを考える。ストリーミングマルチプロセッサ１２１－１は、ブロック＃５，＃６の連結ソートを行い、ブロック＃４，＃５の連結ソートを行い、ブロック＃３，＃４の連結ソートを行う。ブロック＃３，＃４が開始された時点で、ストリーミングマルチプロセッサ１２１－１によるブロック＃５，＃６の更新は既に終わっているため、ストリーミングマルチプロセッサ１２１－２はブロック＃５，＃６の連結ソートを行う。ストリーミングマルチプロセッサ１２１－１はブロック＃２，＃３の連結ソートを行い、これと並列に、ストリーミングマルチプロセッサ１２１－２はブロック＃４，＃５の連結ソートを行う。

ストリーミングマルチプロセッサ１２１－１はブロック＃１，＃２の連結ソートを行う。これにより、ソート後のブロック＃１が確定する。これと並列に、ストリーミングマルチプロセッサ１２１－２はブロック＃３，＃４の連結ソートを行う。また、ブロック＃３，＃４が開始された時点で、ストリーミングマルチプロセッサ１２１－２によるブロック＃５，＃６の更新は既に終わっているため、ストリーミングマルチプロセッサ１２１－３はブロック＃５，＃６の連結ソートを行う。

ストリーミングマルチプロセッサ１２１－２はブロック＃２，＃３の連結ソートを行う。これにより、ソート後のブロック＃２が確定する。これと並列に、ストリーミングマルチプロセッサ１２１－３はブロック＃４，＃５の連結ソートを行う。その後、ストリーミングマルチプロセッサ１２１－３はブロック＃３，＃４の連結ソートを行う。これにより、ソート後のブロック＃３が確定する。これと並列に、ストリーミングマルチプロセッサ１２１－１はブロック＃５，＃６の連結ソートを行う。

そして、ストリーミングマルチプロセッサ１２１－１はブロック＃４，＃５の連結ソートを行う。これにより、ソート後のブロック＃４が確定する。ストリーミングマルチプロセッサ１２１－１はブロック＃５，＃６の連結ソートを行う。これにより、ソート後のブロック＃６が確定し、ブロック＃１～＃６のソートが完了する。

なお、図２０では３つのストリーミングマルチプロセッサを使用しているが、ブロック数Ｎに応じて、並列度が最大になるように使用するストリーミングマルチプロセッサを増やしてもよい。また、並列制御が簡潔になるように、使用するストリーミングマルチプロセッサを２個など所定個に限定してもよい。

図２１は、第２段階ソートの第２の変形例を示す図である。
第２の変形例の第２段階ソートは、第１段階ソートと同様に、多くのストリーミングマルチプロセッサを使用して並列度を上げるようにする。第２の変形例の第２段階ソートは、隣接する２つのブロックを連結することを木構造で繰り返す。このため、ブロック数を２のべき乗とし、不足する分についてはスコアが全て０のダミーブロックを用意する。

例えば、ブロック＃１～＃８の８個のブロックに対して第２段階ソートを行うことを考える。ストリーミングマルチプロセッサ１２１－１は、１０２４個のスレッドを２セット実行してブロック＃１，＃２の連結ソートを行う。これと並列に、ストリーミングマルチプロセッサ１２１－２は、１０２４個のスレッドを２セット実行してブロック＃３，＃４の連結ソートを行う。これと並列に、ストリーミングマルチプロセッサ１２１－３は、１０２４個のスレッドを２セット実行してブロック＃５，＃６の連結ソートを行う。これと並列に、ストリーミングマルチプロセッサ１２１－４は、１０２４個のスレッドを２セット実行してブロック＃７，＃８の連結ソートを行う。

隣接２ブロックのソートが終わると、ストリーミングマルチプロセッサ１２１－１は、１０２４個のスレッドを４セット実行してブロック＃１～＃４の連結ソートを行う。ブロック＃１，＃２の集合とブロック＃３，＃４の集合はそれぞれソート済みであるため、２つのデータセットの連結ソートとして実行できる。これと並列に、ストリーミングマルチプロセッサ１２１－３は、１０２４個のスレッドを４セット実行してブロック＃５～＃８の連結ソートを行う。ブロック＃５，＃６の集合とブロック＃７，＃８の集合はそれぞれソート済みであるため、２つのデータセットの連結ソートとして実行できる。

隣接４ブロックのソートが終わると、ストリーミングマルチプロセッサ１２１－１は、１０２４個のスレッドを４セット実行してブロック＃１～＃８の連結ソートを行う。ブロック＃１～＃４の集合とブロック＃５～＃８の集合はそれぞれソート済みであるため、２つのデータセットの連結ソートとして実行できる。

前述の元の第２段階ソートでは、８個のブロックから上位６個のソート済みブロックを求める場合、１つのストリーミングマルチプロセッサで１０２４個のスレッドを２×（７＋６＋５＋４＋３＋２）＝５４回実行することになる。これに対し、第２の変型例の第２段階ソートによれば、まず、４つのストリーミングマルチプロセッサそれぞれで１０２４個のスレッドを２回実行する。次に、２つのストリーミングマルチプロセッサそれぞれで１０２４個のスレッドを４回実行する。そして、１つのストリーミングマルチプロセッサで１０２４個のスレッドを８回実行する。よって、実質的な実行回数は１４である。このため、スレッドの実行時間を短縮できる。

ただし、第２の変型例の第２段階ソートは、グローバルメモリ１２３と各ストリーミングマルチプロセッサの共有メモリとの間のブロックの転送量が増加する。このため、第２の変型例の第２段階ソートは、並列度の上昇による合計スレッド実行時間の減少量が、メモリアクセス時間の増加量を超えることで、全体としてソートを高速化できる。

次に、ステップＳ２５のＮＭＳ処理の効率化について説明する。
図２２は、スコア付き位置データのＮＭＳ処理例を示す図である。
スコア付き位置データ１５１は、物体候補領域を示す要素の集合であり、スコアの大きい順にソートされたものである。物体候補領域生成部１３５の選択部１３９は、ＮＭＳ処理によりスコア付き位置データ１５１から一部の要素を削除する。削除する要素は、スコアの小さい物体候補領域のうちスコアの大きい物体候補領域との間で領域重複割合が高いものを示す要素である。領域重複割合の指標としてＩｏＵを使用することができる。物体候補領域Ａと物体候補領域Ｂの間のＩｏＵは、ＩｏＵ＝（Ａ∩Ｂ）／（Ａ∪Ｂ）であり、物体候補領域Ａ，Ｂの全体領域のうち重複している部分の面積の割合である。ＩｏＵは領域の重なりが多いほど１に近くなり、領域の重なりが少ないほど０に近くなる。選択部１３９は、物体候補領域Ａ，ＢのＩｏＵが閾値（例えば、０．７）を超えている場合、物体候補領域Ａ，Ｂのうちスコアの小さい方を削除する。

例えば、図２２において、スコアが０．９９の物体候補領域とスコアが０．０７の物体候補領域との間の領域重複割合が大きいため、スコアが０．０７の要素がスコア付き位置データ１５１から削除される。また、スコアが０．９７の物体候補領域とスコアが０．０５の物体候補領域との間の領域重複割合が大きいため、スコアが０．０５の要素がスコア付き位置データ１５１から削除される。また、スコアが０．９５の物体候補領域とスコアが０．０２の物体候補領域との間の領域重複割合が大きいため、スコアが０．０２の要素がスコア付き位置データ１５１から削除される。また、スコアが０．９４の物体候補領域とスコアが０．０１の物体候補領域との間の領域重複割合が大きいため、スコアが０．０１の要素がスコア付き位置データ１５１から削除される。

次に、並列化しないＮＭＳ処理の手順について説明する。
図２３は、ＮＭＳ処理の逐次実行の手順例を示すフローチャートである。
逐次実行のＮＭＳ処理は、前述のステップＳ２５で実行することができる。

（Ｓ５０）選択部１３９は、変数ｉの値をｉ＝１に初期化する。
（Ｓ５１）選択部１３９は、変数ｊの値をｊ＝ｉ＋１に初期化する。
（Ｓ５２）選択部１３９は、スコア付き位置データのｉ番目の要素（要素ｉ）が示す物体候補領域と、スコア付き位置データのｊ番目の要素（要素ｊ）が示す物体候補領域との間で、領域重複割合であるＩｏＵを算出する。

（Ｓ５３）選択部１３９は、ステップＳ５２で算出したＩｏＵが閾値（例えば、０．７）を超えるか判断する。ＩｏＵが閾値を超える場合はステップＳ５４に進み、ＩｏＵが閾値以下である場合はステップＳ５５に進む。

（Ｓ５４）選択部１３９は、スコア付き位置データから要素ｊを削除する。なお、スコア付き位置データからの要素ｊの削除は、要素ｊのスコアを、ｆｌｏａｔ型最小値など要素ｊが無効であることを示す所定値に設定することで行うことができる。

（Ｓ５５）選択部１３９は、要素ｊよりスコアの小さい要素（順位の低い要素）が残っているか判断する。要素ｊよりスコアの小さい要素が残っている場合はステップＳ５６に進み、残っていない場合はステップＳ５７に進む。

（Ｓ５６）選択部１３９は、変数ｊの値をｊ＝ｊ＋１に更新する。これにより、比較相手の要素が１つ下位の要素になる。そして、ステップＳ５２に進む。
（Ｓ５７）選択部１３９は、要素ｉよりスコアの小さい要素（順位の低い要素）が残っているか判断する。要素ｉよりスコアの小さい要素が残っている場合はステップＳ５８に進み、残っていない場合はＮＭＳ処理が終了する。

（Ｓ５８）選択部１３９は、変数ｉの値をｉ＝ｉ＋１に更新する。これにより、比較元の要素が１つ下位の要素になる。そして、ステップＳ５１に進む。
上記ではＮＭＳ処理の逐次実行について説明した。これに対し、２つの要素の間でＩｏＵが閾値を超えているか否かをビットマップで管理するようにし、ＧＰＵ１０４を用いてＮＭＳ処理を並列化することが考えられる。そこで、ＮＭＳ処理の並列化を説明する。

図２４は、ビットマップの例を示す図である。
ビットマップ１５２は、スコア付き位置データの２つの要素の間でＩｏＵが閾値を超えているか否かを示すフラグの集合である。ビットマップ１５２は、６０００行×６０１６列の行列である。ビットマップ１５２の１行目から６０００行目は、ソートされたスコア付き位置データに含まれる６０００個の要素に対応する。１行目は１番目の要素に対応し、２行目は２番目の要素に対応し、６０００行目は６０００番目の要素に対応する。ビットマップ１５２の１列目から６０００列目も６０００個の要素に対応する。１列目は１番目の要素に対応し、２列目は２番目の要素に対応し、６０００列目は６０００番目の要素に対応する。６００１列目から６０１６列目はダミーの列である。

ビットマップ１５２に含まれる各フラグは０または１を示すビットであり、初期値として０をとる。ｉ行ｊ列のフラグが０であることは、要素ｉと要素ｊの間のＩｏＵが閾値以下であることを示す。ｉ行ｊ列のフラグが１であることは、要素ｉと要素ｊの間のＩｏＵが閾値を超えることを示す。ビットマップ１５２は、横方向に連続する６４個のフラグを１つの単位ビット列として取り扱う。これは、プログラム上では６４ビット整数変数によって１つの単位ビット列を表現することができるためである。

１つの行は９４個の単位ビット列を含むため、ビットマップ１５２は９４×６０００＝５６４０００個の単位ビット列を含む。ＧＰＵ１０４を用いてビットマップ１５２を生成する場合、ＧＰＵ１０４が実行する１つのスレッドを１つの単位ビット列に割り当てる。よって、ビットマップ１５２は５６４０００個のスレッドを用いて並列に生成できる。

１行目の１個目の単位ビット列を担当するスレッドは、要素＃１と要素＃２～＃６４それぞれの間のＩｏＵを算出して閾値と比較し、ＩｏＵが閾値を超える組み合わせに対してフラグを０から１に変更する。１行目の２個目の単位ビット列を担当するスレッドは、要素＃１と要素＃６５～＃１２８それぞれの間のＩｏＵを算出して閾値と比較し、ＩｏＵが閾値を超える組み合わせに対してフラグを０から１に変更する。ただし、ビットマップ１５２の一部のフラグについては計算を省略できる。

図２５は、重複判定のスキップ例を示す図である。
異なる２つの要素の間のＩｏＵの計算は、要素の順序と無関係である。すなわち、ビットマップ１５２に含まれるフラグのうち、ｉ行ｊ列のフラグとｊ行ｉ列のフラグは同じ値をとる。また、同じ要素同士のＩｏＵの計算は不要である。このため、ビットマップ１５２のうち対角線を除く上三角部分のフラグのみ判定すればよい。１つのスレッドは横方向に連続する６４ビットの単位ビット列を担当するため、対角線上のフラグと単位ビット列との間の位置関係によって３通りの処理パターンが考えられる。

１つ目は、図２５の単位ビット列１５２－１のように、担当する単位ビット列が対角線の左側にある場合である。具体的には、担当する単位ビット列の中の最大の列番号が行番号以下である場合である。単位ビット列１５２－１に割り当てられたスレッドは、単位ビット列１５２－１の全てのフラグの計算を省略できる。

２つ目は、図２５の単位ビット列１５２－２のように、担当する単位ビット列の途中に対角線が通っている場合である。具体的には、担当する単位ビット列の中の最大の列番号が行番号より大きく、かつ、担当する単位ビット列の中の最小の列番号が行番号以下である場合である。単位ビット列１５２－２に割り当てられたスレッドは、単位ビット列１５２－１のうち、行番号と一致する列番号をもつ対角フラグおよび対角フラグより前方のフラグの計算を省略できる。単位ビット列１５２－２に割り当てられたスレッドは、対角フラグの１つ後ろのフラグから計算を開始することができる。

３つ目は、図２５の単位ビット列１５２－３のように、担当する単位ビット列が対角線の右側にある場合である。具体的には、担当する単位ビット列の中の最小の列番号が行番号より大きい場合である。単位ビット列１５２－３に割り当てられたスレッドは、全てのフラグの計算を省略せずに行うことになる。

なお、第２の実施の形態では、単位ビット列の途中に対角線が通っている場合、スレッドは計算量を削減するため単位ビット列の途中からフラグの計算を行うこととしている。これに対し、並列制御を簡潔にするため、単位ビット列の途中に対角線が通っている場合に、スレッドが単位ビット列の全てのフラグを計算するようにしてもよい。

図２６は、ビットマップの集計例を示す図である。
ビットマップ１５２が生成されると、以下のようにして削除すべき要素を判定できる。ビットマップ１５２の１つの行に相当する６０１６ビットのビット列を行ビット列とする。選択部１３９は、１行目の行ビット列を基準行ビット列として選択する。選択部１３９は、２行目から６０００行目までのフラグ情報を基準行ビット列に集約する。

具体的には、選択部１３９は、ｉ行目の行ビット列を選択し、基準行ビット列のｉ列目のフラグを確認する。基準行ビット列のｉ列目のフラグが０である場合、要素ｉは削除されるものではないため、要素ｉは要素ｉより下位の要素に影響を与える。そこで、選択部１３９は、基準行ビット列にｉ行目の行ビット列を合成する。行ビット列の合成は、ｉ行目の行ビット列に含まれる１のフラグを基準行ビット列に転記する論理和演算である。一方、基準行ビット列のｉ列目のフラグが１である場合、要素ｉは削除されるべきものであるため、要素ｉは要素ｉより下位の要素に影響を与えない。そこで、選択部１３９は、ｉ行目の行ビット列を基準行ビット列に合成せず無視する。これを２行目から６０００行目まで繰り返すことで、基準行ビット列にフラグ情報が集約される。基準行ビット列でフラグが１になっている列に対する要素が削除すべき要素である。

例えば、行ビット列１５３－１が１行目の行ビット列であり基準行ビット列である。行ビット列１５３－２が２行目の行ビット列であり、行ビット列１５３－３が３行目の行ビット列である。選択部１３９は、行ビット列１５３－１の２列目のフラグを確認する。フラグが０であるため、選択部１３９は、行ビット列１５３－２でフラグが１になっている列について、行ビット列１５３－１のフラグを１にする。これは、行ビット列１５３－１，１５３－２の論理和を算出して行ビット列１５３－１とすることで実現できる。次に、選択部１３９は、行ビット列１５３－１の３列目のフラグを確認する。フラグが１であるため、選択部１３９は、行ビット列１５３－１を更新しない。

ＧＰＵ１０４を用いてビットマップ１５２の集計を行う場合、ビットマップ１５２の連続する６４列を１つのスレッドに割り当てる。これは、６４ビット整数変数を用いた論理演算によってフラグの集計を行うことが効率的であるためである。ビットマップ１５２は６４列×９４個の列を含むため、９４個のスレッドを用いて並列に集計することができる。１列目から６４列目を担当するスレッドは、２行目から６０００行目の単位ビット列を１行目の単位ビット列に合成する。６５列目から１２８列目を担当するスレッドは、２行目から６０００行目の単位ビット列を１行目の単位ビット列に合成する。

次に、並列化したＮＭＳ処理の手順について説明する。
図２７は、ＮＭＳ処理の並列実行の手順例を示すフローチャートである。
並列実行のＮＭＳ処理は、前述のステップＳ２５で実行される。

（Ｓ６０）選択部１３９は、６０００行×６０１６列のビットマップを生成して各フラグを０に初期化する。６０１６列は６４ビット×９４個に分割される。
（Ｓ６１）選択部１３９は、ＧＰＵ１０４に６０００×９４個のスレッドを起動し、それぞれ６４ビットを含む６０００×９４個の単位ビット列に異なるスレッドを割り当てる。以下のステップＳ６２～Ｓ７０は単位ビット列毎に並列実行される。

（Ｓ６２）選択部１３９は、担当行番号ｉと単位ビット列の中の最大担当列番号とを比較する。担当行番号ｉが最大担当列番号以上である場合はステップＳ７１に進み、担当行番号ｉが最大担当列番号未満である場合はステップＳ６３に進む。

（Ｓ６３）選択部１３９は、担当行番号ｉが単位ビット列の中の最小担当列番号とを比較する。担当行番号ｉが最小担当列番号未満である場合はステップＳ６４に進み、担当行番号ｉが最小担当列番号以上である場合はステップＳ６５に進む。

（Ｓ６４）選択部１３９は、変数ｊの値を最小担当列番号としステップＳ６６に進む。
（Ｓ６５）選択部１３９は、変数ｊの値をｊ＝ｉ＋１とする。
（Ｓ６６）選択部１３９は、ソート済みのスコア付き位置データからｉ番目の要素（要素ｉ）とｊ番目の要素（要素ｊ）を読み出す。選択部１３９は、要素ｉの座標情報と要素ｊの座標情報に基づいて、領域重複割合としてＩｏＵを算出する。

（Ｓ６７）選択部１３９は、ステップＳ６６で算出したＩｏＵが閾値（例えば、０．７）より大きいか判断する。ＩｏＵが閾値より大きい場合はステップＳ６８に進み、ＩｏＵが閾値以下である場合はステップＳ６９に進む。

（Ｓ６８）選択部１３９は、ビットマップのｉ行ｊ列のフラグを１に更新する。
（Ｓ６９）選択部１３９は、変数ｊの値が最大担当列番号と一致するか判断する。変数ｊの値が最大担当列番号と一致する場合はステップＳ７１に進み、変数ｊの値が最大担当列番号と一致しない場合はステップＳ７０に進む。

（Ｓ７０）選択部１３９は、変数ｊの値をｊ＋１に更新してステップＳ６６に進む。
図２８は、ＮＭＳ処理の並列実行の手順例を示すフローチャート（続き）である。
（Ｓ７１）選択部１３９は、ＧＰＵ１０４に９４個のスレッドを起動し、それぞれ６４列を含む９４個の列集合に異なるスレッドを割り当てる。これ以降、ステップＳ７５までの処理は列集合毎に並列実行される。選択部１３９は、変数ｉの値をｉ＝２に設定する。

（Ｓ７２）選択部１３９は、ビットマップの中の１行ｉ列のフラグが１であるか判断する。ビットマップの１行ｉ列のフラグが１である場合はステップＳ７４に進み、ビットマップの１行ｉ列のフラグが０である場合はステップＳ７３に進む。

（Ｓ７３）選択部１３９は、１行目の単位ビット列とｉ行目の単位ビット列の論理和演算により、ｉ行目で値が１のフラグを１行目に合成する。
（Ｓ７４）選択部１３９は、ｉ＝６０００であるか判断する。ｉ＝６０００である場合はステップＳ７６に進み、ｉ≠６０００である場合はステップＳ７５に進む。

（Ｓ７５）選択部１３９は、変数ｉの値をｉ＝ｉ＋１に更新しステップＳ７２に進む。
（Ｓ７６）選択部１３９は、ビットマップの１行目でフラグが１になっている列を検索し、フラグが１の列に対応する要素をスコア付き位置データから削除する。スコア付き位置データからの要素の削除は、その要素のスコアを、ｆｌｏａｔ型最小値など要素が無効であることを示す所定値に設定することで行うことができる。

次に、画像認識の高速化の効果について説明する。
図２９は、ソートとＮＭＳ処理の実行時間例を示すグラフである。
グラフ５０は、物体候補領域生成部１３５におけるソート処理の実行時間とソート実装方法との間の関係を示している。更に、グラフ５０は、物体候補領域生成部１３５におけるＮＭＳ処理の実行時間とＮＭＳ実装方法との間の関係を示している。実行時間は、Ｆａｓｔｅｒ Ｒ－ＣＮＮ方式による入力画像１つ当たりの時間である。

棒５１は、ＣＰＵにより汎用的なソートプログラムでソート処理を行った場合の実行時間を示しており、実行時間は約１．５ミリ秒である。棒５２は、ＣＰＵにより既存の画像認識用プログラムでＮＭＳ処理を行った場合の実行時間を示しており、実行時間は約１２．２ミリ秒である。棒５３は、ＣＰＵにより既存の画像認識用プログラムでソート処理を行った場合の実行時間を示しており、実行時間は約０．９ミリ秒である。棒５４は、ＧＰＵにより既存の画像認識用プログラムでＮＭＳ処理を行った場合の実行時間を示しており、実行時間は約２．２ミリ秒である。棒５５は、第２の実施の形態のソート処理の実行時間を示しており、実行時間は約０．５ミリ秒である。棒５６は、第２の実施の形態のＮＭＳ処理の実行時間を示しており、実行時間は約１．２ミリ秒である。

図３０は、画像認識の実行時間例を示すグラフである。
グラフ６０は、１つの入力画像（１フレーム）当たりの画像認識全体の実行時間を示している。なお、ソート処理自体の高速化およびＮＭＳ処理自体の高速化による実行時間の短縮に加えて、できる限りＧＰＵ１０４にデータを保持し続けてＧＰＵ１０４とＲＡＭ１０２の間のデータ転送を削減することによっても実行時間が短縮されている。

棒６１は、既存の画像認識用プログラムによる画像認識全体の実行時間を示しており、実行時間は約８０ミリ秒である。これに対して、棒６２は、第２の実施の形態の画像認識全体の実行時間を示しており、実行時間は約５５ミリ秒である。

第２の実施の形態の画像認識装置１００によれば、ＲＰＮ層における要素のソート処理において、異なるスレッドが異なる要素に割り当てられ、ソート後の順位を示すインデックスが並列に算出される。そして、算出されたインデックスに基づいて複数の要素が一斉に移動される。これにより、並列度を上げることができ、多数のスレッドを並列実行可能なＧＰＵ１０４を活用してソート処理を高速化できる。また、２つのソート済みのグループから１つのソート済みのグループを形成する場合、自グループにおける現在の順位と他グループに対する二分探索により、各要素のソート後の順位を示すインデックスが算出される。これにより、スコアの比較回数を削減することができる。

また、ソート処理の第１段階では、各ストリーミングマルチプロセッサでローカルに、小グループを段階的に連結することで１０２４個の要素がソートされる。これにより、できる限り各ストリーミングマルチプロセッサ内の閉じた処理により多くの要素がソートされ、メモリアクセスを抑制することができる。また、８要素グループを最小グループとすることで、計算量を削減できる。また、ソート処理の第２段階では、１つのストリーミングマルチプロセッサでバブルソート方式により、１０２４個を超える要素がソートされる。これにより、メモリアクセスを抑制することができる。また、ソート処理の第２段階では、複数のストリーミングマルチプロセッサを用いて並列度を上げることもできる。

また、ＲＰＮ層におけるＮＭＳ処理において、要素間の領域重複割合が閾値を超えているか否かを示すビットマップが生成され、ビットマップを集計して削除すべき要素が判定される。これにより、複数のスレッドを用いてＮＭＳ処理を並列化することが容易となり、ＧＰＵ１０４を活用してＮＭＳ処理を高速化できる。また、ビットマップの中の過半数のフラグについては計算を省略することができ、ＮＭＳ処理の計算量を削減できる。このように、ＧＰＵ１０４を活用して画像認識の実行時間を短縮できる。

１０ 画像認識装置
１１ 演算処理装置
１１－１～１１－８ 演算部
１２ 記憶部
１３－１～１３－８ データ要素
１４－１～１４－８ インデックス

Claims (9)

1. 複数の演算部を含む演算処理装置と、
   画像の中から検出された複数の候補領域に対応して、それぞれが候補領域の位置および評価値を示す複数のデータ要素を記憶する記憶部とを有し、
   前記演算処理装置は、前記複数のデータ要素それぞれのソート後の順位を示すインデックスを、当該データ要素の評価値および少なくとも一部の他のデータ要素の評価値を参照して、前記複数の演算部を用いて並列に算出し、前記インデックスの算出後、前記複数の演算部を用いて、前記インデックスに基づいて前記複数のデータ要素を並列に移動させることで、前記複数のデータ要素をソートし、
   前記演算処理装置は、ソート後の前記複数のデータ要素の順序に基づいて、前記複数の候補領域の中から一部の候補領域を選択する、
   画像認識装置。
2. 前記複数のデータ要素のソートでは、前記演算処理装置は、
   前記複数のデータ要素を複数の単位グループに分割し、
   前記複数の単位グループそれぞれの中で、当該単位グループに属するデータ要素の間で評価値を比較して、当該単位グループに属するデータ要素をソートし、
   ソート済みの２つの単位グループの間で、一方の単位グループに属するデータ要素の連結後の順位を示すインデックスを、前記一方の単位グループ内における順位と当該データ要素を他方の単位グループに挿入する場合の前記他方の単位グループ内における順位とから算出して、前記２つの単位グループを連結したソート済みのグループを生成する、
   請求項１記載の画像認識装置。
3. 前記複数のデータ要素のソートでは、前記演算処理装置は、
   前記複数のデータ要素を、所定数のデータ要素をもつ複数のブロックに分割し、
   前記複数のブロックそれぞれの中でデータ要素をソートし、
   ソート済みの２つのブロックを連結してソート済みの連結ブロックを生成し、前記連結ブロックから前記評価値の順に前記所定数のデータ要素を抽出し、抽出した前記所定数のデータ要素と他のブロックとを連結することを繰り返すことで、前記複数のデータ要素の中から前記評価値の順に前記所定数のデータ要素を抽出する、
   請求項１記載の画像認識装置。
4. 前記複数のブロックのうち一部のブロックを一時的に記憶する他の記憶部を更に有し、
   前記複数のデータ要素のソートでは、前記演算処理装置は、前記２つのブロックを前記記憶部から前記他の記憶部に読み込み、連結後に前記所定数のデータ要素を前記他の記憶部に保持して、前記連結ブロックの中の他のデータ要素を前記他の記憶部から前記記憶部に書き出し、前記他のブロックを前記記憶部から前記他の記憶部に読み込む、
   請求項３記載の画像認識装置。
5. 前記複数のデータ要素のソートでは、前記演算処理装置は、第１のブロックと第２のブロックとを連結して第１の連結ブロックを生成し、前記第１の連結ブロックのうちの前記所定数のデータ要素と第３のブロックとを連結して第２の連結ブロックを生成した場合、前記第２の連結ブロックのうちの前記所定数のデータ要素と第４のブロックとを連結する処理と、前記第１の連結ブロックのうちの残りのデータ要素と前記第２の連結ブロックのうちの残りのデータ要素とを連結する処理とを並列に実行する、
   請求項３記載の画像認識装置。
6. 前記複数の演算部は、所定の並列度をもつ複数の演算部グループに分かれており、
   前記複数のデータ要素のソートでは、前記演算処理装置は、前記複数のデータ要素を前記所定の並列度に応じた個数のデータ要素をもつ複数のブロックに分割し、前記複数のブロックそれぞれの中でデータ要素をソートする第１の処理と、それぞれソート済みである前記複数のブロックを連結する第２の処理とを、異なるソート方法によって実行する、
   請求項１記載の画像認識装置。
7. 前記複数の演算部は、ＧＰＵ（Graphics Processing Unit）が有するプロセッサコアであり、前記記憶部は、前記ＧＰＵが有するメモリである、
   請求項１記載の画像認識装置。
8. 画像認識装置が、
   画像の中から検出された複数の候補領域に対応して、それぞれが候補領域の位置および評価値を示す複数のデータ要素を取得し、
   前記複数のデータ要素それぞれのソート後の順位を示すインデックスを、当該データ要素の評価値および少なくとも一部の他のデータ要素の評価値を参照して、前記画像認識装置が有する複数の演算部を用いて並列に算出し、
   前記インデックスの算出後、前記複数の演算部を用いて、前記インデックスに基づいて前記複数のデータ要素を並列に移動させることで、前記複数のデータ要素をソートし、
   ソート後の前記複数のデータ要素の順序に基づいて、前記複数の候補領域の中から一部の候補領域を選択する、
   画像認識方法。
9. コンピュータに、
   画像の中から検出された複数の候補領域に対応して、それぞれが候補領域の位置および評価値を示す複数のデータ要素を取得し、
   前記複数のデータ要素それぞれのソート後の順位を示すインデックスを、当該データ要素の評価値および少なくとも一部の他のデータ要素の評価値を参照して、前記コンピュータが有する複数の演算部を用いて並列に算出し、
   前記インデックスの算出後、前記複数の演算部を用いて、前記インデックスに基づいて前記複数のデータ要素を並列に移動させることで、前記複数のデータ要素をソートし、
   ソート後の前記複数のデータ要素の順序に基づいて、前記複数の候補領域の中から一部の候補領域を選択する、
   処理を実行させる画像認識プログラム。

Images