[發明專利]一種基于2D Wilson迷宮的數字置亂方法

有效

• 申請號: 201410748363.3
• 申請日: 2014-12-08
• 公開（公告）號: CN104361551B
• 公開（公告）日: 2019-03-05
• 發明（設計）人: 邵利平
• 申請（專利權）人: 陜西師范大學
• 主分類號: G06T1/00
• 分類號: G06T1/00
• 代理公司: 西安通大專利代理有限責任公司 61200
• 代理人: 陸萬壽

1.一種基于2D Wilson迷宮的數字置亂方法，其特征在于包括以下步驟：

第1步：設定迷宮初始范圍為S_init＝()_m×n和迷宮有效區域S_maze＝(s_i,j)_m×n，S_maze＝(s_i,j)_m×n為圖像上的2D局部不規則封閉連通區域，對于若則標記s_i,j＝-1，反之則標記s_i,j＝0表示節點s_i,j未訪問，若s_i,j>0表示節點s_i,j已訪問，統計S_maze范圍內的節點數量Num_maze＝count(S_maze)；

第2步：對于記s_i,j.d,d＝0,1,2,3依次為節點s_i,j的下方墻、右方墻、上方墻和左方墻，初始化s_i,j.d＝-1,d＝0,1,2,3，即將S_maze范圍內的所有節點以墻進行分隔，s_i,j.d＝-1表示有墻，s_i,j.d＝0表示無墻；

第3步：選擇隨機數發生器y＝RG(x)，設定隨機數發生器初始值RG.init＝seed，記已訪問的節點數量Num_visited，初始Num_visited＝0，初始化已訪問迷宮節點列表A_update＝Φ，其中Φ為空集；

第4步：隨機選取標記s_x,y＝1，將其加入到節點更新序列，A_update＝A_update.add(s_x,y)，Num_visited＝Num_visited+1；

第5步：若Num_visited＜Num_maze，則循環執行第6步～第10步，反之若Num_visited≥Num_maze時，則執行第11步；

第6步：初始化Wilson隨機游走路線列表A_Wilson＝Φ，初始化全0元素Wilson矩陣M_Wilson＝(mw_i,j)_m×n，其中mw_i,j＝0表示s_i,j不在Wilson隨機游走路線上，mw_i,j＝-1表示s_i,j在Wilson隨機游走路線上；

第7步：從s_x,y周圍S_maze范圍內有效節點s_x+1,y,s_x,y+1,s_x-1,y,s_x,y-1中隨機選擇1個節點s_x′,y′作為當前節點，若s_x′,y′＝0且mw_x′,y′＝-1，則在Wilson隨機游走路線列表A_Wilson中移除s_x′,y′第1次位置出現之后的所有節點并將對應的節點重新在M_Wilson上標記為0；

第8步：若s_x′,y′＝0且mw_x′,y′＝0，則標記mw_x′,y′＝-1，則將s_x′,y′加入A_Wilson，即A_Wilson＝A_Wilson.add(s_x′,y′)；

第9步：若s_x′,y′＝1，則將A_Wilson中的所有節點標記為已訪問，將其加入到A_update，Num_visited＝Num_visited+A_Wilson.length；

第10步，若s_x,y周圍不存在可以訪問的S_maze范圍內有效節點，則從A_update中隨機選擇1個節點作為當前節點s_x,y；

第11步：利用A_update構造S_maze＝(s_i,j)_m×n范圍內所有節點間的節點位置映射關系，從而將圖像上2D局部不規則封閉連通區域S_maze＝(s_i,j)_m×n范圍內的所有節點進行整體置亂。