Database Management Systems Theory:

 CMSDSC509T/CMSMIN704T/CMSCOR404T:

Database Management Systems Theory: 45 Lectures

1. Introduction (4 Lectures)

Characteristics of database approach, data models, database system architecture and data

independence.

2. Entity Relationship(ER) Modeling (5 Lectures)

 Entity types, relationships, constraints.

3. Relation data model (15 Lectures)

Relational model concepts, relational constraints, relational algebra, SQL queries.

4. Database design (12 Lectures)

Mapping ER/EER model to relational database, functional dependencies,

Lossless decomposition, Normal forms (up to BCNF).

5. Transaction Processing (3 Lectures)

ACID properties, concurrency control.

6. File Structure and Indexing (6 Lectures)

Operations on files, File of Unordered and ordered records, overview of File organizations,

Indexing structures for files( Primary index, secondary index, clustering index), Multilevel

indexing using B and B+ trees.

Text Books

1. R. Elmasri, S.B. Navathe, Fundamentals of Database Systems 6th Edition, Pearson Education, 2010.

2. R. Ramakrishanan, J. Gehrke, Database Management Systems 3rd Edition, McGraw-Hill, 2002.

Books Recommended:

1. A. Silberschatz, H.F. Korth, S. Sudarshan, Database System Concepts 6th Edition, McGraw Hill,

2010.

2. R. Elmasri, S.B. Navathe Database Systems Models, Languages, Design and application

Programming, 6th Edition, Pearson Education, 2013.

HUFFMAN ALGORITHM ONLINE TOOL

Huffman Coding Visualizer

Interactive Step-by-Step Lossless Data Compression Tool

How Huffman Coding Works

Huffman Coding is a greedy algorithm used for lossless data compression. Instead of using a fixed-length code (like standard 8-bit ASCII) for every character, it assigns variable-length codes based on character frequencies:

• High-Frequency Characters: Assigned shorter binary codes (e.g., 2 or 3 bits).
• Low-Frequency Characters: Assigned longer binary codes.

Prefix Rule: No valid code is a prefix of another code. This allows the decoder to continuously parse a stream of bits without needing explicit separators between characters.

Input Text Huffman coding is a lossless data compression algorithm.

1. Character Frequencies

2. Compression Metrics & Detailed Math

Original Size (8-bit ASCII) 0 bits

Compressed Size 0 bits

Space Saved 0%

Encoded Bitstream

Character Codes Lookup Table

Character	Frequency	Assigned Huffman Code	Bit Length

3. Huffman Binary Tree Construction (Animated) Left = 0 Right = 1

Speed: Slow (1.5s) Normal (0.8s) Fast (0.3s)

Ready to build tree.

B+ TREE

B Tree

🌳 B-Tree Visualizer

⚡ Speed: Slow Normal Fast Instant

Maximum Degree: 3 4 5 6 7

Dynamic B-Tree Visualization

📋 Step-by-Step Operation

Ready to perform B-Tree operations...

Status: Ready

Image Morphing & Spatial Transformations

Image Morphing & Spatial Transformations

Gonzalez & Woods • DIP

According to Digital Image Processing by Gonzalez & Woods, image morphing belongs to the class of Geometric Spatial Transformations (Image Warping) combined with intensity interpolation. A spatial transformation modifies the spatial relationship between pixels in an image.

1. Two-Step Mapping Mechanism

A complete morphing process relies on two fundamental operations applied to image coordinates $(x, y)$:

• Spatial Coordinate Transformation (Warping): Mapping spatial coordinates $(x, y)$ to new coordinates $(x', y')$ using transformation equations.
• Intensity Interpolation (Gray-Level Mapping): Assigning pixel values to the newly mapped coordinates using methods like Nearest-Neighbor, Bilinear, or Bicubic Interpolation.

2. Affine & Matrix Transformations

Forward spatial mapping transforms coordinates via linear combination matrices:

// General Affine Transformation Matrix (Gonzalez & Woods)
[x' y' 1] = [x y 1] * T

T = | t₁₁ t₁₂ 0 | (Rotates, scales, shears, and translates)
| t₂₁ t₂₂ 0 |
| t₃₁ t₃₂ 1 |

3. Tie-Points & Mesh-Based Warping

When the transformation cannot be modeled globally by a single matrix, Tie-Points (Control Points) are established across quadrangle or triangular meshes (Delaunay Triangulation) over both images.

For a triangular region with vertices $(x_1, y_1), (x_2, y_2), (x_3, y_3)$, the mapped coordinates are uniquely determined using affine coefficient solvers:

