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

Re: [問題] 二維的字串比對問題

看板Prob_Solve (計算數學 Problem Solving)作者slanla (slanla)時間18年前 (2006/07/18 18:50)推噓3(3推 0噓 0→)

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

※ 引述《windows2k (KERORO軍曹)》之銘言： : 以下這個方法通常只是理論上可以實行, 做起來就囧了 : 可以把二維的字串看作是影像, : 原來的問題就變成從一張影像當中, 找到一致性的 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 恩恩..好像有聽老師教過褶積的方法.. 不過好像有另外一個比較簡單..相關係數法(Normalized Cross-Correlation) 假設A為目標影像(小影像)、B為搜尋影像(大影像) 而要在B影像中找出與A最有相關性的位置其公式如 http://140.116.80.230/ncc.jpg

以下面為例: A B 12 512 34 234 442 首先先計算 A的平均=(1+2+3+4)/4=2.5 (1,1) : B'影像: 51 23 B'的平均=(5+1+2+3)/4=2.75 分子=(1-2.5)*(5-2.75)+(2-2.5)*(1-2.75)+(3-2.5)*(2-2.75)+(4-2.5)*(3-2.75) =-2.5 分母=( ((1-2.5)^2 +(2-2.5)^2 +(3-2.5)^2 +(4-2.5)^2 )* ((5-2.75)^2+(1-2.75)^2+(2-2.75)^2+(3-2.75)^2) ) ^ (0.5) =6.614 →C=分子/分母=-0.377964473 (1,2) : B'影像: 12 34 B'的平均=(1+2+3+4)/4=2.5 分子=(1-2.5)*(1-2.5)+(2-2.5)*(2-2.5)+(3-2.5)*(3-2.5)+(4-2.5)*(4-2.5) =5 分母=( ((1-2.5)^2+(2-2.5)^2+(3-2.5)^2+(4-2.5)^2 )* ((1-2.5)^2+(2-2.5)^2+(3-2.5)^2+(4-2.5)^2) ) ^ (0.5) =5 →C=分子/分母=1→C=1表示此處兩影像100%相同,C=-1代表者100%不同,同如底片 (2,1) : B'影像: 23 44 B'的平均=(2+3+4+4)/4=3.25 分子=(1-2.5)*(2-3.25)+(2-2.5)*(3-3.25)+(3-2.5)*(4-3.25)+(4-2.5)*(4-3.25) =3.5 分母=( ((1-2.5)^2+(2-2.5)^2+(3-2.5)^2+(4-2.5)^2 )* ((2-3.25)^2+(3-3.25)^2+(4-3.25)^2+(4-3.25)^2) ) ^ (0.5) =3.708 →C=分子/分母=0.943879807 (2,2) : B'影像: 34 42 B'的平均=(3+4+4+2)/4=3.25 分子=(1-2.5)*(3-3.25)+(2-2.5)*(4-3.25)+(3-2.5)*(4-3.25)+(4-2.5)*(2-3.25) =3.5 分母=( ((1-2.5)^2+(2-2.5)^2+(3-2.5)^2+(4-2.5)^2 )* ((3-3.25)^2+(4-3.25)^2+(4-3.25)^2+(2-3.25)^2) ) ^ (0.5) =3.708 →C=分子/分母=-0.404519917 ----------------------------------------------------------------------------- 上述是影像匹配的方法...不過如果用在英文字母我想應該也是ok的~~ 把字母視為Ascii一樣可以處理.... 呼..打好久..不知道有沒有打錯~"~ 有錯..請大大多多包含了^^ -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.116.80.230