物体检测技术和聚类算法是计算机视觉、模式识别和智能系统领域中的两个重要课题,其中物体检测技术研究的是如何利用计算机在图像或视频中准确、高效地检测出某种类别的物体;聚类算法研究的是如何把相似的物体或数据组织到一起。它们是人机交互、环境感知以及图像理解等高层次任务的基础,具有巨大的应用需求。本文针对这一需求,着重进行了两方面的研究:第一部分研究物体检测技术中一个重要的内容,即行人检测技术;第二部分研究半定规划松弛的聚类算法。主要的工作和创新如下:(1)首次把中心对称的局部二进制模式特征(CS-LBP)和中心对称局部三进制模式特征(CS-LTP)引入行人检测,设计了描述能力强、计算简单的密集描述特征。CS-LBP和CS-LTP分别是著名的LBP和LTP的变种,结合了著名LBP(LTP)特征和HOG特征的优点,在提取形状信息的同时还能提取显著的纹理信息,并且计算简单。基于CS-LBP和CS-LTP,首先设计了密集描述CS-LBP特征;为了获得描述空间信息的能力,设计了金字塔结构的密集描述CS-LBP和CS-LTP特征,并用积分图像(Integral Image)提高金字塔结构特征的提取速度。在INRIA行人数据库上的实验结果表明,论文设计的特征能够取得优于经典的HOG特征和金字塔HOG特征的性能。(2)利用“核技巧(Kernel Trick)”,设计了基于距离度量的非线性核SVM分类器,在具有优良分类性能的同时,还具有快速的分类速度。首先利用bin-to-bin距离中的L1距离,设计了L1距离核SVM分类器,它等价于著名的直方图交互核SVM分类器;其次,由于cross-bin距离具有比bin-to-bin距离更好的度量特性,利用cross-bin距离中的推土机距离(Earth Mover’s Distance,EMD),设计了EMD距离核SVM,并提出了一种特征提取和分类器设计相结合的行人检测方法;再次,利用特殊的近似方法把设计的非线性核SVM对特征进行分类的时间复杂度降低到O(n)(n为特征的维数)。INRIA数据库上的行人检测实验证明,本文设计的密集描述特征和非线性核SVM结合起来的行人检测算法具有良好的性能,超过了经典的金字塔HOG特征结合HIK SVM的行人检测方法。(3)研究了利用特征组合提高行人检测性能的方法。本文首次利用多核学习的方法组合常用的行人检测特征。首先用基于稀疏多核学习的方法,把本文涉及的一些密集描述特征组合起来,能取得比核函数平均特征组合法更好的性能;然后,研究了基于非稀疏多核学习的特征组合方法,它能比稀疏多核学习利用更多的有效特征。INRIA数据库上的实验结果表明,本文的特征组合方法能明显提高行人检测的性能。(4)研究了半定规划松弛的聚类算法。半定规划松弛聚类算法需要求解一类NP-hard的半定规划优化问题,现有方法求解该类问题的计算复杂度非常高。本文首先推导出半定规划问题的对偶问题,利用矩阵生成(Matrix Generation)算法把求解原问题转化为一个迭代求解过程;在每次迭代中,利用指数梯度下降(Exponentiated Gradient Algorithm)算法求解由矩阵生成算法产生的特殊结构最优化子问题,并利用原问题和对偶问题在最优解处应具有的关系作为迭代终止的判断条件。仿真结果表明,本文提出的矩阵生成算法和指数梯度下降算法能有效地求解半定规划约束的最优化问题,能够很好的适应矩阵尺寸较大时的计算要求。UCI数据库上的实验结果表明,本文的半定规划松弛聚类算法能取得比K-means算法和谱聚类算法更好的聚类性能。