Category: Subjects

Principal Component Analysis | Dimension Reduction

Pattern Recognition

Dimension Reduction-

 

In pattern recognition, Dimension Reduction is defined as-

  • It is a process of converting a data set having vast dimensions into a data set with lesser dimensions.
  • It ensures that the converted data set conveys similar information concisely.

 

Example-

 

Consider the following example-

  • The following graph shows two dimensions x1 and x2.
  • x1 represents the measurement of several objects in cm.
  • x2 represents the measurement of several objects in inches.

 

 

In machine learning,

  • Using both these dimensions convey similar information.
  • Also, they introduce a lot of noise in the system.
  • So, it is better to use just one dimension.

 

Using dimension reduction techniques-

  • We convert the dimensions of data from 2 dimensions (x1 and x2) to 1 dimension (z1).
  • It makes the data relatively easier to explain.

 

 

Benefits-

 

Dimension reduction offers several benefits such as-

  • It compresses the data and thus reduces the storage space requirements.
  • It reduces the time required for computation since less dimensions require less computation.
  • It eliminates the redundant features.
  • It improves the model performance.

 

Dimension Reduction Techniques-

 

The two popular and well-known dimension reduction techniques are-

 

 

  1. Principal Component Analysis (PCA)
  2. Fisher Linear Discriminant Analysis (LDA)

 

In this article, we will discuss about Principal Component Analysis.

 

Principal Component Analysis-

 

  • Principal Component Analysis is a well-known dimension reduction technique.
  • It transforms the variables into a new set of variables called as principal components.
  • These principal components are linear combination of original variables and are orthogonal.
  • The first principal component accounts for most of the possible variation of original data.
  • The second principal component does its best to capture the variance in the data.
  • There can be only two principal components for a two-dimensional data set.

 

PCA Algorithm-

 

The steps involved in PCA Algorithm are as follows-

 

Step-01: Get data.

Step-02: Compute the mean vector (µ).

Step-03: Subtract mean from the given data.

Step-04: Calculate the covariance matrix.

Step-05: Calculate the eigen vectors and eigen values of the covariance matrix.

Step-06: Choosing components and forming a feature vector.

Step-07: Deriving the new data set.

 

PRACTICE PROBLEMS BASED ON PRINCIPAL COMPONENT ANALYSIS-

 

Problem-01:

 

Given data = { 2, 3, 4, 5, 6, 7 ; 1, 5, 3, 6, 7, 8 }.

Compute the principal component using PCA Algorithm.

 

OR

 

Consider the two dimensional patterns (2, 1), (3, 5), (4, 3), (5, 6), (6, 7), (7, 8).

Compute the principal component using PCA Algorithm.

 

OR

 

Compute the principal component of following data-

CLASS 1

X = 2 , 3 , 4

Y = 1 , 5 , 3

CLASS 2

X = 5 , 6 , 7

Y = 6 , 7 , 8

 

Solution-

 

We use the above discussed PCA Algorithm-

 

Step-01:

 

Get data.

The given feature vectors are-

  • x1 = (2, 1)
  • x2 = (3, 5)
  • x3 = (4, 3)
  • x4 = (5, 6)
  • x5 = (6, 7)
  • x6 = (7, 8)

 

 

Step-02:

 

Calculate the mean vector (µ).

 

Mean vector (µ)

= ((2 + 3 + 4 + 5 + 6 + 7) / 6, (1 + 5 + 3 + 6 + 7 + 8) / 6)

= (4.5, 5)

 

Thus,

 

Step-03:

 

Subtract mean vector (µ) from the given feature vectors.

  • x1 – µ = (2 – 4.5, 1 – 5) = (-2.5, -4)
  • x2 – µ = (3 – 4.5, 5 – 5) = (-1.5, 0)
  • x3 – µ = (4 – 4.5, 3 – 5) = (-0.5, -2)
  • x4 – µ = (5 – 4.5, 6 – 5) = (0.5, 1)
  • x5 – µ = (6 – 4.5, 7 – 5) = (1.5, 2)
  • x6 – µ = (7 – 4.5, 8 – 5) = (2.5, 3)

 

Feature vectors (xi) after subtracting mean vector (µ) are-

 

 

Step-04:

 

Calculate the covariance matrix.

Covariance matrix is given by-

 

 

