Re: [討論] label矩陣

[YoursEver (銀英傳出webgame!?)]

※ 引述《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://www.ptt.cc/bbs/MATLAB/M.1474339509.A.25F.html
→ YoursEver: 回了才發現和前一篇sunev老大的寫法是一樣的.
推 sunev: 但是原PO說變慢了，可能先profile分析一下瓶項在哪裡
這我就不確定了,
因為我自己處理過一模一樣要重新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
推 sunev: 應該是第一種 a=1;for i=1:mod(2*max(a),5),a=[a i];end,a

剛才測試了一下, 的確是第一種沒錯.

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
推 andgitisaac: 首先先感謝大大的解釋，很抱歉最近沒有回版上看到前
→ andgitisaac: 輩的後續發文。
→ andgitisaac: 同時也相當感謝sunev大大在第一時間回覆我的疑問。
→ andgitisaac: 當初在看了大大的buffer解釋後，也覺得變慢很奇怪
→ andgitisaac: 事情忙完後重新跑了一次程式，卻發現時間確實有加快
→ andgitisaac: 由於當初沒有做更深的研究因此沒多加注意
→ andgitisaac: 過幾天要再來實測高解析度的影像。
→ andgitisaac: 相信是我一時不察所發生的錯誤，也再次感謝兩位前輩
→ andgitisaac: 的協助。謝謝！
推 sunev: 如果瓶頸是bwlabel，num都不大，這種改寫不會改善太多
→ sunev: 但變慢應該是不至於。