# 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-, 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!**