1. 从边线提取说起为什么八邻域是绕不开的一课做智能车视觉的朋友应该都有同感摄像头图像处理这部分看起来思路就那么几条——二值化、提取边线、算中线、判断元素可真到了赛场上图像一抖、光线一变问题全冒出来了。尤其处理赛道边界的时候最让人头疼的不是“找不到线”而是“找到一堆杂七杂八的东西”噪点、反光、赛道外的物体全被当成边线车就跟着乱跑。我最早做这块用的是最简单的逐行扫描每一行从左往右找第一个跳变点当成边界。这个方法实现起来很快十几行代码就搞定但有个致命问题一旦赛道断线、反光导致某一行的黑白跳变不止一次或者边线斜率太陡比如环岛入弯的位置逐行扫描就疯了。它会把噪声当成边界也会把同一行里第二个跳变点忽略掉导致提取出的边线断断续续中线的计算结果也就没法看。后来我开始研究八邻域追踪才真正把边界提取这件事做踏实了。八邻域本质上是一种基于像素邻接关系的边界跟踪算法它不依赖“逐行找跳变”这种行扫描逻辑而是从一个已知的边界点出发按某种方向顺序去找下一个边界点像沿着墙走一样一步一步把整条边界串出来。这样得到的边界是一个有序点列天然带有连续性比逐行扫描拿到的“每一行的点拼起来的线”稳定得多。这篇文章是系列第六篇我就把八邻域从原理到实现在智能车场景下的应用完整拆一遍包括边界跟踪的细节、代码怎么写、为什么会踩坑、以及它在十字、环岛、断路这些典型元素上的实际表现。适合正在调车的参赛选手也适合刚接触图像处理、想理解“边界追踪到底是怎么一回事”的朋友。2. 八邻域追踪的核心思想沿着墙走而不是每一行重新找2.1 先理解“八邻域”这三个字八邻域的定义本身不复杂对图像里的任意一个像素它周围8个相邻像素上、下、左、右、左上、右上、左下、右下就是它的八邻域。处理二值化图像时我们关心的是“一个白色像素周围的八个位置里哪些也是白色”。边界点则是另一个关键概念。在一张二值化图像里如果某个白色像素的八邻域里既有白色又有黑色那它就是一个边界点。八邻域追踪的基本思路就是从一个已知边界点开始查看它周围8个方向找到下一个满足条件的边界点然后以这个新点为起点继续找一步一步把边界串成一条链。这个过程很像在一个迷宫里摸墙走你左手一直贴着墙顺着墙走最终一定能绕着墙走回原点。边界追踪也是这个逻辑只不过“墙”是赛道白色边界和黑色背景的交界线“摸墙”的方向则由我们预设的搜索顺序决定。2.2 内边界和外边界方向顺序决定一切实现八邻域追踪时有一个容易被忽视的细节搜索方向顺序不同追踪出的边界性质就不同。如果我们用顺时针方向搜索比如从右方开始依次是右、右下、下、左下、左、左上、上、右上追踪出来的通常是白色区域的内边界也就是贴着白色区域边缘走的那条线。反过来如果用逆时针顺序搜索则会追踪出外边界。对应到智能车场景我们通常需要的是内边界。原因是这样的赛道在二值化图像里是一个白色连通区域我们想提取的是赛道边缘也就是“白色区域与黑色背景交界”的这条线。按照顺时针方向从某个边界点开始走会始终贴着白色区域的边缘走也就是赛道内侧的边缘这正好是我们要的边线。如果方向顺序选反了可能会得到背景那一侧的外边界虽然在简单场景下两条线差别不大但到了有杂物、锥桶甚至是赛道外浅色物体的时候就会明显偏掉。2.3 起点怎么找从图像底部的中间搜索边界追踪不能凭空开始必须先找到一个边界起点。起点找不好后面全是白搭。智能车上比较稳定的做法是从图像底部那一行从中间位置往两边扫描找到第一个黑色到白色的跳变点作为某一边边界的起点。这样做的理由是车正前方近处的赛道在图像底部而且正常行驶时赛道一定出现在画面中间区域从这里找起点基本不会找到赛道外的东西。还有一种更稳的做法不只在底行找而是从底行的中间往左、往右各扫一次分别作为左右边线的起点。如果底行中线附近全白或者全黑比如车已经压线了可以向上多扫几行直到找到边界点为止。这个“向上找起点”的兜底逻辑非常重要因为比赛时车不可能永远处在完美的居中位置压线、出界的情况迟早会遇到。找到起点后就从它开始做八邻域追踪。追踪过程中记录每个点的坐标放到一个数组里这就是最后得到的边界链。2.4 追踪终止条件闭环、超长、还是走丢八邻域追踪不能无限跑下去必须设置终止条件。常见的终止条件有三个第一个是回到起点形成闭环。这种情况最理想说明边界找完整了。对于常见的赛道元素比如十字、直道、弯道边界大概率能闭合成环但如果是断路元素边界本来就不闭合这时候不能等闭环要防止死循环。第二个是追踪点数超过设定上限比如超过图像的行数乘以列数。一旦达到上限就强制停止防止程序卡死。这个上限可以设得宽松些代价只是多浪费一点计算时间但能避免异常情况下无限循环。第三个是“走丢了”也就是找不到下一个边界点。这种情况通常出现在噪点成片、边界断开的位置或者起点选在了一个孤立白点上比如一小块反射光斑。走丢后当前得到的边界链虽然不完整但仍有一定参考价值可以选择保留已追踪的这段也可以直接丢弃重新找起点。我实际用下来最省心的组合是“回起点闭环”作为正常结束同时用“超过最大点数”作为强制退出两者配合就可以覆盖绝大多数情况。判断“走丢”则通过返回状态码提醒上层逻辑由上层决定这一帧边线是否可用。3. 动手实现一个简洁的八邻域边界追踪函数3.1 数据结构的选择与思考写八邻域追踪数据结构不外乎两种数组和栈。数组方案最直接开一个固定大小的坐标数组比如Point edge[IMG_H * IMG_W]然后把追踪到的点依次存进去。这个方案的优点是逻辑简单、遍历方便后续计算中线、拟合曲率都直接对数组操作就行缺点是固定大小写死了极端情况下边界点太多会溢出太少又浪费内存。栈方案则更贴近追踪过程本身把边界点压栈弹出找下一个点。但实际用下来我发现纯栈方案在智能车上并不好用因为后续处理时我们经常需要访问边界的中间点、需要知道边界长度用栈的话还得先出栈转数组多了一层搬运。所以我的建议是主数据结构用数组但借助一个“待检查点栈”来辅助宽度优先式的扩展。也就是把当前边界点的八邻域里所有符合条件的点都找出来按优先级排序压入一个临时栈再从栈里弹出优先级最高的那个作为下一个边界点继续走。这样既保证了追踪的连续性又不会漏掉分叉处的其他候选点。3.2 核心代码实现与逐步解释下面是一个跑在竞赛单片机平台上的八邻域追踪实现语言用C风格偏嵌入式没有malloc全部用静态数组。#define IMG_W 188 #define IMG_H 120 // 二值化图像数组1代表白色赛道0代表黑色背景 extern unsigned char binary_image[IMG_H][IMG_W]; // 边界点存储 typedef struct { unsigned short x; unsigned short y; } Point; Point left_edge[IMG_H * IMG_W]; Point right_edge[IMG_H * IMG_W]; // 8个方向偏移顺序为顺时针从右方开始 const char dx[8] {1, 1, 0, -1, -1, -1, 0, 1}; const char dy[8] {0, 1, 1, 1, 0, -1, -1, -1}; // 判断点是否在图像范围内且为白色 static unsigned char is_white(int x, int y) { if (x 0 || x IMG_W || y 0 || y IMG_H) return 0; return binary_image[y][x]; } // 在指定行上从start_x开始向dir方向扫描找到黑白跳变点 // 返回找到的点的坐标找不到则返回 -1 static int find_start_point(int row, int start_x, int dir, unsigned short *out_x, unsigned short *out_y) { int x start_x; while (x 0 x IMG_W) { if (binary_image[row][x] 1 (x dir 0 || x dir IMG_W || binary_image[row][x dir] 0)) { *out_x x; *out_y row; return 1; } x dir; } return 0; } // 八邻域追踪一条边界返回边界点数找不到起点返回0 int trace_boundary(int start_row, int start_x, int dir, Point *edge) { unsigned short sx, sy; int found find_start_point(start_row, start_x, dir, sx, sy); if (!found) return 0; int cnt 0; int cur_x sx, cur_y sy; int prev_dir 4; // 初始方向设为左表示从左边进入起点 int search_start; edge[cnt].x cur_x; edge[cnt].y cur_y; cnt; while (cnt IMG_H * IMG_W) { // 核心技巧下一个点的搜索方向从“来向的后一个方向”开始 // 这样可以保证边界连续不会走回头路 search_start (prev_dir 1) % 8; int found_next 0; for (int i 0; i 8; i) { int d (search_start i) % 8; int nx cur_x dx[d]; int ny cur_y dy[d]; if (is_white(nx, ny)) { cur_x nx; cur_y ny; prev_dir d; found_next 1; break; } } if (!found_next) break; // 走丢 edge[cnt].x cur_x; edge[cnt].y cur_y; cnt; // 回到起点并周围没别的点说明闭环了 if (cur_x sx cur_y sy cnt 3) { break; } } return cnt; }3.3 代码里最重要的一句search_start 的设定这段代码的核心就在search_start (prev_dir 1) % 8这一句。它的意思是每到一个新点优先从“来时的方向的下一个方向”开始搜索而不是每次都从方向0开始。举个例子说明为什么这样写。假设当前点的坐标是(10, 10)上一步是从右边方向0x1走到这个点的说明(11,10)这个位置是黑色的。如果我们下一个点又从方向0开始找每次都会先看右边那个黑点白白浪费一次判断更重要的是如果搜索方向没有规律很容易出现“来回走”的情况——从A走到B下一步又从B回到A形成死循环。从prev_dir 1开始搜索就等于告诉程序“我刚从右边来右边是黑墙那我就不看右边了从右下开始顺时针转着找。”这是一种贪心策略每一步找的都是在“靠墙”前提下的下一块白斑能保证边界链的连续性和方向一致性。这个方法本质上和很多图像处理教材里的“边界跟踪”是一致的只不过针对智能车的二值化图像做了精简。理解了这一句后面所有的调试都会顺畅很多。3.4 为什么这里没有用递归图像处理教材里八邻域经常和“连通域标记”一起出现而连通域标记的经典写法是递归。但递归在单片机上是禁区——栈空间小稍不注意就爆栈重启而且递归调用本身的压栈开销对图像这种动辄几万像素的数据量来说完全不可接受。所以实际工程里必须把递归改成循环。上面给出的实现本质上是循环迭代的边界追踪不存在操作系统栈溢出的风险即使图像最坏情况下边界点有几千个也只是一个静态数组的写入不会出现调用栈爆炸。如果你之前在PC上用OpenCV写过递归版的连通域标记转到单片机上时请务必改写成循环或栈模拟这是从“能跑demo”到“上了真车不崩”的关键一步。4. 八邻域在赛道元素识别里的具体玩法4.1 边线提取逐行扫描和八邻域配合使用很多人以为用了八邻域就不需要逐行扫描了其实不是这样。我实际在工程里是把两者结合用的先用逐行扫描快速计算每条边线的行坐标得到一个“每行边界点在哪”的粗略结果再用八邻域追踪对边界点排序剔除离群点把断开的边线补起来。逐行扫描的结果不是最终边界而是给八邻域提供起点、给后续中线计算提供行对应的映射。真正的边界连续性由八邻域保证。这么做的好处是逐行扫描即使出现噪点误判也只会影响起点选择不会带偏整条边线因为八邻域追踪一旦开始后续点完全由边界链决定不再依赖逐行的独立性。4.2 中线计算与方向控制有了左右边线最常用的办法就是逐行取中点// 计算中线 float mid_x[IMG_H]; for (int row 0; row IMG_H; row) { if (left_y[row] 0 right_y[row] 0) { mid_x[row] (left_y[row] right_y[row]) / 2.0f; } }但这里有个问题两边边线长度可能不一样特别是环岛或者十字区域某一边的边界点明显多于另一边。如果直接按行号取中点可能出现某一行左边有点、右边没点中点就算不出来。八邻域追踪出的有序边界链在这里就有优势了因为边界链是有序的我们可以从边界链的第一行开始往下逐行找到最近的左右点配对。如果某一行缺失边界点就用相邻行加权平均补一个虚拟点。这样算出的中线连续性比单纯逐行扫描强很多方向控制的抖动也会小很多。4.3 十字、环岛、断路这些元素的判定依据八邻域追踪出来的边界链除了算中线还有一个更大的用处通过边界的形状特征来判断当前赛道元素。以十字为例。十字的本质是路面左右两侧都有赛道延伸出去体现在边界上就是左右边线在某一行附近出现明显的“向外拐”的特征。如果用八邻域追踪出的边界有多条闭合子边界或者一条边界在某一点突然拐弯接近90度就有理由怀疑是十字。再以断路为例。断路区域的赛道中间有一段是黑的体现在二值化图像上就是白色的赛道连通域中间出现一条黑色的断开带。八邻域追踪的边界在断路处会走不完整——要么边界链长度明显比正常值短要么闭环位置不在底部。我们可以定义一个“边界链完整度”指标实际追踪到的边界长度除以理论完整边界长度。完整度低于某个阈值时判定前方可能是断路或者大曲率弯道被遮挡。环岛的判定则更依赖边界链的曲率变化。环岛入环处的外侧边线会出现连续的大曲率弯折曲率方向还会从一侧反向到另一侧。计算边界链上每三个连续点构成的向量夹角变化就可以提取出一个粗糙的曲率曲线再根据波峰波谷特征判断是否进入环岛。4.4 边界链方向的额外信息八邻域追踪出来的边界链自带方向信息这一点用好了能做出很巧妙的元素判断。具体来说如果追踪右边线时边界链的方向是从下往上、再往右拐说明右侧赛道正在向外张开可能是环岛入口或十字如果方向是从下往上、再往左收拢可能是弯道合流或坡道。方向的变化本质上是边界的凸凹变化而凸凹性恰好在八邻域追踪的方向序列里体现得很直观。我在实际代码里维护了一个“方向变化累积量”int direction_change 0; for (int i 2; i cnt - 2; i) { // 计算三点构成的两个向量叉积判断拐向 int cross (edge[i].x - edge[i-1].x) * (edge[i1].y - edge[i].y) - (edge[i].y - edge[i-1].y) * (edge[i1].x - edge[i].x); if (cross 0) direction_change; else if (cross 0) direction_change--; }这个direction_change累计量在直道上基本接近0大弯道会有明显的正向累积环岛则会先正向再反向利用这个特征可以辅助元素切换。它比单纯看某一行边界点变化稳定得多因为它是基于十几二十个点的统计结果单个噪点影响不大。5. 真车调试中的性能算账八邻域到底慢不慢5.1 复杂度分析为什么不用担心八邻域追踪的复杂度是O(N)N是边界点个数。对于一张188×120的图像即使赛道全部点都是边界极端情况几乎不可能也就是22560次循环真实场景下赛道边界点大约在几百到一千多个完全在单片机的承受范围内。从时间上讲假设主频150MHz的单片机每条循环语句编译后大概几个周期1000个边界点大约执行8000到10000条指令加上二值化和其他处理整帧图像处理预算如果是15ms八邻域这部分的耗时完全可以控制在1ms以内。我做过一个粗略的计时TC264平台188×120灰度图像二值化约2ms八邻域追踪左右边线共约0.5ms中线计算加元素判断约1ms整帧处理不到4ms完全有余量再做更复杂的元素识别。所以“八邻域太慢”这种担心在竞赛级别图像分辨率下不存在。5.2 内存占用怎么算内存方面左右边界各开一个Point edge[IMG_H * IMG_W]数组一个Point用4字节两个数组最大占用约180KB这明显太大了必须精打细算。竞赛单片机通常是几百KB的RAM不能这么浪费。实际优化方法是不需要存储全图边界点只需要记录每个行号上边界点的x坐标以及边界点的总数。也就是只保存left_x[IMG_H]和right_x[IMG_H]一个行号存一个x坐标内存占用瞬间降到480字节对MCU来说几乎可以忽略。那完整边界链还用不用用但不是每帧都用。当需要判断元素十字、环岛时可以临时再走一次八邻域拿到完整边界链判断完就丢弃节省平时内存。5.3 静态数组还是动态分配嵌入式C里我强烈建议用静态数组不要用malloc。原因有三点第一动态分配会产生内存碎片长时间运行后可能分配不出连续的边界数组程序表现会越来越不稳定。第二单片机上的malloc实现不一定有成熟的内存管理有的平台甚至是简单指针递增用多了很容易踩到未定义行为。第三竞赛调试时需要反复修改帧率和分辨率静态数组配合宏定义改起来最方便编译期就能发现数组越界的问题。一句话单片机上的图像处理凡是能用静态数组解决的内存就别用动态分配。6. 调试八邻域时我踩过且你大概率也会踩的坑6.1 噪点导致的边界链“打转”八邻域追踪最怕的不是慢而是图像里有孤立噪点。一个单独的白点周围8个方向都是黑如果你以它为起点开始追踪第一次搜索就会找不到下一个点得到一个只有1个点的边界链。虽然不影响程序跑但这个链会被上层误判成“前方断路”或“边界中断”。更麻烦的是如果噪点成对出现比如两个相邻白点追踪就会在两点之间来回反复直到达到最大点数才退出。这种情况在直道上特别容易发生表现为边线提取结果一会儿正常、一会儿抽风图像行坐标突变极大。解决办法有两个方向一是从源头去噪二值化前先做一个3×3中值滤波或者二值化后做一次腐蚀再膨胀二是在追踪时加一个“最小边界链长度”的过滤追踪完如果边界点数小于某个阈值比如20就丢弃这个边界链不做后续计算。两个方法组合使用基本能杜绝噪点引发的大部分异常。6.2 方向顺序选错结果完全相反我第一次实现八邻域时图省事把8个方向从左上开始按逆时针排列采样时发现边界链始终在赛道外侧走算出的中线和实际中线偏了好几行。排查了很久才发现是搜索方向顺序的问题。前面说过顺时针搜索得到的是白色区域内边界逆时针得到的是外边界。这个顺序不能凭感觉来必须结合你所用的坐标系。如果图像坐标系是x向右、y向下最常见的情况那么“顺时针”到底是哪几个方向要自己画个图推导一遍不能照搬教材里的数组。调试时的验证方法也简单把追踪到的边界点叠加打印在原图上用串口或SD卡存下带标记的图像肉眼看一下边界链是贴着赛道内侧还是在赛道外面。这一眼就能发现问题不用反复猜测。6.3 起点选的太鲁莽边界链从中间断掉起点搜索逻辑如果只在底部行的固定位置左右找遇到压线或车偏的时候很容易扫不到跳跃点直接返回找不到起点整帧图像都没有边线输出。我的改进方法是做一个“起点搜索金字塔”先在底部行找找不到就往上移5行再找再找不到就继续往上移最多上移到图像中部。同时左右两个方向分别独立找左右边线起点互不影响。这样即使车压线、某一边几乎全白或者全黑也能从其他行找到至少一条边的起点。6.4 边界链长度上限设置不合理导致误判有的朋友把所有堵死的条件都算在“闭环”上结果遇到断路元素时边界链无法闭环程序就一直在追踪直到撞上最大值才退出。这个“最大值”如果太大一帧图像的处理时间就会被拖长帧率掉得厉害如果太小正常的大弯道边界都可能被截断元素判断随之出错。我建议把上限设成图像总行数的2到3倍。比如120行的图像上限设240360。正常赛道边界不会超过这个数断路时也能在几十毫秒内退出不会拖垮帧率。6.5 图像二值化阈值对边界追踪的影响最后说一个容易被忽略但影响巨大的点二值化阈值。八邻域追踪本身就是基于二值化图像的阈值选不好直接导致边界链波动。比如阈值设得太高赛道边缘一些灰度值略低的区域会被当成黑色导致边界链在靠近摄像头远端的位置被切断阈值设得太低赛道外的浅色背景也会被当成白色边界链会“跑出”赛道追到背景杂物上。调八邻域前一定要先确认二值化图像的稳定性。我常用的验证方式是把二值化图像和原图叠在一起输出到上位机看边缘是否贴合赛道真实边缘。如果贴合度差先调阈值再调八邻域不要跳过图像质量直接调算法参数那样只会越调越乱。还有一个经验动态阈值比如大津法比固定阈值在智能车上更稳因为比赛场地的光照变化太大固定阈值早晚会翻车。但动态阈值也要注意场景比如赛道上强烈反光时大津法的分割效果可能还不如调整好的固定阈值。实际做法是准备多套阈值根据图像上半部分的平均灰度自动切换。7. 写在最后八邻域之外还要想清楚什么八邻域边界追踪这条路我走通之后回头看它真正解决的核心问题是“连续性”。逐行扫描给出的边界点是相互孤立的每个点只跟同一行的信息相关而八邻域给出的边界链每个点都跟上下左右临近点关联天然带有几何结构这让后续所有处理都变得更扎实。但也要说清楚八邻域不是万能的。它解决的是边界提取和连通域追踪的问题不能解决元素分类的所有问题。一场比赛下来元素判断的准确性更多依赖你对赛道几何特征的建模以及多帧图像之间的状态机切换。八邻域只是让边界数据更干净、更有序给你一个能稳定提取特征的基础。给刚开始做智能车图像处理的朋友一个建议不要一上来就铺开把十字、环岛、坡道全做了。先把左右边线提取做到极致稳定让边界链在每一帧都能正确闭合再考虑往上叠元素识别。我见过很多队伍死在边线不稳这步却以为是自己元素判断逻辑不够复杂其实问题出在图像处理的第一层。我自己的调试习惯是每次改完八邻域相关代码先在直道上跑100米确认边界链不丢、中线不抖再上弯道。直道都稳定不了弯道上就别提了。这算不上什么高级技巧但真的能帮你省下大量在赛场上不知所措的时间。