机器视觉人工智能及其应用

1、第九章第九章 机器视觉机器视觉人工智能及其应用 对人类感觉信息的理解与处理是人工智能研究和应用又一重要领域。人类的这些感觉信息是多种多样的,包括视觉、听觉、力觉、触觉、嗅觉、味觉、接近感和临场感(telexistence或telepresence)以及情感等。其中,对视觉和力觉的研究最为重要,且均已进入实用阶段。对触觉和听觉的研究也已获得显著进展。不过,对嗅觉,尤其是味觉的研究尚未有重大突破。至于对人工情感的研究,仍停留在科学幻想阶段。 除了对各种单一的传感信息进行研究外,近年来又出现了对多种传感信息的集成与融合(integration and fusion)研究；它利用各种传感器性能上的差异

2、性与互补性,融合不同传感器的信息源并加以综合分析,以得到正确理解的、稳定可靠的周围环境信息,使系统具有容错性,提高系统的信息处理速度,保证决策的正确性和准确性。联为联为- -稻草人自动化稻草人自动化联为联为- -稻草人自动化稻草人自动化 视觉是人类最重要的感觉能力之一。视觉数据是人的最复杂和最有用的感觉输入信息。人眼能感觉颜色,因为它具有全色能力。人眼能感觉运动,因为视网能提供所出现事物的实际响应。 当代科学技术能否用机器来完全解释、模拟、复现和处理人的视觉呢？作为一种感觉输入数据,人们已能以有限的但是比较重要的方法重现视觉信息。机器视觉涉及对相似视觉数据的解释。接至计算机的视觉传感器感受到图

3、像的明暗信号,并把这些信号变换为可供处理的形式。把视觉传感器装在机器人的机械手上,只要物体与其背景的对比度明显不同,而且不相互接触或重叠,那么就能够让机器人通过图像轮廓来识别物体。这种视觉系统已获得应用。 由机器来感觉环境并执行要完成的任务具有明显的优点,并获得多方面的应用。除了用于由机器人进行装配和检验作业外,还可用于星际空间搜索、医用X-射线自动鉴别、地球资源遥感监视和各种军事应用等。这种视觉机器有助于执行许多日常单调的甚至对人危险的任务；如果没有某种感觉能力,那么这些任务是很难甚至无法完成的。 大多数工业装配任务,包括一些看起来很简单的任务(如把车辆装在汽车上),一般都需要采用视觉技术。

4、在恶劣环境下(例如,在太空和水下)或在加工有害材料时,一般都需要机器视觉。对于许多应用,视觉系统必须是自主的。 计算机视觉(即机器视觉)就是由图像数据来产生视野环境内有用符号描述的过程。所开发的计算机视觉的特点与过程往往与其应用场合有关。 机器视觉包含众多的研究课题,如视觉可计算性原理、图像的形成和获取、图像预处理、边缘检测与分割、特征抽取与匹配、区域生成与分割、形状分析与识别、运动视觉、主动视觉、三维视觉以及视觉知识的表示和视觉系统的控制策略等。机器视觉已发展成为一门独立的学科。因此,对机器视觉的系统、全面和深入的研究,已不是本书的任务。本章仅对机器视觉进行导论性介绍,仅限于讨论一些比较基本

5、的问题,这些问题可能与机器人视觉有比较直接的关系。联为联为- -稻草人自动化稻草人自动化9.1图像的理解与分析 对图像的理解和解释是计算机视觉的研究中心,也是人工智能研究的焦点之一。可以把视觉理解为一个从外部世界图像产生对观察者有用的描述过程。这些描述依次由许多不同的记录了的景物某一方向的固定表达组成。因此,选择视觉系统的表达方法,对于视觉系统是至关重要的。联为联为- -稻草人自动化稻草人自动化联为联为- -稻草人自动化稻草人自动化9.1.1视觉信息的表达方法 根据马氏(Marr)提出的假设,视觉信息处理过程包括三个主要表达层次,即初始简图、二维半简图和三维简图,如图9.1所示。联为联为- -

6、稻草人自动化稻草人自动化1.初始简图初始简图 亮度图像含有两种重要信息：图像的亮度变化和局部几何特征。初始简图是一种本原表达法,它能完全而又清楚地表示上述信息。初始简图所包含的信息大部分集中在与实际边缘以及边缘终止点有关的剧烈灰度变化上。对于每一边缘亮度变化,在初始简图上都有对应的描述。这些描述包括：与边缘有关的亮度变化率、总的亮度变化、边缘长度、曲率和方向等。粗略地说,初始简图是以勾画草图的形式来表示图像中的亮度变化的。图9.2即为初始简图的一个例子,说明它的辉亮边界描述和亮度变化。如果所用边缘检测方法所产生的是短线段,那么,就要利用聚集过程把那些相容的描述线段连接起来。 根据马氏理论产生初

7、始简图,并不需要关于特定物体的有关知识。也就是说,马氏建议试图描述图像具有的属性,而对景物可能与什么事物有关则不作任何假设。联为联为- -稻草人自动化稻草人自动化2.二维半简图二维半简图 要对图像进行更深入的描述,需要知道其内在特性。这些内在特性包括表面方向、从观察者至被观察表面的距离、反射和入射光照表面的纹理以及材料特性等。二维半简图(2D sketch)包含景物表面的信息,可以把它看做某些内在特性的混合信息。二维半简图清楚地表示物体表面方向的信息。物体表面法线从物体内部穿出来,使物体好像穿刺满了针一样。有时,这种二维半简图又称为指针图,或简称针图(needle diagram)。此外,二维

