〔两行哥〕OpenCV4Android入门教程之算法系列（一）

你知道一条简单的直线是怎么显示在计算机屏幕上吗？有人说，就是一个个像素点啊，将一个个像素点连起来就显示为一条直线了。但是这些点是如何排布的呢？通过什么样的算法展示给坐在电脑前面的你呢？让我们一起来研究一下。
有能力的同志可以先参考：维基百科-Bresenham's line algorithm，看不懂没关系，两行哥带你一步一步分析。

一、计算机是如何显示直线的

在屏幕上我们看到了一条直线，但是它真的是一条直线吗？我们用最简单的方法验证一下：
打开Windows的画图，画一条直线，看到了什么？让我们看看图1。

图1 一条直线

貌似是一条直线，但是我们放大后看看，看到了什么？如图2所示，这并不是一条直线，而是一条条较短的水平线，近似地拼接成一条直线。

图2 放大后的直线
为什么会出现上面的现象？让我们再次放大这条直线，如图3所示：
图3 直线栅格化
图中的黑色直线是我们理想中要显示的目标直线（实际上并没有被绘制出来）。但是在栅格图像中（即位图，比如我们的计算机显示屏），像素点是一个个分割的小型区域（如图中的方格），如果想要表示一条直线，只能通过一定的算法，确定要显示的目标区域（如图中的标记为灰色的方格），这些目标区域就组成了一条近似直线的图像，展示给用户，这就是我们真正看到的直线。

显然，如果我们确定了直线的起始点startPoint和结束点endPoint，我们还需要一定的算法来确定这两点中间还有哪些方格需要显示（变成灰色），哪些方格不需要显示（依旧为白色），然后再绘制一条“类直线”，接下来，我们就来建立数学模型，看看这个算法是怎么实现的。

二、基本Bresenham直线算法

Bresenham直线算法是用来描绘由两点所决定的直线的算法，它会算出一条线段在n维光栅上最接近的点。这个算法只会用到较为快速的整数加法、减法和位元移位，常用于绘制电脑画面中的直线。是计算机图形学中最先发展出来的算法。

这里就引入我们计算机图形学中Bresenham算法，让我们以上图3为基础，从建立坐标系开始，一点一点进行推演。

图4 建立栅格坐标系

如图4所示，我们建立了左上角为原点的坐标系（通常计算机图形学中的原点位于左上角），x轴正方向向右，y轴正方向向下。以每个小方格（栅格）的中心（如图4中栅格中的红色点）作为标准点，以每个栅格的边长为坐标轴单位长度，即每个栅格的边长计为1。
观察上述建立的坐标系，原点为左上角第一个栅格的中心。假设目标直线的起始点坐标为图中的（x1，y1)，终点为图中的（x2，y2），并且斜率介于0与1之间，即与x轴正方向的夹角小于45°（图中用深黑色直线表示），那么如何确定出与这条直线拟合度最大的栅格呢（图中的灰色方块们）？
观察图中的相邻栅格B1（x3，y3）以及栅格B2（x4，y4），两者满足x3=x4且y4-y3=1。在Y轴方向上，栅格B1与目标直线的偏差为d1，栅格B2与目标直线的偏差为d2。比较d1与d2的大小，若d1<=d2，则认为距离目标直线最近的栅格为B1，若d1>d2，则认为距离目标直线最近的栅格为B2。

在目标直线穿过的所有栅格中，取目标直线在X轴方向的投影，对于投影区间[x1，x2]中的每个x的值，在Y轴方向上都有一个或多个栅格与之对应。如果仅有一个栅格与之对应，显示该栅格（图中即标灰色），如果有多个栅格与之对应，取距离目标直线最近的栅格显示（标记为灰色）。

