作者LPH66 (-858993460)
看板Prob_Solve
標題Re: [問題] RSTA(Rotated Summed Area Table)
時間Thu Aug 11 19:38:18 2011
這個演算法其實是在用這個方法來算 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: 不過若改成 R(-1,y)=R(0,y-1) 帶 (0 1)會錯耶@@ 08/11 20:17
→ LPH66:R(0,1)=R(-1,0)+R(1,0)-R(0,-1)+I(0,1)+I(0,0) 08/11 20:57
→ LPH66:第一項變成R(0,-1)依然是0 第三項也是0 08/11 20:58
→ LPH66:第二項就是I(1,0)一個 所以答案還是正確的... 08/11 20:59
補充一下好了
其實原式可以改成不需要左右兩邊的邊界條件
但相對的就是公式變複雜一些些:
改動的只有最左邊和最右邊兩條的公式
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
推 pigcat1315::) 原來是我以為要帶原來y 謝謝我可以來寫成code了 08/11 21:55
→ pigcat1315:^^感謝LPH大大 08/11 21:56
修正一個筆誤 orz
※ 編輯: LPH66 來自: 140.112.24.158 (08/12 00:01)