## Image Retrieval ### Basics - Image representation: Matrix with color values - Low-level features: - Idea: How are images described with natural language? - Color (foreground, background) - Shapes - Texture (contrast, repetition) - Problem: - Loss of information/semantics - Low-level feature combination works better - Use LLF to exclude images - High-level features: - Wavelets - Fourier transformation - Input: Image (as signal) - Position space to frequency domain - Similarity search / matching - Exact matching is easy - Similarity not --- ### Color-based Retrieval #### Basics - Assumption: If two images share the same color, their content is similar - Problem: Loss of information (e.g., sunset vs sunrise) - *Color*: - Event with three participants - Light (property) - Object (property) - Observer - Important for human perception #### Color Spaces - Motivation: - Required to work with colors (e.g., add lightning) - Describe and compare colors mathematically - Definition: Multi-dimensional space to describe color components - *Requirement for MMDBs*: Distance in a color space should correlate to distance in perception - Perception: Three receptors for wavelengths - Blue (435 nm) - Green (546 nm) - Red (700 nm) ##### RGB - Euclidean vector space - Additive color mixing - Red, Green, Blue (`$ 0-255 $`) - Advantage - Good representation of visible light - Disadvantage - Poor for similarity search (equal distance is no equal similarity change, magenta vs. blue/red) ![](images/color-rgb.png) ##### CMYK - Cyan, Magenta, Yellow, Black/key - Subtractive color model - Represent painting ink ##### Munsell Color System - Munsell, 1905 - Idea: - Create color space respecting human perception (transform RGB) - Distance in color space is distance in perception - Problem: No known color space with uniform perception - Creation: Humans sort colors - Dimensions: - Chroma (i.e., saturation) - Hue - Value (black to white) - Use cases - Hair color / skin color - Color of liquids - Disadvantages - Distances between non-adjacent colors don't respect perception - No simple transformation to RGB ![](images/color-munsell.png) ##### CIE Color space - Commission Internationale de l'eclairage (*Standardization Commission on Illumination*) - Idea: - Propose perceptional space - Based on opponency + thrichromacy - CIE 1976 (L*, a*, b*) - L: Lightness (0-100) - a*: green (negative value) to magenta (positive value) - b* blue (negative value) to yellow (positive value) - Successful color model (implemented in Photoshop) - Non-linear transformation from RGB ![](images/color-cie.svg) ##### HSV Color space - Simpler than CIE - Hue, saturation, value - Non-linear transformation from RGB (but easy to compute) - Advantage - Intuitive/easy - *Nearly* perceptional - Good for similarity search - Used in MPEG-7 (color space for image descriptors) ![](images/color-hsv.png) #### Color Features - Problem: - Image has many pixels - Pixel-by-pixel-comparison is too expensive - Solution: Aggregate color 1. Color channel metric (e.g., average) 2. Color histogram 3. Color layout/regions - Important trade-off: - Complexity of calculation (e.g., average color, quadratic distance) - Accuracy of description (e.g., cross-talk matrix has more semantics) ##### Color Channel Metrics - Idea: Represent image by vector of three components - Moments: 1. Mean-color-distance (average color) 2. Variance-color-distance: `$ \sigma_R^2, \sigma_G^2, \sigma_B^2 $` 3. Skewness-color-distance - Comparison: Euclidean distance - Experiment Castelli/Bergmann: - Color channel metrics have bad retrieval accuracy - Minkowski/Quadratic distance are similar ###### Average Color - Compute average color of all pixels - `$ C_{avg} = (R_{avg}, G_{avg}, B_{avg}) $` - Advantage: Simple - Disadvantage: Very bad measure (perceptionally insufficient) - Use case: - Exclude/prune images using average color (dominant color influences average color) ##### Color Histogram - Use histogram of colors - Represents number of pixels with certain color - Represents a *global description* of the image - Normalization - Used for comparison - Normalize by number of pixels - Sum of columns equals one - RGB: - 16 million colors too much - Reduce number of columns, i.e., *color quantization* - Problem: Transform vector to column - Solution: Color quantization - Comparison using metrics (distance functions): - Minkowski distance - Quadratic distance - Mahalanobis distance ###### Color Quantization - Purpose: - Reduce number of columns in histogram - Merge similar colors (e.g., quantize vector space) - Mapping from k-dim. space to color partition - Formal - Code words/Codebook (columns) `$ C=\{y_0,...,y_{m-1}\} $` - Encoding/Code `$ Q_C $` - `$ Q_C^m: \mathbb{R}^k \rightarrow C $` - Requirements - Group *perceptionally similar* colors together - Codeword should be best representation of color - Minimize number of partitions (increase search efficiency) - **Quantization HSV** - `$ Q_C^{166} $` (Smith, 1997) - Hue: 18 segments (each 20°) - Saturation: 3 segments - Value: 3 segments - Gray: 4 segments - Saturation is zero - Hue can be any value for gray - Group *perceptionally similar* - `$ 0\leq 25 \leq 50 \leq 75 \leq 100 $` - **Quantization RGB** (idea) - Use k-means centroids as code words - Enumerate clusters - Use k-NN on other images to sort into code words ###### Minkowski distance - Histogram `$ h_1, h_2 $` - Histogram as vector - Usually, `$ r\in\{1,2\} $` - *Personal Idea: Consider weighted Minkowski distance* - Weight different colors - e.g., collection of leafs (focus on greenish colors, ignore red/yellow/blue noise) - Counterargument: red/yellow/blue may be important for discrimination/differentiation - Disadvantage: - Does not respect color similarity (e.g., distance between red and bright red is equal to red and blue) - Works poorly for color shifts (i.e., higher/lower saturation) - Advantage - Sufficient for MMDBMS ###### Quadratic measure - Idea: Use similarity of different colors - Use cross-talk matrix `$ A $` - Pairwise similarity `$ a_{i,j} $` between colors `$ y_i $` and `$ y_j $` - `$ a_{i,i}=1 $` - `$ a_{i,j}=a_{j,i} $` - Formula - `$ d_A(h_1, h_2) = (h_1-h_2)^T \cdot A \cdot (h_1-h_2) $` ###### Mahalanobis distance - Observation: Color combinations with high covariance don't contribute to discrimination - Idea: - Co-occurring colors should receive low weight - Use covariance matrix `$ \Sigma^{-1} $` as cross-talk matrix - Generate covariance matrix using a representative set of images (histograms) from the collection - Formula - `$ d_M(h_1, h_2) = (h_1-h_2)^T \cdot \Sigma^{-1} \cdot (h_1-h_2) $` - Covariance matrix: - All colors un-correlated: - Diagonal matrix - Norm is quadratic weighted Euclidean distance (weighted by standard deviation of the respective color) - Some colors correlated: - Transform coordinate system - Reduce correlating colors to one dimension (e.g., PCA / SVD) - Result: New basis vectors are uncorrelated - In reduced space, the distance is weighted by the eigenvectors `$ \lambda $` - Weighted Euclidean distance in reduced space is Mahalanobis distance in original space ##### Color regions - Idea: - Divide image into regions (individual description) - Object of interest is in focus/the middle of the image - *Take semantics of an image into account* - Calculation: Use weighted sum of similarity of regions - Different regions can be weighted - e.g., foreground is more important - Approaches - Grid distribution (Hsu et al., 1995) - Divide image into grid - Weight regions differently - Common compositions (Stricker/Dimai, 1996) - e.g., foreground motif - Fuzzy regions (image) - Weighted regions --- ### Texture-based Retrieval #### Texture - Definition - **Recurrent**, typical, obvious (clearly visible) pattern in picture - Often used to describe images - Research - Texture segmentation - Find areas with homogeneous textures - Decomposition of image - Color and texture are related (can be combined for features) - Texture classification - Denote homogeneous textures with text or - Describe homogeneous textures with features - e.g., Ice, water, tomography - Semantic classification - Represent objects from the real world (e.g., corn, water) - Application-dependent - Descriptive classification - No direct meaning (e.g., parallel) - Can be used for query-by-example - Ensure comparability between image collections - Texture synthesis (create textures) - Criteria for a texture (Rao/Lohse, 1993) - Repetition - Orientation (e.g., vertical) - Complexity (e.g., how regular?) - Features - Low-level - Julesz' Texton - Tamura-measure - Random field model - High-level - Gabor-filter - Fourier transform - Wavelet transform #### Low-level features ##### Julesz' Texton - Also called *grey-level analysis* - *Grey-level*: Intensity of pixel - Idea: - Create grey-level histogram (distribution) - Use moments of distribution for description - **Histogram of grey values** - Claim: Similar pattern produce similar distribution of grey values - Problem: Distribution ignores position - Problem: Repetition can't be seen - **Grey-level co-occurrence matrix** `$ C_d $` - Matrix for a specific distance `$ d $` - Cell `$ a_{ij} $` indicating how often grey-level `$ i $` co-occurs with grey-level `$ j $` for points with Euclidean distance `$ d $` - Consider all pairs of points with Euclidean distance `$ d $` - Julesz, 1961: - Empirical probability distribution of intensity *change* to the right - Use position - `$ P(I(s) = i \land I(s+d)=j) $` - Julesz, 1975: - Generalization to any directions - Julesz, 1973 - Thesis: Texture with identical grey-level co-occurrence matrices => People can't distinguish - Thesis is *wrong* (Julesz, 1981) - Can be used as *rule of thumb* - Problem: Texture is more complex than just the intensity distribution ![](images/03-histogram.png) ##### Tamura Measure - Tamura et al., 1978 - Describe texture with dimensions: - Granularity (e.g., gravel vs. sand) - Contrast (sharpness) - Directionality - Line-Likeness (ignore) - Regularity (ignore) - Roughness (ignore) - Matching - Granularity, Contrast and directionality are un-correlated - Image - `$ d_\text{texture}^2(x,y) = \frac{(G_x-G_y)^2}{\sigma_G^2}+\frac{(C_x-C_y)^2}{\sigma_C^2}+\frac{(D_x-D_y)^2}{\sigma_D^2} $` - Divide by standard deviation to normalize the components, e.g., granularity is a window size and directionality is a ratio between zero and one ###### Granularity - Example: Areal photo from different heights - *Granularity*: - Also called *coarseness* - Size of the *objects* in the texture - Idea: - Neighborhood influences the granularity - Observe neighborhood for brightness changes - Try to find the size of the *objects* in the texture (e.g., checkerboard: size of one square) - Calculation - *Idea: Look at the brightness of left/right pixel, to see if they change, if there are different objects* - Use windows of sizes `$ 2^i \times 2^i $` - For each pixel and every window size `$ 0\leq i\leq 5 $`, compute the average gray value - For each pixel, compute difference of grey-level means of all adjacent windows - Vertical: `$ y+2^{i-1}, y-2^{i-1} $` - Horizontal: `$ x+2^{i-1}, x-2^{i-1} $` - `$ \delta_i^h, \delta_i^v $` - Compute the window size maximizing the difference of means in either direction - `$ S_{best} = 2^i $` with `$ i=\arg_i\max \{\delta_i^h,\delta_i^v\} $` - Granularity of entire image: - Mean of maximum window sizes of al pixels - Histogram of pixels and their maximum window size - Each pixel is assigned exactly one maximum window size - Finer-grained comparison - Meaning of the window size: - Size of the objects in the texture (e.g., circles, squares, etc.) - Window size larger than the granularity: Similar distribution of grey levels - Window size smaller than granularity: No difference or very high difference - Problem: Small images lead to small granularity - Reason: The window size can't be large - Equitz/Niblack, 1994 - Estimation of `$ \delta_i $` for smaller images ###### Contrast - Visual: - Clarity of image - Sharpness of color transitions - Exposure - Shadows - Grey-level distribution: - Low contrast: Flat peaks - High contrast: Sharp peaks - Use higher-order moments of grey-level distribution - Contrast: `$ K=\frac{\sigma}{\sqrt[4]{\alpha_4}} $` - `$ \sigma $`: Standard deviation on collection - `$ \alpha_4 = \frac{\mu_4}{\sigma^4} $`: Kurtosis - `$ \mu_4 $`: Fourth central moment - Can differentiate Uni- and Bi-modal distributions ![](images/03-contrast.png) ###### Directionality - Find predominant direction of elements - Example: - Trunks: Highly directional - Stones: Weak directional - Description for the gradient of each pixel - Angle (direction) - Magnitude (strength) - Computation - Idea: *How many pixels can I go in a certain direction without exceeding a certain gradient?* - Compute gradient of color for a set of angles - Histogram with number of pixels exceeding a threshold per angle (*Morris: number of pixels below a certain threshold*) - *Dominant direction*: Peak in histogram - Problem: *Rotated images* - Rotated image has different dominant direction - Results in bad retrieval results - Use number of peaks and peak amplitude (bar height) for images ![](images/03-directionality.png) ##### Random-Field model - Stochastic/probabilistic model - Use repeating/recurrent nature of texture - Idea: - Use generative model for texture synthesis - Assume, a model generated textures in collection - Use model parameters for description/matching - Comparable to IR language models - Generative model - *Good model*: Create different but similar textures - Predict pixel color/intensity by neighborhood - *Random field* - `$ F $` is matrix with pixel intensities from image - `$ F $` is random variable - Called *random field* - Known distribution - Unknown parameters - Maximum likelihood estimation: - Given an image - Find the parameters for `$ F $` that generated the image best - *Markov property* - Event does not depend on complete history of events - Only depends on the last k events - e.g., *sufficiently regular textures* require only the neighborhood/locality pixels - Neighborhood shifts `$ N\subset \mathbb{Z} \times \mathbb{Z} $` - Neighborhood `$ N_s = \{s+t\mid t\in N\} $` - Assumptions: - Markov condition is valid - Size of neighborhood is well chosen - Models: - Simultaneous AutoRegressive model (SAR) ###### Simultaneous AutoRegressive Model (SAR) - Popular class of models for texture description - *auto-regression*: self-similar - Idea: - Function depends on its own - Formal - `$ F(s) $`: Value of pixel `$ s $` - `$ W(s) $`: Random variable for noise (mean 0, variance 1) - `$ \theta(t), \beta $`: Parameters - `$ F(s) = \sum_{t\in N} \theta(t) \cdot F(s+t)+\sqrt{\beta}\cdot W(s) $` - Computation: - Minimization problem - *Idea: Compute using the least squares method* - Problem: Neighborhood size different to estimate - Neighborhood size must reflect texture size - Small texture vs. large texture - Solution: Mao/Jain, 1992 (Multi-resolution simultaneous autoregressive model) - Advantage: - Good low-level description of textures #### High-level features ##### Basics - Goal: Describe complete picture without information loss - Image as input signal - `$ f:\mathbb{N}\times \mathbb{N} \rightarrow [0,1] $` - Image row is sequence of real numbers (intensity) - Image is *discrete function* - Color space: One function per component - Polynomial interpolation - Transform sequence of numbers into polynomial - Problem: Polynomial not suitable for shape representation - Textures are recurrent/periodic - Polynomials are not periodic - Other transformations - Discrete Fourier Transform - Discrete Cosine Transform - Wavelet Transform ##### Discrete Fourier Transform - Fourier transform can be generalized to two-dimensional data - Each pixel has direction and wavelength of oscillation - Results in `$ A(i,j), B(i,j) $` indicating amplitude of sine/cosine wave - Compare using an image - Instead of matrices `$ A $` and `$ B $` - Pixel value `$ (i,j) $` is length of vector `$ (A(i,j), B(i,j)) $` - Properties of frequency space: - Centered on fundamental frequency - Symmetrically towards origin - Harmonics - Main oscillation - Amplitude (strength) - Size of period - Computation - Fast Fourier Transform (FFT) - Complexity `$ O(n^2) $` - Implementations: - Cooley-Tukey (Divide-and-conquer, `$ O(n \log n) $`) - Prime Factor FFT - Bruun's FFT - Problem for textures: - Use frequencies only (ignore location/time) - Result: Single change in position space leads to complete change in frequency domain - Problem: - Textures can be local in images (could be good feature) - Can't be extracted using the Fourier transform - Problem: - Noise occurs in certain interval in signal - Reduction in frequency domain (remove noise-frequencies) - Reduction impacts *complete* position space ##### Discrete Cosine Transform - Similar to DFT - Does not use sine-parts (only cosine) - Application: JPEG encoding - Use Power spectrum (also in DFT) for comparison ##### Wavelet transform - Motivation: - Add location information to transformation (missing in Fourier transform) - Approximation using different class of functions - *Wavelet*: - Meaning "Part of a wave" - Wavelet is a function which only exists in a certain interval (vanishes outside) - Most simple wavelet: Haar wavelet (Step function) - Idea: - Use local base function (mother wavelet) - Scale and shift the mother wavelet (baby wavelets) - Represent a function (signal) with the sum of these baby wavelets - Types: - Continuous Wavelet Transform - Discrete Wavelet Transform - Fast Wavelet Transform (special type of DWT) - Further Reading: - [Wolfram "Haar Function"](https://mathworld.wolfram.com/HaarFunction.html) - [Wikipedia "Haar Wavelet"](https://en.wikipedia.org/wiki/Haar_wavelet) ###### Mathematics - Scaling function (sometimes called *father wavelet*) `$ \phi(x) $` - Mother wavelet `$ \Psi(x) $` - Haar wavelet: Step function on interval `$ [0,1) $` (very easy) - Daubechies wavelet (more sophisticated) - Baby wavelet: - Baby wavelet is a scaled and/or shifted version of the Mother wavelet - *Haar* wavelet: `$ \Psi_{a,b}(x)=2^\frac{a}{2}\Psi(2^a x - b) $` - Base `$ B=\{\Psi_{a,b}\mid (a,b)\in \mathbb{R}_+ \times \mathbb{R}\} $` - Base `$ B $` must be an **orthonormal basis** - Each point can be represented by a sum of the basis functions - Functions must be pairwise orthogonal: `$ \langle w_1,w_2\rangle = 0 $` - `$ \langle w,w\rangle = 1 $` - Dot product of functions: `$ \langle w,w\rangle = \int |w(x)|^2dx $` ###### Transforms - Continuous Wavelet Transform (CWT): - For each pair `$ (a,b)\in\mathbb{R}^2 $`, compute the wavelet coefficient - Mother wavelet `$ \Psi $` - Target function `$ f $` - `$ CWT_{a,b}(f,w)=\langle f, w_{a,b}\rangle $` - Reconstruct original function using wavelet coefficients - Discrete Wavelet Transform (DWT): - Goal: Represent vector `$ v\in\mathbb{N}^{2^n} $` of integers of length `$ 2^n $` - Represent vector as continuous function over the interval `$ [0,1) $`: - `$ f(x)=\sum_{k=0}^{2^n-1} v_k \cdot 1_{[k2^{-n},(k+1)2^{-n})}(x) $` - Scaling and shifting of Haar Wavelet to the power of 2 - Representation of `$ f(x) $`: - `$ f(x)=c_{0,0}\phi(x) + \sum_{a=0}^{2^n-1}\sum_{b=0}^{2^a-1} d_{a,b}\Psi_{a,b}(x) $` - `$ c_{0,0} $`: Wavelet coefficient of the scaling function `$ \phi(x) $` (father wavelet; later, this is the averages part) - `$ d_{a,b} $`: Wavelet coefficent of the baby wavelet `$ \Psi_{a,b} $` (later, this is the detail part) - Fast Wavelet Transform (FWT): - Compute a sufficient set of wavelet coefficients - Haar transform matrix `$ H_n $` - Discrete input vector `$ v\in\mathbb{N}^{2^n} $` - Wavelet coefficients `$ b\in\mathbb{R}^{2^n} $` - `$ v = H_n \cdot b\equiv b=H_n^T\cdot v $` (`$ H_n^T=H_n^{-1} $`) ![](images/03-fwt.png) ###### Matching - Representation of Image is unique and contains location and intensity (due to orthonormal basis functions) - Use first `$ k $` wavelet coefficients that represent the image well enough - Only represent broad structure of images - Use Euclidean distance for matching #### Multi-Resolution Analysis - High resolution images: - Have many pixels - Wavelet transformation lead to high-dimensional equation systems - Problem: Expensive - *Tilo: Not interested in details -> broad structure* - Solution: *Fast wavelet transform* - Time complexity `$ O(n) $` - Algorithm works repeating the steps: 1. Reduce resolution (leads to smaller equation systems) 2. Store lost information to reconstruct images (provides the wavelet coefficients) - Underlying technology: *Multi-resolution Analysis* - Idea of MRA: - Image in different resolutions without information loss - *Keep detail information but store it somewhere else* - Image signal consists of two parts: raster + detail - *Averaging and downsampling* - Summarize blocks of pixels (average color, remove noise) - Average is the *new* pixel - Works best for quadratic images (otherwise a single row or column must be stripped off, which is OK for MMDB purposes) ##### Formal - `$ V_k $`: Original image - Resolution stage `$ k $` - Works best for quadratic images `$ 2^k $` - `$ V_{k-1} $`: Raster of lower resolution (less pixels than `$ V_k $`) - `$ V_0 $`: Single pixel (average color, not that helpful) - Getting `$ V_{i-1} $` from `$ V_i $` - Halve width/height iteratively by taking the average of two adjacent pixels (alternating width and height) - *Mean* of pixels corresponding to `$ V_i $` - Store difference information - *Averaging and differencing* - Resolution state `$ 0\leq i\leq k $` - `$ f_i(x,y) = f_{i-1}(x,y) + d_{i-1}(x,y) $` - `$ f_i $`: Intensity of pixel `$ p_i(x,y) $` in `$ V_i $` - `$ d_i $`: Detail (difference) information to reconstruct the pixel - Reconstruct original image recursively: - `$ f_k(x,y) $` - `$ =f_{k-1}(x,y)+d_{k-1}(x,y) $` - `$ =f_{k-2}(x,y)+d_{k-2}(x,y)+d_{k-1}(x,y) $` - `$ =f_0(x,y)+\sum_{j=0}^{k-1}d_j(x,y) $` - Additionally store matrix with difference between one of the pixels to the lower resolution image - Advantage: - No information loss - Small differences ##### Filtering (Signal Processing) - *Averaging and differencing* corresponds to filtering - High-pass filter - Extracts detail information - Baby-wavelets of higher order - *Shows changes* - Low-pass filter - Extracts averages - Baby-wavelets of lower-order - *Shows energy* - Application of filters: `LL, LH, HL, HH` - H: High-pass (corresponds to *differences*) - L: Low-pass (corresponds to *average* - `HL`: High-pass in X direction, Low-pass in Y direction, i.e., averages of the differences of X - Feature array - Save expected value + standard deviation of Wavelet coefficients ![](images/04-mra.png) --- ### Shape-based Retrieval #### Basics - Shape - Definition: *‌A shape is the form of an object or its external boundary, outline, or external surface.* ([Wikipedia](https://en.wikipedia.org/wiki/Shape)) - Contribute significantly to similarity of images - Often carry semantic information - Often independent of color (e.g., banana shape may be red) - Idea - Simple shape-features: Round, elliptical, triangular, square, star, ... - Combine simple shape-features with other features (color, texture) to improve retrieval quality - Fundamental problems - Shape recognition/segmentation (which shapes are in an image) - Semantic mapping (is it always possible?) - Feature mapping/representation - Similarity/comparison of shapes #### Segmentation - Task: Find relevant, displayed shapes in an image - Problems: - Relevance: Is water in background a relevant shape? - What if the shape is not completely visible?, e.g., sunset - What represents a shape? - Is a shape homogeneous in color or texture? (e.g., Zebra, [The Wave](https://de.wikipedia.org/wiki/Vermilion_Cliffs_National_Monument)) - Automated segmentation - Hard problem - Often *specialized solutions* for automated segmentation exist - Shape-features removed from commercial systems (problems with segmentation) - Segmentation in QBIC - *Seeded Region Growing* - Select seed points, add pixels to region if a certain criterion matches (e.g., gradient of greyscale) - Problem: In QBIC this works only for monochrome surfaces - What is a *Shape*?: - Outline (outer perimeter) or the - Area enclosed by the outline - Approaches - Area Detection: Areas with same brightness/color/texture - Edge detection: Differences in brightness, gradient, watersheds - Morphological operators: Filling (dilation/erosion) - Active Contour: Segment the outline as closed curve - *Observation (personal)*: *Most of the approaches should be combined to obtain a good segmentation. Remove noise with a Gaussian filter, then apply the edge-detection or threshold algorithm and improve the image with morphological operators.* ##### Area Detection (Thresholding) - Approach: *Thresholding* - Used for grey value images - Find *area* of shapes - Idea - Differentiate areas from background using brightness - Assume that background is significantly darker/lighter than the foreground - Can be combined with area-based approaches - Split image in areas and detect objects in areas - Use for colored images - Assumption (deprecated) - Thematically related areas have similar gray values - Separate shape from background - Approaches - Fixed (static) threshold - Fixed threshold for each image - Good for similar lightning in all images - Flexible (dynamic) threshold - Depend on grey-value histogram - Optional: Smooth histogram - Algorithms - ISODATA - Ridler/Calvard, 1978 - Split histogram into two parts (*divide mass of background and mass of object*) - Calculate two expected values - Threshold is average of expected values - Recursively compute expected values until no significant change - Triangle algorithm - Zack et al., 1977 - Connect highest peak with highest brightness value with a line - Find maximal distance orthogonal to line - Add certain constant --> This point is the threshold - ==Why does this work? Why is this the threshold?== - Applications: Medical detection - Advantage - Simple - Disadvantage - Determination of right thresholds - Assumption doubtful - Strong color change of back- and foreground - Does not work if object is enlightened (high and low brightness values) - Decomposition of complex objects into simple shapes does not work ##### Edge detection - Idea - Find borders of objects - Goal: Closed curves around object - Maximum change in brightness function represents edge - Brightness function - `$ I:\mathbb{N}\times\mathbb{N}\rightarrow [0,1] $` - Idea: High change in brightness function (inflection point) represents edge - Mathematical: - Maximum/minimum in first derivative - Zero/root in second derivative (real zero-crossing) - Problem: - Derivates require differentiable functions - Image is discrete function - Gradient calculation - Estimate continuous function from complete image (e.g., Fourier transform) - Estimate gradient of function from neighborhood (faster, e.g., Sobel filter) - Approaches: - Gradient-based method - Laplacian Zero-Crossing - Comparison - Gradient: Shape is better (stronger) detected - Zero-crossing: Noise is removed - Both approaches may require the use of morphological operators ###### Gradient-based method - Calculate magnitude of the gradient at each point - e.g., using the Sobel filter - If the gradient is *high enough*, the corresponding pixel belongs to an edge - This approach is stricter than the *Laplacian Zero-Crossing* - Then, use threshold algorithm for detection - Avantage - Simple filter - Disadvantage - Susceptible to noise (can be prevented by noise reduction pre-processing) - Can not detect blurred/merging contours ![](images/04-gradient.png) ###### Laplacian Zero-Crossing - Address problem of blurred edges and noisy images - *Zero-crossing of second derivative* - Idea: - Zero passage of second derivate shows maximum gradient - *The ideal edge*: Edges are only on *real* zero-crossings (not zero points) - Creation of the new image: - Pixels with real zero-crossings are marked (maybe multiplied by the magnitude of the gradient) - Then, use thresholding to detect shapes - Problem: Noise (apply Gaussian filter before) ![](images/04-zero.png) ##### Watersheds transformation - What is a *Watershed*? - A *Watershed* (dt. Wasserscheide) is a border between two adjacent rivers/seas. - Assumption: - Surfaces are defined by minimal grey values and zone of influence - Area color of shapes is homogeneous (forming a *lake*) - Idea: - *Flood* a surface based on gray values - Stop if gradient is too big - *Interpret* the image as topological map - Workflow - Compute gradients of image - Take minimal gradient(s) as *markers* or *seed points* (seed points may be set manually) - *Flood* from each seed point - If two floods meet, create a watershed line - Advantage - Enclosing/correct bordering - Disadvantage - Difficult to implement efficiently - Over-segmentation ##### Active Contour - Assumption: - Regions are bordered/enclosed by closed curve (*salient boundary*) - Regions are round/circle-like/elliptical - Method - A curve iterates towards the best possible separation - Goal: Minimize *energy* - Internal energy: Curvature/continuity - External energy: Gradient of image (fit of curve) - Advantage - Can fit *fuzzy* edge - Disadvantage - The more accurate the contour should be, the more complex is the curve - Initial curve must be given (usually manual given by seed point) ![](images/04-active.png) ##### Morphological operators - Problem: Noise - Hard for shape segmentation - May result in badly extracted shapes - Goal: Easily recognize contours - Idea: Morphological operations as pre-processing (remove noise, e.g., spikes in lines, holes in border) - Binary neighborhood operations - Change the surface - Pixels are removed/added to edges - Control operations using an operator mask (*structure element*) - Workflow: 1. Apply structure element to every pixels in source image 2. Apply operator - *Structural element* - Define neighborhood around pixel (usually symmetrical but not required) - Applied on each pixel, then apply operators - Example: Symmetric areas of pixel - Operators: - Dilation (add pixels) - Effect: Enlarge areas - Connect objects with small distance, e.g., fill holes, blow up shapes - e.g., add black pixel if any pixel in the structure element/neighborhood is colored - Erosion (remove pixels) - e.g., Add white pixel if any pixel in structure element/neighborhood is white - Problem: - Dilation and Erosion are not useful on their own - Solution: Combine operations - Operations: - *Opening* - Erosion followed by Dilation - Eliminate small/thin objects - Break tiny collections - Smooth edges - *Closing* - Dilation followed by Erosion - Fill small holes - Join near objects - Smooth edges - Advantages - Make it easier to obtain shapes - Disadvantages - Requires uniform grey values (either black or white pixels) - Precise control is difficult #### Representation ##### Basics - Shape representation - Per Object - Contours (closed curve) - Area (enclosed by curve) - Hybrid (curve + surface) - Per Image - Describe all objects at once, i.e., the dominant edges in image (e.g., edge histogram) - Shape similarity - Interpretations - Similar shaped objects - Similar dominant shapes - Choice is application-dependent - Types: - Contour-based (represent the outline) - Area-based (represent the interior/area) - Similarity measure - Usually is complex - Measure must be robust against: - Shifts (translation invariance) - Scaling (scale invariance) - Rotation (rotational invariance) - Contour-based Retrieval - Determine images with *similarly shaped objects* - Outline is viewed as closed contour (result of the segmentation) - Better semantics than global representation - Area-based Retrieval - Represent the *contour* and the *interior* of the shape - High-level features (information-preserving) - Hough / Walsh / Wavelet transforms - Possible features: - Low-level features - Chain Codes (contour-based) - Skeleton (area-based) - Moments (area-based) ##### Low-Level Features - Area non-information-preserving - Contour-based - Number of vertices - Surface area (with holes) - Enclosed area (without holes) - Eccentricity (*deviation from being circular*, [Wikipedia](https://en.wikipedia.org/wiki/Eccentricity_(mathematics))) - Area-based - Structural (primitive shapes covering an area) - Geometric (Shape area, number of holes, compactness, symmetry, moments, moment invariants) - Shape area (number of set pixels) - Roundness (*how close to circle*) - Euler number (Number of connected components - number of holes in component) - Problem contour features: - No scale invariance - Shape is not reconstructable - Shape similarity doubtful (e.g., number of vertices, area) - Therefore: Combine with other features ##### Chain Codes - Simple, pixel-based description - Represent the *contour* of the shape - Idea: - Start with certain pixel - Traverse contour clockwise/anti-clockwise - Describe changes of edge direction (depend on predecessor pixel) - Approaches: - Freeman Code (Chain Code) - Reduced Chain Code - Reduce Difference Chain Code - Shape Numbers - Scale invariance: - Improvement: Remove equal consecutive numbers - Only for simple shapes - e.g., `000666222 -> 062` - Matching/similarity: Edit distance (e.g., Levensthein) - Advantages - Relatively easy (computationally + understandable) - Disadvantage - Scaling/rotation invariance very hard (does not work well) - Lot of lost information ###### Freeman Code - Freeman, 1961 - Direction codes (example) - Right: `0` - Right-top: `1` - Top: `2` - etc. - *Reduced Chain Code* - opposite direction gets same code - e.g., Right/Left: `0`, Top/Bottom: `1` ###### Reduced Difference Chain Code - Base: Reduced Chain Code - Motivation: - Reduced Chain Code is rotation-dependent - Long codes lead to expensive similarity computation - Reduce Difference Chain Code (RDC) - Summarize consecutive numbers to their difference - Advantage: Compression - e.g, `000222000 -> 00-200200 -> 0-2020` - Problem: Only works for rotations `$ k*45° $` ###### Shape Numbers - Bribiesca/Guzman, 1978 - Idea: - Assign each type of edge a number - Build a code for the shape - Generate set of cyclic permutations of this code - Sort permutations lexicographically - Use first permutation as representation for shape - Example codes: - Convex corners - Edges - Concave corners ###### Levenstein Distance - Part of family of *edit distances* - String similarity measure - `$ A=(a_1,\ldots,a_n), B=(b_1,\ldots,b_m) $` - Weighted Levenstein distance - Idea: Convert string A to B using sequence of operations - Operations - Substitution (`$ a\rightarrow b $`) - Insertion (`$ \epsilon\rightarrow a $`) - Deletion (`$ a \rightarrow\epsilon $`) - Operations have costs (natural number) - Distance: Minimal cost for any sequence - Advanced Levenstein distance - Generalization of Levenstein Distance - New operations: - `$ aab\rightarrow abb $` - `$ abb\rightarrow aab $` - `$ a\rightarrow aa $` - `$ aa\rightarrow a $` ##### Skeleton - Blum, 1973 - Represent interior of the shape - *Skeleton*: - A thin version of a shape being equidistant to its boundaries - Set of points (only the anchor points) - Approaches - *Central axis*: - Number of centers of circles with maximum area, contained inside the shape - Do not consider all centers (only the maximal ones) - *Symmetric boundary points* - Set of centers of bi-tangent circles - Bi-tangent: Touch boundary in at least two points - Sensitive to small changes - *Shock set* (propagation model) - Simulate waves from the borders - Vertices are set where *waves* intersect - Like *Wildfire* - Use skeleton graph for comparison - Important: Consider holes - Represent using a string - Use disk with letters (like a segmentation of the space) - Source: [Shape recognition](https://www.slideshare.net/kaidul/shape-recognition-and-retrieval-based-on-edit-distance-and-dynamic-programming) - Matching: - Similarity using an edit distance (e.g., Levenshtein) - Operations - *Splice*: Remove branch - *Contract*: Represent `$ n $` branches with a single node having `$ n-1 $` branches - *Merge*: Remove node between two skeleton branches - *Deform*: Deform branch (Move node to another location) ![](images/05-skeleton.png) ##### Moments ###### Stochastic foundation - *1D discrete probability distribution* `$ f $` - Finite set `$ A $` - `$ \forall x\in A: f(x) \geq 0 $` - `$ \sum_{x\in A} f(x) = 1 $` - Random variable `$ X $` with distribution `$ f $` (`$ f(x) = P(X=x) $` - *Moment of X* - `$ m_i = \sum_{x\in A} x^i \cdot f(x) $` - First moment is expected value - *Central moments of X* - `$ \mu_i = \sum_{x\in A} (x-m_1)^i \cdot f(x) $` - First central moment is zero - Second central moment is variance - Property: Central moments are invariant to shifts - *2D discrete probability distribution* `$ f $` - `$ f:A\times B \rightarrow [0,1] $` - `$ \forall (x,y) \in A\times B: f(x) \geq 0 $` - `$ \sum_{(x,y)\in A\times B} f(x,y) = 1 $` - Random vector `$ (X,Y) $` with distribution `$ f $` - *Moment of (X,Y)* - `$ m_{i,j} = \sum_{(x,y)\in A\times B} x^i \cdot y^i \cdot f(x,y) $` - *Central moment (X,Y)* - `$ \mu_{i,j} = \sum_{(x,y)\in A\times B} (x-m_{1,0})^i \cdot (y-m_{0,1})^i \cdot f(x,y) $` - `$ \mu_{1,1} $` is covariance of X and Y - *Uniqueness theorem* - Each distribution function can be uniquely described by its moments - Condition: All elements must exist (be finite) ###### Basics - Idea: - Use intensity function `$ I $` to create probability distribution `$ f_I $` - *Image moments*: Moments of `$ f_I $` - Use image moments as features for the shape - Normalize I to get probability distribution f - `$ f(x,y)=\frac{I(x,y)}{\sum_{(u,v) \in A\times B} I(u,v)} $` - Uniqueness theorem: - Moments of `$ f_I $` (*image moments*) are an information-preserving description - Use first `$ k $` image moments as features (low-level) - Translation invariance: - Use *central moments* - Scaling invariance: - Use *normalized central moments* - `$ \eta_{i,j} = \frac{\mu_{i,j}}{(\sum_{(x,y)\in A\times B} I(x,y))^{(i+j)/2}} $` - Rotational invariance: - Idea: - Rotation/scaling in `$ \mathbb{R}^2 $` are linear transformations - Rotation by `$ \alpha $` and scaling by `$ s $`: `$ A = s \cdot (\begin{smallmatrix}\cos(\alpha)& -\sin(\alpha)\\ \sin(\alpha) & \cos(\alpha)\end{smallmatrix}) $` - Intensity function of shape yields distribution `$ f $` - Distribution `$ f $` yields normalized central moments `$ \eta $` - Goal: - Shape A is linearly transformed to shape B, the normalized central moments of A and B should be invariant under the new function `$ g $` - Invariant function `$ g $` - `$ g(\eta_{0,0},\eta_{0,1},...)=g(\eta_{0,0}',\eta_{0,1}',...) $` - `$ g $` transforms normalized central moments to new *characteristic values* so that rotation does not change these values ###### Moment Invariants - Hu, 1962 - *Moment Invariants*: Metrics that are translation, scaling and rotational invariant - Algebraic invariants - Definition - `$ g:\mathbb{R}^n \rightarrow \mathbb{R}^n $` - Weight `$ w\in \mathbb{R} $` - Matrix `$ A\in\mathbb{R}^{n \times n} $` with full rank - `$ g $` is *relative invariant* with weight `$ w $` if for **all** matrices `$ A $` and **all** `$ x\in\mathbb{R}^n $`: `$ g(Ax)=det(A)^w \cdot g(x) $` - *Absolute invariant*: `$ w=0 $` - Important Property - `$ g_1, g_2 $` are independent with weights `$ w_1, w_2 $` - `$ h(x) = \frac{g_1(x)^{w_2}}{g_2(x)^{w_1}} $` - `$ h $` is absolute invariant (`$ h(Ax)=h(x) $`) - **Important**: Independent of `$ A $` (rotation does not matter) - Hu propose seven absolute moment invariants - `$ g_1(\ldots)=\eta_{0,2}+\eta_{2,0} $` - `$ g_2(\ldots)=(\eta_{0,2}+\eta_{2,0})^2+4\eta_{1,1}^2 $` - ... - Similarity - Use vector of characteristic values (result of invariant functions) - Euclidean distance - *Separability property* - *How many moment invariants do we need?* - Two different shapes must differ in at least one component - Two similar shapes have same equal/similar components - Use property to estimate number of invariants - Improvement - Use other types of moments - Zernike moment - Tschebyschew moment - Fourier moment - Simplified computation special shapes: - Splines (polynomial functions) - Polygons - Curves (parametric representation) - Experiments - Hu, 1962 - STAR (Mehtre et al, 1995) - Company logos - Average retrieval efficiency (probably F1) of 85% - 88% - In combination with other features 89% - 94% #### Discrete Image Correspondence - Method for testing image similarity - Advantages - Simple - Fast - Steps 1. Detect points of interest 2. Describe neighborhood of points of interest (using vectors) 3. Match description vectors - Points of interest - Capture distinctive locations (==How to get them???==) - Scale/rotation invariant - Algorithms - SIFT - SURF - Matching - Distance measure on feature vector (e.g., Mahalanobis, Euclidean) - Advantage - Easy - Scale/rotation/lighting/contrast invariant - Suitable fir searching similar images - Disadvantage - No detailed information - Bad for querying objects ##### SIFT - Scale-invariant feature transform - Multi-resolution analysis - Uses linear Gaussian low-pass filter - Detection: - Filter image - Features are extreme points in gray-level histogram - *Stable point* - Extreme points in several consecutive resolutions - Are *scale invariant* - Only keep stable points - Description - Interest points get an orientation - Orientation based on grey-level histogram in direction of change - ==Peaks???== - 36 directions - Feature vector: 160 orientations ##### SURF - Speeded Up Robust Features - Detection - Box filter (averaging, better performance) - Consider consecutive resolutions - Description - Circular neighborhood (==Why?==) - Haar wavelets