还以上文的相邻栅格B1（x3，y3）与栅格B2（x4，y4）为例，B1、B2都被目标直线穿过，并且它们拥有同样的X轴坐标（两者满足x3=x4且y4-y3=1）。此时对于目标直线在X轴方向上的投影区间[x1，x2]中的x3值而言，有两个不同y值的栅格B1（x3，y3）和B2（x4，y4）与之对应。我们取距离目标直线较近的栅格来显示。上文我们已经假设过，每个栅格的边长为1（坐标轴单位长度为1），在Y轴方向上，如果栅格（x，y）中心与目标直线的偏差d<=1/2，即显示该栅格，如果栅格中心与目标直线的偏差d>1/2，即显示Y轴方向的下一个栅格，即栅格（x，y+1），此栅格的中心与目标直线在Y轴方向上的偏差为d - 1。而对于目标直线在X轴方向上的投影区间[x1，x2]中的x1值只有一个y值为y1的栅格（x1，y1）与之对应，直接显示该栅格即可。
弄清楚原理之后，可以开始我们的推演了。在图4的坐标系中，目标直线对应的代数表达式为：

y = （ y2 - y1 ） / （ x2 - x1 ） * （ x - x1 ） + y1

下面我们用伪代码来绘制这些最拟合目标直线的栅格们。
假定drawPoint（x，y）为绘制该栅格的方法，drawLine（startX，startY，endX，endY）为绘制直线的方法。

//startX：直线的起点坐标x
//startY：直线的起点坐标y
//endX：直线的终点坐标x
//endY：直线的终点坐标y
function drawLine(startX，startY，endX，endY){
    int diffX = endX - startX;
    int diffY = endY - startY;
    float error = 0F;//记录栅格中心与目标直线在Y轴方向上的偏差值，如果error > 0表示直线在该栅格中心的下方，如果error < 0，表示直线在该栅格中心的上方
    int y = startY;
    for( x = startX ; x <= endX ; x++){
        draw( x , y );
        error  = error + diffY / diffX;
        if( error > 0.5F ){
             //如果在Y轴方向上，该栅格中心与目标直线的偏差大于0.5F，就使用Y轴方向上的下一个栅格，即y = y + 1
             y = y + 1;
             //因为使用了Y轴方向上的下一个栅格，所以需要重新计算栅格中心与目标直线的偏差值
             error = error - 1.0F;
        }
    }
}

三、Bresenham直线算法扩展

上面我们假设目标直线是斜率介于0与1之间，并且由左上至右下的直线，现对其进行扩展。

1.对于从右下到左上（绘制直线的方向与之前相反）：

此时判断是否startX大于endX，如果是，将目标直线的起始点和终点进行交换即可；

2.对于负斜率（介于-1与0之间）：

此时目标直线的startX > endX，我们把偏差大于0.5F时y = y + 1改为y = y - 1即可；

3.对于斜率绝对值大于1：

我们不直接使用斜率大于1的目标直线，而是使用目标直线关于y = x对称的直线，此直线的斜率小于1。此时我们将计算过程中的x与y调换，同时将drawPoint（）方法的参数调换。
新增定义取value绝对值的方法abs（value），交换两个变量值的方法swap（ a ，b），此时的伪代码如下：

//startX：直线的起点坐标x
//startY：直线的起点坐标y
//endX：直线的终点坐标x
//endY：直线的终点坐标y
function drawLine(startX，startY，endX，endY){
    boolean needExchange = abs（endY - startY） > abs（endX - startX）
    if( needExchange ){//交换x与y
        swap( x1 , y1 );
        swap( x2 , y2 );
    }
    if( x1 > x2 ){//交换开始点与结束点
        swap( x1 , x2 );
        swap( y1 , y2);
    }
    int diffX = endX - startX;
    int diffY = abs( endY - startY );
    float error = 0F;
    int y = startY;
    for( x = startX ; x <= endX ; x++){
        if( needExchange ){
            draw( y , x );
        }else{
            draw( x , y );
        }
        error  = error + diffY / diffX;
        if( error > 0.5F ){
            if( y1 <= y2 ){
                y = y + 1; 
            }else{
                y = y - 1;
            }
            error = error - 1.0F;
        }
    }
}

