方案。事实上，这种论点表明，利用每次的特征向量和下一个最小特征向量，可以细分现有的图形。然而，在实际中，从实际价值解决方案到离散价值解决方案的逼近误差随着每一个特征向量的使用而积累，并且每一个特征向量必须满足互相正交的约束，这种基于更高的特征向量的解决方案就变得不可靠。最好是重新单独解决每个子图的分割问题。
总之，我们建议利用规范化分割准则进行图形分割，并且，我们已经说明这一准则是怎样通过解决广义特征值问题而得到高效的计算。
3.分组算法
像我们之前看到的，（6）中的广义特征系统可以转化为标准特征值问题。解决所有特征向量的标准特征值问题需要O（n3）个步骤，n是图形的节点数。对于图像分割应用这是不可行的，其中n是图像中的像素数。幸运的是，我们的图像分割具有以下特征：（1）图形经常只是局部连接，由此产生的特征系统非常稀松，（2）图形分割只需少数的高特征变量，（3）特征向量的精度要求低，往往只需正确的符号位。我们问题的这些特殊属性可以被称为lanczos方法的特征求解器充分利用。Lanczos算法的计算时间为O(mn)+O(mM(n)),其中m是矩阵相量运算需要的最大数值，M(n)是矩阵向量计算的成本。在（D-W）矩阵稀松的情况下，矩阵向量只需要O(n)时间。m值取决于许多因素。在我们图像分割的实验中，m
1值一般小于O(n2)。
计算特征向量时，我们可以利用第二个最小特征向量将图形分割成两部分。理想情况下，特征向量只有两个离散值，值得迹象会告诉我们怎样分割图形。让本人，我们的特征向量可以取连续的值，我们必须选择一个分割点将图形分为两部分。选择这一分割点有许多方法。可以取0值或中间值作为分割点，或者寻找一个分割点使结果有一个最合适的Ncut(A,B)值。我们在工作中采取了后者。现在，研究工作是检查等间隔的可能的分割点和计算Ncut最优值。在我们的实验中，特征向量的值一般分离，即使L值很小，这种选择分割点的方法也很可靠。
图形被分成两部分后，我们可以在两个分区第贵的运行我们的算法。或者等价的，我们可以利用其他高级特征向量的特殊属性，就像前面介绍的基于那些特征向量分割图形。当Ncut值超过一定限制时递归停止。
我们也对分割加了一个稳定准则，有一些类似于边缘检测的定位准则。我们可以通过一个准则区分真正的边缘与具有高梯度阴影的区域，这一准则是在高梯度阴影区域真正边缘位置不同会改变其强度，而在平滑阴影区域时假定边缘位置不同不影响其强度。在目前情况下，如果改变形成切割的图形边缘，Ncut值变化不大，我们将其视为不稳定切割。为了计算这一稳定值，我们围绕优化值改变切割点的值，并且引入两个不同分区，P1=(A1,B1)和P2=(A2,B2)。稳定值是
?cut(P1,P2)?D(P1,P2),其中?D(P1,P2)??i?(A1/A2)di。
我们的分组算法可以总结如下：
1.已知一组特征，设置一个加权图G=(V,E)，计算每个边缘的权重，并且将信息汇总到W和D。
2.利用最小特征向量解式(D?W)X??DX的特征向量。
3.通过第二个最小特征向量的特征值划分图形找到切割点，从而使规范化切割值值最小化。
4.通过检查分割稳定性决定现在的划分是否需要细分，并且确保规范化切割值低于指定值。
5.如果有必要对分割部分再划分。
通过这种方法分割组的数量直接受最大规范化切割值的控制。
4.实验
我们已经将分组算法应用于基于亮度，颜色，质地和运动信息的图像分割。在每种情况下，我们通过将每个像素当做一个节点构建图形G=(V,E)，并且定义节点i和j的边沿权重wij为特征相似性术语和空间邻近性术语：
其中X(i)是节点i的空间位置，F(i)是基于强度，颜色，质地信息的节点的特征向量，定义为：（1）在分割点集的情况下，F(i)=1；（2）F(i)=I(i)，强度值，为了分割亮度图像；（3）F(i)?[v,v?s?sin(h),v?s?cos(h)](i)，h,s,v是HSV的值，用于颜色分割；（4）
F(i)?[|I?f1|,.....,|I?fn|](i)，用于质地图像分割。需要注意的是任意节点i和j的权重wij=0已经超过分离的r像
素。 图3
我们首先在类似于图2的空间点集合上测试算法。图3说明点集和分割结果。从图中可以看出，标准化切割准则确实可以用我们在第二部分讨论的理想方式切割点集。
图4，5，6是应用分割算法于不同亮度的图像。图4 是又添加噪声的合成图像。图5，6是自然图像。需要注意的是图6 的物体边界不明确，这将会是边界检测不佳。图7是颜色图像的分割，在这些处
理中重现灰度。 图4
需要注意的是，在所有的例子中，算法可以提取场景的主要组成部分而忽略小的内部成分的变化。根据需要，递归分割可以用于进一步分解每个部分。
最后，我们用以斑马为背景的自然图像的质地分割的初步结果作为总结，看图8。需要注意的是我们的措施是变化方向的。因此，部分拥有不同条纹的斑马的皮肤应该标为单独区域。
在这些例子中，我们已经分别考虑了基于亮度，颜色和质地的分割。显然这些可以和视差，运动信息结合在一起。
图5
图6
图8
图7
5 相关分割算法
利用特征值问题解决图像分割的 观点最初是在多纳特，霍夫曼和 费德勒的作品中提到的。费德勒 认为(D?W)x??x的特征向量
的第二个最小特征值可以用于 分割图像。实际上第二个最小特 征值被称为费德勒值，相应的特 征向量是费德勒特征向量。这一 光谱分割的想法已经复兴，并且 通过一些研究者得到进一步发展， 特别是在并行科学计算领域。
在应用于其它领域时，与多做这表明光谱分割放吧确实提供了分割
图形的好方法。在这个领域的理论工作集中于切割率和费德勒值之间的联系。区域A的切割率定义为
cut(A,V?A)min(|A|,|V?A|)。可以看出费德勒值越小，基于费德勒向
量的图像分割会有较好的切割率。我们在2.1的推导表明费德勒向量是
mincut(A,V?A)A?V|A|?cut(V?A,A)|V?A|问题的解决方法，我们可以称之为平均分割。
尽管平均分割看起来与规范化分割相似，但平均分割没有平均相关这一属
性，可以定义为
asso(A,A)|A|?asso(V?A,V?A)|V?A|。因此，不可以同时减小非相关
和增大组内相关。当我们将所有技术都用于图像分割，范县在实际中规范化分割效果更好。
广义特征值方法通过平衡并行计算机的计算负载而第一次应用于图像分割。 在计算机社区，有一些相关的图像分割方法。吴和莱希利用最小切割准则进行分割。Cox寻求减小
cut(A,V?A)weight(A),A?V，其中weight（A）是点集A的函数。
Cox假设图形是一个平面，利用搞笑的离散算法解决了优化问题。
萨卡和博耶利用Wx??x的具有最大特征值的特征向量，找到边界图最连贯的区域。尽管他们的特征系统钰图形分割没有直接关系，利用2.1的推导，我们可以看到他们的系统接近minasso(A,A)A?V|A|。
6.总结
在本文中，我们提出一个分组算法，该算法基于的观点是感知分组是一个旨在提取场景的总体印象和提供分层描述的过程。通过将分组问题看成图形分割问题，我们提出了规范化切割准则。规范化切割解决子图非相关行的好方法，并且有一个较好的特性是减小切割将增大相关性，这对于子组内部的总相关是公平的。在为了计算最小切割值而找有效算法过程中，我们又提出广义特征值系统对于我们的问题提供了一个还得解决方案。
基于这种观点的计算方法已得到发展，并且应用于亮度，颜色，质地图像的分割。对于真实和合成图像的实验结果是令人鼓舞的，并且说明了这一规范化切割准则确实满足我们提取场景的大图像的最初目标。