一、論文解讀

論文：?Drost et al. Model Globally, Match Locally: Efficient and Robust 3D Object Recognition. CVPR, 2010. http://campar.in.tum.de/pub/drost2010CVPR/drost2010CVPR.pdf Model Globally, Match Locally?論文名字用 4 個詞高度總結(jié)了 PPF 算法的精髓：“整體建模，局部匹配”。下面研讀一下摘要（Abstarct）：

[1] This paper addresses the problem of?recognizing free form 3D objects in point clouds.

第一句話表明論文的研究方向與問題：3D物體點云（free form）的識別

[2] Compared to traditional approaches based on?point descriptors, which depend on local information around points, we propose a novel method that?creates a global model description based on oriented point pair features and matches that model locally using a fast voting scheme.

第二句話既表明論文的創(chuàng)新點（與前人方法的區(qū)別），又用一句話總結(jié)本文的中心思想。 ·Model Globally:?creates a global model description based on oriented point pair features ·Match Locally:?matches that model locally using a fast voting scheme

[3] The?global model description?consists of all model point pair features and represents a mapping from the point pair feature space to the model, where similar features on the model are grouped together.

第三句話緊接著解釋了什么是 global model description

[4] Such representation allows using much sparser object and scene point clouds, resulting in very fast performance.

第四句話說明這種 representation 的優(yōu)點：稀疏采樣，提升算法速度

[5] Recognition is done locally using an efficient voting scheme on a reduced two-dimensional search space.

第五句話表明如何實現(xiàn) recognition：使用有效的投票機(jī)制在二維搜索空間里做局部匹配

[6] We demonstrate the efficiency of our approach and show its high recognition performance in the case of?noise, clutter and partial occlusion.

第六句話表明本文算法針對的場景問題：干擾、堆疊、部分遮擋

[7] Compared to state of the art approaches we achieve better recognition rates, and demonstrate that with a slight or even no sacrifice of the recognition performance our method is much faster then the current state of the art approaches.

第七句話說明通過與 SOTA 方法的對比，文中提出的方法既保證了高的識別率，又在不犧牲識別性能的情況下提升了算法的速度。 接下來看一下論文的算法：

1. Model Globally

首先定義兩個詞：scene?和?model?，scene 是我們測得的真實場景（點云），model 是物體的真實模型（點云）。

Both the scene and the model are represented as a finite set of oriented points, where a normal is associated with each point.

符號表示：

?points in the scene

?points in the model

（1）Point Pair Feature (PPF) Model Gobally 的本質(zhì)是通過定義 Point Pair Feature，來構(gòu)建特征矢量的集合以及每個特征矢量對應(yīng)的點對集，作為 Global Model Desciption。所以，首先先定義 PPF。 PPF 描述了兩個有向點（oriented points）的相對位置和姿態(tài)。 假設(shè)有兩個點??和??，法向量（normals）分別為??和??，??，則 PPF 定義為： 注：??為兩個矢量的夾角，且??是非對稱的。PPF 示意圖見 Figure2.(a)。 有了 Point Pair Feature，就可以用其來定義 Global Model Description。 （2）Global Model Description 注：Global Model Description 是離線（in the off-line phase）構(gòu)建的 先看原文：

The model is represented by a set of?point pair features?with similar?feature vectors?being grouped together.

實現(xiàn)方法： 第一步：計算 model 表面所有 point pairs 的特征矢量??，其中 distances 和 angles 分別以??和??的步長做采樣； 第二步：構(gòu)建哈希表（hash table），將具有相同 feature vector??的 point pair 放在一起，即哈希表的鍵（key ）為 feature vector??，值（value）為具有相同特征矢量的點對集??，如 Figure2.(b) 所示。 ?

The global model description is a mapping from the sampled point pair feature space to the model.

2. Match Locally

當(dāng)定義好全局模型描述（Global Model Description）后，就可以考慮局部匹配了。 All model features??that are similar to a given scene feature??can then be searched in constant time by using??as a key to access the hash table. （1）Local Coordinates 局部匹配的大概思路如下： ·從 scene 中選取任意一個參考點??，假設(shè)它在物體的表面上，若假設(shè)正確，則在 model 存在一個點??與??對應(yīng)； ·將這兩個參考點配準(zhǔn)，需同時將點的位置和法向量對齊； ·讓 model 繞??的法向軸轉(zhuǎn)動一定角度與 scene 配準(zhǔn) 由此看來，從 model space 到 scene space 的剛體變換可以由 model 中的一點和轉(zhuǎn)動角度??來描述，將這個 pair??定義為 model 相對于參考點??的Local Coordinates 。 現(xiàn)在明確一下思路： ·給定參考點??，選取與 scene 點對??具有相似 fecture vector?（same distance and relative orientation）的 model 點對??； ·通過變換矩陣??將??移動到 Local Coordinates 的原點，并且轉(zhuǎn)動 model，使其法向軸??與 Local Coordinates 的??軸重合； ·同理，通過??對 scene 做相同操作； ·最后，將 model 中的一點??繞??軸轉(zhuǎn)動??與??配準(zhǔn) 通過上述描述，可以將從 model 到 scene 的 transformation 定義為：??，如 Figure 3 所示。

