Tag: Hough transform

I like to use my favourite binarization method for cleaning up the image:

 – First apply a gaussian blur to blur the image a bit to get rid of random dots

 – Use adaptive thresholding to set each pixel to black or white

 cv::Size size(3,3);  
 cv::GaussianBlur(img,img,size,0);  
 adaptiveThreshold(img, img,255,CV_ADAPTIVE_THRESH_MEAN_C, CV_THRESH_BINARY,75,10);  
  cv::bitwise_not(img, img);

We get a nice clean image with distinct shapes marked in white. However, we do get a few dots of white but they shouldn’t affect anything.

Use a probabilistic Hough line detection to find the sides of the rectangle. It works by going to every point in the image and checking if a line exists for all the angles. This is the most expensive operation in the whole process because it has to check every point and angle.

 cv::Mat img2;  
  cvtColor(img,img2, CV_GRAY2RGB);  
  vector<Vec4i> lines;  
  HoughLinesP(img, lines, 1, CV_PI/180, 80, 400, 10);  
  for( size_t i = 0; i < lines.size(); i++ )  
  {  
   Vec4i l = lines[i];  
   line( img2, Point(l[0], l[1]), Point(l[2], l[3]), Scalar(0,0,255), 3, CV_AA);   
  }

From: http://opencv-code.com/tutorials/automatic-perspective-correction-for-quadrilateral-objects/

However, we need to sort the points from top left to bottom right:

 bool comparator(Point2f a,Point2f b){  
  return a.x<b.x;  
  }  
 void sortCorners(std::vector<cv::Point2f>& corners, cv::Point2f center)  
 {  
   std::vector<cv::Point2f> top, bot;  
   for (int i = 0; i < corners.size(); i++)  
   {  
     if (corners[i].y < center.y)  
       top.push_back(corners[i]);  
     else  
       bot.push_back(corners[i]);  
   }  
  sort(top.begin(),top.end(),comparator);  
  sort(bot.begin(),bot.end(),comparator);  
   cv::Point2f tl = top[0].x;  
   cv::Point2f tr = top[top.size()-1];  
   cv::Point2f bl = bot[0];  
   cv::Point2f br = bot[bot.size()-1];  
   corners.clear();  
   corners.push_back(tl);  
   corners.push_back(tr);  
   corners.push_back(br);  
   corners.push_back(bl);  
 }  
 // Get mass center  
  cv::Point2f center(0,0);  
  for (int i = 0; i < corners.size(); i++)  
  center += corners[i];  
  center *= (1. / corners.size());  
  sortCorners(corners, center);

At first I used a minimum area rectangle for extracting the region and cropping it but i got a slanted image. Because the picture was taken at an angle, the rectangle we took a picture of, has become a trapezoid. However, if you’re using a scanner, than this shouldn’t be too much an issue.

However, we can fix this with a perspective transform and OpenCV supplies a function for doing so.

 // Get transformation matrix  
  cv::Mat transmtx = cv::getPerspectiveTransform(corners, quad_pts);  
  // Apply perspective transformation  
  cv::warpPerspective(img3, quad, transmtx, quad.size());

We use Hough transform to find all the circles using a provided function for detecting them.

Now that we have the valid circles we should sort them into rows and columns. We can check if two circles are in a row with a simple test:
y1 = y coordinate of centre of circle 1
y2 = y coordinate of centre of circle 2
r = radius
y2-r > y1 and y2+r<y1
If two circles pass this test, then we can say that they are in the same row. We do this to all the circle until we have figure out which circles are in which rows.Row is an array of data about each row and index. The double part of the pair is the y coord of the row and the int is the index of arrays in bubble (used for sorting).

 vector<vector<Vec3f> > bubble;  
 vector<pair<double,int> > row;  
 for(int i=0;i<circles.size();i++){  
  bool found = false;  
  int r = cvRound(circles[i][2]);   
   int x = cvRound(circles[i][0]);  
   int y= cvRound(circles[i][1]);  
  for(int j=0;j<row.size();j++){  
 int y2 = row[j].first;  
   if(y-r<y2&&y+r>y2){  
   bubble[j].push_back(circles[i]);  
   found = true;  
   break;  
   }  
  }  
  if(!found){  
   int l = row.size();  
   row.push_back(make_pair(y,l));  
   vector<Vec3f> v;  
   v.push_back(circles[i]);  
   bubble.push_back(v);  
  }  
  found = false;  
  }

Then sort the rows by y coord and inside each row sort by x coord so you will have a order from top to bottom and left to right.

bool comparator2(pair<double,int> a,pair<double,int> b){  
  return a.first<b.first;  
 }  
 bool comparator3(Vec3f a,Vec3f b){  
  return a[0]<b[0];  
 }  
 ....  
 sort(row.begin(),row.end(),comparator2);  
 for(int i=0;i<bubble.size();i++){  
  sort(bubble[i].begin(),bubble[i].end(),comparator3);  
 }

7. Check bubble

Now that we have each circle sorted, in each row we can check if the density of pixels is 30% or higher which will indicate that it is filled in.

We can use countNonZero to count the filled in pixels over the area of the region.

In each row, we look for the highest filled density over 30% and it will most likely be the answer that is highlighted. However, if none are found then it is blank.

Source code here: https://github.com/ayoungprogrammer/MultipleChoiceScanner