Now,

 

 

Now,

Covariance matrix

= (m1 + m2 + m3 + m4 + m5 + m6) / 6

 

On adding the above matrices and dividing by 6, we get-

 

 

Step-05:

 

Calculate the eigen values and eigen vectors of the covariance matrix.

λ is an eigen value for a matrix M if it is a solution of the characteristic equation |M – λI| = 0.

So, we have-

 

 

From here,

(2.92 – λ)(5.67 – λ) – (3.67 x 3.67) = 0

16.56 – 2.92λ – 5.67λ + λ2 – 13.47 = 0

λ2 – 8.59λ + 3.09 = 0

 

Solving this quadratic equation, we get λ = 8.22, 0.38

Thus, two eigen values are λ1 = 8.22 and λ2 = 0.38.

 

Clearly, the second eigen value is very small compared to the first eigen value.

So, the second eigen vector can be left out.

 

Eigen vector corresponding to the greatest eigen value is the principal component for the given data set.

So. we find the eigen vector corresponding to eigen value λ1.

 

We use the following equation to find the eigen vector-

MX = λX

where-

  • M = Covariance Matrix
  • X = Eigen vector
  • λ = Eigen value

 

Substituting the values in the above equation, we get-

 

 

Solving these, we get-

2.92X1 + 3.67X2 = 8.22X1

3.67X1 + 5.67X2 = 8.22X2

 

On simplification, we get-

5.3X1 = 3.67X2       ………(1)

3.67X1 = 2.55X2     ………(2)

 

From (1) and (2), X1 = 0.69X2

From (2), the eigen vector is-

 

 

Thus, principal component for the given data set is-

 

 

Lastly, we project the data points onto the new subspace as-

 

 

Problem-02:

 

Use PCA Algorithm to transform the pattern (2, 1) onto the eigen vector in the previous question.

 

Solution-

 

The given feature vector is (2, 1).

 

The feature vector gets transformed to

= Transpose of Eigen vector x (Feature Vector – Mean Vector)

 

 

To gain better understanding about Principal Component Analysis,

Watch this Video Lecture

 

Get more notes and other study material of Pattern Recognition.

Watch video lectures by visiting our YouTube channel LearnVidFun.

K-Means Clustering Algorithm | Examples

Pattern Recognition

K-Means Clustering-

 

  • K-Means clustering is an unsupervised iterative clustering technique.
  • It partitions the given data set into k predefined distinct clusters.
  • A cluster is defined as a collection of data points exhibiting certain similarities.

 

 

It partitions the data set such that-

  • Each data point belongs to a cluster with the nearest mean.
  • Data points belonging to one cluster have high degree of similarity.
  • Data points belonging to different clusters have high degree of dissimilarity.

 

K-Means Clustering Algorithm-

 

K-Means Clustering Algorithm involves the following steps-

 

Step-01:

 

  • Choose the number of clusters K.

 

Step-02:

 

  • Randomly select any K data points as cluster centers.
  • Select cluster centers in such a way that they are as farther as possible from each other.

 

Step-03:

 

  • Calculate the distance between each data point and each cluster center.
  • The distance may be calculated either by using given distance function or by using euclidean distance formula.

 

Step-04:

 

  • Assign each data point to some cluster.
  • A data point is assigned to that cluster whose center is nearest to that data point.

 

Step-05:

 

  • Re-compute the center of newly formed clusters.
  • The center of a cluster is computed by taking mean of all the data points contained in that cluster.

 

Step-06:

 

Keep repeating the procedure from Step-03 to Step-05 until any of the following stopping criteria is met-

  • Center of newly formed clusters do not change
  • Data points remain present in the same cluster
  • Maximum number of iterations are reached

 

Advantages-

 

K-Means Clustering Algorithm offers the following advantages-

 

Point-01:

 

It is relatively efficient with time complexity O(nkt) where-

  • n = number of instances
  • k = number of clusters
  • t = number of iterations

 

Point-02:

 

  • It often terminates at local optimum.
  • Techniques such as Simulated Annealing or Genetic Algorithms may be used to find the global optimum.

 

Disadvantages-

 

K-Means Clustering Algorithm has the following disadvantages-

  • It requires to specify the number of clusters (k) in advance.
  • It can not handle noisy data and outliers.
  • It is not suitable to identify clusters with non-convex shapes.

 

PRACTICE PROBLEMS BASED ON K-MEANS CLUSTERING ALGORITHM-

 

Problem-01:

 

Cluster the following eight points (with (x, y) representing locations) into three clusters:

A1(2, 10), A2(2, 5), A3(8, 4), A4(5, 8), A5(7, 5), A6(6, 4), A7(1, 2), A8(4, 9)

 

Initial cluster centers are: A1(2, 10), A4(5, 8) and A7(1, 2).

The distance function between two points a = (x1, y1) and b = (x2, y2) is defined as-

Ρ(a, b) = |x2 – x1| + |y2 – y1|

 

Use K-Means Algorithm to find the three cluster centers after the second iteration.

 

Solution-

 

We follow the above discussed K-Means Clustering Algorithm-

 

Iteration-01:

 

  • We calculate the distance of each point from each of the center of the three clusters.
  • The distance is calculated by using the given distance function.

 

The following illustration shows the calculation of distance between point A1(2, 10) and each of the center of the three clusters-

 

Calculating Distance Between A1(2, 10) and C1(2, 10)-

 

Ρ(A1, C1)

= |x2 – x1| + |y2 – y1|

= |2 – 2| + |10 – 10|

= 0

 

Calculating Distance Between A1(2, 10) and C2(5, 8)-

 

Ρ(A1, C2)

= |x2 – x1| + |y2 – y1|

= |5 – 2| + |8 – 10|

= 3 + 2

= 5

 

Calculating Distance Between A1(2, 10) and C3(1, 2)-

 

Ρ(A1, C3)

= |x2 – x1| + |y2 – y1|

= |1 – 2| + |2 – 10|

= 1 + 8

= 9

 

In the similar manner, we calculate the distance of other points from each of the center of the three clusters.

 

Next,

  • We draw a table showing all the results.
  • Using the table, we decide which point belongs to which cluster.
  • The given point belongs to that cluster whose center is nearest to it.

 

Given Points Distance from center (2, 10) of Cluster-01 Distance from center (5, 8) of Cluster-02 Distance from center (1, 2) of Cluster-03 Point belongs to Cluster
A1(2, 10) 0 5 9 C1
A2(2, 5) 5 6 4 C3
A3(8, 4) 12 7 9 C2
A4(5, 8) 5 0 10 C2
A5(7, 5) 10 5 9 C2
A6(6, 4) 10 5 7 C2
A7(1, 2) 9 10 0 C3
A8(4, 9) 3 2 10 C2

 

From here, New clusters are-

 

Cluster-01:

 

First cluster contains points-

  • A1(2, 10)

 

Cluster-02:

 

Second cluster contains points-

  • A3(8, 4)
  • A4(5, 8)
  • A5(7, 5)
  • A6(6, 4)
  • A8(4, 9)

 

Cluster-03:

 

Third cluster contains points-

  • A2(2, 5)
  • A7(1, 2)

 

Now,

  • We re-compute the new cluster clusters.
  • The new cluster center is computed by taking mean of all the points contained in that cluster.

 

For Cluster-01:

 

  • We have only one point A1(2, 10) in Cluster-01.
  • So, cluster center remains the same.

 

For Cluster-02:

 

Center of Cluster-02

= ((8 + 5 + 7 + 6 + 4)/5, (4 + 8 + 5 + 4 + 9)/5)

= (6, 6)

 

For Cluster-03:

 

Center of Cluster-03

= ((2 + 1)/2, (5 + 2)/2)

= (1.5, 3.5)

 

This is completion of Iteration-01.

 

Iteration-02:

 

  • We calculate the distance of each point from each of the center of the three clusters.
  • The distance is calculated by using the given distance function.

 

The following illustration shows the calculation of distance between point A1(2, 10) and each of the center of the three clusters-

 

Calculating Distance Between A1(2, 10) and C1(2, 10)-

 

Ρ(A1, C1)

= |x2 – x1| + |y2 – y1|

= |2 – 2| + |10 – 10|

= 0

 

Calculating Distance Between A1(2, 10) and C2(6, 6)-

 

Ρ(A1, C2)

= |x2 – x1| + |y2 – y1|

= |6 – 2| + |6 – 10|

= 4 + 4

= 8

 

