Computer Vision

\[T: \mathbb{R} \rightarrow \mathbb{R}\quad g(x,y) =T(f(x,y))\]

• contrast stretching

• intensity thresholding

  • automatic: otsu, isodata, multilevel
• intensity inversion
• log transformation
• power transformation
• piecewise linear transformation
• piecewise contrast stretching
• gray-level slicing
• bit-plane slicing
• histogram of pixel values
• histogram-based thresholding "triangle"

• histogram equalisation

  • continuous; discrete
  • constrained

• histogram matching

  • continuous, discrete
• arithmetic and logical operations
• averaging

\[T: \mathbb{R^n} \rightarrow \mathbb{R}\quad g(x,y) = T(f(x,y),f(x+1,y),f(x-1,y),...\]

• convolution

  • linear, shift-invariant

  • properties:

    • commutativity \[f_1 * f_2 = f_2 * f_1 \]
    • associativity \[f_1 * (f_2 * f_3) = (f_1 * f_2) * f_3 \]
    • distributivity \[f_1 * (f_2 * f_3) = f_1 * f_2 + f_1 * f_3\]
    • multiplicativity \[a(f_1*f_2) = (a f_1) * f_2 = f_1 * (a f_2) \]
    • derivation \[(f_1 * f_2)' = f_1'*f_2 = f_1*f_2' \]
    • theorem \[f_1 * f_2 \iff \hat{f_1} \hat{f_2}\] convolution in spatial domain amounts to multiplication in spectral domain
• spatial filtering
• linear shift-invariant operations

• border problem

  • padding: add more pixels with value 0
  • clamping: repeat all border pixel values indefinitely
  • wrapping: copy pixel values from opposite sides
  • mirroring: reflect pixel values across borders

• interpretations:

  • frequencies correspond to patterns
  • $F(0,0)$ is the total intensity over all pixels of the image
  • noise (typically) corresponds to fluctuations in the highest frequencies

• notation:

  • $f(x)$ is the spatial input function
  • $F(u)$ is the Fourier transform
  • $e^{i\omega x} = \cos(\omega x) + i\sin(\omega x) $
  • $\omega = 2\pi u$ is radial frequency
  • $u$ is spatial frequency
• forward fourier transform \[F(u) = \int^\infty_{-\infty} f(x)\; e^{\displaystyle -i 2\pi u x}\,\mathrm{d}x\]
• inverse fourier transform \[f(x) = \int^\infty_{-\infty} F(u)\; e^{\displaystyle i 2\pi u x}\,\mathrm{d}u\]
• properties:

• 2D:

  • forward fourier transform \[F(u,v) = \int^\infty_{-\infty}\int^\infty_{-\infty} f(x,y)\; e^{\displaystyle -i 2\pi (ux+vy)}\;\mathrm{d}x\,\mathrm{d}y\]
  • inverse fourier transform \[f(x,y) = \int^\infty_{-\infty}\int^\infty_{-\infty} F(u,v)\; e^{\displaystyle -i 2\pi (ux+vy)}\;\mathrm{d}u\,\mathrm{d}v\]
  • $f \leftrightarrow F$: fourier transform pair
  • $F = R + i I$: real plus imaginary part
  • $|F| = \sqrt{R^2 + I^2}$: Magnitude
  • $\phi = \arctan(\frac{I}{R})$: Phase

• Discrete:

  • forward \[F(u,v) = \sum_{x=0}^{M-1} \sum_{y=0}^{N-1} f(x,y)\;e^{\displaystyle -i 2 \pi (\frac{ux}{M} + \frac{vy}{N})} \] for $u=0... M-1$ and $v = 0... N -1$
  • inverse \[f(x,y) = \frac{1}{MN} \sum_{u=0}^{M-1} \sum_{v=0}^{N-1} F(u,v)\;e^{\displaystyle i 2\pi (\frac{ux}{M} + \frac{vy}{N})} \] for $x=0... M-1$ and $y = 0... N -1$

• procedure:

  1. multiply input image $f(x,y)$ by $(-1)^{x+y}$ to ensure centering $F(u,v)$
  2. compute the transform $F(u,v)$ from image $f(x,y)$ using 2D DFT
  3. multiply $F(u,v)$ by a centred filter $H(u,v)$ to obtain result $G(u,v)$
  4. compute the inverse 2D DFT of $G(u,v)$ to obtain the spatial result $g(x,y)$
  5. take the real component of $g(x,y)$ (imaginary component is zero)
  6. multiply the result by $(-1)^{x+y}$ to remove the pattern introduced in step 1^^

(TODO add image demo?)

• represent the global distribution of pixel colours in an image
• step 1: construct a histogram for each colour channel (R, G, B)
• step 2: concatenate the histogrames (vectors) of all channels as the final feature vector.

• moments based representation of colour distributions
• gives a feature vector of only 9 elements (for RGB)
• lower representation capability than above histogram

• array of statistical descriptors of image patterns
• captures spatial relationship between neighbouring pixels
• step 1: construct the gray-level co-occurence matrix (GLCM) - representing the frequency of peixel intensity pairs occurring at a specific offset and direction
• step 2: compute the Haralick feature descriptors from the GLCM - that summarises texture information (how pixel intensities are spatially related)
• often used in practice due to their simplicity and interpretability.

• describe the spatial structure of local image texture

algorithm:

• divide the image into cells of $N\times N$ pixels ($N=16$ or $N=32$)
• compare each pixel in a given cell to each of its 8 neighbouring pixels
• if the neighbour's value is greater than or equal to the centre, write 1; otherwise write 0.
• this gives an 8-digit binary pattern per pixel, representing a value in the range $0...255$
• count the number of times each 8-digit binary number occurs in the cell
• this gives a 256-bin histogram (also known as the LBP feature vector)
• combine the histograms of all cells of the given image
• this gives the image-level LBP feature descriptor

TODO insert example

• LBP can be multiresolution and rotation-invariant

  • in the case of multiresolution, you vary the distance between the centre pixel and neighbouring pixels and vary the number of neighbouring pixels

  • for rotation-invariance: vary the way of constructing the 8-digit binary number by performing bitwise shift to derive the smallest number

    • note: not all patterns have 8-shifted variants (i.e. 11001100 has only 4)
    • reduces LPB feature dimension from 256 to 36

• describes texture in a localised region around a keypoint
• invariant to scaling, rotation, shift.
• robust to affine distortion and illumination changes

• net area; principal axes; convex area
• convexity, concavity; convex hull ⊕ ; convex deficiency (set difference between the convex hull and the object)

• compactness; circularity

  • ^inversely related
  • compactness: ratio of the area of a circle with the same perimeter as the object to the area of the object
  • circularity: ratio of $4\pi$ times the area of an object to the second power of its perimeter ($4\pi A/p^=1$ for a circle)

• elongation; eccentricity

  • elongation: ratio between the length and width of the object's bounding box
  • eccentricity: ratio of the length of the minor axis to the length of the major axis

• chain code descriptor
• local curvature descriptor

• global curvature descriptors:

  • total bending energy $B=\oint_C K^2\; \mathrm{d}s$
  • total absolute curvature $K=\oint_C |K(s)|\;\mathrm{d}s$
• radial distance descriptor

• is a point-wise local feature descriptor

  • pick $n$ points $p_i$ on the contour of a shape
  • for each point, create a radial coordinate system centred at this point and compute a histogram $h_i$ based on the relative coordinates of the other $n-1$ points
  • this is the shape context of $p_i$
• e.g. shape matching ALGORITHM TODO; TODO graphic

• describes the distributions of gradient orientations in localised areas
• does not require initial segmentation

• algorithm:

  1. calculate the gradient vector at each pixel

     • gradient magnitude
     • gradient orientation

  2. construct the gradient histogram of all pixels in a cell

     • divide orientations into $N$ bins (typically $N=9$ bins evenly splitting 180 degrees)
     • assign the gradient magnitude of each pixel to the bin corresponding to its orientation

  3. generate detection-window level HOG descriptor

     • concatenate cell histograms
     • block-normalise cell histograms

sliding window ? TODO

• use-case: detecting humans in images.

• works fine if regions have sufficiently different intensity distributions
• problematic if regions have overlapping intensity distributions

• may work if the number of clusters is known a priori
• problematic if not

• extract a patch around each pixel and compute its features
• classify each pixel based on its features using a trained classifier

• recursively split the whole image into pieces based on local statistics
• recursively merge pieces together (in a hierarchical fashion)
• combine splitting and merging sequentially

• based on the analogy of immersion of a topographic surface

• meyer's flooding algorithm:

  1. choose a set of markers to start the flooding

     • i.e. local minima. give each a different label

  2. put neighbouring pixels of each marker into a priority queue

     • a pixel with more similar gray value has higher priority
  3. pop the pixel with the highest priority level from the queue. if the neighbours of the popped pixel that have already been labelled all have the same label, then give the pixel that same label. put all non-labelled neighbours that have never been in the queue into the queue
  4. repeat step 3 until the queue is empty

• preprocessing:

  • invert the image or compute edges if needed to get local minima markers
• images often have many local minima, leading to heavy oversegmentation
• preprocessing (image smoothing) may be needed to reduce false minima
• postprocessing (basin merging) may be needed to reduce fragmentation
• many different implementations and pre/postprocessing criteria exist
• it is possible to start from user-defined markers instead of local minima

• try multiple thresholds and analyse the shape of the connected components
• select regions with virtually constant shape over many thresholds

• seeks stationary points (peaks / modes) in a density function
• attempts to find all possible cluster centers in feature space
• does not require knowing the number of clusters a priori
• is a variant of iterative steepest-ascent method

• algorithm:

  1. initialise a random seed point $x$ and window $N$
  2. calculate the mean (centre of gravity) $m(x)$ within $N$ \[m(x)=\frac{\sum_{x_i\in N(x)} K(x_i-x)x_i}{\sum_{x_i\in N(x)} K(x_i-x)}\qquad K(x) = \exp(-|x|^2)\] \[\text{Mean (centre of gravity)}\qqquad\text{Kernel (weight function)}\]
  3. shift the search window to the mean
  4. repeat step 2 until convergence

• advantages:

  • model-free (does not assume any prior shape on data clusters)
  • has just a single parameter (window size)
  • finds variable number of modes (clusters)
  • robust to outliers

• limitations:

  • computationally expensive (need to shift many windows)
  • output depends on window size parameter value
  • window size (bandwidth) selection is not trivial
  • does not scale well with dimensionality of feature space

• improves efficiency:

  • group similar pixels into a superpixel
  • superpixels together are an oversegmentation of the image
  • ultimate segmentation (classification, mergingg) performed on superpixels

• simple linear iterative clustering (SLIC)

  • popular superpixel generation algorithm
  • preserves object boundaries, is fast and memory efficient

  • algorithm:

    1. initialise cluster centres $C_j$ on pixel grid with step size $S$
    2. move $C_j$ to position in $3\times 3$ window with smallest gradient
    3. compute distance $D_{ij}$ for each pixel $i$ in $2S\times 2S$ window around $C_j$
    4. assign each pixel $i$ to the cluster $C_j$ with smallest distance $D_{ij}$
    5. recompute cluster centres as mean colour and position of pixels in $C_j$
    6. iterate (go to step 3) until the residual error is small \[\begin{align} D &= \sqrt{\frac{d_{\text{lab}^2}}{m^2} + \frac{d_{xy}^2}{S^2}}\quad\text{(weight $m$ controls influence of colour over spatial distance)}\\ d_\text{lab} &= \sqrt{(l_j-l_i)^2 + (a_j-a_i)^2 + (b_j-b_i)^2}\quad\text{(distance in CIELAB space)}\\ d_{xy}=\sqrt{(x_j-x_i)^2+(y_j-y_i)^2}\quad\text{(distance in pixel space)} \]

• superpixels provide a basis for further segmentation

  • determine spatial relationship between the superpixels
  • compute similarities between superpixels
  • group superpixels to form larger segments

• conditional random field (CRF) approach

  • a probabilistic graphical model that encodes the relationships between observations (i.e. superpixels) and constructs a consistent interpretation (i.e. a segmentation) for a set of data (i.e. an image)
• nodes: superpixels (value based on features of superpixels)
• edges: adjacency (value based on similarity between superpixels)

• formulated as an energy minimisaion problem: \(E(s,c) = \sum_i \psi (s_i,c_i) \sum_{ij}\Psi (s_i, s_j)\)

  • unary potentials $\psi$:

    • data term based on graph node values
    • computes the cost of superpixel $s_i$ belonging to class $c_i$
    • a lower cost means a higher likelihood of $s_i$ belonging to $c_i$
    • can be obtained via superpixel classification

  • pairwise potentials $\Psi$:

    • smoothness term based on graph edge values
    • computes a cost of neighbourhood consistency
    • a cost is assigned if adjacent superpixels are assigned to different classes
    • higher similarity results in a lower cost (0 if assigned to the same class)
• graph cutting by min-cut / max-flow algorithm

• a contour-based approach to object segmentation
• aims to locate object boundaries in images by curve fitting
• represents the curve by set of control points and interpolation
• iteratively moves the control points to fit the curve to the object
• uses image, smoothness and user-guidance forces along curve

• a.k.a snakes:

  • smoothly follows high intensity gradients at the object boundary
  • bridges areas of noise or missing gradients using smooth interpolation
• missing gradient problem?

• active contours / snakes are parametric models

  • explicit representations of the object boundaries
  • typically requires manual interaction to initialise the curve
  • it is challenging to change the topology of the curve as it evolves
  • curve reparametrisation may be required for big shape changes

• level-set methods have become more popular alternatives

  • implicit representations of the object boundaries
  • boundaries defined by the zero-set of a higher dimensional function
  • level-set function evolves to make the zero-set fit and track objects
  • easily accommodates topological changes in object shape
  • computationally more demanding than active contours

• representation:

  • define an initial 3D level-set function
  • zero-level plane represents the 2D shape
  • iteratively deform the function to fit the shape

• segmented object pixels: $S$
• true object pixels: $T$

• true positives: $TP = S \cup T$

  • pixels correctly segmented as object

• true negatives: $TN = S^c\cup T^c$

  • pixels correctl segmented as background

• false positives: $FP=S\cap T^c$

  • pixels incorrectly segmented as object

• false negatives: $FN=S^c \cap T$

  • pixels incorrectly segmented as background

• sensitivity (= true-positive rate)

  • fraction of the true object that is correctly segmented \[\text{TPR} = \frac{\text{TP}}{\text{TP}+\text{FN}}\]

• specificity (= true-negative rate)

  • fraction of the true background that is correctly segmented \[\text{TNR} = \frac{\text{TN}}{\text{TN}+\text{FP}}\]

• precision (= positive predictive value)

  • fraction of the segmented object that is correctly segmented \[\text{P} = \frac{\text{TP}}{\text{TP}+\text{FP}}\]
• F-measure (= harmonic mean of precision and recall) \[\text{F1} = \frac{2\text{RP}}{\text{R}+\text{P}}\]

• recall (= sensitivity)

  • fraction of the true object that is correctly segmented \[\text{R} = \frac{\text{TP}}{\text{TP}+\text{FN}}\]

• Jaccard similarity coefficient (JSC)

  • intersection over union (IoU) = correctly segmented fraction of the union of the segmented object and the true object \[\text{JSC} = \frac{S\cap T}{S\cup T} = \frac{\text{TP}}{\text{FP}+\text{TP}+\text{FN}}\]

• Dice similarity coefficient (DSC)

  • correctly segmented fraction of the segmented object set joined with the true object set \[\text{DSC} = \frac{2|S\cap T|}{|S|\cup |T|} = \frac{2\text{TP}}{\text{FP}+2\text{TP}+\text{FN}}\]

• plots the true-positive rate (sensitivity) versus the false positive rate (one minus the specificity) of a method as a function of its free parameters

• auc

  • higher is better.
  • ranges from 0.0 to 1.0. can technically go negative, but maybe just invert your work at that point.

• dilation \(I \oplus S = \{\,x \mid (S^{r})_x \cap I \neq \varnothing\,\}\)
• erosion \(I \ominus S = \{\,x \mid S_x \subseteq I\,\}\)
• default struct elem: symmetric \(3 \times 3\); use decomposition / iteration for bigger ones

• opening \(I \circ S = (I \ominus S)\, \oplus S\) -> drops tiny foreground blobs
• closing \(I \bullet S = (I \oplus S)\, \ominus S\) -> fills tiny background gaps

• morph gradient \((I \oplus S) - (I \ominus S)\) -> outer + inner edge
• 1‑px outline \((I \oplus S) - I\)

• keep chosen objs: repeatedly dilate marker inside mask until no change
• kill boundary objs: marker = border; reconstruct; subtract result
• fill holes: work on complement, reconstruct from border, then take complement back

• distance transform: count erosion steps per pixel
• ultimate erosion: local maxima of dist map -> object centres
• ultimate dilation (no‑merge) -> voronoi tessellation
• skeleton: iterative thinning that keeps connectivity

• swap \(3 \times 3\) for \(3 \times 3 \times 3\) voxels, etc.; everything generalises

• treat an \(n\)-d image as an \((n+1)\)-d binary volume under its surface

• dilation \(I \oplus S = \max_{p \in S}\, I(x - p)\)
• erosion \(I \ominus S = \min_{p \in S}\, I(x + p)\)

• opening / closing: size‑selective smoothing (remove bright / dark specks)
• morph gradient \(D - E\); outer / inner variants give one‑sided edges
• laplacian \(D + E - 2I\)
• white top‑hat \(I - (I \circ S)\) (bright peaks)
• black top‑hat \((I \bullet S) - I\) (dark wells)

• 2 conv + subsample then 3 fully connected

• 5 conv + 3 fc, relu, lrn, dropout, heavy data aug

• stacks of 3x3 conv, about 144m params

• parallel 1x1, 3x3, 5x5, pool paths then concat

• residual block \(y = F(x) + x\), allows 50+ layers

• squeeze‑excitation channel reweighting

• dense block concatenates all previous features

• compound scaling of depth, width, resolution

• image patches to tokens, pure self‑attention

• convnet with transformer design cues (patchify stem, layer norm)