Relationships between image pixels
1 Neighbors of a pixel
- A pixel $p$ at $(x,y)$ has four horizontal and vertical neighbors $N_4(p)$ or 4-neighbors in blue.
- Four diagonal neighbors of $p$ or $N_D(p)$ in green
- $N_8(p)=N_4(p) \cup N_D(p)$ or 8-neighbors
2 Adjacency
$V=\{\text{gray levels of similarity}\}$
Two pixels $p$ and $q$ have a pixel value from $V$: \[f(p)\in V\text{ and }f(q)\in V\]
- 4-adjacency if $q\in N_4(p)$
- 8-adjacency if $q\in N_8(p)$
- m-adjacency (mixed) if
- $q\in N_4(p)$ or
- $q\in N_D(p)$ and $N_4(p)\cap N_4(q)$ has no pixels whose values are from $V$
2.1 Adjacency examples
4-adjacency
8-adjacency
m-adjacency
3 Connectivity
- $p$ at $(x_0,y_0)=(x,y)$ and $q$ at $(x_n,y_n)=(s,t)$
- A sequence of distinct pixels $(x_0,y_0),(x_1,y_1),\cdots,(x_n,y_n)$ is a path from $p$ to $q$ if $(x_i,y_i)$ and $(x_{i-1},y_{i-1})$ are adjacent for $1\leq i\leq n$
- 4-, 8-, or m-path depending on the adjacency
- Let $S$ be a subset of pixels in an image, two pixels $p$ and $q$ are connected in $S$ if there exists a path in $S$ between the two pixels
- For $p\in S$, the set of pixels connected to it in $S$ is a connected component of $S$
- If $S$ has only one connected component, it is called a connected set
- Two subsets $S_1$ and $S_2$ are adjacent if a pixel in $S_1$ is adjacent to another pixel in $S_2$
4 Region and boundary
- Let $R$ be a subset of pixels in an image, $R$ is a region of the image if $R$ is a connected set
- The boundary (border or contour) of a region $R$ is the set of pixels in the region that have neighbors that are not in $R$
- The first and last rows and columns if $R$ is an entire image
5 Distance measures
5.1 Distance requirements
$p$ at $(x,y)$, $q$ at $(u,v)$, and $s$ at $(w,z)$
$D$ is a distance function or metric if
- $D(p,q)\geq0$ ($D(p,q)=0\text{ iff }p=q$),
- $D(p,q)=D(q,p)$, and
- $D(p,s)\leq D(p,q)+D(q,s)$.
5.2 Different distance measures
- Euclidean distance \[D_e(p,q)=\left[(x-u)^2+(y-v)^2\right]^{1/2}\]
- $D_4$ distance or city-block distance (aka Manhattan distance, boxcar distance, alsolute value distance) \[D_4(p,q)=|x-u|+|y-v|\]
- $D_8$ distance or chessboard distance \[D_8(p,q)=\max\left(|x-u|,|y-v|\right)\]
- $D_m$ distance based on m-adjacency: Shortest m-path
6 Operations
6.1 Pixel-by-pixel operations
Images $f$ and $g$ are often represented by matrices.
Dividing image $f$ by image $g$
- Does not mean matrix division (not defined anyway)
- Means dividing pixels in $f$ by corresponding pixels in $g$
6.2 Linear vs. nonlinear operations
An operator $H$ whose input and output are images is linear if \[H(af+bg)=aH(f)+bH(g)\] where $f$ and $g$ are images, and $a$ and $b$ are scalars.
- Sum is linear because $\sum(af+bg)=a\sum f+b\sum g$.
- Absolute is nonlinear because $|af+bg|\neq a|f|+b|g|$.
Can you find more examples of nonlinear operations?
7 Homework: Shortest paths
Problem 2.20(b) on page 125.
Let $V=\{1,2\}$. Find the shortest 4-, 8-, and m-path between $p$ and $q$, and calculate their lengths. If there are no path, explain why. Use the $D_m$ distance for length calculations.
Show your work for full credits!