😾 🎛️ 🎫 Pesquisa de amostra unidimensional usando transformada discreta de Fourier 🙏🏿 👨🏼‍🏫 💃🏿

Depois de ler o artigo sobre a busca de uma imagem em uma imagem [1], muitas questões foram deixadas para as fórmulas, e para o próprio código, onde a transformação de matrizes me pareceu não transparente devido ao uso de muitos terceiros funções de biblioteca.

Portanto, fiz uma busca adicional por implementações prontas, mas infelizmente, apesar da abundância de referências à ideia de 1974 [2], não encontrei implementações do algoritmo mesmo no criador de tendências em matemática computacional Fortran. Em seminários e palestras, e mesmo em dissertações, a descrição não brilhou com integridade, portanto, tendo reunido uma dezena de artigos e discussões em uma pilha, houve o desejo de escrever um artigo para quem quer "segurar nas mãos" a implementação mais simples de pesquisa de substring.

E assim, eu geralmente escrevo programas algorítmicos primeiro em pacotes matemáticos, e só depois de descobrir a estabilidade numérica e a correção da operação do algoritmo eu traduzo em código em linguagens compiladas ou orientadas a bytes. Esta é a minha experiência - ou contando lentamente, mas com precisão, ou rapidamente, mas o que já é conhecido na prática. Portanto, para o código ilustrativo de depuração utilizei a linguagem Wolfram e o conjunto de funções do pacote Mathematica V 12.

Na verdade, qual é o valor da ideia: o uso de uma transformada discreta de Fourier (DFT) reduz a complexidade do cálculo de O "ingênuo" (n * m) para O (n Log (n)), onde n é o tamanho do texto em é o tamanho da amostra desejada. Além disso, as extensões de método permitem pesquisar com "Joker" - um símbolo que denota qualquer outro caractere no alfabeto, enquanto as implementações de sufixo não permitem isso.

Descrição da abordagem "ingênua":

Para uma matriz T de tamanho n e uma amostra P de tamanho m, calculamos a função dos quadrados da diferença nos valores dos elementos. A matriz é numerada começando em zero.

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

O resultado do cálculo da diferença quadrática sem um termo constante

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

Calculando PP e TT usando 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]];

Vamos comparar os valores obtidos:

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

Três gráficos, dois coincidentes e um mostrando a diferença entre eles, coincidem com o eixo.

conclusões

Apesar de o método ser aproximado, sua precisão é mais do que suficiente para trabalhar com texto e a maioria das imagens comuns onde os valores de brilho diferem significativamente.

O código fornecido não pretende ser otimizado para desempenho, mas se destina mais à conveniência de compreender e avaliar a precisão do algoritmo.

Pesquisa de amostra unidimensional usando transformada discreta de Fourier

More articles: