The Image Smoother Algorithm in C++/Java

  • 时间：2020-10-05 13:15:44
  • 分类：网络文摘
  • 阅读：142 次

Given a 2D integer matrix M representing the gray scale of an image, you need to design a smoother to make the gray scale of each cell becomes the average gray scale (rounding down) of all the 8 surrounding cells and itself. If a cell has less than 8 surrounding cells, then use as many as you can.

Example 1:
Input:
[[1,1,1],
[1,0,1],
[1,1,1]]

Output:
[[0, 0, 0],
[0, 0, 0],
[0, 0, 0]]

Explanation:
For the point (0,0), (0,2), (2,0), (2,2): floor(3/4) = floor(0.75) = 0
For the point (0,1), (1,0), (1,2), (2,1): floor(5/6) = floor(0.83333333) = 0
For the point (1,1): floor(8/9) = floor(0.88888889) = 0

Note:
The value in the given matrix is in the range of [0, 255].
The length and width of the given matrix are in the range of [1, 150].

How to Smooth Image in C++?

The following C++ code implements O(N) algorithm (where N is the number of pixels in the image) that iterates each pixel. We can’t modify the existing image, rather, it has to be done on a separate copy of image.

We can deep copy the std::vector, or just assign new pixel to it.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
public:
    vector<vector<int>> imageSmoother(vector<vector<int>>& M) {
        int row = M.size();
        if (row == 0) return M;
        int width = M[0].size();
        if (width == 0) return M;
        vector<vector<int>> N(row, vector<int>(width)); // or N = M deep copy of vector
        for (int i = 0; i < row; ++ i) {
            for (int j = 0; j < width; ++ j) {
                int sum = 0, c = 0;
                for (int k = max(0, i - 1); k <= min(i + 1, row - 1); k ++) {
                    for (int u = max(0, j - 1); u <= min(j + 1, width - 1); u ++) {
                        sum += M[k][u];
                        c ++;
                    }
                }
                N[i][j] = sum / c;
            }
        }
        return N;
    }
};
class Solution {
public:
    vector<vector<int>> imageSmoother(vector<vector<int>>& M) {
        int row = M.size();
        if (row == 0) return M;
        int width = M[0].size();
        if (width == 0) return M;
        vector<vector<int>> N(row, vector<int>(width)); // or N = M deep copy of vector
        for (int i = 0; i < row; ++ i) {
            for (int j = 0; j < width; ++ j) {
                int sum = 0, c = 0;
                for (int k = max(0, i - 1); k <= min(i + 1, row - 1); k ++) {
                    for (int u = max(0, j - 1); u <= min(j + 1, width - 1); u ++) {
                        sum += M[k][u];
                        c ++;
                    }
                }
                N[i][j] = sum / c;
            }
        }
        return N;
    }
};

We can check if the neighbour index of pixels are valid. Alternatively, we can use min/max to make sure the indices are always valid. We don’t need to use floor function as the integer division is floor anyway.

How to Smooth Image in Java?

The same image smooth algorithm can be implemented in Java as follows.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
    public int[][] imageSmoother(int[][] M) {
        int row = M.length;
        if (row == 0) return M;
        int width = M[0].length;
        if (width == 0) return M;
        int[][] N = new int[row][width];
        for (int i = 0; i < row; ++ i) {
            for (int j = 0; j < width; ++ j) {
                int sum = 0, c = 0;
                for (int k = Math.max(0, i - 1); k <= Math.min(i + 1, row - 1); k ++) {
                    for (int u = Math.max(0, j - 1); u <= Math.min(j + 1, width - 1); u ++) {
                        sum += M[k][u];
                        c ++;
                    }
                }
                N[i][j] = sum / c;
            }
        }
        return N;        
    }
}
class Solution {
    public int[][] imageSmoother(int[][] M) {
        int row = M.length;
        if (row == 0) return M;
        int width = M[0].length;
        if (width == 0) return M;
        int[][] N = new int[row][width];
        for (int i = 0; i < row; ++ i) {
            for (int j = 0; j < width; ++ j) {
                int sum = 0, c = 0;
                for (int k = Math.max(0, i - 1); k <= Math.min(i + 1, row - 1); k ++) {
                    for (int u = Math.max(0, j - 1); u <= Math.min(j + 1, width - 1); u ++) {
                        sum += M[k][u];
                        c ++;
                    }
                }
                N[i][j] = sum / c;
            }
        }
        return N;        
    }
}

–EOF (The Ultimate Computing & Technology Blog) —

推荐阅读：
黑木耳营养丰富对健康有五大好处　 香蕉和橘子能起到解毒护肝的作用　 吃葡萄、喝葡萄酒能帮助调节性功能　 绿茶、红茶、青茶、黑茶、白茶和黄茶　 奶茶多添加奶精 长期食用会引发心脏病　 奶茶调查：街头奶茶店调香味多用奶精　 适合秋天食用的养肺食谱可滋阴润肺　 哪些食物可以起到止咳润肺的作用　 食物的禁忌：中医如何区分食物的寒热性　 味道鲜美营养丰富的黑木耳最佳吃法　
评论列表
添加评论