UNIT – 4

Supervised vs Unsupervised vs Reinforcement Learning

Criteria Supervised Unsupervised Reinforcement
Learning Learning Learning

Definition Learns from labeled Identifies patterns in Learns through

data unlabeled data interaction with
environment

Type of Data Labeled data Unlabeled data No predefined data

learn from
environment

Type of Classification, Clustering, Sequential decision-

Problems Regression Association making

Supervision Requires external No supervision No supervision, learns

supervision from feedback

Algorithms SVM, Decision K-Means, PCA, Q-learning, DQN,

Trees, Neural Autoencoders SARSA
Networks

Goal Predict outcomes Discover hidden Optimize actions for

accurately patterns maximum rewards

Applications Medical diagnosis, Customer Self-driving cars,

fraud detection segmentation, robotics, gaming
anomaly detection

Real-World Applications

Machine Learning Domain Examples

Type

Supervised Learning Healthcare Disease diagnosis like cancer detection

Finance Loan approval, credit risk assessment

NLP Sentiment analysis, text classification

Unsupervised E-commerce Product recommendation, customer
Learning segmentation

Cybersecurity Fraud detection, intrusion detection

Biology Gene classification, dimensionality

reduction

Reinforcement Autonomous Self-driving cars learning optimal driving

Learning Driving behavior

Robotics Training robots for automated assembly

tasks

Gaming AI-driven strategy games like AlphaGo

Choosing the Right Learning Approach

 Supervised Learning: When labeled data is available for prediction tasks like
spam filtering, stock price forecasting.

 Unsupervised Learning: When exploring data structures without predefined

labels like customer segmentation, anomaly detection.

 Reinforcement Learning: When decision-making is required in a dynamic

environment like game AI, robotics, self-driving cars.
Clustering in Machine Learning
Clustering is an unsupervised machine learning technique that groups similar data
points together into clusters based on their characteristics, without using any labeled
data. The objective is to ensure that data points within the same cluster are more
similar to each other than to those in di erent clusters, enabling the discovery of
natural groupings and hidden patterns in complex datasets.

 Goal: Discover the natural grouping or structure in unlabeled data without

predefined categories.

 How: Data points are assigned to clusters based on similarity or distance

measures.

 Similarity Measures: Can include Euclidean distance, cosine similarity or other

metrics depending on data type and clustering method.

 Output: Each group is assigned a cluster ID, representing shared

characteristics within the cluster.

For example, if we have customer purchase data, clustering can group customers with
similar shopping habits. These clusters can then be used for targeted marketing,
personalized recommendations or customer segmentation.

Types of Clustering

1. Hard Clustering
2. Soft Clustering

Types of Clustering Methods

Clustering methods can be classified on the basis of how they form clusters,

1. Centroid-based Clustering (Partitioning Methods)

Centroid-based clustering organizes data points around central prototypes called

centroids, where each cluster is represented by the mean (or medoid) of its members.
The number of clusters is specified in advance and the algorithm allocates points to the
nearest centroid, making this technique e icient for spherical and similarly sized
clusters but sensitive to outliers and initialization.

Algorithms:

 K-means: Iteratively assigns points to nearest centroid and recalculates

centroids to minimize intra-cluster variance.

 K-medoids: Similar to K-means but uses actual data points (medoids) as

centers, robust to outliers.
Pros:

 Fast and scalable for large datasets.

 Simple to implement and interpret.

Cons:

 Requires pre-knowledge of kk.

 Sensitive to initialization and outliers.

 Not suitable for non-spherical clusters.

2. Density-based Clustering (Model-based Methods)

Density-based clustering defines clusters as contiguous regions of high data density

separated by areas of lower density. This approach can identify clusters of arbitrary
shapes, handles noise well and does not require predefining the number of clusters,
though its e ectiveness depends on chosen density parameters.

Algorithms:

 DBSCAN (Density-Based Spatial Clustering of Applications with Noise): Groups

points with su icient neighbors; labels sparse points as noise.

 OPTICS (Ordering Points To Identify Clustering Structure): Extends DBSCAN to

handle varying densities.

Pros:

 Handles clusters of varying shapes and sizes.

 Does not require cluster count upfront.

 E ective in noisy datasets.

Cons:

 Di icult to choose parameters like epsilon and min points.

 Less e ective for varying density clusters (except OPTICS).

3. Connectivity-based Clustering (Hierarchical Clustering)

