1 - Introduction and problem definition
1.1 - Introduction
Image segmentation is an important process in Computer Vision that is used for several operations as edge detection, classification, 3D reconstruction, etc.. The main goal of image segmentation is to cluster pixels into regions. This clustering image pixels into image regions in turns convert the image into a representation that is more meaningful and easier to analyse. More precisely, image segmentation is the process of assigning a label to every pixel in an image such that pixels with the same label share certain characteristics. Image segmentation has broad range of applicability in different fields of science ans engineering.
In this lab work, we implement the region growing algorithm which is one of the basic process of partitioning a digital image and then analyse the design and implementation of it. Finally, we compare the region growing algorithm with other image segmentation algorithms. We describe also about the organization and development phase of the lab work.
1.2 - Problem definition
Our lab work problem asks for performing image segmentation over different image representation and check the result. We implement our image segmentation algorithm over gray level images and RGB color space images to cluster into different image regions. And then we compare our clustering result with Fuzzy C-Means (FCM) clustering algorithm.
Showing posts with label MATLAB. Show all posts
Showing posts with label MATLAB. Show all posts
Saturday, October 3, 2015
Thursday, June 11, 2015
Robot Navigation - Q learning algorithm
Objective
The aim of this lab is to understand the reinforcement learning subject of the autonomous robots course and implement a reinforcement learning algorithm to learn a policy that moves a robot to a goal position. The algorithm is the Q-learning algorithm and it will be implemented in Matlab.
1 - Introduction
The reinforcement learning algorithm does not force the robot to plan path by using any path planning algorithm, rather the algorithm learns optimal solution by randomly moving inside map for several times. It is an approximation of natural learning process, where unknown problem is solved just by trial and error method. The following sections will briefly discuss about the implementation and the results obtained by the algorithm.
Environment: The environment used for this lab experiment is shown below.
States and Actions: The size of the given environment is 20$\times$14 = 280 states. The robot can only do 4 different actions: ←, ↑, →, ↓. Thus, the size of the Q matrices would be 280$\times$4 = 1120 cells.
Dynamics: Dynamics make the robot move towards a direction according to the actions. The robot will move one cell per iteration to the direction of the action that we select, unless there is an obstacle or the wall in front of it, in which case it will stay in the same position.
Reinforcement function: Reinforcement function assigns reward at each cell, +1 for goal cell and -1 otherwise.
The aim of this lab is to understand the reinforcement learning subject of the autonomous robots course and implement a reinforcement learning algorithm to learn a policy that moves a robot to a goal position. The algorithm is the Q-learning algorithm and it will be implemented in Matlab.
1 - Introduction
The reinforcement learning algorithm does not force the robot to plan path by using any path planning algorithm, rather the algorithm learns optimal solution by randomly moving inside map for several times. It is an approximation of natural learning process, where unknown problem is solved just by trial and error method. The following sections will briefly discuss about the implementation and the results obtained by the algorithm.
Environment: The environment used for this lab experiment is shown below.
Figure-1: Environment used for the implementation.
States and Actions: The size of the given environment is 20$\times$14 = 280 states. The robot can only do 4 different actions: ←, ↑, →, ↓. Thus, the size of the Q matrices would be 280$\times$4 = 1120 cells.
Dynamics: Dynamics make the robot move towards a direction according to the actions. The robot will move one cell per iteration to the direction of the action that we select, unless there is an obstacle or the wall in front of it, in which case it will stay in the same position.
Reinforcement function: Reinforcement function assigns reward at each cell, +1 for goal cell and -1 otherwise.
Tuesday, May 12, 2015
Robot Navigation - Rapidly-Exploring Random Tree Algorithm
Objective
The aim of this post is to understand the rapidly-exploring random tree and implement it in Matlab.
1 - Introduction
A rapidly exploring random tree (RRT) is an algorithm designed to efficiently search nonconvex, high-dimensional spaces by randomly building a space-filling tree. The tree is constructed incrementally from samples drawn randomly from the search space and is inherently biased to grow towards large unsearched areas of the problem. It widely used in autonomous robotic path planning.
2 - The Algorithm
RRTs were proposed as both a sampling algorithm and a data structure designed to allow fast searches in high-dimensional spaces in motion planning. RRTs are progressively built towards unexplored regions of the space from an initial configuration as shown in Figure 1.
At every step a random $q\_rand$ configuration is chosen and for that configuration the nearest configuration already belonging to the tree $q\_near$ is found. For this a definition of distance is required (in motion planning, the euclidean distance is usually chosen as the distance measure). When the nearest configuration is found, a local planner tries to join $q\_near$ with qrand with a limit distance . If $q\_rand$ was reached, it is added to the tree and connected with an edge to $q\_near$. If $q\_rand$ was not reached, then the configuration $q\_new$ obtained at the end of the local search is added to the tree in the same way as long as there was no collision with an obstacle during the search. This operation is called the Extend step, illustrated in Figure 2. This process is repeated until some criteria is met, like a limit on the size of the tree.
The aim of this post is to understand the rapidly-exploring random tree and implement it in Matlab.
1 - Introduction
A rapidly exploring random tree (RRT) is an algorithm designed to efficiently search nonconvex, high-dimensional spaces by randomly building a space-filling tree. The tree is constructed incrementally from samples drawn randomly from the search space and is inherently biased to grow towards large unsearched areas of the problem. It widely used in autonomous robotic path planning.
2 - The Algorithm
RRTs were proposed as both a sampling algorithm and a data structure designed to allow fast searches in high-dimensional spaces in motion planning. RRTs are progressively built towards unexplored regions of the space from an initial configuration as shown in Figure 1.
Progressive construction of an RRT.
At every step a random $q\_rand$ configuration is chosen and for that configuration the nearest configuration already belonging to the tree $q\_near$ is found. For this a definition of distance is required (in motion planning, the euclidean distance is usually chosen as the distance measure). When the nearest configuration is found, a local planner tries to join $q\_near$ with qrand with a limit distance . If $q\_rand$ was reached, it is added to the tree and connected with an edge to $q\_near$. If $q\_rand$ was not reached, then the configuration $q\_new$ obtained at the end of the local search is added to the tree in the same way as long as there was no collision with an obstacle during the search. This operation is called the Extend step, illustrated in Figure 2. This process is repeated until some criteria is met, like a limit on the size of the tree.
Friday, May 1, 2015
Robot Navigation - A Star Algorithm
Objective
The aim of this lab is to understand the A* algorithm and implement it in Matlab.
1 - Introduction
In computer science, A* is a computer algorithm that is widely used in pathfinding and graph traversal, the process of plotting an efficiently traversable path between points, called nodes. A* achieves better time performance by using heuristics.
2 - The Algorithm
A* uses a best-first search and finds a least-cost path from a given initial node to the goal node. As A* traverses the graph, it follows a path of the lowest expected total cost or distance, keeping a sorted priority queue of alternate path segments along the way.
It uses a knowledge-plus-heuristic cost function of node x to determine the order in which the search visits nodes in the tree. The cost function is a sum of two functions:
If the heuristic h satisfies the additional condition h(x) = d(x,y) + h(y) for every edge (x, y) of the graph (where d denotes the length of that edge), then h is called consistent. In such a case, A* can be implemented more efficiently. No node needs to be processed more than once and. Now let's look at closely to the each steps.
The aim of this lab is to understand the A* algorithm and implement it in Matlab.
1 - Introduction
In computer science, A* is a computer algorithm that is widely used in pathfinding and graph traversal, the process of plotting an efficiently traversable path between points, called nodes. A* achieves better time performance by using heuristics.
2 - The Algorithm
A* uses a best-first search and finds a least-cost path from a given initial node to the goal node. As A* traverses the graph, it follows a path of the lowest expected total cost or distance, keeping a sorted priority queue of alternate path segments along the way.
It uses a knowledge-plus-heuristic cost function of node x to determine the order in which the search visits nodes in the tree. The cost function is a sum of two functions:
- the past path-cost function, which is the known distance from the starting node to the current node x (denoted g(x))
- a future path-cost function, which is an admissible "heuristic estimate" of the distance from x to the goal (denoted h(x)).
If the heuristic h satisfies the additional condition h(x) = d(x,y) + h(y) for every edge (x, y) of the graph (where d denotes the length of that edge), then h is called consistent. In such a case, A* can be implemented more efficiently. No node needs to be processed more than once and. Now let's look at closely to the each steps.
Thursday, April 30, 2015
Robot Navigation - The Rotational Sweep Algorithm
Objective
The aim of this post is to understand the rotational plane sweep algorithm to build a visibility graph and implement it in Matlab.
1 - Introduction
The rotational plane sweep is a path planning algorithm based on topological maps. It is one of the most powerful method of intelligent robot navigation. The basic concepts and details of the algorithm are going to be explained in the next chapter. After that, we are going to see the results.
2 - The Algorithm
Topological map is a simplified map with only relationship between points. It can be represented as a graph:
In order to create visibility graph. We should define for a 2D polygonal configuration space
The aim of this post is to understand the rotational plane sweep algorithm to build a visibility graph and implement it in Matlab.
1 - Introduction
The rotational plane sweep is a path planning algorithm based on topological maps. It is one of the most powerful method of intelligent robot navigation. The basic concepts and details of the algorithm are going to be explained in the next chapter. After that, we are going to see the results.
2 - The Algorithm
Topological map is a simplified map with only relationship between points. It can be represented as a graph:
- nodes are real positions
- edges join positions in the free space.
In order to create visibility graph. We should define for a 2D polygonal configuration space
- The nodes $v_{i}$ of the visibility graph include the start location, the goal location, and all the vertices of the configuration space obstacles.
- The graph edges $e_{ij}$ are straight-line segments that connect two line-of-sight nodes $v_{i}$ and $v_{j}$, i.e.,
Saturday, March 28, 2015
Robot Navigation - The Wavefront Planner Algorithm
Hi, reader this report was written for the 'Autonomous Robots' labwork. It explains 'The Wavefront Planner Algorithm'. End of this post, you can see the Matlab codes and also the report itself.
1 - Introduction
The theories behind robot maze navigation is immense. It would take several books just to cover the basics. But this labwork only concentrate on the wavefront planner algorithm which is still powerful methods of intelligent robot navigation. The basic concepts and details of the algorithm are going to be explained in the next chapter. After that, we are going to see the results.
2 - The Algorithm
The wavefront algorithm finds a path from point S (start) to point G (goal) through a discretized workspace such as this (0 designates a cell of free space, 1 designates a cell fully occupied by an obstacle):
\[
\begin{bmatrix}
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\
1 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 1 \\
1 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 2 & 0 & 1 \\
1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 1 \\
1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 1 \\
1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 1 \\
1 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 1 \\
1 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\
1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\
1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\
1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 \\
1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 1 \\
1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 1 \\
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\
\end{bmatrix}
\]
1 - Introduction
The theories behind robot maze navigation is immense. It would take several books just to cover the basics. But this labwork only concentrate on the wavefront planner algorithm which is still powerful methods of intelligent robot navigation. The basic concepts and details of the algorithm are going to be explained in the next chapter. After that, we are going to see the results.
2 - The Algorithm
The wavefront algorithm finds a path from point S (start) to point G (goal) through a discretized workspace such as this (0 designates a cell of free space, 1 designates a cell fully occupied by an obstacle):
\[
\begin{bmatrix}
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\
1 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 1 \\
1 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 2 & 0 & 1 \\
1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 1 \\
1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 1 \\
1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 1 \\
1 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 1 \\
1 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\
1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\
1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\
1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 \\
1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 1 \\
1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 1 \\
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\
\end{bmatrix}
\]
Wednesday, January 21, 2015
Face Recognition
Chapter 1: Introduction
1. Preliminary
In this project, we implemented a face recognition system by using principal component analysis, which is known as PCA. PCA method provide a mathematical way to reduce the dimension of problem.
Since the most elements of a facial image are highly correlated, it is better to extract a set of interesting and discriminative feature of a facial image. Mathematically speaking, we transform the correlated data to independent data. To implement the transform, we employed some linear algebra method such as SVD (Chapter3). The main idea is to obtain Eigenfaces that every face can be regard as a linear combination of these eigenfaces (Chapter4). Then the face recognition problem convert to a mathematic problem: what is the linear combination of a face? In other words, it simplify a problem from 2D to 1D.
1. Preliminary
In this project, we implemented a face recognition system by using principal component analysis, which is known as PCA. PCA method provide a mathematical way to reduce the dimension of problem.
Since the most elements of a facial image are highly correlated, it is better to extract a set of interesting and discriminative feature of a facial image. Mathematically speaking, we transform the correlated data to independent data. To implement the transform, we employed some linear algebra method such as SVD (Chapter3). The main idea is to obtain Eigenfaces that every face can be regard as a linear combination of these eigenfaces (Chapter4). Then the face recognition problem convert to a mathematic problem: what is the linear combination of a face? In other words, it simplify a problem from 2D to 1D.
Friday, November 21, 2014
How Google ranks Web pages?
Google’s search algorithm combined precomputed PageRank scores with text matching scores to obtain an overall ranking score for each webpage. The PageRank algorithm assigns a PageRank score to each webpages. The algorithm models the behavior of an idealized random Web surfer [1, 2]. This Internet user randomly chooses a webpage to view from the listing of available webpages. Then, the surfer randomly selects a link from that webpage to another webpage.
The model the activity of the random Web surfer, the PageRank algorithm represents the link structure of the Web as a directed graph.
The model the activity of the random Web surfer, the PageRank algorithm represents the link structure of the Web as a directed graph.
The process for determining PageRank begins by expressing the directed Web graph as the nxn hyperlink matrix, H, where n is the number of webpages.
Wednesday, October 22, 2014
"Light's Out" Game and Its Solution with Linear Algebra
Hi reader, this is my first article that is written in English here. Why I am writing in English? Actually, I want to share my reports and projects that I found interesting during the master. All reports and projects are of course in English. So, I don't want to translate these subject to Turkish. If you don't know English but want to learn more about. You can ask everything about the related subject. Today, I am going to talk about "Light's Out" game and its solution with "Linear Algebra". If you know Linear Algebra and how to apply it to the game, then it is just 10-15 lines of code. I am also going to share the MATLAB solution end of the article.
Chapter 1: Abstract
1. Preliminary
Light out is a game introduced by tiger electronics, an American toy manufacturer, on a 5 by grid matrix, where each matrix can have either on or off status? The game begins with some of the matrices turned on randomly. Pressing a single buttons will affect the status of itself and its neighbors. The game of the game is to systematically press as much as possible less number of times and making every matrices become off.[1][2]
The goal of the game is to turn all of the lights off. The goal of the puzzle is to switch all the lights off, preferably in as few button presses as possible. Every time a button is pressed, the state of that button as well as the state of the buttons above, below and to the left and right are changed. For example, if all buttons are turned off and a button is pressed, the resulting outcome could result in three, four, or five buttons lighting up depending upon where the original button was located on the game board.[4]
Chapter 1: Abstract
1. Preliminary
Light out is a game introduced by tiger electronics, an American toy manufacturer, on a 5 by grid matrix, where each matrix can have either on or off status? The game begins with some of the matrices turned on randomly. Pressing a single buttons will affect the status of itself and its neighbors. The game of the game is to systematically press as much as possible less number of times and making every matrices become off.[1][2]
Subscribe to:
Posts (Atom)