x' = c₁x + c₂y + c₃
y' = c₄x + c₅y + c₆

// Solved via 3 non-collinear tie-points per triangle pair

4. Inverse Mapping vs. Forward Mapping

Mapping Type	Mechanism	Key Advantage / Disadvantage
Forward Mapping	Maps directly from source $(x, y)$ to destination $(x', y')$	Causes hole artifacts or overlap when multiple pixels map to one destination.
Inverse Mapping	Iterates target coordinates $(x', y')$ backward to source $(x, y)$	Guarantees every output pixel is filled via bilinear/bicubic interpolation.

5. Intensity Cross-Dissolving

Once both images are spatially warped to an intermediate control-point geometry at morph stage $t \in [0, 1]$, pixel intensities are combined:

f_morph(x, y, t) = (1 - t) · f_A(x_A', y_A') + t · f_B(x_B', y_B')

Notes Created By Bijan Krishna Paul Digital Image Processing (DIP) Syllabus

Image Morphing

Image Morphing Workstation

Digital Image Processing

Source Image (A)

Target Image (B)

Morph Progress 0%

1. Definition & Core Objective

Image Morphing is an advanced digital image processing technique that smoothly transforms a source image into a target image through a seamless visual transition. Unlike simple cross-fading, morphing combines spatial geometric deformation (warping) with color intensity blending (cross-dissolving) to preserve structural alignment during transition.

2. Comprehensive Step-by-Step Pipeline

1. Feature Specification & Point Mapping:
   Key structural control points (landmarks such as eyes, mouth contours, or corners) are specified on both Source Image $A$ and Target Image $B$.
2. Intermediate Mesh Generation:
   An intermediate feature point grid is calculated for time $t$ ($0 \le t \le 1$) using linear interpolation:
   P_intermediate = (1 - t) * P_source + t * P_target
3. Warping (Delaunay Triangulation / Splines):
   Both source and target images are geometrically distorted toward the intermediate shape using affine transformations or Thin-Plate Splines (TPS).
4. Cross-Dissolving (Color Interpolation):
   The warped images are color-blended pixel-by-pixel using weighted intensity interpolation to produce the final morph frame.

3. Mathematical Framework

The pixel-wise intensity blending equation at frame $t$ is expressed as:

// Cross-Dissolve / Intensity Interpolation Equation
I_m(x, y) = (1 - t) · I_A(x', y') + t · I_B(x'', y'')

// Where:
t = Morph Progress Parameter [0.0 ≤ t ≤ 1.0]
I_A(x', y') = Intensity at warped coordinates of Image A
I_B(x'', y'') = Intensity at warped coordinates of Image B

4. Key Differences: Morphing vs. Cross-Dissolving

Feature	Standard Cross-Dissolve	Image Morphing
Geometric Alignment	None (Static overlay)	Full feature alignment via warping
Visual Quality	Produces double-exposure / ghosting artifacts	Smooth, realistic structural transition
Computational Complexity	$O(N)$ — Very Low	$O(N \log N)$ to $O(N^2)$ — High (Triangulation/TPS)

5. Real-World Applications

• Entertainment & Visual Effects (VFX): Character transformations in movies, animation, and video games.
• Biometrics & Security: Facial age-progression modeling and landmark tracking validation.
• Medical Imaging: Visualizing anatomical changes over time (e.g., tumor growth or surgical outcome simulation).

Reference Textbook Notes

Image Morphing & (Gonzalez & Woods)

Access Notes →

Notes Created By Bijan Krishna Paul Computer Science & Engineering

Huffman Coding Algorithm

Huffman Coding Algorithm Lossless Compression

Overview: Huffman Coding is a greedy algorithm created by David Huffman in 1952 while working on his Ph.D. at MIT. It is an optimal prefix-free, variable-length statistical entropy encoding technique. The core principle dictates that symbols occurring more frequently in a source message receive shorter binary codes, while less frequent symbols receive longer binary codes.

Because it is prefix-free (no assigned binary codeword is a prefix of any other codeword), a bitstream can be decoded sequentially in a single pass without needing explicit boundaries or delimiters between symbols.

Algorithmic Complexity

Time Complexity

O(N log N) — Where N is the number of unique characters. Building the min-heap takes O(N), and extracting the minimum nodes N-1 times takes O(N log N).

Space Complexity

O(N) — Requires storage for the priority queue, leaf nodes, and internal tree structures representing the N unique symbols.

Core Algorithm Steps

1. Frequency Counting & Analysis:
   Scan the input stream to compute the frequency distribution of each distinct character or byte sequence.