Connectivity-based (or hierarchical) clustering builds nested groupings of data by

evaluating how data points are connected to their neighbors. It creates a dendrogram a
tree-like structure that reflects relationships at various granularity levels and does not
require specifying cluster numbers in advance, but can be computationally intensive.

Approaches:
  Agglomerative (Bottom-up): Start with each point as a cluster; iteratively merge
closest clusters.

 Divisive (Top-down): Start with one cluster; iteratively split into smaller clusters.

Pros:

 Provides a full hierarchy, easy to visualize.

 No need to specify number of clusters upfront.

Cons:

 Computationally intensive for large datasets.

 Merging/splitting decisions are irreversible.

4. Distribution-based Clustering

Distribution-based clustering assumes data is generated from a mixture of probability

distributions, such as Gaussian distributions and assigns points to clusters based on
statistical likelihood. This method supports clusters with flexible shapes and overlaps,
but usually requires specifying the number of distributions.

Algorithm:

 Gaussian Mixture Model (GMM): Fits data as a weighted mixture of Gaussian

distributions; assigns data points based on likelihood.

Pros:

 Flexible cluster shapes.

 Provides probabilistic memberships.

 Suitable for overlapping clusters.

Cons:

 Requires specifying number of components.

 Computationally more expensive.

 Sensitive to initialization.

5. Fuzzy Clustering

Fuzzy clustering extends traditional methods by allowing each data point to belong to
multiple clusters with varying degrees of membership. This approach captures
ambiguity and soft boundaries in data and is particularly useful when the clusters
overlap or boundaries are not clear-cut.
Algorithm:

 Fuzzy C-Means: Similar to K-means but with fuzzy memberships updated

iteratively.

Pros:

 Models data ambiguity explicitly.

 Useful for complex or imprecise data.

Cons:

 Choosing fuzziness parameter can be tricky.

 Computational overhead compared to hard clustering.

Use Cases

 Customer Segmentation: Grouping customers based on behavior or

demographics for targeted marketing and personalized services.

 Anomaly Detection: Identifying outliers or fraudulent activities in finance,

network security and sensor data.

 Image Segmentation: Dividing images into meaningful parts for object

detection, medical diagnostics or computer vision tasks.

 Recommendation Systems: Clustering user preferences to recommend

movies, products or content tailored to di erent groups.

 Market Basket Analysis: Discovering products frequently bought together to

optimize store layouts and promotions.

K means Clustering
K-Means Clustering groups similar data points into clusters without needing labeled
data. It is used to uncover hidden patterns when the goal is to organize data based on
similarity.

 Helps identify natural groupings in unlabeled datasets

 Works by grouping points based on distance to cluster centers

 Commonly used in customer segmentation, image compression, and pattern

discovery

 Useful when you need structure from raw, unorganized data

Working of K-Means Clustering

Suppose we are given a data set of items with certain features and values for these
features like a vector. The task is to categorize those items into groups. To achieve this
we will use the K-means algorithm. "𝑘" represents the number of groups or clusters we
want to classify our items into.

The algorithm will categorize the items into "𝑘" groups or clusters of similarity. To
calculate that similarity we will use the Euclidean distance as a measurement. The
algorithm works as follows:

1. Initialization: We begin by randomly selecting k cluster centroids.

2. Assignment Step: Each data point is assigned to the nearest centroid, forming
clusters.

3. Update Step: After the assignment, we recalculate the centroid of each cluster
by averaging the points within it.

4. Repeat: This process repeats until the centroids no longer change or the
maximum number of iterations is reached.

The goal is to partition the dataset into 𝑘 clusters such that data points within each
cluster are more similar to each other than to those in other clusters.

Selecting the right number of clusters is important for meaningful segmentation to do

this we use Elbow Method for optimal value of k in KMeans which is a graphical tool
used to determine the optimal number of clusters (k) in K-means.

Why Use K-Means Clustering?

K-Means is popular in a wide variety of applications due to its simplicity, e iciency and
e ectiveness. Here’s why it is widely used:

1. Data Segmentation: One of the most common uses of K-Means is segmenting

data into distinct groups. For example, businesses use K-Means to group
customers based on behavior, such as purchasing patterns or website
interaction.

2. Image Compression: K-Means can be used to reduce the complexity of images

by grouping similar pixels into clusters, e ectively compressing the image. This is
useful for image storage and processing.