8、半简图还包含从观察者到图像各部分的距离。图9.3表示出二维半简图的表面方向信息。图中,指针的箭头表示垂直于表面的矢量,即为表面法线。 在初始简图和二维半简图中,信息往往是以与观察者有关的坐标系表示的。因此,这种表达法称为观察者中心表达法。联为联为- -稻草人自动化稻草人自动化3.三维模型三维模型 三维表达法能够完全而又清晰地表示有关物体形状的信息，其方法之一即为广义柱体。广义柱体的概念十分重要，而其表示方法又十分简单，如图9.4所示。图中，柱体的横截面沿轴线的投影不变。一个普通圆柱可看做是一个圆周沿其中心垂线移动而成；一个楔形物是一个三角形沿其中垂线移动而得的，等等。一般地说，一个广义柱体是二

9、维轮廓图沿其轴线移动而成的。在移动过程中，轮廓与轴线之间保持固定的角度不变。轮廓可为任何形状，而且在移动过程中其尺寸可能是变化的，其轴线也不一定是垂线或直线，如图9.5所示。联为联为- -稻草人自动化稻草人自动化 复杂物体往往是由一些广义柱体连接而成的。一般地,一个中央主柱体被一些凹槽或凸面所修正。这样,复杂物体就可以由一些基本图形构成。联为联为- -稻草人自动化稻草人自动化9.1.2 边缘距离的计算1.图像辉亮边缘的平均与差分图像辉亮边缘的平均与差分 图9.6表示出两平面间边缘处的亮度变化图。其中,图9.6(a)为理想边缘亮度变化；这时,亮度在边缘处由一值跃变为另一值。图9.6(b)则表示实

10、际边缘亮度变化；这时亮度的变化比较模糊,不存在明显的阶跃变化,因而也就很难确定边缘的位置。这种情况是与图像输入装置不可能产生足够清晰的图像有关的。因为在获得图像时,会遇到传感器的亮度灵敏性波动、图像坐标信息误差、电子噪声、光源扰动以及无力接收大范围变化的亮度信息等。另一个原因是图像本身很复杂,其实际边缘并不是陡峭的,而是逐步过渡的；还可能存在相互照明效应、意外划痕和灰尘等。联为联为- -稻草人自动化稻草人自动化 一种处理噪声边缘的方法包括下列4个步骤:(1)从图像建立平均亮度阵列。取局部亮度的平均值能够减少噪声的影响。下述公式说明需要进行的计算。为简化起见,所列公式是用于二维计算的一维形式：

11、式中,Ii为i点的图像亮度,而Ai为i点的平均亮度。(2)从平均亮度阵列产生平均一阶差分阵列。取右邻差分(Ai+1 -Ai)与左邻差分(Ai-Ai-1)的平联为联为- -稻草人自动化稻草人自动化 均值,这相当于把i的左邻和右邻相平均。令Fi为平均亮度Ai的一次平均差分,则有： 上式与一次微分的有限差分近似。(3)从一次平均差分阵列建立二次平均差分阵列。 为此,求一次差分的平均值。令Si为平均亮度的平均二次差分,则(4)据所得阵列,记下峰点、陡变斜率和过零点,以寻求边缘信号的集合。 平均过程是把理想的台阶曲线和被噪声模糊的台阶曲线都变换为平滑的台阶曲线；一次差分过程把平滑了的台阶曲线变换为凸缘形

12、曲线；二次差分过程又把凸缘形曲线变换为S形曲线,如正弦曲线一样变化。图9.7(b)至(d)表示出上述边缘处理过程,而图9.7(a)则表示理想的边缘亮度分布。联为联为- -稻草人自动化稻草人自动化 平均和差分作用能够被综合到一个综合平均过程中去,并通过点扩散函数由输入点特性来确定输出点特性。点扩散函数表示单个孤立点亮度不为。的点在图像中如何扩散其影响。当按输入来确定输出特性时,称输出被点扩散函数所滤波。 在实际图像中所用到的点扩散函数必须表示比较多的点的组合,而且点扩散函数必须是二维的。这些计算论证的概要是：联为联为- -稻草人自动化稻草人自动化(1)必须用衰减高频点扩散函数对噪声进行滤波处理。

13、选用二维高斯函数要比平均函数好得多。(2)应当用二次差分来对边缘进行定位。高斯滤波器对噪声的抑制作用能够抵消差分过程对噪声增强的影响。(3)用二维高斯滤波后,进行的二次二维差分相当于以形状像墨西哥草帽或宽边草帽的单个点扩散函数来滤波。墨西哥草帽形状是一维情况下尖峰和穿越(peak-and-through)形状在二维情况下的相似物。联为联为- -稻草人自动化稻草人自动化(4)一个窄的正高斯点扩散函数加上一个宽的负高斯点扩散函数,能够足够精确地表示出先高斯滤波后差分所对应的二维墨西哥草帽状的点扩散函数,如图9.8所示。(5)用二维高斯点扩散函数来滤波相当于连续以两个一维高斯点扩散函数(一个为垂直方

14、向,另一为水平方向)来滤波。这意味着,高斯滤波是快速的。因此,墨西哥草帽形滤波也可以是快速的。联为联为- -稻草人自动化稻草人自动化2.灵长目动物视网膜特性灵长目动物视网膜特性 墨西哥草帽形滤波器与一些了解灵长目动物早期视觉的实验相一致。关键实验如图9.9所示。被试动物注视各种从白色背景前移过的色质(stimuli)。这些色质包括一条窄的黑带、一条宽的黑带以及一个单白一黑边缘。记录探针测定各种神经反应。把此神经反应与据墨西哥形草帽滤波器作出的预计进行比较。联为联为- -稻草人自动化稻草人自动化 图9.10给出比较结果。在图9.10中,(a)表示3个自左向右移动的色质的亮度分布曲线;(b)表示以

15、适当宽度的墨西哥草帽形滤波器对所给出的亮度分布进行滤波的结果；(c)为所谓X神经节细胞上记录的实验数据。比较图9.10(b)和(c)可见,两者极其相似。这表明灵长目动物的视网膜确实进行了某些与墨西哥草帽形滤波器十分相似的处理工作。如果对墨西哥草帽形滤波器稍加修改,就能够改善相似性,如图9.10(d)所示。联为联为- -稻草人自动化稻草人自动化 比较结果得到的高度相似性,使我们有足够的根据作出下列假设：(1)灵长目动物视网膜所进行的滤波处理功能在运算上与由墨西哥草帽形点扩散函数所进行的滤波相似。(2)存在有两种视网膜细胞,一种用于传输滤波图像的正向部分,另一种传递滤波匾像的负向部分。(3)对于每

