Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 구현하는 이미지 스무더(Image Smoother) 알고리즘

문제 개요

2차원 행렬 M이 이미지의 그레이스케일 값을 나타낸다고 가정해 보겠습니다. 이때 각 픽셀의 밝기를, 자기 자신을 포함한 주변 8개 픽셀의 평균값(소수점 이하는 버림)으로 바꾸는 이미지 스무더(Smoother)를 설계해야 합니다. 만약 어떤 셀의 주변에 8개보다 적은 셀이 있다면, 존재하는 모든 유효한 픽셀만을 대상으로 계산합니다.

입력 예시

111
101
111

출력 결과

000
000
000

가운데 값 0을 기준으로 계산하면, 주변 8개 픽셀과 자기 자신의 합은 8이고 개수는 9이므로 8 ÷ 9 = 0.88...에서 버림하여 0이 됩니다. 모서리와 가장자리 픽셀 역시 유효한 이웃 픽셀들만으로 평균을 내면 결국 모든 값이 0으로 스무딩됩니다.

해결 접근 방법

이 문제는 다음 단계로 해결할 수 있습니다.

  • R := 행렬 M의 행(row) 개수

  • C := 행렬 M의 열(column) 개수

  • 방향 배열 d = { -1, 0, 1 } 정의 — 상하좌우 및 대각선 이동을 표현

  • 크기가 R x C인 2차원 배열 res 생성 (결과 저장용)

  • i := 0부터 i < R까지 반복:

    • j := 0부터 j < C까지 반복:

      • sum := 0, count := 0으로 초기화

      • k := 0부터 k < 3까지 반복:

        • l := 0부터 l < 3까지 반복:

          • m := i + d[k], n := j + d[l] 로 이웃 좌표 계산

          • m >= 0 이고 m < R 이며 n >= 0 이고 n < C 인 경우(행렬 범위 내):

            • count를 1 증가시키고 sum에 M[m, n] 값을 더함

      • res[i, j] := sum / count (정수 나눗셈으로 자동 버림 처리)

  • 최종적으로 res 반환

핵심 아이디어는 3x3 방향 오프셋을 활용해 현재 픽셀과 그 이웃들을 순회하되, 행렬 경계를 벗어나는 좌표는 건너뛰는 것입니다. 이렇게 하면 모서리나 가장자리에 있는 픽셀도 올바르게 처리할 수 있습니다.

C++ 구현 예제

아래 구현 코드를 통해 더 잘 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<vector<auto> > v){
    cout << "[";
    for(int i = 0; i<v.size(); i++){
        cout << "[";
        for(int j = 0; j <v[i].size(); j++){
            cout << v[i][j] << ", ";
        }
        cout << "],";
    }
    cout << "]"<<endl;
}
class Solution {
public:
    vector<vector<int>> imageSmoother(vector<vector<int>>& M) {
        int R = M.size();
        int C = M[0].size();
        vector<int> d{ -1, 0, 1 };
        vector<vector<int> > res(R, vector<int>(C, 0));
        for (int i = 0; i < R; ++i) {
            for (int j = 0; j < C; ++j) {
                int sum = 0, count = 0;
                for (int k = 0; k < 3; ++k) {
                    for (int l = 0; l < 3; ++l) {
                        int m = i + d[k], n = j + d[l];
                        if (m >= 0 && m < R && n >= 0 && n < C) ++count, sum += M[m][n];
                    }
                }
                res[i][j] = sum / count;
            }
        }
        return res;
    }
};
main(){
    Solution ob;
    vector<vector<int>> v = {{1,1,1},{1,0,1},{1,1,1}};
    print_vector(ob.imageSmoother(v));
}

실행 결과 확인

입력

{{1,1,1},{1,0,1},{1,1,1}}

출력

[[0, 0, 0],[0, 0, 0],[0, 0, 0]]

복잡도 분석

이 알고리즘의 시간 복잡도는 O(R × C × 9), 즉 O(R × C)입니다. 각 픽셀마다 최대 9개의 이웃(자기 자신 포함)을 확인하기 때문입니다. 공간 복잡도는 결과 행렬을 저장하기 위해 O(R × C)가 필요합니다. 참고로 원본 행렬을 수정하지 않아야 하는 제약이 있어 추가 결과 배열이 필수적이며, 만약 in-place 처리가 허용된다면 비트 연산 등을 활용해 공간을 절약하는 최적화도 가능합니다.