[發明專利]一種基于游程的單次掃描連通域標記方法及其硬件結構

有效

• 申請號: 201810641505.4
• 申請日: 2018-06-21
• 公開（公告）號: CN108876701B
• 公開（公告）日: 2022-08-02
• 發明（設計）人: 趙晨;葛興;姚英朋;苗兆偉;高武
• 申請（專利權）人: 西北工業大學
• 主分類號: G06T1/20
• 分類號: G06T1/20
• 代理公司: 西北工業大學專利中心 61204
• 代理人: 劉新瓊

1.一種基于游程的單次掃描連通域標記方法，其特征在于步驟如下：

步驟1：行掃描：

行掃描模塊從外存中讀取當前行像素數據，從RAM_BUFFER中讀取上一行像素數據，兩行同時掃描，并將當前行像素數據存入RAM_BUFFER；當前行為奇數行，游程信息存入RAM_EV，反之，則存入RAM_OD；所述的游程信息包括臨時標記值lab_tem、行坐標最小值X_min、行坐標最大值X_max三項；掃描過程中檢測到上一行與當前行游程等價時：若當前行游程臨時標記lab_tem_c為0，即未賦予該游程臨時標記值，則lab_tem_c＝lab_tem_l，lab_tem_l為等價的上一行游程lab_temp值；若當前行游程lab_tem_c不為0，則(lab_tem_l，lab_tem_c)存入RAM_EQU；掃描過程中檢測到當前行游程結束時：若該游程lab_tem為0，即未賦予臨時標記值，則lab_ct＝lab_ct+1，lab_tem＝lab_ct，lab_ct當新產生一個未賦臨時標記值的游程時加1；

步驟2：更新等價游程表：

等價游程表由rtable、tail、next三個數據陣列組成，分別存儲于片上存儲器RAM_RTAB、RAM_TAIL和RAM_NEXT中；若干個同屬于一個連通域的等價游程，其臨時標記信息構成鏈表集合S，該連通域對應唯一一個代表標記值lab_rep；RAM_RTAB位寬為RAM_TAIL和RAM_NEXT的2倍，RAM_RTAB[:,1]存儲游程代表標記lab_rep和臨時標記lab_tem之間的關系，即RAM_RTAB[lab_tem]＝lab_rep；RAM_TAIL存儲S中最后一個游程臨時標記值，RAM_TAIL[lab_rep]＝lab_final；RAM_NEXT存儲S中臨時標記的順序，RAM_NEXT[lab_i]＝RAM_NEXT[lab_j]表示S中臨時標記lab_i下一個等價的臨時標記為lab_j，若RAM_NEXT[lab_n]＝-1，表示S最后一個臨時標記值為lab_n；RAM_RTAB[lab_rep,2]存儲代表標記為lab_rep的S中包含多少個游程；當建立一個新的臨時標記lab_tem時，如果代表標記和臨時標記相同，即RAM_RTAB[lab_tem]＝lab_tem，同時，連通域包含的游程個數設置為1，下一個等價的游程臨時標記設置為-1，最后一個游程的臨時標記值設為lab_tem；

等價游程更新子模塊根據存儲在RAM_EQU中的等價游程信息更新等價游程表，假設RAM_EQU存儲了N對等價游程信息，等價游程表更新如下：相鄰兩行等價游程的臨時標記分別為lab_tem_l和lab_tem_c，從RAM_RTAB讀出其代表標記lab_rl和lab_rc，兩者的較大值為lab_max，較小值為lab_min；迭代更新lab_max開始的等價游程鏈表，將其代表標記均賦值為lab_min；lab_min開始的等價游程鏈表，其原尾部指向lab_max，新尾部指向lab_max開始的等價游程鏈表尾部，同時，更新lab_min對應的連通域所含游程個數，即原有游程個數與lab_max對應的連通域所含游程個數之和，然后lab_max對應的連通域所含游程個數清零；

步驟3：檢測結束連通域：

連通域標記硬件加速模塊中的連通域結束檢測子模塊檢測上一行已結束連通域，將上一行中結束連通域的游程寫入外存儲器，并將結束連通域的代表標記值寫入RAM_OVER，然后將上一行剩余的游程寫入游程緩沖區存儲器RAM_INFO，清空存儲上一行游程信息的存儲器，當前行為奇數行，存儲上一行游程信息的存儲器為RAM_EV，否則為RAM_OD；檢測上一行游程是否結束的方法為：對于上一行的每個游程，檢測其代表標記值是否與當前行中的某個游程代表標記值相同，如果相同，則說明該游程在當前行有等價游程，連通域未結束，否則，該游程所屬連通域結束；

步驟4：將已結束連通域游程信息寫入外存儲器：

連通標記硬件加速模塊中的游程緩沖區控制子模塊根據RAM_OVER中存儲的結束連通域代表標記值信息，遍歷RAM_INFO，將以結束連通域的游程信息寫入外存儲器；

步驟5：最后一行及緩沖區內所有游程寫入外存儲器：

當前行為最后一行時，游程緩沖區控制子模塊首先將當前行游程信息從片上存儲器中取出寫入外存儲器，其中當前行為奇數行時片上存儲器為RAM_OD，為偶數行時片上存儲器為RAM_EV，然后將RAM_INFO中的游程信息依次寫入外存儲器。

2.根據權利要求1所述的連通域標記方法，其特征在于步驟4中采用優化機制減少遍歷RAM_INFO所需的時間，優化機制包括兩個方面：①RAM_RTAB中記錄連通域包含的游程個數，已結束連通域的游程向外存儲器寫一個，該區域對應的游程個數減1，游程個數變為0時，即表示已結束連通域的游程信息全部寫入外存儲器，停止遍歷RAM_INFO；②遍歷RAM_INFO過程中，如果位置X處游程被選中寫入外存儲器，則將RAM_INFO中最后位置處的游程信息讀出寫入X位置，然后從X位置重新開始遍歷，同時有效游程信息深度X_depth減1。