2

I'm having my thesis "Multiple Choice Examination Checker" and I'm having a big issue about what to do with my problem. I got a picture image (a bitmap specifically) here it is, so you can see:

Box Detection using EmguCV

This is the image with the detectedbox, I will describe this:

  • This is an examination paper, 1-50 items. each number has a corresponding box(right side of the number, that serves as a container for the answer)
  • This pictures is just a sample, the number of detected boxes may vary. My approximation is it contains 150-200 detected boxes.
  • Each detectedboxes are stored in a List(MCvBOX2D) which holds the detectedboxes' size, center, etc.
  • I transferred those center coordinates in a new list List(PointF) center;
  • Each box from the image, may have 3-5 detectedboxes. as you can see there are more than one detectedboxes in each of the boxes from the image.
  • I sorted all the detectedboxes in ascending order, so I would know which will possibly be the number1, number2, and so on..

Here is some of my code, which contains the sorting of boxes.

List<PointF> center = new List<PointF>();
List<PointF> centernew = new List<PointF>();
foreach (MCvBox2D box in lstRectangles)
{
   // this code transfers every center-coordinates of detected boxes 
   // to a new list which is center
    center.Add(new PointF(box.center.X, box.center.Y));
}
// and this one sorts the coordinates in ascending order.
centernew = center.OrderBy(p => p.Y).ThenBy(p => p.X).ToList(); 
  • I'm done with the sorting part, now my problem is, since there many detected boxes in every box from the image, I would like to group the sortedlist of center-coordinates, so I could eliminate the other detectedboxes and get only one detectedbox for each number.

  • I know it's hard to understand so I'll explain more.

    Let's say my sortedlist of detectedboxes contains first five center-coordinates which are:

let's say this are the center-coordinates of each of the detectedboxes from first box of the image.

 center[0] = [ 45.39, 47.6]
 center[1] = [ 65.39, 47.6]
 center[2] = [ 45.40, 47.10]
 center[3] = [ 65.45, 47.25]
 center[4] = [ 46.01, 47.50]

and the 2nd are:

 center[5] = [ 200.39, 47.2]
 center[6] = [ 45.39, 47.2]
 center[7] = [ 45.39, 47.3]
 center[8] = [ 45.39, 47.55]
  • My goal is to organize all the sorted detectedboxes inside the list, I must be able to group all the center-coordinates that have close value with the other center, specifically their Y-coordinates.
2
  • What should be the output for your sample list with 9 items? Jan 9, 2014 at 16:52
  • My output should be only 50 detected boxes, meaning 50 center-coordinates. Those 1st and 2nd group of coordinates, are coordinates which are similar but not exact, those are center-coordinates of boxes that detected the some box. Jan 10, 2014 at 1:24

4 Answers 4

2
var rand = new Random();
var threshold = 1;
var points = new List<PointF>();

for (int i = 0; i < 20; i++)
{
    points.Add(new PointF((float) rand.NextDouble()*10, (float) rand.NextDouble()*10));
}

Console.WriteLine(points.Count);

for (int i = 0; i < points.Count(); i++)
{
    for (int j = i + 1; j < points.Count(); )
    {
        var pointHere = points[i];
        var pointThere = points[j];

        var vectorX = pointThere.X - pointHere.X;
        var vectorY = pointThere.Y - pointHere.Y;

        var length = Math.Sqrt(Math.Pow(vectorX, 2) + Math.Pow(vectorY, 2));

        if (length <= threshold)
        {
            points.RemoveAt(j);
        }
        else
        {
            j += 1;
        }
    }
}

Console.WriteLine(points.Count);
2
  • hello, i got the correct output. very excellent answer, if im not mistaken this is distance between two points? I just wonder what is that Random() code for? Jan 16, 2014 at 18:24
  • Just some example data for a complete working example. What you're after is the vector length between centers... its brute force though. If you want a "Better" solution have a look at nearest neighbor search. i.e. that will cut down the amount of points you have to check and make your code run much faster. alglib.net/other/nearestneighbors.php Jan 17, 2014 at 10:07
1

You can calculate the distance between a given point and any other point in the list. If the distance is less than half the width of a box, you can be pretty sure that it's part of the same box.

double threshold = 3.0;  // Make this whatever is appropriate

for (int i = center.Count - 1; i >= 0; --i)
    if (center.Any(p => p != center[i] && Distance(center[i], p) < threshold))
        center.Remove(center[i]);

And you could use this for your Distance() method:

private double Distance(PointF p1, PointF p2)
{
    double deltaX = Math.Abs(p1.X - p2.X);
    double deltaY = Math.Abs(p1.Y - p2.Y);

    return Math.Sqrt((deltaX * deltaX) + (deltaY * deltaY));
}
1

You could use Distinct with an custom IEqualityComparer (see MSDN).

As an example, define a class:

class BoxEqualityComparer : IEqualityComparer<MCvBox2D>
{
    private static Double Tolerance = 0.01; //set your tolerance here

    public Boolean Equals(MCvBox2D b1, MCvBox2D b2)
    {
        if (CentersAreCloseEnough(b1.Center, b2.Center))
        {
            return true;
        }
        else
        {
            return false;
        }
    }

    private Boolean CentersAreCloseEnough(PointF c1, PointF c2)
    {
        return Math.Abs(c1.X - c2.X) < Tolerance && Math.Abs(c1.Y - c2.Y) < Tolerance;
    }

}

then use the method in your code like so:

var distinctRectangles = lstRectangles.Distinct(new BoxEqualityComparer());

You are free to implement CentersAreCloseEnough(PointF c1, PointF c2) however you would like; you could use vector distance, absolute distance in x and y, etc.

-1

If you are just concerned about positions with Y coordinates, just sort by that number. If you want to sort both you can add both X and Y and use that number to sort them. Here is an example of what I meen.

    for(int i = 0; i < points.length - 1; i++)
    {
        int temp = points[i].x + points[i].y;

        for(int j = i+1; j < points.length; i++)
        {
             int temp2 = point[j].x + points[j].y;

             if(temp2 < temp)
             {
                 Point jugglePoint = points[i];
                 points[i] = points[j];
                 points[j] = jugglePoint;
             }
        }
    }
2
  • @Katianie- Hi I already sorted my points in ascending order, my problem is there are redundant points, not really redundant because they are not exactly the same. but, they are quite similar. maybe a point in difference. I want to eliminate those quite similar points and retain only one center-coordinates. Jan 10, 2014 at 1:30
  • you could try to take the difference between each point to see if its > a certain amount and if it is keep it. It would probably be a similar double for loop
    – Katianie
    Jan 10, 2014 at 14:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.