16、种细胞,墨西哥草帽形滤波器是通过激发与禁止这两种操作的组合来实现的。这个滤波器等价于两个以二维高斯滤波器滤波所得图像的差。联为联为- -稻草人自动化稻草人自动化3.物体距离的确定物体距离的确定 立体视觉由两眼得到的信息来确定距离。由于两眼间的距离是已知的,因而一旦在两眼所得图像中找到了物体的位置,就容易求得观察者到此物体的距离。 图9.11表示两眼立体视觉中的相对位置关系。图中,P点为一物体。两个透镜的轴线是平行的。f为两透镜与图像平面的距离,即为其焦距。b为两透镜轴线在基线上的距离,即为两眼的距离。l和r分别为P点与左、右透镜轴的距离。和分别为左右图像与其相应透镜轴线的距离。 从两相似三角形

17、,我们可以得下列关系式：联为联为- -稻草人自动化稻草人自动化 已知b=L+r,代入上式,可求得观察者双眼至物体的距离： 由于双眼距离b为已知,焦距f也是确定的,因此,一个物体与双眼的距离和(+)反比。 (+)为该点的一幅图像点位置相对于另一幅图像点位置的位移,称为视(disparity)。 立体视觉的实际问题就是根据左右两图像找到相应的物体,以便能够测量视差。有许多不同的立体视觉系统能在不同程度上成功地寻找出相应的物体。联为联为- -稻草人自动化稻草人自动化9.1.3表面方向的计算 研究由图像明暗度(shading)来计算物体表面方向信息的过程,其目的在于更多翅解为产生二维半简图信息所需要的

18、计算。1.反射图体现光照约束反射图体现光照约束 从物体表面反射的光量取决于表面材料以及光源、观察者与表面法线之间的相对角度。这些角度如图9.12所示。其中, i为表面法线与光源方向之间的入射角；e为表雇线和观察者之间的出射角;g为观察者方向与光源方向间的相位角。 把从所有可能位置观察到的亮度都相同的表面定义为朗伯表面(Lamber surface),它的亮度只由光源的方向决定。这一关系遵循下列公式： Ecosi (9.5) 式中,E为被观察亮度; 为表面反射率(对于特定的表面材料, 为一常数)；i为入射角。联为联为- -稻草人自动化稻草人自动化联为联为- -稻草人自动化稻草人自动化 为了认识朗

19、伯表面如何反射光,我们进行如下实验：用朗伯颜料涂敷一个球面,并让它在一点光源附近移动。对于每一光源位置,观察并记下亮度与表面法线的关系,画出其等亮度线。图9.13给出三个不同光源方向情况下的等亮度线。其中,对于图9.13(a),光线正好从观察者背后照射,其等亮度线为一些同心圆。最亮点的亮度为, 此点的法线正好指向观察者。这时,cos i=1。离开球面的边界方向,亮度逐渐变暗,在边界处的亮度变为0,因为这时cosi=0。对于图9.13(b),光源方向与观察者方向间的夹角为450,这时,最亮点的亮度仍为,但它已不是表面法线正对观察者的点,而是表面法线指向光源的点。亮度为0的线是球面上的圆周,但不是

20、球面的二维图像中的圆周。有时,称亮度为0的线为阴影线(shadow line),或明暗界线(terminator)。对于图9.13(c),光线是从右面照射的,而且观察者方向与光源方向呈直角交角。这时,最亮点是在球面边缘上,而阴影线则为直线。联为联为- -稻草人自动化稻草人自动化联为联为- -稻草人自动化稻草人自动化 虽然图9.13可用来说明表面方向与亮度的关系,不过它是在空间曲面上的表示方法,因而不便于实际使用。实际中使用的方法是把等亮度线投影到平面上去。投影后的等亮度线构成反射图(reflectance map)。 有多种绘制反射图的方法,其中之一是把等亮度线投影到梯度空间平面。梯度空间平面

21、是一个和视线垂直的切面。投影的方法是把表面各点的法线向外延长,直至与梯度空间平面相交为止。另一种有用的投影方法也是把球面上的点投影到球面的切面上去(切面的坐标轴为F和G),其投影方法是：从球面上与观察者相对的点出发,与要投影的点连成直线,再与切面相交。联为联为- -稻草人自动化稻草人自动化2.表面方向的确定表面方向的确定 上面研究了利用表面方向预测表面的亮度。下面研究相反的问题,即从感测到的亮度来计算表面各方向参数f和g。 由f和g来确定表面方向,初看起来似乎是不可能的。因为一小块表面只能确定切面FG上的一条曲线,而不是单一的点。但是,事实上这样做却是可能的,因为大部分表面是平滑的,在不同深度

22、和方向上只出现有少数不连续的情况。因此,可以利用下面两个约束：(1)亮度。由f和g所确定的表面方向应与表面亮度所要求的表面方向无多大不同。(2)表面平滑度。一点的表面方向应与邻近各点的表面方向无多大变化。 对于每个点,计算的f和g值应兼顾上述两个约束计算所得的值。图9.14中,根据亮度,要求特定点的f和g值应落在等亮度线上,而据表面平滑度则要求f和g值接近相邻点f和g的平均值。 从直观上看,在平均点与等亮度线之间选择某个点是有道理的。不过,仍然存在两个间题,即这个所选择的点在哪里,以及如何知道相邻点的平均值。下面是这两个问题的解答。联为联为- -稻草人自动化稻草人自动化(1)折中通过平均点并垂

