18

より大きな行列 M で部分行列 m を探すための高速な方法を考えていました。また、部分一致を識別する必要もあります。

私が考えることができるいくつかのアプローチは次のとおりです。

  1. 通常のブルートフォースを最適化して、増分行と列のみを処理します。
  2. Rabin-karp アルゴリズムを 2-d に拡張する可能性がありますが、部分的な一致を処理する方法がわかりません。

これは、画像処理で頻繁に発生する問題だと思います。誰かが入力してくれるか、このトピックに関するリソース/論文を教えていただければ幸いです。

編集: より小さな例:

より大きな行列:
1 2 3 4 5
4 5 6 7 8
9 7 6 5 2

より小さい行列:
7 8
5 2

結果: (行: 1 列: 3)

(1, 3) で部分一致と見なされる小さい行列の例:
7 9
5 2

半分以上のピクセルが一致する場合は、部分一致と見なされます。

ありがとう。

4

4 に答える 4

2

「2Dパターンマッチングアルゴリズム」でインターネット検索を行うことをお勧めします。あなたはたくさんの結果を得るでしょう。あなたの問題のアルゴリズムを紹介する論文であるGoogleの最初のヒットをリンクします。

また、論文の最後にある引用を見て、他の既存のアルゴリズムのアイデアを得ることができます。

要約：

二次元のnxnテキストで二次元のmxmパターンを検索するためのアルゴリズムが提示されます。テキストのサイズよりも平均して少ない比較を実行します：m^2の余分なスペースを使用してn^2/m。基本的に、テキストのn/m行のみで複数の文字列照合を使用します。最大で2n^2の時間で実行され、多くのパターンの最適なn^2時間に近くなります。これは、同様の最悪の場合のアルファベットに依存しないアルゴリズムに着実に拡張されます。実験結果は実際のバージョンのために含まれています。

于 2012-05-10T16:10:03.663 に答える
0

1 つの大きな行列に対して 1 つの小さな行列を一致させるだけでよい場合、これを高速に行う方法はありません。ただし、大きな行列に対して多くの小さな行列を実行する必要がある場合は、大きな行列を前処理します。

簡単な例、完全一致、1 つの巨大な行列に対する多くの 3x3 行列。

「ビッグマトリックス」と同じサイズの新しい「マッチマトリックス」を作成します。ビッグマトリックスの各位置について、ビッグマトリックスの各x、yからx + 3、y + 3の3x3ハッシュを計算します。これで、一致するハッシュの一致マトリックスをスキャンするだけです。

同じ部分一致プロパティを持つものに同じハッシュを与える特殊なハッシュ関数を使用して、部分一致を実現できます。トリッキー。

さらに高速化し、メモリを確保したい場合は、マッチ マトリックスのハッシュ テーブルを作成し、ハッシュ テーブルでハッシュを検索します。

3x3 ソリューションは、3x3 以上のテスト マトリックスで機能します。完璧なハッシュ メソッドを使用する必要はありません。不適切な一致の大部分を拒否し、ハッシュ テーブル内の潜在的な一致に対して完全な一致を実行するものだけが必要です。

于 2012-06-22T16:41:29.877 に答える
0

何らかのアプローチで部分行列がどこにあるかを推測することはできないと思いますが、検索を最適化することはできます。

たとえば、行列 A MxN と部分行列 B mxn が与えられた場合、次のように実行できます。

SearchSubMatrix (Matrix A, Matrix B)

answer = (-1, -1)

Loop1:
for i = 0 ... (M-m-1)
|
|   for j = 0 ... (N-n-1)
|   | 
|   |   bool found = true
|   |
|   |   if A[i][j] = B[0][0] then
|   |   |
|   |   |   Loop2:
|   |   |   for r = 0 ... (m-1)
|   |   |   |   for s = 0 ... (n-1)
|   |   |   |   |   if B[r][s] != A[r+i][s+j] then
|   |   |   |   |   |   found = false
|   |   |   |   |   |   break Loop2
|   |
|   |   if found then
|   |   |   answer = (i, j)
|   |   |   break Loop1
|
return answer

これを行うと、部分行列のサイズのために検索を減らすことができます。

Matrix         Submatrix         Worst Case:
1 2 3 4           2 4            [1][2][3] 4
4 3 2 1           3 2            [4][3][2] 1
1 3 2 4                          [1][3]{2  4}
4 1 3 2                           4  1 {3  2}

                                 (M-m+1)(N-n+1) = (4-2+1)(4-2+1) = 9

これは ですが、部分行列の次元が 1 つしかない場合を除き、時間O(M*N)は決して見えません。M*N

于 2015-12-06T15:30:43.220 に答える