Mathematical Image Analysis

A Note on notation

My mathematical rigor may be lacking as it has been quite a while, thus my notation may be a bit confusing and at times incorrect. Please let me know when there are mistakes or how to improve clarity.

Groups

A group is a set $G$ with a binary operation “$+$” with the following properties:

• $g_{1}$ - Associativity: $a + (b + c) = (a + b) + c$
• $g_{2}$ - Existence of “additive” identity: $a + 0 = 0 + a$
• $g_{3}$ - Existence of “additive” inverse: $\forall a \in G, \exists -a \ni a + (-a) = (-a) + a = 0$

Abelian Groups

• $g_{4}$ - Commutativity: $a + b = b + a$

For now I won’t talk about compactness, but to define an integral on a group, the group must be locally compact. For the content being covered, we will be dealing almost exclusively with locally compact abelian (LCA) groups.

Examples:

• $$(\mathbb{R}, +)$$
• $$(\mathbb{Z}, +)$$
• $$(\mathbb{Q}, +)$$
• $$(\mathbb{R}^{n \times n}, \cdot )$$

Signals Defined On Groups

Let us define a signal as a function $s: I \rightarrow G, t \mapsto s(t)$ where $I = I_{0} / P$

Where $I_o$ is a set (typically $\mathbb{R}$, $\mathbb{R}^{2}$, $\mathbb{Z}$, …) that we’ll call the domain group and $P$ is a subgroup of $I_o$ (i.e. P is a subset of $I_o$ with $g_1$, $g_2$, $g_3$) that we’ll call the periodicity group. (For now we will ignore $G$, however, for our purposes it is useful to think about this as the “intensity” of a signal at a given $t$ and is often continuous, discrete, or complex. For most of our purposes, $G = \Complex$)

Now, when we write $s(t); t\in I = I_o / P$, we mean: $s(t + p) = s(t)$$\forall t \in I_o, \forall p \in P$

Commonly used groups:

• Trivial group: $\mathbb{O} = \{ 0\}$
• Reals: $\mathbb{R}$
• Discrete w/ sampling frequency $T$: $Z(T) = \{nT: n \in \mathbb{Z}\}$

Now we can define a few commonly used signal types:

• Aperiodic continuous: $I = \mathbb{R} / \mathbb{O}$
• Aperiodic discrete with sampling period $T$: $I = Z(T) / \mathbb{O}$
• $T$ periodic continuous: $I = \mathbb{R} / Z(T)$
• $NT$ periodic discrete with sampling period $T$: $I = Z(T) / Z(NT)$

Multidimensional signals (images)

Cartesian products:

$A \times B$ is the set of ordered pairs $A \times B = \{ (a, b) : a \in A, b \in B\}$

Cartesian subgroups of $\mathbb{R}^{2}$

Let’s define the following signal $s(x, y)$:

$$s(x, y), (x, y)\in I= (I_{o_{1}} \times I_{o_{2}}) / (P_1 \times P_2) = I_{o_{1}} / P_1 \times I_{o_{2}} / P_2$$ $$s(x+p_1, y+p_2) = s(x, y)$$ $$\forall x\in I_{o_1}, \forall y\in I_{o_2}, \forall p_1\in P_1, \forall p_2\in P_2$$

It is often useful to think about the real world before it reaches a detector or certain types of detectors as images/signals defined on $I = \reals \times \reals$ (continuous).

On the other hand, it is useful to think about digital images as defined on $I = Z(T_1) \times Z(T_2) / Z(MT_1) \times Z(NT_2)$ where $T_1$ and $T_2$ are the $x, y$ pixel dimensions and the periods $M, N$ as the image size. The reason digital images are often considered periodic will become apparent later as we begin to use the Fourier transform.

Integrals

Note: topology is not my strong suit so please forgive me for any inaccuracies.

The Haar measure allows us to define the integral $\int_{I}dt$ on LCA groups (I believe it’s all locally compact groups but for now we’ll just focus on LCA) with the following properties (my notes are lacking here):

