How to merge a lot of square images via OpenCV?

Question

How can I merge images like below into a single image using OpenCV (there can be any number of them both horizontally and vertically)? Is there any built-in solution to do it?

Additional pieces:

Answer 1

Well, it seems that I finished the puzzle:

Main steps:

1. Compare each pair of images (puzzle pieces) to know the relative position (findRelativePositions and getPosition).
2. Build a map knowing the relative positions of the pieces (buildPuzzle and builfForPiece)
3. Create the final collage putting each image at the correct position (final part of buildPuzzle).

Comparison between pieces A and B in step 1 is done checking for similarity (sum of absolute difference) among:

• B is NORTH to A: A first row and B last row;
• B is SOUTH to A: A last row and B first row;
• B is WEST to A : A last column and B first column;
• B is EAST to A : A first column and B last column.

Since images do not overlap, but we can assume that confining rows (columns) are quite similar, the key aspect is to use a (ad-hoc) threshold to discriminate between confining pieces or not. This is handled in function getPosition, with threshold parameter threshold.

Here the full code. Please let me know if something is not clear.

#include <opencv2\opencv.hpp>
#include <algorithm>
#include <set>

using namespace std;
using namespace cv;

enum Direction
{
    NORTH = 0,
    SOUTH,
    WEST,
    EAST
};


int getPosition(const Mat3b& A, const Mat3b& B, double& cost)
{
    Mat hsvA, hsvB;
    cvtColor(A, hsvA, COLOR_BGR2HSV);
    cvtColor(B, hsvB, COLOR_BGR2HSV);

    int threshold = 1000;

    // Check NORTH
    Mat3b AN = hsvA(Range(0, 1), Range::all());
    Mat3b BS = hsvB(Range(B.rows - 1, B.rows), Range::all());

    Mat3b AN_BS;
    absdiff(AN, BS, AN_BS);
    Scalar scoreN = sum(AN_BS);

    // Check SOUTH
    Mat3b AS = hsvA(Range(A.rows - 1, A.rows), Range::all());
    Mat3b BN = hsvB(Range(0, 1), Range::all());

    Mat3b AS_BN;
    absdiff(AS, BN, AS_BN);
    Scalar scoreS = sum(AS_BN);

    // Check WEST
    Mat3b AW = hsvA(Range::all(), Range(A.cols - 1, A.cols));
    Mat3b BE = hsvB(Range::all(), Range(0, 1));

    Mat3b AW_BE;
    absdiff(AW, BE, AW_BE);
    Scalar scoreW = sum(AW_BE);

    // Check EAST
    Mat3b AE = hsvA(Range::all(), Range(0, 1));
    Mat3b BW = hsvB(Range::all(), Range(B.cols - 1, B.cols));

    Mat3b AE_BW;
    absdiff(AE, BW, AE_BW);
    Scalar scoreE = sum(AE_BW);

    vector<double> scores{ scoreN[0], scoreS[0], scoreW[0], scoreE[0] };
    int idx_min = distance(scores.begin(), min_element(scores.begin(), scores.end()));
    int direction = (scores[idx_min] < threshold) ? idx_min : -1;
    cost = scores[idx_min];
    return direction;
}

void resolveConflicts(Mat1i& positions, Mat1d& costs)
{
    for (int c = 0; c < 4; ++c)
    {
        // Search for duplicate pieces in each column

        set<int> pieces;
        set<int> dups;

        for (int r = 0; r < positions.rows; ++r)
        {
            int label = positions(r, c);
            if (label >= 0)
            {
                if (pieces.count(label) == 1)
                {
                    dups.insert(label);
                }
                else
                {
                    pieces.insert(label);
                }
            }
        }

        if (dups.size() > 0)
        {
            int min_idx = -1;
            for (int duplicate : dups)
            {
                // Find minimum cost position
                Mat1d column = costs.col(c);
                min_idx = distance(column.begin(), min_element(column.begin(), column.end()));

                // Keep only minimum cost position
                for (int ir = 0; ir < positions.rows; ++ir)
                {
                    int label = positions(ir, c);
                    if ((label == duplicate) && (ir != min_idx))
                    {
                        positions(ir, c) = -1;
                    }
                }
            }
        }
    }
}

void findRelativePositions(const vector<Mat3b>& pieces, Mat1i& positions)
{
    positions = Mat1i(pieces.size(), 4, -1);
    Mat1d costs(pieces.size(), 4, DBL_MAX);

    for (int i = 0; i < pieces.size(); ++i)
    {
        for (int j = i + 1; j < pieces.size(); ++j)
        {
            double cost;
            int pos = getPosition(pieces[i], pieces[j], cost);

            if (pos >= 0)
            {
                if (costs(i, pos) > cost)
                {
                    positions(i, pos) = j;
                    costs(i, pos) = cost;
                    switch (pos)
                    {
                    case NORTH:
                        positions(j, SOUTH) = i;
                        costs(j, SOUTH) = cost;
                        break;
                    case SOUTH:
                        positions(j, NORTH) = i;
                        costs(j, NORTH) = cost;
                        break;
                    case WEST:
                        positions(j, EAST) = i;
                        costs(j, EAST) = cost;
                        break;
                    case EAST:
                        positions(j, WEST) = i;
                        costs(j, WEST) = cost;
                        break;
                    }
                }
            }
        }
    }

    resolveConflicts(positions, costs);
}


