🚵🏼 🏘️ 🌩️ 離散フーリエ変換を使用した1次元サンプル検索 ✊🏻 ❤️ 👨‍🎤

画像内の画像の検索に関する記事[1]を読んだ後、数式やコード自体に多くの質問が残されています。多くのサードパーティを使用しているため、配列の変換は透過的ではないと思われました。ライブラリ関数。

したがって、既製の実装をさらに検索しましたが、残念ながら、1974 [2]のアイデアへの参照が豊富であるにもかかわらず、計算数学Fortranのトレンドセッターでもアルゴリズムの実装は見つかりませんでした。ゼミや講演会、論文でも誠実に説明が光りませんでしたので、十数件の記事や議論を山積みにして、「手に取って」欲しい人のために記事を書きたいという思いがありました。サブストリング検索の最も単純な実装。

そのため、私は通常、最初に数学パッケージでアルゴリズムプログラムを作成し、アルゴリズムの操作の数値的安定性と正確性を見つけた後でのみ、それをコンパイル済みまたはバイト指向の言語のコードに翻訳します。これは私の経験です-ゆっくりと正確に、またはすばやく数えますが、すでに実際に知られていることです。したがって、デバッグ用の例示的なコードには、Wolfram言語とMathematica V12パッケージの一連の関数を使用しました。

実際、このアイデアの価値は何ですか。離散フーリエ変換（DFT）を使用すると、計算の複雑さが「ナイーブ」なO（n * m）からO（n Log（n））に減少します。ここでnはテキストサイズとmは、目的のサンプルのサイズです。さらに、メソッド拡張機能を使用すると、「ジョーカー」（アルファベットの他の文字を示す記号）で検索できますが、接尾辞の実装ではこれができません。

「ナイーブ」アプローチの説明：

サイズnの配列TとサイズmのサンプルPについて、要素値の差の2乗の関数を計算します。配列にはゼロから始まる番号が付けられます。

$S_i ^ F = \ sum \ nolimits_ {j = 0} ^ {m --1} {（{t_ {i + j}}}-{p_j} {）^ 2} = \ sum \ nolimits_ {j = 0} ^ {m-1} {t_ {i + j} ^ 2} -2 \ sum \ nolimits_ {j = 0} ^ {m --1} {{t_ {i + j}}} {p_j} + \ sum \ nolimits_ {j = 0} ^ {m-1} {p_j ^ 2} = T {T_i} -2P {T_i} + P {P_i}$

, . , . . S O((n-m+1)*m) , O(n*m).

${S_i} = \ sum \ nolimits_ {j = 0} ^ {m-1} {t_ {i + j} ^ 2} -2 \ sum \ nolimits_ {j = 0} ^ {m-1} {{t_ { i + j}}} {p_j} = T {T_i} -2P {T_i}$

Img = ColorConvert[Import["Test.png"], "Grayscale"];
{W, H} = ImageDimensions[Img];   

y = IntegerPart[H/2];                                (*Pattern width and coordinates*)
x = IntegerPart[W/4]; 
w = IntegerPart[W/8];            

L = Part[ImageData[ImageTake[Img, {y, y}]],1];       (*Stripe Array*)

T[i_] := Table[Part[L[[i + j - 1]], 1], {j, 1, w}] ;      (*Sample data*)
P[i_] := Table[Part[L[[j + x - 1]], 1], {j, 1, w}] ;      (*Pattern data*)

TT = Table[Sum[(T[i][[j]]* T[i][[j]]), {j, 1, w}], {i, 1, W - w + 1}];
PT = Table[Sum[(P[i][[j]]* T[i][[j]]), {j, 1, w}], {i, 1, W - w + 1}];

ListPlot[TT - 2 PT, Joined -> True, PlotRange -> All]

(x=175), , .

, .

PolyT = {1, 2, 3, 4, 5};               LT = Length[PolyT];
PolyP = {1, 2, 3};                     LP = Length[PolyP];
PolyR = {};                            LR = LT + LP - 1;