Calculating Distance Between A1(2, 10) and C3(1.5, 3.5)-

 

Ρ(A1, C3)

= |x2 – x1| + |y2 – y1|

= |1.5 – 2| + |3.5 – 10|

= 0.5 + 6.5

= 7

 

In the similar manner, we calculate the distance of other points from each of the center of the three clusters.

 

Next,

  • We draw a table showing all the results.
  • Using the table, we decide which point belongs to which cluster.
  • The given point belongs to that cluster whose center is nearest to it.

 

Given Points Distance from center (2, 10) of Cluster-01 Distance from center (6, 6) of Cluster-02 Distance from center (1.5, 3.5) of Cluster-03 Point belongs to Cluster
A1(2, 10) 0 8 7 C1
A2(2, 5) 5 5 2 C3
A3(8, 4) 12 4 7 C2
A4(5, 8) 5 3 8 C2
A5(7, 5) 10 2 7 C2
A6(6, 4) 10 2 5 C2
A7(1, 2) 9 9 2 C3
A8(4, 9) 3 5 8 C1

 

From here, New clusters are-

 

Cluster-01:

 

First cluster contains points-

  • A1(2, 10)
  • A8(4, 9)

 

Cluster-02:

 

Second cluster contains points-

  • A3(8, 4)
  • A4(5, 8)
  • A5(7, 5)
  • A6(6, 4)

 

Cluster-03:

 

Third cluster contains points-

  • A2(2, 5)
  • A7(1, 2)

 

Now,

  • We re-compute the new cluster clusters.
  • The new cluster center is computed by taking mean of all the points contained in that cluster.

 

For Cluster-01:

 

Center of Cluster-01

= ((2 + 4)/2, (10 + 9)/2)

= (3, 9.5)

 

For Cluster-02:

 

Center of Cluster-02

= ((8 + 5 + 7 + 6)/4, (4 + 8 + 5 + 4)/4)

= (6.5, 5.25)

 

For Cluster-03:

 

Center of Cluster-03

= ((2 + 1)/2, (5 + 2)/2)

= (1.5, 3.5)

 

This is completion of Iteration-02.

 

After second iteration, the center of the three clusters are-

  • C1(3, 9.5)
  • C2(6.5, 5.25)
  • C3(1.5, 3.5)

 

Problem-02:

 

Use K-Means Algorithm to create two clusters-

 

 

Solution-

 

We follow the above discussed K-Means Clustering Algorithm.

Assume A(2, 2) and C(1, 1) are centers of the two clusters.

 

Iteration-01:

 

  • We calculate the distance of each point from each of the center of the two clusters.
  • The distance is calculated by using the euclidean distance formula.

 

The following illustration shows the calculation of distance between point A(2, 2) and each of the center of the two clusters-

 

Calculating Distance Between A(2, 2) and C1(2, 2)-

 

Ρ(A, C1)

= sqrt [ (x2 – x1)2 + (y2 – y1)2 ]

= sqrt [ (2 – 2)2 + (2 – 2)2 ]

= sqrt [ 0 + 0 ]

= 0

 

Calculating Distance Between A(2, 2) and C2(1, 1)-

 

Ρ(A, C2)

= sqrt [ (x2 – x1)2 + (y2 – y1)2 ]

= sqrt [ (1 – 2)2 + (1 – 2)2 ]

= sqrt [ 1 + 1 ]

= sqrt [ 2 ]

= 1.41

 

In the similar manner, we calculate the distance of other points from each of the center of the two clusters.

 

Next,

  • We draw a table showing all the results.
  • Using the table, we decide which point belongs to which cluster.
  • The given point belongs to that cluster whose center is nearest to it.

 

Given Points Distance from center (2, 2) of Cluster-01 Distance from center (1, 1) of Cluster-02 Point belongs to Cluster
A(2, 2) 0 1.41 C1
B(3, 2) 1 2.24 C1
C(1, 1) 1.41 0 C2
D(3, 1) 1.41 2 C1
E(1.5, 0.5) 1.58 0.71 C2

 

From here, New clusters are-

 

Cluster-01:

 

First cluster contains points-

  • A(2, 2)
  • B(3, 2)
  • E(1.5, 0.5)
  • D(3, 1)

 

Cluster-02:

 

Second cluster contains points-

  • C(1, 1)
  • E(1.5, 0.5)

 

Now,

  • We re-compute the new cluster clusters.
  • The new cluster center is computed by taking mean of all the points contained in that cluster.

 

For Cluster-01:

 

Center of Cluster-01

= ((2 + 3 + 3)/3, (2 + 2 + 1)/3)

= (2.67, 1.67)

 

For Cluster-02:

 

Center of Cluster-02

= ((1 + 1.5)/2, (1 + 0.5)/2)

= (1.25, 0.75)

 

This is completion of Iteration-01.

Next, we go to iteration-02, iteration-03 and so on until the centers do not change anymore.

 

To gain better understanding about K-Means Clustering Algorithm,

Watch this Video Lecture

 

Next Article- Principal Component Analysis

 

Get more notes and other study material of Pattern Recognition.

Watch video lectures by visiting our YouTube channel LearnVidFun.

A* Algorithm | A* Algorithm Example in AI

Artificial Intelligence

A* Algorithm-

 

  • A* Algorithm is one of the best and popular techniques used for path finding and graph traversals.
  • A lot of games and web-based maps use this algorithm for finding the shortest path efficiently.
  • It is essentially a best first search algorithm.

 

Working-

 

A* Algorithm works as-

  • It maintains a tree of paths originating at the start node.
  • It extends those paths one edge at a time.
  • It continues until its termination criterion is satisfied.

 

A* Algorithm extends the path that minimizes the following function-

f(n) = g(n) + h(n)

 

Here,

  • ‘n’ is the last node on the path
  • g(n) is the cost of the path from start node to node ‘n’
  • h(n) is a heuristic function that estimates cost of the cheapest path from node ‘n’ to the goal node

 

Algorithm-

 

  • The implementation of A* Algorithm involves maintaining two lists- OPEN and CLOSED.
  • OPEN contains those nodes that have been evaluated by the heuristic function but have not been expanded into successors yet.
  • CLOSED contains those nodes that have already been visited.

 

The algorithm is as follows-

 

Step-01:

 

  • Define a list OPEN.
  • Initially, OPEN consists solely of a single node, the start node S.

 

Step-02:

 

If the list is empty, return failure and exit.

 

Step-03:

 

  • Remove node n with the smallest value of f(n) from OPEN and move it to list CLOSED.
  • If node n is a goal state, return success and exit.

 

Step-04:

 

Expand node n.

 

Step-05:

 

  • If any successor to n is the goal node, return success and the solution by tracing the path from goal node to S.
  • Otherwise, go to Step-06.

 

Step-06:

 

For each successor node,

  • Apply the evaluation function f to the node.
  • If the node has not been in either list, add it to OPEN.

 

Step-07:

 

Go back to Step-02.

 

AI algorithms will differ based on their applications.  For a better understanding of how AI algorithms work in coding, the Github Certification course offers skills to learn how AI algorithms are used to analyze code, identify bugs, etc.

 

PRACTICE PROBLEMS BASED ON A* ALGORITHM-

 

Problem-01:

 

Given an initial state of a 8-puzzle problem and final state to be reached-

 

 

Find the most cost-effective path to reach the final state from initial state using A* Algorithm.

Consider g(n) = Depth of node and h(n) = Number of misplaced tiles.

 

Solution-

 

  • A* Algorithm maintains a tree of paths originating at the initial state.
  • It extends those paths one edge at a time.
  • It continues until final state is reached.

 

 

Problem-02:

 

Consider the following graph-

 

 

The numbers written on edges represent the distance between the nodes.

The numbers written on nodes represent the heuristic value.

Find the most cost-effective path to reach from start state A to final state J using A* Algorithm.

 

Solution-

 

Step-01:

 

  • We start with node A.
  • Node B and Node F can be reached from node A.

 

A* Algorithm calculates f(B) and f(F).

  • f(B) = 6 + 8 = 14
  • f(F) = 3 + 6 = 9

 

Since f(F) < f(B), so it decides to go to node F.

 

Path- A → F

 

Step-02:

 

Node G and Node H can be reached from node F.

 

A* Algorithm calculates f(G) and f(H).

  • f(G) = (3+1) + 5 = 9
  • f(H) = (3+7) + 3 = 13

 

Since f(G) < f(H), so it decides to go to node G.

 