3. Anomaly Detection: K-Means can be applied to detect anomalies or outliers by

identifying data points that do not belong to any of the clusters.
 4. Document Clustering: In natural language processing (NLP), K-Means is used to
group similar documents or articles together. It’s often used in applications like
recommendation systems or news categorization.

5. Organizing Large Datasets: When dealing with large datasets, K-Means can
help in organizing the data into smaller, more manageable chunks based on
similarities, improving the e iciency of data analysis.

Challenges with K-Means Clustering

K-Means algorithm has the following limitations:

 Choosing the Right Number of Clusters (𝑘): One of the biggest challenges is
deciding how many clusters to use.

 Sensitive to Initial Centroids: The final clusters can vary depending on the
initial random placement of centroids.

 Non-Spherical Clusters: K-Means assumes that the clusters are spherical and
equally sized. This can be a problem when the actual clusters in the data are of
di erent shapes or densities.

 Outliers: K-Means is sensitive to outliers, which can distort the centroid and,
ultimately, the clusters.

Gaussian Mixture Model

A Gaussian Mixture Model (GMM) is a probabilistic model that assumes data points are
generated from a mixture of several Gaussian (normal) distributions with unknown
parameters. Unlike hard clustering methods such as K-Means which assign each point
to a single cluster based on the closest centroid, GMM performs soft clustering by
assigning each point a probability of belonging to multiple clusters.

Working of GMM

Each cluster corresponds to a Gaussian distribution. For a given data point 𝑥 of

belonging to a cluster. GMM computes the probability it belongs to each cluster k:
where:

 𝑧 =k is a latent variable indicating which Gaussian the point belongs to.

 𝜋 is the mixing probability of the k-th Gaussian.

 𝒩(𝑥 ∣ 𝜇 , Σ )is the Gaussian distribution with mean 𝜇 and covariance Σ

Next we need to calculate the overall likelihood of observing a data point 𝑥 under all
Gaussians. This is achieved by summing over all possible clusters (Gaussians) for each
point:

where:

𝑃(𝑥 ) is the overall likelihood of observing the data point 𝑥 .

Classification
Classification is a supervised machine learning technique used to predict labels or
categories based on input data. The goal is to assign each data point to a predefined
class, such as spam vs. non-spam emails or diseased vs. healthy patients.

For example, a classification model might be trained on dataset of images labeled as

either dogs or cats and it can be used to predict the class of new and unseen images as
dogs or cats based on their features such as colour, texture or shape.

Examples of Machine Learning Classification in Real Life

Classification algorithms are widely used in many real-world applications across

various domains, including:

 Email spam filtering: Filters our emails into spam or not spam based on email
content.

 Credit risk assessment: Algorithms predict whether a loan applicant is likely to

default by analyzing factors such as credit score, income and loan history. This
helps banks make informed lending decisions and minimize financial risk.

 Medical diagnosis: Machine learning models classify whether a patient has a

certain condition like cancer or diabetes based on medical data such as test
results, symptoms and patient history. This aids doctors in making quicker, more
accurate diagnoses, improving patient care.
  Image classification : Applied in fields such as facial recognition, autonomous
driving and medical imaging.

 Sentiment analysis: Determining whether the sentiment of a piece of text is

positive, negative or neutral. Businesses use this to understand customer
opinions, helping to improve products and services.

 Fraud detection : Algorithms detect fraudulent activities by analyzing

transaction patterns and identifying anomalies crucial in protecting against
credit card fraud and other financial crimes.

 Recommendation systems : Used to recommend products or content based on

past user behavior, such as suggesting movies on Netflix or products on Amazon.
This personalization boosts user satisfaction and sales for businesses.

Naive Bayes Classifiers

Naive Bayes is a machine learning classification algorithm that predicts the category of
a data point using probability. It assumes that all features are independent of each
other. Naive Bayes performs well in many real-world applications such as spam
filtering, document categorization and sentiment analysis.

Key Features of Naive Bayes Classifiers

The main idea behind the Naive Bayes classifier is to use Bayes' Theorem to classify
data based on the probabilities of di erent classes given the features of the data. It is
used mostly in high-dimensional text classification

 The Naive Bayes Classifier is a simple probabilistic classifier and it has very few
number of parameters which are used to build the ML models that can predict at
a faster speed than other classification algorithms.

 It is a probabilistic classifier because it assumes that one feature in the model is