1. Linearity: $\int_{I}dt\ as(t) = a\int_{I}dt\ s(t)$
2. My notes are unexplicably lacking right here. I will revisit this section to both define Haar measure and compactness at some point.
3. If $S:I \rightarrow \reals^{I}$ and $s(t) \geq 0 \Rightarrow \forall t \in \reals, \int_{I}dt\ s(t) \geq 0$
4. Invariance w.r.t. reflection: $\int_{I}dt\ s(t) = \int_{I}dt\ s_{-}(t)$ where $s_{-}(t) = s(-t)$
5. Invariance w.r.t. translation: $\forall t_0 \in I, \int_{I}dt\ s(t-t_0) = \int_{I}dt\ s(t)$

Common domain-integral pairs:

• Continuous domain $\rightarrow$ Lebesgue Integral
• Discrete domain $\rightarrow$ Summation

For the four common types of signals we defined previously we have the following:

• $I = \mathbb{R}$ $\rightarrow \int_{I}dt\ s(t) = \int_{-\infty}^{\infty} s(t) dt$
  
• $I = Z(T)$ $\rightarrow \int_{I}dt\ s(t) = \sum_{n=-\infty}^{\infty} s(nT)$
  
• $I = \mathbb{R} / Z(T)$ $\rightarrow \int_{I}dt\ s(t) = \int_{0}^{T} s(t) dt$
  
• $I = Z(T) / Z(NT)$ $\rightarrow \int_{I}dt\ s(t) = T \sum_{n=0}^{N} s(nT)$

Note that for the periodic cases, shifting the bounds by some $t_0$ or $n_0$ is still equal to the same integral to due translational invariance. Additionally, note that the discrete integrals are multiplied by T to preserve area.

Convolutions

For two functions, $s(t), h(t)$ defined on $I$, we have the following operator:

$$(s \ast h) (t) = \int_{I} d\tau\ s(\tau) h(t-\tau)$$

Additionally, let us define the area of the signal $\mathbf{Area}(s) = \int_{I}dt\ s(t)$.

Theorem: $\mathbf{Area}(s \ast h) = \mathbf{Area} (s) \mathbf{Area} (h)$

Proof left to the reader…

Impulse

Let us also define the impulse on I as the identity w.r.t. convolution, i.e. a function $\delta_{I}(t); t \in I$ with the following property:

$$(s \ast \delta_{I}) (t) = s(t) \qquad \forall s(t), \forall t \in I$$

Properties:

1. $\mathbf{Area}(s) = 1$,
2. $s(t) \delta (t-t_0) = s(t_0) \delta(t-t_0)$,
3. Let $\delta_{I, t_0}(t) = \delta_I (t - t_0)$. Then , $(s \ast \delta_{I, t_0})(t) = s(t - t_0)$

Examples:

• For $I = \reals$: (Dirac Delta)

