🏀 📃 🏛️ Recherche d'échantillons unidimensionnelle à l'aide de la transformation de Fourier discrète 🧛🏻 🎭 👨🏼‍⚖️

Après avoir lu l'article sur la recherche d'une image dans une image [1], il reste de nombreuses questions aux formules, et au code lui-même, où la transformation des tableaux me paraissait peu transparente en raison de l'utilisation de nombreux tiers fonctions de la bibliothèque.

Par conséquent, j'ai entrepris une recherche supplémentaire d'implémentations prêtes à l'emploi, mais malheureusement, malgré l'abondance de références à l'idée de 1974 [2], je n'ai pas trouvé d'implémentations de l'algorithme même sur le pionnier en mathématiques computationnelles Fortran. Dans les séminaires et les conférences, et même dans les mémoires, la description ne brillait pas avec intégrité, par conséquent, ayant rassemblé une douzaine d'articles et de discussions dans un tas, il y avait un désir d'écrire un article pour ceux qui veulent «tenir entre leurs mains» la mise en œuvre la plus simple de la recherche de sous-chaînes.

Et donc, j'écris généralement des programmes algorithmiques d'abord dans des packages mathématiques, et ce n'est qu'après avoir découvert la stabilité numérique et l'exactitude du fonctionnement de l'algorithme que je le traduis en code dans des langages compilés ou orientés octets. C'est mon expérience - soit compter lentement mais avec précision, soit rapidement, mais ce qui est déjà pratiquement connu. Par conséquent, pour le code illustratif de débogage, j'ai utilisé le Wolfram Language et l'ensemble des fonctions du package Mathematica V 12.

En fait, quelle est la valeur de l'idée: l'utilisation d'une transformée de Fourier discrète (DFT) réduit la complexité du calcul de "naïf" O (n * m) à O (n Log (n)), où n est le la taille du texte et m est la taille de l'échantillon souhaité. De plus, les extensions de méthode vous permettent de rechercher avec "Joker" - un symbole désignant tout autre caractère de l'alphabet, alors que les implémentations de suffixes ne le permettent pas.

Description de l'approche «naïve»:

Pour un tableau T de taille n et un échantillon P de taille m, nous calculons la fonction des carrés de la différence des valeurs des éléments. Le tableau est numéroté à partir de zéro.

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

Le résultat du calcul de la différence au carré sans terme constant

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

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

Calculer PP et TT à l'aide de 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]];

Comparons les valeurs obtenues:

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

Trois graphiques, deux coïncidant et un montrant la différence entre eux, coïncident avec l'axe.

conclusions

Malgré le fait que la méthode soit approximative, sa précision est plus que suffisante pour travailler avec du texte et la plupart des images ordinaires où les valeurs de luminosité diffèrent considérablement.

Le code donné ne prétend pas être optimisé pour les performances, mais est davantage destiné à faciliter la compréhension et l'évaluation de la précision de l'algorithme.

Recherche d'échantillons unidimensionnelle à l'aide de la transformation de Fourier discrète

More articles: