Stack Memory vs Heap Memory in C/C++

Lately i have been working on something that required me to read text files having approx 200,00,000 lines using C.
Using the normal method( int a[200000000] ) of declaring an integer array with 200,00,000 elements always ends up in a Segmentation Fault(Memory Overflow).

Answer to this problem was fairly trivial.

There are typically two kinds of memory associated with programs, Stack Memory and Heap Memory.

Stack Memory

This type of memory stores all the local variables and the function calls made in a program.

Normal variable declarations like,

int a;
int b[5];

happen in Stack Memory during compile time.

Stack Memory is generally small in size(usually less than 8MB).

Small size of the Stack Memory leads to memory overflow in situations where we try to use large amount of space(declare really large arrays or an array of a structure) or in recursive programs where the depth of recursion becomes really large( because function calls are also stored in the Stack Memory) and hence we get a Segmentation Fault.

Heap Memory 

Heap Memory on the other hand is used in case of dynamic allocations( mallocs ) like,

int *a = (int*)malloc(length*sizeof(int));

Size of the Heap Memory is only limited by the size of the RAM and the swap memory. Memory allocation happens at runtime.

This is like a free pool of memory for programs from which they can request some space for their use and then put it back in the pool( using free() ).
Heap memory is mostly used in situations where large amount of memory is needed(when Stack Memory is not enough).

Example comparing Stack and Heap Memory

Let us try to declare an integer array with 108 elements.

1) Normal Declaration.

int a[100000000];

error

It reports an error saying “array size is too large”. Because Stack Memory does not have enough space to allocate to this array.

2) Dynamic Allocation

int *a;
a = (int*)malloc(100000000*sizeof(int));

This piece of code executes successfully without any errors. The array was allocated space in the Heap Memory( malloc ).

A good practice is to free up the used Heap Space so that eventually you dont run out of the Heap Space too.

int *a;
a = (int*)malloc(100000000*sizeof(int));
free(a);

 
 

To wrap-up, Stack Memory stores local variables and function calls and is limited in space. Heap Memory stores the dynamically allocated data, used when large amount of memory is needed.
 

Communicating with Arduino using C/C++

arduino

Hello Everyone

This post is on “How to communicate with Arduino using C/C++”.

I basically have an array of integers from my C/C++ code which i need to send to an Arduino. I need to communicate between C/C++ and Arduino

Before we actually see how this is done, we should know a little about how are actually devices handled in Linux.
Under Linux and UNIX each and every hardware device is treated as a file. They are special files located in the /dev folder in your system which allow us to access the hardware directly.

Like any other normal file in our computer we can read/write to these device files(which means reading or writing to the device itself). That is pretty much how the OS also does it on a primitive level. It opens the file associated with the device it has to use and then reads or writes to it accordingly.

Arduino boards are also handled in the same way. We will read/write to the device file of our Arduino.

First, we need to identify the device file for our arduino.

  • Go to the tools menu and look for Serial Port submenu.
  • There it will show you the list of device files(Serial Ports). For Arduino Duemilanove it is /dev/ttyUSB0(file name can change if it is already in use), for Arduino UNO it will be /dev/ttyACM0. Select a file from this menu which will be used for communication.

Now, there are 2 parts to this problem, the C code and the Arduino code.

  • C code will send data
  • Arduino code will receive data.

C code

int main()
{
    int data[] = {10,5,13};  //Random data we want to send
    FILE *file;
    file = fopen("/dev/ttyUSB0","w");  //Opening device file
    int i = 0;
    for(i = 0 ; i < 3 ; i++)
    {
        fprintf(file,"%d",data[i]); //Writing to the file
        fprintf(file,"%c",','); //To separate digits
        sleep(1);
    }
    fclose(file);
}

Explanation.

  • We have an array of integers and we want to send this array to our arduino. First we open our arduino device file which is /dev/ttyUSB0.
    int data[] = {10,5,13};  //Random data we want to send
    FILE *file;
    file = fopen("/dev/ttyUSB0","w");  //Opening device file
  • Next we write each element of the array to the file using a simple for loop, after writing each element we add a comma(‘,‘) to separate elements in our file.
    int i = 0;
    for(i = 0 ; i < 3 ; i++)
    {
        fprintf(file,"%d",data[i]); //Writing to the file
        fprintf(file,"%c",','); //To separate digits
        sleep(1);
    }
    fclose(file);

Next thing is to read this data through an arduino.

Arduino Code

void setup()
{
    Serial.begin(9600);
}

int calc()
{
    int num=0,x=0;

    for(x;x<=j;x++)
          num=num+(buff[x]-48)*pow(10,j-x);

    return num;
}

int input,num;
int buff[5];
int j=-1;

void loop()
{
    if(Serial.available()>0)
    {
        input=Serial.read();

        if(input==',')
        {
            num=calc();
            j=-1;
            Serial.println(num);
        }
        else
        {
            j++;
            buff[j]=input;
        }
    }
}

Explanation

  • First we setup the Serial port in void setup()(line 3).
  • After setting it up, we have to start reading, now in our C code we wrote integer values to our file
    fprintf(file,"%d",data[i]);
    

    But our arduino will read them as characters, so we need to read characters and convert them back to our original number.

  • So in void loop() we keep on reading data(which is nothing but our integers converted to characters) and store them in an array(buff) until we read a comma (‘,‘) . comma was used to separate digits(line 10 of our C code).
    input=Serial.read();
    
    if(input==',')
    {
        num=calc();
        j=-1;
        Serial.println(num);
    }
    else
    {
        j++;
        buff[j]=input;
    }
    

    As soon as we read a comma we call calc() where we convert the read characters back to the integer.

  • In calc() we subtract 48 from the ascii value of the character, multiply it with its place value raised to 10 and return the final integer num.
    for(x;x<=j;x++)
        num=num+(buff[x]-48)*pow(10,j-x);
    
  • Repeat the process until all the data has been read.

Finally, we were able to send an array from C/C++ to our arduino.

This was a very basic way of communicating, many better techniques can also be used.

SuDoKu!

Hello Everyone!

So, this is my first blog post!

Here I’ll talk about a very simple app that i tried to make.

It is a Sudoku Grabber.
It takes an image as the input and extracts the Sudoku and the individual digits from the image.

I’ll start by describing the different techniques i have used and then a step-by-step explanation of my algorithm.

The basic technique used is the application of contours in an image.
Simply put Contours are nothing but boundaries of a particular pattern. Identification of the different connected components in an image.
Say for example the image shown below has a circle , a square and some text. The second image shows us the different contours in that image. It has Identified the circle , the square and the different alphabets separately(White parts in the second image are contours).

Circle , Square , Text
Circle , Square , Text
Contours
Contours

So, we will basically extract the different contours in our input image and then try to identify the correct contour that represents our SuDoKu grid. For this I have made an assumption that the contour with the largest area will be our grid. It is a safe assumption to make because anyone would focus on the SuDoKu more for our purpose.

Let’s start!

  1. Prepare the Image.
    First apply an adaptive threshold on the image.
    Adaptive Threshold forms a binary version of the image, which will be used for finding the contours in the image. Binary Images are also easy to operate on.

    Mat thresh(Mat img)
    {
    cvtColor(img,img,CV_BGR2GRAY);
    Mat img_t=Mat::zeros(img.size(),CV_8UC3);
    adaptiveThreshold(img,img_t,255,ADAPTIVE_THRESH_MEAN_C,THRESH_BINARY_INV,5,10);
    return img_t;
    }

    The above code takes an input image converts it to a gray scale image first and then thresholds the image.

    Adaptive Threshold
    Adaptive Threshold
  2. Extract the Grid.

    Next
    step is to extract the grid from the thresholded image.
    This is where we find contours in our image.

    Mat grid_extract(Mat img)
    {
      int index;
      double max;
      Mat grid;
      grid=Mat::zeros(img.size(),CV_8UC1);
      vector<vector<Point> > contour;
      vector<Vec4i> h;
      vector<Point> req;
    
      findContours(img,contour,h,CV_RETR_TREE,CV_CHAIN_APPROX_SIMPLE,Point(0,0));
    

    The above code snippet we initialize a new Mat type Image and a vector of vectors which will store our contours.

    We actually find contours in line 11.
    After finding the contours we find out the contour with the maximum area.

      max=contourArea(contour[0]);
      for(int i=0;i<contour.size();i++)
      {
        double temp;
        temp=contourArea(contour[i]);
        if(max<temp)
        {
          max=temp;
          index=i;
          req=contour[i];
        }
      }
    

    Displaying the grid.

      drawContours(grid,contour,index,Scalar(255,255,255),CV_FILLED,8,h);
      namedWindow("Grid",0);
      imshow("Grid",grid);
      waitKey(0);
      return grid(boundingRect(req));
    }
    

    Extracted Grid
    Extracted Grid
  3. Extracting Digits from the Grid.After having extracted the grid from the given image, we now have to extract the digits.This is a two step process.
    From the grid first remove the Grid Lines and then extract the digits.

    1. Removing Grid Lines. Hough Transformation is a very good way of detecting shapes(lines , circles….) in an image. Using this we will detect grid lines in our image and remove them.

      After detecting lines in our grid(using Hough Transform) we will iterate over each line one by one and paint the line black. We are painting our lines black to merge them with the background(which is black after Adaptive Thresholding), which is as good as removing them from our image.
      //Function to remove the lines from the grid(To seperate out digits from the grid)
      Mat hough(Mat img)
      {
      	vector<Vec4i> lines;
      	HoughLinesP(img,lines,1,CV_PI/180,100,30,10);
      	for(int i=0; i<lines.size();i++)
      	{
      		Vec4i l=lines[i];
      		line(img,Point(l[0],l[1]),Point(l[2],l[3]),Scalar(0,0,0),10,CV_AA);
      	}
      	imshow("Digits",img);
      	waitKey(0);
      	return img;
      }
      

      After this operation parts we are left with only the digits.

      After Hough Transformation
      After Hough Transformation
    2. Extracting Digits. To extracts digits again we will use contours. We will again find contours in our image.
      Contours that we get this time will be our digits only.

      void digit_extract(Mat img)
      {
      	Mat digit;
      	vector<vector<Point> > contour;
      	vector<Vec4i> h;
      
      	findContours(img,contour,h,CV_RETR_TREE,CV_CHAIN_APPROX_SIMPLE,Point(0,0));
      	for(int i=0;i<contour.size();i++)
      	{
      		vector<Point> temp;
      		temp=contour[i];
      		img(boundingRect(temp)).copyTo(digit);
      		namedWindow("Digit",0);
      		imshow("Digit",digit);
      		waitKey(500);
      	}
      }
      

      To operate on the digits separately(like digit recognition…) we can set a ROI in our image(Line 12).

      2
      2(Scaled UP image)

      3
      3(Scaled UP image)

Finally we now have the digits extracted.🙂

To further build upon this we can actually solve the puzzle using the extracted information.

🙂
Salil