En estadísticas y de procesamiento de señal , detección de paso (también conocido como suavizado paso , el filtrado de paso , detección de cambio , la detección de salto o de detección de borde ) es el proceso de encontrar los cambios bruscos (pasos, saltos, cambios) en el nivel medio de una serie de tiempo o señal. Por lo general, se considera como un caso especial del método estadístico conocido como detección de cambio o detección de punto de cambio. A menudo, el paso es pequeño y la serie temporal se corrompe con algún tipo de ruido., y esto hace que el problema sea desafiante porque el paso puede estar oculto por el ruido. Por lo tanto, a menudo se requieren algoritmos estadísticos y / o de procesamiento de señales.
El problema de detección de pasos ocurre en múltiples contextos científicos y de ingeniería, por ejemplo, en el control de procesos estadísticos [1] (el gráfico de control es el método más directamente relacionado), en la geofísica de exploración (donde el problema es segmentar un registro de pozo en estratigráficos zonas [2] ), en genética (el problema de separar datos de microarrays en regímenes similares de número de copias [3] ) y en biofísica (detectar transiciones de estado en una máquina molecular registradas en trazas de posición temporal [4] ). Para las señales 2D, el problema relacionado de la detección de bordes se ha estudiado intensamente para el procesamiento de imágenes . [5]
Algoritmos
Cuando la detección de pasos debe realizarse a medida que llegan los datos, generalmente se utilizan algoritmos en línea , [6] y se convierte en un caso especial de análisis secuencial . Dichos algoritmos incluyen el método clásico CUSUM aplicado a cambios en la media. [7]
Por el contrario, los algoritmos fuera de línea se aplican a los datos potencialmente mucho después de que se hayan recibido. La mayoría de los algoritmos fuera de línea para la detección de pasos en datos digitales se pueden clasificar como métodos de arriba hacia abajo , de abajo hacia arriba , de ventana deslizante o globales .
De arriba hacia abajo
Estos algoritmos comienzan con la suposición de que no hay pasos e introducen posibles pasos candidatos uno a la vez, probando cada candidato para encontrar el que minimiza algunos criterios (como el ajuste de mínimos cuadrados de la señal constante por partes subyacente estimada). Un ejemplo es el algoritmo de colocación de salto escalonado , estudiado por primera vez en problemas geofísicos, [2] que ha encontrado usos recientes en la biofísica moderna. [8]
De abajo hacia arriba
Los algoritmos de abajo hacia arriba adoptan el enfoque "opuesto" a los métodos de arriba hacia abajo, primero asumiendo que hay un paso entre cada muestra en la señal digital, y luego fusionando sucesivamente los pasos basados en algunos criterios probados para cada combinación de candidatos.
Ventana deslizante
Al considerar una pequeña "ventana" de la señal, estos algoritmos buscan evidencia de un paso que ocurre dentro de la ventana. La ventana se "desliza" a través de la serie temporal, paso a paso. La evidencia de un paso se prueba mediante procedimientos estadísticos, por ejemplo, mediante el uso de la prueba t de Student para dos muestras . Alternativamente, se aplica a la señal un filtro no lineal como el filtro mediano . Filtros como estos intentan eliminar el ruido conservando los pasos abruptos.
Global
Los algoritmos globales consideran la señal completa de una vez e intentan encontrar los pasos en la señal mediante algún tipo de procedimiento de optimización. Los algoritmos incluyen métodos wavelet , [9] y eliminación de ruido de variación total que utiliza métodos de optimización convexa . Cuando los pasos pueden modelarse como una cadena de Markov , también se utilizan con frecuencia los modelos ocultos de Markov (un enfoque popular en la comunidad de biofísica [10] ). Cuando solo hay unos pocos valores únicos de la media, también se puede utilizar la agrupación de k-medias .
Métodos de procesamiento de señales lineales versus no lineales para la detección de pasos
Debido a que los pasos y el ruido (independiente) tienen un ancho de banda teóricamente infinito y, por lo tanto, se superponen en la base de Fourier , los enfoques de procesamiento de señales para la detección de pasos generalmente no utilizan técnicas clásicas de suavizado como el filtro de paso bajo . En cambio, la mayoría de los algoritmos son explícitamente no lineales o varían en el tiempo. [11]
Detección de pasos y señales constantes por partes
Debido a que el objetivo de la detección de pasos es encontrar una serie de saltos instantáneos en la media de una señal, la señal media subyacente deseada es constante por partes . Por esta razón, la detección de pasos puede verse de manera rentable como el problema de recuperar una señal constante a trozos corrompida por ruido. Hay dos modelos complementarios para señales constantes por partes: como splines de 0 grados con unos pocos nudos, o como conjuntos de niveles con unos pocos niveles únicos. Por lo tanto, muchos algoritmos para la detección de pasos se entienden mejor como métodos de ajuste de spline de 0 grados o de recuperación de conjunto de niveles.
Detección de pasos como recuperación de niveles establecidos
Cuando hay solo unos pocos valores únicos de la media, las técnicas de agrupamiento como el agrupamiento de k-medias o el cambio de media son apropiadas. Estas técnicas se entienden mejor como métodos para encontrar una descripción de conjunto de niveles de la señal constante por partes subyacente.
Detección de pasos como ajuste estriado de 0 grados
Muchos algoritmos ajustan explícitamente splines de 0 grados a la señal ruidosa para detectar pasos (incluidos los métodos de colocación de salto paso a paso [2] [8] ), pero hay otros algoritmos populares que también pueden considerarse métodos de ajuste de splines después de alguna transformación , por ejemplo, eliminación de ruido de la variación total . [12]
Detección de pasos generalizada mediante eliminación de ruido constante por partes
Todos los algoritmos mencionados anteriormente tienen ciertas ventajas y desventajas en circunstancias particulares, sin embargo, un número sorprendentemente grande de estos algoritmos de detección de pasos son casos especiales de un algoritmo más general. [11] Este algoritmo implica la minimización de un funcional global: [13]
( 1 )
Aquí, x i para i = 1, ...., N es la señal de entrada en tiempo discreto de longitud N , y m i es la señal de salida del algoritmo. El objetivo es minimizar H [ m ] con respecto a la señal de salida m . La forma de la funcióndetermina el algoritmo particular. Por ejemplo, eligiendo:
donde I ( S ) = 0 si la condición S es falsa, y una en caso contrario, obtiene el algoritmo de eliminación de ruido de variación total con parámetro de regularización. Similar:
conduce al algoritmo de desplazamiento medio , cuando se utiliza un integrador de Euler de tamaño de paso adaptativo inicializado con la señal de entrada x . [13] Aquí W > 0 es un parámetro que determina el soporte del kernel de desplazamiento medio. Otro ejemplo es:
que conduce al filtro bilateral , dondees el parámetro tonal del kernel y W es el soporte espacial del kernel. Otro caso especial más es:
especificando un grupo de algoritmos que intentan ajustar codiciosamente splines de 0 grados a la señal. [2] [8] Aquí,se define como cero si x = 0 y uno en caso contrario.
Muchos de los funcionales en la ecuación ( 1 ) definidos por la elección particular deson convexos : pueden minimizarse utilizando métodos de optimización convexa . Otros son no convexos, pero se ha ideado una serie de algoritmos para minimizar estos funcionales. [13]
Detección de pasos usando el modelo de Potts
Un método variacional clásico para la detección de pasos es el modelo de Potts. Viene dado por el problema de optimización no convexa
El termino penaliza el número de saltos y el término mide la fidelidad a los datos x . El parámetro γ> 0 controla la compensación entre la regularidad y la fidelidad de los datos. Desde el minimizador es constante por partes los pasos están dados por las ubicaciones distintas de cero del gradiente . Para y Hay algoritmos rápidos que dan una solución exacta del problema de Potts en . [14] [15] [16] [17]
Ver también
- Segmentación de series de tiempo
Referencias
- ^ Página de ES (1955). "Una prueba para un cambio en un parámetro que ocurre en un punto desconocido". Biometrika . 42 (3–4): 523–527. doi : 10.1093 / biomet / 42.3-4.523 . hdl : 10338.dmlcz / 103435 .
- ^ a b c d Gill, D. (1970). "Aplicación de un método de zonificación estadística a la evaluación de yacimientos y análisis de registros digitalizados". Boletín de la Asociación Estadounidense de Geólogos del Petróleo . 54 : 719–729. doi : 10.1306 / 5d25ca35-16c1-11d7-8645000102c1865d .
- ^ Snijders, AM; et al. (2001). "Ensamblaje de microarrays para la medición de todo el genoma del número de copias de ADN". Genética de la naturaleza . 29 (3): 263–264. doi : 10.1038 / ng754 . PMID 11687795 .
- ^ Sowa, Y .; Rowe, AD; Leake, MC; Yakushi, T .; Homma, M .; Ishijima, A .; Berry, RM (2005). "Observación directa de pasos en rotación del motor flagelar bacteriano". Naturaleza . 437 (7060): 916–919. Código bibliográfico : 2005Natur.437..916S . doi : 10.1038 / nature04003 . PMID 16208378 .
- ^ Serra, JP (1982). Análisis de imágenes y morfología matemática . Londres; Nueva York: Academic Press.
- ^ Basseville, M .; IV Nikiforov (1993). Detección de cambios bruscos: teoría y aplicación . Prentice Hall.
- ^ Rodionov, SN, 2005a: una breve descripción de los métodos de detección de cambios de régimen. link to PDF En: Disturbios a gran escala (cambios de régimen) y recuperación en ecosistemas acuáticos: desafíos para la gestión hacia la sostenibilidad, V. Velikova y N. Chipev (Eds.), Taller UNESCO-ROSTE / BAS sobre cambios de régimen, 14–16 Junio de 2005, Varna, Bulgaria, 17-24.
- ^ a b c Kerssemakers, JWJ; Munteanu, EL; Laan, L .; Noetzel, TL; Janson, ME; Dogterom, M. (2006). "Dinámica de ensamblaje de microtúbulos a resolución molecular". Naturaleza . 442 (7103): 709–712. Código Bibliográfico : 2006Natur.442..709K . doi : 10.1038 / nature04928 . PMID 16799566 .
- ^ Mallat, S .; Hwang, WL (1992). "Detección y procesamiento de singularidades con wavelets". Transacciones IEEE sobre teoría de la información . 38 (2): 617–643. CiteSeerX 10.1.1.36.5153 . doi : 10.1109 / 18.119727 .
- ^ McKinney, SA; Joo, C .; Ha, T. (2006). "Análisis de trayectorias FRET de una sola molécula utilizando el modelado de Markov oculto" . Revista biofísica . 91 (5): 1941-1951. doi : 10.1529 / biophysj.106.082487 . PMC 1544307 . PMID 16766620 .
- ^ a b Little, MA; Jones, NS (2011). "Métodos generalizados y solucionadores para la eliminación de ruido de señales constantes por partes: Parte I. Teoría de antecedentes" . Proceedings of the Royal Society A . 467 (2135): 3088–3114. Código Bibliográfico : 2011RSPSA.467.3088L . doi : 10.1098 / rspa.2010.0671 . PMC 3191861 . PMID 22003312 .
- ^ Chan, D .; T. Chan (2003). "Propiedades de conservación de bordes y dependientes de la escala de la regularización de variación total". Problemas inversos . 19 (6): S165 – S187. Código Bibliográfico : 2003InvPr..19S.165S . doi : 10.1088 / 0266-5611 / 19/6/059 .
- ^ a b c Mrazek, P .; Weickert, J .; Bruhn, A. (2006). "Sobre estimación robusta y suavizado con núcleos espaciales y tonales". Propiedades geométricas para datos incompletos . Berlín, Alemania: Springer.
- ^ Mumford, D. y Shah, J. (1989). Aproximaciones óptimas mediante funciones suaves por partes y problemas de variación asociados. Comunicaciones sobre matemáticas puras y aplicadas, 42 (5), 577-685.
- ^ Winkler, G .; Liebscher, V. (2002). "Suavizadores para señales discontinuas". Revista de estadísticas no paramétricas . 14 (1–2): 203–222. doi : 10.1080 / 10485250211388 .
- ^ Friedrich; et al. (2008). "Estimación M penalizada por complejidad: cálculo rápido". Revista de Estadística Computacional y Gráfica . 17 (1): 201–224. doi : 10.1198 / 106186008x285591 .
- ^ A. Weinmann, M. Storath, L. Demaret. "La-Potts funcionales para una reconstrucción robusta de saltos dispersos. "SIAM Journal on Numerical Analysis, 53 (1): 644-673 (2015).
enlaces externos
- PWCTools: software flexible de Matlab y Python para la detección de pasos mediante eliminación de ruido constante por partes
- Pottslab: caja de herramientas de Matlab para la estimación constante por partes basada en el modelo de Potts