void builfForPiece(int idx_piece, set<int>& posed, Mat1i& labels, const Mat1i& positions)
{
    Point pos(-1, -1);

    // Find idx_piece on grid;
    for (int r = 0; r < labels.rows; ++r)
    {
        for (int c = 0; c < labels.cols; ++c)
        {
            if (labels(r, c) == idx_piece)
            {
                pos = Point(c, r);
                break;
            }
        }
        if (pos.x >= 0) break;
    }

    if (pos.x < 0) return;


    // Put connected pieces
    for (int c = 0; c < 4; ++c)
    {
        int next = positions(idx_piece, c);
        if (next > 0)
        {
            switch (c)
            {
            case NORTH:
                labels(Point(pos.x, pos.y - 1)) = next;
                posed.insert(next);
                break;
            case SOUTH:
                labels(Point(pos.x, pos.y + 1)) = next;
                posed.insert(next);
                break;
            case WEST:
                labels(Point(pos.x + 1, pos.y)) = next;
                posed.insert(next);
                break;
            case EAST:
                labels(Point(pos.x - 1, pos.y)) = next;
                posed.insert(next);
                break;
            }
        }
    }
}


Mat3b buildPuzzle(const vector<Mat3b>& pieces, const Mat1i& positions, Size sz)
{
    int n_pieces = pieces.size();
    set<int> posed;
    set<int> todo;
    for (int i = 0; i < n_pieces; ++i) todo.insert(i);

    Mat1i labels(n_pieces * 2 + 1, n_pieces * 2 + 1, -1);

    // Place first element in the center
    todo.erase(0);
    labels(Point(n_pieces, n_pieces)) = 0;
    posed.insert(0);
    builfForPiece(0, posed, labels, positions);

    // Build puzzle starting from the already placed elements
    while (todo.size() > 0)
    {
        auto it = todo.begin();
        int next = -1;
        do
        {
            next = *it;
            ++it;
        } while (posed.count(next) == 0 && it != todo.end());


        todo.erase(next);
        builfForPiece(next, posed, labels, positions);
    }

    // Posed all pieces, now collage!

    vector<Point> pieces_position;
    Mat1b mask = labels >= 0;
    findNonZero(mask, pieces_position);
    Rect roi = boundingRect(pieces_position);

    Mat1i lbls = labels(roi);
    Mat3b collage(roi.height * sz.height, roi.width * sz.width, Vec3b(0, 0, 0));

    for (int r = 0; r < lbls.rows; ++r)
    {
        for (int c = 0; c < lbls.cols; ++c)
        {
            if (lbls(r, c) >= 0)
            {
                Rect rect(c*sz.width, r*sz.height, sz.width, sz.height);
                pieces[lbls(r, c)].copyTo(collage(rect));
            }
        }
    }

    return collage;
}


int main()
{
    // Load images

    vector<String> filenames;
    glob("D:\\SO\\img\\puzzle*", filenames);

    vector<Mat3b> pieces(filenames.size());

    for (int i = 0; i < filenames.size(); ++i)
    {
        pieces[i] = imread(filenames[i], IMREAD_COLOR);
    }

    // Find Relative positions
    Mat1i positions;
    findRelativePositions(pieces, positions);

    // Build the puzzle
    Mat3b puzzle = buildPuzzle(pieces, positions, pieces[0].size());

    imshow("Puzzle", puzzle);
    waitKey();

    return 0;
}

NOTE

1. No, there is no built-in solution to perform this. Image stitching won't work since the images are not overlapped.
2. I cannot guarantee that this works for every puzzle, but should work for the most.
3. I probably should have worked this couple of hours, but it was fun :D

---

EDIT

Adding more puzzle pieces generates wrong results in the previous code version. This was due the (wrong) assumption that at most one piece is good enough to be connected with a given piece.

Now I added a cost matrix, and only the minimum cost piece is saved as neighbor of a given piece. I added also a resolveConflicts function that avoid that one piece can be merged (in non-conflicting position) with more than one piece.

This is the result adding more pieces:

---

UPDATE

Considerations after increasing the number of puzzle pieces:

• This solution it's dependent on the input order of pieces, since it turns out it has a greedy approach to find neighbors.
• While searching for neighbors, it's better to compare the H channel in the HSV space. I updated the code above with this improvement.
• The final solution needs probably some kind of global minimization of the of a global cost matrix. This will make the method independent on the input order. I'll be back on this asap.