Пиксельное подключение

В обработке изображений связность пикселей — это способ, которым пиксели в двумерных (или гипервоксели в n-мерных) изображениях соотносятся со своими соседями .

Формулировка

9 возможных связей в районе 5x5x5

Чтобы задать набор связностей, необходимо указать размерность N и ширину соседства n . Размерность соседства действительна для любого измерения . Общая ширина равна 3, что означает, что вдоль каждого измерения центральная ячейка будет смежной с 1 ячейкой с каждой стороны для всех измерений. ${\displaystyle n\geq 1}$

Пусть представим N-мерную гиперкубическую окрестность с размером по каждому измерению ${\displaystyle M_{N}^{n}}$ ${\displaystyle n=2k+1,k\in \mathbb {Z} }$

Пусть представим дискретный вектор в первом ортанте от центрального структурирующего элемента до точки на границе . Это подразумевает, что каждый элемент и что по крайней мере один компонент ${\displaystyle {\vec {q}}}$ ${\displaystyle M_{N}^{n}}$ ${\displaystyle q_{i}\in \{0,1,...,k\},\forall i\in \{1,2,...,N\}}$ ${\displaystyle q_{i}=k}$

Пусть представим N-мерную гиперсферу радиусом . ${\displaystyle S_{N}^{d}}$ ${\displaystyle d=\left\Vert {\vec {q}}\right\Vert }$

Определим количество элементов на гиперсфере в пределах окрестности как E. Для заданного E будет равно количеству перестановок, умноженному на количество ортантов. ${\displaystyle S_{N}^{d}}$ ${\displaystyle M_{N}^{n}}$ ${\displaystyle {\vec {q}}}$ ${\displaystyle {\vec {q}}}$

Пусть представим количество элементов в векторе, которые принимают значение j . ${\displaystyle n_{j}}$ ${\displaystyle {\vec {q}}}$ ${\displaystyle n_{j}=\sum _{i=1}^{N}(q_{i}=j)}$

Общее число перестановок можно представить в виде многочлена ${\displaystyle {\vec {q}}}$ ${\displaystyle {\frac {N!}{\prod _{j=0}^{k}n_{j}!}}}$

Если есть , то вектор является общим для всех ортантов. Из-за этого множитель перестановки должен быть скорректирован с до ${\displaystyle q_{i}=0}$ ${\displaystyle {\vec {q}}}$ ${\displaystyle 2^{N}}$ ${\displaystyle 2^{N-n_{0}}}$

Умножение количества перестановок на скорректированное количество ортантов дает,

${\displaystyle E={\frac {N!}{\prod _{j=0}^{k}n_{j}!}}2^{N-n_{0}}}$

Пусть V представляет собой число элементов внутри гиперсферы в пределах окрестности . V будет равно числу элементов на гиперсфере плюс все элементы на внутренних оболочках. Оболочки должны быть упорядочены по возрастанию порядка . Предположим, что упорядоченным векторам назначен коэффициент p, представляющий их место в порядке. Тогда упорядоченный вектор , если все r уникальны. Поэтому V можно определить итеративно как ${\displaystyle S_{N}^{d}}$ ${\displaystyle M_{N}^{n}}$ ${\displaystyle \left\Vert {\vec {q}}\right\Vert =r}$ ${\displaystyle {\vec {q}}}$ ${\displaystyle {\vec {q}}_{p},p\in \left\{1,2,...,\sum _{x=1}^{k}(x+1)\right\}}$

${\displaystyle V_{{\vec {q}}_{p}}=V_{{\vec {q}}_{p-1}}+E_{{\vec {q}}_{p}},V_{{\vec {q}}_{0}}=0}$,

или

${\displaystyle V_{{\vec {q}}_{p}}=\sum _{x=1}^{p}E_{{\vec {q}}_{x}}}$

Если некоторые , то оба вектора следует рассматривать как один и тот же p, такой что Обратите внимание, что к каждому соседству необходимо будет добавить значения из следующего наименьшего соседства. Пример. ${\displaystyle \left\Vert {\vec {q}}_{x}\right\Vert =\left\Vert {\vec {q}}_{y}\right\Vert }$ $${\displaystyle V_{{\vec {q}}_{p}}=V_{{\vec {q}}_{p-1}}+E_{{\vec {q}}_{p,1}}+E_{{\vec {q}}_{p,2}},V_{{\vec {q}}_{0}}=0}$$ ${\displaystyle V_{{\vec {q}}=(0,2)}=V_{{\vec {q}}=(1,1)}+E_{{\vec {q}}=(0,2)}}$

V включает центральный гипервоксель, который не включен в связность. Вычитание 1 дает связность соседства, G

${\displaystyle G=V-1}$^[1]

Таблица выбранных подключений

Пример

Рассмотрим решение для ${\displaystyle G|{\vec {q}}=(0,1,1)}$

В этом сценарии, поскольку вектор трехмерный. поскольку существует один . Аналогично, . поскольку . . Окрестность есть и гиперсфера есть ${\displaystyle N=3}$ ${\displaystyle n_{0}=1}$ ${\displaystyle q_{i}=0}$ ${\displaystyle n_{1}=2}$ ${\displaystyle k=1,n=3}$ ${\displaystyle \max q_{i}=1}$ ${\displaystyle d={\sqrt {0^{2}+1^{2}+1^{2}}}={\sqrt {2}}}$ ${\displaystyle M_{3}^{3}}$ ${\displaystyle S_{3}^{\sqrt {2}}}$

${\displaystyle E={\frac {3!}{1!*2!*0!}}2^{3-1}={\frac {6}{2}}4=12}$

Базовый в окрестности , . Манхэттенское расстояние между нашим вектором и базовым вектором равно , поэтому . Следовательно, ${\displaystyle {\vec {q}}}$ ${\displaystyle N_{3}^{3}}$ ${\displaystyle {\vec {q}}_{1}=(0,0,0)}$ ${\displaystyle \left\Vert {\vec {q}}-{\vec {q}}_{0}\right\Vert _{1}=2}$ ${\displaystyle {\vec {q}}={\vec {q}}_{3}}$

${\displaystyle G_{{\vec {q}}_{3}}=V_{{\vec {q}}_{3}}-1=E_{{\vec {q}}_{1}}+E_{{\vec {q}}_{2}}+E_{{\vec {q}}_{3}}-1=E_{{\vec {q}}=(0,0,0)}+E_{{\vec {q}}=(0,0,1)}+E_{{\vec {q}}=(0,1,1)}}$

${\displaystyle E_{{\vec {q}}=(0,0,0)}={\frac {3!}{3!*0!*0!}}2^{3-3}={\frac {6}{6}}1=1}$

${\displaystyle E_{{\vec {q}}=(0,0,1)}={\frac {3!}{2!*1!}}2^{3-2}={\frac {6}{2}}2=6}$

${\displaystyle G=1+6+12-1=18}$

Что соответствует предоставленной таблице

Более высокие значения k и N

Предположение о том, что все являются уникальными, не выполняется для более высоких значений k и N. Рассмотрим , и векторы . Хотя находится в , значение для , тогда как находится в меньшем пространстве , но имеет эквивалентное значение . но имеет большее значение , чем минимальный вектор в . ${\displaystyle \left\Vert {\vec {q}}_{p}\right\Vert =r}$ ${\displaystyle N=2,k=5}$ ${\displaystyle {\vec {q}}_{A}=(0,5),{\vec {q}}_{B}=(3,4)}$ ${\displaystyle {\vec {q}}_{A}}$ ${\displaystyle M_{2}^{5}}$ ${\displaystyle r=25}$ ${\displaystyle {\vec {q}}_{B}}$ ${\displaystyle M_{2}^{4}}$ ${\displaystyle r=25}$ ${\displaystyle {\vec {q}}_{C}=(4,4)\in M_{2}^{4}}$ ${\displaystyle r=32}$ ${\displaystyle M_{2}^{5}}$

Чтобы это предположение было верным, ${\displaystyle {\begin{cases}N=2,k\leq 4\\N=3,k\leq 2\\N=4,k\leq 1\end{cases}}}$

При более высоких значениях k и N значения d станут неоднозначными. Это означает, что спецификация данного d может относиться к нескольким . ${\displaystyle {\vec {q}}_{p}\in M_{n}^{N}}$

Типы подключения

2-мерный

Пример соседства пикселей - объединение восьми и четырех пикселей

4-связанный

4-связанные пиксели являются соседями каждого пикселя, который касается одного из их краев. Эти пиксели связаны горизонтально и вертикально. В терминах координат пикселей, каждый пиксель, который имеет координаты

${\displaystyle \textstyle (x\pm 1,y)}$или ${\displaystyle \textstyle (x,y\pm 1)}$

подключен к пикселю в . ${\displaystyle \textstyle (x,y)}$

6-связанный

Шестисвязанные пиксели являются соседями каждого пикселя, который касается одного из их углов (включая пиксели, которые касаются одного из их краев) в гексагональной сетке или прямоугольной сетке с растяжкой .

Существует несколько способов отображения шестиугольных плиток в целочисленные пиксельные координаты. С одним методом, в дополнение к 4-связанным пикселям, два пикселя в координатах и ​​соединены с пикселем в . ${\displaystyle \textstyle (x+1,y+1)}$ ${\displaystyle \textstyle (x-1,y-1)}$ ${\displaystyle \textstyle (x,y)}$

8-связанный

8-связанные пиксели являются соседями каждого пикселя, который касается одного из их краев или углов. Эти пиксели связаны по горизонтали, вертикали и диагонали. В дополнение к 4-связанным пикселям, каждый пиксель с координатами связан с пикселем в . ${\displaystyle \textstyle (x\pm 1,y\pm 1)}$ ${\displaystyle \textstyle (x,y)}$

3-х мерный

6-связанный

6-связанные пиксели являются соседями каждого пикселя, который касается одной из их граней. Эти пиксели соединены вдоль одной из основных осей . Каждый пиксель с координатами , , или соединен с пикселем в . ${\displaystyle \textstyle (x\pm 1,y,z)}$ ${\displaystyle \textstyle (x,y\pm 1,z)}$ ${\displaystyle \textstyle (x,y,z\pm 1)}$ ${\displaystyle \textstyle (x,y,z)}$

18-связанный

18-связанные пиксели являются соседями каждого пикселя, который касается одной из их граней или ребер. Эти пиксели соединены вдоль одной или двух основных осей. В дополнение к 6-связанным пикселям, каждый пиксель с координатами , , , , , или соединен с пикселем в . ${\displaystyle \textstyle (x\pm 1,y\pm 1,z)}$ ${\displaystyle \textstyle (x\pm 1,y\mp 1,z)}$ ${\displaystyle \textstyle (x\pm 1,y,z\pm 1)}$ ${\displaystyle \textstyle (x\pm 1,y,z\mp 1)}$ ${\displaystyle \textstyle (x,y\pm 1,z\pm 1)}$ ${\displaystyle \textstyle (x,y\pm 1,z\mp 1)}$ ${\displaystyle \textstyle (x,y,z)}$

26-связанный

26-связанные пиксели являются соседями каждого пикселя, который касается одной из их граней, ребер или углов. Эти пиксели связаны вдоль одной, двух или всех трех основных осей. В дополнение к 18-связанным пикселям, каждый пиксель с координатами , , , или связан с пикселем в . ${\displaystyle \textstyle (x\pm 1,y\pm 1,z\pm 1)}$ ${\displaystyle \textstyle (x\pm 1,y\pm 1,z\mp 1)}$ ${\displaystyle \textstyle (x\pm 1,y\mp 1,z\pm 1)}$ ${\displaystyle \textstyle (x\mp 1,y\pm 1,z\pm 1)}$ ${\displaystyle \textstyle (x,y,z)}$

Смотрите также

• Топология ячеек сетки
• Район Мур

Ссылки

1. Джонкер, Питер (1992). Морфологическая обработка изображений: архитектура и проектирование СБИС . Kluwer Technische Boeken BV, стр. 92–96. ISBN 978-1-4615-2804-3.

• А. Розенфельд, AC Kak (1982), Цифровая обработка изображений , Academic Press, Inc., ISBN 0-12-597302-0
• Cheng, CC; Peng, GJ; Hwang, WL (2009), "Взвешивание поддиапазонов с пиксельной связностью для трехмерного вейвлет-кодирования", IEEE Transactions on Image Processing , 18 (1): 52–62, Bibcode : 2009ITIP...18...52C, doi : 10.1109/TIP.2008.2007067, PMID  19095518 , получено 16.02.2009
• Cheng, CC; Peng, GJ; Hwang, WL (2009), "Взвешивание поддиапазонов с пиксельной связностью для трехмерного вейвлет-кодирования", IEEE Transactions on Image Processing , 18 (1): 52–62, Bibcode : 2009ITIP...18...52C, doi : 10.1109/TIP.2008.2007067, PMID  19095518 , получено 16.02.2009