计算机工程与应用
計算機工程與應用
계산궤공정여응용
COMPUTER ENGINEERING AND APPLICATIONS
2014年
23期
31-35
,共5页
连通域%标记算法%一遍扫描%标号%二值图像%标记连接表
連通域%標記算法%一遍掃描%標號%二值圖像%標記連接錶
련통역%표기산법%일편소묘%표호%이치도상%표기련접표
connected component%labeling algorithm%one-scan%label%binary image%label connected table
二值图像的连通区域标记算法是图像处理的一个基本问题。为了提高算法的效率，以Suzuki等人提出的多遍扫描算法为基础，提出了一种快速的一遍扫描连通域标记算法。算法通过对图像做一次正向扫描，先计算出每个当前像素所在邻域内的最小标号，再利用一个递推过程，查找该连通域中具有较小标号的结点，将被更新结点所在连通分支连接到该结点，以保证等价信息不损失。同时，用最小标号更新递推查找路径上结点的临时标号，以减小分支的深度。通过对连接表的更新使每个结点获得最终标号。算法不需要动态数据结构和递归过程的支持，需要的存储空间较小，算法比原算法速度提高了近2倍，也快于近期提出的一些基于游程的算法。
二值圖像的連通區域標記算法是圖像處理的一箇基本問題。為瞭提高算法的效率，以Suzuki等人提齣的多遍掃描算法為基礎，提齣瞭一種快速的一遍掃描連通域標記算法。算法通過對圖像做一次正嚮掃描，先計算齣每箇噹前像素所在鄰域內的最小標號，再利用一箇遞推過程，查找該連通域中具有較小標號的結點，將被更新結點所在連通分支連接到該結點，以保證等價信息不損失。同時，用最小標號更新遞推查找路徑上結點的臨時標號，以減小分支的深度。通過對連接錶的更新使每箇結點穫得最終標號。算法不需要動態數據結構和遞歸過程的支持，需要的存儲空間較小，算法比原算法速度提高瞭近2倍，也快于近期提齣的一些基于遊程的算法。
이치도상적련통구역표기산법시도상처리적일개기본문제。위료제고산법적효솔，이Suzuki등인제출적다편소묘산법위기출，제출료일충쾌속적일편소묘련통역표기산법。산법통과대도상주일차정향소묘，선계산출매개당전상소소재린역내적최소표호，재이용일개체추과정，사조해련통역중구유교소표호적결점，장피경신결점소재련통분지련접도해결점，이보증등개신식불손실。동시，용최소표호경신체추사조로경상결점적림시표호，이감소분지적심도。통과대련접표적경신사매개결점획득최종표호。산법불수요동태수거결구화체귀과정적지지，수요적존저공간교소，산법비원산법속도제고료근2배，야쾌우근기제출적일사기우유정적산법。
How to label connected components of a binary image is a basic problem in image processing field. To improve efficiency, a fast one-scan algorithm to label connected components is presented in this paper on the base of the multiple-scans algorithm proposed by Suzuki et al. The algorithm runs a forward scan to the object image only once. The node with the minimum label in the mask of the object pixel is calculated. The node with smaller label is searched in the connected component by an iterative process, and the connected branch including the note to be updated is linked to it. This tech-nique can guarantee no loss to the equivalent information. At the same time, the provisional labels in iterative search path are updated by the minimum label in order to decrease the depth of the branch. The final labels of all nodes are obtained by scanning the connected table. Dynamic data structure and recursive procedure are not needed in this algorithm, and only less memory is required. Experiments and analysis show that the algorithm is about 2 times faster than the original one, and is also faster than some run algorithms proposed recently.
