Digital Image Fundamentals and Computer Vision Notes

Overview of Computer Vision and Digital Image Processing

• Key Definitions:

  • Image Function: Represented mathematically as a two-dimensional function $f(x, y)$, where $x$ and $y$ denote spatial (plane) coordinates.

  • Intensity / Gray Level: The amplitude or value of the function $f$ evaluated at any specific spatial coordinate pair $(x, y)$.

  • Digital Image: Formed when the spatial coordinates $x, y$ and the amplitude/intensity values of $f$ are all finite, discrete quantities.

  • Digital Image Processing: The domain involving the computational processing and manipulation of digital images using digital computers.

  • Pixel (Picture Element / Image Element / Pel): The fundamental discrete element comprising a digital image, possessing a specific spatial position and scalar intensity value.

• Spectrum of Computerized Visual Processing:

  • Computer Vision: A subfield of Artificial Intelligence ($\text{AI}$) whose overarching objective is to emulate human visual perception, learning, inference, and action execution from visual inputs.

  • Continuum Boundaries: No strict boundary exists between digital image processing at one extreme and computer vision at the other, but processes are generally categorized into three computational levels:

  • Low-Level Processes: Take an image as input and produce an image as output. Encompass primitive operations such as noise reduction, contrast enhancement, and image sharpening.

  • Mid-Level Processes: Take an image as input and yield extracted image attributes (such as edges, contours, or object identities) as output. Includes tasks like image segmentation, object description, and object classification/recognition.

  • High-Level Processes: Involve visual cognition, scene understanding, image analysis, and executing high-level decisions based on an ensemble of recognized objects.

Historical Context: Origins of Digital Image Processing

• Early Telecommunication Milestones:

  • Bartlane Cable Picture Transmission System: Introduced in the early 1920s to transmit digital images across transatlantic submarine cables.

  • Transmission Efficiency: Reduced the total transport duration of a newspaper image across the Atlantic Ocean from over one week to under three hours.

  • System Mechanics: Encoded image data onto paper tapes at the transmitting terminal and reconstructed images at the receiving terminal using telegraph printers equipped with specialized typefaces.

Fundamental Steps in Digital Image Processing

• Process Classification & Architecture:

  • Image Output Stages: Image Acquisition, Image Enhancement, Image Restoration, Color Image Processing, Wavelets and Multiresolution Processing, Compression, and Morphological Processing.

  • Attribute Output Stages: Segmentation, Representation and Description, and Object Recognition.

  • Knowledge Base: A centralized database containing problem-domain information that interacts continuously across all processing stages.

• Detailed Functional Breakdown:

  • Image Acquisition:

  • The initial stage in any image processing pipeline.

  • Involves converting a physical scene into a digital image, which may include spatial scaling and preprocessing.

  • Can be as simple as receiving an existing image file in digital format.

  • Image Enhancement:

  • A subjective processing discipline focused on highlighting specific features of interest or unmasking hidden detail.

  • Example: Increasing contrast to make an image more visually useful or aesthetically appealing.

  • Image Restoration:

  • An objective processing discipline focused on reversing image degradation.

  • Relies on explicit mathematical or probabilistic models of degradation mechanisms, contrasting with subjective enhancement.

  • Color Image Processing:

  • Focuses on techniques for handling full-color digital images and multi-spectral imagery.

  • Crucial due to the rapid proliferation of color digital graphics across global networks.

  • Wavelets and Multiresolution Processing:

  • Provides a mathematical framework for representing images at varying degrees of spatial resolution.

  • Images are recursively decomposed into smaller spatial frequency sub-bands.

  • Compression:

  • Focuses on reducing data redundancy to decrease storage requirements and transmission bandwidth.

  • Utilizes standards such as the Joint Photographic Experts Group ($\text{JPEG}$), commonly denoted by the $.jpg$ file extension.

  • Morphological Processing:

  • Provides mathematical tools for extracting structural image components useful in shape representation and description.

  • Segmentation:

  • Partitions an input image into its constituent regions, structures, or individual objects.

  • Autonomous segmentation is one of the most challenging tasks in image processing.

  • Robust segmentation algorithms are necessary for successful high-level visual analysis; weak algorithms lead to failure.

  • Representation and Description:

  • Follows the segmentation stage, taking raw pixel data representing boundaries or regions.

  • Boundary Representation: Used when the focus is on external shape features (such as corners and inflection points).

  • Regional Representation: Used when the focus is on internal attributes (such as texture or skeletal topology).

  • Description: Computes specific feature descriptors from representation data to differentiate objects.

  • Object Recognition:

  • Assigns specific symbolic labels (such as vehicle, cell, or letter) to objects based on computed descriptors.

  • Knowledge Base:

  • Encodes domain-specific information, directing algorithm execution and guiding interactions between processing stages.

Components of a General-Purpose Image Processing System

• Hardware and Software Architecture:

  • Systems integrate sensing, hardware acceleration, general processing, mass storage, displays, hardcopy units, and networking.

• Functional Subsystem Specifications:

  • Image Sensors:

  • Requires a physical sensing device sensitive to emitted or reflected physical energy (such as light).

  • Requires a digitizer to convert continuous physical voltage waveforms into digital values.

  • Specialized Image Processing Hardware:

  • Hardware modules designed for high-throughput processing, such as Digitizers and Arithmetic Logic Units ($\text{ALU}$).

  • Operates as a front-end subsystem to perform fast parallel operations across entire image matrices.

  • Performs real-time tasks like frame-averaging at video rates ($30\,\text{frames/s}$) to eliminate noise.

  • Main Computer:

  • General-purpose computer system ranging from standard personal computers ($\text{PC}$) to high-performance supercomputers.

  • Image Processing Software:

  • Specialized software libraries consisting of dedicated image manipulation modules.

  • Allows integration of custom user scripts and high-level programming language routines.

  • Mass Storage Subsystems:

  • Essential due to high memory demands; an uncompressed $1024 \times 1024$ pixel image with $8\text{-bit}$ intensity values requires $1\,\text{MB}$ ($10^6\,\text{bytes}$) of storage.

  • Short-Term Storage: High-speed system memory and dedicated frame buffers capable of rapid refresh at video rates ($30\,\text{images/s}$).

  • Online Storage: Fast-recall magnetic disks and optical media.

  • Archival Storage: Massive capacity storage with lower access speeds, such as magnetic tapes and automated optical jukeboxes.

  • Standard Storage Metrics: Bytes ($8\,\text{bits}$), Kilobytes ($\text{KB} = 10^3\,\text{bytes}$), Megabytes ($\text{MB} = 10^6\,\text{bytes}$), Gigabytes ($\text{GB} = 10^9\,\text{bytes}$), and Terabytes ($\text{TB} = 10^{12}\,\text{bytes}$).

  • Hardcopy Output Devices:

  • Film cameras, laser printers, heat-sensitive devices, inkjet printers, and digital storage media.

  • Film provides the highest achievable spatial resolution, whereas paper is standard for printed documents.

  • Networking Infrastructure:

  • Handles image data transfer across remote computational nodes, where network bandwidth represents the primary operational constraint.

Image Sampling and Quantization

• Mathematical Principles of Discretization:

  • Physical sensors capture continuous real-world phenomena as continuous voltage waveforms.

  • To create a digital image, continuous spatial coordinates and continuous amplitude values must both be digitized.

  • Spatial Coordinate Discretization: Termed sampling.

  • Intensity Amplitude Discretization: Termed quantization.

• Step-by-Step Digitization along a Scanline:

  • A continuous 1D intensity profile taken along line segment $AB$ contains minor fluctuations due to sensor noise.

  • Spatial sampling selects discrete, equally spaced spatial locations along line $AB$, indicated by vertical tick marks.

  • Amplitude quantization divides the continuous intensity scale into discrete levels (such as $8$ distinct levels from black to white).

  • Each spatial sample is assigned the closest discrete intensity level on the scale to yield a digital scanline profile.

Digital Image Representation

