Fast Point Feature Histograms (FPFH) descriptors

高速点特徴量ヒストグラム(FPFH)記述子

出典:http://pointclouds.org/documentation/tutorials/fpfh_estimation.php#fpfh-estimation

与えられたポイントクラウド$\boldsymbol{P}$の$n$個の点の点特徴ヒストグラム(PFH, http://lang.sist.chukyo-u.ac.jp/Classes/PCL/PFHdescriptors.html を参照)の理論計算量は$O(nk^2)$である。ここで$k$は$\boldsymbol{P}$の各ポイント$\boldsymbol{p}$の近傍数とする。したがってリアルタイムもしくはほぼリアルタイムのアプリケーションの場合、密度の高い近傍の点特徴ヒストグラムの計算は、主要なボトルネックの1つとなっている。

このチュートリアルでは、FPHの単純化であるFPFH(Fast Point Feature Histogram)(詳細については 詳細は Rusu (2009) PhD Thesis http://mediatum.ub.tum.de/download/800632/800632.pdf を参照)を紹介する。これはPHFの識別能力をほぼ保持しながら、アルゴリズムの計算量を$O(nk)$に減少させたものである。

Theoretical primer

基礎理論

ヒストグラム特徴計算を単純化するために、以下のようにする:

  • 最初のステップでは、各クエリーポイント$\boldsymbol{p}_q$に対し、それ自体とその近傍との間の$\alpha, \phi, \theta$の組(PFHの項参照)の集合を計算する。これを単純化点特徴量ヒストグラム( Simplified Point Feature Histogram, SPFH)と呼ぶ。
  • 2番目のステップでは、各点について、そのk個の近傍を再決定し、隣接するSPFH値を重みとして用いて$\boldsymbol{p}_q$の最終的なヒストグラム(FPFHと呼ぶ)を次のように求める: http://pointclouds.org/documentation/tutorials/_images/math/6532e29a336c015f77cf8ea40df23a28b188bf0a.png

ここで、重み$\omega_k$はある距離空間においてクエリー点$\boldsymbol{p}_q$と近傍点$\boldsymbol{p}_k$の距離を表し、したがって$(\boldsymbol{p}_q、\boldsymbol{p}_k)$対に対する値を計算している。ただし、必要ならば異なる距離空間を選択することもできる。 この重み付け手法の重要性を理解できるよう、下の図は、$\boldsymbol{p}_q$を中心とする$k$-近傍集合の影響領域図を示したものである。

http://pointclouds.org/documentation/tutorials/_images/fpfh_diagram.png

このアルゴリズムは、与えられたクエリ点$\boldsymbol{p}_q$について、その点自身とその近傍との間のペア(赤線で示す)を作成して、まずそのSPFH値を推定する。 これをデータセット内のすべての点について繰り返し、次に$\boldsymbol{p}_k$近傍のSPFH値を使用して$\boldsymbol{p}_q$のSPFH値を再重み付けし、$\boldsymbol{p}_q$のFPFHを作成する。 最後に追加された重み付けに関係したFPFH接続は、図において黒線で示されている。 図に示すように、ペアのいくつかは2回カウントされる(図では太い線で示されている)。

Differences between PFH and FPFH

PFHとFPFHの違い

PFHとFPFH製剤の主な相違点を以下に要約する。

  1. FPFHは、図からわかるように、$\boldsymbol{p}_q$のすべての近傍を完全には相互接続していないため、クエリ点の周囲の幾何形状を把握するのに役立ついくつかの値のペアが欠落する。
  2. PFHはクエリー点の周りに正確に決定された表面をモデル化するが、FPFHは半径${\bf r}$球の外側に($2{\bf r}$以下)追加の点のペアを含める。
  3. 再加重方式のため、FPFHはSPFH値を結合し、隣接した点ペアのいくつかの値を再捕捉する。
  4. FPFHの全体的な複雑さは大幅に減少し、リアルタイムのアプリケーションで使用することが可能。
  5. 得られたヒストグラムは、値を非相関化して単純化している。つまり、特徴量次元ごとに1つずつ合計$d$個の個別の特徴量ヒストグラムを作成し、それらを連結する(下図参照)。

http://pointclouds.org/documentation/tutorials/_images/fpfh_theory.jpg

Estimating FPFH features

FPFH特徴量の推定

FPFH(Fast Point Feature Histograms)は、pcl_featuresライブラリの一部としてPCLに実装されている。

デフォルトのFPFH実装では、11ビン領域(たとえば、4個の特徴量の値のそれぞれがこの個数のビンを用いる)と非相関スキーム(前述したように、特徴量ヒストグラムが別々に計算され結合される) が用いられ、結果としてfloat値の33バイトの配列が返される。 これらは、pcl :: FPFHSignature33ポイントタイプとして記憶される。

実際にFPFHEstimationで計算されていることは次:

for each point p in cloud P
  1. pass 1:
     1. get the nearest neighbors of :math:`p`
     2. for each pair of :math:`p, p_k` (where :math:`p_k` is a neighbor of :math:`p`, compute the three angular values
     3. bin all the results in an output SPFH histogram
  2. pass 2:
     1. get the nearest neighbors of :math:`p`
     2. use each SPFH of :math:`p` with a weighting scheme to assemble the FPFH of :math:`p`: