Have a Question ?
Ask about our products, services, or latest research. Let's discuss how we can help you solve your problem.
Friday, November 23, 2018
Recognizing Geometric Shapes in 2D Space Using Machine Learning
If you have ever searched on google, ordered food online, browsed an item online, used a messaging app or composed an email, each and every time you came across a machine learning algorithm. A lot of people are interested in learning how to apply machine learning to solve some of their own problems. CCTech has expertise in CAD and Computational Geometry, and we keep experimenting with machine learning to solve problems in geometry. In this blog, we will demonstrate how to apply machine learning to solve a simple geometrical problem of 2D conic shape recognition. Readers will be able to understand various aspects of machine learning and also learn some useful tools. We hope this would serve as a nice tutorial for those who want to build machine learning applications of their own.
Does anyone recall struggling with math problems in high-school? We are talking specifically about the problems in coordinate geometry, where you need to solve a set of equations for a curve in order to find tangents, intersections etc. There is one class of equations, that always seemed to turn up in coordinate geometry and that is the equation of conic curves, which have this general form
Equation of conic curve
This equation can be used to represent a circle, ellipse, parabola and a hyperbola.
Conic sections
"A conic section is a curve obtained by the intersection of a plane and a circular cone. Depending on the angle of the plane with respect to the cone, a conic section may be a circle, an ellipse, a parabola, or a hyperbola."
Now here's a math problem for you - "Suppose you are given a set of 10 points. How would you find out the type of conic curve that these points represent?" How would you do it? You might be thinking of writing lots of equations! That sounds like a tough problem!
Tough problem
What if we told you that there is no need to solve this problem analytically yourself (using equations), but rather you can use a machine learning algorithm "to learn the equations for identifying a conic section"
Sounds exciting, doesn't it? We'll show you how it's done.
Teach me
We will show you how to quickly recognize any conic section shape (circle, ellipse, parabola and hyperbola) from a few sets of point coordinates.
First, let's talk a bit about machine learning.
"Machine Learning is a field of study that involves techniques to get computers to learn from data progressively without being explicitly programmed. It is used for tasks that are too complex for humans to code directly. So instead, we provide a large amount of data to a machine learning algorithm and let the algorithm work it out by exploring that data and searching for a model that will achieve what the programmers have set it out to achieve."
And this is what we intend to do. We will be following a supervised learning approach to build a machine learning classifier. A supervised learning technique - is where a computer is presented with examples of inputs and their desired outputs. The goal of the computer is to learn a general formula which maps inputs to outputs.
In this blog we will show you how to create a dataset of conic curves, as well as how to train a machine learning classifier to identify curve types.
Let’s tackle this problem step-by-step.
STEP 1: Set up the environment
We need to first set up our programming environment, so we can accomplish all the steps given in this blog. Here’s what we would need:
Operating System (Windows 8/10/Linux)
Python 3.6
Pandas
Numpy
Matplotlib
Jupyter notebook
Scikit-learn
TensorFlow
Keras
Follow these instructions to set up:
First install python 3.6 from the official website. After installing python, open the command prompt and execute the following commands:
pip install jupyter
pip install pandas
pip install numpy
pip install matplotlib
pip install scikit-learn
pip install tensorFlow
pip install keras
We will be writing our code in jupyter, which is an awesome application used by data-scientists and machine learning practitioners. You may think of it as an IDE for quickly prototyping code. To start jupyter, type the following in a terminal:
jupyter notebook
Create a python 3 notebook and then you can start writing your code in the cells provided. You may refer this nice jupyter notebook tutorial to get started with jupyter.
STEP 2: Generating the Dataset
Now we will generate a dataset of a few thousand conic section curves. This dataset will consist of several columns which will be provided as inputs to our machine learning classifier. There are two types of columns in our data set, which are called feature columns and label columns. The features are the inputs to the machine learning classifier and the labels are the outputs, which the classifier will learn to predict correctly after repeated training.
This is what we want our dataset to look like:
ML Training dataset for conic shape
Generated Dataset for Different Conic Sections
Here, are our feature columns and 'shape' is our label column.
Each row in the above table is a conic curve represented by a set of 6 points (as coordinates (xi, yi)), and a string ('circle' / 'parabola' / 'ellipse' / 'hyperbola') to describe the curve type. We assert that a conic curve can be completely described by 6 points, since mathematically we need a minimum of 5 points to uniquely determine a conic shape.
We use parametric equations of these curves to generate points. Parametric equations are pretty useful for curve generation.
Parametric equations of conic shape
Parametric Equations of conic curves
Let’s code a few functions for generating points for each type of curve parametrically. Our functions will take into account orientation and position of the curves as well.
def createParabola(focal_length, centre, rotation):
    t = np.linspace(-math.pi, math.pi,100)
    x_parabola = focal_length * t**2
    y_parabola = 2 * focal_length * t
    if rotation is not None:
        x_parabola, y_parabola = rotateCoordinates(x_parabola, y_parabola, rotation) 
    x_parabola = x_parabola + centre[0]
    y_parabola = y_parabola + centre[1]
    return x_parabola, y_parabola

def createCircle(radius, centre):
    theta = np.linspace(0, 2*math.pi,100)
    x_circle = radius * np.cos(theta) + centre[0]
    y_circle = radius * np.sin(theta) + centre[1]
    return x_circle, y_circle

def createEllipse(major_axis, minor_axis, centre, rotation):
    theta = np.linspace(0, 2*math.pi,100)
    x_ellipse = major_axis * np.cos(theta) 
    y_ellipse = minor_axis * np.sin(theta) 
    if rotation is not None:
        x_ellipse, y_ellipse = rotateCoordinates(x_ellipse,y_ellipse, rotation)
    x_ellipse = x_ellipse + centre[0]
    y_ellipse = y_ellipse + centre[1]
    return x_ellipse, y_ellipse

def createHyperbola(major_axis, conjugate_axis, centre, rotation):
    theta = np.linspace(0, 2*math.pi,100)
    x_hyperbola = major_axis * 1/np.cos(theta) + centre[0]
    y_hyperbola = conjugate_axis * np.tan(theta) + centre[1]
    if rotation is not None:
        x_hyperbola, y_hyperbola = rotateCoordinates(x_hyperbola, y_hyperbola, rotation)
    x_hyperbola = x_hyperbola + centre[0]
    y_hyperbola = y_hyperbola + centre[1]
    return x_hyperbola, y_hyperbola

def rotateCoordinates(x_data, y_data, rot_angle):
    x_ = x_data*math.cos(rot_angle) - y_data*math.sin(rot_angle)
    y_ = x_data*math.sin(rot_angle) + y_data*math.cos(rot_angle)
    return x_,y_
Let’s try to visualize a few sample outputs from these functions. We will write a simple function to plot the curve points. For plotting, we will use a nice visualization tool called matplotlib. Here’s a code snippet to plot 2D points using matplotlib:
def plotter(x_data, y_data, title):
    fig = plt.figure(figsize=[10,10]) 
    plt.plot(x_data,y_data,'b--')
    plt.xlabel('X-axis',fontsize=14)
    plt.ylabel('Y-axis',fontsize=14)
    plt.ylim(-18,18)
    plt.xlim(-18,18)
    plt.axhline(y=0, color ="k")
    plt.axvline(x=0, color ="k")
    plt.grid(True)
    saveFile = title + '.svg'
    plt.savefig(saveFile)
    plt.show()
Here’s a code sample to generate and plot a curve
x,y = createParabola(focal_length= 1, centre= [10,10],rotation= math.pi/5)
get_n_samples(x,y, sample_count)
Circle euqation plot
Ellipse euqation plot
Hyperbola euqation plot
Parabola euqation plot
Yes. Its done
Now that our curve generation functions are ready, let’s generate lots of curves by varying the parameters.
We will store variations of each parameter in separate lists. The below code snippet creates a list of 100 uniformly spaced values for each parameter, in a specified interval.
# Parabola
focal_length_array = np.linspace(1, 20, 100)
centre_x_arr = np.linspace(-12, 12, 100)
centre_y_arr = np.linspace(-12, 12, 100)
rotation_array = np.linspace(2*math.pi, 100)
To define a curve, we will choose a random parameter value from each of the above parameter lists.
Once the parameters for a curve have been chosen and the curve points have been generated, we sample 6 points uniformly from the generated curve.
sample_count = 6
We will do this in a loop to generate 1000 parabolic curves!
parabola_dataset = pd.DataFrame()
for i in range(1000):
    focal_length = focal_length_array[get_random_index(len(focal_length_array))]
    centre_x = centre_x_arr[get_random_index(len(centre_x_arr))]
    centre_y = centre_y_arr[get_random_index(len(centre_y_arr))]
    rotation = rotation_array[get_random_index(len(rotation_array))]
    x,y = createParabola(focal_length= focal_length, centre= [centre_x, centre_y],rotation= rotation)
    x_, y_ = get_n_samples(x, y, sample_count)
    data = build_dataset(x_, y_, 'parabola')
    parabola_dataset = parabola_dataset.append(data, ignore_index=True)
We can do this similarly for the other curve types as well. You can refer to this notebook that contains all the code to see how the rest of the curves have been generated.
We now have a dataset of 4000 curves that contains 4 types of conic curves, created using different sets of parameters along with rotation and translation. Here are a few samples of the curves that have been generated :
Training data for parabola curve
Training data for ellipse curve
Training data for hyperbola curve
Export the data of all curves into a single csv file. We will leave this as an exercise for you.
(Hint: Pandas provides a really nice interface to do so)
STEP 3: Training a Machine Learning Algorithm
Now comes the really interesting part - training a machine learning algorithm!
We will train a neural network classifier for our problem. We choose neural networks as they are capable of learning very complex functions. We will use Tensorflow along with Keras to quickly and simply design and train neural networks.
Let’s create a new notebook and import the dataset we generated earlier. The following code snippet demonstrates how to read our dataset csv file using pandas:
data = pd.read_csv('Conic-Section_dataset.csv', index_col=False)
data= data.sample(frac=1, random_state=42).reset_index()
data.drop(['index'], 1, inplace=True)
ML Training dataset for conic shape
Let’s process out data first by converting the string labels ('circle' / 'parabola' / 'ellipse' / 'hyperbola') into integer values. Why do we need to do this? It's because the machine learning algorithm is mathematical, and strings don’t mean anything to it!
We will convert our labels into integer values. Since we have four classes, we will get four integer values (0,1,2,3). To convert to integer values, we use the LabelEncoder class from scikit-learn.
X = data.values[:,1:]
Y = data.values[:,0]
# encode class values as integers
encoder = LabelEncoder()
encoder.fit(Y)
encoded_Y = encoder.transform(Y)
# convert integers to dummy variables (i.e. one hot encoded)
dummy_y = np_utils.to_categorical(encoded_Y)
Then we convert it into "one-hot encoding". Basically, this step converts:
Y : [“parabola” , “ellipse” , “circle” , “hyperbola”]
Into this
encoded_Y : [0 , 1 , 2 , 3]
Which then becomes
dummy_Y : [1, 0, 0, 0] , [0, 1, 0, 0] , [0, 0, 1, 0] , [0, 0, 0, 1]
These are our labels, in “one-hot-encoded” form. We will use dummy_Y as label for our algorithm.
We are now ready to create our neural network model using Keras.
Let’s start off by defining the function that creates our model. To create a neural network, we will use the Sequential API of keras. We add four fully connected hidden layers with [128, 256, 64, 32] neurons respectively in each layer. After each hidden layer, we use the ReLu activation unit for adding non-linearity to the output of each layer. This helps ensure that our neural network model can learn complex patterns, and also gives a continuous, non-negative output.
Neural network training generally tend to overfit the input, which means the model could get unnecessarily complex. To control the complexity, we also add a dropout percentage after each layer. The final layer has a softmax function to produce output.
def baseline_model():
# create model
    model = Sequential()
    model.add(Dense(128, input_dim=12, activation='relu'))
    model.add(Dropout(0.2))
    model.add(Dense(256, activation='relu'))
    model.add(Dropout(0.3))
    model.add(Dense(64, activation='relu'))
    model.add(Dropout(0.5))
    model.add(Dense(32, activation='relu'))
    model.add(Dropout(0.5))
    model.add(Dense(4, activation='softmax'))
# Compile model
    Adadelta =  optimizers.Adadelta(lr = 1)
    model.compile(loss='categorical_crossentropy', optimizer=Adadelta, metrics=['accuracy'])
    return model
Finally, we are using the categorical cross entropy for computing the loss during training and an efficient optimization algorithm Adadelta for training the data set.
After compiling the model, we call the model.fit() function to start the training on our data. In the model.fit(), we specify the features and targets. We also specify that the algorithm should use 80% data for training and 20% data as unseen data(validation_split=0.2), for performing inference.
history = model.fit(x=X,y=dummy_y,validation_split=0.2,shuffle=True, epochs=200, batch_size=12)
After the model.fit() execution is complete, we obtain loss and accuracy curves for the training and validation data.
ML Train and Validation loss curves
Train and Validation loss curves
ML Train and Validation loss curves
Train and Validation accuracy curves
Looking at the curves, we seem to have achieved an accuracy of 99.38% on unseen data. This means our model has learnt to distinguish conic curves like a pro!
Beautiful results upvote
Summary and Conclusions
We were able to build a classifier that can classify any conic curve given the six coordinates of the curve as input. And we were able to achieve a solid accuracy of 99.38% in our model.
Epoch 199/200
3200/3200 - 0s 117us/step - loss: 0.0822 - acc: 0.9922 - val_loss: 0.0311 - val_acc: 0.9935
Epoch 200/200
3200/3200 - 0s 114us/step - loss: 0.0979 - acc: 0.9878 - val_loss: 0.0167 - val_acc: 0.9938
For the benefit of our readers, we have open-sourced our notebooks for data generation as well as training on github. They can be found here : cctech-labs/ml-2dshapes
As a future experiment, we will try to do this for curves and surfaces in 3-D space. Do stay tuned to our blog, and please let us know your thoughts in the comments. Thanks for reading!
Thank You
About Authors
Saurabh Varma
Saurabh is a Senior Member of Technical Staff at Centre for Computational Technologies Private Limited (CCTech), Pune. He is a Machine Learning and Deep Learning enthusiast. He holds a Bachelor's degree in Mechanical Engineering from IIIT Jabalpur.
Blog Author - Saurabh Varma
Pradyna Pawar
Pradnya is a Jr. Member of Technical Staff at Centre for Computational Technology Pvt. Ltd. (CCTech), Pune. She has holds a B.E. in Electronics and Telecommunications Engineering and an M.Tech. in VLSI and Embedded Systems. She has experience in the fields of Machine Learning, Deep Learning, and Data Analytics. In her free time, she likes to blog about food on Instagram.
Blog Author - Pradyna Pawar
Prasad Pawar
Prasad is a Junior Member of Technical Staff at Centre for Computational Technologies (CCTech), Pune. He has completed his bachelor's degree in Mechanical Engineering from the University of Pune. He is exploring cutting-edge technologies like Machine Learning, Augmented Reality along with Computational Fluid Dynamics. He is very passionate about Badminton and loves to listen to a variety of Music.
Blog Author - Prasad Pawar
Suryansh Agarwal
Suryansh is a Jr. Member of Technical Staff at Centre for Computational Technology Pvt. Ltd. (CCTech), Pune, He has interests in mathematics, machine learning, and robotics. He is enthusiastic about programming and exploring new technologies. He holds a Bachelor's degree from the Indian Institute of Information Technology Design and Manufacturing, Jabalpur in Mechanical Engineering. When he is not doing programming or reading he can be found driving his imaginary VW Beetle on the streets of Pune.
Blog Author - Suryansh Agarwal
Comments
Like what your are reading ?
Subscribe to our newsletter and get our apps/news updates earlier than others, let's get in touch.