2021, Vol. 47
2. 大连理工大学 计算机科学与技术学院, 辽宁 大连 116024
2. School of Computer Science and Technology, Dalian University of Technology, Dalian, Liaoning 116024, China
开放科学（资源服务）标志码（OSID）：
区域填充是指对图像中一块被封闭轮廓包围的区域重新着色。图像中区域的表达方式主要有：对于规则或近似为多边形的区域，使用顶点/边的形式来表达；对于较复杂的形状，用光栅图像来表达；为进一步压缩存储空间，用链码的形式来表达。
以顶点/边的形式表示多边形，采用射线法、弧长法进行逐点填充，或使用有序边表、活动边表、奇偶扫描转换算法进行逐行填充[1-2]。这些算法主要计算出射线、扫描线与多边形边的交点，利用奇偶规则来判断某个像素是否位于多边形内部，进而进行填充。
对于光栅格式的图像，区域填充问题可以用种子填充法来解决。光栅图像中的区域可以用两种方式定义：内部定义是区域内部像素具有一种特定颜色，而区域外部像素具有其他颜色；边界定义是区域轮廓上的像素具有不同于背景色的特定颜色。在内部定义区域上运行的种子填充算法称洪泛法[3]；在边界定义区域上运行的种子填充算法称边界填充算法[2, 4]。洪泛法和边界填充算法流程相似，仅在判断区域边界时存在细微差别。种子填充算法需要一个轮廓内部的像素作为种子点，算法从种子点开始，通过4连通或8连通规则向邻居像素进行填充。
FREEMAN[5]通过区域轮廓的起点和像素间的相对位置来记录区域轮廓线信息，该编码方式称为链码，具有节省空间、易于提取几何特征的优点。CAI[6]等研究基于链码的图像恢复方式，利用相邻像素间的相对位置对像素进行分类，从而决定哪些像素间的线段需要被填充。LIU等[7]提出一种基于链码并融合了边界点奇偶性检查和区域生长法优点的填充算法。研究者对基于链码的填充算法做了进一步优化[8-10]。
体图形学[11]广泛应用在建模、工业设计、医学影像中。将种子填充算法移植到三维空间以解决封闭空间的填充问题。针对该问题，FENG等[12]提出一种高效的三维种子填充算法。薛斌党[13]通过改进栈结构和入栈种子方法去除多余出入栈和回溯操作，提高算法效率。YU[14]等提出基于扫描切片的三维种子填充算法。
填充算法在地理信息系统、遥感数据分析[15]、计算机动画制作、目标识别[16-17]、图像重建[10]、区域覆盖[18]、工业设计[19-20]、医学影像[21]等方面有重要的应用。本文在异构平台上设计并实现并行反向填充算法，利用不同并行方案在CPU和GPU处理器上获取最佳参数。通过构建异构流水线处理模型批量处理图像，有效提高处理器的利用率和轮廓填充速度。
1 种子填充与反向填充算法在多数情况下，光栅格式图像可以直接获得，如卫星遥感、地质勘探、工业监控等场景，而顶点和链码表示的图像需做进一步提取处理。传统种子填充算法如图 1所示。
|
Download:
|
| 图 1 传统种子填充算法示意图 Fig. 1 Schematic diagram of traditional seed filling algorithm | |
种子填充算法的缺点主要有：1）使用深度优先堆栈来保存种子数据，每个像素点需进栈出栈一次才能完成填充，因此算法效率低；2）需人工交互，在每个封闭轮廓内指定一个像素作为种子，该缺点对于批量处理图像十分不利。
针对第1个缺点，PAVLIDIS等[1]提出扫描线种子填充算法，该算法只保存一条连续待填充线段最右侧的像素作为种子，堆栈的访问次数，提高填充效率。研究者从种子存储结构、像素访问顺序等方面对该算法进行优化[22-24]，进一步提高算法效率。陈卓等[20]在获取新种子点入栈阶段采用多线程并行方案，在一定程度上提升了算法的并行度。VUCKOVIC等[25]通过使用针对内存访问高度优化的线性图像数据结构[26]和DMA技术，从实现角度优化扫描线种子填充算法的效率。
针对第2个缺点，柳稼航[27]提出一种反向填充算法，先求出轮廓的外接矩形，进而在外接矩形上任选一点作为种子，确定该种子点一定位于轮廓的外部。反向填充算法如图 2所示。以此种子为出发点完成对轮廓外部的填充。将上一步的结果进行一次求反，即获得封闭轮廓内的填充结果。由于避免了人工指定种子，该算法适合工业上处理批量图像。例如，在流水线工件检测场景中，工业相机对流水线上工件进行拍照和处理，每秒可能产生数十帧图像。使用传统种子填充算法对图像中不规则封闭轮廓内部进行填充，需要人工在每张图片的轮廓内部指定一个像素作为种子，无法保证处理的可靠性和效率，反向填充算法则克服了这些缺点。
|
Download:
|
| 图 2 反向填充算法 Fig. 2 Conversely filling algorithm | |
随着半导体和光学技术的不断进步，视频和图像设备的分辨率越来越高，数据量越来越大。在民用方面，如苹果手机iphone11拍照最大分辨率达到了3 840像素×2 160像素（4K高清），视频录制分辨率也到了1 920像素×1 080像素（1 080P）；华为Mate30手机拍照最高支持7 296像素×5 472像素（40MP选项）；高清电视信号也采用4K高清标准。在工业方面，遥感技术、地质勘探、地图测绘、土地资源可视化等领域也产生海量的高分辨图像。目前，无论是扫描线种子填充算法还是反向填充算法都基于堆栈/队列的串行算法，无法充分利用多核、多线程、异构处理器的优势。例如，即使采用高性能的C++图形库OpenCV，对8 KB分辨图像进行一次填充需要约120 ms，每秒钟只能处理8.3帧。因此，处理高分辨、大批量的图像，设计高效率的种子填充算法非常有必要。
基于以上需求，本文提出了并行反向填充算法，在保留反向填充算法无需人工交互优点的同时，利用多核、异构处理器提高算法性能。
2 基于图连通的并行填充算法 2.1 相关概念为更方便和准确地描述算法流程，定义如下概念：
图像边界：矩形图形的四条边（border），即图像中坐标x=0、x=w-1、y=0、y=h-1的像素；
图像轮廓：待填充区域的轮廓线（contour/boundary）；
背景色：原始图像中背景颜色，本文采用灰度值0；
轮廓线色：原始图像中轮廓线的颜色是待填充区域和背景区域的分隔线，轮廓线内部为待填充区域，外部为背景区域，本文采用灰度值255；
结果外部色：填充结果中要求对轮廓外部填充的颜色，本文采用灰度值0；
结果内部色：填充结果中要求对轮廓内部填充的颜色；
外部边界种子：位于图像边界上的种子；
内部随机种子：均匀分布函数产生的非边界种子，可能位于背景区域、带填充区域、轮廓线上；
外部边界种子线程：以外部边界种子为初始填充点的线程；
内部随机种子线程：以内部随机种子为初始填充点的线程；
线程填充任务量：每个线程所填充的像素个数，衡量线程之间的负载均衡程度。
2.2 算法设计基于图连通的并行填充算法中，在图像的边界上放置若干外部边界种子，图像的内部放置若干内部随机种子。使多个线程同时从图像的内部和外部一起填充，从而提升算法并行度和填充效率。但也带来新的问题，即算法开始时，无法判定这些内部随机种子位于轮廓内部还是外部，其填充过的区域是否合理。为了解决该问题，为每个线程增加一个邻居堆栈来记录该线程在填充过程中与其他线程的相邻关系。在完成填充后，使用并查集算法来完成相邻区域的合并。
2.2.1 种子生成种子生成主要是生成M个外部边界种子和N个内部随机种子。
1）生成M个外部边界种子，在图像边界上选择M个点作为外部边界种子，为了简化算法，直接在图像的4条边界上选择若干像素作为种子，不求轮廓的外接矩形。
2）生成N个内部随机种子，利用随机函数在图像内部随机选择若干像素点作为内部随机种子。假设轮廓外像素点个数为X，轮廓内部像素点个数为Y，轮廓线上像素点个数为Z。随机种子的位置可能出现3种情况：（1）位于待填充区域外部，概率为X/（X+Y+Z）；（2）位于待填充区域内部，概率为Z/（X+Y+Z）；（3）位于待填充区域边界上，概率为Y/（X+Y+Z）。通常情况下Z远小于X和Y，故第3种情况出现的概率很小。
由于种子扫描线算法首先进行行填充，如果两个种子位于同一行，则这两个种子的填充区域会很快相遇，降低算法效率。为避免这种情况发生，在初始化时将种子尽量放置在不同的行上。具体做法是在图像内部以均匀间隔确定N条横线，然后在每条横线上用随机函数产生一个点作为随机种子点。
种子分布情况如图 3所示。图 3演示种子数量为16的分布情况（4个外部种子编号1~4，12个内部种子编号5~16）。
|
Download:
|
| 图 3 种子分布情况 Fig. 3 Seeds distribution | |
串行反向填充算法只启动1个线程，使用1个不同于原图中背景色和轮廓色的标签。对并行反向填充算法而言，以边界种子为起始点的线程填充区域位于轮廓外部；以内部随机种子为起始点的线程在填充时无法判定所填充的区域位于轮廓外部还是内部，填充结果是否合理。因此需要为每个内部随机种子线程指派1个唯一的填充标记，并在填充完成后对每个线程所填充的区域进行分析，剔除无效区域。如果使用256级灰度图像，每个像素用1 Byte表示，背景色为0黑色，轮廓线为255白色，则使用的标记为1~254。将标签1分配给外部边界种子共同使用，则最多可以使用253个内部随机种子线程来并行填充。对于需要同时运行更多线程才能发挥优势的GPU而言，1 Byte提供的标记范围不足以发挥硬件的全部潜力，所以在GPU版本中，使用双字节的unsigned short类型代替unsigned char类型来保存每个像素。
1）标记设定规则
外部边界种子线程可以确定其定位于待填充轮廓的外部，其填充区域也一定位于轮廓外部，所以外部边界种子线程全部使用同一个填充标记1。
在填充前无法判定内部随机种子线程的种子位于轮廓内部还是外部，其填充区域是否有效也待检测，所以每个线程使用唯一的填充标记。为简便起见，使用线程号作为填充标记。
2）填充规则
在多线程环境下，需要对种子扫描线算法的填充规则进行扩充。
对于内部随机种子的情况3，即种子落在轮廓线上（如图 3、图 4中的种子10）不做任何操作，直接结束线程。该情况在串行算法中不会发生，在并行算法中发生的概率也很小。
|
Download:
|
| 图 4 多线程填充后的结果 Fig. 4 Results after multithreading filling | |
对于外部种子线程以及内部随机种子的情况1（种子位于轮廓外部）和情况2（种子位于轮廓内部），按照以下规则进行填充：（1）当遇到一个未填充像素时（值为背景色0），填充为该线程自己的填充标记；（2）当遇到轮廓线（值为255）或图像边界（坐标超出图像范围）时，结束当前行填充，从堆栈中出栈新种子，开始上下相邻行填充；（3）当遇到其他线程填充过的像素时（值不为0，也不为255），不仅要按照标准的种子扫描线算法结束当前行的填充，还要将该像素的值（即其他线程的填充标记）记录到本线程私有的邻居堆栈中。为减少冗余数据，规定外部边界种子线程（填充标记为1）不用记录邻居关系。由于邻居关系具有对偶性，这个规定不影响结果的正确性。
多线程填充后的结果如图 4所示，此时图像中任意像素属于以下3种情况之一：1）位于被填充过的区域中，此时像素值为填充该像素的线程填充标记（1~254），如字母E内部被标签6、15填充，H的内部被标签8填充，轮廓外的部分被其他线程的标签所填充；2）位于未被填充过的封闭轮廓内部，某些封闭区域的内部可能没有落入种子，所以轮廓内部未被填充过，保持原来的值（背景色0），如字母G的内部；3）位于轮廓线上，轮廓线上的像素不会被任何线程填充，保持原来的值（轮廓色255）。
当所有线程完成填充后，每个内部随机种子线程的邻居堆栈中会记录与该线程填充区域相邻的标记。填充后的邻居信息如表 1所示。
|
下载CSV 表 1 填充后的邻居信息 Table 1 Neighbor information after filling |
种子8单独落在一个轮廓的内部，因此没有邻居；种子10位于轮廓线上，提前结束，没有进行填充，故邻居堆栈也为空。种子8和12位于同一轮廓内部，所以相互记录对方为邻居。其他种子均在堆栈中记录邻居的标签。
2.2.3 并查集算法合并连通区域该步骤是并行反向填充算法的核心。有些随机种子位于轮廓外部，有些位于轮廓内部。位于轮廓外部的种子特征是其填充过的区域必定直接或间接同边界种子的填充区域相邻，需识别这些区域并将其反转为结果背景色，剩余未被填充区域和被填充但与边界种子填充区域不连通则设为结果前景色。
利用上一步得到的邻居关系将相邻区域进行合并的本质是动态连接（Dynamic connectivity）问题。邻居关系具有自反性、对称性和传递性，该问题可以利用不相交集合森林的并查集（Union_Find）算法[28]来解决。并查集算法通过Find和Union操作，利用给出元素之间邻接联系，将元素划分成若干个集合，每个集合中的元素具有直接或间接联系。该算法的时间复杂度为O（N×（1~lg M）），其中N是相邻关系信息数量，M是合并后独立集合的数量。
在填充问题中，N是全部线程邻居关系的数量。在本例中，N=21，即算法记录了21条邻居信息。除了边界种子标签值1之外，其他标签的邻居关系存在部分冗余数据，例如线程5记录邻居关系（5，7），而线程7同样记录邻居关系（7，5）。冗余邻居关系记录处理可以提前结束。M是合并后集合的个数。在填充问题中，每个独立轮廓线会围起一个独立区域，全部轮廓外的部分则合并成另一个独立区域，因此当每个封闭轮廓内部都有种子时，M为图中轮廓数量+1。在本例中，字母G中没有包含种子，也没有产生邻居信息，所以没有形成一个独立区域，因此M=3+1-1=3。
并查集算法在运行初期，将每个填充标记看作一颗只有一个节点的树，全部标记的集合构成一个森林，用root数组来表示树中节点之间的父子关系。root数组中下标表示一个节点，而对应数组元素值则表示该节点的父节点。算法开始运行时，外部边界种子填充标记对应节点的数组元素值等于1，内部随机种子填充标记对应节点的数组元素值等于自己的下标，表示自己是自己的父节点，即该树目前只有自己一个节点。每个邻居关系对的加入都可能导致两颗树合并成为一棵。具体操作是在root数组中逐级向上查找邻居关系对中两个节点的根节点，如果两者的根节点不同，则将一个节点的根节点设置为另一个节点的根节点的父节点，完成两棵树的合并；如果两者根节点相同，说明属于同一颗树，这条邻居信息是冗余数据，不需再做处理。为了简便，规定合并时由值较小的节点充当父节点。全部邻居关系对处理后，得到若干棵合并后的树。但此时的树可能拥有较大的高度，不利于下一步查找工作。所以在完成合并后需对树进行路径压缩，将同一颗树中所有节点的父节点都设为该树的根节点。只需在root数组中进行一次查找，便可确定一个节点是某个指定根节点的子节点。
经过并查集算法处理后，可以得到若干棵树。将这些树分为以外部边界种子填充标记（值为1）为根的树和不以1为根的树。在本例中，节点集合{1，5，6，7，9，11，12，13，14，16}都以1为根，说明它们和边界种子连通，同属于轮廓的外部；而节点集合{10}和{6，15}分别以根6和10为根，同标记1不连通，可以确定其位于封闭轮廓的内部。并查集算法结果如表 2所示。
|
下载CSV 表 2 并查集算法结果 Table 2 Results of Union_Find algorithm |
得到并查集结果后，扫描整个图像，对每个像素进行判定和处理，规则如下：
1）如果该像素未被填充（值为0），则必然位于轮廓内部，需设为结果内部色，例如字母G的内部；
2）如果该像素位于轮廓线上（值为255），则可以根据填充要求设为结果内部色、外部色或者不变；
3）如果像素被某个标记填充，且在root数组中以该标记为下标的元素值为1，说明该像素和边界种子连通，位于轮廓外部，将其设置为结果外部色；
4）如果像素被某个标记填充，且在root数组中以该标记为下标的元素值不为1，说明该像素位于轮廓内部，将其设为结果内部色，例如值为6、8、15的像素。
至此，完成轮廓内部的填充，合并后与反转后的结果如图 5所示。
|
Download:
|
| 图 5 并查集算法填充结果 Fig. 5 Filling results of Union_Find algorithm | |
本文算法在填充阶段启动多个线程进行填充，每个线程的任务量和填充范围是不固定的，而是由种子附近的像素分布情况以及处理器的调度情况来决定，可能会出现多个线程同时访问同一像素的情况。理论上，为了避免线程间的竞争，需要在读写像素时使用互斥量来保证结果的正确性，但互斥机制有比较高的代价，导致大量线程等待，从而降低算法效率。
对算法进行分析和验证，认为有可能两个甚至多个线程同时读取同一个像素，判断其为未填充像素后，同时将该像素放入自己的种子堆栈，并在填充完当前行后将其出栈，并写入本线程的标签。
在不使用互斥量的情况下，无法避免出现多个线程写一个像素的现象，也无法确定多个线程的写入顺序，但可以保证最终必定有一个线程的标记会被写入，此像素不会被遗漏。由于这种情况一定发生在两个或多个线程填充区域的边界上，因此该像素最终被写入哪个线程的标记，都是合理的。发生竞争的线程会在各自的邻居堆栈里记录彼此相邻关系，这些具有相邻关系的区域在反转阶段都会被合并为一个区域。同样适用一个线程的填充区域将另一个线程的填充区域分割开的情况。因此这个像素被填充为哪个线程的标签都不会影响最终结果的正确性。在本算法填充阶段，无需使用代价高的原子操作、互斥量机制，放任线程间的自由竞争不存在死锁、死循环或像素遗漏的问题。
在算法反转阶段，由于每个线程分配的待处理像素是固定的，因此不存在竞争、同步问题。
2.4 填充阶段GPU堆栈的构造种子扫描线算法在保存种子和邻居信息时需要用堆栈数据结构。在CPU中实现该算法时，使用C++STL提供可以根据存储内容动态调整容量的std：：stack类。但CUDA不支持C++STL，复杂数据结构需要编程者自己实现，而在GPU中使用动态分配内存函数来实现具有动态调整容量功能的堆栈，其时间成本较高，因此使用定长数组和计数器变量来构造GPU堆栈。每个GPU线程和CPU线程执行的算法完全相同，利用CPU版本运行期间种子堆栈和邻居堆栈的统计信息来设定GPU堆栈的最大长度。CPU版本在启动不同数量的线程时，种子堆栈容量和邻居堆栈的使用情况如图 6所示（8 KB分辨率图像）。
|
Download:
|
| 图 6 堆栈使用情况（8 KB分辨率图像） Fig. 6 Stack usage(8 KB resolution image) | |
从图 6可以看到，在CPU多线程环境下，种子堆栈的最大长度为14，平均长度约为5。将GPU种子堆栈最大容量设置为16；邻居堆栈最大长度为6，平均长度约为2，将GPU邻居堆栈最大容量设为8。实验证明，此设置也可以处理8 KB分辨率图像时。像素坐标使用无符号2 Byte类型（最大65 535），每个像素的x、y坐标共占8 Byte，每个线程的种子堆栈需要8×16=128 Byte。邻居堆栈保存邻居标签信息，标签也使用无符号2 Byte类型，每个线程需要2×8=16 Byte。
待填充图像被多个SM共享，所以需放在全局内存中；邻居堆栈传回Host端，且访问频率低于种子堆栈，因此将其放在全局内存中。而种子堆栈是每个线程私有的，无需与其他线程共享，具有较高的访问频率且无需回传CPU，将其放在共享内存中来加快访问速度。Kepler架构[29]GPU可以提供最大48 KB的共享内存，每个SM的共享内存容量可以支持最多48 KB/128 Byte=384个线程同时运行。
3 实验设计与分析本文算法将多个种子放置在图像的边界和内部，多个线程同时从图像的边界和内部开始填充，因此填充效率高于单种子填充算法。该算法增加了记录区域邻接关系和使用并查集判断区域连通性步骤，则增加了算法的时间成本和空间代价。
3.1 实验设计 3.1.1 硬件配置实验平台为HP580 Gen 9服务器，XeonE7 10核处理器，160 GB内存。实验平台如表 3所示。
|
下载CSV 表 3 实验平台信息 Table 3 Experimental platform information |
实验中使用6种常见分辨率的图像作为测试数据，轮廓像素满足4连通规则。实验图像数据如表 4所示。
|
下载CSV 表 4 实验图像数据 Table 4 Experimental images data |
采用C++11提供的高精度chrono库，以μs为单位，对算法和函数进行测量。对GPU Kernel进行测量时，利用CUDA同步函数进行同步来确保准确计时。在算法之间进行横向比较时，以串行算法作为基准，采用相对于串行算法的加速比作为衡量手段。为保证客观和可移植性，在编译时使用默认–O0选项实现全部代码。算法运行100次并求平均值作为实验结果。只统计算法在CPU、GPU中处理的时间以及数据在CPU~GPU传输的时间。
3.2 算法流程对比相比传统反向填充算法，本文算法省略了求外接矩形步骤，增加用并查集算法对多线程的填充标记进行分类。
在初步实验中，根据种子数量不同，种子生成耗时在3~760 μs；并查集算法耗时1~2 786 μs。相对于需要大量读写内存，耗时达数十、数百毫秒的填充和反转过程，这两个步骤在算法总耗时中只占较小的比例。根据阿姆达尔定律，应该对占算法中较大比例的部分进行优化，将并行化重点放在填充和反转阶段，采用C++多线程和CUDA两种技术对这两个环节进行并行化，通过实验确定每个阶段的最佳参数。
3.3 算法最优参数获取 3.3.1 填充阶段采用C++多线程技术和CUDA技术来实现填充阶段的并行化，每个线程负责一个种子的填充。C++多线程实现的关键参数是并发线程数量（种子数量），而CUDA实现的性能不仅与线程数量（种子数量）有关，而且与Kernel中Block的配置有关，因此测试两者的全部组合，并从中选择6种不同分辨率图像上的加速比平均值作为衡量标准。填充阶段最优参数如表 5所示。
|
下载CSV 表 5 填充阶段最优参数 Table 5 Optimal parameters in filling phase |
采用最优参数配置时，虽然GPU线程数量远超CPU方案，但GPU填充实现的平均加速比（2.27）低于CPU（4.12）。主要原因是：
1）种子扫描线算法不适合SIMT执行模型
该算法具有三重循环和大量分支操作，易引起GPU线程分支，导致线程之间串行执行，进而导致性能急剧下降。
2）大量不规则全局存储器访问
GPU版本中，图像数据保存在全局内存中，具有较长的访问延迟。GPU的编程手册建议在显存中合理安排数据，以便能进行联合访问（coalesced access）。但每个线程的种子点和周围轮廓都不相同，决定属于同一warp多个线程发出的内存访存请求是不连续和不规则的。种子堆栈使用共享内存来实现，基于同样的原因，同一warp内不同线程以不规则的方式访问共享内存，也会导致延迟。
3）数据传输负担大
相对于CPU版本，GPU版本还存在数据传输负担，Kernel运行前需要将图像从CPU传输到GPU，运行后需要将数据返回CPU，降低了GPU的加速比。
启动较多线程才能发挥GPU的优势，而每个线程需要唯一的填充标记。为满足这个要求，将图像中每个像素用2 Byte表示，这样除了背景色和前景色外，还有65 534个值可以作为线程填充标记。但导致图像数组的内存占用量增加1倍，数据在CPU和GPU之间的传输耗费更长的时间。8 bit和16 bit图像的传递耗时对比如图 7所示（8 KB分辨率图像），可以看出使用CUDAMemcpy2D（）函数在PCI-E总线上传输数据时具有不对称性，GPU向CPU回传数据需要更长的时间，并且随着传输量的增加，这种不对称性越明显。该问题不仅存在填充阶段，在反转阶段也会影响算法效率。
|
Download:
|
| 图 7 8位/16位图像传输耗时对比（8 KB分辨率图像） Fig. 7 Comparison of transmission time with 8 bit/16 bit images(8 KB resolution image) | |
合并阶段是根据并查集算法结果，将第一阶段中被不同标记填充过图像中的像素分为同图像边界连通、同图像边界不连通、图像原来的轮廓，然后分别填充为结果背景色、结果前景色或保持不变。
CPU合并将图像自上而下分割为若干块，每个线程负责一块图像中像素的反转。
GPU合并为每个像素启动一个线程，线程数量由图像分辨率决定。鉴于图像的二维结构，将Kernel中的Block也配置为二维结构。为了获得最优性能，测试block.x、block.y两个维度上全部可能的组合（每个维度的测试范围从1~1 024，但一个Block中的线程数量上限为1 024，因此某些组合如256×8是非法组合）。GPU中每个线程需要读取一个像素，以像素值为下标查找root数组中对应元素进行标记，根据该标记向像素写入不同的值，图像数据和root数组都位于全局内存，因此算法性能对全局内存的访问效率比较敏感。
GPU合并过程的输入图像数据有两个来源：由CPU填充的中间结果和由GPU填充的中间结果。两者最大的区别在于图像像素位数不同。CPU填充时最佳种子/线程数量是110，因此每个像素使用8 bit的unsigned char表示。GPU填充时最佳种子/线程数量是32 768，需要用位长为16 bit的unsigned short类型。两者图像容量相差一倍，root数组长度（等于种子个数）相差32 768/110=297.89倍。因此，在数据传输效率和GPU全局内存访问性能上存在较大差异，导致同一算法表现出不同的平均加速比。反转阶段最优参数如表 6所示。
|
下载CSV 表 6 反转阶段最优参数 Table 6 Optimal parameters in reverse phase |
在填充和合并步骤通过CPU和GPU技术组合形成一个完整的算法，完成图像填充。不同技术的组合如表 7所示。
|
下载CSV 表 7 不同技术的组合 Table 7 Combination of different technologies |
串行算法作为加速比计算标准使用单线程、单个堆栈来完成填充与反转，作为有效性衡量标准的OpenCV实现使用cv：：floodFill（）和cv：：threshold（）函数分别完成图像的填充与反转。在实验平台上测试各种方案的性能，并计算不同组合相对于串行实现的加速比，如图 8所示。
|
Download:
|
| 图 8 相对串行不同组合的加速比 Fig. 8 Speedup of different combinations relative to serial | |
从图 8可以看出，并行算法在高分辨图像上的性能远高于低分辨图像。因数据量较小时，多线程并行带来的受益不足以弥补线程管理的开销。GPU+GPU组合略高于1的加速比，这是因为填充过程复杂的逻辑结构不适合GPU的SIMT执行模型。组合CPU+CPU、CPU+GPU则获得了超过3倍的加速比，高于OpenCV实现的性能（彩色效果见《计算机工程》官网HTML版）。不同组合各阶段耗时情况如图 9所示。
|
Download:
|
| 图 9 各阶段不同组合耗时情况 Fig. 9 Time consumption of different combinations in each phase | |
从图 9可以看出，不同组合中种子的初始化和并查集算法耗时只占非常小的比例，填充过程耗时占主导地位。在未使用GPU的组合中，合并/反转过程耗时占第2位；在使用GPU的组合中，数据传输占耗时的第2位，合并/反转过程占第3位。
3.5 批量图像流水线模型实际应用场景，如流水线工件检测中，往往需要对批量图像进行处理。对于填充和合并在同一设备上运行的组合而言，批量图像处理时间就是单个图像处理时间的叠加；而CPU+GPU的组合运行在异构平台上，对于批量任务，具有额外的优势，使得该组合具备进一步优化的可能：
1）CPU+GPU组合的填充阶段在CPU上运行，而合并阶段在GPU上运行，对于批量填充任务，通过合理安排相邻两张图像处理步骤之间的执行顺序，将异构平台构建为流水线，进一步提升处理效率。
串行模型和流水线模型如图 10所示，当第i个图像在CPU上完成填充步骤后，将填充中间结果传递至GPU进行合并/反转，同时CPU不需等待GPU工作完成，可以开始第i+1个图像的填充过程。此时异构平台的CPU和GPU同时进行两张图片处理，实现任务间的并行。
|
Download:
|
| 图 10 串行模型和流水线模型 Fig. 10 Serial model and pipeline model | |
2）CPU+GPU组合填充阶段使用CPU，最佳种子/线程数量范围是70~110，使用8位的unsigned char表示一个像素即可。相对于GPU填充阶段实现（最佳种子数量32 768，需要16 bit像素），减少数据在CPU和GPU之间传输的耗时。
构建一个长度为100的图像数组，模拟处理一批图片的应用场景，计算整体处理时间后除以100，获得单张图片的处理时间。
异构流水线模型处理批量任务的性能如图 11所示。从图 11可以看出，相对于单张图像填充、反转两阶段串行的实现，在处理批量情况下，流水线模型平均性能提高了15.4%。
|
Download:
|
| 图 11 异构流水线模型处理批量任务的加速比 Fig. 11 Speedup of heterogeneous pipeline model for batch tasks | |
本文在反向填充算法的基础上设计了并行反向填充算法，并基于CPU和GPU平台实现算法的填充、反转/合并阶段，获得最优参数。实验结果表明，在6种常见分辨率的图像上，CPU+GPU异构方案和流水线模型分别获得相对串行反向填充算法平均3.84倍和4.43倍的加速比，其中，在4 KB以上的高分辨图像上获得了平均5.68倍和6.72倍的加速比。改进的算法具有无需人工设定种子的优点，可以充分利用多核、异构处理器的计算能力。下一步考虑将二维并行填充算法的优势延伸到三维填充算法中，优化和隐藏数据传输以提高改进算法的性能。
| [1] |
PAVLIDIS T. Filling algorithms for raster graphics[J]. Computer Graphics and Image Processing, 1979, 10(2): 126-141. DOI:10.1016/0146-664X(79)90046-7 |
| [2] |
PAVLIDIS T. Algorithms for graphics and image processing[M]. Berlin, Germany: Springer, 1982.
|
| [3] |
BURTSEV S V, KUZMIN Y P. An efficient flood-filling algorithm[J]. Computers & Graphics, 1993, 17(5): 549-561. |
| [4] |
Rogers David F. Procedural elements for computer graphics[M]. 2nd ed. New York, USA: McGraw-Hill Companies, 1998.
|
| [5] |
FREEMAN H. On the encoding of arbitrary geometric configurations[J]. IRE Transactions on Electronic Computers, 1961, 10(2): 260-268. |
| [6] |
CAI Z G. Restoration of binary images using contour direction chain codes description[J]. Computer Vision Graphics and Image Processing, 1988, 41(1): 101-106. DOI:10.1016/0734-189X(88)90119-3 |
| [7] |
LIU Y, HU W X, HAN L Z. A fast filling algorithm for image restoration based on contour parity[J]. Computers, Materials & Continua, 2020, 63(1): 509-519. |
| [8] |
TSAI Y H, CHUNG K L. Region-filling algorithm on bincode-based contour and its implementation[J]. Computers & Graphics, 2000, 24(4): 529-537. |
| [9] |
JU Z Y, CHEN Y G. New filling algorithm based on chain code[J]. computer engineering, 2007, 33(17): 211-212. (in Chinese) 巨志勇, 陈优广. 一种新的基于链码的填充算法[J]. 计算机工程, 2007, 33(17): 211-212. DOI:10.3969/j.issn.1000-3428.2007.17.072 |
| [10] |
LI X, HUANG L. New region filling algorithm based on chain codes description[C]//Proceedings of the 3rd International Congress on Image and Signal Processing. Yantai, China: IEEE Press, 2010: 2806-2809.
|
| [11] |
KAUFMAN A, COHEN D, YAGEL R. Volume graphics[J]. Computer, 1993, 26(7): 51-64. DOI:10.1109/MC.1993.274942 |
| [12] |
FENG L, SOON S H. An effective 3D seed fill algorithm[J]. Computers & Graphics, 1998, 22(5): 641-644. |
| [13] |
XUE B D, XUE W F, JIANG Z G. Improvement of 3D seed filling algorithm[J]. Journal of Computer-Aided Design and Computer Graphics, 2006, 18(10): 1553-1556. (in Chinese) 薛斌党, 薛文芳, 姜志国. 三维种子填充算法的改进[J]. 计算机辅助设计与图形学学报, 2006, 18(10): 1553-1556. DOI:10.3321/j.issn:1003-9775.2006.10.016 |
| [14] |
YU W W, HE F, XI P. A rapid 3D seed-filling algorithm based on scan slice[J]. Computers & Graphics, 2010, 34(4): 449-459. |
| [15] |
SARPATE G K, GURU S K. Image inpainting on satellite image using texture synthesis & region filling algorithm[C]//Proceedings of 2014 International Conference on Advances in Communication and Computing Technologies. Washington D.C., USA: IEEE Press, 2014: 1-5.
|
| [16] |
ABDULADHEM A A, HUSSEIN A H. Real-time lane markings recognition based on seed-fill algorithm[C]//Proceedings of ICICT'19. New York, USA: ACM Press, 2019: 190-195.
|
| [17] |
LIU H F, ZHANG C, LUO J, et al. A binary image boat region fast and auto filling algorithm[C]//Proceedings of the 4th China conference on command and control. Beijing, China: Publishing House of Electronics Industry, 2016: 647-650. (in Chinese) 刘海峰, 张超, 罗江, 等. 一种二值图像船舶目标区域快速自动化填充算法[C]//第四届中国指挥控制大会论文集. 北京: 电子工业出版社, 2016: 647-650. |
| [18] |
MA Y, SUN H, YE P, et al. Mobile robot multi-resolution full coverage path planning algorithm[C]//Proceedings of the 5th International Conference on Systems and Informatics. Nanjing, China: IEEE Press, 2018: 120-125.
|
| [19] |
WANG J, LIAO D M, ZHAO J H, et al. Application of the seed filling algorithm to the rapid display of hot spot by 3D casting process software[J]. Foundry, 2015, 64(1): 25-28. (in Chinese) 汪俊, 廖敦明, 赵建华, 等. 基于种子填充算法的热节快速显示在三维铸造工艺CAD中的应用[J]. 铸造, 2015, 64(1): 25-28. |
| [20] |
CHEN Z, LIAO D M, CHEN T. Improvement to seed filling algorithm in casting gas phase based on scanning line[J]. Special-cast and Non-ferrous Alloys, 2020, 40(1): 42-46. (in Chinese) 陈卓, 廖敦明, 陈涛. 基于扫描线的铸造气相域种子填充算法改进[J]. 特种铸造及有色合金, 2020, 40(1): 42-46. |
| [21] |
XU M C, JIANG X G, LI L. A new algorithm of backtrack 3D seed filling for mini-organ segmentation[J]. Journal of East China Jiaotong University, 2010, 27(2): 71-73. (in Chinese) 许苗村, 蒋先刚, 李林. 细小器官分割的可回溯三维种子填充新算法[J]. 华东交通大学学报, 2010, 27(2): 71-73. |
| [22] |
LIU C Y. Improvement of scan line algorithm for region filling[J]. Computer Engineering, 1994(S1): 469-472. (in Chinese) 柳朝阳. 对区域填充扫描线算法的改进[J]. 计算机工程, 1994(S1): 469-472. |
| [23] |
REN J C, LIU S Q. Improvement of area filling scanline algorithm[J]. Journal of Computer-Aided Design and Computer Graphics, 1998(6): 2-7. (in Chinese) 任继成, 刘慎权. 区域填充扫描线算法的改进[J]. 计算机辅助设计与图形学学报, 1998(6): 2-7. |
| [24] |
YU L S, SHEN D Y. A refinement of the scan line seed fill algorithm[J]. Computer Engineering, 2003(10): 70-72. (in Chinese) 余腊生, 沈德耀. 扫描线种子填充算法的改进[J]. 计算机工程, 2003(10): 70-72. |
| [25] |
VUČKOVIĆ V, ARIZANOVIĆ B, BLOND S L. Generalized N-way iterative scanline fill algorithm for real-time applications[J]. Journal of Real-Time Image Processing, 2019, 16(6): 2213-2231. DOI:10.1007/s11554-017-0732-1 |
| [26] |
VUČKOVIĆ V, ARIZANOVIĆ B, BLOND S L. Ultra-fast basic geometrical transformations on linear image data structure[J]. Expert Systems with Applications, 2018, 91: 322-346. DOI:10.1016/j.eswa.2017.09.011 |
| [27] |
LIU J H, FANG T, YANG J F. Fully automatic area-filling method for any complicated area[J]. Computer Engineering, 2008, 34(4): 238-240. (in Chinese) 柳稼航, 方涛, 杨建峰. 适用于任意复杂区域的全自动填充方法[J]. 计算机工程, 2008, 34(4): 238-240. |
| [28] |
GALLER B A, FISHER M J. An improved equivalence algorithm[J]. Communications of the ACM, 1964, 7(5): 301-303. |
| [29] |
NVIDIA N, GENERATION N, COMPUTE C. Whitepaper-NVIDIA's next generation CUDA compute architecture[J]. ReVision, 2009, 23(6): 1-22. |