2. Priority Queue Initialization:
   Create a leaf node for each symbol containing its character value and frequency count. Insert all leaf nodes into a Min-Heap (priority queue sorted by frequency).
3. Tree Construction (Greedy Approach):
   Iterate while the min-heap contains more than one node:
   • Pop the two lowest-frequency nodes (Node_1, Node_2).
   • Create a parent node with a combined frequency equal to Node_1.freq + Node_2.freq.
   • Set Node_1 as the left child and Node_2 as the right child.
   • Insert the new parent node back into the min-heap.
4. Bit Assignment & Dictionary Generation:
   Perform a Depth-First Search (DFS) starting from the root of the constructed Huffman Tree. Assign a bit value of 0 to every left branch and 1 to every right branch. The path from the root to any leaf node defines that symbol's unique binary code.

Detailed Worked Example

Launch Huffman Tree Generator

Input String: BCCABBDDAAEE (12 characters, 96 bits under standard 8-bit ASCII encoding)

Step 1: Calculate Frequency Table

• A: 3 occurrences (P = 3/12)
• B: 3 occurrences (P = 3/12)
• C: 2 occurrences (P = 2/12)
• D: 2 occurrences (P = 2/12)
• E: 2 occurrences (P = 2/12)

Step 2: Tree Synthesis Sequence

• Combine lowest nodes C (2) and D (2) → Internal Node [CD: 4]
• Combine lowest remaining E (2) and A (3) → Internal Node [EA: 5]
• Combine B (3) and [CD: 4] → Internal Node [BCD: 7]
• Combine [EA: 5] and [BCD: 7] → Root Node [12]

Step 3: Visual Huffman Tree Structure

[Root: 12] / \ (0) / \ (1) / \ [EA: 5] [BCD: 7] / \ / \ (0) / \ (1) (0)/ \ (1) / \ / \ E (2) A (3) B (3) [CD: 4] / \ (0) / \ (1) / \ C (2) D (2)

Step 4: Final Binary Encoding Dictionary

Symbol	Frequency	Huffman Code	Bit Length	Total Encoded Bits
E	2	00	2 bits	4 bits
A	3	01	2 bits	6 bits
B	3	10	2 bits	6 bits
C	2	110	3 bits	6 bits
D	2	111	3 bits	6 bits

Compression Ratio Achieved:

• Original Size (8-bit ASCII): 12 characters × 8 bits = 96 bits
• Compressed Huffman Size: 4 + 6 + 6 + 6 + 6 = 28 bits
• Space Reduction: (96 - 28) / 96 = 70.83% savings

Applications in Image Processing

In digital image processing, raw image data contains vast spatial redundancy. Huffman coding serves as the final, critical step in lossless and lossy compression formats (such as JPEG and PNG).

• Entropy Coding in the JPEG Pipeline:
  In JPEG compression, image blocks (8x8 pixels) are transformed using Discrete Cosine Transform (DCT) and then quantized. The resulting high-frequency coefficients contain long runs of zeroes. Huffman coding is executed on these final run-length pairs to store the image coefficients without further data loss.
• Handling Pixel Intensity Distribution:
  Images (like medical X-rays or astronomical photography) frequently exhibit dominant background shades. Instead of wasting 8 bits per grayscale pixel (0-255), Huffman coding assigns short 2 to 4-bit codes to dominant background pixel intensities, dramatically reducing raw image payload size.
• Integration with Run-Length Encoding (RLE):
  For lossy image routines, pixel coefficients are reordered in a Zig-Zag pattern to consolidate zero-value frequencies. RLE creates tuples of (run_length, value), which are subsequently mapped to optimized pre-defined or dynamic Huffman Tables.
• PNG Compression (DEFLATE Algorithm):
  PNG image formats use the DEFLATE compression engine. DEFLATE combines LZ77 (sliding window dictionary substitution) with dual dynamic Huffman trees—one tree for literal/length symbols and another for distance metrics—producing high compression ratios for graphics.

Key Takeaway: Huffman Coding achieves maximum efficiency when symbol probabilities are inverse powers of two (2^-1, 2^-2, 2^-3). For datasets with skewed distributions—like quantized image coefficients—it approaches Shannon's theoretical Entropy limit.

Notes Created By Bijan Krishna Paul Computer Science & Engineering

IMAGE PROCESSING

CMSDSC716T: Image Processing and Computer Vision Theory: 45 Lectures

CMSDSC716P: CLICK HERE FOR PRACTICAL USING OPENCV 

1. Introduction (4 Lectures)

Light, Brightness adaption and discrimination, Pixels, Coordinate conventions, Imaging Geometry,

Perspective Projection, Spatial Domain Filtering, Sampling and quantization.

