Detección de pasos

Ejemplos de señales que pueden contener pasos corrompidos por ruido. (a) Relaciones de número de copias de ADN a partir de datos de microarrays , (b) intensidad de rayos cósmicos de un monitor de neutrones , (c) velocidad de rotación en función del tiempo del motor flagelar de R. Sphaeroides , y (d) intensidad de píxeles rojos de una única línea de escaneo de una imagen digital.

En estadística y procesamiento de señales , la detección de pasos (también conocida como suavizado de pasos , filtrado de pasos , detección de desplazamientos , detección de saltos o detección de bordes ) es el proceso de encontrar cambios abruptos (pasos, saltos, desplazamientos) en el nivel medio de una serie temporal o señal. Por lo general, se considera un caso especial del método estadístico conocido como detección de cambios o detección de puntos de cambio. A menudo, el paso es pequeño y la serie temporal está corrompida por algún tipo de ruido , y esto hace que el problema sea un desafío 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 se presenta en múltiples contextos científicos y de ingeniería, por ejemplo, en el control estadístico de procesos ^[1] (siendo el diagrama de control el método más directamente relacionado), en la geofísica de exploración (donde el problema es segmentar un registro de pozo en zonas estratigráficas ^[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 tal como se registran en trazas de posición-tiempo ^[4] ). Para señales 2D, el problema relacionado de la detección de bordes se ha estudiado intensivamente para el procesamiento de imágenes . ^[5]

Algoritmos

Cuando la detección de pasos debe realizarse a medida que llegan los datos, se suelen utilizar algoritmos en línea ^[6] y se convierte en un caso especial de análisis secuencial . Entre estos algoritmos se encuentra el método CUSUM clásico aplicado a los cambios en la media ^[7] .

Por el contrario, los algoritmos fuera de línea se aplican a los datos posiblemente 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 parten del supuesto de que no hay pasos y presentan los posibles pasos candidatos uno a la vez, probando cada candidato para encontrar el que minimiza algunos criterios (como el ajuste por mínimos cuadrados de la señal constante por partes subyacente estimada). Un ejemplo es el algoritmo de colocación de saltos por pasos , 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, asumiendo primero que hay un paso entre cada muestra en la señal digital y luego fusionando sucesivamente los pasos en función de algunos criterios probados para cada fusión candidata.

Ventana corrediza

Al considerar una pequeña "ventana" de la señal, estos algoritmos buscan evidencia de que se está produciendo un paso dentro de la ventana. La ventana se "desliza" a lo largo de la serie temporal, un paso de tiempo a la vez. La evidencia de un paso se prueba mediante procedimientos estadísticos, por ejemplo, mediante el uso de la prueba t de Student de dos muestras . Alternativamente, se aplica a la señal un filtro no lineal , como el filtro de mediana . Los filtros como estos intentan eliminar el ruido al tiempo que conservan los pasos abruptos.

Global

Los algoritmos globales consideran toda la señal de una sola 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 se pueden modelar como una cadena de Markov , entonces también se utilizan a menudo los modelos de Markov ocultos (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 y 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 se puede ver de manera provechosa como el problema de recuperar una señal constante por partes corrompida por el ruido. Hay dos modelos complementarios para señales constantes por partes: como splines de 0 grados con algunos nudos o como conjuntos de niveles con algunos niveles únicos. Por lo tanto, muchos algoritmos para la detección de pasos se entienden mejor como métodos de ajuste de splines de 0 grados o de recuperación de conjuntos de niveles.

Detección de pasos como recuperación del conjunto de niveles

Cuando solo hay unos pocos valores únicos de la media, son adecuadas las técnicas de agrupamiento, como el agrupamiento de k-medias o el desplazamiento de la media . 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 de spline 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 saltos escalonados ^{[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, la eliminación de ruido de 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, una cantidad 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 una función global: ^[13]

Aquí, x _i para i  = 1, ....,  N es la señal de entrada de 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ón determina el algoritmo particular. Por ejemplo, eligiendo: ${\displaystyle \scriptstyle \Lambda }$

${\displaystyle \Lambda ={\frac {1}{2}}\left|x_{i}-m_{j}\right|^{2}I(i-j=0)+\gamma \left|m_{i}-m_{j}\right|I(i-j=1)}$

donde I ( S ) = 0 si la condición S es falsa, y 1 en caso contrario, se obtiene el algoritmo de eliminación de ruido de variación total con parámetro de regularización . De manera similar: ${\displaystyle \gamma }$

${\displaystyle \Lambda =\min \left\{{\frac {1}{2}}\left|m_{i}-m_{j}\right|^{2},W\right\}}$

conduce al algoritmo de cambio de media , 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 núcleo de cambio de media. Otro ejemplo es:

${\displaystyle \Lambda ={\frac {1-\exp(-\beta |m_{i}-m_{j}|^{2}/2)}{\beta }}\cdot I(|i-j|\leq W)}$

que conduce al filtro bilateral , donde es el parámetro del núcleo tonal y W es el soporte del núcleo espacial. Otro caso especial es: ${\displaystyle \scriptstyle \beta >0}$

${\displaystyle \Lambda ={\frac {1}{2}}\left|x_{i}-m_{j}\right|^{2}I(i-j=0)+\gamma \left|m_{i}-m_{j}\right|^{0}I(i-j=1)}$

especificando un grupo de algoritmos que intentan ajustar con avidez splines de 0 grados a la señal. ^{[2] [8]} Aquí, se define como cero si x  = 0, y uno en caso contrario. ${\displaystyle \scriptstyle \left|x\right|^{0}}$

Muchos de los funcionales en la ecuación ( 1 ) definidos por la elección particular de son convexos : se pueden minimizar utilizando métodos de optimización convexa . Otros no son convexos, pero se han ideado una variedad de algoritmos para minimizar estos funcionales. ^[13] ${\displaystyle \scriptstyle \Lambda }$

Detección de pasos mediante el modelo de Potts

Un método variacional clásico para la detección de pasos es el modelo de Potts. Está dado por el problema de optimización no convexa

${\displaystyle u^{*}=\arg \min _{u\in \mathbb {R} ^{N}}\gamma \|\nabla u\|_{0}+\|u-x\|_{p}^{p}}$

El término penaliza el número de saltos y el término mide la fidelidad a los datos x . El parámetro γ > 0 controla el equilibrio entre regularidad y fidelidad de los datos . Dado que 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]} ${\displaystyle \|\nabla u\|_{0}=\#\{i:u_{i}\neq u_{i+1}\}}$ ${\displaystyle \|u-x\|_{p}^{p}=\sum _{i=1}^{N}|u_{i}-x_{i}|^{p}}$ ${\displaystyle u^{*}}$ ${\displaystyle \nabla u^{*}}$ ${\displaystyle p=2}$ ${\displaystyle p=1}$ ${\displaystyle O(N^{2})}$

Véase también

• Segmentación de series temporales

Referencias

1. ES Page (1955). "Una prueba para detectar 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 .
2. Gill, D. (1970). "Aplicación de un método de zonificación estadística a la evaluación de yacimientos y al 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.
3. Snijders, AM; et al. (2001). "Ensamblaje de microarrays para la medición del número de copias de ADN en todo el genoma". Nature Genetics . 29 (3): 263–264. doi :10.1038/ng754. PMID  11687795. S2CID  19460203.
4. Sowa, Y.; Rowe, AD; Leake, MC; Yakushi, T.; Homma, M.; Ishijima, A.; Berry, RM (2005). "Observación directa de los pasos en la rotación del motor flagelar bacteriano". Nature . 437 (7060): 916–919. Bibcode :2005Natur.437..916S. doi :10.1038/nature04003. PMID  16208378. S2CID  262329024.
5. Serra, JP (1982). Análisis de imágenes y morfología matemática . Londres; Nueva York: Academic Press.
6. Basseville, M.; IV Nikiforov (1993). Detección de cambios abruptos: teoría y aplicación . Prentice Hall.
7. Rodionov, SN, 2005a: Una breve descripción de los métodos de detección de cambios de régimen. enlace a PDF En: Perturbaciones 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 de junio de 2005, Varna, Bulgaria, 17-24.
8. Kerssemakers, JWJ; Munteanu, EL; Laan, L.; Noetzel, TL; Janson, ME; Dogterom, M. (2006). "Dinámica de ensamblaje de microtúbulos a resolución molecular". Nature . 442 (7103): 709–712. Bibcode :2006Natur.442..709K. doi :10.1038/nature04928. PMID  16799566. S2CID  4359681.
9. Mallat, S.; Hwang, WL (1992). "Detección y procesamiento de singularidades con wavelets". IEEE Transactions on Information Theory . 38 (2): 617–643. CiteSeerX 10.1.1.36.5153 . doi :10.1109/18.119727. 
10. McKinney, SA; Joo, C.; Ha, T. (2006). "Análisis de trayectorias de FRET de moléculas individuales utilizando modelos ocultos de Markov". Revista biofísica . 91 (5): 1941–1951. doi :10.1529/biophysj.106.082487. PMC 1544307 . PMID  16766620. 
11. 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 fondo". Actas de la Royal Society A . 467 (2135): 3088–3114. Bibcode :2011RSPSA.467.3088L. doi :10.1098/rspa.2010.0671. PMC 3191861 . PMID  22003312. 
12. Chan, D.; T. Chan (2003). "Propiedades de regularización de variación total que preservan los bordes y dependen de la escala". Problemas inversos . 19 (6): S165–S187. Código Bibliográfico :2003InvPr..19S.165S. doi :10.1088/0266-5611/19/6/059. S2CID  30704800.
13. 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.
14. Mumford, D., y Shah, J. (1989). Aproximaciones óptimas mediante funciones suaves por partes y problemas variacionales asociados. Communications on pure and applied mathematics, 42(5), 577-685.
15. Winkler, G.; Liebscher, V. (2002). "Suavizadores para señales discontinuas". Journal of Nonparametric Statistics . 14 (1–2): 203–222. doi :10.1080/10485250211388. S2CID  119562495.
16. Friedrich; et al. (2008). "Estimación M con penalización de complejidad: computación rápida". Revista de estadística computacional y gráfica . 17 (1): 201–224. doi :10.1198/106186008x285591. S2CID  117951377.
17. A. Weinmann, M. Storath, L. Demaret. "El funcional de -Potts para la reconstrucción robusta de saltos dispersos". Revista SIAM sobre análisis numérico, 53(1):644-673 (2015). ${\displaystyle L^{1}}$

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 de constantes por partes basada en el modelo de Potts