Path- A → F → G

 

Step-03:

 

Node I can be reached from node G.

 

A* Algorithm calculates f(I).

f(I) = (3+1+3) + 1 = 8

It decides to go to node I.

 

Path- A → F → G → I

 

Step-04:

 

Node E, Node H and Node J can be reached from node I.

 

A* Algorithm calculates f(E), f(H) and f(J).

  • f(E) = (3+1+3+5) + 3 = 15
  • f(H) = (3+1+3+2) + 3 = 12
  • f(J) = (3+1+3+3) + 0 = 10

 

Since f(J) is least, so it decides to go to node J.

 

Path- A → F → G → I → J

This is the required shortest path from node A to node J.

 

 

Important Note-

 

It is important to note that-

  • A* Algorithm is one of the best path finding algorithms.
  • But it does not produce the shortest path always.
  • This is because it heavily depends on heuristics.

 

To gain better understanding about A* Search Algorithm,

Watch this Video Lecture

 

Get more notes and other study material of Artificial Intelligence.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Machine Learning Workflow | Process Steps

Machine Learning

Machine Learning-

 

Before you go through this article, make sure that you have gone through the previous article on Machine Learning.

 

We have discussed-

  • Machine learning is building machines that can adapt and learn from experience.
  • Machine learning systems are not explicitly programmed.

 

In this article, we will discuss machine learning workflow.

 

Machine Learning Workflow-

 

Machine learning workflow refers to the series of stages or steps involved in the process of building a successful machine learning system.

 

The various stages involved in the machine learning workflow are-

 

 

  1. Data Collection
  2. Data Preparation
  3. Choosing Learning Algorithm
  4. Training Model
  5. Evaluating Model
  6. Predictions

 

Let us discuss each stage one by one.

 

1. Data Collection-

 

In this stage,

  • Data is collected from different sources.
  • The type of data collected depends upon the type of desired project.
  • Data may be collected from various sources such as files, databases etc.
  • The quality and quantity of gathered data directly affects the accuracy of the desired system.

 

2. Data Preparation-

 

In this stage,

  • Data preparation is done to clean the raw data.
  • Data collected from the real world is transformed to a clean dataset.
  • Raw data may contain missing values, inconsistent values, duplicate instances etc.
  • So, raw data cannot be directly used for building a model.

 

Different methods of cleaning the dataset are-

  • Ignoring the missing values
  • Removing instances having missing values from the dataset.
  • Estimating the missing values of instances using mean, median or mode.
  • Removing duplicate instances from the dataset.
  • Normalizing the data in the dataset.

 

This is the most time consuming stage in machine learning workflow.

 

3. Choosing Learning Algorithm-

 

In this stage,

  • The best performing learning algorithm is researched.
  • It depends upon the type of problem that needs to solved and the type of data we have.
  • If the problem is to classify and the data is labeled, classification algorithms are used.
  • If the problem is to perform a regression task and the data is labeled, regression algorithms are used.
  • If the problem is to create clusters and the data is unlabeled, clustering algorithms are used.

 

The following chart provides the overview of learning algorithms-

 

 

4. Training Model-

 

In this stage,

  • The model is trained to improve its ability.
  • The dataset is divided into training dataset and testing dataset.
  • The training and testing split is order of 80/20 or 70/30.
  • It also depends upon the size of the dataset.
  • Training dataset is used for training purpose.
  • Testing dataset is used for the testing purpose.
  • Training dataset is fed to the learning algorithm.
  • The learning algorithm finds a mapping between the input and the output and generates the model.

 

 

5. Evaluating Model-

 

In this stage,

  • The model is evaluated to test if the model is any good.
  • The model is evaluated using the kept-aside testing dataset.
  • It allows to test the model against data that has never been used before for training.
  • Metrics such as accuracy, precision, recall etc are used to test the performance.
  • If the model does not perform well, the model is re-built using different hyper parameters.
  • The accuracy may be further improved by tuning the hyper parameters.

 

 

6. Predictions-

 

In this stage,

  • The built system is finally used to do something useful in the real world.
  • Here, the true value of machine learning is realized.

 

To gain better understanding about Machine Learning Workflow,

Watch this Video Lecture

 

Next Article- Linear Regression

 

