作者YoursEver (銀英傳出webgame!?)
看板MATLAB
標題Re: [討論] label矩陣
時間Tue Sep 20 10:45:06 2016
※ 引述《andgitisaac (AndGiTiSaaC)》之銘言：
: 請問各位前輩們
: 現在有個label矩陣
: L = [2 2 2 2 3;
: 2 3 2 3 3;
: 2 3 2 4 4;
: 2 2 2 4 4;
: 1 1 2 1 1];
: 但目前碰到的問題得把
: 即便是相同label
: 但沒有連通的區域給分離(4連通)
: 也就是說L變成
: L = [2 2 2 2 3;
: 2 6 2 3 3;
: 2 6 2 4 4;
: 2 2 2 4 4;
: 1 1 2 5 5];
: 目前的作法是
: maxlabel = max(L(:))
: for n = 1:max(L(:))
: [bw, num] = bwlabel(L == n, 4)
: if num > 1
: for k = 2:num
: maxlabel = maxlabel + 1
: L(bw == k) = maxlabel
: end
: end
: end
: 但是由於label矩陣標籤數非常多，200多組就要花快十秒
: 想請問前輩們有沒有其他更好的做法
你的作法大概是 O(n^2),
所以理論上只要增加一個buffer,
寫成 O(n) 的形式就能加速.
所以改成:
Total_num = 0;
Relabeled_L = zeros( size(L) );
for n=1:1:max( L(:) )
[bw_buffer, num] = bwlabel(L==n,4);
Relabeled_L( bw_buffer~0 ) = bw_buffer( bw_buffer~0 ) + Total_num;
%把bw_buffer得到的label,略過0的位置,平移前一個iteration的總label數
Total_num = Total_num + num;
%更新總label數
clear bw_buffer; clear num;
end
--
沒仔細檢查,如果有typo請見諒.
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.109.22.216
算的僱{迭뀠文章網址:
https://webptt.com/m.aspx?n=bbs/MATLAB/M.1474339509.A.25F.html
1F：→ YoursEver: 回了才發現和前一篇sunev老大的寫法是一樣的. 09/20 10:58
2F：推 sunev: 但是原PO說變慢了，可能先profile分析一下瓶項在哪裡 09/24 02:16
這我就不確定了,
因為我自己處理過一模一樣要重新labelling的問題,
當時的經驗是這樣寫才會快.
我的case是要在一個stage內,
處理 400*9張 400*9的小影像 + 400*9張800*9的小影像
靠i7, 64-bit Win7, 32GB ram, Matlab 2012/2013的機器,
平均約需4xx秒.
因此我對於原po所說的速度下降毫無頭緒.
※ 編輯: YoursEver (218.161.51.131), 09/24/2016 07:40:26
以下是不負責猜測,
我的主要問題是: 有沒有人知道Matlab的 for-loop 運作機制?
對於下面的這個for loop來說:
for i=1:1:max(L(:))
...
end
到底運作的機制是
(1) 先計算 bound = max( L(:) ),
再跑 for i=1:1:bound,
還是,
(2) 類似do-while的機制,
但,是在每一個iteration之初,檢查是否 i<=max(L(:)),
會這樣說是因為,
若照前篇原po和sunev的寫法,
結構大致是:
for i=1:1:max(L(:))
...
L(bw>1)=L(bw>1)+maxlabel-1;
maxlabel=maxlabel+num-1;
...
end
換句話說,在for-loop的計算過程裡,
max( L(:) )是一直被增加的,
因此,
若Matlab的機制是上面的(2),
那的確可能因為for-loop的中止條件一直後延,
而造成不必要的延宕.
用我的寫法,另開一個array存重新labelling過後的資料,
就不會有這樣的問題.
※ 編輯: YoursEver (218.161.51.131), 09/24/2016 08:05:42
3F：推 sunev: 應該是第一種 a=1;for i=1:mod(2*max(a),5),a=[a i];end,a 09/24 14:26
剛才測試了一下, 的確是第一種沒錯.
clear all;
L = [1:1:10];
for ii=1:2:max(L)
ii
L = [L, 10+ii];
[L]
end
最後跑完時,
ii = 9;
L = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19];
那我就真的不知道為什麼原po會說速度變慢了.
※ 編輯: YoursEver (218.161.51.131), 09/24/2016 16:25:28
4F：推 andgitisaac: 首先先感謝大大的解釋，很抱歉最近沒有回版上看到前 09/27 20:18
5F：→ andgitisaac: 輩的後續發文。 09/27 20:19
6F：→ andgitisaac: 同時也相當感謝sunev大大在第一時間回覆我的疑問。 09/27 20:19
7F：→ andgitisaac: 當初在看了大大的buffer解釋後，也覺得變慢很奇怪 09/27 20:20
8F：→ andgitisaac: 事情忙完後重新跑了一次程式，卻發現時間確實有加快 09/27 20:21
9F：→ andgitisaac: 由於當初沒有做更深的研究因此沒多加注意 09/27 20:23
10F：→ andgitisaac: 過幾天要再來實測高解析度的影像。 09/27 20:24
11F：→ andgitisaac: 相信是我一時不察所發生的錯誤，也再次感謝兩位前輩 09/27 20:25
12F：→ andgitisaac: 的協助。謝謝！ 09/27 20:25
13F：推 sunev: 如果瓶頸是bwlabel，num都不大，這種改寫不會改善太多 09/28 11:41
14F：→ sunev: 但變慢應該是不至於。 09/28 11:41