图片平滑器

难度: Easy

图像平滑器 是大小为 3 x 3 的过滤器，用于对图像的每个单元格平滑处理，平滑处理后单元格的值为该单元格的平均灰度。

每个单元格的 平均灰度 定义为：该单元格自身及其周围的 8 个单元格的平均值，结果需向下取整。（即，需要计算蓝色平滑器中 9 个单元格的平均值）。

如果一个单元格周围存在单元格缺失的情况，则计算平均灰度时不考虑缺失的单元格（即，需要计算红色平滑器中 4 个单元格的平均值）。

给你一个表示图像灰度的 m x n 整数矩阵 img ，返回对图像的每个单元格平滑处理后的图像。

示例 1:

输入:img = [[1,1,1],[1,0,1],[1,1,1]]
输出:[[0, 0, 0],[0, 0, 0], [0, 0, 0]]
解释:
对于点 (0,0), (0,2), (2,0), (2,2): 平均(3/4) = 平均(0.75) = 0
对于点 (0,1), (1,0), (1,2), (2,1): 平均(5/6) = 平均(0.83333333) = 0
对于点 (1,1): 平均(8/9) = 平均(0.88888889) = 0

示例 2:

输入: img = [[100,200,100],[200,50,200],[100,200,100]]
输出: [[137,141,137],[141,138,141],[137,141,137]]
解释:
对于点 (0,0), (0,2), (2,0), (2,2): floor((100+200+200+50)/4) = floor(137.5) = 137
对于点 (0,1), (1,0), (1,2), (2,1): floor((200+200+50+200+100+100)/6) = floor(141.666667) = 141
对于点 (1,1): floor((50+200+200+200+200+100+100+100+100)/9) = floor(138.888889) = 138

提示:

m == img.length
n == img[i].length
1 <= m, n <= 200
0 <= img[i][j] <= 255

Submission

运行时间: 91 ms

内存: 17.1 MB

class Solution:
    def imageSmoother(self, img: List[List[int]]) -> List[List[int]]:
        m, n = len(img), len(img[0]) 
        result = [[0 for i in range(n)] for j in range(m)]              
        
        if m == 1:
            if n == 1:
                return img
            else:
                for j in range(n):
                    if j == 0:
                        result[0][j] = (img[0][j]+ img[0][j+ 1]) // 2
                    elif j == n - 1:
                        result[0][j] = (img[0][j]+ img[0][j- 1]) // 2
                    else:
                        result[0][j] = (img[0][j]+ img[0][j- 1]+ img[0][j+ 1]) // 3
        else:
            if n == 1:
                for i in range(m):
                    if i == 0:
                        result[i][0] = (img[i][0]+ img[i+ 1][0]) // 2
                    elif i == m - 1:
                        result[i][0] = (img[i][0]+ img[i- 1][0]) // 2
                    else:
                        result[i][0] = (img[i][0]+ img[i+ 1][0]+ img[i- 1][0]) // 3 
            else:                      
                for i in range(m):
                    for j in range(n):
                        if i == 0:
                            if j == 0:
                                result[i][j] = (img[i][j]+ img[i][j+ 1]+ img[i+ 1][j]+ img[i+ 1][j+ 1]) // 4
                            elif j == n- 1:
                                result[i][j] = (img[i][j]+ img[i][j- 1]+ img[i+ 1][j]+ img[i+ 1][j- 1]) // 4
                            else:
                                result[i][j] = (img[i][j]+ img[i][j- 1]+ img[i][j+ 1]+ img[i+ 1][j]+ img[i+ 1][j- 1]+ img[i+ 1][j+ 1]) // 6
                        elif i == m - 1:
                            if j == 0:
                                result[i][j] = (img[i][j]+ img[i][j+ 1]+ img[i- 1][j]+ img[i- 1][j+ 1]) // 4
                            elif j == n- 1:
                                result[i][j] = (img[i][j]+ img[i][j- 1]+ img[i- 1][j]+ img[i- 1][j- 1]) // 4
                            else:
                                result[i][j] = (img[i][j]+ img[i][j- 1]+ img[i][j+ 1]+ img[i- 1][j]+ img[i- 1][j- 1]+ img[i- 1][j+ 1]) // 6
                        else:
                            if j == 0:
                                result[i][j] = (img[i][j]+ img[i+ 1][j]+ img[i- 1][j]+ img[i][j+ 1]+ img[i- 1][j+ 1]+ img[i+ 1][j+ 1]) // 6
                            elif j == n- 1:
                                result[i][j] = (img[i][j]+ img[i+ 1][j]+ img[i- 1][j]+ img[i- 1][j- 1]+ img[i+ 1][j- 1]+ img[i][j- 1]) // 6
                            else:
                                result[i][j] = (img[i][j]+ img[i][j- 1]+ img[i][j+ 1]+ img[i- 1][j]+ img[i- 1][j- 1]+ img[i- 1][j+ 1]+ img[i+ 1][j]+ img[i+ 1][j- 1]+ img[i+ 1][j+ 1]) // 9
        return result

Explain

