- Por el equivalente discreto de la transformada de Laplace , ver Z-transformar .
En matemáticas , el operador discreto de Laplace es un análogo del operador continuo de Laplace , definido para que tenga significado en un gráfico o una cuadrícula discreta . Para el caso de un gráfico de dimensión finita (que tiene un número finito de aristas y vértices), el operador discreto de Laplace se denomina más comúnmente matriz Laplaciana .
El operador discreto de Laplace ocurre en problemas de física como el modelo de Ising y la gravedad cuántica de bucles , así como en el estudio de sistemas dinámicos discretos . También se utiliza en análisis numérico como sustituto del operador continuo de Laplace. Las aplicaciones comunes incluyen el procesamiento de imágenes , [1] donde se conoce como el filtro de Laplace , y en el aprendizaje automático para la agrupación en clústeres y el aprendizaje semi-supervisado en gráficos de vecindad.
Definiciones
Graph Laplacians
Hay varias definiciones del laplaciano discreto para gráficos , que se diferencian por el signo y el factor de escala (a veces se promedia sobre los vértices vecinos, otras veces solo se suman; esto no hace ninguna diferencia para un gráfico regular ). La definición tradicional del gráfico Laplaciano, dada a continuación, corresponde al Laplaciano continuo negativo en un dominio con un límite libre.
Dejar ser un grafo con vértices y bordes . Dejarser una función de los vértices que toman valores en un anillo . Entonces, el discreto laplaciano actuando es definido por
dónde es la distancia de la gráfica entre los vértices wy v. Por lo tanto, esta suma está sobre los vecinos más cercanos del vértice v . Para un gráfico con un número finito de aristas y vértices, esta definición es idéntica a la de la matriz laplaciana . Es decir,se puede escribir como un vector de columna; y entonces es el producto del vector columna y la matriz laplaciana, mientras que es solo la v ' ésima entrada del vector de producto.
Si el gráfico tiene bordes ponderados, es decir, una función de ponderación se da, entonces la definición se puede generalizar a
dónde es el valor del peso en el borde .
Estrechamente relacionado con el laplaciano discreto está el operador de promediado :
Laplacianos de malla
Además de considerar la conectividad de los nodos y los bordes en un gráfico, los operadores de Laplace de malla tienen en cuenta la geometría de una superficie (por ejemplo, los ángulos en los nodos). Para una malla triangular múltiple , el operador de Laplace-Beltrami de una función escalar en un vértice se puede aproximar como
donde la suma está sobre todos los vértices adyacentes de , y son los dos ángulos opuestos al borde , y es el área del vértice de; es decir, un tercio de las áreas sumadas de triángulos incidentes a. La fórmula cotangente anterior se puede derivar usando muchos métodos diferentes, entre los que se encuentran elementos finitos lineales por partes , volúmenes finitos (ver [2] para una derivación) y cálculo exterior discreto (ver [1] ).
Para facilitar el cálculo, el laplaciano está codificado en una matriz. tal que . Dejarser la matriz cotangente (escasa) con entradas
Dónde denota el barrio de .
Y deja ser la matriz de masa diagonal cuyo -th entrada a lo largo de la diagonal es el área del vértice . Luego es la buscada discretización del laplaciano.
En [3] se ofrece una descripción más general de los operadores de malla.
Diferencias finitas
Las aproximaciones del Laplaciano , obtenidas por el método de diferencias finitas o por el método de elementos finitos , también pueden llamarse Laplacianos discretos . Por ejemplo, el laplaciano en dos dimensiones se puede aproximar utilizando el método de diferencias finitas de la plantilla de cinco puntos , lo que resulta en
donde el tamaño de la cuadrícula es h en ambas dimensiones, de modo que la plantilla de cinco puntos de un punto ( x , y ) en la cuadrícula es
Si el tamaño de la cuadrícula h = 1, el resultado es el Laplaciano discreto negativo en el gráfico, que es la cuadrícula de celosía cuadrada . No hay restricciones aquí sobre los valores de la función f ( x , y ) en el límite de la cuadrícula de celosía, por lo tanto, este es el caso de que no haya fuente en el límite, es decir, una condición de límite sin flujo (también conocida como aislamiento , o condición de frontera de Neumann homogénea ). El control de la variable de estado en el límite, como f ( x , y ) dado en el límite de la cuadrícula (también conocido como condición de límite de Dirichlet ), rara vez se usa para gráficos laplacianos, pero es común en otras aplicaciones.
Los laplacianos discretos multidimensionales en cuadrículas regulares cuboides rectangulares tienen propiedades muy especiales, por ejemplo, son sumas de Kronecker de laplacianos discretos unidimensionales, ver suma de Kronecker de laplacianos discretos , en cuyo caso todos sus autovalores y autovectores pueden calcularse explícitamente.
Método de elementos finitos
En este enfoque, el dominio se discretiza en elementos más pequeños, a menudo triángulos o tetraedros, pero son posibles otros elementos como rectángulos o cuboides. Luego, el espacio de la solución se aproxima utilizando las llamadas funciones de forma de un grado predefinido. La ecuación diferencial que contiene el operador de Laplace se transforma luego en una formulación variacional y se construye un sistema de ecuaciones (problemas lineales o de valores propios). Las matrices resultantes suelen ser muy escasas y se pueden resolver con métodos iterativos.
Procesamiento de imágenes
El operador discreto de Laplace se utiliza a menudo en el procesamiento de imágenes, por ejemplo, en aplicaciones de detección de bordes y estimación de movimiento. [4] El Laplaciano discreto se define como la suma de las segundas derivadas del operador de Laplace # Expresiones de coordenadas y se calcula como la suma de las diferencias sobre los vecinos más cercanos del píxel central. Dado que los filtros derivados suelen ser sensibles al ruido en una imagen, el operador de Laplace suele ir precedido de un filtro de suavizado (como un filtro gaussiano) para eliminar el ruido antes de calcular la derivada. El filtro de suavizado y el filtro de Laplace a menudo se combinan en un solo filtro. [5]
Implementación mediante discretización del operador
Para señales unidimensionales, bidimensionales y tridimensionales, el laplaciano discreto se puede dar como convolución con los siguientes núcleos:
- Filtro 1D: ,
- Filtro 2D: .
corresponde a la fórmula de diferencias finitas ( plantilla de cinco puntos ) vista anteriormente. Es estable para campos que varían muy suavemente, pero para ecuaciones con soluciones que varían rápidamente se requiere una forma más estable e isotrópica del operador laplaciano, [6] como la plantilla de nueve puntos , que incluye las diagonales:
- Filtro 2D: ,
- Filtro 3D: el uso de una plantilla de siete puntos viene dado por:
- primer plano = ; segundo plano = ; tercer plano = .
- y usando una plantilla de 27 puntos por: [7]
- primer plano = ; segundo plano = ; tercer plano = .
- n Filtro D : Para el elemento del kernel
- donde x i es la posición (ya sea -1 , 0 o 1 ) del elemento en el núcleo en la i -ésima dirección, y s es el número de direcciones i para las cuales x i = 0 .
Tenga en cuenta que la versión n D, que se basa en la generalización gráfica del Laplaciano, asume que todos los vecinos están a la misma distancia y, por lo tanto, conduce al siguiente filtro 2D con diagonales incluidas, en lugar de la versión anterior:
- Filtro 2D:
Estos núcleos se deducen utilizando cocientes diferenciales discretos.
Se puede demostrar [8] [9] que la siguiente aproximación discreta del operador laplaciano bidimensional como una combinación convexa de operadores de diferencia
para γ ∈ [0, 1] es compatible con las propiedades discretas del espacio de escala, donde específicamente el valor γ = 1/3 da la mejor aproximación de la simetría rotacional. [8] [9] [10] Con respecto a las señales tridimensionales, se muestra [9] que el operador laplaciano puede ser aproximado por la familia de dos parámetros de operadores de diferencia.
dónde
Implementación mediante reconstrucción continua
Una señal discreta, que comprende imágenes, puede verse como una representación discreta de una función continua. , donde el vector de coordenadas y el dominio del valor es real . Por tanto, la operación de derivación es directamente aplicable a la función continua,. En particular, cualquier imagen discreta, con presunciones razonables sobre el proceso de discretización, por ejemplo, asumiendo funciones de banda limitada, o funciones expandibles de wavelets, etc., puede reconstruirse mediante funciones de interpolación de buen comportamiento subyacentes a la formulación de reconstrucción, [11]
dónde son representaciones discretas de en la red y son funciones de interpolación específicas de la cuadrícula . En una cuadrícula uniforme, como imágenes, y para funciones de banda limitada, las funciones de interpolación son invariantes de desplazamiento y ascienden a con siendo una función sinc adecuadamente dilatada definida en-dimensiones es decir . Otras aproximaciones deen cuadrículas uniformes, son funciones gaussianas apropiadamente dilatadas en-dimensiones. En consecuencia, el laplaciano discreto se convierte en una versión discreta del laplaciano del continuo
que a su vez es una convolución con el laplaciano de la función de interpolación en la cuadrícula uniforme (imagen) . Una ventaja de usar gaussianos como funciones de interpolación es que producen operadores lineales, incluidos los laplacianos, que están libres de artefactos rotacionales del marco de coordenadas en el que se representa a través de , en -dimensiones, y son conscientes de la frecuencia por definición. Un operador lineal no solo tiene un rango limitado en elpero también un rango efectivo en el dominio de la frecuencia (alternativamente, el espacio de escala gaussiana) que se puede controlar explícitamente a través de la varianza del Gauss de una manera basada en principios. El filtrado resultante se puede implementar mediante filtros separables y representaciones de diezmado (procesamiento de señales) / piramidales (procesamiento de imágenes) para una mayor eficiencia computacional en-dimensiones. En otras palabras, el filtro Laplaciano discreto de cualquier tamaño se puede generar convenientemente como el Laplaciano de Gauss muestreado con un tamaño espacial adecuado a las necesidades de una aplicación particular controlada por su varianza. Los monomios que son operadores no lineales también pueden implementarse utilizando un enfoque similar de reconstrucción y aproximación, siempre que la señal esté suficientemente sobremuestreada. De este modo, se pueden realizar tales operadores no lineales, por ejemplo , el tensor de estructura y el tensor de estructura generalizado que se utilizan en el reconocimiento de patrones para su optimización total de mínimos cuadrados en la estimación de orientación.
Espectro
El espectro del laplaciano discreto en una cuadrícula infinita es de interés clave; dado que es un operador autoadjunto , tiene un espectro real. Para la convención en , el espectro se encuentra dentro (ya que el operador de promediado tiene valores espectrales en ). Esto también se puede ver aplicando la transformada de Fourier. Tenga en cuenta que el laplaciano discreto en una cuadrícula infinita tiene un espectro puramente absolutamente continuo y, por lo tanto, no tiene valores propios ni funciones propias.
Teoremas
Si el gráfico es una cuadrícula de celosía cuadrada infinita , entonces se puede demostrar que esta definición del Laplaciano corresponde al Laplaciano continuo en el límite de una cuadrícula infinitamente fina. Así, por ejemplo, en una cuadrícula unidimensional tenemos
Esta definición del laplaciano se usa comúnmente en el análisis numérico y en el procesamiento de imágenes . En el procesamiento de imágenes, se considera un tipo de filtro digital , más específicamente un filtro de borde , llamado filtro de Laplace .
Operador discreto de Schrödinger
Dejar ser una función potencial definida en el gráfico. Tenga en cuenta que P puede considerarse un operador multiplicativo que actúa diagonalmente sobre
Luego es el operador discreto de Schrödinger , un análogo del operador continuo de Schrödinger .
Si el número de aristas que se encuentran en un vértice está uniformemente acotado y el potencial está acotado, entonces H es acotado y autoadjunto .
Las propiedades espectrales de este hamiltoniano se pueden estudiar con el teorema de Stone ; esto es una consecuencia de la dualidad entre posets y álgebras de Boole .
En las celosías regulares, el operador normalmente tiene soluciones de localización de onda viajera y de Anderson , dependiendo de si el potencial es periódico o aleatorio.
Función de Discrete Green
La función de Green del operador discreto de Schrödinger viene dada en el formalismo resolutivo por
dónde se entiende que es la función delta de Kronecker en el gráfico:; es decir, es igual a 1 si v = w y 0 en caso contrario.
Para fijo y un número complejo, la función de Green considerada una función de v es la única solución para
Clasificación ADE
Ciertas ecuaciones que involucran al laplaciano discreto solo tienen soluciones en los diagramas de Dynkin simplemente entrelazados (todas las aristas multiplicidad 1) y son un ejemplo de la clasificación ADE . Específicamente, las únicas soluciones positivas a la ecuación homogénea:
en palabras,
- "El doble de cualquier etiqueta es la suma de las etiquetas de los vértices adyacentes",
están en los diagramas de Dynkin ADE extendidos (afines), de los cuales hay 2 familias infinitas (A y D) y 3 excepciones (E). La numeración resultante es única hasta la escala, y si el valor más pequeño se establece en 1, los otros números son números enteros, que van hasta 6.
Los gráficos ADE ordinarios son los únicos gráficos que admiten un etiquetado positivo con la siguiente propiedad:
- El doble de cualquier etiqueta menos dos es la suma de las etiquetas en los vértices adyacentes.
En términos del Laplaciano, las soluciones positivas de la ecuación no homogénea:
La numeración resultante es única (la escala se especifica mediante el "2") y consta de números enteros; para E 8 oscilan entre 58 y 270, y se han observado ya en 1968. [12]
Ver también
- Análisis de forma espectral
- Red eléctrica
- Suma de Kronecker de laplacianos discretos
- Cálculo discreto
Referencias
- ^ Leventhal, Daniel (otoño de 2011). "Procesamiento de imágenes" (PDF) . Universidad de Washington . Consultado el 1 de diciembre de 2019 .
- ^ Crane, K., de Goes, F., Desbrun, M. y Schröder, P. (2013). "Procesamiento de geometría digital con cálculo exterior discreto" . Cursos ACM SIGGRAPH 2013 . SIGGRAPH '13. 7 . ACM, Nueva York, NY, EE. UU. págs. 7: 1–7: 126. doi : 10.1145 / 2504435.2504442 .CS1 maint: varios nombres: lista de autores ( enlace )
- ^ Reuter, M. y Biasotti, S. y Giorgi, D. y Patane, G. y Spagnuolo, M. "(2009)." Operadores discretos de Laplace-Beltrami para análisis de formas y segmentación ". Computers & Graphics . 33 (3) : 381–390df. CiteSeerX 10.1.1.157.757 . Doi : 10.1016 / j.cag.2009.03.005 .CS1 maint: varios nombres: lista de autores ( enlace )
- ^ Forsyth, DA; Ponce, J. (2003). "Visión por computador". Computadoras y Gráficos . 33 (3): 381–390. CiteSeerX 10.1.1.157.757 . doi : 10.1016 / j.cag.2009.03.005 .
- ^ Matthys, Don (14 de febrero de 2001). "Filtro LoG" . Universidad de Marquette . Consultado el 1 de diciembre de 2019 .
- ^ Provatas, Nikolas; Élder, Ken (13 de octubre de 2010). Métodos de campo de fase en ciencia e ingeniería de materiales (PDF) . Weinheim, Alemania: Wiley-VCH Verlag GmbH & Co. KGaA. pag. 219. doi : 10.1002 / 9783527631520 . ISBN 978-3-527-63152-0.
- ^ O'Reilly, H .; Beck, Jeffrey M. (2006). "Una familia de aproximaciones laplacianas discretas de plantilla grande en tres dimensiones". Revista internacional de métodos numéricos en ingeniería : 1–16.
- ↑ a b Lindeberg, T., "Espacio de escala para señales discretas", PAMI (12), No. 3, marzo de 1990, págs. 234-254.
- ^ a b c Lindeberg, T., Teoría del espacio de escala en la visión por computadora, Kluwer Academic Publishers, 1994 , ISBN 0-7923-9418-6 .
- ^ Patra, Michael; Karttunen, Mikko (2006). "Plantillas con error de discretización isotrópica para operadores diferenciales". Métodos numéricos para ecuaciones diferenciales parciales . 22 (4): 936–953. doi : 10.1002 / núm.20129 . ISSN 0749-159X .
- ^ Bigun, J. (2006). Visión con dirección . Saltador. doi : 10.1007 / b138918 . ISBN 978-3-540-27322-6.
- ^ Bourbaki, Nicolas (1968), "Capítulos 4–6", Groupes et algebres de Lie , París: Hermann
- T.Sunada , Análisis geométrico discreto, Proceedings of Symposia in Pure Mathematics (editado por P. Exner, JP Keating, P. Kuchment, T. Sunada, A. Teplyaev), 77 (2008), 51-86
enlaces externos
- Definición y aplicación a la brecha espectral