eT = Table[If[i > LT, 0, PolyT[[i]]], {i, 1, LR}]
eP = Table[If[i > LP, 0, PolyP[[i]]], {i, 1, LR}]

PolyR = InverseFourier[
   Fourier[eT, FourierParameters -> {1, 1}]*
   Fourier[eP, FourierParameters -> {1, 1}]
  , FourierParameters -> {1, 1}]
PolyR[[LP ;; LT]]

{1, 2, 3, 4, 5, 0, 0} 						(* PolyT *)
{1, 2, 3, 0, 0, 0, 0} 						(* PolyP *)
{1., 4., 10., 16., 22., 22., 15.} (* PolyR = PolyT * PolyP *)
{10., 16., 22.}                   (* PolyR starting at LP to LT*)

, , n+m-1.

$\左（{1 + 2x + 3 {x ^ 2} + 4 {x ^ 3} + 5 {x ^ 4}} \右）\左（{1 + 2x + 3 {x ^ 2}} \右） = 1 + 4x + 10 {x ^ 2} + 16 {x ^ 3} + 22 {x ^ 4} + 22 {x ^ 5} + 15 {x ^ 6}$

, m ( ) m:

10 = 1*3+2*2+3*1
16 = 2*3+3*2+4*1
...

PT P . n-m+1 .

PolyT = {1, 2, 3, 4, 5};            LT = Length[PolyT];
PolyP = {1, 1, 1};                  LP = Length[PolyP];
PolyR = {};                         LR = LT + LP - 1;

eT = Table[If[i > LT, 0, PolyT[[i]]], {i, 1, LR}]
eP = Table[If[i > LP, 0, PolyP[[i]]], {i, 1, LR}]

PolyR = InverseFourier[
   Fourier[eT, FourierParameters -> {1, 1}]*
   Fourier[eP, FourierParameters -> {1, 1}]
  , FourierParameters -> {1, 1}]
PolyR[[LP ;; LT]]

{1, 2, 3, 4, 5, 0, 0}                 (* PolyT *)
{1, 1, 1, 0, 0, 0, 0}                 (* PolyP *)
{1., 3., 6., 9., 12., 9., 5.}         (* PolyR = PolyT * PolyP *)
{6., 9., 12.}                         (* PolyR starting at LP to LT*)

6 = 1*1+2*1+3*1
9 = 2*1+3*1+4*1
...

, , , - m.

DFTを使用したPPとTTの計算：

Tt = Table[If[1 <= i <= W, Part[L[[i]], 1], 0], {i, 1, Wt}] ;    (*Sample data*)
Ft = Fourier[Tt, FourierParameters -> {1, 1}];

Ts = Table[If[1 <= i <= W, (Part[L[[i]], 1])^2, 0], {i, 1, Wt}]; (*Sample squared data*)
Fs = Fourier[Ts, FourierParameters -> {1, 1}];

Es = Table[If[1 <= i <= w, 1, 0], {i, 1, Wt}] ;                  (*m size unit array*)
Fe = Fourier[Es, FourierParameters -> {1, 1}];

Pa = Table[If[1 <= i <= w, Part[L[[x + w - i]], 1], 0], {i, 1, Wt}];                                                             \
Fp = Fourier[Pa, FourierParameters -> {1, 1}];                   (*Inverse pattern data*)

TTf = InverseFourier[Fs*Fe, FourierParameters -> {1, 1}][[w ;; W]];
PTf = InverseFourier[Ft*Fp, FourierParameters -> {1, 1}][[w ;; W]];

得られた値を比較してみましょう。

ListPlot[{TT - 2 PT, TTf - 2 PTf, TT - 2 PT - TTf + 2 PTf}, Joined -> True, PlotRange -> All]

結論

この方法は概算ですが、その精度は、明るさの値が大幅に異なるテキストやほとんどの通常の画像を処理するのに十分すぎるほどです。

与えられたコードは、パフォーマンスのために最適化されたふりをしていませんが、アルゴリズムの精度を理解して評価するための便宜を目的としています。

離散フーリエ変換を使用した1次元サンプル検索

More articles: