Возможность подключения пикселей

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

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

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

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

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

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

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

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

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

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

Умножение количества перестановок на скорректированное количество ортантов дает результат:

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

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

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

,

или

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

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

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

G=V-1

^[1]

Таблица выбранных возможностей подключения


Район Размер: $M_{N}^{n}$	Возможности подключения Тип	Типичный Вектор: ${\vec {q}}$	Сфера Радиус: $д$	Элементы на Сфере: $И$	Элементы в сфере: $V$	Район Возможности подключения: $Г$
1	край	(0)	√ 0	1 × 1 = 1	1	0
3	точка	(1)	√ 1	1 × 2 = 2	3	2
5	точка-точка	(2)	√ 4	1 × 2 = 2	5	4
...
1 × 1	лицо	(0,0)	√ 0	1 × 1 = 1	1	0
3 × 3	край	(0,1)	√ 1	2 × 2 = 4	5	4
3 × 3	точка	(1,1)	√ 2	1 × 4 = 4	9	8
5 × 5	край-край	(0,2)	√ 4	2 × 2 = 4	13	12
	острие	(1,2)	√ 5	2 × 4 = 8	21	20
	точка-точка	(2,2)	√ 8	1 × 4 = 4	25	24
...
1 × 1 × 1	объем	(0,0,0)	√ 0	1 × 1 = 1	1	0
3 × 3 × 3	лицо	(0,0,1)	√ 1	3 × 2 = 6	7	6
	край	(0,1,1)	√ 2	3 × 4 = 12	19	18
	точка	(1,1,1)	√ 3	1 × 8 = 8	27	26
5 × 5 × 5	лицо-лицо	(0,0,2)	√ 4	3 × 2 = 6	33	32
	кромка	(0,1,2)	√ 5	6 × 4 = 24	57	56
	острие	(1,1,2)	√ 6	3 × 8 = 24	81	80
	край-край	(0,2,2)	√ 8	3 × 4 = 12	93	92
	острие	(1,2,2)	√ 9	3 × 8 = 24	117	116
	точка-точка	(2,2,2)	√ 12	1 × 8 = 8	125	124
...
1 × 1 × 1 × 1	гиперобъем	(0,0,0,0)	√ 0	1 × 1 = 1	1	0
3 × 3 × 3 × 3	объем	(0,0,0,1)	√ 1	4 × 2 = 8	9	8
	лицо	(0,0,1,1)	√ 2	6 × 4 = 24	33	32
	край	(0,1,1,1)	√ 3	4 × 8 = 32	65	64
	точка	(1,1,1,1)	√ 4	1 × 16 = 16	81	80
...

Пример

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

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

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

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

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)}

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

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

G=1+6+12-1=18

Что соответствует прилагаемой таблице

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

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

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

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

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

2-мерный

4-связный

Четырехсвязные пиксели являются соседями каждого пикселя, касающегося одного из их краев. Эти пиксели соединены горизонтально и вертикально. С точки зрения координат пикселей, каждый пиксель, имеющий координаты

\textstyle (x\pm 1,y)

или

\textstyle (x,y\pm 1)

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

6-связный

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

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

8-связный

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

3-мерный

6-связный

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

18-связный

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

26-связный

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

См. также

Ссылки

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

А. Розенфельд, AC Kak (1982), Цифровая обработка изображений , Academic Press, Inc., ISBN 0-12-597302-0
Ченг, CC; Пэн, Дж.Дж.; Хван, В.Л. (2009), «Взвешивание поддиапазонов с возможностью подключения пикселей для трехмерного вейвлет-кодирования» , Транзакции IEEE по обработке изображений , 18 (1): 52–62, Bibcode : 2009ITIP...18...52C , doi : 10.1109/TIP.2008.2007067 , PMID 19095518 , получено 16 февраля 2009 г.
Ченг, CC; Пэн, Дж.Дж.; Хван, В.Л. (2009), «Взвешивание поддиапазонов с возможностью подключения пикселей для трехмерного вейвлет-кодирования» , Транзакции IEEE по обработке изображений , 18 (1): 52–62, Bibcode : 2009ITIP...18...52C , doi : 10.1109/TIP.2008.2007067 , PMID 19095518 , получено 16 февраля 2009 г.

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

[1]