Relationships between image pixels

Dr. Huidae Cho
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

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

4-adjacency

8-adjacency

8-adjacency

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

dm-distance

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.

shortest-4-path-homework

Show your work for full credits!