至此，已经实现了完整的Bresenham直线算法。

四、Bresenham直线算法整数化

电脑处理浮点运算的速度比较慢，而error的计算是浮点运算。此外，error的值经过多次浮点数加法之后，可能有累积误差（计算机中浮点运算是不精确的）。使用整数运算可令算法更快、更准确。只要将以上所有的分数数值乘以diffX，我们就可以用整数来表示它们。唯一的问题是程序中的常数0.5F—我们可以通过改变error的初始方法，以及将error的计算由递增改为递减来解决。整数化后的逻辑如下：

//startX：直线的起点坐标x
//startY：直线的起点坐标y
//endX：直线的终点坐标x
//endY：直线的终点坐标y
function drawLine(startX，startY，endX，endY){
    boolean needExchange = abs（endY - startY） > abs（endX - startX）
    if( needExchange ){//交换x与y
        swap( x1 , y1 );
        swap( x2 , y2 );
    }
    if( x1 > x2 ){//交换开始点与结束点
        swap( x1 , x2 );
        swap( y1 , y2);
    }
    int diffX = endX - startX;
    int diffY = abs( endY - startY );
    float error = diffX / 2;
    int y = startY;
    for( x = startX ; x <= endX ; x++){
        if( needExchange ){
            draw( y , x );
        }else{
            draw( x , y );
        }
        error  = error - diffY;
        if( error < 0 ){
            if( y1 <= y2 ){
                y = y + 1; 
            }else{
                y = y - 1;
            }
            error = error + diffX;
        }
    }
}

有个疑问，为什么error的初始值取为diffX / 2呢？其实我们先将error由递增改为了递减，error取值0.5F，如果error递减后的值小于0，则对y进行相应操作。而我们的目的是将0.5F化为整数，因此将error乘以diffX，即error = diffX / 2。

至此，我们的Bresenham直线算法已经讲解完毕，这与我们OpenCV中的LineType参数有很大的关联。

五、LineType参数详解

OpenCV中LineType有三种类型：

LINE_AA = 16
LINE_8 = 8
LINE_4 = 4

先讲LINE_4和LINE_8。LINE_4和LINE_8表示绘制的直线为4连通直线或8连通直线。要理解4连通直线或8连通直线，我们先引入邻域概念，若存在栅格点P（x，y）：

1.四领域

图5 四邻域

如图5，像素P(x，y)的四邻域是：（x+1，y）、（x-1，y）、（x，y+1）、（x，y-1），即图中的4个黄色栅格。

2.对角邻域

图6 对角邻域

如图6，像素P（x，y）的对角邻域是：（x+1，y+1）；（x+1，y-1）；（x-1，y+1）；（x-1，y-1），即图中的4个黄色栅格。

3.八邻域

图7 八邻域

如图7，像素P（x，y）的八邻域是其四邻域和对角邻域的和，即图中的8个黄色栅格。
那么LINE_4和LINE_8代表的直线绘制上有什么不同呢？观察图8和图9：

图8 四连通直线LINE_4
图9 八连通直线LINE_8

图8中，点A的下一个连接点B位于点A的四邻域中，因此直线是四连通直线。图9中，点A的下一个连接点B位于点A的八邻域中，因此直线是八连通直线。这里留意一下，因为八邻域已经包含了四邻域，所以通常我们认为：点A的下一个连接点B位于点A的对角邻域中，此直线为八连通直线，而在四邻域中（在四邻域中一定在八邻域中）的话，我们依旧认为直线为四连通直线。
那么我们上文分析的直线绘制方法绘制出来的是什么直线呢？很明显是八连通直线。如何将八连通直线算法改造为四连通直线算法呢？留给读者自己思考（提示：y = y + 1时，x是否需要 + 1？）
至于LINE_AA，则是抗锯齿直线，采用了高斯滤波，本文就不详细介绍了，如果考虑性能，我们一般使用LINE_4和LINE8。

经过上文的分析，相信大家会对LineType参数的理解更深。我们下次再会。