2. Spatial Domain Filtering: (8 Lectures)

Intensity transformations, contrast stretching, histogram equalization, Correlation and convolution,

Smoothing filters, Sharpening filters, Gradient and Laplacian.

3. Filtering in the Frequency domain: (8 Lectures)

Hotelling Transform, Fourier Transforms and properties, FFT (Decimation in Frequency and

Decimation in Time Techniques), Convolution, Correlation, 2-D sampling, Discrete Cosine Transform,

Frequency domain filtering.

4. Image Restoration: (8 Lectures)

Basic Framework, 

Interactive Restoration, 

Image deformation and geometric transformations,

 image morphing, 

Restoration techniques,

 Noise characterization, 

Noise restoration filters,

 Adaptive filters,

Linear, 

Position invariant degradations, 

Estimation of Degradation functions, 

Restoration from projections.

5. Image Compression & Segmentation: (10 Lectures)

Encoder-Decoder model:

Types of redundancies:

Lossy and Lossless compression:

 Entropy of an

information source:

 Shannon's 1st Theorem:
 Huffman Coding- CLICK HERE,

 Arithmetic Coding: , 

Run length coding.

JPEG. 

Boundary detection based techniques

, Point, line detection,

 Edge detection,

 Edge linking, 

Local processing, 

Regional processing, 

Hough transform, 

Thresholding,

 Iterative thresholding.

6. Image Description (5 Lectures)

Introduction to Computer Vision: Comparison of Image Processing, Computer Vision and Computer

Graphics, What is Computer Vision - Low-level, Mid-level, High-level processing, Overview of Diverse

Computer Vision Applications: Document Image Analysis, Biometrics, Object Recognition, Object

Tracking, Gesture Recognition, Motion Estimation

 

Data Preprocessing

Data Preprocessing Core Framework

Data preprocessing is a foundational phase in data science that transforms raw, real-world data into a clean, integrated, and optimized format suitable for downstream mining algorithms.

3.2

Data Cleaning

Resolves data quality flaws by explicitly handling missing values and smoothing out noisy data structures to minimize system bias.

3.3

Data Integration

Consolidates multi-source schemas, eliminates entity redundancies, tracks value conflicts, and clears duplicate metadata profiles.

3.4

Data Reduction

Compresses volume and dimension footprints via mechanisms like Wavelets, PCA, Sampling, Histograms, and Data Cube Aggregation.

3.5

Transformation & Discretization

Standardizes ranges through data normalization, structural binning, and histogram cluster segmentations into actionable categorical intervals.

_________________

MEAN MEDIAN MODE

 

Statistical Analysis Summary

Central Tendency Metrics

I2.2 Suppose that the data for analysis includes the attribute age. The age values for the data tuples are (in increasing order) 13, 15, 16, 16, 19, 20, 20, 21, 22, 22, 25, 25, 25, 25, 30, 33, 33, 35, 35, 35, 35, 36, 40, 45, 46, 52, 70. (a) What is the mean of the data? What is the median? (b) What is the mode of the data?

Mean

29.96

Median

25

Mode

25, 35

Bimodal (Freq: 4)

Methodology & Calculations

Dataset Context

N = 27 observations (Sorted Age Attributes)

MEAN

Calculated by dividing the sum of all data elements by the total population size (N).

μ = 809 / 27 = 29.9629...

MEDIAN

Identified as the structural midpoint of the ordered dataset. For an odd population size (N = 27), the value aligns with position (N + 1) / 2.

Target Index: 14th position → 25

MODE

Determined by peak structural frequency. The values 25 and 35 share the highest recurring density within the sample profile.

Maximum Frequency: 4 occurrences each

import numpy as np

from scipy import stats

ages = [13, 15, 16, 16, 19, 20, 20, 21, 22, 22, 25, 25, 25, 25, 30, 33, 33, 35, 35, 35, 35, 36, 40, 45, 46, 52, 70]

# Total count

n = len(ages)

# Mean

mean_val = np.mean(ages)

# Median

median_val = np.median(ages)

# Mode

mode_result = stats.mode(ages, keepdims=True)

mode_val = mode_result.mode[0]

mode_count = mode_result.count[0]

# Find all modes just in case it is multimodal

from collections import Counter

counts = Counter(ages)

max_count = max(counts.values())

all_modes = [k for k, v in counts.items() if v == max_count]

print(f"Count: {n}")

print(f"Sum: {sum(ages)}")

print(f"Mean: {mean_val:.2f}")

print(f"Median: {median_val}")

print(f"Modes: {all_modes} with count {max_count}")