Re: [問題] 二維的字串比對問題
看板Prob_Solve (計算數學 Problem Solving)作者windows2k (KERORO軍曹)時間18年前 (2006/07/08 13:49)推噓1(1推 0噓 0→)留言1則, 1人參與討論串8/9 (看更多)
以下這個方法通常只是理論上可以實行, 做起來就囧了
可以把二維的字串看作是影像,
原來的問題就變成從一張影像當中, 找到一致性的 pattern
定義 SSE = Sum of Square Error,
SSE = sigma (Image[x+i][y+j] - pattern[i][j]) ^ 2
i = 1...p, j = 1...q
p和 q 是 pattern的高和寬 x,y 可以看作是搜索的起點
只要找到 SSE = 0 的區塊, 就表示兩個部份是一樣的
我們可以將 SSE 重新改寫成
SSE = sigma (Image[x+i][y+j] ) ^ 2 + sigma (pattern[i][j]) ^ 2
i, j i,j
- 2* sigma Image[x+i][y+j] * pattern[i][j]
i,j
前面兩項可以經由預處理做掉.
後面 Convolution的部份,可以交由 FFT 先將資料轉至頻率空間
H[i] = F[i] * G[i]
再經由 Inverser FFT 轉回來得到每個點的convolution.
不過, 這沒有比較快, 加上可能有浮點誤差的問題存在
只是提供一種不同的作法, 聽聽就算了 XD
--
打了這麼多, P幣應該不少才是
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.115.220.140
推
07/08 16:31, , 1F
07/08 16:31, 1F
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 8 之 9 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