$$\begin{equation*} \delta_I(t) = \left\{\begin{array}{lr} 0, & t \neq 0 \\ \infty, & t = 0 \end{array}\right. \end{equation*}$$

• For $I = Z(T)$:

$$\begin{equation*} \delta_I(t) = \left\{\begin{array}{lr} 0, & t \neq 0 \\ \frac{1}{T}, & t = 0 \end{array}\right. \end{equation*}$$

Separability

Definition: A signal $s(t_1, t_2); I = I_1 \times I_2$ is separable iff:

$$s(t_1, t_2) = s(t_1)s(t_2)$$

Thus, the impulse on $I = I_1 \times I_2$ is separable:

$$\delta_I(t_1, t_2) = \delta_{I_1} (t_1) \delta_{I_2} (t_2)$$

For $I = \reals \times \reals$:

$$\begin{equation*} \delta_I(x, y) = \left\{\begin{array}{lr} 0, & t \neq 0 \\ \infty, & x=0, y=0 \end{array}\right. \end{equation*}$$

For $I = Z(T_1) \times Z(T_2)$:

$$\begin{equation*} \delta_I(n_1 T_1, n_2 T_2) = \left\{\begin{array}{lr} 0, & t \neq 0 \\ \frac{1}{T_1 T_2}, & n_1 T_1=0, n_2 T_2=0 \end{array}\right. \end{equation*}$$

Theorem: For a periodic domain $I=I_o / P$, the impulse $\delta_{I}$ is the periodic repetition of the impulse on the aperiodic domain $I_o$:

$$\delta_I (t) = \sum_{p \in P} \delta_{I_o} (t - p)$$

Examples:

• For $I = \reals / Z(T)$ (continuous periodic), the impulse is the following “Dirac comb”:

$$\delta_I(t) = \sum_{n=-\infty}^{\infty} \delta (t - nT)$$

• For $I = Z(T) / Z(NT)$ (discrete periodic), the impulse is the following:

$$\delta_I(nt) = \sum_{m=-\infty}^{\infty} \delta_{Z(T)} (nT - mNT)$$

Fourier Transform

While you are likely already familiar with Fourier transforms and dealing with going from time/space to the frequency domain, we will cover some general properties of the Fourier transform defined on LCA groups.

When we take the FT of a signal $s(t)$:

$$s(t), t \in I = I_o / P \xrightarrow{\mathcal{F}} S(f), \quad f\in \hat{I}$$

Where $\hat{I}$ is the Dual Group of $I$.

Now we have the definition of the FT on $I$ and the inverse FT on $\hat{I}$ to be

$$\mathcal{F}[s(t)](f) = S(f) = \int_{I}dt s(t) e^{- i 2 \pi f t}, \quad f \in \hat{I}$$ $$\mathcal{F}^{-1}[S(f)](t) = s(t) = \int_{\hat{I}}dt S(f) e^{i 2 \pi f t}, \quad t \in I$$

Dual and Reciprocal Groups

The dual group of $I = I_o / P$ is $\hat{I} = P^* / I_o^*$ where * indicates the reciprocal group. Examples of reciprocal groups include:

$$\reals^* = \mathbb{O}$$ $$\mathbb{O} = \reals^*$$ $$Z^* (T) = Z(\frac{1}{T})$$

Now we can define the dual groups and Fourier transforms for signals defined on our four commonly used groups:

1. Aperiodic continuous (the “classical” Fourier transform):

$$I = \reals = \reals / \mathbb{O} \quad \Longrightarrow \quad \hat{I} = \mathbb{O}^* / \reals^* = \reals / \mathbb{O}= \reals$$

1. Periodic continuous (Fourier series)

$$I = \reals / Z(T) \quad \Longrightarrow \quad \hat{I} = Z^*(T) / \reals^* = Z(\frac{1}{T}) / \mathbb{O}= Z(T)$$

1. Aperiodic Discrete (Discrete-time Fourier transform or DTFT)

$$I = Z(T) \quad \Longrightarrow \quad \hat{I} = \mathbb{O}^* / Z^*(T) = \reals / Z(\frac{1}{T})$$

1. Periodic Discrete (Discrete Fourier transform or DFT)

$$I = Z(T) / Z(NT) \quad \Longrightarrow \quad \hat{I} = Z(\frac{1}{NT}) / Z(\frac{1}{T})$$

Now note that for the periodic discrete case, the DFT becomes $\frac{1}{T}$ periodic with a sampling period of $\frac{1}{NT}$. To give a practical example, for a signal sampled with a $T = 2$ second time step and is repeated every $N=10$ time steps, the DFT of that signal will have a frequency step of $\frac{1}{10 * 2}$ Hz and will be repeated every $\frac{1}{2}$ Hz, or every 10 frequency steps.

It also becomes apparent why treating digital images as periodic is useful, since the DFT has a periodic discrete output, while the DTFT has a periodic continuous output. Representing a “periodic” discrete signal in memory is much easier than representing any continuous signal.