academic-computer-graphics-image-processing

# Computer Graphics, Computer Vision, and Image Processing This skill establishes the rigorous mathematical foundations, rendering algorithms, modern computer vision, digital visual effects compositing, and numerical processing of 2D/3D geometry. --- ## 📐 1. 3D Geometric Transformations and Projection Algebra ### 1.1 Homogeneous Coordinates and the Transformation Pipeline In computer graphics, points in $\mathbb{R}^3$ are represented in homogeneous coordinates $\mathbf{p} = [x, y, z, 1]^T$ to unify affine operations (translation, rotation, scale, and shear) into $4 \times 4$ matrices: $$\mathbf{v}_{clip} = \mathbf{M}_{proj} \cdot \mathbf{M}_{view} \cdot \mathbf{M}_{model} \cdot \mathbf{v}_{local}$$ - **Translation Matrix**: $$\mathbf{T}(t_x, t_y, t_z) = \begin{bmatrix} 1 & 0 & 0 & t_x \\ 0 & 1 & 0 & t_y \\ 0 & 0 & 1 & t_z \\ 0 & 0 & 0 & 1 \end{bmatrix}$$ - **Rotation Matrix around an Arbitrary Axis $\mathbf{u} = [u_x, u_y, u_z]^T$ with $\|\mathbf{u}\|=1$ (Rodrigues' Formula)**: $$\mathbf{R}(\theta, \mathbf{u}) = \cos\theta \mathbf{I} + (1 - \cos\theta) \mathbf{u}\mathbf{u}^T + \sin\theta [\mathbf{u}]_\times$$ where $[\mathbf{u}]_\times$ is the skew-symmetric matrix: $$[\mathbf{u}]_\times = \begin{bmatrix} 0 & -u_z & u_y \\ u_z & 0 & -u_x \\ -u_y & u_x & 0 \end{bmatrix}$$ ### 1.2 Quaternions and Spherical Interpolation (SLERP) To avoid Gimbal Lock and guarantee smooth rotational interpolation of 3D orientations: - **Unit Quaternion**: $\mathbf{q} = s + x\mathbf{i} + y\mathbf{j} + z\mathbf{k} = [\cos(\theta/2), \mathbf{u}\sin(\theta/2)]$ where $\|\mathbf{q}\| = 1$. - **Rotation of a Point**: $\mathbf{p}' = \mathbf{q} \mathbf{p} \mathbf{q}^{-1} = \mathbf{q} \mathbf{p} \mathbf{q}^*$. - **SLERP (Spherical Linear Interpolation)**: $$\text{SLERP}(\mathbf{q}_1, \mathbf{q}_2; t) = \frac{\sin((1-t)\Omega)}{\sin\Omega} \mathbf{q}_1 + \frac{\sin(t\Omega)}{\sin\Omega} \mathbf{q}_2 \quad \text{where } \cos\Omega = \mathbf{q}_1 \cdot \mathbf{q}_2$$ ### 1.3 Perspective and Orthographic Projection Matrices - **Symmetric Perspective Projection (Frustum with $fov$, $aspect$, $z_{near}$, $z_{far}$)**: $$\mathbf{M}_{persp} = \begin{bmatrix} \frac{1}{\text{aspect} \cdot \tan(fov/2)} & 0 & 0 & 0 \\ 0 & \frac{1}{\tan(fov/2)} & 0 & 0 \\ 0 & 0 & -\frac{z_f + z_n}{z_f - z_n} & -\frac{2 z_f z_n}{z_f - z_n} \\ 0 & 0 & -1 & 0 \end{bmatrix}$$ - **Perspective Division**: Normalized Device Coordinate (NDC) normalization: $\mathbf{v}_{ndc} = [x_c/w_c, y_c/w_c, z_c/w_c]^T$. --- ## 〰️ 2. Parametric Curves and 3D Surfaces ### 2.1 Bézier Curves and the De Casteljau Algorithm A Bézier curve of degree $n$ defined by $n+1$ control points $\mathbf{P}_0, \mathbf{P}_1, \dots, \mathbf{P}_n$: $$\mathbf{C}(t) = \sum_{i=0}^n B_{i,n}(t) \mathbf{P}_i, \quad t \in [0, 1]$$ where $B_{i,n}(t) = \binom{n}{i} t^i (1-t)^{n-i}$ are the Bernstein polynomials. - **Cubic Bézier ($n=3$)**: $$\mathbf{C}(t) = (1-t)^3 \mathbf{P}_0 + 3t(1-t)^2 \mathbf{P}_1 + 3t^2(1-t) \mathbf{P}_2 + t^3 \mathbf{P}_3$$ - **De Casteljau Algorithm**: Numerically stable recursive evaluation by successive linear interpolations $\mathbf{P}_i^{(k)}(t) = (1-t)\mathbf{P}_i^{(k-1)}(t) + t\mathbf{P}_{i+1}^{(k-1)}(t)$. ### 2.2 B-Splines and NURBS Surfaces - **B-Splines**: Offer local control and arbitrary $C^k$ continuity using a knot vector $U = \{u_0, u_1, \dots, u_m\}$ with Cox-de Boor basis functions. - **NURBS (Non-Uniform Rational B-Splines)**: Allow exact representation of conics (circles, ellipses, spheres) through control points weighted by weights $w_i$: $$\mathbf{S}(u, v) = \frac{\sum_{i=0}^n \sum_{j=0}^m N_{i,p}(u) N_{j,q}(v) w_{i,j} \mathbf{P}_{i,j}}{\sum_{i=0}^n \sum_{j=0}^m N_{i,p}(u) N_{j,q}(v) w_{i,j}}$$ --- ## 💡 3. Illumination Models, Shading, and Rendering ### 3.1 Empirical vs Physically Based Illumination (PBR) | Model | Fundamental Equation | Main Characteristics | | :--- | :--- | :--- | | **Classical Phong** | $I = k_a I_a + k_d I_d (\mathbf{L} \cdot \mathbf{N}) + k_s I_s (\mathbf{R} \cdot \mathbf{V})^n$ | Empirical, does not conserve energy, uses the ideal reflection vector $\mathbf{R}$. | | **Blinn-Phong** | $I = k_a I_a + k_d I_d (\mathbf{L} \cdot \mathbf{N}) + k_s I_s (\mathbf{H} \cdot \mathbf{N})^n$ | More efficient, uses the half-way vector $\mathbf{H} = \frac{\mathbf{L} + \mathbf{V}}{\|\mathbf{L} + \mathbf{V}\|}$. | | **PBR Cook-Torrance (Microfacet)** | $f_r(\mathbf{x}, \omega_i, \omega_o) = \frac{D(\mathbf{h}) F(\omega_i, \mathbf{h}) G(\omega_i, \omega_o, \mathbf{h})}{4 (\mathbf{n} \cdot \omega_i) (\mathbf{n} \cdot \omega_o)}$ | Physically plausible, energy-conserving, microfacet-based. | - **Cook-Torrance BRDF Terms**: 1. **Normal Distribution $D(\mathbf{h})$ (GGX / Trowbridge-Reitz)**: $$D_{GGX}(\mathbf{h}) = \frac{\alpha^2}{\pi \left( (\mathbf{n} \cdot \mathbf{h})^2 (\alpha^2 - 1) + 1 \right)^2}$$ 2. **Fresnel $F(\omega_i, \mathbf{h})$ (Schlick Approximation)**: $$F_{Schlick}(\theta) = F_0 + (1 - F_0) (1 - \cos\theta)^5$$ 3. **Geometry / Shadowing $G(\omega_i, \omega_o, \mathbf{h})$ (Smith GGX)**: $$G(\mathbf{n}, \mathbf{v}, \mathbf{l}) = G_1(\mathbf{n}, \mathbf{v}) G_1(\mathbf{n}, \mathbf{l}), \quad G_1(\mathbf{n}, \mathbf{v}) = \frac{2 (\mathbf{n} \cdot \mathbf{v})}{(\mathbf{n} \cdot \mathbf{v}) + \sqrt{\alpha^2 + (1-\alpha^2)(\mathbf{n} \cdot \mathbf{v})^2}}$$ ### 3.2 Kajiya's Rendering Equation (Global Ray Tracing) $$L_o(\mathbf{x}, \omega_o) = L_e(\mathbf{x}, \omega_o) + \int_{\Omega} f_r(\mathbf{x}, \omega_i, \omega_o) L_i(\mathbf{x}, \omega_i) (\mathbf{n} \cdot \omega_i) \, d\omega_i$$ - **Spatial Acceleration Algorithms**: BVH (Bounding Volume Hierarchy), Octrees, and KD-Trees with the Surface Area Heuristic (SAH). --- ## 🔍 4. Taxonomy of Computer Vision Metrics & Descriptors ### 4.1 Local Feature Detectors and Descriptors (Scott Krig Taxonomy) ``` Taxonomy of Visual Features: ├── Corner & Edge Detectors: │ ├── Spatial Gradient: Sobel, Prewitt, Scharr │ ├── Autocorrelation Eigenvalues: Harris Corner Detector, Shi-Tomasi (Good Features to Track) │ └── Accelerated Segment Tests: FAST (Features from Accelerated Segment Test), AGAST ├── Descriptors Based on Gradient Histograms: │ ├── SIFT (Scale-Invariant Feature Transform) - DoG (Difference of Gaussians), 128-dim vector │ ├── SURF (Speeded-Up Robust Features) - Box Filters and Integral Images, 64-dim vector │ └── HOG (Histogram of Oriented Gradients) - Dense detection of pedestrians/objects └── Binary Descriptors (Low Cost / Mobile): ├── BRIEF (Binary Robust Independent Elementary Features) ├── ORB (Oriented FAST and Rotated BRIEF) - Rotation invariant and noise resistant ├── BRISK (Binary Robust Invariant Scalable Keypoints) - Circular sampling pattern └── FREAK (Fast Retina Keypoint) - Sampling inspired by the human retina ``` ### 4.2 Similarity, Distance, and Image Quality Metrics - **Hamming Distance for Binary Descriptors**: $$D_H(\mathbf{a}, \mathbf{b}) = \text{popcount}(\mathbf{a} \oplus \mathbf{b})$$ - **PSNR (Peak Signal-to-Noise Ratio)**: $$\text{PSNR} = 10 \log_{10} \left( \frac{\text{MAX}_I^2}{\text{MSE}} \right), \quad \text{MSE} = \frac{1}{MN} \sum_{x=0}^{M-1} \sum_{y=0}^{N-1} [I(x,y) - K(x,y)]^2$$ - **SSIM (Structural Similarity Index Measure)**: $$\text{SSIM}(x, y) = \frac{(2\mu_x\mu_y + c_1)(2\sigma_{xy} + c_2)}{(\mu_x^2 + \mu_y^2 + c_1)(\sigma_x^2 + \sigma_y^2 + c_2)}$$ --- ## 🤖 5. Modern Computer Vision with PyTorch 2.0 ### 5.1 PyTorch 2.0 High-Performance Stack (`torch.compile`) - **TorchDynamo**: Captures Python execution graphs without modifying the model code. - **TorchInductor**: Compiler with high-performance C++/Triton code generation for NVIDIA GPUs. - **AOTAutograd**: Ahead-of-time tracing of the backpropagation graph for operator fusion. ```python import torch import torchvision.models as models # Vision Transformer model compiled with PyTorch 2.0 model = models.vit_b_16(weights=models.ViT_B_16_Weights.DEFAULT).cuda() model.eval() # TorchDynamo + TorchInductor optimization compiled_model = torch.compile(model, mode="max-autotune") with torch.inference_mode(): dummy_input = torch.randn(1, 3, 224, 224, device="cuda") output = compiled_model(dummy_input) ``` ### 5.2 State-of-the-Art Computer Vision Architectures 1. **Object Detection**: - **One-Stage**: YOLOv8 / YOLOv9 / RetinaNet (Focal Loss for class imbalance). - **Two-Stage**: Faster R-CNN with RPN (Region Proposal Network) and RoIAlign. - **Transformer-Based**: DETR (Detection Transformer) with bipartite matching via Hungarian Loss. 2. **Image Segmentation**: - **Semantic**: UNet, DeepLabV3+ (with Atrous Spatial Pyramid Pooling - ASPP). - **Instance / Panoptic**: Mask R-CNN, Segment Anything Model (SAM).