# Relationships between image pixels

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

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

$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)$
• $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$

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