Week4,如何判斷一張圖(黑白圖)是雜亂的

Week4:如何判斷一張圖(黑白圖)是雜亂的(延伸)
延續上次我post的想法...上次的想法太籠統而且可能會產生問題!
問題在於:亂的程度要怎麼去算?怎樣定義一個"臨界值"才市最公正且為大家所能接受的? 這樣變的比較難了!
昨天晚上想到一個延伸的方式!於是把keyword 寫下來,今天post上!但是精神和之前的想法相似!只是我覺得更具powerful且reasonable.
ALGO:
我們可以對一張圖,
每個沒有被計算(加入region或是從佇列刪除)的pixel做處理,
當我們選定此pixel,則往他的4臨方向(4-neighbor)去做擴展計算,
如果4臨方向的顏色和他相近則加入(也可以說把他從佇列上刪去,下次就不再做計算) 且把他的權值(也可以說是region大小值)加一.
一直擴展到他遇到了不同的顏色!於是停止.
這是類似region growing技術的一個想法, 只要最後我們判定這樣的region個數跟region範圍(應該說region個數比較少,因為如果雜亂的話很可能region個數大,但是每個region範圍卻很小(可能一點或是兩三點)) 這樣可以判斷出合理的圖形切片複雜的地方!
以下是虛擬碼部分的演算法(計算region size 的遞迴(不知有沒有錯)),有錯的話之後會再更正!
int P(int X,int Y)
repeat
if the pixel P we selected is in execution Queue
do
if P(x+1,y) has the same color with P(x,y)
then delete form Queue and label it(bind it with P(x,y));
region size = region size + P(x+1,y);
if P(x-1,y) has the same color with P(x,y)
then delete form Queue and label it(bind it with P(x,y));
region size = region size + P(x-1,y);
if P(x,y+1) has the same color with P(x,y)
then delete form Queue and label it(bind it with P(x,y));
region size = region size + P(x,y+1);
if P(x,y-1) has the same color with P(x,y)
then delete form Queue and label it(bind it with P(x,y));
region size = region size + P(x,y-1);
else
return region size of P=0

就Data stucture 而言!我們可以宣告一個和圖片大小相同的二維陣列(two dimemsion):Array[i][j]

Pixel[i][j] //圖的像素
if Pixel[i][j]=黑
Array[i][j]=1;
else if Pixel[i][j]=白
Array[i][j]=0;
如何去label?
依照上敘的演算法!只要顏色相同就填一個數字2
碰壁後(顏色區隔完),就換另一個數3,再區隔完換4....依次類推!
最後去統計這個Array[][]有幾種>=2的數字
數字種類越多表示region區塊很多(i.e.很雜亂)
數字種類越少表示region區塊很少(i.e.不雜亂)
圖示:
initial:
0 1 1 1 0 0 1 0
0 0 0 1 1 1 0 0
0 0 0 0 1 1 0 1
1 1 1 0 0 0 0 1
1 1 1 0 0 0 0 1
1 1 1 1 1 1 0 0
0 0 0 1 0 1 0 0
1 1 1 1 0 1 1 0
0 0 1 1 0 1 1 0
0 0 0 0 1 1 0 0
label後:
2 3 3 3 4 4 5 2
2 2 2 3 3 3 2 2
2 2 2 2 3 3 2 6
7 7 7 2 2 2 2 6
7 7 7 2 2 2 2 6
7 7 7 7 7 7 2 2
8 8 8 7 9 7 2 2
7 7 7 7 9 7 7 2
10 10 7 7 9 7 7 2
10 10 10 10 7 7 2 2
記數到10
可想而知,若是1,0均勻分配且穿插則出現的數字會更多!
0 1 0 1 0 1 0 1
1 0 1 0 1 0 1 0
1 0 1 1 0 0 1 0
0 0 0 0 1 1 0 1
1 1 1 1 0 0 1 0
0 0 0 0 1 1 0 1
1 0 1 0 1 0 0 0
1 0 1 0 1 0 1 1
0 1 0 1 0 1 0 1
1 1 0 0 1 0 1 0

label後:
2 3 4 5 6 7 8 9
10 11 12 13 14 15 16 17
10 11 12 12 15 15 16 17
11 11 11 11 18 18 19 20
21 21 21 21 22 22 23 24
25 25 25 25 26 26 27 28
29 25 30 25 26 27 27 27
29 25 30 25 26 27 31 31
32 33 34 35 36 37 38 39
33 33 34 34 40 41 42 43

記數到43



and...逢甲通訊的論文,上篇我有po有關PoV的 他的敘述我不太了!不知道是翻譯原文的關係,還是我的中文理解力退化了!挺想寫那個程式的><