1. flood fill
10多年前，在学习孙家广老师的《计算机图形学》的时候，就知道了flood fill算法。在一个连通区域内部指定种子点，种子点的颜色就会像水一样溢满这个区域。一种常用的实现是用如下的递归方式:

Flood-fill (node):
 1. If node 不在区域内，返回.
 2. 设置node为目标颜色，并且对于node的上下左右4个(或8个)邻域neighbors(node)，做如下操作：
     Flood-fill (neighbors(node));

这样的程序书写容易，但调试起来麻烦，而且C语言教材还特别提到，这种嵌套式的递归调用让程序有堆栈溢出的危险。所以，通常采用非递归的方式来进行处理。

Step.1 给定深色区域内部的一个种子点，把它加入队列中。

Step.2 开始扫描这个队列。可以看出队列中的点是已经标定区域（2的区域）的边界点（称为frontier points），作为候选点，标为1。

Step.3 移除标为2的点，只保留frontier points

Step.4 重复Step2～3，直到队列为空，结束。

这个队列Queue-list相当于递归调用的堆栈空间，但是与递归方法相比，逻辑更加简单明了。可以看出队列中存放的是候选的位置，程序的主要工作就是扫描这个队列数组，同时进行两种操作，一是检查其中的候选项能否被加入到我们定义的目标集合中去；二是把目标集合中元素的邻域点加入到列表中。由于有新元素不断地加入，队列长度会不断增加（当然这个长度的上限不会超过图像尺寸），为了控制队列长度，可以同时把队列中不用的元素删去。比如，上面图中删去那些标记为2的点。这样当这个队列为空的时候，表示所有的候选点都处理完毕，而且也没有新点加入，程序就结束了。

实际上这也可以看作是连通区域标定问题（Connected components labeling,Matlab函数为bwlabel），因为目标集合的模型已经固定，就是"颜色相等"一个条件，那么使用顺序扫描图像的方法就可以把这个区域标出来。通常图像是按照逐行扫描的方式存储的，就是说访问上下两个邻域点要跨过一整行的数据。而从上面图中描述的flood fill算法来看，需要对图像任意区域的随机读取，假设有一个区域，它的候选点的增长方向是跨越图像的第一行到最后一行，那么图像指针就可能需要在图像的第一行和最后一行之间跳来跳去，它的实现效率显然就不如CCL来的高。能否按scanline的方式顺序读取图像也限制了算法在硬件设备上的实现，比如对于算法的芯片实现来说，片外存储器DRAM只能按顺序读写，不能实现想读图像的哪个区域就读那个区域，这样就需要很大的片内buffer（相当于SRAM）来预先存储更多行的图像内容，这会使芯片面积增加。这也是为什么大多数机器学习和图像处理算法无法完全植入芯片的原因。

2. Region growing
以上写的是常见的一种区域增长算法的应用，它定义的‘目标集合’指一个灰度值相等的区域，也就是说这个集合的共同属性是颜色相等，并且是图像上的连通区域。这种共同属性的定义还可以有其他的形式，比如上面的例子可以进一步，允许区域内点的像素值的变化不超过一个范围，比如可以定义点x与均值的差小于一的阈值:|Ix-Imean|<T。关于这样的区域增长，网上有一个很好的matlab例子：

http://www.mathworks.com/matlabcentral/fileexchange/19084-region-growing   （它对应的论文是Seeded region growing）

它和上面的Flood-fill的不同之处在于，队列中的每个候选点加入到目标集合中会导致这个区域的参数（可以看成模型参数）这里是均值Imean的变化。有的点加入后会导致均值变化很大，有的点加入后均值变化很小。这样，它的程序里不是当候选点x满足条件|Ix-Imean|<T就马上加入到目标集合中去（这种方法见我改写的程序 region_growing.rar）的，而是每次从候选列表中选出|Ix-Imean|最小的点x加入的。与我改写的程序相比，它最后生成的区域的最大最小值与均值的差都不会超过T。产生这样的差别的原因在于随时加入的新点，有可能导致区域均值远远偏离初始值，从而使目标集合中有些已经加入的点不再满足约束|Ix-Imean|<T了。

3. Fitting line segments by Region growing
直线检测算法LSD（文章名字叫 LSD: A Fast Line Segment Detector）就是一个利用区域增长方法的例子。我也做了个类似的程序，把图像中提取的局部最强的边缘拟合成直线：只有满足直线约束的候选点（这些点来自canny算法的前两步）才加入到目标集合中，直线模型用两端点表达，同时也保存了法线方向（sin,cos值），另外线段是有方向的（在下图中线段用绿线表示，起点用红点标志），即让较暗的区域保持在直线的左边。

这样的方法用于fiducial marker detection中。首尾相接的4个线段才有可能是目标。然后利用正方形四条边计算homography和R,T。最终的AR效果如下图：

再来一把茶壶：

基于边缘的AR marker detection要比基于thresholding的方法鲁棒性好，但更加鲁棒的方法应该能应对部分遮挡。这还是个问题，留待来年解决吧。