人工智能物体形状的分析与识别.docx

人工智能物体形状的分析与识别教学内容：多面体化为对非多面体景物的描述问题，并以这些描述为基础,对物体形状进行分析与识别。教学重点：讨论非多面物体的分析，并特别集中于形状分析。教学难点：松弛标示法、多层匹配法。教学方法：课堂讲解教学要求：了解物体形状分析与识别的基本概念1复杂形状物体的表示一个好的形状表示能够由物体的部分视图来识别物体，而且物体形状的小变化只引起形状描述的小变化。物体各部分的连接表示应当是很方便的，它能够比较两个物体的差别和相似性，而不仅是进行简单的分类。如果把复杂物体表示为被分割的比较简单的部分以及这些部分间的相互关系，那么上述要求就比较容易得到满足。对形状的识别是由两个相关描述的匹配获得的。一个物体的部分视图所产生的描述图是完整的物体描述子图，并能适当匹配过程的需要。1、曲线形状的描述与量度曲线描述对于一些特别物体（如字母符号）和三维景物（如某地区照片上的道路）分析是很重要的。此外，三维物体的形状描述也往往被简化为“轮廓”线条结构。（1）曲线的存储方法。依次采用曲线上各点的坐标序列来表示线条是最容易的描述方法。如果只要存储曲线的起点坐标和依次各点的坐标增量，那么就能够显著节省计算机内存。（2）曲线的近似描述。曲线的紧密和结构描述可以采用近似方法。一种方法是把曲线展开为正交级数；另一种是把曲线分段为一些比较简单的曲线。线性分割分段近似是最常见的，而样条函数（对多项式分段，在各连接点规定连续条件）具有普遍意义。（3）曲线形状分析量度法。把一些与某曲线的分析近似法有关的系数用来表示该曲线形状的特征。不同形状的曲线具有不同的系数。不过，随着比例尺、旋转和遮断情况的不同，这些系数可能变化很大。因此，这种分析量度法只适用于曲线数目较少及预期变化较小的情况。2、面积形状的描述与量度采用图形内部不在边界上的点来描述图形，比较健全，因为比较小的面积变化能引起大得多的边界变化。（1）简单形状的量度。由平面图形的面积和周边来粗略量度其形状面积X（周长F是个与图形尺寸、位置和方向无关的量度不变式。把一个图形的最小约束矩形定义为一个完全包围该图形的矩形，而且此矩形不会被任何其它的这类矩形所包围，见图10.10。一种改进的对图形形状的近似量度是由它的凸缘进行的。把凸缘定义为包围已知图形的最小凸出图形。原图形则由凸缘形状及图中凹面或凹陷的数目和形状来描述，见图10.Ilo图10.10最小约束矩形图10.11图形的凸缘与凹陷（2）面积分析量度法。如同曲线描述一样，借助于某些基本函数（如二维傅里叶级数）对图形展开或近似而得到的系数，可用于对图形形状进行分析量度。对于一些基本函数，有可能组合这些系数以获得一个对比例尺、位置和方向的不变式。2三维物体的形状描述三维物体的形状可由物体的外表面或这些外表面所包络的容体来描述（可把洞孔描述为负容积）。三维物体描述特别困难之处在于，三维表面或容积需要二维图象来推断，尤其是对不可见表面的推断。下面我们将着重分析由二维图象进行容积描述问题。1、物体形状的广义锥体表示可用广义柱体（有时称为广义锥体）来表示物体的形状。由于单一的广义锥体能够描述任意容积，因此，复杂的形状能够自然地分割为若干个比较简单的广义锥体来描述。图10.13所示的螺丝起子可由4个广义锥体来描述。其中，一个对应于螺丝刀片，为一变化的矩形截面；另一个对应于螺丝刀杆，具有圆截面；还有2个广义锥体在手把上。简化广义锥体的准则应是其横截面的形状、尺寸或轴线方向不发生陡削变化。图10.13螺丝起子的广义锥体表示2、广义锥体描述的计算广义锥体表示不是变换表示，对于同一输入可能有许多可供选择的描述。需要从中选择一种或多种最好的描述。（1）拟合表面数据。已知可见表面的三维位置以及对轴线和横截面形状的约束，就能拟合出最佳广义锥体。对于已知形状的横截面，可能求得一个简单的迭代解答。考虑一个正圆柱体。起初，该圆柱体的轴线方向和横截面都是未知的。任选一个方向之后，就能够对可见表面拟合出椭圆横断面。通过这些横截面矩心的某轴线，并不需要与该轴线垂直。接着，能够作出垂直于该轴的横截面。重复此过程，直至只观察到很小的横截面变化为止。对于正圆柱体和正圆锥体，这个过程收敛得很快。对于任意形状的物体，其收敛情况是不确定的，这时，要采用这种拟合技术，需要假设横截面由椭圆所近似。（2）采用物体边界。二维锥面能够由物体的边界来计算。如果二维轮廓是三维物体的投影，那么被计算的锥面就是所求的三维锥体的投影。3物体形状识别方法物体或者由几个物体组成的构件，可由比较它们的描述及存储在计算机内的模型描述来识别。这些模型可能由下列方法获取：存储预先遇到的物体的机器描述，直接学习视图数据序列，或者只是由操作人员提供。如果物体的描述是一张特性清单，即特性矢量，那么能够采用一般的数学模式识别技术来识别。对于结构性描述，需要采用比较复杂的匹配技术。此外，不要求用大量的内存把一个描述与每一个存储模型进行匹配试验，没有完全匹配而要选择一个合适的子集，就需要进行检索。1、图匹配法(GraPhmatching)结构性描述可视为图或网络。我们对评价两幅图的相似性感兴趣。下面介绍一些有关相似性的量度。令某幅图G：N,P,R定义为由结点集合N(表示物体的部件)、这些结合特性的集合P以及结点(节点)间关系的集合R组成的。已知两幅图G：(N,P,R>和G'：N'，P',R'),如果当且仅当P(n)与P'(n)对某一给定的相似性量度相似(即节点n的特性与节点晨的特性相似)时，就说形成一对配对(assignment)(n,n,)。如果有两对配对(n,nJ)和(m,n2,),对于R中的r和R'中的J的所有关系使得r(m,r)=r,(n2,n2,)成立，那么就说这两对配对是兼容的。其中，我们假设关系是二元的。如果两幅图G和G'的节点具有一对一的配对，使得所有配对相互兼容，那么就称这两幅图是同构的(isomorphic)。其中，如果(n,n')为一配对，那么仍然要求P(n)=P'(nz)o如果G的子图与G'的子图同构，那么就称图G与G'为亚同构的(subisomorphic)02、松弛标示法(RelaXatiOnlabeling)把标示问题定义为一个标示集合与一个节点(或单元)集合的配对，使得标示配对与给定约束相一致。这种标示法有许多应用，而且包含了图匹配问题。这时，标示是其它图的节点。令N为被标示节点的集合，L为可标示的集合。对于每个n”想要指定一个标示集合L1,使得Li为L的一个子集，而且这些标示与给定约束相容。对于不含糊的情况，每个集合Li只包含一个元。最简单的约束是一元的，限制标示只可能赋予某个确定的节点，而不考虑网络中的其它节点。二元约束规定一对节点的标示之间的关系。对于节点A的一个标示集合L,可能与节点内的一个标示集合Lj相容，如果Li的每个标示至少与Lj的一个标示相容的话。这种相容性称为弧相容性(arcconsistency)0一般说来，约束是n元的，而且弧相容性可能并不导致全局相容性(globalconsistency)0图10.44给出一个例子，其一元约束为：要对每个节点标示为红色或绿色,而且要求相邻点为不同的颜色。每当对一个节点指定红色或绿色之后，我们能够对其相邻节点指定一个相容的标示，但是不能使这3个节点同时满足全局约束。一个更大的约束是路径相容性(Pathconsistency)o两个节点a和r其标示为Ik和L)是路径一致的，如果网络内存在一条从m至内的路径，对于此路径上的每个节点不存在标示集合，而对于两端点同时与标示Ik和L相一致(用二元法)。图10.14的网络不是距径相容的。只考虑弧相容性，因为它对减少可供选择的方案往往是有用的。(红.»)图10.14弧一致但全局不一致的标示3、多层匹配法(MUltiIeVelmatching)图匹配和景物松驰标示技术是普遍的。不过，它们不能提供对相似和差异的满意描述。采用数字权，结合非相关特性(如颜色和尺寸等)可能没有多大意义。一个可供替代的方案是多层匹配法。对两种描述进行多层匹配的结果本身就是一种有关它们相似和差异的描述。如果由两个模型匹配求出同样的差异，那么可能需要对景物重新进行检查，以找出更精细的细节。已有一些采用这种方法来识别物体的例子。在某些情况下，两个模型可能具有类似的连通性。这时，可由各个单独部件的特性来对模型加以区别。一般上，需要比较详细的分析。当模型数较多时，对每个模型进行匹配是不适宜的，而且对内存的检索很可能只需要检索少数几个模型即可。可以采用诸如观察者方位以及环境中期望物体的知识等关系来检索。一个检索过程应当能够适应因观察条件不同而引起的物体描述变化以及由描述过程本身引起的可变性。描述的可变性可由检索观察过的描述以及根据期望变化干涉这些描述来调整。