【计算机视觉】Grouping and model fitting

标签（空格分隔）： 【图像处理】

说明：本系列是整理课程计算机视觉（英语）的笔记所成，不对之处还望指出。

这一讲的主要内容有：hough transformation，least squares fitting，Incremental line fitting，RANSAC方法，fitting using probabilistic model，E-estimator，optical flow等。

记得上一讲中分析列一下segmentation与grouping的区别，segmentation是将similar的像素cluster为一个个region，便于统一处理，而grouping则是在global上将similar的像素的潜在的structure给找出来，比如找出一条直线，circle等。而本文所要讲的就是用来将一组similar 的像素点grouping，找到合适的model fitting。

##fitting 就是找到一个参数对象来表示一组tokens。它是针对的global，对所有的set内部的points，而只盯着某几个看，是不行的。有三个主要的问题：用什么object来表示这组tokens最好呢？有多少个objects呢？token到底属于哪一个objects呢？可以用line，circle或者ellipse等。

##Hough transform ###算法思想 哈弗变换，是一个参数估计技术，使用了voting mechanism，每一个数据点都对参数进行投票，获得最大投票分数的参数就是最后的winners。 比如a line：

细想一下，在(x，y)空间，（m,c）决定一条直线，那么对于（m,c）空间，(x，y)则决定一条直线，也就是说知道了（x,y）set集合N，就可以在参数空间找到N条直线，如果在数据空间，N个点是在同一条直线上，那么对应到参数空间，对应的N条直线也就相交于同一点，这个点对应的就是数据空间中直线的参数(m，c)。所以对于不理想的数据，在参数空间可以定义一堆累加器，对于每个累加器统计N条直线中有多少是过这个累加器的，找出最多的那个累加器，它所对应参数空间的点，就是所谓的winner。

通常使用直角坐标，对于数据空间到参数空间的转化有些许的不方便，因为对于与坐标轴平行的直线，可能无法转化。通常采用极坐标系进行转化。 ###算法细节 具体的细节，不用说，这种思想是非常好的。voting的机制。 来看看算法的具体说明： 将参数空间恰当的量化了，比如如果参数在[0,1]和[0,1]之间，都均匀的分成10份儿，那么就得到了一个有$10\times 10=100$个取值解的参数空间。将每个cell都初始化为0，作为一个累加器。然后对于image 空间中的每一个point，对应到参数空间绘制一条曲线，这个曲线经过的累加器就自增1。具有最大值的累加器就是这个set的合适的modeling parameters。

###算法分析 有三个问题：第一个是如何确定每个cell多大呢？太小了很显然噪声影响大，太大了精度不高啊，区分不了不同的lines。第二个是如果累加器出现了多个peaks呢，那么你要输出几条lines呢？第三个是哪些数据点是属于lines的呢？这个问题可以通过对votes贴上标签，那个数据点投票给了哪个lines。

所以，在具体实现中很难得到令人满意的结果：噪声和cell size

##line fitting by least squares 这个没啥可说的，实际上就是linear regression，最小化的是vertical或者是y上的平方差，通常这样的操作是不太好，因为实际上如果是line的话，我们希望最小化的实际上应该是点到line的这个距离，所以一种方法是将代价函数转变为垂直距离。但是还有问题，特别是出现了孤立的点的时候，这个平方项使得误差变得更大，大部分的minimum都是用来minimize这个噪声点了，所以使得拟合出来的曲线错误较大。记得在Ng的机器学习课上还讲到了local weighted linear regression，就是根据样本分布进行分段拟合，然后加权好像是。

另外就是如果我们知道有多少个lines存在，那么如何去找到这些lines呢，如果我们知道哪些点属于哪些line的话，就比较容易了。下面三个方法strategy可以实现。

##incremental line fitting 将所有的数据点按照curve排开，从前两个points开始，逐渐增加points，如果一直refitting的好的话，就一直增加，直到出现问题为止。将line加入到line list当中。然后重新开始一轮，这新的一轮不包括已经fitting过的点，不然就是重复了。一直迭代到剩下的points很少为止。这一点似乎有点像是local weights linear regression。

##K-means line fitting 思想是先假设有K个lines，可能是随机的平均分布；或者是假设一些点分属于某些lines；这是初始化嘛！ 下面是迭代聚类： 将每个点分配到离他最近的那个line上，然后重新refit。一直重复这个过程直到收敛。实际上就是K-means的思想。就是EM算法或者说是 alternative optimization technique。

##分析一下fitting的robustness性质 large errors来自：outliers，即孤立的噪声点，或者说是并不是来自这条lines的data points；还是说这些large error可能导致平方误差退化严重，导致fit biased，incorrect等。 所以鲁棒性的方法应当是试着减少large errors的影响。

##M-Estimator 这个算法的思想改进平方误差代价函数，用一些小的d代替$d^2$，对于比较大的d，干脆让它接近一个常数，也就是类似一个当d较大的时候，误差函数接近于平滑，常数，即当d变动很大，而代价函数却增加很少。一般是通过ln对数函数来进行处理。$\sum_i\rho (r_i(x_i,\theta);\sigma)$一个非常好的example就是$\rho(u;\sigma)={u^2\over u^2+\sigma^2}$，这个方法的问题是最小化是数值分析的，通常具有多个最小值，可能比较困难。