23、直于等亮度线的直线上的某个点,作为所选择的点。(2)首先假设所有未知的f和g均为零值,然后用在初始值的平均点与等亮度线之间求得的折中方法,为每一点计算新的f和g值,再重复利用更新了的值计算f和g值,直至其值变化足够小为止。 为检查上述计算过程是否可行,需要一些耗时的和可选择的计算。先研究两种误差平滑性偏差e1和预计亮度偏差e2的测量。联为联为- -稻草人自动化稻草人自动化联为联为- -稻草人自动化稻草人自动化 总误差为e=e1+e2,其中为一常数,用于调整两偏差以保持一定的平衡。要求得使总偏差为最小的fi,j和gi,j,我们对fi,j和gi,j分别取微分,并令其微分值等于0。这样可得下式： 根

24、据下列第(n+1)个迭代项(fi,jn+1,gi,jn+1)与第n个迭代项(fi,jn,gi,jn)的相关规则,能够求得这些方程式的解答如下：式中, fi,j0=0,gi,j0=0联为联为- -稻草人自动化稻草人自动化 这些规则称为松弛公式。应用这些公式相当于从原来的估计值出发,沿着垂直于等亮度线方向,朝等亮度线移动一步,以改善对f和g的估计。每步移动大小正比于所观察到的亮度与据当前f和9预测到的亮度之差,也与误差平衡参数成正比。 应用松弛公式的过程,通常称为松弛过程。 综上所述,可得计算表面方向的松弛算法如下：(1)对所有非边界点,令f=0和g=0。对所有边界点,令f和g规定一个长度为2的垂

25、直于边界的矢量。称输入阵列为当前阵列。(2)进行下列步骤(直到所有的值变化得足够慢为止)： (a)对当前阵列中的每个点： i)如果是边界点,则不做任何事； ii)如果是非边界点,那么用松弛公式计算新的f和g值。 (b)把所得新阵列称为当前阵列。联为联为- -稻草人自动化稻草人自动化9.2积木世界的景物分析 景物分析是研究视觉的重要问题。可见的景物由传感器编码,并被表示为一个灰度数值矩阵,再由检测器处理。检测器搜索图像的主要成分,如线段、简单曲线和角度等。对这些成分进行处理,以便利用知识来推断有关景物的三维特征信息。其最终目标在于利用模型来表示该景物。联为联为- -稻草人自动化稻草人自动化9.2

26、.1积木世界景物的线条标示方法 积木世界视觉研究的主要目标是理解从一堆玩具积木的图像得到对于景物的描述。所谓描述就是把出现在图像中的大量的线条聚集成代表景物中各个积木的线条组。研究积木世界景物时,输入的图像可以是积木景物的照片、电视摄影图像或是线条图。如果是属于前两种,那么第一步就是从图像得到线条图。这属于马氏初始简图的范围,但没有那样复杂,只是用了边缘检测算子。在以下的讨论中,我们都假设已经得到了积木世界的线条图的情况。联为联为- -稻草人自动化稻草人自动化 积木世界景物分析的研究对象比较狭窄,并且是有意地进行了简化,但仍不失为合适的计算机视觉研究的初步目标。在这个领域中的研究已经取得了一些

27、有实用意义的成果。积木世界可以推广为类似工业零件的多面体,而理解简单的三维工程图是建立有视觉的工业机器人装配系统的第一步。 对积木世界研究的最早成果是罗伯茨(Roberts)在1965年发表的论文。罗伯茨希望以图9.15中所示的多面体基元来解释图9.16(a)中的线条图。景物中的一个简单的物体可以看成是基元经、过变换以后得到的一个实例。变换可以包括沿三个轴的比例变化、转化和旋转。组合的多面体可以看成是由若干个简单的多面体猫合而成。联为联为- -稻草人自动化稻草人自动化 要理解景物的局部,首先要确定图像中有哪些基元,基元要经过什么变换才能出现在景物中现在的位置上。识别基元是通过把线条图和模型基元

