👩‍🚒 ♥️ 👉🏾 Eindimensionale Probensuche mit diskreter Fourier-Transformation ☎️ ☹️ 🥋

Nach dem Lesen des Artikels über die Suche nach einem Bild in einem Bild [1] bleiben den Formeln und dem Code selbst viele Fragen offen, bei denen mir die Transformation von Arrays aufgrund der Verwendung vieler Drittanbieter nicht transparent erschien Bibliotheksfunktionen.

Daher habe ich eine zusätzliche Suche nach vorgefertigten Implementierungen aufgenommen, aber leider habe ich trotz der Fülle von Verweisen auf die Idee von 1974 [2] selbst auf dem Trendsetter in der Computermathematik Fortran keine Implementierungen des Algorithmus gefunden. In Seminaren und Vorträgen und sogar in Dissertationen strahlte die Beschreibung nicht mit Integrität. Nachdem ein Dutzend Artikel und Diskussionen auf einem Haufen gesammelt worden waren, bestand der Wunsch, einen Artikel für diejenigen zu schreiben, die "in ihren Händen halten" wollen. die einfachste Implementierung der Teilstringsuche.

Daher schreibe ich normalerweise algorithmische Programme zuerst in mathematischen Paketen, und erst nachdem ich die numerische Stabilität und Korrektheit der Operation des Algorithmus herausgefunden habe, übersetze ich sie in Code in kompilierte oder byteorientierte Sprachen. Dies ist meine Erfahrung - entweder langsam aber genau oder schnell zählen, aber was bereits praktisch bekannt ist. Daher habe ich für den illustrativen Debugging-Code die Wolfram-Sprache und die Funktionen des Mathematica V 12-Pakets verwendet.

Was ist eigentlich der Wert der Idee: Die Verwendung einer diskreten Fourier-Transformation (DFT) reduziert die Komplexität der Berechnung von "naiv" O (n * m) auf O (n Log (n)), wobei n die ist Textgröße und m ist die Größe der gewünschten Stichprobe. Darüber hinaus können Sie mit Methodenerweiterungen mit "Joker" suchen - einem Symbol, das jedes andere Zeichen im Alphabet kennzeichnet, während Suffix-Implementierungen dies nicht zulassen.

Beschreibung des "naiven" Ansatzes:

Für ein Array T der Größe n und eine Stichprobe P der Größe m berechnen wir die Funktion der Quadrate der Differenz der Elementwerte. Das Array ist ab Null nummeriert.

$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]

Das Ergebnis der Berechnung der quadratischen Differenz ohne konstanten Term

(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.

$\ left ({1 + 2x + 3 {x ^ 2} + 4 {x ^ 3} + 5 {x ^ 4}} \ right) \ left ({1 + 2x + 3 {x ^ 2}} \ right) = 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.

Berechnung von PP und TT mit DFT:

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]];

Vergleichen wir die erhaltenen Werte:

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

Drei Diagramme, von denen zwei zusammenfallen und eines den Unterschied zwischen ihnen zeigt, fallen mit der Achse zusammen.

Schlussfolgerungen

Trotz der Tatsache, dass die Methode ungefähr ist, ist ihre Genauigkeit mehr als ausreichend für die Arbeit mit Text und den meisten normalen Bildern, bei denen sich die Helligkeitswerte erheblich unterscheiden.

Der angegebene Code gibt nicht vor, für die Leistung optimiert zu sein, sondern dient eher dem Verständnis und der Bewertung der Genauigkeit des Algorithmus.

Eindimensionale Probensuche mit diskreter Fourier-Transformation

More articles: