Lucas-Kanade(LK)算法原理介绍及OpenCV代码实现分析

Lucas-Kanade跟踪算法是视觉跟踪中一个很经典的基于点的逐帧跟踪算法。起初这个算法是用来求解stero matching1的,后来经过Carlo Tomasi2和Jianbo Shi3等人的发展渐趋成熟。Jianbo Shi提出了一种筛选跟踪点特征的方法,使得特征的跟踪更可靠。Jean-Yves Bouguet4详细阐述了如何采用金字塔方式实现LK算法以处理两帧之间特征点位移较大的情况。

问题阐述

首先我们来看一下我们要解决的问题是什么?LK算法是基于特征点的跟踪,而这里的特征点就是每个点对应的一个小窗口图像块,LK所要解决的是求解连续两帧图像相同特征点的位移问题。这里我们假设\(I\)\(J\)为连续两帧图像,其\((x,y)\)点的灰度值分别对应\(I(x,y), J(x,y)\)。设\(\mathbf{u}=[u_x,u_y]^T\)是图像\(I\)上一点,LK算法的目标是在图像\(J\)找到一点\(\mathbf{v}= \mathbf{u} + \mathbf{d} = [u_x+d_x,u_y+d_y]^T\)使得点\(I(\mathbf{u})\)和点\(J(\mathbf{v})\)是同一个位置。为了求解这样的点,LK求解这两个点对应的小窗口内像素的相似度。设\(\omega_x\)\(\omega_y\)分别是点左右扩展的窗口范围,这样我们可以定义如下residual function为

\[\epsilon(\mathbf{d})=\epsilon(d_x,d_y)=\sum_{x=u_x-\omega_x}^{u_x+\omega_x}\sum_{y=u_y-\omega_y}^{u_y+\omega_y}(I(x,y)-J(x+d_x,y+d_y))^2\]

窗口大小为\((2\omega_x+1)\times (2\omega_y+1)\),通常情况下\(\omega_x\)\(\omega_y\)的值为2,3,4,5,6,7。

Read More

一个关于visual tracking的benchmark

自从工作后,就很少接触visual tracking这个领域了。最近下班没事,浏览博客看到几篇CVPR2013关于visual tracking的paper,其中有一篇名为Online Object Tracking: A Benchmark的paper对目前该领域几乎大部分优秀算法做了一个分析和评估,提出了更为严谨合理的评估方法。作者是University of California at Merced的一个博士后,以前好像是自动化所的一个博士。他针对29个算法,测试了50个视频,并且标记了所有视频的groundtruth,其耐心和毅力值得敬佩。

分析算法特性

当然,作者不是简单的罗列出所有的算法,而是针对目前的存在的算法,总结出四个模块:Representation Scheme,Search Mechanism,Model Update,Context and Fusion of Trackers。个人觉得前三个模块的确是visual tracking最重要的部分,Representation Scheme方面,算法的提出相对热闹些:基于图像原始像素值(如Lucas and Kanade稀疏点的光流法),直方图(如color histograms, histograms of oriented gradients (HOG)等),Harr-like特征,binary feature,基于sparse representation等等。Search Mechanism方面,可以用的方法相对就会比较单一。对于跟踪算法是基于最优化函数框架的算法,跟踪物体的位置通过local optimum search确定位置。而对于算法是基于binary classifier的,方法主要有两种:particle filter和dense sampling search。Model Update方面,对于binary classifier就是训练样本的更新。对于subspace-based tracking就是物体外观图像块的update。

Read More

几种联通区域标记的算法介绍

联通区域标记(Connected Component Labeling)是图像处理里面常用的一个技术,它是用来检测二值图像中联通的区域,在许多跟踪检测算法中充当目标区域检测的作用。常见的CCL(Connected Component Labeling)包括Two-Pass的方法和One-Pass的方法,这里pass就是扫描的遍数,Two-Pass就是扫描两遍的算法,One-Pass就是扫描一遍的算法。下面仅就这两类算法中有代表性的算法做一个简单的介绍。

Two-Pass

传统的Two-Pass:

关于该算法的一个形象的描述可以参考博客Labelling connected components – Example。具体的流程是:

  1. 逐行扫描图像上的点,检查每个点是否是前景点,如果不是,继续扫描;
  2. 检查该前景点的左边的点和上边的点
  • 如果有一个为前景点,则为当前扫描点标记和此点相同编号;
  • 如果两个都是前景点,则选择标号小的,为当前扫描点标记编号;这里注意如果两个都是前景点且标号不同,需要把标号小的点设为标号大的点的父节点,以方便第二遍扫描的时候用并查集算法(参考利用不相交集实现等价元素的聚类)合并;
  • 如果都不是,则赋值目前标号label,label++(label初始值为零);
  1. 再次扫描图像,利用并查集算法合并联通的不同的label的区域。

Read More

利用不相交集实现等价元素的聚类

说到聚类,相信大家最先想到的应该是k-means,但是我们知道k-means必须指定聚类的个数,而且聚类初始点的选取也很大影响最后聚类的效果。虽然有一些方法(如k-means++)可以设置较为合理的初始聚类点,但仍然需要指定聚类的个数,但有时我们并不知道一堆数据中有多少个类,这样就使得聚类变得没法下手。这里介绍一种利用一种树型数据结构——不相交集,实现的数据聚类方法。

不相交集(disjoint-set),也叫并査集(union-find)是保持一组不相交的动态集合。给定一系列数据,我们首先假设每个元素是一个集合,通过集合的查找合并实现等价元素的合并,从而实现相同类别的元素的聚类。这里两个元素等价的标准是由自己设定,取决于具体应用。例如目标检测中滑窗检测目标时用于聚合方框,其等价标准就是方框的重叠率的大小;再比如图像处理中联通区域标记的应用,其等价标准就是两个点是否联通。

Read More

浅析霍夫变换检测直线

霍夫变换在检测直线,圆和椭圆等形状有着很广泛的应用,它通过一个投票过程实现对不同形状的参数的估算。这里这个投票过程是指把二值图像空间的点映射到参数空间,记录参数空间中不同参数对应的点的累积,从而实现形状上的点对参数的投票过程,然后选取局部累积最大值作为检测到的形状的参数输出。

那为什么叫它霍夫变换,当然是和霍夫有关系的。1962年保罗.霍夫(Paul.Hough)写了一个叫Method and Means for Recognizing Complex Patterns的专利,其中有用到该方法检测粒子物理中云图中的直线和曲线。目前广泛应用的霍夫变换是1972年由 Richard Duda 和 Peter Hart 提出的[1],该方法提出了用 angle-radius 替换 slope-intercept 作为霍夫变换的参数空间,简化了计算。后来 Dana H. Ballard的一篇 Generalizing the Hough transform to detect arbitrary shapes 使得霍夫变换在计算机视觉领域开始广泛应用。

Read More