Get more notes and other study material of Machine Learning.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Bezier Curve in Computer Graphics | Examples

Computer Graphics

Bezier Curve-

 

Bezier Curve may be defined as-

  • Bezier Curve is parametric curve defined by a set of control points.
  • Two points are ends of the curve.
  • Other points determine the shape of the curve.

 

The concept of bezier curves was given by Pierre Bezier.

 

Bezier Curve Example-

 

The following curve is an example of a bezier curve-

 

 

Here,

  • This bezier curve is defined by a set of control points b0, b1, b2 and b3.
  • Points b0 and b3 are ends of the curve.
  • Points b1 and b2 determine the shape of the curve.

 

Bezier Curve Properties-

 

Few important properties of a bezier curve are-

 

Property-01:

 

Bezier curve is always contained within a polygon called as convex hull of its control points.

 

 

Property-02:

 

  • Bezier curve generally follows the shape of its defining polygon.
  • The first and last points of the curve are coincident with the first and last points of the defining polygon.

 

Property-03:

 

The degree of the polynomial defining the curve segment is one less than the total number of control points.

 

Degree = Number of Control Points – 1

 

Property-04:

 

The order of the polynomial defining the curve segment is equal to the total number of control points.

 

Order = Number of Control Points

 

Property-05:

 

  • Bezier curve exhibits the variation diminishing property.
  • It means the curve do not oscillate about any straight line more often than the defining polygon.

 

Bezier Curve Equation-

 

A bezier curve is parametrically represented by-

 

 

Here,

  • t is any parameter where 0 <= t <= 1
  • P(t) = Any point lying on the bezier curve
  • Bi = ith control point of the bezier curve
  • n = degree of the curve
  • Jn,i(t) = Blending function = C(n,i)ti(1-t)n-i where C(n,i) = n! / i!(n-i)!

 

Cubic Bezier Curve-

 

  • Cubic bezier curve is a bezier curve with degree 3.
  • The total number of control points in a cubic bezier curve is 4.

 

Example-

 

The following curve is an example of a cubic bezier curve-

 

 

Here,

  • This curve is defined by 4 control points b0, b1, b2 and b3.
  • The degree of this curve is 3.
  • So, it is a cubic bezier curve.

 

Cubic Bezier Curve Equation-

 

The parametric equation of a bezier curve is-

 

 

Substituting n = 3 for a cubic bezier curve, we get-

 

 

Expanding the above equation, we get-

P (t) = B0J3,0(t) + B1J3,1(t) + B2J3,2(t) + B3J3,3(t)     ………..(1)

 

Now,

 

 

Using (2), (3), (4) and (5) in (1), we get-

 

P(t) = B0(1-t)3 + B13t(1-t)2 + B23t2(1-t) + B3t3

 

This is the required parametric equation for a cubic bezier curve.

 

Applications of Bezier Curves-

 

Bezier curves have their applications in the following fields-

 

1. Computer Graphics-

 

  • Bezier curves are widely used in computer graphics to model smooth curves.
  • The curve is completely contained in the convex hull of its control points.
  • So, the points can be graphically displayed & used to manipulate the curve intuitively.

 

2. Animation-

 

  • Bezier curves are used to outline movement in animation applications such as Adobe Flash and synfig.
  • Users outline the wanted path in bezier curves.
  • The application creates the needed frames for the object to move along the path.
  • For 3D animation, bezier curves are often used to define 3D paths as well as 2D curves.

 

3. Fonts-

 

  • True type fonts use composite bezier curves composed of quadratic bezier curves.
  • Modern imaging systems like postscript, asymptote etc use composite bezier curves composed of cubic bezier curves for drawing curved shapes.

 

PRACTICE PROBLEMS BASED ON BEZIER CURVE IN COMPUTER GRAPHICS-

 

Problem-01:

 

Given a bezier curve with 4 control points-

B0[1 0] , B1[3 3] , B2[6 3] , B3[8 1]

Determine any 5 points lying on the curve. Also, draw a rough sketch of the curve.

 

Solution-

 

We have-

  • The given curve is defined by 4 control points.
  • So, the given curve is a cubic bezier curve.

 

The parametric equation for a cubic bezier curve is-

 

P(t) = B0(1-t)3 + B13t(1-t)2 + B23t2(1-t) + B3t3

 

