How to group near coordinates

Question

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:

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.

Answer 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.

Answer 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);

Answer 3

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));
}

Answer 4

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;
             }
        }
    }