凝聚算法是一种用于视觉序列及其他动态系统中目标跟踪的概率方法。它属于粒子滤波器家族，后者通过一组带权重的随机样本（称为粒子）来表示系统状态的概率分布。名称“condensation”是“条件密度传播”（Conditional Density Propagation）的缩写，反映了其随时间传播条件概率密度的核心操作。该算法于20世纪90年代中期提出，作为一种实用的视觉跟踪方法，特别适用于杂乱环境中移动目标的跟踪，而传统卡尔曼滤波器假设线性动力学和高斯噪声，在此类场景下往往不适用。
该算法以递归的预测-更新循环运行。在每个时间步，它根据前一粒子集的权重按比例抽取一组新粒子，这一过程称为重采样或选择。随后，每个被选中的粒子根据运动模型进行传播，以预测目标的新状态，通常加入随机噪声以反映不确定性。最后，算法衡量每个预测粒子与观测图像或传感器数据的匹配程度，并根据该似然度赋予权重。加权粒子集随后近似目标状态的后验分布，估计位置通常为加权均值或权重最高的粒子。
历史发展
凝聚算法由迈克尔·I·乔丹及其同事于20世纪90年代在加州大学伯克利分校开发。基础论文《凝聚，，用于视觉跟踪的条件密度传播》于1998年由迈克尔·伊萨德和安德鲁·布莱克发表，他们当时分别任职于牛津大学和麻省理工学院媒体实验室。该工作建立在早期粒子滤波方法之上，如尼尔·戈登、大卫·萨尔蒙德和阿德里安·史密斯于1993年提出的自举滤波器，以及序贯重要性重采样技术。该算法专门旨在解决卡尔曼滤波器在视觉跟踪中的局限性，其中目标运动可能高度非线性，且观测模型可能因遮挡或背景杂乱而呈现多模态。
算法细节
凝聚算法可分为四个主要步骤。首先，初始化：从初始先验分布中抽取N个粒子，每个粒子权重相等。其次，选择：从当前粒子集中有放回地抽取一组新的N个粒子，其中选择某粒子的概率与其权重成正比。此步骤将粒子集中在高似然区域。第三，预测：每个被选中的粒子通过动态模型传播，例如随机游走或恒定速度模型，并加入高斯噪声以表示过程不确定性。第四，测量更新：每个预测粒子通过似然函数与当前观测进行比较，并相应更新其权重。随后循环对下一帧重复。
该算法的一个关键特性是能够同时维持多个假设。由于粒子可以分布在后验分布的不同模态上，算法能够在临时遮挡或模糊情境下跟踪目标。粒子数N是一个关键参数：粒子过少会导致近似效果差，而过多则增加计算成本。典型实现使用数百到数千个粒子，具体取决于状态维度和观测模型的复杂性。
应用
凝聚算法已广泛应用于计算机视觉和机器人学。其主要用途是视觉跟踪，例如在视频序列中跟踪人的头部或手部、在交通监控中跟踪车辆，以及跟踪铰接物体的姿态。它也被用于医学成像，例如在超声序列中跟踪心脏运动，以及在增强现实中估计相机姿态。在机器人学中，该算法支撑了蒙特卡洛定位，这是一种利用粒子滤波器让机器人在已知地图中估计自身位置的方法。该算法的灵活性还促使其用于语音识别和音频源分离，其中状态空间为声源的位置或身份。
局限性与扩展
尽管有其优势，凝聚算法也存在已知的局限性。基本版本存在粒子退化问题，即经过几次迭代后，大多数粒子的权重可忽略不计，浪费计算资源。重采样可缓解此问题，但可能导致样本贫化，即粒子集失去多样性，尤其在低噪声场景下。已提出多种扩展方法来解决这些问题，包括系统重采样、辅助粒子滤波器和无迹粒子滤波器。该算法还需要精心设计的似然函数，这在复杂场景中可能具有挑战性。在实践中，粒子数和运动模型参数的选择显著影响性能，且这些参数通常通过经验调优。
与其他方法的关系
凝聚算法是更广泛的粒子滤波器类（也称为序贯蒙特卡洛方法）的一个具体实例。它与自举滤波器和采样重要性重采样滤波器密切相关。在机器学习的背景下，粒子滤波器用于状态空间模型，如具有连续状态的隐马尔可夫模型，以及强化学习中的策略评估。该算法还与一般的蒙特卡洛方法相关，后者利用随机采样来近似复杂概率分布。与卡尔曼滤波器相比，后者为线性高斯系统提供最优估计，凝聚算法虽非最优但通用性更强，可处理非线性动力学和非高斯噪声。这种通用性使其成为计算机视觉领域的标准工具，并仍是概率机器人学和视觉跟踪中的基础技术。
参见
- 粒子滤波器
- 卡尔曼滤波器
- 视觉跟踪
- 蒙特卡洛方法