第三章基于推理的视觉理解 3.1基于推理的视觉理解概述 3.1.1逆向和不适定问题 3.1.2感知组织现象 3.1.3视觉识别和推理 3.2感知组织的基本原理 3.2.1根据图象关系的显要性进行聚类 3.2.1.1图象关系非偶然性产生的概率 3.2.1.2限制计算的复杂性 3.22通过求能量极小进行聚类 3.22.1计算策略 3.222感知聚类中的表象 3.22.3聚类能量的计算 3.23根据图象特征推论三维空间结构 3.3景物结构的模型 3.31部件模型和自然形状表示法 33.2部件识别理论( Recognition-By- Component,RBC) 31基于推理的视觉理解 在研究基于推理的视觉理解以前先要对视觉信息处理和理解中的一些主要特点和特性 有基本的了解。其中最主要的是要认识到视觉问题从本质上说是不适定的(l- posed),如 果没有附加信息就不能找到解答。这在很大程度上是由于许多视觉任务从本质上来说是逆向 的问题。例如,图象是三维景物的二维投影,如果已知景物的三维模型,在一定的几何条件 下通过投影(正向过程)产生的图象是唯一的。但是同一幅图象可以是无穷多种三维物体的 投影的结果。因此根据图象不可能唯一地确定它是什么景物投影的结果。例如,图3.1中所 示的M形图象,它可以是由图3.1(a)中的空间某M形物体投影的结果,但它同样也可以是 图3.1(b)中所示的三根在空间互不相交的一些空间曲线投影的结果 nag Plane a) 图3.1不同的形体产生相同的图象 但是当人们看到(a)中所示的图象时,并不感到它是多义的,这说明人类视觉在理解这
44 第三章 基于推理的视觉理解 3.1 基于推理的视觉理解概述 3.1.1 逆向和不适定问题 3.1.2 感知组织现象 3.1.3 视觉识别和推理 3.2 感知组织的基本原理 3.2.1 根据图象关系的显要性进行聚类 3.2.1.1 图象关系非偶然性产生的概率 3.2.1.2 限制计算的复杂性 3.2.2 通过求能量极小进行聚类 3.2.2.1 计算策略 3.2.2.2 感知聚类中的表象 3.2.2.3 聚类能量的计算 3.2.3 根据图象特征推论三维空间结构 3.3 景物结构的模型 3.3.1 部件模型和自然形状表示法 3.3.2 部件识别理论（Recognition-By-Component, RBC） 3.1 基于推理的视觉理解 在研究基于推理的视觉理解以前先要对视觉信息处理和理解中的一些主要特点和特性 有基本的了解。其中最主要的是要认识到视觉问题从本质上说是不适定的（ill-posed），如 果没有附加信息就不能找到解答。这在很大程度上是由于许多视觉任务从本质上来说是逆向 的问题。例如，图象是三维景物的二维投影，如果已知景物的三维模型，在一定的几何条件 下通过投影（正向过程）产生的图象是唯一的。但是同一幅图象可以是无穷多种三维物体的 投影的结果。因此根据图象不可能唯一地确定它是什么景物投影的结果。例如，图 3.1 中所 示的 M 形图象，它可以是由图 3.1(a)中的空间某 M 形物体投影的结果，但它同样也可以是 图 3.1(b)中所示的三根在空间互不相交的一些空间曲线投影的结果。 图 3.1 不同的形体产生相同的图象 但是当人们看到(a)中所示的图象时，并不感到它是多义的，这说明人类视觉在理解这
样的图象时要么是利用了附加的高层信息(例如,知道图中是哪一类物体的知识),要么是 利用了某些可以去除多义性解释的通用约束。心理物理学研究的结果表明人类同时使用了这 两种策略,但令人惊奇的是在消除多义性方面,高层知识提供的信息要比低层的通用约束提 供的少。这说明人类视觉在理解图象时必定利用了某些通用的约束。当然这些通用约束中包 括景物和物体成象的基本物理性能,但还不止这些。其中很可能还包括所谓的感知组织 ( perceptual organization)。如果不对这些约束有透彻的了解,要建立通用的视觉系统是困 难的。以下对逆向和不适定问题,以及感知组织作简要介绍 311逆向和不适定问题 通常逆向问题涉及在只知道输出和所进行处理的本质的条件下,重构由于某种操作所畸 变的数据。例如,已知x+y=17;求解满足上述公式的x和y,就是一个逆向问题。这时所进 行的处理是已知的(加法),操作输出是已知的(17),但其输入x和y是未知的。许多低 层计算机视觉问题是逆向的,因为这些问题要求根据从三维到二维变换后的输出(例如灰度 图象),重构三维形状、边缘位置或运动等。 1.适定性定义 1923年 Hadamard定义当一个数学问题满足下述条件时是适定的: (1)存在一个解;(2)这个解是唯一的:(3)解连续地取决于输入数据,即输入数据的很小 变化对输出也只引起一个小的变化。 虽然许多逆向问题是不适定的,如上述简单例子所示。这是因为在这些问题中存在许多 可能的解,因此不满足条件(2)。此外,实际中只能得到观察数据,而不是实际数据,所以 不能保证满足(3),因此需要附加的信息来使这问题成为适定的。附加信息可以是定量的 这就得到近似解( quasisolution)。另一种方法是使问题正则化,这时需要应用诸如解的特 征这样的定性信息 2.正则理论 正则理论提供一个解决不适定问题的框架。这涉及通过扩展问题的定义来限制解的空 间,具体方法是增加体现解所希望特性的约束。这些附加的约束被称为稳定函数( stabilizing function),设:A是已知线性算子,y是已知数据,g是要恢复的未知数据。逆向问题定义 为恢复g,使得: Ag 通常,y是由测量得到,但伴随着噪声。所以,只知道它的近似值y,因此,所能得到的是 由下式求得近似解 y=Ag 这个近似解可通过寻找使得下式为极小的g来求得: 其中‖是合适的模。设:g是体现解的所希望特性的通解。因此,所希望的解g应使下式 为极小: P(g)被称为稳定函数( stabilizing function) 设:P(g)至少是半单调的( quasimonotone),把上述两条件综合起来,求解就可表示为寻 找使下式为极小的g 4g-y|+x[(g 其中λ是控制上述两项相对重要性的正则化参数。这里第一项描述所求解经变换后的符合程
45 样的图象时要么是利用了附加的高层信息（例如，知道图中是哪一类物体的知识），要么是 利用了某些可以去除多义性解释的通用约束。心理物理学研究的结果表明人类同时使用了这 两种策略，但令人惊奇的是在消除多义性方面，高层知识提供的信息要比低层的通用约束提 供的少。这说明人类视觉在理解图象时必定利用了某些通用的约束。当然这些通用约束中包 括景物和物体成象的基本物理性能，但还不止这些。其中很可能还包括所谓的感知组织 （perceptual organization）。如果不对这些约束有透彻的了解，要建立通用的视觉系统是困 难的。以下对逆向和不适定问题，以及感知组织作简要介绍。 3.1.1 逆向和不适定问题 通常逆向问题涉及在只知道输出和所进行处理的本质的条件下，重构由于某种操作所畸 变的数据。例如，已知 x+y=17；求解满足上述公式的 x 和 y，就是一个逆向问题。这时所进 行的处理是已知的（加法），操作输出是已知的（17），但其输入 x 和 y 是未知的。许多低 层计算机视觉问题是逆向的，因为这些问题要求根据从三维到二维变换后的输出（例如灰度 图象），重构三维形状、边缘位置或运动等。 1. 适定性定义 1923 年 Hadamard 定义当一个数学问题满足下述条件时是适定的： (1)存在一个解；(2)这个解是唯一的；(3)解连续地取决于输入数据，即输入数据的很小 变化对输出也只引起一个小的变化。 虽然许多逆向问题是不适定的，如上述简单例子所示。这是因为在这些问题中存在许多 可能的解，因此不满足条件(2)。此外，实际中只能得到观察数据，而不是实际数据，所以 不能保证满足(3)，因此需要附加的信息来使这问题成为适定的。附加信息可以是定量的， 这就得到近似解（quasisolution）。另一种方法是使问题正则化，这时需要应用诸如解的特 征这样的定性信息。 2. 正则理论 正则理论提供一个解决不适定问题的框架。这涉及通过扩展问题的定义来限制解的空 间，具体方法是增加体现解所希望特性的约束。这些附加的约束被称为稳定函数（stabilizing function），设：A 是已知线性算子，y 是已知数据，g 是要恢复的未知数据。逆向问题定义 为恢复 g，使得： y = Ag 通常，y 是由测量得到，但伴随着噪声。所以，只知道它的近似值 y *，因此，所能得到的是 由下式求得近似解： y Ag = 这个近似解可通过寻找使得下式为极小的 g 来求得： Ag − y 2 其中 是合适的模。设：g *是体现解的所希望特性的通解。因此，所希望的解 g 应使下式 为极小： P( g) = g − g 2 P(g)被称为稳定函数（stabilizing function）。 设：P(g)至少是半单调的（quasimonotone），把上述两条件综合起来， 求解就可表示为寻 找使下式为极小的 g Ag − y + P P( g) 其中p 是控制上述两项相对重要性的正则化参数。这里第一项描述所求解经变换后的符合程
度,第二项说明所求解与所希望的解的特性的接近程度。通过应用稳定函数,在某种程度的 数据范围内,可保证解的唯一性和强制所得结果连续地取于所观察的数据。这样就使问题成 为适定的并在现在这种极小化问题形式下可求解。 312感知组织 感知组织是指人类视觉系统所具有的在不知道图象内容的先验知识条件下,从图象获得 相对的聚类和结构的能力。例如,人能从随机分布的图象元素的背景中迅速地检测出对称性、 共线性、平行性、连通性和重复纹理等特性。对感知组织研究的全盛时期是在1920~30年 代,这个时期在感知研究中占主导的是 Gestalt理论。这个理论主要的研究内容就是感知组 织现象。 Gestalt学家的基本原则是整体要大于部分之和。例如,纸上画的两个点具有每个 点单独时所没有的方向性。所以方向性被认为是形成特性( emergent property)。因此, Gestal 研究如何把简单的敏感输入组织或聚类成为复合的稳定感知。这样的感知表现出形式和结 构。 Gestalt这个词本身的含意就是整体( whole)和结构( Configuration)。 Gestalt心理学家对我们理解感知组织的主要贡献是进行了大量的感知组织现象的验证, 并把它们进行分类(见图3.2), Gestalt心理学家认为下述这些因素在结构的感知中起重要 作用: (1)接近性( Proximity):较为接近的元素倾向于聚集在一起 (2)相似性( Similarity):颜色、方向、或大小这样的物理属性相似的元素相聚集 (3)封闭性( Closure):曲线段在形成完整曲线时有形成封闭区域的倾向 (4)连续性( Continuation):位于同一条直线或平滑曲线上的元素相聚集 (5)对称性( Symmetry):任何横向对称于某个轴的元素相聚集 (6)熟知性( familiarity):我们经常看到它们在一起的元素相聚集。 Proximity similarity ][][] Coleus ()5 Symme 图3.2聚类现象的分类 此外还有如相同方向上以同一速度移动的点、同一运动结构的各部分应被聚成一类。 Gestalt心理学家研究的一种影响是引起了对感知组织基本原理的研究。初始的 Gestalt学家 对这方面的研究不很成功,他们把组织的规则归结为称为完形( pragnanz)的单个规则, Pragnanz这个德文字的含意是“简单”或“完善”的形式。但这只是一个没有定量公式的
46 度，第二项说明所求解与所希望的解的特性的接近程度。通过应用稳定函数，在某种程度的 数据范围内，可保证解的唯一性和强制所得结果连续地取于所观察的数据。这样就使问题成 为适定的并在现在这种极小化问题形式下可求解。 3.1.2 感知组织 感知组织是指人类视觉系统所具有的在不知道图象内容的先验知识条件下，从图象获得 相对的聚类和结构的能力。例如，人能从随机分布的图象元素的背景中迅速地检测出对称性、 共线性、平行性、连通性和重复纹理等特性。对感知组织研究的全盛时期是在 1920～30 年 代，这个时期在感知研究中占主导的是 Gestalt 理论。这个理论主要的研究内容就是感知组 织现象。Gestalt 学家的基本原则是整体要大于部分之和。例如，纸上画的两个点具有每个 点单独时所没有的方向性。所以方向性被认为是形成特性（emergent property）。因此，Gestalt 研究如何把简单的敏感输入组织或聚类成为复合的稳定感知。这样的感知表现出形式和结 构。Gestalt 这个词本身的含意就是整体（whole）和结构（Configuration）。 Gestalt 心理学家对我们理解感知组织的主要贡献是进行了大量的感知组织现象的验证， 并把它们进行分类（见图 3.2），Gestalt 心理学家认为下述这些因素在结构的感知中起重要 作用： (1) 接近性（Proximity）：较为接近的元素倾向于聚集在一起； (2) 相似性（Similarity）：颜色、方向、或大小这样的物理属性相似的元素相聚集； (3) 封闭性（Closure）：曲线段在形成完整曲线时有形成封闭区域的倾向； (4) 连续性（Continuation）：位于同一条直线或平滑曲线上的元素相聚集； (5) 对称性（Symmetry）：任何横向对称于某个轴的元素相聚集； (6) 熟知性（familiarity）：我们经常看到它们在一起的元素相聚集。 图 3.2 聚类现象的分类 此外还有如相同方向上以同一速度移动的点、同一运动结构的各部分应被聚成一类。 Gestalt 心理学家研究的一种影响是引起了对感知组织基本原理的研究。初始的 Gestalt 学家 对这方面的研究不很成功，他们把组织的规则归结为称为完形（pragnanz）的单个规则， Pragnanz 这个德文字的含意是“简单” 或“完善”的形式。但这只是一个没有定量公式的
转圈的定义。总的来说 Gestalt理论只是描述性的,而不是定量的。例如,根据相似性或熟 知性这样很通用的术语是难以得到定量的理论的。因此当代的感知组织研究是要寻找聚类因 素的定量和客观的测量。例如, Hochberg和 Brooks(1960)提出了直线线画图中角的数量能很 好地反映形象的复杂性,和所感知物体的立体性。 Hochberg(1981)o8n和Rock(1975)提 出简单性原理,即通常被感知的是要求最少量信息来规定的组织。但不幸的是简单性本身也 是不适定的,因为描述一个形象的简单性的程度完全取决于所用的描述语言。所以,Lowe 和 Binford(1982)w82以及 WitKin和 Tenebaum(1983)w8提出了非偶然性概念 (non- accidentalness)。即所感知的是最不可能由于偶然机会产生的形状。 Mccafferty(1990c提出了用求能量极小进行聚类的方法。他们都提出一种可通过计算来 对聚类过程进行评价和衡量的方法。这两种方法将在下一节中分别介绍。此外值得注意的是 某些新发现的感知组织现象,这些现象有助于加深对感知组织的理解。其中一个是由 Kanizsa (1979)提出的形状完整性( Shape Completion)或错觉轮廓( illusory Contour),图 33上所示为这种现象的一例子。从图上人们通常可以感觉到一个把四角分别放在四个圆上 的正方形,而不是四个单独的圆。这个感觉到的正方形大部分是由在物理上并不存在,但是 可感知的轮廓构成。这个现象是重要的,因为这表明感知组织可以通过并无直接物理起因的 推理输入产生,与此类似的还有由 Glass(1969)和 Stevens(1978)提出的虚拟线( Virtual 图3.3错觉轮廓 还有一个不清楚的问题是感知组织的各个方面与立体视觉融合或物体识别这样的其它 视觉处理过程之间的关系。这个关系是就它们在视觉通路上的相对位置而言的。Mar(1982 976)m82提出:基于边缘点的相似性之上的聚类和线段的连接,发生在产生完全的初始 简图的过程中,这说明聚类发生在根据各种视觉线索恢复形状的处理过程以前。对这个观点 Mar没有给出什么心理物理学或心理学的证明,他只是给出了一些例证。 图3.4是一个例证,说明感知组织如何能为根据影调恢复形状的分析提供标记。图上所 示的是一些分布在黑色背景上的非黑色离散点,这些非黑色点的灰度是按照一个圆柱图象的 灰度分布曲线来确定的。这些非黑色点被聚类,以恢复原来的灰度分布情况,并呈现出圆柱 的三维形状。这表明在进行形状分析以前单独的点必须以某种方式被聚类成单元,这是因为 正是由这样的聚类产生的区域而不是单独点本身产生三维形状。 总之,有证据表明感知组织的不同方面是在视觉通路的不同阶段上进行的。这说明感知 组织是视觉通路上的许多阶段都涉及的功能,这个功能的目的是试图发现所通过数据中的结 构。还有一个重要的问题是低层视觉处理输出应采取的形式。这个问题很重要,因为聚类处 理是递归进行的,这点可由图34所示来证明,其中非黑色的象素被聚类成块,块又被聚类
47 转圈的定义。总的来说 Gestalt 理论只是描述性的，而不是定量的。例如，根据相似性或熟 知性这样很通用的术语是难以得到定量的理论的。因此当代的感知组织研究是要寻找聚类因 素的定量和客观的测量。例如，Hochberg 和 Brooks(1960)提出了直线线画图中角的数量能很 好地反映形象的复杂性，和所感知物体的立体性。Hochberg（1981）[Hoc 81]和 Rock(1975) 提 出简单性原理，即通常被感知的是要求最少量信息来规定的组织。但不幸的是简单性本身也 是不适定的，因为描述一个形象的简单性的程度完全取决于所用的描述语言。所以，Lowe 和 Binford(1982)[Low 82] 以 及 WitKin 和 Tenebaum(1983)[Wit 83] 提出了非偶然性概念 （ non-accidentalness ）。即所感知的是最不可能由于偶然机会产生的形状。 McCafferty(1990)[Mcc 90]提出了用求能量极小进行聚类的方法。他们都提出一种可通过计算来 对聚类过程进行评价和衡量的方法。这两种方法将在下一节中分别介绍。此外值得注意的是 某些新发现的感知组织现象，这些现象有助于加深对感知组织的理解。其中一个是由 Kanizsa （1979）[Kan 79]提出的形状完整性（Shape Completion）或错觉轮廓（ illusory Contour），图 3.3 上所示为这种现象的一例子。从图上人们通常可以感觉到一个把四角分别放在四个圆上 的正方形，而不是四个单独的圆。这个感觉到的正方形大部分是由在物理上并不存在，但是 可感知的轮廓构成。这个现象是重要的，因为这表明感知组织可以通过并无直接物理起因的 推理输入产生，与此类似的还有由 Glass（1969）和 Stevens（1978）提出的虚拟线（Virtual lines）。 图 3.3 错觉轮廓 还有一个不清楚的问题是感知组织的各个方面与立体视觉融合或物体识别这样的其它 视觉处理过程之间的关系。这个关系是就它们在视觉通路上的相对位置而言的。Marr（1982, 1976）[Mar 82]提出：基于边缘点的相似性之上的聚类和线段的连接，发生在产生完全的初始 简图的过程中，这说明聚类发生在根据各种视觉线索恢复形状的处理过程以前。对这个观点 Marr 没有给出什么心理物理学或心理学的证明，他只是给出了一些例证。 图 3.4 是一个例证，说明感知组织如何能为根据影调恢复形状的分析提供标记。图上所 示的是一些分布在黑色背景上的非黑色离散点，这些非黑色点的灰度是按照一个圆柱图象的 灰度分布曲线来确定的。这些非黑色点被聚类，以恢复原来的灰度分布情况，并呈现出圆柱 的三维形状。这表明在进行形状分析以前单独的点必须以某种方式被聚类成单元，这是因为， 正是由这样的聚类产生的区域而不是单独点本身产生三维形状。 总之，有证据表明感知组织的不同方面是在视觉通路的不同阶段上进行的。这说明感知 组织是视觉通路上的许多阶段都涉及的功能，这个功能的目的是试图发现所通过数据中的结 构。还有一个重要的问题是低层视觉处理输出应采取的形式。这个问题很重要，因为聚类处 理是递归进行的，这点可由图 3.4 所示来证明，其中非黑色的象素被聚类成块，块又被聚类
成圆周。聚类处理可以是在另一种聚类处理输出的基础上进行的事实说明,在所有的聚类过 程中应使用相同的表达。 图3.4随机点图案,其中非黑色点的灰度是按圆柱图象的灰度分布取的 13视觉识别与推理 在计算机视觉中解决视觉任务的方法可分成两大类:基于重构( reconstruction)的方法 和基于识别( recognition)的方法。基于重构的方法试图根据图象恢复和重构外部视觉环境 的物理参数。例如,物体表面的深度或方向,物体的边界,以及光源的方向等,Mar的视 觉计算理论基本可以归入这一类。基于识别方法的目标是物体的识别和描述。识别是指发现 图象中的成份与环境中物体的先验表示之间的对应。所以就识别而言,并不需要重构环境完 整的物理参数,在识别过程中关于环境的先验知识将起极其重要的作用。我们在日常生活中 可能看到的物体和景物数量巨大、种类繁多,如果没有这些先验期望的约束作用,许多视觉 问题就可能因为约束不充分而不能被解决。识别使我们能超越图象中的数据,因为我们可根 据小部分预期的对应达到可靠的识别,然后应用知识来推论由视觉数据没有直接提供的景物 的特性。这说明视觉信息处理中在尽可能早的阶段中应用知识的价值和必要性,也说明视觉 理解可以通过推理来完成。因此基于识别的方法也可以称为基于推理的方法。 Image feature O 2. 5D sketch 3D-inference Groupings 3D Grouping Object Model 48
48 成圆周。聚类处理可以是在另一种聚类处理输出的基础上进行的事实说明，在所有的聚类过 程中应使用相同的表达。 图 3.4 随机点图案，其中非黑色点的灰度是按圆柱图象的灰度分布取的。 1.3 视觉识别与推理 在计算机视觉中解决视觉任务的方法可分成两大类：基于重构（reconstruction）的方法 和基于识别（recognition）的方法。基于重构的方法试图根据图象恢复和重构外部视觉环境 的物理参数。例如，物体表面的深度或方向，物体的边界，以及光源的方向等，Marr 的视 觉计算理论基本可以归入这一类。基于识别方法的目标是物体的识别和描述。识别是指发现 图象中的成份与环境中物体的先验表示之间的对应。所以就识别而言，并不需要重构环境完 整的物理参数，在识别过程中关于环境的先验知识将起极其重要的作用。我们在日常生活中 可能看到的物体和景物数量巨大、种类繁多，如果没有这些先验期望的约束作用，许多视觉 问题就可能因为约束不充分而不能被解决。识别使我们能超越图象中的数据，因为我们可根 据小部分预期的对应达到可靠的识别，然后应用知识来推论由视觉数据没有直接提供的景物 的特性。这说明视觉信息处理中在尽可能早的阶段中应用知识的价值和必要性，也说明视觉 理解可以通过推理来完成。因此基于识别的方法也可以称为基于推理的方法。 Perceptual Organization Object Model Image feature 3D-inference Perceptual 2.5D sketch Groupings 3D Grouping