基于PCA和可变部件模型的大量重复目标检测方法*

苏 宁, 郝兆才

(1.济宁学院 产业学院,山东 济宁 273155； 2.曲阜师范大学 数学科学学院,山东 济宁 273165)

0 引 言

目前，很多研究领域会遇到大量相似目标的计数与重复检测[1]任务，重复目标检测应用广泛，该技术可应用于生产车间中的产品检验、医学研究中的细胞计数、交通节点的人群统计[2]等。执行这些任务时，除了需要人工参与外，借助计算机技术进行目标自动检测成为必然选择。然而，在缺少先验知识的情况下，自动检测变得很困难，其原因主要是形状、光照以及目标视觉复杂性等因素的影响。

目标计数与检测一般分为两类，第一类方法基于不同的视觉描述符[3]。其主要方式是从图像中提取低层描述符，预测目标的位置信息。常用的特征有：局部方向梯度直方图[4]、霍夫变换[5]、尺度不变特征[6]等，预测则由一些分类器完成。例如，文献[7]将分层结构的检测器和一个像素级的分割器一起学习，以获得更高的检测精度。文献[8]在霍夫变换中加入了更高层次的几何约束，并结合了随机场模型，但所需的计算成本较高。

第二类方法面向大量密集的对象，例如人群，该类目标由少量像素组成，一般基于不同的纹理描述符对目标密度进行回归，并通过密度积分得出目标数量[9]。如文献[10]提出一种基于密度等级分类的田间棉铃计数算法，采用密度等级分类估计器对图像中的全局上下文信息进行编码，但该方法对训练集的注释要求较多，训练过程较为繁琐。

上述方法一般包含训练过程，且要求大量样本和目标位置信息。因此在多样化的场景中容易受到限制。本文利用图像的重复性，对视觉特征进行估计，提出了基于可变形部件模型(deformable part model,DPM)的目标检测方法，其主要思想是利用图像中目标外观的绝对数量自动对参数进行恢复。因此，所提方法允许一定的几何变形，且不需要琐碎的训练过程。

1 提出的方法

1.1 方法流程概述

本文方法基本流程如图1所示，分为两个步骤：1)提取图像中的目标包围框，对反复出现的分块，分析其空间相关性，获得DPM的组件参数；2)确定重复目标的描述符，采用随机抽样一致性(random sample consensus,RANSAC)聚类来判定DPM指向的潜在重复目标位置，对分类特征运用主成分分析(principal component analysis,PCA)方法获得分类结果。其中，潜在重复目标是通过一个主动学习程序适应到输入数据中，该学习程序要求用户在极少数的边缘实例上提供反馈。

图1 本文方法的基本流程图

1.2 提取反复出现的分块

本文希望找到与目标模式相关，且反复出现的分块，提取出这些分块，并将其作为目标DPM的视觉描述符。为此，首先，围绕一个随机坐标的一个较小正方形窗口，设为候选分块p，计算其余图像中围绕着x的每个分块之间的互相关函数ρ(x)，图像分块p和q之间的互相关值定义为：〈p-pu,q-uq〉/(σpσq)。其中，〈.,.〉表示点积算子，μ表示分块均值，σ为标准偏差。通过设q=p得出p的自相关值，通过对ρ(x)进行极大值抑制来定义p的出现映射z(x)。像素y与所用分块维度相同，是围绕着x的窗口中的一个像素，在任何像素y处，若ρ(x)≤ρ(y)，则设z(x)=1，式中ρ(x)>1-ε，在其他地方设z(x)=0。本文在所有报告测试中均采用ε=1/20，但预计该数值在噪声水平较高的情况下会增加。这里使用的分块尺寸为9×9，并假设目标为该分块大小的3倍。因此，本文要求用户对图像中的目标之一使用一个包围框并对图像进行相应的缩放。

上述中的出现映射z(x)是一个二值图，其中z(x)=1表示图像I(x)和分块p中的像素具有强烈的结构相似性，反之则z(x)=0。因此,可以通过∑xz(x)测量p在图像中的频率。对该步骤进行多次重复操作(本文考虑的候选分块为30个)并将频率最高的分块添加到一个反复出现分块的列表中p1,p2…并保留对应的出现映射z1,z2…。重复该过程，直到得出的分块频率降低到之前步骤中遇到的最大频率的某个比例之下(本文该比例为30 %)。

1.3 分块相关性分析

在找到的反复出现分块中，很多分块有极大可能性对应着重复目标的不同部分，因此表现出的空间排列具有一致性，如图2所示。本文使用一个分块相关分析对该空间依赖性进行检测，并且用其定义DPM的弹簧参数。这个步骤可以在分块出现和某个特有目标之间建立联系，同时丢弃之前步骤中得到的离群分块。

图2 所有分块出现及其聚类

本文利用目标在图像中的重复性给出映射zi和zj之间的自相关函数和互相关函数τi,j，其中,1≤i，j≤n，n为提取出的分块数量。如果第i个分块和第j个分块对应着重复目标的两个部分，那么这两个分块对相同的出现做出响应。这些响应都会记录在zi和zj中，但为每个响应采用一个不同的空间偏移量，该偏移量与目标中的分块偏移相对应。出现映射中的这种空间依赖性将在两个分块的互相关函数中得到一个峰值，该峰值与空间偏移向量相等。

为了检测强相关的分块，本文通过对τi,j(x)中的最大值和第二大值之间的比例进行度量，该第二大值作为一个局部最优值(大于距其最近的8个点)。如果该比例超过了某个因子(设置为2)，则将分块对(i,j)标注为相关，并通过ui,j=arg maxxτi,j(x)提取该分块对的特有空间偏移量。

对于已找到的重复出现的分块集合，其对应于一个不完全图的顶点，该图的边缘为强相关的分块对。图中的每个边缘均与分块间的平均空间偏移向量uij相关联。接着，构建形状模型，将这些相关关系转换到一组平面坐标集中，利用该坐标集对潜在的目标进行高效检测。为了进行整体规划，本文利用局部线性嵌入(LLE)技术[11]，即通过式(1)进行最小化处理，并寻找与空间偏移uij尽可能一致的全局顶点坐标x1,…,xn

(1)

式中E为图中的边缘集合。

1.4 重复目标检测

1.4.1 重复目标的潜在位置

如果DPM为树形结构，可通过动态规划[12]检测目标，时间复杂度为O(nN)，其中，N为图像像素的数量，n为分块的数量。如上文所述，本文利用出现映射，将范围缩小到O(nm)进行搜索，m为目标出现的数量。由于每个实例的出现都可能伴随着自身的形变，以上转换方法消除了分块在目标中位置的一致性偏移，并导致响应的大量聚集，如图2所示。因此，为提取潜在位置，本文采用RANSAC算法进行聚类。

1.4.2 重复目标的描述符

为确定得到的簇是否表示一个真实的目标外观，采取了一个低维的线性分离器进行分类。该分类基于每个簇中提取的以下几个度量：

1)簇中的分块数量；

2)分块和图像之间的平均相关值；

3)簇中的平均形变，其计算公式为

(2)

4)出现在簇中的分块质心和簇中心之间的平均距离为||∑j∈Ckyj/|Ck|-ck||。

图3 用于分类的特征

1.4.3 重复目标的分类

通过将每个簇的特征向量输入一个线性支持向量机(support vector machine,SVM)，即(〈fj,w〉-b)，以判定该簇是否与一个目标外观相对应，式中w和b分别为分离向量和偏移值。

本文允许用户针对输入图像的特性对决策判定进行调整。首先，启动w=(1,0,0,…)，即仅考虑分块的数量，并计算所有正向判定的偏差bmin和所有负向判定的偏差bmax；然后，提取在此范围内均匀采样的20个簇及其得分〈fj,w〉，允许用户使用滑块选择b∈[bmin,bmax]以修改簇的分类。

已知当前w和b，设δ±=min{|b-bmin|,|b-bmax|}，执行以下步骤。随机采样7个得分作为b<〈fk,w〉

2 实验结果与分析

实验在配置了Intel酷睿i3双核2.4 GHz，4 GB RAM的台式机上进行实验，采用MATLAB与C++混合编程，并利用CellC软件进行辅助计数。实验的对象是生产线上的水杯、啤酒、药片，以及荧光显微镜细胞图像，细胞图像来自文献[13]，并与文献[10]、文献[14]和文献[15]进行评估比较。

2.1 不同情形的实验比较与分析

实验测试结果如表1所示，其中“较小”指的是细胞图像，“较大”指的是在该数据集的图像中添加了少数虚假的较大细胞[13]。“大—小”指的是在混合细胞(包括“较大”细胞)上进行训练，并且在仅包含较小细胞的图像上进行测试。数据集中的每个图像包含250个细胞。结果表明：与文献[14]的监督密度估计方法相比，所提目标检测机制具有更高的准确度。表1中霍夫变换的结果误差较大，这主要是由于不完整目标造成得分范围很广，使得寻找一个合适阈值进行出现检测变得困难。

表1 测试结果

此外，如表1所示，本文从图像中提取出的DPM比其他方法的准确度更高，这是因为本文使用的分块反复出现和相互关联是从整个数据中恢复的，而非从单一实例中推导得出。当在包含少数较大细胞的数据集上对本文方法以及文献[14]方法进行训练时，文献[14]方法在仅由较小细胞组成的图像上的性能欠佳，但本文的用户辅助可避免对训练数据的特定性。

为了进一步比较，将本文方法与文献[10]、文献[14]和文献[15]方法进行比较，采用更多其他的数据和图片。实验包括15个参与者和5个图像，为每个参与者随机选择测试方法和图像顺序。表2给出了在这些用户辅助程序的每次迭代时的平均计数误差。其中，H1表示误报，H0表示漏报，“点击”为鼠标总点击次数，最后一列为总处理时间，加粗数据为最优数据。本文方法在时间栏的括号中给出了预处理时间(已记入括号外的时间内)。结果表明，文献[15]和文献[10]方法的精度较差。文献[14]稍优，本文所提计数程序能够以较少的用户时间和精力(鼠标点击)实现了最高的计数准确度。当考虑总目标计数时，本文方法的准确度依然相当高。这主要得益于利用图像中目标外观的绝对数量自动对参数进行恢复，允许目标产生一定的几何变形，具有较高的计数准确度。

表2 用户辅助程序每次迭代时的平均计数误差

2.2 大量目标检测与计数实例

图4给出了本文方法和文献[14]方法所生成的样本图像和检测到的目标，瓶装水图像是目标透视变形所得，其中，“#”表示鼠标点击的次数。以图4(a)为例，(213/250;H1:0,H0:37,#:10)的意思是：文献[14]统计出213个目标(总目标为250个)，误报H1为0个，漏报H0为37个，鼠标点击数为10次。由图4可知，所提方法可以检测统计出更多的目标。虽然本文使用的特征不具备对此类变换的不变性，但每个尺寸均有足够数量的实例，因此本文方法可以找到足够的辨识分块。

图4 各方法检测结果

3 结论与展望

本文提出了一种用于图像重复目标定位和计数的方法，基本思想是利用图像中目标反复出现的绝对数量，抽取图像内容，并使用其自身的分块搜索重复出现的目标，通过相关分析得出DPM的形状。实验结果表明，所提方法能够实现更准确的重复目标检测。

但所提方法在严重遮挡或目标形变很大的图像中，无法识别足够数量的重复分块和分块出现。且没有旋转或缩放变换，因此在此情况下，所提方法可能表现不佳。这将是未来研究和改进的方向。