independent of existence of another feature. In other words, each feature
contributes to the predictions with no relation between each other.

 Naive Bayes Algorithm is used in spam filtration, Sentimental analysis,

classifying articles and many more.

Why it is Called Naive Bayes?

It is named as "Naive" because it assumes the presence of one feature does not a ect
other features. The "Bayes" part of the name refers to its basis in Bayes’ Theorem.
Assumption of Naive Bayes

The fundamental Naive Bayes assumption is that each feature makes an:

 Feature independence: This means that when we are trying to classify

something, we assume that each feature (or piece of information) in the data
does not a ect any other feature.

 Continuous features are normally distributed: If a feature is continuous, then

it is assumed to be normally distributed within each class.

 Discrete features have multinomial distributions: If a feature is discrete, then

it is assumed to have a multinomial distribution within each class.

 Features are equally important: All features are assumed to contribute equally
to the prediction of the class label.

 No missing data: The data should not contain any missing values.

Introduction to Bayes' Theorem

Bayes’ Theorem provides a principled way to reverse conditional probabilities. It is

defined as:
𝑃(𝑋 ∣ 𝑦) ⋅ 𝑃(𝑦)
𝑃(𝑦 ∣ 𝑋) =
𝑃(𝑋)

Where:

 𝑃(𝑦 ∣ 𝑋): Posterior probability, probability of class 𝑦 given features 𝑋

 𝑃(𝑋 ∣ 𝑦): Likelihood, probability of features 𝑋 given class 𝑦

 𝑃(𝑦): Prior probability of class 𝑦

 𝑃(𝑋): Marginal likelihood or evidence

Advantages of Naive Bayes Classifier

 Easy to implement and computationally e icient.

 E ective in cases with a large number of features.

 Performs well even with limited training data.

 It performs well in the presence of categorical features.

 For numerical features data is assumed to come from normal distributions

Disadvantages of Naive Bayes Classifier

  Assumes that features are independent, which may not always hold in real-world
data.

 Can be influenced by irrelevant attributes.

 May assign zero probability to unseen events, leading to poor generalization.

Applications of Naive Bayes Classifier

 Spam Email Filtering: Classifies emails as spam or non-spam based on

features.

 Text Classification: Used in sentiment analysis, document categorization, and

topic classification.

 Medical Diagnosis: Helps in predicting the likelihood of a disease based on

symptoms.

 Credit Scoring: Evaluates creditworthiness of individuals for loan approval.

 Weather Prediction: Classifies weather conditions based on various factors.

KNN vs ANN
Criteria KNN ANN

Accuracy Known for precision, Prioritizes speed over exact precision,

identifies 'k' closest approximates nearest neighbors with
neighbors for high slight accuracy compromise
accuracy

Speed Slower due to Faster searches through approximation

exhaustive search, techniques, suitable for real-time
especially with large applications
datasets

Computational Requires significant Designed for e iciency, reduces

Resources computational computational load through indexing
resources, especially and approximation
with large datasets

Scalability Challenges in scaling Handles larger datasets e ectively,

due to high scalable
computational
demands
Use Cases Best for tasks requiring Ideal for scenarios needing speed and
high accuracy (e.g., scalability (e.g., search engines,
medical diagnosis, recommendation systems)
financial forecasting)

Learning Instance-based Not applicable in the traditional sense;

Approach learning, makes ANN is an optimization technique rather
predictions based on than a learning method
proximity without
building a model

Handling of Handles non-linearity Capable of capturing complex non-

Non-linearity naturally based on linear relationships, but this is more
local data patterns relevant to neural networks rather than
ANN specifically[Note: This point is
more about neural networks than ANN,
but included for completeness]

Advantages and Disadvantages of ANN

Advantages and Disadvantages of ANN

 Learning Complex Patterns: ANNs can model complex relationships and

patterns in data.

 Adaptability: They can adapt to new data through training, improving their
performance over time.

 Versatility: ANNs can be applied to various tasks, including classification,

regression, and pattern recognition.

Disadvantages of ANN

 Computationally Intensive: Training ANNs can be resource-heavy and time-

consuming, requiring significant computational power.

 Overfitting Risk: ANNs can overfit the training data, especially with insu icient
regularization or too many parameters.

 Complexity: Designing and tuning ANN architectures can be complex and

requires expertise.

Advantages and Disadvantages of KNN

Advantages of KNN

 Simplicity: KNN is straightforward and easy to implement, with minimal training

