PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: [問題] RSTA(Rotated Summed Area Table)

看板Prob_Solve (計算數學 Problem Solving)作者LPH66 (-858993460)時間13年前 (2011/08/11 19:38)推噓3(3推 0噓 4→)

留言7則, 3人參與討論串2/2 (看更多)

這個演算法其實是在用這個方法來算 R(x,y): ■■■■■■■ ■■■■■■■ ■■■■■■■ ■■■■■■■ ■■■■■■■ ■■■■■■■ ■■■■■■■ ■■■■■■■ ■■■■■■■ ＝ ■■■■■■■ ＋ ■■■■■■■ － ■■■■■■■ ■■■■■■■ ■■■■■■■ ■■■■■■■ ■■■■■■■ ■■■■■■■ ■■■■■■■ ■■■■■■■ ■■■■■■■ R(x,y) ＝ R(x-1,y-1) ＋ R(x+1,y-1) － R(x,y-2) ■■■■■■■ ■■■■■■■ ＋ ■■■■■■■ ■■■■■■■ ■■■■■■■ ＋ I(x,y)+I(x,y-1) 如果把它套在你的問題點 (0,2) 上就會發現變成了這樣: ■■■■■ ■■■■■ ■■■■■ ■■■■■ ■■■■■ ■■■■■ ■■■■■ ■■■■■ ■■■■■ ■■■■■ ■■■■■ ＝ ■■■■■ ＋ ■■■■■ － ■■■■■ ＋ ■■■■■ ■■■■■ ■■■■■ ■■■■■ ■■■■■ ■■■■■ ■■■■■ ■■■■■ ■■■■■ ■■■■■ ■■■■■ R(0,2) ＝ R(-1,1) ＋ R(1,1) － R(0,0) ＋ I(0,2)+I(0,1) 圖形是應該要有的值但 R(-1,1) 的值卻不是這個地方的和而是 0 於是產生錯誤所以正確說來邊界條件應該要修正為 R(-1,y) = R(0,y-1) R(w,y) = R(w-1,y-1) (w 是圖寬) 這樣就會對了至於 y < 0 的邊界條件設為 0 是沒有問題的因為那等於是在圖上方的區域當然和為 0 -- 話說我 google 到的 RSAT 介紹網頁用的也是這個錯誤的邊界條件... 該不會原論文這裡就錯了吧?! (看那網頁的 Bibliography 原論文應該是 2002 年發表的... 這麼近代的東西會犯這種小錯誤這還頗微妙...) -- 実琴：「河野！你真的就這樣被物質慾望給吸引過去了嗎?!」亨：「只要穿著女裝擺出親切的樣子，所有必要花費就能全免，似乎一點都不壞啊。」実琴：「難道你沒有男人的尊嚴了嗎?!」亨：(斷然道)「沒有。在節衣縮食且生活吃緊的學生面前，沒有那種東西。」－－プリンセス・プリンセス第二話 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.24.158

推

pigcat1315

08/11 20:17, , 1^F

08/11 20:17, 1^F

→

LPH66

08/11 20:57, , 2^F

08/11 20:57, 2^F

→

LPH66

08/11 20:58, , 3^F

08/11 20:58, 3^F

→

LPH66

08/11 20:59, , 4^F

08/11 20:59, 4^F

補充一下好了其實原式可以改成不需要左右兩邊的邊界條件但相對的就是公式變複雜一些些: 改動的只有最左邊和最右邊兩條的公式 R(0,y)=R(1,y-1)+I(0,y)+I(0,y-1) R(w-1,y)=R(w-2,y-1)+I(w-1,y)+I(w-1,y-1) 其他的 R 值照原來的式子計算之所以能這樣改是因為 (請對照原文圖) 紅色和紫紅色區域在 x=0 時一定相等相對的在 x=w-1 時是藍色和紫紅色區域相等因此它們就會一正一負抵消就成了上式了如果你要用這個方法去計算也是可以這樣就不需要管左右兩邊的邊界條件了 ※ 編輯: LPH66 來自: 140.112.24.158 (08/11 21:11)

推

tropical72

08/11 21:30, , 5^F

08/11 21:30, 5^F

推

pigcat1315

08/11 21:55, , 6^F

08/11 21:55, 6^F

→

pigcat1315

08/11 21:56, , 7^F

08/11 21:56, 7^F