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]
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 .
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]
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.
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.
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 .
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]
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.
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.
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]
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:
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:
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:
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:
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.
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]
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
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]