Después de leer el artículo sobre la búsqueda de una imagen en una imagen [1], quedan muchas preguntas a las fórmulas, y al código en sí, donde la transformación de matrices no me pareció transparente debido al uso de muchos terceros. funciones de biblioteca.
Por lo tanto, emprendí una búsqueda adicional de implementaciones listas para usar, pero desafortunadamente, a pesar de la abundancia de referencias a la idea de 1974 [2], no encontré implementaciones del algoritmo ni siquiera en el creador de tendencias en matemáticas computacionales Fortran. En seminarios y conferencias, e incluso en disertaciones, la descripción no brilló con integridad, por lo tanto, después de haber recopilado una docena de artículos y discusiones en un montón, hubo un deseo de escribir un artículo para aquellos que quieren "tener en sus manos". la implementación más simple de búsqueda de subcadenas.
Entonces, generalmente escribo programas algorítmicos primero en paquetes matemáticos, y solo después de descubrir la estabilidad numérica y la corrección de la operación del algoritmo, lo traduzco a código en lenguajes compilados u orientados a bytes. Esta es mi experiencia, ya sea contando lentamente pero con precisión, o rápidamente, pero lo que ya es prácticamente conocido. Por lo tanto, para el código ilustrativo de depuración utilicé Wolfram Language y el conjunto de funciones del paquete Mathematica V 12.
En realidad, cuál es el valor de la idea: el uso de una transformada discreta de Fourier (DFT) reduce la complejidad del cálculo de "ingenuo" O (n * m) a O (n Log (n)), donde n es el el tamaño del texto y m es el tamaño de la muestra deseada. Además, las extensiones de método le permiten buscar con "Joker", un símbolo que indica cualquier otro carácter del alfabeto, mientras que las implementaciones de sufijos no lo permiten.
Descripción del enfoque "ingenuo":
Para una matriz T de tamaño n y una muestra P de tamaño m, calculamos la función de los cuadrados de la diferencia entre los valores de los elementos. La matriz se numera a partir de cero.
, . , . . S O((n-m+1)*m) , O(n*m).
:
:
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), , .
.
, .
PT
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.
, m ( ) m:
10 = 1*3+2*2+3*1
16 = 2*3+3*2+4*1
...
PT P . n-m+1 .
TT
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.
Cálculo de PP y 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]];
Comparemos los valores obtenidos:
ListPlot[{TT - 2 PT, TTf - 2 PTf, TT - 2 PT - TTf + 2 PTf}, Joined -> True, PlotRange -> All]
conclusiones
A pesar de que el método es aproximado, su precisión es más que suficiente para trabajar con texto e imágenes más comunes donde los valores de brillo difieren significativamente.
El código proporcionado no pretende estar optimizado para el rendimiento, sino que está destinado más a la conveniencia de comprender y evaluar la precisión del algoritmo.