Brute force for best fit cell alignment

Problem Definition

After doing text extraction by using an OCR library, we try to find and highlight useful information.  In the following diagram, the useful information is being highlighted with a green border.  As it can be seen in the diagram the date highlighted exists more than once, but it is not aligned with the other information that were are interested into and hence producing a false positive match.

The above problem has been simplified as shown in the next diagram.  In this problem, we need to find the row which contains the most different number of colors.  Should a cell color exist in the document but not on the final row to be identified, the first occurrence of that cell color would be considered as the correct value.  Should the final row have two or more cells of the same color, only the first occurrence of that cell color on this row would be considered as the correct value. All other cells would be ignored.

The expected result would be the following:

It's important to note that these diagrams simplify the original problem shown initially.  In reality each cell would define a rectangle with its corner coordinates (top, bottom, left, right) having different values.  Each rectangle would also have different dimensions, though in general each rectangle on the same row would almost have the same height.  To determine whether two cells are on the same row or not, we make use of the top-right corner of the two cells being compared. To get the corner coordinate to fit its target, a margin of error of 1% would be added to suffice the height differentiation deficiency.

Problem Resolution

The approach taken to address this problem is via brute force.

The first step taken is that of grouping by a color all the cell coordinates.  For the same example shown above, the coordinates are shown in the format (x, y).

The next step taken was that of comparing the y-coordinate of a cell color with all other y-coordinate of all other cells colors.  When they have the same y-coordinate, we keep track that they are on the same row and move to the next color.

Iteration 1: Yellow cell (2,  1) compare with Brown cell (5, 1) - same y-coordinate and hence matched

Iteration 2: Yellow cell (2, 1)  compare with Violet cells - no matches

Iteration 3: Yellow cell (2, 1)  compare with Grey cells - no matches

Iteration 4: Yellow cell (2, 1)  compare with Green cells - no matches

Iteration 5: Yellow cell (2, 1)  compare with Orange cells - no matches

Iteration 6: Yellow cell (2, 1)  compare with Blue cells - no matches

Iteration 7: Yellow cell (2, 4)  compare with Yellow cells - no matches

Iteration etc

foreach (sourceCellColor in cellColors)

{

    foreach (sourceCellCoordinate in sourceCellColor.Coordinates)

    {

        foreach (targetCellColor in cellColors)

        {

            foreach (targetCellCoordinate in targetCellColor.Coordinates)

            {

                if (sourceCellCoordinate = targetCellCoordinate)

                {

                    sourceCellColor has a match on targetCellColor with targetCellCoordinate;

                    break loop for targetCellColor.Coordinates;

                }

            }

        }

    }

}

Optimization 1

Reducing the number of iterations.  

• On the first loop there is no need to make use of the last color as it would have already been processed and compared via one of the inner loops.
• On the inner loop there is no need to compare to currently color being processed by outside loop.  Also, already processed colors from the outside loop would have already been processed. If I already compared Yellow to Brown, there is no need to compare again Brown to Yellow.

foreach (sourceCellColor in cellColors - lastColor)

{

    foreach (sourceCellCoordinate in sourceCellColor.Coordinates)

    {

        foreach (targetCellColor in (cellColors - already or currently being processed sourceCellColor))

        {

            foreach (targetCellCoordinate in targetCellColor.Coordinates)

            {

                etc

            }

        }

    }

}

Optimization 2

Ranking colors by minimum number of occurrences.

This would be beneficial especially if one of the initial cells being compared is a best fit, as we reduce the number of iterations.  Also, eliminating processed colors would continue reduce the number of iterations.

Optimization 3

During the processing of a colors, we might be in a position that we have already found the best fit and hence there is no need for additional brute force processing.  To determine this, we need to know the number of remaining colors to be matched.  Should within the current iteration we have a total match as the renaming number of colors to be matched, then we can terminate processing.

Examples:

Iteration 1: Current color = Violet; Number of colors to be matched = 7

Iteration 2: Current color = Grey; Number of colors to be matched = 6

Iteration 3: Current color = Orange; Number of colors to be matched = 5; Using the sample data above, at this stage we would have found the best fit and processing can stop

Should the colors Grey and Violet have been inverted, we would have been able to find the best fit in the 2nd iteration.

Other notes

The logic for comparing cells isn't included here.  This involves more processing than just comparing two values.  The additional processing required is to adjust the cell coordinates due to image rotation because of imperfect document scanning.  This rotation processing consists of additional mathematical transformation that incur a performance charge.

Parallelism on a thread-safe data structure

Introduction

In this article we have generated some smalls tests on Parallelism using Dot Net Framework 4.0 with some further extensions from the previous article.  In this article we will be adding items on a list.  The list is to have an unknown initial size and without indexing.  In the previous article, data was added to a two-dimensional array with known initial size and allows for indexing.

The construct used for parallelism to produce the below tests, is the same as that used in the previous article.  The new construct that will be used will allow for different threads to add data to a shared list.  Thus this construct must ensure for race conditions, in order to avoid having two items written simultaneously in the same location and thus overwriting the first write.


Construct Details
ConcurrentBag Class


Bags are useful for storing objects when ordering doesn't matter, and unlike sets, bags support duplicates. ConcurrentBag is a thread-safe bag implementation, optimized for scenarios where the same thread will be both producing and consuming data stored in the bag.


Methodology 
The test performed was the factorial of the current iteration number and taking timing benchmarks  while adding it to the list.  The tests where performed using:

• standard sequential method, and
• parallelism.

The method used to compute the factorial in both scenarios is:

public int Factorial(int number)
{
    if (number == 0)
    {
        return 1;
    }
    else
    {
        return number * Factorial(number - 1);
    }
}


The machine used has the following specifications: 

Intel(R) Core(TM)2 CPU 6400 @ 2.16, 2.14 GHz, 1.00GB of RAM

Results

These are the results achieved (time shown is in seconds):

                       10       100     1000     10000 12000

Sequential       0      0       0.01        1.38           1.99

Parallel 0.03   0.02    0.03        0.79           1.31

Conclusions
As per the results produced, it can be concluded that the best performance was achieved using parallelism.  Unfortunately, I could not perform more tests with larger iterations, since a StackOverflowException was being given.

Code
Below is the code for all the mentioned above methods using C#:

public List GenerateNumbersListSequentially(int size)
{
    List numbers = new List();

    for (int x=0; x
    {
        numbers.Add(Factorial(x));
    }

    return numbers;
}


public List GenerateNumbersListParallel(int size)
{
    ConcurrentBag numbers = new ConcurrentBag();

    Parallel.For(0, size, x =>
    {
        numbers.Add(Factorial(x));
    });

    return numbers.GetEnumerator() as List;
}