ピクセル接続

画像処理において、ピクセルの接続性は、 2 次元画像 (またはn 次元画像のハイパーボクセル) 内のピクセルが隣接するピクセルとどのように関係するかを指します。

処方

5x5x5の近傍における9つの接続性

接続性のセットを指定するには、次元Nと近傍の幅nを指定する必要があります。近傍の次元は任意の次元で有効です。共通の幅は 3 です。これは、各次元に沿って、中心のセルがすべての次元で両側の 1 つのセルに隣接することを意味します。 ${\displaystyle n\geq 1}$

各次元の大きさが ${\displaystyle M_{N}^{n}}$ ${\displaystyle n=2k+1,k\in \mathbb {Z} }$

を中心構造要素から境界上の点への第一直交座標上の離散ベクトルとします。これは、各要素と少なくとも1つの成分が ${\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 M_{N}^{n}}$	接続 タイプ	典型的な ベクトル: ${\displaystyle {\vec {q}}}$	球の 半径: d	球面上の要素 : E	球内の要素 : V	近隣の つながり: G
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
	ポイント	（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
...

例

解決方法を検討する ${\displaystyle G|{\vec {q}}=(0,1,1)}$

このシナリオでは、ベクトルは3次元なので、が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次元

ピクセルの近傍の例 - 8ピクセルと4ピクセルの関連付け

4接続

4連結ピクセルは、その辺に接するすべてのピクセルと隣接しています。これらのピクセルは水平方向と垂直方向に連結されています。ピクセル座標で言えば、

${\displaystyle \textstyle (x\pm 1,y)}$または ${\displaystyle \textstyle (x,y\pm 1)}$

は のピクセルに接続されます。 ${\displaystyle \textstyle (x,y)}$

6接続

6 接続ピクセルは、六角形グリッドまたはストレッチャーボンド長方形グリッド内のいずれかのコーナーに接するすべてのピクセル (いずれかのエッジに接するピクセルを含む) に隣接します。

六角形タイルを整数ピクセル座標にマッピングする方法はいくつかあります。ある方法では、4連結ピクセルに加えて、座標 と の2つのピクセルが のピクセルに接続されます。 ${\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連結ピクセルは、その面または辺に接するすべてのピクセルと隣接しています。これらのピクセルは、主軸の1つまたは2つに沿って連結されています。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連結ピクセルは、その面、辺、または角のいずれかに接するすべてのピクセルと隣接しています。これらのピクセルは、主軸の1つ、2つ、または3つすべてに沿って連結されています。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).形態学的画像処理: アーキテクチャと VLSI 設計。 Kluwer Technische Boeken BV、 92 ～ 96ページ 。ISBN 978-1-4615-2804-3。

• A. Rosenfeld, AC Kak (1982), Digital Picture Processing , Academic Press, Inc., ISBN 0-12-597302-0
• Cheng, CC; Peng, GJ; Hwang, WL (2009)、「3次元ウェーブレット符号化におけるピクセル連結性を考慮したサブバンド重み付け」、IEEE Transactions on Image Processing、18 (1): 52– 62、Bibcode :2009ITIP...18...52C、doi :10.1109/TIP.2008.2007067、PMID  19095518 、 2009年2月16日取得
• Cheng, CC; Peng, GJ; Hwang, WL (2009)、「3次元ウェーブレット符号化におけるピクセル連結性を考慮したサブバンド重み付け」、IEEE Transactions on Image Processing、18 (1): 52– 62、Bibcode :2009ITIP...18...52C、doi :10.1109/TIP.2008.2007067、PMID  19095518 、 2009年2月16日取得

Retrieved from "https://en.wikipedia.org/w/index.php?title=Pixel_connectivity&oldid=1232758127"