Brute Force Seam Carving

Brute Force Seam Carving

The Problem: Given a 2 dimensional array of with some intensity values (a grey-scale image, for example), find the the minimum, vertical path through the matrix that minimizes the intensities withdrawn.

A particular cell in the matrix [i, j] has the option can only explore at most its three closest neighbors. For example, a cell on the left, center, and right end of the matrix have the following exploration options:

left				center				right
[r, c]				[r,c]				[r,c]
[r+1,c]	[r+1, c+1]		[r+1,c-1]	[r+1,c]	[r+1,c+1]		[r+1, c-1]	[r+1,c]

Instructions: Use the brute force approach for implementation, and then explain, but not implement, a linear time strategy.

Implementation:

#define NUM_BASE_CHILD 3
#define NUM_EDGE_CHILD 2

struct Node {
    Node(const int act_val, int accum_val, const int r, const int c, const int num_child, Node *parent)
        : actual_val(act_val), r(r), c(c), accum_val(accum_val), parent(parent) {

        children.reserve(num_child);
        for (int i = 0; i < num_child; i++) {
            children.push_back(nullptr);
        }
    }

    const int r, c;
    const int actual_val;
    int accum_val;

    vector<Node*> children;
    Node *parent;
};

class Nary_tree {
public:
    Nary_tree(const vector<vector<int>> &m)
        : matrix(m) {
        root = new Node(INT_MIN, INT_MIN, INT_MIN, INT_MIN, 0, nullptr);
    }

    void create_bf_tree()
    {
        // initialize root with child nodes
        int r = 0;
        for (int c = 0; c < matrix.size(); c++) {
            if (c > 0 && c > matrix.size())
                root->children.push_back(new Node(matrix[r][c], matrix[r][c], r, c, NUM_BASE_CHILD, root));
            else
                root->children.push_back(new Node(matrix[r][c], matrix[r][c], r, c, NUM_EDGE_CHILD, root));
        }

        for (int c = 0; c < matrix.at(0).size(); c++) {
            create_bf_tree_rec(root->children[c]);
        }
    }

    vector<Node*> backtrack_minimum_path()
    {
        vector<Node*> min_path;

        Node *iter = *min_element(leaf_nodes.begin(), leaf_nodes.end(), 
            [](const Node* l, const Node* r) {
            return l->accum_val < r->accum_val;
        });

        while (iter->parent != nullptr) {
            min_path.push_back(iter);
            iter = iter->parent;
        }

        return min_path;
    }

    void print_attributes(vector<Node*> &stuff)
    {
        for (Node *n : stuff) {
            cout << setw(21) << "Row value: " << n->r << endl;
            cout << setw(21) << "Col value: " << n->c << endl;
            cout << setw(21) << "Actual value: " << n->actual_val << endl;
            cout << setw(21) << "Accumulated value: " << n->accum_val << endl;
            cout << endl;
        }
        cout << endl;
    }

    void pre_order_traversal()
    {
        pre_order_traversal_rec(root);
    }

private:
    const vector<vector<int>> matrix;
    vector<Node*> leaf_nodes;
    Node *root;

