# Relationships between image pixels

Institute for Environmental and Spatial Analysis...University of North Georgia

Contents

## 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

## 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-, 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 $p$ has only one connected component in $S$, 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 $(s,t)$, and $z$ at $(v,w)$

$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,z)\leq D(p,q)+D(q,z)$.

### 5.2 Different distance measures

- Euclidean distance \[D_e(p,q)=\left[(x-s)^2+(y-t)^2\right]^{1/2}\]
- $D_4$ distance or city-block distance (aka Manhattan distance, boxcar distance, alsolute value distance) \[D_4(p,q)=|x-s|+|y-t|\]
- $D_8$ distance or chessboard distance \[D_8(p,q)=\max\left(|x-s|,|y-t|\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 4-path

Let $V=\{1,2\}$. Is the shortest 4-path between $p$ and $q$ unique?

**Show your work for full credits!**