• Matrix Representation of Digital Images:

  • Sampling and quantization map a continuous image $f(x, y)$ into an $M \times N$ numerical matrix.

  • Discrete spatial coordinate system: Origin $(x, y) = (0, 0)$ is located at the top-left corner.

  • Axis Orientation: Row index $x$ extends vertically downward from $0$ to $M-1$; column index $y$ extends horizontally rightward from $0$ to N-1$.\n\n\n\n* Matrix Formulations:\n * Continuous sampling representation:\n    f(x, y) = \begin{bmatrix} f(0,0) & f(0,1) & \cdots & f(0, N-1) \ f(1,0) & f(1,1) & \cdots & f(1, N-1) \ \vdots & \vdots & \ddots & \vdots \ f(M-1,0) & f(M-1,1) & \cdots & f(M-1, N-1) \end{bmatrix}\n * Traditional matrix notation:\n    \mathbf{A} = \begin{bmatrix} a_{0,0} & a_{0,1} & \cdots & a_{0,N-1} \ a_{1,0} & a_{1,1} & \cdots & a_{1,N-1} \ \vdots & \vdots & \ddots & \vdots \ a_{M-1,0} & a_{M-1,1} & \cdots & a_{M-1,N-1} \end{bmatrix}\n\n* Intensity Quantization and Memory Footprint Calculations:\n * Discrete intensity levels L$are typically restricted to integer powers of$2 due to hardware constraints:\n    L = 2^k\n * Intensity values are equally spaced integers in the closed range [0, L-1].\n * Dynamic Range: The range of intensity values present in an image. Images spanning a high dynamic range exhibit high contrast, whereas low dynamic range images appear dull and washed out.\n * Required Memory Capacity b (in bits):\n    b = M \times N \times k\n * For square digital images where M = N:\n    b = N^2 \times k\n\n* Exact Memory Capacity Values for Square Images (N \times N):\n * N = 32, k = 1\,(L = 2) \implies 1,024\,\text{bits}\n * N = 32, k = 8\,(L = 256) \implies 8,192\,\text{bits}\n * N = 64, k = 8\,(L = 256) \implies 32,768\,\text{bits}\n * N = 128, k = 8\,(L = 256) \implies 131,072\,\text{bits}\n * N = 256, k = 8\,(L = 256) \implies 524,288\,\text{bits}\n * N = 512, k = 8\,(L = 256) \implies 2,097,152\,\text{bits}\n * N = 1024, k = 8\,(L = 256) \implies 8,388,608\,\text{bits}\n * N = 2048, k = 8\,(L = 256) \implies 33,554,432\,\text{bits}\n * N = 4096, k = 8\,(L = 256) \implies 134,217,728\,\text{bits}\n * N = 8192, k = 8\,(L = 256) \implies 536,870,912\,\text{bits}\n\n# Spatial and Gray-Level Resolution\n\n* Core Definitions:\n * Spatial Resolution: The smallest discernible spatial detail in an image, governed primarily by spatial sampling frequency. Quantified as discernible line pairs per unit distance (e.g., 100\,\text{line pairs/mm}).\n * Gray-Level Resolution: The smallest discernible variation in intensity levels within an image.\n\n* Sampling Operations:\n * Subsampling: Reduces image dimensions by deleting rows and columns from the pixel array.\n * Resampling: Enlarges smaller images to original dimensions via row and column duplication.\n\n\n\n* Zooming and Shrinking:\n * Zooming (Oversampling): Requires creating a high-density grid and assigning intensity values to new pixel locations.\n * Shrinking (Undersampling): Collapses an existing grid into fewer spatial samples.\n * Interpolation Techniques:\n * Nearest Neighbor Interpolation: Assigns the intensity of the nearest pixel in the original image. Computationally simple, but produces visible blockiness.\n * Bilinear Interpolation: Interpolates intensity using the four closest neighbors, producing smoother transitions.\n\n\n\n# Basic Relationships Between Pixels\n\n* Pixel Neighborhoods:\n * For a central pixel p$at spatial coordinates$(x, y):\n * 4\text{-Neighbors } N_4(p): The four orthogonally adjacent pixels:\n    N_4(p) = {(x+1, y), (x-1, y), (x, y+1), (x, y-1)}\n * Diagonal Neighbors N_D(p): The four diagonally adjacent pixels:\n    N_D(p) = {(x+1, y+1), (x+1, y-1), (x-1, y+1), (x-1, y-1)}\n * 8\text{-Neighbors } N_8(p): Union of orthogonal and diagonal neighbors:\n    N_8(p) = N_4(p) \cup N_D(p)\n\n* Pixel Adjacency Types:\n * Let V$be the set of intensity values used to define adjacency (e.g.,$V = {1}$for binary images, or a designated subset of$[0, 255] for grayscale images).\n * 4\text{-Adjacency}$: Pixels$p$and$q$with values from$V$are$4\text{-adjacent}$if$q \in N_4(p).\n * 8\text{-Adjacency}$: Pixels$p$and$q$with values from$V$are$8\text{-adjacent}$if$q \in N_8(p).\n * m\text{-Adjacency (Mixed Adjacency)}$: Pixels$p$and$q$with values from$V$are$m\text{-adjacent} if:\n 1. q \in N_4(p), OR\n 2. q \in N_D(p)$AND the intersection set$N_4(p) \cap N_4(q)$contains no pixels with intensity values from$V$.

  • Purpose of $m\text{-Adjacency}$: Modifies $8\text{-adjacency}$ to eliminate ambiguous, multiple path connections.

