Дискретный оператор Лапласа

Дискретный оператор Лапласа часто используется в обработке изображений, например, в задаче выделения границ или в приложениях оценки движения. Дискретный лапласиан определяется как сумма вторых производных и вычисляется как сумма перепадов на соседях центрального пиксела^[1].

Для одномерных, двухмерных и трёхмерных сигналов дискретный лапласиан можно задать как свёртку со следующими ядрами:

Фильтр 1D: ${\displaystyle {\vec {D}}_{x}^{2}={\begin{bmatrix}1&-2&1\end{bmatrix}}}$.

Фильтр 2D: ${\displaystyle \mathbf {D} _{xy}^{2}={\begin{bmatrix}0&1&0\\1&-4&1\\0&1&0\end{bmatrix}}}$

или с диагоналями:

Фильтр 2D: ${\displaystyle \mathbf {D} _{xy}^{2}={\begin{bmatrix}1&1&1\\1&-8&1\\1&1&1\end{bmatrix}}}$.

Фильтр 3D: ${\displaystyle \mathbf {D} _{xyz}^{3}}$

для первой плоскости = ${\displaystyle {\begin{bmatrix}0&0&0\\0&1&0\\0&0&0\end{bmatrix}}}$ ; для второй ${\displaystyle {\begin{bmatrix}0&1&0\\1&-6&1\\0&1&0\end{bmatrix}}}$ ; для третьей ${\displaystyle {\begin{bmatrix}0&0&0\\0&1&0\\0&0&0\end{bmatrix}}}$.

Эти ядра выводятся с помощью дискретных частных производных.

Есть разные определения дискретного лапласиана, различающиеся знаком и масштабным коэффициентом (иногда средние на соседних вершинах, иногда просто сумма; это не имеет значения для регулярного графа).

Пусть G=(V,E) будет графом с вершинами V и рёбрами E. Зададим функцию значений ${\displaystyle \phi \colon V\to R}$ из вершин графа в кольцо ${\displaystyle R}$. Тогда дискретный лапласиан ${\displaystyle \Delta }$ от ${\displaystyle \phi }$ будет определяться как:

${\displaystyle (\Delta \phi )(v)=\sum _{w:d(w,v)=1}\left[\phi (w)-\phi (v)\right]}$,

где d(w,v) есть функция расстояния между вершинами графа. Эта сумма — на ближайших соседях вершины v. Вершины конечного графа можно пронумеровать, тогда отображение ${\displaystyle \phi }$ может быть записано как вектор-столбец, элементами которого являются значения отображения: ${\displaystyle \phi _{v}=\phi (v)}$. Данное выше определение лапласиана также может быть переписано в векторной форме с использованием матрицы Лапласа ${\displaystyle L}$:

${\displaystyle (\Delta \phi )(v)=(L\cdot \phi )_{v}}$

Если рёбра графа имеют веса, то есть задана весовая функция ${\displaystyle \gamma \colon E\to R}$, то определение можно записать как:

${\displaystyle (\Delta _{\gamma }\phi )(v)=\sum _{w:d(w,v)=1}\gamma _{wv}\left[\phi (w)-\phi (v)\right]}$,

где ${\displaystyle \gamma _{wv}}$ есть вес ребра ${\displaystyle wv\in E}$.

Близко лежит определение усредняющего оператора:

${\displaystyle (M\phi )(v)={\frac {1}{\deg v}}\sum _{w:d(w,v)=1}\phi (w)}$