Template Matching and Cross-Correlation

Template Matching

• Template matching identifies image regions that closely resemble a template image.
• Template matching is used for object detection, image registration, and object tracking in computer vision.

Cross-Correlation

• Cross-correlation measures the similarity between two images as one is displaced relative to the other.
• In template matching, cross-correlation locates the template image within the source image using the formula: $C(x, y) = \sum_{u,v} I(x + u, y + v) T(u, v)$
• $I(x, y)$ is the source image, and $T(x, y)$ represents the template image.
• The summation occurs over the pixels in the template image.

Normalized Cross-Correlation

• Normalized cross-correlation is less sensitive to brightness and contrast changes.
• The formula for normalized cross-correlation is: $C_{norm}(x, y) = \frac{\sum_{u,v} I(x + u, y + v) T(u, v)}{\sqrt{\sum_{u,v} I(x + u, y + v)^2 \sum_{u,v} T(u, v)^2}}$

Object Tracking

• Object tracking estimates an object's trajectory in an image sequence.
• It's a computer vision problem used in surveillance, robotics, and autonomous driving.

Simple Object Tracker

• A simple object tracker implementation uses template matching.
• Tracked objects are represented as template images.
• The tracker searches for the template image in each video frame to estimate the object's location.
• Object tracking steps:
• Select the object in the first frame.
• Create a template image.
• Search each subsequent frame for the template.
• Update and display the object's location.

OpenCV Template Matching

• The cv2.matchTemplate() function in OpenCV performs template matching with various methods:
• cv2.TM_CCOEFF: Cross-correlation
• cv2.TM_CCOEFF_NORMED: Normalized cross-correlation
• cv2.TM_CCORR: Correlation
• cv2.TM_CCORR_NORMED: Normalized cross-correlation
• cv2.TM_SQDIFF: Sum of squared differences
• cv2.TM_SQDIFF_NORMED: Normalized sum of squared differences
• The function returns a result image of matching scores.
• Use cv2.minMaxLoc() to find the best match location in the image.

OpenCV MeanShift Tracking

• MeanShift is a non-parametric clustering algorithm used for object tracking.
• It iteratively shifts a window to the densest region of a probability distribution.
• Probability distribution is typically a color histogram of the object being tracked.
• The cv2.meanShift() function implements the MeanShift algorithm in OpenCV.
• The function requires the image, initial object location, and search window size.
• cv2.meanShift Returns the object's new location.

Turing Machine Recap

• A Turing Machine (TM) is defined as $M = (Q, \Sigma, \Gamma, \delta, q_0, q_{accept}, q_{reject})$.
• $Q$ is a finite set of states.
• $\Sigma$ is the input alphabet (excluding the blank symbol $\sqcup$).
• $\Gamma$ is the tape alphabet ($\Sigma \subseteq \Gamma$, $\sqcup \in \Gamma$).
• $\delta: Q \times \Gamma \rightarrow Q \times \Gamma \times {L, R}$ is the transition function.
• $q_0 \in Q$ is the start state.
• $q_{accept} \in Q$ is the accept state.
• $q_{reject} \in Q$ is the reject state ( $q_{reject} \neq q_{accept}$).

Transition Function

