DIP and Pattern Recognition Important Questions with Answers: Chapter 4 Feature Extraction and Dimension Reduction
Very Short Answers (1-2 marks)
1. Define texture as an image feature.
- Texture describes the spatial arrangement and repetition of intensity patterns in a region - smoothness, coarseness, regularity - used to characterise surfaces like grass, fabric or bark.
2. What is a shape feature?
- A measurable property of an object's boundary or region - area, perimeter, compactness, aspect ratio, moments - that stays useful for recognition regardless of texture or colour.
3. Define a local feature.
- A distinctive structure detected at a specific image location - a corner, blob or edge patch - described independently of the rest of the image, so matching works under occlusion and viewpoint change.
4. What is the frequency domain?
- The representation of an image as a sum of sinusoidal components (via the Fourier transform), where each coefficient captures variation at one spatial frequency instead of one pixel position.
5. Define HOG.
- Histogram of Oriented Gradients: a descriptor that counts gradient orientations within small cells of an image patch, capturing local shape through the distribution of edge directions - classic in pedestrian detection.
6. What is corner detection?
- Finding image points where intensity changes strongly in two or more directions - junctions and corners - which are stable, well-localised features for matching and tracking.
7. Define SIFT.
- Scale-Invariant Feature Transform: a detector-descriptor that finds keypoints across scales and describes each with a 128-dimensional histogram of local gradient orientations, invariant to scale and rotation.
8. What is SURF?
- Speeded-Up Robust Features: a faster approximation of SIFT using box filters and integral images for Hessian-based keypoint detection and gradient histogram description.
9. Define the Hough transform.
- A voting technique that maps edge points into a parameter space so that collinear (or co-circular) points accumulate votes at the parameters of the line (or circle) they lie on - detects shapes despite gaps and noise.
10. What is dimension reduction?
- Mapping high-dimensional feature vectors into fewer dimensions while keeping the information that matters for classification - to cut computation, storage and overfitting.
11. Define Principal Component Analysis.
- PCA: an unsupervised linear transform that finds orthogonal directions (principal components) of maximum variance in the data, so the first few components retain most of the information.
12. What is Fisher Linear Discriminant Analysis?
- A supervised linear projection that maximises the separation between class means relative to within-class scatter - dimensions chosen for class separability, not just variance.
13. Define the Expectation-Maximization algorithm.
- An iterative method for maximum-likelihood estimation with hidden variables: the E-step estimates the expected hidden assignments given current parameters; the M-step re-estimates parameters from those assignments; repeat to convergence.
14. What is a Hidden Markov Model?
- A probabilistic model for sequences: hidden states generate observations with emission probabilities and evolve with transition probabilities - used for speech and sequential pattern recognition.
15. Define a Gaussian Mixture Model.
- A density model that represents a distribution as a weighted sum of several Gaussian components, usually fitted with the EM algorithm.
Short Answers (5-7 marks)
1. Explain the difference between spatial domain and frequency domain processing.
| Point | Spatial domain | Frequency domain |
|---|---|---|
| Representation | Pixel intensities at coordinates | Sinusoidal coefficients per frequency |
| Operation | Direct pixel/neighbourhood manipulation | Modify coefficients, then invert the transform |
| Typical tasks | Smoothing, sharpening by convolution | Filtering by frequency selection, compression |
| Feature view | Local geometry (edges, corners) | Global periodic structure (texture direction, coarseness) |
2. Why are corners considered good features for matching?
- They are distinctive: intensity changes in two directions, so each corner's neighbourhood is unlike flat or edge regions nearby.
- They are well-localised: a corner pins down an exact (x, y) position, unlike an edge which is ambiguous along its length.
- They repeat: the same physical corner is detectable across viewpoints, scales and lighting changes.
- Hence corner matches give precise, reliable correspondences for tracking, stitching and 3D reconstruction.
3. Explain the significance of eigenvalues in PCA.
- Each eigenvalue of the covariance matrix equals the variance of the data along its eigenvector (principal component).
- Sorting eigenvalues ranks components by information content; the top-k capture most variance.
- The ratio (sum of kept eigenvalues)/(total) quantifies how much information the reduced representation retains - a direct guide for choosing k.
4. What is the role of the E-step and M-step in the EM algorithm?
- E-step: using current parameters, compute the posterior probability that each sample belongs to each hidden component (soft assignment).
- M-step: re-estimate the parameters (weights, means, covariances) by maximum likelihood using those soft assignments as weights.
- Alternating the two steps never decreases the likelihood, so iteration climbs to a local maximum.
5. Compare PCA and Fisher LDA.
| Point | PCA | Fisher LDA |
|---|---|---|
| Type | Unsupervised | Supervised (uses class labels) |
| Maximises | Total variance captured | Between-class separation vs within-class scatter |
| Best for | Compression, visualisation, denoising | Classification-oriented reduction |
| Max components | Up to the feature dimension | At most (number of classes - 1) |
| Risk | High-variance direction may not separate classes | Needs labelled data; weaker with few samples |
6. Explain color, texture and shape features used in image analysis.
- Color: histograms and moments in RGB/HSV space - fast, viewpoint-tolerant, but lighting-sensitive.
- Texture: co-occurrence matrices, Gabor responses, local binary patterns - capture surface micro-structure.
- Shape: boundary and region descriptors - moments, compactness, Fourier descriptors - capture object form.
- Real systems combine them: colour for coarse filtering, texture for material, shape for identity.
7. Discuss local features and their advantages over global features.
- Global features describe the whole image with one vector (one colour histogram for everything); local features describe many small patches (SIFT keypoints).
- Advantages of local: robust to occlusion (unseen patches simply do not vote), to background clutter, and to viewpoint change; they also support geometric verification of matches.
- Cost: hundreds of descriptors per image, needing indexing structures for fast matching.
8. Explain the Histogram of Oriented Gradients (HOG) feature descriptor.
- Compute gradients (magnitude and orientation) at every pixel.
- Divide the detection window into small cells (e.g. 8x8 pixels).
- In each cell build a histogram of gradient orientations weighted by magnitude.
- Normalise histograms over overlapping blocks for lighting invariance.
- Concatenate all block histograms into one descriptor vector.
The descriptor captures local edge-direction structure - the silhouette cues that make pedestrian and object detection work.
9. Describe the Harris corner detection method.
- For each pixel, form the 2x2 matrix M of summed squared gradients over a window: M = [ΣIx² ΣIxIy; ΣIxIy ΣIy²].
- Compute the corner response R = det(M) - k*trace(M)².
- Flat regions give small eigenvalues (small R), edges give one large eigenvalue (R negative or small), corners give two large eigenvalues (large positive R).
- Threshold R and keep local maxima as corners.
It is rotation-invariant and needs no eigen decomposition per pixel, which is why it became the default corner detector.
10. Explain the SIFT and SURF feature descriptors.
- SIFT: detect extrema in a Difference-of-Gaussians scale space, assign a dominant orientation, then build a 4x4 grid of 8-bin gradient-orientation histograms (128 values). Invariant to scale and rotation, partly to lighting and viewpoint.
- SURF: same goals with speed-ups - box-filter approximations of second-order derivatives on integral images for detection, and Haar-wavelet responses summed over sub-regions for description (64 or 128 values).
- Both turn each keypoint into a vector matchable by nearest neighbour in descriptor space.
11. Discuss the working of the Hough transform for line detection.
- Run edge detection to get edge points.
- Each edge point (x, y) votes for every parameter pair (ρ, θ) satisfying ρ = x cosθ + y sinθ - a sinusoid in parameter space.
- Sinusoids of collinear points intersect at the line's true parameters, producing a peak in the accumulator.
- Detect accumulator peaks above a threshold; each peak is a detected line.
Voting makes it robust to broken edges and noise: gaps do not destroy the peak, only lower it.
12. Explain Principal Component Analysis as a dimension reduction technique.
- Centre the data (subtract the mean vector).
- Compute the covariance matrix.
- Find its eigenvectors and eigenvalues; sort descending.
- Keep the top-k eigenvectors as the projection matrix W.
- Project: z = Wᵘ(x - mean) gives the k-dimensional representation.
The first k components capture the maximum possible variance of any k-dimensional linear projection - the optimal linear compression in the least-squares sense.
13. Compare PCA and Fisher Linear Discriminant Analysis for dimension reduction.
PCA finds directions of maximum overall variance without knowing classes; Fisher LDA finds directions maximising between-class scatter relative to within-class scatter, so it targets discrimination directly. Example: for two classes elongated along the same axis, PCA keeps that axis (variance) even if the classes separate best across it - LDA picks the across-axis direction. PCA suits unlabelled compression; LDA suits pre-classification reduction but is capped at (classes - 1) dimensions and needs labels.
14. Analyze the working of the Expectation-Maximization algorithm with a suitable example.
Take a Gaussian mixture with unknown weights, means and variances. E-step: for each point, compute the responsibility of each component (how likely that Gaussian generated it). M-step: update each component's mean as the responsibility-weighted average of points, similarly variance and weight. Example: heights of a mixed population with no gender labels - EM soft-assigns each height to a cluster, refits the two Gaussians, and iterates until assignments stop changing. Each cycle provably raises (or holds) the likelihood; it converges to a local optimum, so initialisation matters.
15. Differentiate between Hidden Markov Models and Gaussian Mixture Models.
| Point | HMM | GMM |
|---|---|---|
| Models | Sequences with temporal order | Independent samples from a static density |
| Hidden structure | State chain with transition probabilities | Component identity per sample, no ordering |
| Emission | Each state emits observations (often a GMM itself) | Each component is one Gaussian |
| Use | Speech, handwriting, time series | Clustering, density modelling |
16. Compare spatial-domain and frequency-domain feature extraction approaches.
- Spatial features come straight from pixels: edges, corners, texture statistics, shape moments - intuitive, localised, easy to combine with geometry.
- Frequency features come from transforms (Fourier, wavelets, Gabor): energy per band, orientation spectra - naturally capture periodic texture and scale structure.
- Spatial methods excel at localisation; frequency methods excel at characterising repetitive patterns over regions. Wavelets bridge both by offering localised frequency analysis.
17. Analyze the computational trade-offs between SIFT and SURF descriptors.
- SURF's integral-image box filters make detection and description several times faster than SIFT's Gaussian pyramids - suitable for real-time use.
- SIFT's 128-D gradient histograms are typically more distinctive and more robust to strong viewpoint and illumination change.
- SURF's approximations trade a little accuracy for speed; SIFT's exactness costs CPU time and memory.
- Rule of thumb: offline matching and stitching - SIFT; live tracking on modest hardware - SURF.
18. Apply PCA to reduce the dimensionality of a given feature set.
Worked outline: with N samples of d-dimensional features, centre the matrix, compute the d×d covariance, take eigen-decomposition, and keep the k eigenvectors whose eigenvalues cover about 95% of total variance. Project every sample onto them. Example: 1000-D image histograms often compress to 50-100 components while keeping recognition accuracy nearly unchanged, cutting storage and classifier training time by an order of magnitude.
19. Apply the Hough transform to detect lines in a given edge image.
Procedure: threshold the edge image; for each edge pixel vote over quantised θ values using ρ = x cosθ + y sinθ; smooth the accumulator; pick peaks above a vote threshold; map each peak (ρ, θ) back to a line and overlay it on the image. Practical notes: fine quantisation finds exact lines but needs more memory; a higher threshold suppresses spurious short alignments; circle detection works the same way with a 3-D (a, b, r) accumulator.
20. Design a feature extraction and dimension reduction pipeline for a face recognition system.
- Detect and crop faces; normalise size and lighting.
- Extract local descriptors (HOG or learned features) on a grid - thousands of dimensions.
- Apply PCA to compress to ~100-200 components (the classic eigenfaces step).
- Optionally apply Fisher LDA to maximise between-person separation.
- Classify with nearest neighbour or a linear classifier in the reduced space.
The pipeline mirrors eigenfaces/Fisherfaces: local raw appearance, unsupervised compression, supervised sharpening, simple final classifier.
Long Answers (10 marks)
1. Explain color, texture, shape and local features used for image representation in detail.
Expand the short-answer core into four full parts: color (histograms, color moments, spaces and their lighting trade-offs); texture (statistical - co-occurrence matrices and Haralick measures; spectral - Gabor and wavelet energy; structural - LBP); shape (boundary - chain codes, Fourier descriptors; region - Hu moments, compactness, eccentricity); local (detectors Harris/SIFT, descriptors as gradient histograms, invariance properties). For each give the definition, one representative method, invariance behaviour, and one application; close with how multi-cue fusion combines them in real recognition systems.
2. Discuss the Histogram of Oriented Gradients (HOG) and corner detection techniques in detail.
Part 1, HOG full pipeline: gradient computation, cell histograms, block normalisation, final vector; why block normalisation gives illumination invariance; the pedestrian-detection use case. Part 2, corner detection: the second-moment matrix M, Harris response R = det(M) - k trace(M)², interpretation of eigenvalue pairs (flat/edge/corner), non-maximum suppression; mention Shi-Tomasi (min eigenvalue criterion) and scale-space variants. Compare: HOG describes regions densely for detection windows; corners give sparse precise points for matching.
3. Explain SIFT and SURF feature descriptors in detail, highlighting their invariance properties.
SIFT: scale-space extrema via Difference of Gaussians, keypoint localisation, orientation assignment from local gradient histogram, 4x4x8 descriptor, 128-D. Invariance: scale (from scale space), rotation (from orientation normalisation), partial illumination and affine change (from normalised gradients). SURF: Hessian detector with box filters on integral images, Haar-wavelet orientation assignment, 64/128-D descriptor; same invariances with much lower compute. Add a comparison table (speed, distinctiveness, dimensionality, best use) and the standard matching pipeline: descriptor nearest neighbour + ratio test + geometric verification.
4. Discuss the Hough transform for detecting lines and circles with suitable mathematical formulation.
Lines: parameterisation ρ = x cosθ + y sinθ, the voting accumulator, peak detection; why ρ-θ beats slope-intercept (vertical lines, bounded space). Circles: (x - a)² + (y - b)² = r² gives a 3-D accumulator; gradient-direction trick reduces voting to a line in (a, b) space. Discuss quantisation, thresholding, robustness to gaps and noise, complexity growth with parameter count, and generalised Hough for arbitrary shapes.
5. Explain Principal Component Analysis in detail and derive the expression for principal components.
Setup: centred data matrix X, sample covariance S = (1/N) X Xᵘ. Goal: unit vector w maximising projected variance wᵘSw. Lagrangian wᵘSw - λ(wᵘw - 1); differentiating gives Sw = λw - principal components are eigenvectors of S, and the variance along each is its eigenvalue. Then: sorting, the variance-retention criterion for choosing k, reconstruction x̂ = W z + mean, and remarks: PCA is the best linear least-squares approximation, it decorrelates features, and its unsupervised nature is both its strength (no labels) and weakness (variance is not class separability).
6. Discuss Fisher Linear Discriminant Analysis and compare it with PCA for dimension reduction.
Fisher criterion: maximise J(w) = (wᵘS_B w)/(wᵘS_W w), with between-class scatter S_B and within-class scatter S_W. The solution for two classes is w ∝ S_W⁻¹(m1 - m2); for c classes, the top (c-1) generalised eigenvectors of S_W⁻¹S_B. Compare with PCA: supervised vs unsupervised, discriminative vs descriptive, capped at c-1 vs d components, behaviour when the high-variance direction is not discriminative, small-sample issues (singular S_W) and the remedy (PCA before LDA - the Fisherfaces pipeline).
7. Explain the Expectation-Maximization algorithm in detail with its application to Gaussian Mixture Models.
General EM: incomplete-data log-likelihood with hidden variables; E-step computes the posterior over hidden variables (responsibilities), M-step maximises the expected complete-data likelihood; monotonic likelihood increase and local-optimum caveat. GMM application: model p(x) = Σ πk N(x|μk, Σk); E-step responsibilities γnk = πk N(xn|μk,Σk) / Σj πj N(xn|μj,Σj); M-step closed-form updates for πk, μk, Σk using responsibilities. Cover initialisation (k-means), choice of K, singularities, and uses in clustering and density modelling for classifiers.
8. Apply dimension reduction techniques (PCA and Fisher LDA) to a given high-dimensional dataset and compare the results.
Protocol: standardise features, split train/test, fit PCA at several k values and LDA at c-1 dimensions on training data only, train the same simple classifier on each reduced space, compare accuracy, training time and storage. Expected findings: PCA accuracy rises with k and plateaus near the 95% variance point; LDA reaches strong accuracy in very few dimensions when classes are well separated; PCA beats LDA when between-class direction has low variance or labels are noisy. Present a comparison table and the lesson: choose by whether variance or separability carries the class signal.
9. Evaluate the suitability of Hidden Markov Models and Gaussian Mixture Models for sequential and non-sequential pattern recognition problems respectively.
GMM: assumes i.i.d. samples from a static mixture - right for non-sequential tasks (image patch clustering, speaker-independent frame modelling, density estimation) and wrong wherever order carries information. HMM: adds a state chain with transitions, capturing temporal structure - right for speech, handwriting, gesture and bio-sequence recognition; its three canonical problems (evaluation by forward-backward, decoding by Viterbi, learning by Baum-Welch EM). Evaluation: use HMM when sequence order matters and states have physical meaning; use GMM alone when samples are unordered; note the hybrid (GMM emissions inside HMM states) used in classic speech systems.
10. Design a complete feature extraction and dimension reduction system for a real-world application such as handwriting or face recognition.
Full design for face recognition: acquisition and face detection; normalisation (alignment, histogram equalisation); feature extraction (grid HOG or raw pixels); PCA compression to ~150 components; Fisher LDA for discriminative sharpening; classification by nearest neighbour with a distance metric, or an SVM; evaluation by cross-validation with recognition rate and false-accept rate; discussion of failure modes (lighting, pose, occlusion) and mitigations (more local features, per-subject enrollment sets). Marks flow: pipeline diagram, justification of each stage, dimension choices with variance/separability reasoning, and an honest evaluation plan.
Comments
Post a Comment