time.
  No Assumptions: It makes no assumptions about the underlying data
distribution, making it versatile for various types of data.

 Adaptability: The algorithm can easily adapt to changes in the data, as it does
not rely on a fixed model.

Disadvantages of KNN

 Computationally Expensive: KNN requires significant computation during the

prediction phase, especially with large datasets.

 Sensitive to Noise: The algorithm can be sensitive to noisy data and irrelevant
features.

 Choice of K and Distance Metric: The performance of KNN is highly dependent

on the choice of K and the distance metric, which can be challenging to optimize.

When to Use KNN vs ANN

When to Use KNN

 Small to Moderate-Sized Datasets: KNN is suitable for datasets where

computational resources and memory are not significant limitations.

 Precise Similarity Search: When precise similarity search is required, and

computational time is not a critical factor.

When to Use ANN

 Large Datasets: ANN is more appropriate for larger datasets or high-

dimensional spaces where computational e iciency is crucial, even if the results
are slightly approximate.

 High-Dimensional Data: Use cases like large-scale searches of images, audio,

and text, real-time content feed generation, recommendation engines, anomaly
detection, and more benefit from ANN.

Dimensionality Reduction
When working with machine learning models, datasets with too many features can
cause issues like slow computation and overfitting. Dimensionality reduction helps to
reduce the number of features while retaining key information. It converts high-
dimensional data into a lower-dimensional space while preserving important details.

For example, when you are building a model to predict house prices with features like
bedrooms, square footage and location. If you add too many features such as room
condition or flooring type, the dataset becomes large and complex.
How Dimensionality Reduction Works?

Lets understand how dimensionality Reduction is used with the help of example.
Imagine a dataset where each data point exists in a 3D space defined by axes X, Y and Z.
If most of the data variance occurs along X and Y then the Z-dimension may contribute
very little to understanding the structure of the data.

 Before Reduction we can see that data exist in 3D (X,Y,Z). It has high redundancy
and Z contributes little meaningful information

 On the right after reducing the dimensionality the data is represented in lower-
dimensional spaces. The top plot (X-Y) maintains the meaningful structure while
the bottom plot (Z-Y) shows that the Z-dimension contributed little useful
information.

This process makes data analysis more e icient hence improving computation speed
and visualization while minimizing redundancy

Dimensionality Reduction Techniques

Dimensionality reduction techniques can be broadly divided into two categories:

1. Feature Selection

Feature selection chooses the most relevant features from the dataset without altering
them. It helps remove redundant or irrelevant features, improving model e iciency.
Some common methods are:

 Filter methods rank the features based on their relevance to the target variable.

 Wrapper methods use the model performance as the criteria for selecting
features.
  Embedded methods combine feature selection with the model training process.

2. Feature Extraction

Feature extraction involves creating new features by combining or transforming the

original features. These new features retain most of the dataset’s important information
in fewer dimensions. Common feature extraction methods are:

1. Principal Component Analysis (PCA): Converts correlated variables into

uncorrelated principal components hence reducing dimensionality while
maintaining as much variance as possible enabling more e icient analysis.

2. Missing Value Ratio: Variables with missing data beyond a set threshold are
removed, improving dataset reliability.

3. Backward Feature Elimination: Starts with all features and removes the least
significant ones in each iteration. The process continues until only the most
impactful features remain, optimizing model performance.

4. Forward Feature Selection: It begins with one feature, adds others

incrementally and keeps those improving model performance.

5. Random Forest: Random forest uses decision trees to evaluate feature

importance, automatically selecting the most relevant features without the need
for manual coding, enhancing model accuracy.

6. Factor Analysis: Groups variables by correlation and keeps the most relevant
ones for further analysis.

7. Independent Component Analysis (ICA): Identifies statistically independent

components, ideal for applications like ‘blind source separation’ where
traditional correlation-based methods fall short.

Real World Use Case

Dimensionality reduction plays a important role in many real-world applications such

as text categorization, image retrieval, gene expression analysis and more. Here are a
few examples:

1. Text Categorization: With vast amounts of online data dimensionality reduction

helps classify text documents into predefined categories by reducing the feature
space like word or phrase features while maintaining accuracy.

2. Image Retrieval: As image data grows indexing based on visual content like
color, texture, shape rather than just text descriptions has become essential.
This allows for better retrieval of images from large databases.
 3. Gene Expression Analysis: Dimensionality reduction accelerates gene
