Fun with OpenCV: Carving Seams

Written on March 4, 2018

NOTE: This post is automatically translated from Farsi using GPT 5.5

There are many things you can do with the OpenCV library. From basic image operations to machine learning. In this post — which will no longer be the middle post of a trilogy! — I will review how to use OpenCV to reduce the dimensions of an image while removing the smallest amount of data. In image processing literature, this is called seam carving.

In this post, we want to do exactly that to this photo of penguins:

The human eye is sensitive to changes within an image. In other words, preserving the data inside an image means preserving the parts of the image whose derivatives are larger than those of the other points:

D (X) = | S_{x} * X | + | S_{y} * X |

The operator $*$ represents convolution, and $S_{x}$ and $S_{y}$ are the Sobel derivative kernels in the horizontal and vertical directions:

S_{x} = [\begin{matrix} - 1 & 0 & 1 \\ - 2 & 0 & 2 \\ - 1 & 0 & 1 \end{matrix}], S_{y} = [\begin{matrix} - 1 & - 2 & - 1 \\ 0 & 0 & 0 \\ 1 & 2 & 1 \end{matrix}]

The output of the function $D$ in seam carving is called the energy matrix. So the first step for performing seam carving is writing the function $D$ , or the energy-computation function:

cv::Mat computeEnergyMatrix(const cv::Mat& _image){    cv::Mat sobelX, sobelY;    cv::Sobel(_image, sobelX, CV_32F, 1, 0);    cv::Sobel(_image, sobelY, CV_32F, 0, 1);    cv::Mat energyMatrix = cv::abs(sobelX) + cv::abs(sobelY);    cv::transform(energyMatrix, energyMatrix, cv::Matx13f(1,1,1));    return energyMatrix;}

The transform function in OpenCV is intended for performing operations on image channels, and here I used it to sum the channel values of the derivative result.

When we apply this function to an input image, it assigns a weight to every point in the image that represents the L1 norm of the image derivative at that point. By computing the energy matrix, we have assigned an importance weight to every point in the image.

Sample energy matrix — Energy matrix of the penguin photo

Well, now suppose we only want to reduce the width of the image. To do this, we need to remove a number of columns from the image. But the importance values of points inside a column of the image are not all the same. So instead of removing a number of columns, it is better to find paths from the top of the image to the bottom whose total importance is the smallest, and remove those:

If you are very detail-oriented, this question has probably occurred to you: “Well, why don’t we pick the point with the lowest importance value from each row and then remove it?” Good question. It would be very good to write the code for this and observe its output. I will write the answer to this question at the end of this post so that you do not lose the chance to implement and test it yourself (you can get the code for this post from https://gitlab.com/vedadian_samples/fun-with-opencv-2.git and modify it.)

But how should we find the vertical path with the lowest total energy? Simply computing the energy of all vertical paths inside an image is impractical. I mean that the running time of a program written for this would become so long that one would effectively give up using that code. For this reason, we use the “dynamic programming” method. If you are not familiar with this problem-solving method, its Wikipedia page provides good explanations.

The result of applying the “dynamic programming” method is that, starting from the second row of the image matrix, we assume that at every point we have the energy values of the best vertical path taken up to the previous row. Having this value for each point in the new row, we consider the energy values of the path up to neighboring points and add the smallest value to the energy of this point. Obviously, this value will correspond to the best vertical path taken up to this point. With the same approach, we can proceed to the last row of the image matrix. What remains is the energy of the best path for the points in the first row. But the paths corresponding to the points in the first row are those very points in the first row themselves; because there was no other row before them!

In short, the following piece of code, given the importance or energy matrix of the points, finds and returns the vertical path with the lowest energy:

#define MAX_DEVIATION   2std::vector<int> findVerticalSeam(const cv::Mat& _energyMatrix){    int m = _energyMatrix.rows, n = _energyMatrix.cols;    cv::Mat pathEnergy = cv::Mat::zeros(cv::Size(n, m), CV_32FC1) + std::numeric_limits<float>::max();    _energyMatrix(cv::Rect(0, 0, n, 1)).copyTo(pathEnergy(cv::Rect(0, 0, n, 1)));    cv::Mat offsets = cv::Mat::zeros(cv::Size(n, m), CV_32SC1);    for(int i = 1; i < m; ++i) {        for(int j = 0; j < n; ++j) {            for(int o = -1; o <= 1; ++o) {                if(j + o >= 0 && j + o < n) {                    float offsetCost = pathEnergy.at<float>(i - 1, j + o) + _energyMatrix.at<float>(i, j);                    if(pathEnergy.at<float>(i, j) > offsetCost) {                        pathEnergy.at<float>(i, j) = offsetCost;                        offsets.at<int>(i, j) = o;                    }                }            }        }    }    std::vector<int> seam(m);    seam[m - 1] = 0;    for(int i = 1; i < n; ++i)        if(pathEnergy.at<float>(m - 1, i) < pathEnergy.at<float>(m - 1, seam[m - 1]))            seam[m - 1] = i;    for(int i = m - 1; i > 0; --i)        seam[i - 1] = seam[i] + offsets.at<int>(i, seam[i]);    return seam;}

I should have said this first, but better late than never. A vertical path from the first row of the image to its bottom is a set of points that starts from the first row in order and reaches the end, while every two adjacent points in the path are neighbors. The value MAX_DEVIATION in the code above determines the size of the neighborhood. The value 2 that has been chosen means that every point in the image lies in a neighborhood with dimensions 5 by 5 (each point is neighbors with points 2 steps away from it in the up, down, left, and right directions.)

Once these two parts of the problem are solved, the whole problem is solved. It is enough to start finding seams and removing them in a loop. We do this until the image size has been reduced by the desired amount:

for(int i = 0; i < 250; ++i) {    auto energyMatrix = computeEnergyMatrix(image);    auto seam = findVerticalSeam(energyMatrix);    image = removeVerticalSeam(image, seam);    std::cout << (i + 1) << " seam(s) removed." << std::endl;}

For example, in the loop above, 250 columns are reduced from the width of the image.

Now we do the same thing for the penguin image shown above. You can see the result below:

Removing low-energy seams or seam carving

But the answer to the question that was supposed to come at the end of this post. The answer is that, in addition to the amount of change, our eyes also show sensitivity to the neighborhoods within an image. For example, a human has eyes, ears, and a nose, with the eyes on the two sides of the nose and the ears on the two sides of the head. If this arrangement is disrupted, the image that results is not an image of a human. Therefore, the image below is not a useful size reduction:

As I mentioned, implementations of seam carving in Python and C++ are available at the Git address https://gitlab.com/vedadian_samples/fun-with-opencv-2.git.