    // tree is built in a preorder fashion
    void create_bf_tree_rec(Node *parent)
    {
        // | - center - |
        if (parent->c > 0 && parent->c < matrix.at(0).size() - 1 && parent->r < matrix.size() - 1) {
            for (int i = 0; i < NUM_BASE_CHILD; i++) {
                int new_r = parent->r + 1;
                int new_c = parent->c + i - 1;
                int sum_val = parent->accum_val +
                    matrix[new_r][new_c];
                Node *temp = new Node(matrix[new_r][new_c], sum_val, new_r, new_c, NUM_BASE_CHILD, parent);
                create_bf_tree_rec(temp);

                // create link and 
                // check for leaf node for later processing
                parent->children.push_back(temp);

                if (parent->r == matrix.size() - 2) {
                    leaf_nodes.push_back(temp);
                }
            }
        }
        // | - left end
        else if (parent->c == 0 && parent->r < matrix.size() - 1) {
            for (int i = 0; i < NUM_EDGE_CHILD; i++) {
                int new_r = parent->r + 1;
                int new_c = parent->c + i;
                int sum_val = parent->accum_val +
                    matrix[new_r][new_c];
                Node *temp = new Node(matrix[new_r][new_c], sum_val, new_r, new_c, NUM_EDGE_CHILD, parent);
                create_bf_tree_rec(temp);

                parent->children.push_back(temp);

                if (parent->r == matrix.size() - 2) {
                    leaf_nodes.push_back(temp);
                }
            }
        }
        // right end - |
        else if (parent->c == matrix.at(0).size() - 1 && parent->r < matrix.size() - 1) {
            for (int i = 0; i < NUM_EDGE_CHILD; i++) {
                int new_r = parent->r + 1;
                int new_c = parent->c + i - 1;
                int sum_val = parent->accum_val +
                    matrix[new_r][new_c];
                Node *temp = new Node(matrix[new_r][new_c], sum_val, new_r, new_c, NUM_EDGE_CHILD, parent);
                create_bf_tree_rec(temp);

                parent->children.push_back(temp);

                if (parent->r == matrix.size() - 2) {
                    leaf_nodes.push_back(temp);
                }
            }
        }
    }

    void pre_order_traversal_rec(Node *root)
    {
        if (root) {
            cout << root->actual_val << ", ";
            for (Node *i : root->children) {
                pre_order_traversal_rec(i);
            }
        }
    }

};

int main()
{
    vector<vector<int>> matrix = { { 1, 3, 0},
                                   { 2, 8, 9 }, 
                                   { 5, 2, 6 }, };

    Nary_tree mytree(matrix);
    mytree.create_bf_tree();
    vector<Node*> bc = mytree.backtrack_minimum_path();
    mytree.print_attributes(bc);

    mytree.pre_order_traversal();

    getchar();
}

The Idea:

The root of our tree in this case, is just an ideal node that initiate the search space. To begin, what we want to is to have the number of children of the tree equal to the width of the matrix. That way, we have the option of exploring any of the cells beginning at the top of the matrix.

It then follows that every sub tree from each of the children aforementioned can explore its 3 or 2 options. Over time, we will accumulate all the possible options, and then leaf nodes at the bottom will express the total values collected along the way. The terminating condition is of course, when the tree reached the bottom of the matrix. Although it could be improved within my code, I tree possible explorations patterns clear within my code.

To obtain the minimum seam carving, we then can back trace from the minimum leaf node back up towards the root. Implementation wise, the important thing to understand was to create a node before linking back it as a child when a recursion cycle completes.

Dynammic Programming Approach

Given a matrix, iterate through all elements of the matrix row by row, beginning from row 1, and adjust each cell value to be equal to the minimum value from its 3 or 2 closest neighbors + 1 itself, depending on where it is.

[r-1,c]	[r-1, c+1]		[r-1,c-1]	[r-1,c]	[r-1,c+1]		[r-1, c-1]	[r-1,c]
[r, c]				[r,c]				[r,c]
left				center				right

And that's it. Now from beginning from minimum element from the bottom of the matrix, we move towards the top by selecting the minimum of its 2 or 3 options.

For example

	matrix				solution
1	3	0		1	3	0
2	8	9	=	3	8	4
5	2	6		8	5	14

Why this works

We can think of skipping the first row because the values themselves are already the minimum - they have nothing to reference from. The second row has the option of selecting the minimum most path that will accumulate onto itself, ignore 1 or 2 paths in the process. Consider the 2xn matrix. Its will follow that the second row in said matrix will contain the minimum accumulated path, since each element in said row will select the only (assuming no duplicates) valid path that minimizes its cost. And in the end, the minimum node is selected in the end.

Now consider the n+1 row. We can think of this as still being a 2xn matrix, by just shifting our focus on the next set of 2xn elements in the matrix. This assumption is valid, because all we have done is replace the previous values from its accumulated values. In the end, it is still a 2xn matrix with different values. Therefore, we can treat every nth + 1 row the same way we've treated the previous row.