此文系第16届智能车智能视觉组-上海交通大学AuTop战队开源算法讲解第二部分--边线提取，专栏及开源方案链接：

llo：第16届智能车智能视觉组-上海交通大学AuTop战队开源汇总

视觉巡线（二）边线提取

在得出一个良好的二值化后（我们采用的自适应阈值，几乎可以做到零调参），还需要从其中提取出赛道的边线。

一个比较常见的做法是从图像中间开始向两侧扫描，遇到的第一个黑色像素即为赛道边线，从图像下端向上重复上述过程。这种做法较为简单，但却并不是十分高效：

• 受赛道中央黑色物体（如AprilTag）或噪声的干扰。

• 无法得到向图像下方弯曲的赛道边线（弯道容易丢线）

• 计算复杂度大，最差情况下，近似遍历了整张图像。

这些问题也会相应的增加赛道元素的判断难度。

我们提出采用“迷宫法”进行边线提取。之所以称其为“迷宫法”，是因为从走迷宫中的“右（左）手法则”中得到的灵感，即采用右（左）手扶墙的方法一定可以走出迷宫。

由于赛道的边界线是一条连续的曲线（良好的二值化是前提），所以我们并不需要每次都从图像中央开始向左右两侧进行扫描，而是仅仅在图像下侧扫描一次，得到边界线的起始点后，沿着边界线“一直走”即可。而这个“一直走”的具体做法则是参考走迷宫的“右（左）手法则”。

想象在边界线的起始点处有一个面朝图像上方的小人，黑色像素为墙，白色像素为路，小人保持左（右）手扶墙向前走，直到走到图像边缘或者走到步数的上限，而其走过的路径即为赛道边线。

而对于小人的移动方法，可以分为3种情况。下面举例说明，黑色为墙，白色为路，绿色为小人当前位置，箭头为小人朝向，小人遵循左手扶墙（注意小人时刻保持脚踩白色，手扶黑色）

1. 小人前进方向被墙挡住。（即前进方向的像素为黑）

由于前进方向被挡住，那么小人只能被迫改变前进方向。同时由于需要保持左手扶墙，所以小人右转（同理，如果是右手扶墙则左转）

2. 小人前进方向没有被挡住，且遇到了墙角。（即前进方向的像素为白，且前进方向左前方为白，右手扶墙则判断右前方）

此时小人需要绕过墙角，同时为了保持左手扶墙，小人还会同时左转。

3. 小人前进方向没有被挡住，且当前不是墙角。（即前进方向的像素为白，且前进方向左前方为黑，右手扶墙则判断右前方）

此时小人向前走，并且不改变方向。

4. 小人前进方向被墙挡住。（即前进方向的像素为黑）

小人右转

5. 小人前进方向被墙挡住。（即前进方向的像素为黑）

小人右转

6. 遇到墙角（即前进方向的像素为白，且前进方向左前方为白，右手扶墙则判断右前方）

小人绕过墙角

7. 小人前进方向没有被挡住，且当前不是墙角。（即前进方向的像素为白，且前进方向左前方为黑，右手扶墙则判断右前方）

小人向前走

走到图像边缘，结束。

对于实际的赛道边线提取过程，针对赛道左边线，使用“左手”巡线；赛道右边线，使用“右手”巡线。该边线提取算法，对比常规算法具有以下优势：

• 只进行一次从图像中间向两侧找起始点的操作。受赛道内黑色物体干扰小。
• 可以提取到向图像下方弯曲的边线。弯道不易丢线。
• 计算量小。提取N个边界点，平均仅需2N次判断。

计算量优化

注意到上述算法是在二值化后的图像上进行的。而在上一篇文章（llo：第16届智能车智能视觉组-上海交通大学AuTop战队开源算法讲解(一)二值化的技巧）中曾提到过，自适应二值化是效果最好的二值化方法，但其计算量极大，如果每个像素使用7*7的区域计算二值化的阈值，那么对整张图片进行二值化可以等效为进行了7*7+1=50次全图遍历。这样的计算量是无法接收的（376*240分辨率计算一次需要大约200ms）。

但是，我们真的需要对整张图像进行二值化吗？在上述边线提取算法中，我们可以注意到，我们在找起始点和“迷宫法”巡线的过程中，仅仅用到了边界线周围很小一部分像素的二值化结果。这意味着，有大量的像素点是不需要对其进行二值化运算的。对于一张376*240分辨率的图像，如果在其中提取左右两个边线，每条边线上有240个点，那么平均我们只用到了2*240个点的二值化结果。如果可以省略不需要的点，我们的计算量平均可以减少188倍。

所以我们提出一边巡线一边二值化的算法。即进行“迷宫法”巡线时，直接输入原始灰度图像，当需要某个点的二值化结果时，才对其进行一次自适应二值化。

这样一个简单的优化，直接使得我们的算法运行速度极快，O3编译优化，最慢情况下也不会超过5ms一次完整的计算。这也是我们可以放心使用高分辨率（376*240）进行图像处理的原因。而不需要为了加快计算速度而牺牲分辨率。考虑到转向舵机50Hz的控制频率，该算法其实还有大量冗余算力可以使用，如果不是RT1064内存不够大，我们甚至可以使用最大768*480的分辨率进行计算，也不会使得控制频率低于50Hz。

SJTU-AuTop完整开源方案链接，如果觉得我们的方案对您有帮助，请在github上帮忙点个star吧:)

llo：第16届智能车智能视觉组-上海交通大学AuTop战队开源汇总