expression analysis help to classify samples like leukemia by identifying key
features, improve both speed and accuracy.

4. Intrusion Detection: In cybersecurity dimensionality reduction helps analyze

user activity patterns to detect suspicious behaviors and intrusions by
identifying optimal features for network monitoring.

Advantages

As seen earlier high dimensionality makes models ine icient. Let's now summarize the
key advantages of reducing dimensionality.

 Faster Computation: With fewer features machine learning algorithms can

process data more quickly. This results in faster model training and testing which
is particularly useful when working with large datasets.

 Better Visualization: As we saw in the earlier figure reducing dimensions makes

it easier to visualize data and reveal hidden patterns.

 Prevent Overfitting: With few features models are less likely to memorize the
training data and overfit. This helps the model generalize better to new, unseen
data improve its ability to make accurate predictions.

Disadvantages

 Data Loss & Reduced Accuracy: Some important information may be lost
during dimensionality reduction and a ect model performance.

 Choosing the Right Components: Deciding how many dimensions to keep is

di icult as keeping too few may lose valuable information while keeping too
many can led to overfitting.

Di erence between PCA, LDA, ICA.

Feature PCA (Principal LDA (Linear ICA (Independent
Component Discriminant Component
Analysis) Analysis) Analysis)

Type Unsupervised Supervised Unsupervised signal

dimensionality dimensionality separation technique
reduction reduction

Goal Maximize variance Maximize class Find statistically

and find principal separability independent
components components
 Requires Class No Yes No
Labels?

Output Orthogonal Linear Independent (non-

Components (uncorrelated) discriminants Gaussian)
components

Key Data with maximum Classes are Source signals are

Assumption variance is linearly separable independent & non-
meaningful Gaussian

When Useful Noise reduction, Classification Blind source

visualization problems separation (e.g.,
separating mixed
voices)

Typical Use Compression, Face recognition, Audio source

Cases exploratory analysis, classification separation, EEG
preprocessing signal processing

Noise Good Moderate Depends on method

Handling

Application General ML, data Supervised ML Signal processing,

Domain preprocessing classification biomedical data

Non-Parametric Density Estimation Method in ML

Non-parametric methods: Similar inputs have similar outputs. These are also called
instance-based or memory-based learning algorithms. There are 4 non-parametric
density estimation methods:

1. Histogram Estimator

2. Naive Estimator

3. Kernel Density Estimator (KDE)

4. KNN estimator (K - Nearest Neighbor Estimator)

Histogram Estimator

It is the oldest and the most popular method used to estimate the density, where the
input space is divided into equal-sized intervals called bins.
Naive Estimator

Unlike the Histogram estimator, the Naive estimator does not use the concept of origin.
There is no assumption of choosing the origin. The density of the sample depends on
the neighbouring training samples.

Kernel Density Estimator (KDE)

Kernel estimator is used to smoothen the probability distribution function (pdf)

and cumulative distribution function (CDF) graphics. The kernel is nothing but a
weight. Gaussian Kernel is the most popular kernel

K - Nearest Neighbor Estimator (KNN Estimator)

Unlike the previous methods of fixing the bin width h, in this estimation, we fix the value
of nearest neighbors k. The density of a sample depends on the value of k and the
distance of the kth nearest neighbor from the sample. This is close enough to the Kernel
estimation method.

Background Subtraction
Background subtraction is a core computer vision technique used to separate moving
foreground from the static background.

For Example: Imagine a security camera facing your front yard. Most of the view stays
the same (house, trees, pavement) but sometimes something changes a passing car or
a wandering cat. Background subtraction spots these changes by modeling static
background and comparing each new frame against it.

This technique is extremely useful for object tracking, motion detection and
surveillance systems.

How it works

 Background initialization: The process starts by creating a background model.

This can be done by analyzing a fixed number of initial frames, assuming they are
stationary, to establish a baseline of the scene.

 Foreground detection: Each subsequent frame is compared to the background

model. Any pixel that di ers significantly from the model is identified as part of
the foreground.

 Background maintenance: To handle changes in the scene, such as lighting

variations or the appearance of long-term stationary objects, the background
model is continuously updated over time.

Key concepts and challenges

  Foreground mask: The output is a binary image where pixels belonging to
moving objects are marked as foreground (e.g., white) and the background is
marked as background (e.g., black).

 Challenges:

