🤒 🍙 👂 Pencarian Sampel Satu Dimensi Menggunakan Transformasi Fourier Diskrit 🕖 👩🏻‍🏭 🔂

Setelah membaca artikel tentang mencari gambar dalam gambar [1], ada banyak pertanyaan yang tersisa untuk rumus, dan kode itu sendiri, di mana transformasi array menurut saya tidak transparan karena penggunaan banyak pihak ketiga fungsi perpustakaan.

Oleh karena itu, saya mengambil pencarian tambahan untuk implementasi siap pakai, tapi sayangnya, meskipun banyak referensi ke ide tahun 1974 [2], saya tidak menemukan implementasi algoritma bahkan pada trendsetter dalam matematika komputasi Fortran. Dalam seminar dan perkuliahan, bahkan dalam disertasi, uraiannya tidak bersinar dengan integritas, oleh karena itu, setelah mengumpulkan belasan artikel dan diskusi di tumpukan, muncul keinginan untuk menulis artikel bagi mereka yang ingin "berpegangan tangan". implementasi paling sederhana dari pencarian substring.

Jadi, saya biasanya menulis program algoritmik terlebih dahulu dalam paket matematika, dan hanya setelah mengetahui stabilitas numerik dan ketepatan operasi algoritme, saya menerjemahkannya ke dalam kode ke dalam bahasa yang dikompilasi atau berorientasi byte. Ini adalah pengalaman saya - entah menghitung perlahan tapi akurat, atau cepat, tapi apa yang sudah diketahui secara praktis. Oleh karena itu, untuk kode ilustratif debugging saya menggunakan Wolfram Language dan set fungsi paket Mathematica V 12.

Sebenarnya, apa nilai idenya: penggunaan transformasi Fourier diskrit (DFT) mengurangi kompleksitas kalkulasi dari "naif" O (n * m) menjadi O (n Log (n)), di mana n adalah ukuran teks dan m adalah ukuran sampel yang diinginkan. Selain itu, ekstensi metode memungkinkan Anda menelusuri dengan "Joker" - simbol yang menunjukkan karakter lain dalam alfabet, sementara penerapan sufiks tidak mengizinkannya.

Deskripsi pendekatan "naif":

Untuk larik T berukuran n dan sampel P berukuran m, kami menghitung fungsi kuadrat dari selisih nilai elemen. Array diberi nomor mulai dari nol.

$S_i ^ F = \ jumlah \ 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]

Hasil penghitungan selisih kuadrat tanpa suku konstanta

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

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

Menghitung PP dan TT menggunakan 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]];

Mari bandingkan nilai yang diperoleh:

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

Tiga grafik, dua bertepatan dan satu menunjukkan perbedaan di antara keduanya, bertepatan dengan sumbu.

kesimpulan

Terlepas dari kenyataan bahwa metode ini hanya perkiraan, akurasinya lebih dari cukup untuk bekerja dengan teks dan sebagian besar gambar biasa di mana nilai kecerahan berbeda secara signifikan.

Kode yang diberikan tidak berpura-pura dioptimalkan untuk performa, tetapi lebih ditujukan untuk kenyamanan pemahaman dan evaluasi keakuratan algoritme.

Pencarian Sampel Satu Dimensi Menggunakan Transformasi Fourier Diskrit

More articles: