按：目前“大数据”、“3D数字化”、“人工智能AI”、“深度学习”、“AR/VR”是数字智能领域的热点研究方向 ，层出不穷的新概念让一般人看的眼花缭乱。

其实，“万变不离其宗”！本【3D智能十八篇】系列共分十八篇，作者吴怀宇（中科院博士、北大博士后）为中国3D科技产业联盟副理事长。每一篇都力求仅以一页纸的篇幅，来系统完整地介绍十八个主要方向 ，深入浅出。以下内容摘自吴怀宇博士2017年新出版的《3D打印：三维智能数字化创造》（第3版）一书，完整内容及详细目录详见链接：点击查看完整目录列表（含购书链接）

往期回看（点击查看）：

【3D智能十八篇之一】形状分析：优化3D打印形状的表现力

【3D智能十八篇之二】立体视觉重建：将照片转成3D数字模型

【3D智能十八篇之三】众里寻她千百度：海量3D模型的形状检索

【3D智能十八篇之四】3D降维攻击：上帝如何优雅地拍扁你！参数化

－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－

【众里寻她千百度──海量3D模型的形状检索】

现在网上的3D模型的数量可谓海量，仅Shapeways这一个网站就有100多万个模型。因此，绝大多数情况下我们根本无须亲手设计模型，只需把自己需要的找出来再3D打印即可。

“找”这个字说起来容易，做起来难。不像文本这样的结构化数据，3D模型属于典型的非结构化数据。因此文本时代的网页搜索引擎已经力不从心了。有的读者会说，我给每一个3D模型用文本描述/标注一下不就行了？如图6-27所示，输入关键词car，则将3D模型库中所有的小汽车都找了出来。但如果是100万个模型，手工标注的工作量就太大了，比如这个模型要标上“一头脸上有道刀疤的黑色的猪”，那个模型要标上“一只黄色的短尾巴狗”等，十分烦琐。而且，光凭文本是无法描述清楚一个具体形状的。比如你钟情的一位美丽姑娘，你即使是用“娇洁凝碧水，似飘雪落轻盈；修弱纤纤指，柔声语嘤；巧笑倩兮，美目盼兮；夫何瑰逸之令姿，独旷世以秀群；佩鸣玉以比洁，齐幽兰以争芬”这样的一堆形容词来描述，别人也还是无法想象出她的具体样子来。

图6-27  通过文本进行3D模型检索。左：输入关键词car，右：返回所有的小汽车模型

因此，最靠谱的形状检索方法还是直接面向形状本身 （即：基于内容的检索），让智能算法自动提取出形状的特征，然后计算形状的相似度度量，将最相似的结果返回给你。要把整个算法流程对之前没有任何基础的读者描述清楚，是个极具挑战性的艰巨任务。因此，下面笔者会把问题做不影响本质的简化，并一步一步娓娓道来。（注：本篇暂不涉及当前最时髦的深度学习算法，读者欲详细了解机器学习的这个分支可查看本书“第4.6.3节 深度学习：像人脑一样深层次地思考”，或耐心等待本连载的第八篇）

1、线性分类与感知机模型

为阐述方便，我们把问题简化成两类。假设整个数据库共有10,000个模型，但只有两种类型的3D模型：人体的模型和猩猩的模型。在检索之前，我们先上传一个已有的模型（人体或猩猩），接下来算法的目标是：要对此模型进行分析，判断它到底是人体还是猩猩。如果是人体，则将数据库中所有的人体模型列出来；反之，则把所有的猩猩模型列出来。于是，问题的关键在于：视觉算法如何智能地判别我们上传的那个3D模型到底是人体还是猩猩呢？

为了让视觉算法解答这个问题，第一步需要提取出形状的特征。我们这里讨论最直观的几何测量特征，比如，我们对数据库中所有模型都测量它们的身高、手臂长度、头围、两眼之间的距离、大腿长度、嘴巴突起的高度、门牙长度等50个特征。

考虑到数据库中有K=10,000个模型，50个特征将形成很高维的数据量，即所谓的“维数灾难”（又名维度之咒，Curse of Dimensionality）。因此我们需要降维。最常用的方法是使用主成分分析PCA，将不重要的或冗余的特征删除。为直观起见，我们假设重新生成的特征中只选择了最重要的两个：“手臂长度与身高的比例”θ、“嘴巴突起的高度与头围的比例”δ。

提示：

 采用主成分分析（PCA）降维后，得到的新特征未必有直观的几何解释，往往都是抽象的、不具备直观意义的。本例采用直观特征主要是为了解说方便。

维数灾难有两个角度的解释。当样本数量很大时，高维会导致数据量很大，占用大量的计算机内存和CPU处理时间。但在机器学习领域更为常见的解释是，当样本数量较少时，高维会使得可用数据在空间中变得很稀疏、距离计算困难，从很多角度看都不相似，导致分类器的预测能力降低，参数得不到正确的估计。这时我们将数据进行（满足特定目标任务的）降维，使其在子空间（Subspace）的样本密度大大提高，距离计算也变得容易。

这样，数据库中的10,000个模型，每个模型都有两个特征。如果把每个模型都远看作一个点（也即一个二维的特征向量），投影到二维屏幕上，每个点的和坐标对应那两个特征值（θ和δ），我们就得到了类似图6-28的一张图。其中，人体模型用红色的“+”号表示，代表正样本；猩猩模型用绿色的“-”号表示，代表负样本。

图6-28  模型库中所有模型在二维平面的投影

我们在数据集中间画一条直线（图中蓝色的线），如果能够直接将这10,000个点划分成两类，那么这个数据集也被称为线性可分的（Linearly Separable）。如果把这条直线看作一个垂直于纸张的平面H，则其被称为分离超平面（Separating Hyperplane），简称超平面。

下面我们回到我们最开始的问题。用户提供一个3D模型，经过特征提取和降维后，在二维坐标上投影为一个二维点（是个包含和两个坐标值的向量）。下面要判断点位于超平面的哪一边，以此来确定到底是人体模型还是猩猩模型。

我们将上面的文本抽象为数学语言。具体来说，我们可以抽象为如下的函数，这个函数有一个很酷的名字：感知机（Perceptron），是神经网络（Neural Network）与支持向量机的基础。从上面的描述可以知道，感知机是一个线性分类器（Linear Classifier）。

提示：

是不是觉得数学符号看得很头疼？其实，抽象的数学所描绘的事物本质往往都是非常简单的，只不过符号化之后让人觉得不太直观和习惯而已。

其中，就是超平面H的数学表达。是垂直于超平面的法线向量，是超平面的截距。超平面将特征空间划分为两类，在本例中，法向量指向的一侧为负类，另一侧为正类。

为符号函数，只有两个返回值（+1和-1），在本例中分别代表是人体模型还是猩猩模型。

有了感知机，我们就可以很方便地判别一个模型属于哪一个类别了。只需把一个新坐标值代入公式（7）中进行计算，如果位于超平面的左边，，则结果应为+1，则知道这个模型是人体；如果位于超平面的右边，，则结果应为-1，则知道这个模型为猩猩。OK，是不是特别简单？！

提示：

Novikoff收敛定理. 如果训练样本集是线性可分的，那么感知机算法可在有限次迭代后收敛。令为输入样本特征向量的最大长度，超平面关于训练样本集的几何间隔距离为，则感知机算法在训练样本集上的误分类次数不超过，也即最多做次更新就会收敛。

证明：感知机算法仅在样本点分类错误时进行更新，令是第次误分类时所更新的（法向量）权值，算法从开始。假设第次误分类发生在样本上，类别标签或，并将截距归一化为0，则有：

  （8）

下面给出感知机的更新规则：当学习率时，我们有。将两边都乘以单位长度法向量（）：

因为初始，将上式递推可得：

（9）

根据上面的公式（8）以及，可得到：

同样，经递推可得到：

两边开根号，并根据公式（9），可得：

因此，，证毕。  ■

通过上面这个定理可知，误分类的数目不会超过样本特征向量的最大长度与几何间隔的比值的平方。也即，当训练数据集线性可分时，感知机算法必然收敛（当不可分时，算法不能保证收敛，迭代结果会发生振荡）。此外，权值的整个更新过程实际上就是与新输入样本的线性组合，因此这是个在线学习（Online Learning）的过程，即根据新来的样例，边学习边给出结果。

2、支持向量机SVM与逻辑回归LR

     同时，我们从图6-28中可以看出，感知机的超平面不是唯一的，因为有无数个超平面都能把两类数据分开！那么，是否存在一个唯一的、最优的分离超平面呢？

答案是肯定的。我们能够找到这么一个超平面，它使得分类间隔最大（Margin Maximization），这时的这个分类器称为支持向量机（SVM，Support Vector Machine）。

如图6-29所示，H就是这个最优的超平面，而H1、H2是两个与H等距平行且通过最邻近的正/负样本点的平面。此时，H1与H2之间的间隔（Margin）最大，其与最优超平面的法向量有关，间隔大小等于。

我们把H1和H2通过的最邻近正/负样本点称为支持向量（Support Vector）。可以看出，在决定最优超平面时，只有最外围的支持向量起作用，而其他内部样本点不起任何作用（去掉这些点不会有任何影响）。因此，支持向量机是典型的“少数派报告”，只由很少的几个支持向量所决定。

讨论一下，支持向量机为何青睐最大间隔，却不是最小间隔呢？因为最大间隔能获得最大的稳定性与区分度。超平面之间的距离越大，分类器的推广（泛化）能力越好，也就是预测精度越高。

有些聪明的读者可能会进一步问：“您刚才讨论的都是线性可分的情况，如果数据本身不是线性可分的，那超平面怎么去分开它们呢？”

图6-29  支持向量机与支持向量（图片来源：Bülent üstün）

Good question！实际上，现实情况很多时候就是线性不可分的，也即：此时的分类问题是非线性的。这里有两种解决方案。第一种解决方案针对近似线性可分的情况，把上面那样的硬间隔（Hard Margin）变成软间隔（Soft Margin），也即引入松驰变量（Slack Variable），允许超平面两边有误分类点，但应该让误分类点的个数尽可能小，同时让软间隔尽可能地大。

另一种解决方案是针对线性不可分的训练数据，我们可以利用核函数，即通过非线性特征映射将输入变量映射到一个高维特征空间（它有一个很酷的名字叫希尔伯特空间：Hilbert Space），在这个高维特征空间中构造最优分类超平面。“映射”这个动词可理解为变换或对应。如图6-30左边所示是一个分类问题，我们无法用直线（线性模型）将正/负样本分开，但可用椭圆线（非线性模型）将它们分开。如图6-30右边所示，如果我们采用某个核函数（Kernel Function），通过非线性变换将原始样本映射到高维特征空间中去（比如由X/Y二维映射到X/Y/Z三维），这时就可以使得原本的非线性问题简化为一个线性问题了（通过一个超平面将样本分开）！

图6-30  将低维线性不可分的数据，映射到高维变成线性可分（图片来源：DTREG）

提示：

再强调一下，我们并不直接定义映射函数和（高维）特征空间的具体形式，只需定义核函数即可，这就是所谓的核技巧（Kernel Trick）。

具体地，设是输入空间（比如本例中的二维空间），为Hilbert特征空间（为高维空间，如本例中的三维空间），如果存在一个从到的映射，使得对任意，函数。这里的就是核函数，为映射函数，中间的圆点符号代表内积运算。

上面之所以考虑内积运算，是因为如果把支持向量机转化到对偶形式（见第10章10.1.3节），可发现分类函数（超平面H）的计算只涉及输入样本之间的内积运算，甚至不必知道映射函数的具体形式。实际上，通过定义映射函数去获得高维的内积通常并非易事，而通过定义核函数在映射到高维同时可方便地获得内积──对于任意的对称函数，只要满足Mercer条件，就可作为内积使用。支持向量机采用恰当的内积函数（核函数）便可实现经某一非线性映射后的线性分类，而计算复杂度却没有增加，因为这个高维空间中的线性分类器与空间的维数无关。

然而，如何针对不同的问题选择不同的核函数仍是一个悬而未决的问题，往往依赖于领域知识。下面是常见的一些核函数。

◆ 多项式核函数（Polynomial Kernel Function）：（p>0），所对应的支持向量机是一个p次多项式分类器。

◆ S形（Sigmoid）核函数：，其中双曲正切函数tanh是Sigmoid函数的一种，所对应的支持向量机是两层感知机的一种特例。

◆ 高斯核函数（Gaussian Kernel Function）：，所对应的支持向量机是高斯径向基函数（RBF，Radial Basis Function）分类器。

上面这段文字仍比较拗口，怎么理解它呢？我们可以将左图理解为散布在面团上的红、绿两种颜色的豆子，在二维平面上无法一刀切开（只能通过画一个非线性的椭圆）。这时，我们可以揪住内部的面团往下拉（即非线性映射），这样绿色方形豆子都被移动到红色圆形豆子的Z轴下方了，由于所处高度不同，此时红、绿两种颜色的豆子就可以一刀切开了。

提示：

非线性映射是针对整个样本空间的，本例中指整个面团。这里我们定义的核函数，使得内部的面团受到的向下拉力更大，能够比外围的面团更快地下落到Z轴下方。

也许还有更聪明的读者会进一步问道：“您刚才讨论的都是两类问题（人体、猩猩），如果是多类问题（人体、猩猩、大象、老虎、狮子）呢，怎么办？”

Very good question！其实，多类问题可通过转化为多个两类问题来求解。比如共有5个类。我们可以第1次问“是第1类还是第2类”，第2次问“是第1类还是第3类”，第3次“是第1类还是第4类”，如此问下去，你终能知道属于哪一个类别。但如此一来，我们总共必须设计“5×4/2=10”个分类器。即在M个类别的情况下，总的两类分类器数目为。

扩展：

除了SVM，在工业界实际用得较多的一种机器学习方法是逻辑回归（Logistic Regression，LR），用于估计某种事物的可能性（取值0～1之间）。与SVM不同，逻辑回归既可用于分类（按照可能性大于0.5或小于0.5来区分），也可用于回归。逻辑回归仅能用于线性问题，其本质实际上仅在线性回归的基础上，套用了一个Sigmoid（S形）函数，如图6-31所示：
                       
               

图6-31  Sigmoid（S形）函数

Sigmoid函数的优势在于，虽然自变量范围是从到，但值域范围限制（挤压：Squashing）在0~1之间，也即可被看成一个概率函数。这种归一化被认为是合乎“逻辑”的，并在实际场合中得到广泛应用。

另一方面，是多个特征变量的加权线性组合：

     比如一个女生对你的好感程度（打分）可用逻辑回归量化到一个0~1之间的数值，其由多个线性因素加权得到，如通过计算你的年龄大小、经济收入多少、…、身材高度等各方面条件综合得到；而是她分别为年龄、经济收入、身高等特征设置的权值参数（回归系数），分别代表着在她心目中对每个特征的看重程度。因此，为了预测她对你的打分，关键就是要通过她之前为多名特征各异男士的已有打分，来估计出她心目中对各项特征条件的权值系数。在具体实现时，可将问题形式化为最大似然估计（参见第10章10.8.3节），并采用梯度下降（参见第10章10.3.1节）优化方法进行求解。
     综上，逻辑回归实质为一个线性分类模型，它与线性回归的不同点在于：逻辑回归将原本线性回归输出的很大范围的数，例如从负无穷到正无穷，限制在了0到1之间。

3、基于内容的3D模型检索

前面我们已经提到过，我们希望进行基于内容的3D模型检索（Content-based 3D Retrieval），也即不是根据文本描述，而是根据模型本身的几何形状、拓扑结构等进行自动检索。

提示：

拓扑学（Topology）是几何学的一个分支，不涉及长度和角度的测量，研究的是当形状发生连续形变时，那些不会改变的性质，这种变换称之为拓扑变换或同胚（Homeomorphism）。比如，我们对形状进行伸缩和弯曲（但不能撕破和黏合）后，拓扑是不变的，即同胚的。这个过程如同手捏有弹性的橡胶膜一样，因此拓扑几何也被称为“橡胶膜几何”。拓扑学不区分咖啡杯和甜甜圈，因为一个足够柔软的甜甜圈可以捏成咖啡杯的形状，两者都是有1个孔的、即亏格（Genus）为1的形状。同理，正方形和圆（都有1条边界Boundary）、立方体和球面（都有0条边界），也分别都是同胚的，它们都是亏格为0的形状，即它们的欧拉示性数（Euler Characteristic，参见第3章第3.5.1节的欧拉公式）。欧拉示性数与3D模型的各种特性都相连，假如3D模型的拓扑结构决定，则欧拉示性数唯一确定，无论形状是甜甜圈还是咖啡杯。

在用户界面上，基于内容的3D模型检索有两种交互模式。

◆ 3D示例模型检索。现有的大多数检索系统都只提供3D示例模型检索：即要求用户上传一个示例模型。比如你上传一头猪的3D模型，则检索系统将模型库中所有猪的3D模型作为返回结果。这种交互模式还可扩展到2D示例图片检索，即用户只需提供一张拍摄有一头猪的2D照片，系统也能返回模型库中所有猪的3D模型。

◆ 手画草图检索。手绘2D草图（如图6-32所示）和手绘3D草图（如图6-33所示）的检索方式提供了比较友好的界面，用户可以通过手绘2D或3D草图来表达检索要求。然而缺点是对用户的手绘技巧有一定要求，不能画得太差。

图6-32  2D草图检索（通过在左边手绘一个2D的钥匙来检索模型库中的3D钥匙模型）（图片来源：普林斯顿大学）

为了让检索系统能更清楚地了解用户的意图，还可引入相关反馈，即通过人机交互，让用户不停地“告诉”计算机：检索结果中哪些是符合要求的（相关模型）、哪些是不符合要求的（不相关模型）。系统根据用户的反馈来对用户的个人偏好进行分析，对检索结果进行修正，并返回新的结果给用户评价。如此反复交互，直到用户满意为止。

在技术原理上，基于内容的3D模型检索主要有两个步骤：提取3D模型的特征，然后比较所提取特征的相似度，以便将那些与示例模型相似度大的模型作为结果返回。

图6-33  3D草图检索（通过在左边手绘一个3D的茶杯来检索模型库中的3D茶杯模型）

一个理想的形状特征描述符（Shape Descriptor）应具有几何不变性（即对模型的平移、旋转、缩放等具有不变性）以及拓扑不变性（比如你双手抱拳与双手分开时的身体拓扑是不同的，但你仍是你）。此外，形状描述符对于噪声影响、模型简化/细分、姿态变化等也应该是保持不变的。如果按照所提取的3D模型特征的不同，3D模型检索技术可以划分为这么几大类。

◆ 基于形状的检索技术。大多数3D模型检索技术都是基于形状特征的，可进一步分为基于空间域的检索和基于频率域的检索。基于空间域的检索技术大多数使用了统计学方法，即通过统计数据来描述模型的形状特征，如形状直方图、形状分布（Shape Distributions）等。基于统计的特征对于模型的区分度不够好，因而只适用于模型的粗分类。基于频率域的检索技术可借助傅里叶变换、球面调和、流形调和（Manifold Harmonics）等频谱数学工具。

◆ 基于拓扑结构的检索技术。如采用骨架或中轴线这种拓扑结构来描述有关节的模型（如人体），代表性的有Multi-Dimensional Reeb Graphs、Shock Graphs等。拓扑结构特征比较符合人眼对模型的全局直观感受，但缺点是特征提取和匹配的时间开销过大。

◆ 基于二维投影图像比较的检索技术。将3D模型往某个侧面投影，得到一幅投影图像，这样就可直接参考已经非常成熟的2D图像检索方法了。代表性的方法有Spin Images、Shape Contexts等。注意：二维投影的图像会受到旋转及缩放的影响，因此在投影之前需要对模型进行归一化处理。

      接下来的相似性度量就是计算（多维）特征向量之间的相似度，即计算用户上传的示例模型的特征向量f与三维模型库中某个模型的特征向量fi之间的相似性距离。常见的距离度量有Euclidean距离、Manhattan距离、Hausdorff距离、Earth Mover's distance（推土机距离）、Pyramid Match Kernels（层次匹配核）等。距离越小，说明两个模型的相似性程度越高；反之，距离越大，说明两个模型之间的相似程度越小。如图6-33所示，最终系统会根据相似性度量的距离大小进行排序以返回查询结果，从而实现基于内容的模型检索。检索好坏的常见评价指标有：查准率（Precision）和查全率（Recall），即生成所谓的PR（Precision-Recall）曲线。

图6-33  根据相似性度量的距离大小进行排序返回查询结果

此外，按照检索对象的不同，现有的三维模型检索方法还可分为“全局检索”和“局部检索”[30]两大类。如图6-34所示，如果用户仅将一把椅子的靠背（属于椅子的局部）作为示例模型（操作上只需用鼠标框选住靠背部分），则检索系统将返回局部检索结果，即返回数据库中所有跟这个靠背（而不是整把椅子）相似的模型。

图6-34  局部检索的例子

目前网上已经有一些3D模型搜索引擎，如Thingiverse、3D Partsource、Defcad.com、Yeggi、Yobi3d、Fabforall、Dimensionext、Google 3D模型库等，你可以去它们的网站上体验一下。