（2）Voting Scheme 現(xiàn)在我們可以將研究問題定義如下： ? 前面我們定義了 local coordinates，現(xiàn)在只需要通過一種方法找到最優(yōu)的 local coordinates 使得 scene 中落在 model 表面的點最多，即可求出物體 pose。 論文通過投票機(jī)制實現(xiàn)，定義一個二維的 accumulator array，行（rows）數(shù)??為 model 采樣點??的個數(shù)，列（columns）數(shù)??為按采樣步長??的旋轉(zhuǎn)角??的個數(shù)。 This accumulator array represents the discrete space of local coordinates for a fixed reference point. 具體實現(xiàn)： ·對于 scene 的參考點??，與 scene 中所有其他的點組成點對??，對每一個點對，計算??； ·將??作為 key，搜索 global model description 的哈希表，找到與??類似（distance & normal）的 model 特征矢量??和點對??； ·對于每個匹配的 model 點對??，通過之前的公式??可以算出旋轉(zhuǎn)角??； ·對??與二維數(shù)組中離散??對應(yīng)的位置投票（+1）； ·全部計算完后，我們就可以得到參考點??的最大得票所對應(yīng)的??和??，即最優(yōu)的 local coordinates?

（3）Efficient Voting Loop 對每個點對都要求解??，為了加速計算，將??分解：??，這樣就可以分別計算??和??了。 根據(jù)??和??，求得： 注： ·對于 model 或者 scene 中的每個點對，??都是唯一的 ·對于 model 中的每個點對，??可以在離線階段求解 ·對于 scene 中的每個點對，??只需要算一次 （4）Pose Clustering 之前的算法基于我們的假設(shè)：參考點是在物體表面的。因此，我們需要在 scene 點云中采樣多個參考點??，保證至少有一個參考點能在物體表面。 每個參考點可能返回多個位姿（投票相同），返回的位姿（retrieved poses）是否逼近 ground truth，取決于 model 和 scene 點的采樣率和旋轉(zhuǎn)角的采樣。 我們對所有返回的位姿做聚類，每個 clutter 中位姿的位置、姿態(tài)的差異不超過設(shè)定的閾值，然后每個聚類的得分是其包含的所有位姿的總得分，找出得分最高的 clutter，則最終的位姿 為得分最高的 clutter 里面包含位姿的平均值。 如果場景中存在物體的多個實例，則會返回多個 clutters。

二、 OpenCV 實現(xiàn)

opencv_contrib 代碼： https://github.com/opencv/opencv_contrib/tree/master/modules/surface_matching 文檔 Documentation： https://docs.opencv.org/3.0-beta/modules/surface_matching/doc/surface_matching.html 測試數(shù)據(jù)集： http://staffhome.ecm.uwa.edu.au/~00053650/recognition.html 注意： ·Mian數(shù)據(jù)集 ply 文件不含 normal 信息，需先計算法向量 ·可視化使用的 open3d（顏色渲染：z coordinate as color） 測試結(jié)果：

model scene 將經(jīng)過位姿轉(zhuǎn)換的 model 點云與 scene 點云疊加的效果： transformed model & scene

三、Matlab 實現(xiàn)

Github Project: https://github.com/guglu/ppf-matching 注： 代碼中 mex 可執(zhí)行文件應(yīng)該是在 windows 平臺下編譯的，而我是在 ubuntu 系統(tǒng)中使用 matlab，所以需要重新編譯一下，在 command line 中運行：

mex mex/computePPFmex.cpp mex mex/computePPFmex.cpp mex mex/MurmurHash3.cpp 運行 test_detector.m 腳本即可。 ? 結(jié)果：??

?

四、PCL 實現(xiàn)

PCL 中關(guān)于 PPF 的示例代碼如下： https://github.com/PointCloudLibrary/pcl/blob/master/apps/src/ppf_object_recognition.cpp PCL 中定義了： PPFSignature：ppf 特征，定義在 point_types.hpp 中，是一種數(shù)據(jù)類型； PPFHashMapSearch：哈希表搜索模板類 PPFRegistration：ppf 配準(zhǔn)模板類 建議在 PPF 之后用 ICP 迭代優(yōu)化。

編輯：黃飛