28、的拓扑特性(面、线、顶点的结构)进行匹配来实现的。先是试验性的匹配,然后由一个量度过程来确定这个转换是否是允许的。当在景物中识别出转换的基元时,这个基元就被想象成已被切开并被移走了,新的可看见的线条就填进来,又开始对新的景物进行分析。罗伯茨的算法虽然不是很可靠,但这是一项开拓性的工作,标志着积木世界景物分析研究工作的开始。联为联为- -稻草人自动化稻草人自动化联为联为- -稻草人自动化稻草人自动化 古兹门(Guzmen)在1969年提出的程序可以对一幅相当复杂的线条图(图9.16 (b)进行分析。线条把图分成若干个多面体区域。程序的目标是把这些区域聚集成组,每一组相应于一个多面体“块”。任何无

29、多义性的、合理的解释都是可以接受的。基本的概念仍然是从景物积累局部证据；然后,根据这些证据聚集成多面体。古兹门的算法以连接两个属于同一物体的两个区域的链作为证据。链围绕顶点排列。顶点可分成图9.17所示的类型。物体和背景之间不考虑链。使用相当复杂的规则,根据区域和链,利用聚类方法对景物进行解释。链还包括不允许某9个相邻区域属于同一物体的禁止链。古兹门的算法对一般的景物可以工作得良好,但由于存在过多的特殊情况和例外,容易引起混乱。总之,在相当广的应用范围里这种算法虽然不十分精巧,但还是可以胜任的。 联为联为- -稻草人自动化稻草人自动化 赫夫曼(Huffmen)与克洛斯(Clows)独立地研究了

30、与古兹门相似的景物。他们希望对景物的解释不只是分析哪些区是由单个物体产生的,而且希望分析线条。图9.18所示为一个悬在空中的L形实心体。标有“”标志的是凸面边缘,标有“”标志的是凹面边缘。箭头标志“”表示物体遮住了后面的表面。当沿着箭头方向看时,引起遮挡的实体是在右面,被遮住的表面是在左面。如果立方体悬在空中,那么最下面的线可标为“”而不是“”(赫夫曼并没有考虑阴影线,也没有考虑断裂线)。按这样的方法,分析的目标就变成对线条图中的每一条线确定它是由景物中的什么类型边缘产生的。换句话说,现在所研究的任务是标示线条。联为联为- -稻草人自动化稻草人自动化 虽然每条线单从其本身来考虑有三种可能性：凸

31、面边缘、凹面边缘以及遮挡边缘,但对一个由线条相交形成的接点来说,并不是所有这些可能性组合都可以解释为实际可能实现的边缘连接。例如,对三面相交的顶点来说,在64种线条组合中只有图9.28所示的18种(T形接点包括在内)是可实现的。这样,就可能对每种接点类型规定可允许的接点。把这些允许的接点收集在一起就可形成“接点字典”。然后,可利用接点字典来限制线条组合的可能性。另外,因为线条在其两端都代表同一种边缘,所以不难看到,从原理上来说算法可以利用这种一致性的约束来删除不可能的标示。 华尔兹(Waltz)发展和完善了古兹门和克洛斯的算法。华尔兹的算法对光照以及阴影条件几乎不作限制。可以分析如图9.16(

32、c)所示线条图。此图中包含有阴影线和断裂线。华尔兹的算法可把图中的每一条线都解释为”种可能的边缘中的一种。联为联为- -稻草人自动化稻草人自动化 在分析线条图时(如图9.16 (c),一个主要问题是确定哪些是分割物体的边界线。从图9.16(c)可以看到边界线、凸面线、凹面线、阴影线和断裂线只能以很少几种方式组合在接点上,而这种对接点组合的限制,称为符号约束或约束,又决定了对线条图中每一条线的合理的物理解释。一旦知道了对线条的正确解释就不难利用已知的边界线把线条图分成各个物体。华尔兹方法的基本过程是约束传播。约束传播过程通过局部计算达到全局的一致性。它也是一种推理过程。 以下介绍华尔兹的线条标示

33、方法,并且主要研究只具有三面顶点的物体。先从比较简单的无阴影和无断裂线的情况开始,然后,扩展到有阴影和有断裂线的情况。联为联为- -稻草人自动化稻草人自动化9.2.2无断裂和阴影时三面顶点的标示方法1.线条和接点的分类线条和接点的分类 下面先研究无断裂的三面顶点,并且设想合适的光照条件,避免了所有的阴影。在这样的环境下,图中的所有线条代表了各种天然产生的边缘。这些线条的简单分类如下： 边界线 所有线条 凸面线 内边线 凹面线 首先把线条分成边界线和内边线。边界线分割属于不同物体的区域,而内边线分割属于同一物体的区域。内边线或者与凸面边缘有关,或者与凹面边缘有关。联为联为- -稻草人自动化稻草人

34、自动化 为便于以符号表示,线条的解释可以在图上以线条标示来辨认。因为经常用到这些标示,所以最好能熟记脑中。 凸面线带有加标志“”； 凹面线带有减标志“一”； 边界线带有箭头标志“”。 围绕接点的线条标示的组合称为接点标示。将可看到天然的约束限制了在实际上可以实现的接点标示的数目。标在边界线上的箭头标示的方向决定于边界线的哪一边相应于造成这条边界线的物体的面。设想沿边界线行进,并保持产生此边界线的物体在你的右面。这样,行进的方向就是箭头的方向。 很容易以一种反映我们对图9.18上所画的L形实心体的直觉的方法来标志图上的每一根线。通过标志这张图说明,为了解释这些线条,我们应用了对实际情况的理解。现

35、在所要探求的关键概念是改变原来过程,转而利用线条解释的知识以达到对实际的可实现性的理解。为了要这样做,必须理解现实世界所强加的固有的约束。联为联为- -稻草人自动化稻草人自动化 现实世界中的顶点造成线条图中的接点。可以根据相交的线条数目和线条之间角度的大小对这些接点进行分类。在图9.19中对每种接点分配了一个助记名。在下述简单假设下,可以把接点种类归纳成叉(fork)、箭(arrow) , L和T形等几种：(1)有限的线条解释,即假设没有阴影或断裂。如果顶点是三面顶点并且无阴影和断裂 线,就只包括叉、箭,L和T4种。(2)三个面组成的顶点,即所有的顶点都正好是由物体的三个面相交而成。(3)通用

36、的位置。观察点应选择好,使其不因眼睛的微小移动而造成接点的变化。 我们只暂时实行上述假设,以后将会撤销这些假设。这些假设的用途是减少可能的接点的数目,从而减少可能的对接点周围线条的解释。联为联为- -稻草人自动化稻草人自动化 三面顶点的假设意味着空间所有的顶点都严格地是三个面相交,如同立方体的顶点那样。图9.20中的每个物体都仅仅涉及到三面顶点。请注意,在图上只出现三种接点：叉形、箭形和L形。因为一个物体可以在另一个物体的前面,所以T形接点也可能出现。但因为仅限于研究三面顶点,所以先避免山峰、Psi,K和X形等顶点。 因为可有4种方式标志任何给定的线条,所以就必然有4“一16种方式标志一个L形

37、接点。类似地,必然有43 =64种方式标志任何特定的叉、箭和T形接点,这就决定了可能出现在一个线条图中的接点标志数目的上界是208种,但事实上只有其中的18种是可能出现的。例如在我们所作的假设之下,在现实的多面体的线条图中要找到图9.21中所示的接点标志是不可能的。 联为联为- -稻草人自动化稻草人自动化 下一项工作是把可能出现的接点标示收集在一起,L、叉、T和箭形接点的可能接点标志数分别为6,5,4和3。知道了这些可能的接点标示,分析线条图就像是玩拼板游戏。联为联为- -稻草人自动化稻草人自动化2.标志三面接点的方法标志三面接点的方法 为了对围绕接点的线条的标示方式进行分类,我们需要从每个可

38、能的方向来观察每种实际可能的三面顶点。这样做会遇到可供选择的方向过多的困难,为此把除了一般的观察位置以外的方向都排除在外,以减少可能出现的情况。假设在这一节的其余部分仅讨论只包含三面顶点的线条图。任何三面顶点的三个面规定了三个相交的平面,这三个相交的平面把空间分成8个间隔,如图9. 22所示。很明显,某个形成一个顶角的物体就占有上述8个间隔(或八分体)中的一个或几个。接点标志所说明的是物体如何占有八分体。可以通过以下两个步骤来构成完整的包含所有连接可能性的字典：先考虑所有的以物体来充满这8个八分体的方式；然后,从未被充满的八分体观察所得到的顶点。联为联为- -稻草人自动化稻草人自动化 当然,如

39、果没有一个八分体被充满,或者所有的八分体都被充满了,那么说明不存在顶点,从而没什么要进一步考虑的。但如果8个八分体中的7个被充满了,如图9.23(a)所示,显然,7个八分体的情况确认了一个叉形接点标志。在此接点标志中,有关的三根线条中的每一根都标有负号。这里要说明的是,在此线条图中我们惟一感兴趣的接点是在中心的接点。图中周围的线条只是为了在视觉上帮助理解这7个被充满的八分体如何形成一个接点。再则,因为有7个八分体被充满,所以只余下一个八分体,从这个八分体来观察这个顶点,不论在八分体内的什么位置,所看到的这个接点的类型都是叉形。幸运的是,在八分体内所观察的接点类型不变这个性质是普遍的。当观察的位

40、置在八分体内移动时,虽然线条之间的角度有显著的变化,但接点的类型并不变。联为联为- -稻草人自动化稻草人自动化 至今,在可能的接点标志的字典中只有一项：叉形。如只有一个八分体被充满,就可得到一个新项。图9.23(b)中所示为这个新项。与上一种情况相似,只研究中心的接点,其周围的线条只是为了帮助理解这个被充满的八分体在空间的位置。因为仅有一个八分体被充满,所以可以从其余7个八分体来观察这个顶点。而至今只有1个从与这个八分体对角相对的八分体观察所得到的接点标志。联为联为- -稻草人自动化稻草人自动化 下面来研究从其余6个八分体观察的情况。图9.24中所画的小人占了其中的3个位置。如图9.25所示,

41、对于剩下的3个八分体中的两个,把小人放入窗框中,并升高到这个立方体顶部所规定的平面以上。最后一个观察点由顶部的小人所规定。所有6个小人观察点只产生两种新的接点标志,因为其中三个产生一种箭形标志,另外三种产生一种L形。实际上,从所研究的情况是对称的就可以料想到这一点。联为联为- -稻草人自动化稻草人自动化 现在来研究有2个、4个或6个八分体被充满的情况。所有这些都仅限在当初的三面顶点的假设之下。例如,设有2个八分体被充满。如果这2个八分体是相邻的,那么,这2个八分体之间的边缘就是断裂线,这样在中心顶点就有4个物体面,所以这个顶点就不再是3面的。如这2个八分体不相邻,那么这2个八分体或者将在一条边

42、缘相交,或在一个公共点。无论上述哪一种方式,都会使中心顶点的面多于3个。相类似的论证可以把4个和6个八分体的情况也排除在外,只留下3个和5个八分体的情况需要考虑。 在3个八分体的情况下,如图9.26所示,从其余5个八分体中的每一个来观察都得到互不相同的接点标志。当然,从其中的一个八分体观察得到的是叉形,从另一个八分体观察得到的是箭形,从其余的三个八分体观察得到的是L形。所观察得到的L形中的每一个都是互不相同的。 图9.27所示为5个八分体被充满的情况。共有三种接点标志,其中的任何一种都不同于以前所看到的。联为联为- -稻草人自动化稻草人自动化联为联为- -稻草人自动化稻草人自动化 最后,因为没

43、有断裂,所以只有4种方式可用来标志T。所有这些T的标志都是部分遮挡的结果。这样使得标志接点的方式的总数达到18种。所有这些标志方式都收集在图9.28中,再要指出一点,即有三种标志的方式是旋转对称的。联为联为- -稻草人自动化稻草人自动化 以上列举了所有可能的组成三面顶点的方式,并且从所有可能的方向来观察每个这样的顶点。这18种接点标志就是所有可能的这些接点被标志的方式,任何不在所列的表中的标志,都找不到实际的三面顶点与之相对应。联为联为- -稻草人自动化稻草人自动化9.2.3有断裂和阴影时线条图的分析 到目前为止,我们都是在物体悬挂在背景前面的假设下分析线条图的。如果一个立方体是放在桌子上,那

44、么这个立方体的底线就表示凹面边缘,而不是边界。然而这样的解释不是惟一的,因为一个立方体也可能如图9.29所示,是贴在墙上的。如果没有附加的线条或假定,几种解释同样都可以接受。联为联为- -稻草人自动化稻草人自动化 如果引入阴影就可以解决这种不确定性。在图9.30中间的那个方块肯定是放在一个水平面上的,而左面和右面的方块虽然不熟悉,但看起来是垂直地贴着的。显然,扩展标志种类使其包括阴影标志加进了新的约束,并简化分析。 注意：注意：图9.30引入的阴影标志,如同边界标志那样,代表一个方向。阴影标志是一个指向阴影区域的小箭头。联为联为- -稻草人自动化稻草人自动化 这样,在标志字典中,已有6种标志,

45、其中边界和阴影各有两种,凸面和凹面边缘各有一种。用这组扩展了的标志来进行标示是简单的但却是乏味的工作。从已完成的例子说明,改善线条描述可使约束的数目增加,从而提高分析的速度。下面进一步研究是否有其他方法对线条的解释作进一步的分类。在介绍具体方法以前,有一个问题需要注意,即随着线标志集合的扩展,实际接点标志的集合将显著增加。将会有几千种合法的接点标志,而不是只有18种。因此不可能建立一个合法接点标志表以试图让模拟计算机利用这个表格来做些什么。我们不这样做,而是问：合法的标志数目相对于不合法的标志数如何增加。然后研究实验结果,以帮助回答关于扩展标志会带来什么改进和为什么能够得到这些改进的问题。下面

46、介绍两种对线条解释作进一步分类的方法。联为联为- -稻草人自动化稻草人自动化(1)对凹面标志进一步分类并引入断裂线标志对凹面标志进一步分类并引入断裂线标志 考虑到物体经常放在一起,所以,凹面标志可以分成三类,这三类表示有关物体的数目并可确定哪个物体是在前面的。设一条凹面边缘表示两个物体接触在一起的地方。然后想象把这两个物体稍为拉开一点。这样,这个凹面边缘就成为边界,其上标志指向两个可能方向中的一个,如图9.31(a)和9.31(b)所示。这两种可能性以一个由原来的负号标志和一个新的箭头标志组成的合成标志来表示。如果有三个物体相接触,同样可以利用一个合成标志表示如果物体稍微离开一些时可以看到什么

47、,如图9.31(c)所示。 断裂线也可以类似地处理：每一根断裂线被标以一个c和一个箭头,表示这两个有关的物体如何配合在一起。连同断裂线一起,我们有如图9.32所示的图表。现在一共有11种标志线条的方法。联为联为- -稻草人自动化稻草人自动化联为联为- -稻草人自动化稻草人自动化(2)用光照条件增加标志数量和严格约束用光照条件增加标志数量和严格约束 另一种改善线条描述的方法是结合单光源的光照条件。假设物体任何一个面的照明状态必定属于如图9.33所示的三种类型中的一种：一个面可能是被直接照明,或被另一个面所遮光,或因为背离光源而处于阴影区。这三种可能性可用符号来表示：工表示直接照明；S表示被另一物

48、体所遮光；SS表示因背离光源而处于阴影,也称为自遮光。联为联为- -稻草人自动化稻草人自动化 线条标志除了表示关于边缘类型的基本信息以外,还可以表示关于照明状态的知识。如果照明状态和线条解释可以自由组合,那么对上述11种线条解释中的每一种都可以有32=9种照明组合,这样可以造成总共99种可能性,但其中只有50种是可能实现的。例如,不存在下述这种组合,在这种组合下,阴影线的两边的面都是被照明的。类似地,任何类型的凹面边缘的两个边的照明状态不可能是不同的。因为这样将要求不可实现的重合情况,即要求.阴影线恰好投影在凹面边缘上。 概括起来,线条解释的每一次改进都促使一次线条标志的大扩展。开始时只考虑基

49、本的线条、边界线、内部的凹面线和凸面线。这些初始的线条种类扩展到包括阴影线。凹面线又分成4类以反映接触在一起的物体个数以及这些物体间相互遮挡的情况。这引入了断裂线并以和凹面线相类似的方式分成两类。最后,线条的信息和照明信息相结合。从最后这次扩展产生50种线条标志。联为联为- -稻草人自动化稻草人自动化 上述这些线条标志的变化扩大了实际的接点集。原来接点种类有叉形、箭形,L形和T形。因解除了三面顶点和一般的位置约束从而新增加有山峰Psi, K, X, Muti和Kk等形接点。下面讨论从增加这些接点类型得到了什么,以及从寻找和使用这些新接点标志可以得到什么结果的问题。 首先来研究可能的实际接点集和

50、无约束集的比较。 表9. 1所列为初始线条标志的情况。顶点类型可能组合成的接点数可实现的接点数比例 (%)L叉T箭16646464654337.57.86.24.7联为联为- -稻草人自动化稻草人自动化 上述比例数表示了严格的但并不过分的约束。但当线条种类扩大时,所有的数量都变大,约束成为不可能了。在扩大了的集合(称为华尔兹集)中的接点标志数,从绝对数来说是大的,但与可能出现的接点数相比却是小的。见表9.2. 在某些情况下,接点标志中合法的部分只有将近总数的110-5%。可以肯定的是,虽然线条标志的总数太多,以致由人工是无法利用这些标志的,但是约束也是如此激烈,所以,对子复杂的线条图来说,计算

51、机利用大的线条标志集,仍然可以更快和更少不确定性地收敛到解。联为联为- -稻草人自动化稻草人自动化顶点类型可能组合成的接点数可实现的接点数比例 (%)L叉T箭PsiKXMuti山峰Kk2.5X1031.2X1051.2X1051.2X1056.2X1066.2X1066.2X1066.2X1066.2X1063.1X10880500500703001001001001030324.0X10-14.0X10-15.6X10-24.8X10-31.6X10-31.6X10-31.6X10-31.6X10-39.6X10-6表表9.2联为联为- -稻草人自动化稻草人自动化9.3视觉的知识表示与控制策

52、略 为研究更高级的思维过程如何影响和利用视觉,必定会遇到非视觉范围的问题以及具有更广泛的适用范围的推理能力的问题。关于某一范围内的事物模型,可以支持在视觉领域中与应用对象有关的对物体的计算,但这样的模型相当复杂。在人工智能其他领域中发展起来的知识表达方法,可以描述这样的模型。类似地,在人工智能领域里还对推理和规划作了大量的研究。相关的技术不但可用于其他目的的推理,也可以用于视觉领域中来处理概念和实现预定的目标。联为联为- -稻草人自动化稻草人自动化9.3.1视觉信息的语义网络表示 在视觉领域里,知识表达方法可能是模拟的,也可能是命题逻辑的。模拟的知识表达方法可以表示物体的重要物理和几何特性。命

53、题逻辑表达方法是一些说明有关的事物(或有关事物的模型)是真或是假的陈述。例如用景物中物体的各种物理特性,如表面方向、速度、遮挡轮廓线来表示图像,是模拟的表达方法。用如实心体的三维模型表示景物也是模拟的表达方法。用这种模型可以计算实心体的几何特性,甚至也能计算某些设计者未表示出来的特性。一组谓词计算的子句是命题逻辑的。这两种表达形式用于不同的目的,一种并不比另一种更高级。通常可以把一种表达形式转换成另一种表达形式而不损失信息。这种区分方法是以关于人类如何表示世界的理论为基础的。心理学实验的数据表明,人类同时应用这两种表达方法,而不是只用一种。这里着重介绍语义网络,这是因为它具有如下特点： 联为联

54、为- -稻草人自动化稻草人自动化(1)语义网络可作为一种很方便地存取模拟知识的表达方法以及命题逻辑的知识表达的数据结构。(2)语义网络可作为一种反映在有关领域中事物之间相互关系的模拟结构。(3)语义网络可用作一种具有特殊的推理规则的命题逻辑表达法。 下面举例介绍语义网络在计算机视觉中的应用。例如,试用语义网络表示以下景物： “在道路57(road57)与河流3(river3)交叉处的桥梁位于建筑物30(building30 )附近。” 这个景物可以用图9.34所示语义网络来表示。图中,e为element of之缩写,ROAD(道路),BLDG(建筑物),BRIDGE(桥梁),RIVER(河流)

55、,NEAR(附近),INT(交叉)是表示类别和概念的节点。ROAD57, BLDG30, RIVER3等节点,以及用ISA链与概念节点相联为联为- -稻草人自动化稻草人自动化 连接的未加标志的节点都是表示实例的节点。原来是多元关系的在语义网络中都已用一组等效的二元关系所代替。除此以外,在图中还有标志为X的节点,它是一条特定的道路与一座特定的桥梁相交叉的结果,它并不表示为任何类别概念的实例,这是一个虚节点。如果引入很复杂的关系,可以免除虚节点。但这将牺牲语义网络的重要特性,即可以用一小组基元来构造大量复杂的关系。虚节点通过引用局部的复杂关系增强了这种能力。联为联为- -稻草人自动化稻草人自动化9

56、.3.2位置网络表示 位置网络是在计算机视觉领域中应用语义网络的一个有普遍意义的例子。位置网络可以把几何的和模拟的数据与一个语义网络结构相结合。这个语义网络有时像一个具有专门的求值规则的框架。位置网络不但可以用于航空图像,也可以用于医学图像的应用场合。 位置网络是一组几何点的网络表示。这组几何点由集合理论以及如集合的交运算、并运算、距离计算等几何运算联系在一起。这些运算相应于有关物体位置的限制,是由思维方面的或是由物理上的因素所决定的。 联为联为- -稻草人自动化稻草人自动化 位置网络中的每个内部节点包含几何运算、运算所需的变量表以及运算结果。例如,一个节点可以表示两个变量点集的并,其运算结果

57、是一个点集。推理是由对网络进行求值来进行的,即对网络中所有,的运算求值,以求取顶节点(根节点)运算的点集。这样,网络就有了一个通过变量链叠加在网络上的祖先和后代层次。在这个层次结构的底部是数据节点。数据节点不包含运算和变量,只有几何数据。网络中的每个节点处于以下三个状态中的一个：如果附加在节点上的数据,在当前被认为是准确的,那么,这个节点是更新的；如果已知数据是不完全的、不准确的或有遗漏的,那么这个数据是过时的；如果节点上的内容是由求值过程建立的,但未经图像验证,那么数据是假设的。联为联为- -稻草人自动化稻草人自动化 在一般的应用场合中,景物中所期望的特征的相对位置都已表示在网络中,这样网络

58、就把图像所期望的结构模型化了。物体之间几何关系的基本运算有以下4种：(1)方向性运算方向性运算(左、反射、北、上、下等)：以相对于其他点集的位置和方向来规定点集。(2)区域运算区域运算(靠近于、在四边形内、在圆周内等)：建立一个和其他点集无方向关系的点集。(3)集合运算集合运算：完成并、交以及求差等集合运算。(4)谓词运算谓词运算：对区域进行的谓词运算可通过测量某些数据的特征来删除某些点集。例如,把宽度、长度或面积相对某个数值进行测试的谓词运算,可以限制在允许范围内集合的大小。 网络是由程序从上而下地、以递归的方式进行解释的。解释过程中把每条规则的部分结果储存在和这条规则有关的最高层节点处(只

59、有少数例外)。求值从根节点开始,在绝大多数网络中,这个节点是运算节点。对运算节点的求值,首先要对它所有的变量求值,然后对这些由变量求值产生的结果进行运算。这样网络中其他要求求值的节点可以利用这个运算结果。联为联为- -稻草人自动化稻草人自动化 数据节点可能已经包含结果,这个结果可能来自变换,或以前应用视觉运算的结果。在求值过程中的某个时刻,求值进行到某个节点。这个节点已被求值,并且是更新的或者是假设的(这样的节点包含对这个节点以下的节点求值的结果)。这些节点的结果被返回,并且可当作数据节点来使用。这时的节点使得求值机构执行一个低级过程,以确定特性的位置。如果这个过程在它的能力范围内不能确定物体

60、的状态,那么节点仍处于过时的状态。任何时候,在处理过时节点时都不要求先重新计算更新节点。标有假设的标志的节点有一个通常由推理过程支持的、但未经低级图像处理过程验证的值。假设的数据可用于推理过程：所有基于假设的数据的推理结果,也都标以假设的标志。 如果什么时候数据节点上的数据改变了(比如,由于一个独立的过程增加了新的信息),那么所有这个节点的祖先就要标志为过时的。因此,根节点也要标为过时的状态。但只有那些在过时的节点的通路上的节点才必须重新求值,以使网络更新。联为联为- -稻草人自动化稻草人自动化9.3.3视觉系统的控制策略 计算机涉及控制规模大而复杂的信息处理任务,有智能的生物系统解决了这个控