Substituting the control points B0, B1, B2 and B3, we get-

P(t) = [1 0](1-t)3 + [3 3]3t(1-t)2 + [6 3]3t2(1-t) + [8 1]t3      ……..(1)

 

Now,

To get 5 points lying on the curve, assume any 5 values of t lying in the range 0 <= t <= 1.

Let 5 values of t are 0, 0.2, 0.5, 0.7, 1

 

For t = 0:

 

Substituting t=0 in (1), we get-

P(0) = [1 0](1-0)3 + [3 3]3(0)(1-t)2 + [6 3]3(0)2(1-0) + [8 1](0)3

P(0) = [1 0] + 0 + 0 + 0

P(0) = [1 0]

 

For t = 0.2:

 

Substituting t=0.2 in (1), we get-

P(0.2) = [1 0](1-0.2)3 + [3 3]3(0.2)(1-0.2)2 + [6 3]3(0.2)2(1-0.2) + [8 1](0.2)3

P(0.2) = [1 0](0.8)3 + [3 3]3(0.2)(0.8)2 + [6 3]3(0.2)2(0.8) + [8 1](0.2)3

P(0.2) = [1 0] x 0.512 + [3 3] x 3 x 0.2 x 0.64 + [6 3] x 3 x 0.04 x 0.8 + [8 1] x 0.008

P(0.2) = [1 0] x 0.512 + [3 3] x 0.384 + [6 3] x 0.096 + [8 1] x 0.008

P(0.2) = [0.512 0] + [1.152 1.152] + [0.576 0.288] + [0.064 0.008]

P(0.2) = [2.304 1.448]

 

For t = 0.5:

 

Substituting t=0.5 in (1), we get-

P(0.5) = [1 0](1-0.5)3 + [3 3]3(0.5)(1-0.5)2 + [6 3]3(0.5)2(1-0.5) + [8 1](0.5)3

P(0.5) = [1 0](0.5)3 + [3 3]3(0.5)(0.5)2 + [6 3]3(0.5)2(0.5) + [8 1](0.5)3

P(0.5) = [1 0] x 0.125 + [3 3] x 3 x 0.5 x 0.25 + [6 3] x 3 x 0.25 x 0.5 + [8 1] x 0.125

P(0.5) = [1 0] x 0.125 + [3 3] x 0.375 + [6 3] x 0.375 + [8 1] x 0.125

P(0.5) = [0.125 0] + [1.125 1.125] + [2.25 1.125] + [1 0.125]

P(0.5) = [4.5 2.375]

 

For t = 0.7:

 

Substituting t=0.7 in (1), we get-

P(t) = [1 0](1-t)3 + [3 3]3t(1-t)2 + [6 3]3t2(1-t) + [8 1]t3

P(0.7) = [1 0](1-0.7)3 + [3 3]3(0.7)(1-0.7)2 + [6 3]3(0.7)2(1-0.7) + [8 1](0.7)3

P(0.7) = [1 0](0.3)3 + [3 3]3(0.7)(0.3)2 + [6 3]3(0.7)2(0.3) + [8 1](0.7)3

P(0.7) = [1 0] x 0.027 + [3 3] x 3 x 0.7 x 0.09 + [6 3] x 3 x 0.49 x 0.3 + [8 1] x 0.343

P(0.7) = [1 0] x 0.027 + [3 3] x 0.189 + [6 3] x 0.441 + [8 1] x 0.343

P(0.7) = [0.027 0] + [0.567 0.567] + [2.646 1.323] + [2.744 0.343]

P(0.7) = [5.984 2.233]

 

For t = 1:

 

Substituting t=1 in (1), we get-

P(1) = [1 0](1-1)3 + [3 3]3(1)(1-1)2 + [6 3]3(1)2(1-1) + [8 1](1)3

P(1) = [1 0] x 0 + [3 3] x 3 x 1 x 0 + [6 3] x 3 x 1 x 0 + [8 1] x 1

P(1) = 0 + 0 + 0 + [8 1]

P(1) = [8 1]

 

Following is the required rough sketch of the curve-

 

 

To gain better understanding about Bezier Curves in Computer Graphics,

Watch this Video Lecture

 

Get more notes and other study material of Computer Graphics.

Watch video lectures by visiting our YouTube channel LearnVidFun.