该题解的思路是对图像的每个像素点进行平滑处理。具体做法是，对于每个像素点，计算其周围 8 个像素点（如果存在的话）的平均值，并将结果赋值给对应位置的输出矩阵中的元素。需要注意的是，对于边界上的像素点，其周围的像素点可能不满 8 个，此时只计算存在的像素点的平均值即可。题解中分别讨论了输入矩阵为一行、一列以及普通情况下的处理方法。

时间复杂度: O(m*n)

空间复杂度: O(m*n)

class Solution:
    def imageSmoother(self, img: List[List[int]]) -> List[List[int]]:
        m, n = len(img), len(img[0])
        result = [[0 for i in range(n)] for j in range(m)]  # 初始化输出矩阵
        
        if m == 1:
            if n == 1:
                return img
            else:
                for j in range(n):
                    if j == 0:
                        result[0][j] = (img[0][j] + img[0][j+1]) // 2  # 处理第一列
                    elif j == n - 1:
                        result[0][j] = (img[0][j] + img[0][j-1]) // 2  # 处理最后一列
                    else:
                        result[0][j] = (img[0][j] + img[0][j-1] + img[0][j+1]) // 3  # 处理中间列
        else:
            if n == 1:
                for i in range(m):
                    if i == 0:
                        result[i][0] = (img[i][0] + img[i+1][0]) // 2  # 处理第一行
                    elif i == m - 1:
                        result[i][0] = (img[i][0] + img[i-1][0]) // 2  # 处理最后一行
                    else:
                        result[i][0] = (img[i][0] + img[i+1][0] + img[i-1][0]) // 3  # 处理中间行
            else:                      
                for i in range(m):
                    for j in range(n):
                        if i == 0:
                            if j == 0:
                                result[i][j] = (img[i][j] + img[i][j+1] + img[i+1][j] + img[i+1][j+1]) // 4  # 处理左上角
                            elif j == n - 1:
                                result[i][j] = (img[i][j] + img[i][j-1] + img[i+1][j] + img[i+1][j-1]) // 4  # 处理右上角
                            else:
                                result[i][j] = (img[i][j] + img[i][j-1] + img[i][j+1] + img[i+1][j] + img[i+1][j-1] + img[i+1][j+1]) // 6  # 处理第一行中间列
                        elif i == m - 1:
                            if j == 0:
                                result[i][j] = (img[i][j] + img[i][j+1] + img[i-1][j] + img[i-1][j+1]) // 4  # 处理左下角
                            elif j == n - 1:
                                result[i][j] = (img[i][j] + img[i][j-1] + img[i-1][j] + img[i-1][j-1]) // 4  # 处理右下角
                            else:
                                result[i][j] = (img[i][j] + img[i][j-1] + img[i][j+1] + img[i-1][j] + img[i-1][j-1] + img[i-1][j+1]) // 6  # 处理最后一行中间列
                        else:
                            if j == 0:
                                result[i][j] = (img[i][j] + img[i+1][j] + img[i-1][j] + img[i][j+1] + img[i-1][j+1] + img[i+1][j+1]) // 6  # 处理中间行第一列
                            elif j == n - 1:
                                result[i][j] = (img[i][j] + img[i+1][j] + img[i-1][j] + img[i-1][j-1] + img[i+1][j-1] + img[i][j-1]) // 6  # 处理中间行最后一列
                            else:
                                result[i][j] = (img[i][j] + img[i][j-1] + img[i][j+1] + img[i-1][j] + img[i-1][j-1] + img[i-1][j+1] + img[i+1][j] + img[i+1][j-1] + img[i+1][j+1]) // 9  # 处理中间行中间列
        return result

Explore

对于大尺寸图像的平滑处理，可以考虑使用积分图（integral image）的技术来优化计算。积分图允许我们在常数时间内计算任意矩形区域的像素和，从而避免重复计算相邻区域的和。具体来说，首先计算输入图像的积分图，然后利用积分图快速得到每个像素周围的区域和，最后计算平均值。这种方法减少了重复计算，特别适合于处理大型图像。

是的，边界像素的处理需要特别注意，因为它们周围的邻近像素数量少于非边界像素。这意味着在编写代码时需要为边界像素设计特定的逻辑，以确保正确计算平均值。例如，对于图像的角落像素，可能只有3个或4个邻近像素，而边缘但非角落的像素则可能有5或6个邻近像素。如果不适当处理这些情况，可能会导致索引越界或计算错误。

使用整数除法确实会导致一定的精度问题，因为它会向下取整结果，可能会使得平滑后的图像失去一些细节。特别是在灰度值变化较大的图像中，这种取整效果可能会导致可见的误差。如果需要更高的精度，可以考虑使用浮点数进行计算，并在最终结果存储前四舍五入到最近的整数，这样可以在一定程度上减少因整数除法引入的误差。

在图像只有一行或一列的特殊情况下，像素点的邻近像素明显减少，因此需要特殊处理。例如，如果图像只有一行，则每个像素点只需要考虑左右邻近的像素（如果存在）。对于位于行首和行尾的像素，只有一个相邻像素；而中间的像素则有两个邻近像素。类似地，如果图像只有一列，每个像素点只需要考虑上下邻近的像素。这种处理确保了即使在极端情况下，平滑操作也能正确执行，而不会因为缺乏邻近像素而引起程序错误。