• Paths, Connectivity, Regions, and Boundaries:

  • Digital Path: A sequence of distinct pixels $(x_0, y_0), (x_1, y_1), \dots, (x_n, y_n)$ where $(x_0, y_0) = (x, y)$, $(x_n, y_n) = (s, t)$, and $(x_i, y_i)$ is adjacent to $(x_{i-1}, y_{i-1})$ for 1 \le i \le n$.\n * Path Length: Total number of steps n along the sequence.\n * Closed Path: A path where (x_0, y_0) = (x_n, y_n).\n * Connectivity: Pixels p$and$q$are connected in a pixel subset$S$if a path exists between them composed entirely of pixels in$S$.

  • Connected Component: The set of all pixels in $S$ connected to a given pixel $p$

  • Connected Set: A subset $S$ that consists of a single connected component.

  • Region $R$: A subset of pixels in an image that forms a connected set.

  • Boundary (Border / Contour): The set of pixels in region $R$ that have at least one neighbor not in $R$. If $R$ is the entire image, its boundary consists of the first and last rows and columns.

Pixel Distance Metrics

• Axiomatic Metric Definition:

  • A distance function $D$ between pixels $p(x, y)$, $q(s, t)$, and $z(v, w)$ is a valid metric if it satisfies:

  1. Non-negativity and Identity: $D(p, q) \ge 0$, and $D(p, q) = 0 \iff p = q$

  2. Symmetry: $D(p, q) = D(q, p)$

  3. Triangle Inequality: $D(p, z) \le D(p, q) + D(q, z)$

• Metric Equations and Geometric Forms:

  • Euclidean Distance $D_e(p, q)$:     $D_e(p, q) = \sqrt{(x - s)^2 + (y - t)^2}$     Pixels satisfying $D_e(p, q) \le r$ form a circular disk of radius $r$ centered at $(x, y)$.

  • City-Block Distance $D_4(p, q)$:     $D_4(p, q) = |x - s| + |y - t|$     Pixels satisfying $D_4(p, q) \le r$ form a diamond centered at $(x, y)$.     Contour of constant $D_4$ distance values centered at $(x, y)$ with $D_4 = 0$: 2 2 1 2 2 1 0 1 2 2 1 2 2     

  • $D_4 = 0 \rightarrow$ center pixel $(x, y)$

  • $D_4 = 1 \rightarrow$ 4-neighbors directly adjacent to the center

  • $D_4 = 2 \rightarrow$ pixels two steps away via horizontal and vertical movements

  • Chessboard Distance $D_8(p, q)$:     $D_8(p, q) = \max(|x - s|, |y - t|)$     Pixels satisfying $D_8(p, q) \le r$ form a square centered at $(x, y)$.     Contour of constant $D_8$ distance values centered at $(x, y)$ with $D_8 \le 2$: 2 2 2 2 2 2 1 1 1 2 2 1 0 1 2 2 1 1 1 2 2 2 2 2 2     

  • $D_8 = 1 \rightarrow$ 8-neighbors of $(x, y)$.