推 LPH66:題外話: 在推文裡畫圖要在別處弄成推圖的方式比較方便 XD 06/08 18:47
→ VictorTom:比如test板嗎XD 太麻煩了所以就直接回文了XDDD 06/08 18:49
推 zodiace:有沒有更具體的方法 我了解問題點@~@ 但是更具體一點的做 06/08 20:12
→ zodiace:法是? 06/08 20:13
概念上這樣想, 假設每一個id都是某種tree的一個node....
- - - - - - - - - 接地, 或說指到NULL
^ ^ ^ ^ ^ ^ ^ ^
| | | | | | | |
o o o o o o o o
1 2 3 4 5 6 7 8 - 每有一個新id, 就開個node, 或者該稱為一個node的tree
假如今天你發現某兩個id等價, 那就把大的接到小的....
Ex: 2 3 等價, 3 5 等價....
- - - - - - - 接地, 或說指到NULL
^ ^ ^ ^ ^ ^
| | | | | |
o o o o o o
1 2 4 6 7 8
^
|
o
3
^
|
o
5
Ex: 再發現 3 6 等價, 7 8 等價....
- - - - - 接地, 或說指到NULL
^ ^ ^ ^
| | | |
o o o o
1 2 4 7
^ ^
| |
o o
3 8
^
/ \
o o
5 6
Ex: 又發現 1 3 等價;
注意, 3已經接到2, 所以3先找到指到源頭(2), 再把2指到1....
- - -
^ ^ ^
| | |
o o o
1 4 7
^ ^
| |
o o
2 8
^
|
o
3
^
/ \
o o
5 6
假如找到源頭以後發現源頭(?)比另一邊還小, 就把對方指過來....
假如兩邊都是tree, 就找到各自的源頭(root), 把大的指到小的....
當然, 找root這種動作也可以嘗試在相接的時候就做簡(矮)化....
比如 2 3 接完又發現 3 5 等價時, 就把 5 直接接到 2 去....
接著 3 6 等價時, 也把 6 直接接到 2 去....
不過這樣在之後的 1 3 等價時, 想把 2 下面的node矮化接到 1 有困難....
只是就算接成 1
2
3 5 6 這樣, 基本上也不會影響結果就是了@_@"
所以矮化tree這個動作, 等tree建完再做也可以, 效能誰好要推一下....
比如最原始那三個tree, 對每個id跑一次執行矮化動作, 會像下面....
- - -
^ ^ ^
1 4 7
2 3 5 6 8
==
以此類推, 到最後就會完成像上面這樣的tree, 即本例該有3種label....
那你接著重新掃過一遍全圖的id, 把每個node都重設成自己tree的root....
就完成re-labeling了, 有心的話也可以重新分配label id, 方便下顏色....
==
概念上是像上面這樣子, 但是實際上做起來卻不必搞tree這麼麻煩....
只要對著你的inx[]跑兩層迴圈掃一下應該就行了, 給您自己想想看吧:)
--
※ 編輯: VictorTom 來自: 220.134.41.4 (06/08 20:47)
※ 編輯: VictorTom 來自: 220.134.41.4 (06/08 21:04)
※ 編輯: VictorTom 來自: 220.134.41.4 (06/08 21:05)
推 zodiace:真的很謝謝你 我有寫出來了 謝謝! 06/08 21:17
→ VictorTom::) 只是聽說好像 OpenCV 都有現成工具可以用了(默Orz) 06/08 22:57
推 zodiace:Q_Q……… 06/08 23:24
→ VictorTom:哈哈, 就當練功吧 ^^|| 因為看您寫的也差不多完成了XD 06/08 23:32
推 zodiace:謝謝 06/09 00:39