comparar las líneas y reconocer similares

Question

¿cómo puedo encontrar patrones similares en una línea si tengo una "plantilla de línea"?

En este ejemplo, si tengo la plantilla (rojo), ¿cómo puedo saber que hay dos ocurrencias en el verde? Las líneas que no coinciden exactamente y min/max valores pueden ser diferentes, pero el tipo es similar. Hay una manera de/algoritmo para conseguir esto?

Tengo los valores X e y de todos estos puntos, si eso ayuda.

Answer 1

Si la anchura de la función de prueba no será modificada, a continuación, un método simple consiste en el cálculo de la correlación cruzada. La correlación cruzada de $(f\star g)(t)$ de dos funciones de $f$ $g$ cuantifica el grado de similitud entre las dos funciones son para un determinado desplazamiento $t$.

Correlación cruzada puede ser calculado usando una convolución. Usted puede tomar su prueba de la función $f(t)$, dicen, y de convolución $f(-t):=h(t)$ con su conjunto de datos de la función $g(t)$, donde la función de prueba "se produce" obtendrá un pico. Mediante la aplicación de un umbral adecuado (que dependerá en gran parte de los datos) puede detectar ocurrencias de la $f$. I. e. las apariciones son indicados por $$ (f\star g)(t) = (h * g)(t) > H$$ para un adecuado $H$.

Aquí es un ejemplo muy sencillo donde he asumido que $f$ $g$ son muestreados en los mismos intervalos. Esta es nuestra función de prueba: Este es nuestros datos: Convolving juntos atractivos, donde las dos curvas de aspecto similar.

Aquí hay otro ejemplo con una función de prueba que no es una función impar. Uno puede ver que el método es relativamente robusto en la adición de ruido significativo.

Como se dijo anteriormente esto no va a funcionar bien si el ancho de la prueba de función también está siendo ampliado. En este caso me gustaría ver a óndula, que podría ser justo lo que estás buscando.

Answer 2

Suponiendo que se sabe (de algún lado la información) que no puede haber más de $1<M<\infty$ occurencies de $s(t)$, el problema puede ser planteado como una instancia de un (varios) pruebas de hipótesis problema: Dado $y(t)$, $t \in [0, T] $, debemos decidir cual de las $M$ hipótesis $\mathcal{H}_m$, $m \in \{1,\ldots,M\}$ se ha producido, donde \begin{equation} \mathcal{H}_m: y(t) = \sum_{i=1}^m a_i s(t-\tau_i) + n(t), m \in \{1,\ldots,M\} \end{equation} es la hipótesis de que hay $m$ apariciones de $s(t)$ donde $\{\tau_i\}_{i=1}^m$ son los retrasos de las apariciones de $s(t)$ ($0 < \tau_i < \tau_j <T_y$, para $i<j$), $\{a_i\}_{i=1}^m$ son los beneficios correspondientes (escalas) ($a_i \in \mathbb{R}$) y $n(t)$ es el ruido. Ya que estamos a sólo interés en la hipótesis de que se produce y no en los parámetros de $\{\tau_i\}_{i=1}^m$$\{a_i\}_{i=1}^m$, este último se conoce generalmente como "molestia" parámetros como su presencia complica el problema.

Con el fin de continuar, debemos hacer suposiciones sobre las propiedades estadísticas de $n(t)$. Un común y matemáticamente conveniente opción es considerar que (suponemos) que $n(t)$ es un ejemplo de un cero significa blanco Gaussiano proceso de alimentación de $N_0/2$.

Supongamos por un momento que sabemos que la molestia de los parámetros, es decir, sabemos que si la hipótesis de $\mathcal{H}_m$ se ha producido, esto sólo puede ser así con el parámetro conocido los valores de $\{\tau_i\}_{i=1}^m$$\{a_i\}_{i=1}^m$. Tenga en cuenta que si no había ruido (es decir, $N_0=0$) esto significaría que sabemos qué hipótesis se produjo por la simple inspección de $y(t)$. Sin embargo, la presencia de ruido presenta incertidumbre (lo que podría parecer una cierta hipótesis pueden ser engañosas debido a una "mala" ruido de realización). Dado el ruido Gaussiano de la asunción, y omitiendo detalles técnicos, uno comúnmente empleada en la regla de decisión es la siguiente:

La máxima probabilidad regla de decisión $\hat{\mathcal{H}}_m$ ( $\hat{m}$ ) es \begin{equation} \hat{m}= \arg \max_{m \in \{1,\ldots,M\}}\ \mathcal{L}(y(t)|\mathcal{H}_m,\{\tau_i\}_{i=1}^m,\{a_i\}_{i=1}^m), \end{equation}

donde $\mathcal{L}(y(t)|\mathcal{H}_m,\{\tau_i\}_{i=1}^m,\{a_i\}_{i=1}^m)$ es la probabilidad funcional de la hipótesis de $m$, da como \begin{equation} \mathcal{L}(y(t)|\mathcal{H}_m,\{\tau_i\}_{i=1}^m,\{a_i\}_{i=1}^m) \triangleq \exp \left\{\frac{2}{N_0} \sum_{i=1}^m a_i\int_0^{T}y(t)s(t-\tau_i)dt - \frac{1}{N_0} \sum_{i=1}^m\sum_{j=1}^m a_i a_j \int_0^{T}\int_0^{T}s(t-\tau_i)s(u-\tau_j)dtdu\right\} \end{equation}

Tenga en cuenta que el segundo término de la exponencial puede ser pre-calculadas, lo que significa que sólo la correlación de $y(t)$ con el desplazado versiones de $s(t)$ es necesario para el cálculo de la probabilidad funcional. La correlación se realiza normalmente por tiempo discreto lineal de filtrado y la complejidad general es relativamente pequeño.

Ahora, con el fin de tomar en cuenta la presencia de la molestia de los parámetros, tenemos que hacer (más) supuestos sobre sus propiedades estadísticas. Uno de los enfoques (Bayesiano) es asumir una cierta distribución (pdf) para la molestia de los parámetros y emplean la misma regla de decisión como en el anterior, esta vez usando el parámetro-un promedio de probabilidad funcional $\mathcal{E}(\mathcal{L}(y(t)|\mathcal{H}_m,\{\tau_i\}_{i=1}^m,\{a_i\}_{i=1}^m))$ donde $\mathcal{E}(\cdot)$ denota la expectativa sobre el pdf de $\{\tau_i\}_{i=1}^m,\{a_i\}_{i=1}^m$.

Otro enfoque es la de asumir que no hay propiedades estadísticas para la molestia de los parámetros. En ese caso, un método comúnmente empleado regla de decisión (generalizada de máxima verosimilitud) es usar la misma regla de decisión como en el anterior, esta vez usando el parámetro-maximiza la probabilidad funcional, es decir, $\max(\mathcal{L}(y(t)|\mathcal{H}_m,\{\tau_i\}_{i=1}^m,\{a_i\}_{i=1}^m))$ donde la maximización de la es $\{\tau_i\}_{i=1}^m,\{a_i\}_{i=1}^m$. Tenga en cuenta que, para la "ganadora" hipótesis"$\hat{m}$, la maximización de la molestia de los valores de los parámetros pueden ser consideradas como estimaciones de los retrasos y cambios de escala de la $\hat{m}$ apariciones de $s(t)$.