实际上想找到合适的参数值是比较困难的。

##RANSAC随机采样一致算法 ###算法思想及issue 重点说一下Random sample consensus（一致）算法，随机均匀的选择一个足够小的子集，去fit，将所有close to 的认为是signal，而将其余的认为是noise，然后再refit，再进行筛选，重复多次，选择最好的。

问题是：执行多少次？通常要enough到我们认为足够好的line为止；最小的子集指的是？通常是能够进行fit的最小的数量，比如line就是2，circle就是3，等等；close意味着啥？这取决于问题是啥；什么是个好的line呢？足够多的数量的点nearby，被fit。

###算法实现 n表示最小数量的点，比如对于fit line，n=2，对于fit circle，n=3； k表示迭代次数； t表示认为一个点close或者fit well的threshold； d表示声明一个model fit well所需要的nearby的points的最小数量。

从数据中draw n个数据点，随即均匀； 然后fit； 对于out of sample的每个数据点，测试distance到model的距离，对比t，如果比t小，则close； 如果有超过d个数据点close这个model，那么认为它是一个好的model，fit well。重新fit它使用所有这些points，并将结果加入到好的fit的集合中；

重复以上操作k次；

从这个好的集合中利用fitting error作为标准，找到最好的fit model。

###算法特点 RANSAC是一个非常general的方法，可以用来fit lines,circles,或者更加复杂的几何。也可以用来fit其他种类的model，不一定是几何结构；这也有一个非常general的idea，hypothesize and test，随机hypotheses，如果一个小的points能够产生一个hypothesis，它就工作的很好；如果他能够很好的区别一个好的和坏的model的话，他工作起来也非常好。

另外，在双目视觉特征点匹配的时候曾经提到过，对于stereo vision，两个camera有一个基础矩阵F或者M，叫做什么约束来着，可以通过8个匹配的特征点来求解这个基础绝阵。我们得到了一组匹配点，paris，现在要remove掉那些假的，匹配不好的pairs，就可以使用RANSAC算法来做。具体的过程可以参看OpencV那本书中的过程。主要的应用就是随机选择8个paris，然后求解基础矩阵，判断其余pairs是否符合，认为是close，就是利用RANSAC来做。

##fitting using probabilistic model 这个最后推出的结果实际上跟linear regression一样，思想是让数据$x_i$服从均匀分布，让拟合出来的模型上加一个零均值的gaussian noise。最大似然准则来处理，得到的结果与linear regression似乎一样。这个可复习一下Ng机器学习内容，for detail。

##missing variable problems 实际上将推出混合高斯模型和EM算法，具体同样可以参考Ng教授的课程笔记。 这里想说的就是对于许多问题，如果一些变量知道的话，通过最大似然准则就能很好的解决，是很多时候是不知道的。这类问题就是潜在变量问题。 fitting：如果我们知道了每个token是来自于哪一条line的话，决定这些line的参数将比较简单。 segmentation：如果知道了每个像素是来自于那个segment，它们对于决定segment parameters也将非常容易。 但是我们不知道，这些参数属于未知的，这个时候采用EM或者alternative optimization的方法，就可以很好的解决。

下面以Mixture models为例： 数据是来自于一些简单sources的mixture，比如通过flip 一个biased的coin，如果它头在上，产生line points，如果尾在上，产生一个noise point。

对这样的情况：两个成分混合：

x对应的observation，$\theta_1$是第一个mixture component的参数，比如line，$\theta_2$是第二个mixture component的参数，比如noise。而$\pi$是这个biased coin的混合权重。

混合模型是很难fit的，如果要通过最大化似然函数来做，descent很难获取，必须使用数值方法，而通常会有好多local minima。

##motion segmentation 运动分割，意思就是将根据运动一致性作为分割similar的标准，将运动一致的pixels分在同一个region中。采用的方法就是optical flow，光流法。

光流法去年就已经学习过了，认识的也比较清楚，但是从来没有往分割上想过。现在想来，真是有点死学了。 三个关键的假设是：brightness constancy（亮度一致，相同的point的project在每一帧都是相同的），small motion（相邻两帧像素的dx，dy都不大），spatial coherent（neighbors内的points运动具有一致性）。

有了这三个条件，就可以求解光流方程了。通过一个5x5的window内部运动一致性，可以拓展到25个方程，over-determinted。不再多说了。

这里要注意的是要想求解，选择points应当慎重，对于那些flat region中的像素，它没什么特征，周围的像素都一样，所以根本无法计算，不可靠。那么edge呢，实际上也不太好，因为它在边界上是相同的，或者说是边界两侧是相同的，这也不太好，最好能够找到各向异性的corner point才能计算。对应的是High textured region。

那么所谓的运动分割，那就是将image sequence分割到不同的layers，每个layer都有一致性的运动。

【待补充】：关于harris corner detector的学习，涉及到几种不同的特征，flat区域，edge，和corner。

课程笔记