• Describes the TM behavior: $\delta(q, a) = (q', b, L)$
• Read $a$ while in state $q$.
• Write $b$ to tape.
• Move to state $q'$.
• Move head to the left.

Computation

• TM receives input $w = w_1 \dots w_n \in \Sigma^*$ on the leftmost $n$ tape positions; the rest is blank ($\sqcup$).
• The head starts on the leftmost cell.
• The TM computes based on $\delta$ until it enters $q_{accept}$ or $q_{reject}$.
• Acceptance: enters $q_{accept}$.
• Rejection: enters $q_{reject}$.
• Looping: If $M$ never enters $q_{accept}$ or $q_{reject}$, $M$ loops forever.

Definitions of Acceptance

• $M$ accepts $w$ if it enters $q_{accept}$.
• $M$ rejects $w$ if it enters $q_{reject}$.
• $M$ halts on $w$ if it accepts or rejects $w$.
• $M$ loops on $w$ if it neither accepts nor rejects $w$.

Language Recognition

• $M$ recognizes language $L \subseteq \Sigma^*$ if it accepts all strings in $L$ and loops or rejects strings not in $L$.
• Denoted as $L(M) = {w \mid M \text{ accepts } w}$.
• $M$ decides $L$ if it accepts all strings in $L$ and rejects all strings not in $L$.

Recognizable and Decidable Languages

• $L$ is Turing-recognizable if there exists a TM $M$ that recognizes $L$.
• $L$ is Turing-decidable if there exists a TM $M$ that decides $L$.

Observations

• If $L$ is decidable, then $L$ is recognizable.
• If $L$ is recognizable, then $L$ may or may not be decidable.

Example

• $A = {0^n1^n \mid n \geq 0 }$ is a decidable language.

Turing Machine $M$ for $A$

• $M$ checks if the input is in the form $0^1^$, rejects if not.
• Repeats crossing off a single 0 and a single 1 until either 0's or 1's are empty
• Rejects if 0's or 1's still remain
• Accepts if the tape has no characters left

Difference between Recognizable and Decidable Languages

• Decidable, we have algorithms for whether a string is in $L$ or not.
• Recognizable, we only have algorithms that tell us whether a string is in $L$ .If the string is not in $L$, the algorithm might loop forever.

More Examples of Decidable Languages

Example: $A = { \langle G \rangle \mid G \text{ is a connected undirected graph } }$ is a decidable language

• Turing Machine $M$ for $A$
• $M$ marked the first node of $G$
• Repeats marking each node in $G$ attached by an edge to an already marked node.
• Accepts if the node of $G$ are marked otherwise it rejects.

Example: $A = { \langle M, w \rangle \mid M \text{ is a DFA that accepts } w }$ is a decidable language

• Turing Machine $M$ for $A$
• $M$ simulates in input of $w$
• Accepts if $M$ ends in $q_{accept}$ otherwise rejects.

Example: $A = { \langle N, w \rangle \mid N \text{ is an NFA that accepts } w }$ is a decidable language

• Turing Machine $M$ for $A$
• $M$ converts $N$ to $M'$ by using standard conversion procedure for conversion of NFA to DFA.
• $M'$ is simulated on input $w$.
• Accepts if $M$ ends in $q_{accept}$ otherwise rejects.

Example: $A = { \langle R \rangle \mid R \text{ is a regular expression that generates some string} }$ is a decidable language

• Turing Machine $M$ for $A$ for
• $R$ coverted $N$ by an equivilant NFA
• $N$ is converted $M'$ an equivalent DFA by the conversion procedure for an NFA to an DFA.
• Determining whether $L(M')$ is empty.
• If $L(M')$ is not empty, accept. Otherwise, reject."

Example: $A = { \langle CFG \rangle \mid CFG \text{ generates some string} }$ is a decidable language

• Turing Machine $M$ for $A$ for
• Converts $CFG$ to Chomsky Normal Form (CNF)
• Lists all derivations of the length at most $2|V |+1,$ where $|V |$ is the number of variables in $CFG$
• CFG generates a string, accept other wise rejects

The Fourier Transform

Complex Exponential

• $e^{j\theta} = cos(\theta) + j sin(\theta)$, where $j = \sqrt{-1}$

Properties

• $(e^{j\theta})^* = e^{-j\theta}$
• $|e^{j\theta}| = 1$

Fourier Transform

• $X(f) = \int_{-\infty}^{\infty} x(t)e^{-j2\pi ft}dt$

Inverse Fourier Transform

• $x(t) = \int_{-\infty}^{\infty} X(f)e^{j2\pi ft}df$
• $f$ represents frequency in Hertz (Hz)
• $t$ represents time in seconds

Fourier Transform Properties

• Linearity: $ax(t) + by(t) \leftrightarrow aX(f) + bY(f)$
• Time shift: $x(t - t_0) \leftrightarrow X(f)e^{-j2\pi ft_0}$
• Scaling: $x(at) \leftrightarrow \frac{1}{|a|}X(\frac{f}{a})$
• Duality: $X(t) \leftrightarrow x(-f)$
• Convolution: $x(t) * y(t) \leftrightarrow X(f)Y(f)$
• Multiplication: $x(t)y(t) \leftrightarrow X(f) * Y(f)$

Common Fourier Transform Pairs

Parseval's Theorem

• $\int_{-\infty}^{\infty} |x(t)|^2 dt = \int_{-\infty}^{\infty} |X(f)|^2 df$

Example

• $x(t) = cos(2\pi f_0 t)$
• $X(f) = \frac{1}{2}[\delta(f-f_0) + \delta(f+f_0)]$