o Shadows: Shadows cast by moving objects are often detected as part of

the foreground, requiring additional algorithms for shadow detection.

o Lighting changes: Dynamic changes in lighting can cause the

background model to misinterpret parts of the scene, necessitating
adaptive models.

o Background changes: Stationary objects that appear later in the video or

long-term background variations can be di icult to handle without proper
model maintenance.

Background Modeling
Background modeling in computer vision is a technique to create a model of a static
scene to distinguish moving objects (foreground) from the background in video
sequences. This is a fundamental step in tasks like moving object detection and
tracking, and it involves initializing a background model, detecting foreground objects
by comparing frames to the model, and updating the model over time. It is crucial for
applications like surveillance, robotics, and video analysis.

How it works

 Initialization: A model of the static background is created, often assuming the

background is stationary.

 Foreground Detection: The current video frame is compared to the background

model. Pixels that are significantly di erent are identified as potential foreground
objects.

 Background Update: The model is updated over time to account for changes,
such as lighting variations, or to incorporate new objects that have become
static.

Key challenges

 Dynamic backgrounds: Scenes with changes like waving trees, water, or lighting
variations can be di icult to model.

 Illumination changes: Shifts in lighting can make it hard to di erentiate between

a static background and a moving object.
  Computational e iciency: Many applications require real-time performance,
which means algorithms must be e icient and have low memory requirements.

Common approaches

 Statistical models: These methods model background pixels using statistical

distributions, such as a single Gaussian, a mixture of Gaussians, or Kernel
Density Estimation.

 Corner-based methods: These techniques use corner features to create a

sparse background model, which can be more computationally and memory
e icient.

 Texture-based methods: These algorithms analyze the texture of the

background using methods like Block Truncation Coding to better handle
illumination changes.

 Deep learning: More recent approaches use deep neural networks, such as
those utilizing convolutional layers and other advanced architectures, for more
accurate background modeling.

Optical Flow
Optical flow in computer vision is a technique that estimates the motion of pixels
between consecutive video frames by calculating a vector for each pixel that indicates
its direction and speed of movement. It is based on the brightness constancy
assumption, which states that pixel brightness remains constant over time, and is used
for tasks like motion detection, tracking, and image stabilization.

Key challenges

 Aperture problem: If the image region is a straight edge, the motion is only
constrained to be perpendicular to that edge, leading to ambiguity in determining
the exact motion vector.

 Lighting changes: Illumination changes, shadows, and noise can violate the
brightness constancy assumption, a ecting accuracy.

Applications

 Motion detection and tracking: Identifying and following moving objects in a

video.

 Image stabilization: Correcting for camera shake in shaky videos.

  Image segmentation: Separating an image into di erent regions based on
motion.

 Robotics and navigation: Using sensors to determine motion, such as in an

optical mouse or drone.

 Computer vision and AI: In applications like CapCut, optical flow can be used
to generate high-quality slow-motion e ects.

KLT
KLT (Kanade-Lucas-Tomasi) optical flow is a method for tracking features in an image
sequence by assuming that the motion of a point is constant in a local neighbourhood.
It is a sparse optical flow method that finds the motion for a selected set of points,
typically corners, and is more robust to image noise than point-wise methods because
it uses a local neighborhood to solve for the motion vector.

How it works

 Feature selection: First, a set of features (usually "good features to track," like
corners) is detected in the initial frame.

 Local neighborhood assumption: For each selected point, the method

assumes that the flow is constant in the small window around it.

 Brightness constancy assumption: It also assumes that the intensity of a pixel

remains constant over a short period, meaning there is little change in position.

 Least squares minimization: The algorithm then solves the optical flow
equations for all pixels in that local neighborhood using the least squares
criterion to find the best estimate for the motion vector of the central feature
point.

 Tracking: The process is repeated for each subsequent frame to track the
features across the video sequence.

Key characteristics

 Sparse: KLT tracks only a limited number of points, not every pixel in the image,
making it computationally e icient.

 Local: It operates on a local window around a feature, which can make it less
sensitive to uniform regions where flow information cannot be determined.
  Robust: By using a local neighborhood and solving the problem with least
squares, it becomes less sensitive to image noise compared to individual pixel
methods.

 Feature-based: It is a feature tracker, so it relies on good features to track, such

as corners, to start with.

Applications

 Object tracking in videos

 Video stabilization

 Structural displacement measurement

 Robotics and autonomous navigation