같은 영역의 합을 반복해서 묻는 질문에 매번 모든 칸을 더하는 것은 낭비다. Integral Image는 "왼쪽 위 모서리부터 여기까지의 누적합"을 격자 전체에 한 번 채워두고, 그 다음부터는 어떤 직사각형의 합이든 모서리 네 개를 포함-배제로 조합해 O(1)에 답한다. 1D 누적합의 자연스러운 2차원 확장이며, Viola-Jones 얼굴 검출이 실시간으로 동작하게 만든 바로 그 자료구조다. 이 페이지는 그 점화식과 4-모서리 쿼리 공식을 유도하고, Square 문제가 이것을 어떻게 쓰는지 추적한다.
H × W 크기의 2차원 격자 A가 주어진다. 임의의 축 정렬 직사각형 [r₁, r₂] × [c₁, c₂] 안에 든 원소들의 합 Σ A[r][c]를 구하는 질의가 Q번 들어온다. 격자는 변하지 않는다(정적).
가장 단순한 방법은 질의마다 직사각형 안을 직접 이중 루프로 더하는 것이다. 직사각형 하나가 최대 HW 칸이므로 한 질의에 O(HW), 전체 O(Q·HW). H, W, Q가 모두 수천이면 수십억 연산 — Expert의 시간 제한을 넘긴다.
핵심 통찰은 1D에서 먼저 본다. 배열 a[0..n−1]의 부분합을 여러 번 묻는다면, 접두합(prefix sum) P[i] = a[0] + … + a[i−1]을 한 번 만들어두면 구간 [l, r]의 합은 P[r+1] − P[l] 한 번의 뺄셈으로 끝난다. "지금까지의 누적"을 미리 쌓아두면, 임의 구간합은 두 누적값의 차이로 환원된다.
Integral Image(적분 영상, summed-area table이라고도 한다)는 이 발상을 2차원으로 끌어올린다. 격자 A에 대해 적분 영상 S를 다음과 같이 정의한다 — S[r][c]는 왼쪽 위 모서리 (0,0)부터 (r−1, c−1)까지의 직사각형 전체의 합이다(0-인덱스, S는 (H+1)×(W+1) 크기로 첫 행·열을 0 패딩한다).
적분 영상의 정확성은 두 부분으로 나뉜다 — 구축 점화식이 정의 S[r][c] = Σ_{i<r,j<c}A[i][j]를 실제로 채우는가(정리 1), 그리고 4-모서리 공식이 임의 직사각형 합과 같은가(정리 2). 둘 다 포함-배제 한 줄로 증명된다.
유한 집합 U 위의 가산 측도(여기서는 원소 값의 합)에 대해, |X ∪ Y| = |X| + |Y| − |X ∩ Y|가 성립한다. 직사각형 영역들에 적용하면, 두 직사각형의 합집합 영역의 합은 각각의 합을 더하고 겹치는 직사각형의 합을 한 번 뺀 것이다.
점화식 S[r][c] = A[r-1][c-1] + S[r-1][c] + S[r][c-1] − S[r-1][c-1]을 행·열 증가 순으로 채우면, 모든 (r,c)에서 S[r][c] = Σ_{i<r,j<c}A[i][j]이다.
증명(귀납법). 기저: r=0 또는 c=0이면 영역이 비어 있어 S=0 — 패딩과 일치. 귀납 단계: S[r−1][c], S[r][c−1], S[r−1][c−1]이 모두 정의대로 채워졌다고 하자. 영역 R(r,c) = \{(i,j) : i<r, j<c\}를 세 조각의 포함-배제로 분해한다. R(r,c) = R(r−1,c) ∪ R(r,c−1) ∪ \{(r−1,c−1)\}. 여기서 R(r−1,c)(위쪽 띠 포함 영역)와 R(r,c−1)(왼쪽 띠 포함 영역)의 교집합은 정확히 R(r−1,c−1)이고, 칸 (r−1,c−1)은 둘 중 어디에도 속하지 않으므로 따로 더한다. Lemma를 합 측도에 적용하면 S[r][c] = S[r−1][c] + S[r][c−1] − S[r−1][c−1] + A[r−1][c−1].
0-인덱스 격자에서 행 [r₁,r₂], 열 [c₁,c₂] (양 끝 포함)인 직사각형의 합은 S[r2+1][c2+1] − S[r1][c2+1] − S[r2+1][c1] + S[r1][c1]이다.
증명. 목표 직사각형을 T라 하자. S[r₂+1][c₂+1]은 (0,0)부터 T의 오른쪽-아래 모서리까지의 큰 직사각형 B의 합이다. B에서 T 위의 가로 띠 U(합 S[r₁][c₂+1])와 T 왼쪽의 세로 띠 L(합 S[r₂+1][c₁])을 빼면 T가 남아야 한다. 그런데 U ∩ L은 좌상단 직사각형으로, U와 L을 둘 다 뺄 때 두 번 제거된다. Lemma의 |X ∩ Y| 항이 바로 이것 — 한 번 도로 더해 보정한다. 그 좌상단 직사각형의 합이 S[r₁][c₁]이다. 따라서 sum(T) = B − U − L + (U∩L) = S[r₂+1][c₂+1] − S[r₁][c₂+1] − S[r₂+1][c₁] + S[r₁][c₁].
long long이어야 한다. (2) 인덱스 경계. S를 한 줄·한 칸 키워 0 패딩하면 쿼리 공식에서 r₁−1 같은 음수 인덱스가 자연히 사라진다 — 패딩 없이 구현하면 r₁=0 또는 c₁=0일 때 경계 분기가 4갈래로 늘어 버그의 온상이 된다. 패딩은 선택이 아니라 표준이다.
구현은 두 부분이다 — 격자 전체를 한 번 훑어 S를 채우는 build(O(HW)), 그리고 모서리 네 개를 조합하는 rectSum(O(1)). S를 (H+1)×(W+1)로 잡고 0번 행·열을 0으로 두는 패딩이 음수 인덱스 분기를 통째로 없앤다.
#include <vector>using namespace std;struct IntegralImage { int H, W; vector<vector<long long>> S; // (H+1) x (W+1), 0 패딩 // A: H x W 입력 격자 → 적분 영상 S 구축, O(HW) IntegralImage(const vector<vector<int>>& A) : H(A.size()), W(A[0].size()), S(H + 1, vector<long long>(W + 1, 0)) { for (int r = 1; r <= H; ++r) for (int c = 1; c <= W; ++c) S[r][c] = A[r-1][c-1] + S[r-1][c] + S[r][c-1] - S[r-1][c-1]; // 포함-배제 } // 직사각형 행[r1,r2] 열[c1,c2] (양끝 포함)의 합, O(1) long long rectSum(int r1, int c1, int r2, int c2) const { return S[r2+1][c2+1] - S[r1][c2+1] - S[r2+1][c1] + S[r1][c1]; // 4-corner }};// 사용 예 — 모든 K x K 정사각형 중 최대 합 찾기long long bestSquare(const vector<vector<int>>& A, int K) { IntegralImage ii(A); long long best = 0; for (int r = 0; r + K <= ii.H; ++r) for (int c = 0; c + K <= ii.W; ++c) { long long s = ii.rectSum(r, c, r+K-1, c+K-1); if (s > best) best = s; } return best; // 전체 O(HW): 후보 HW개 x 쿼리 O(1)}
build의 세 줄(라인 13~15)이 Theorem 1, rectSum의 두 줄(라인 20~21)이 Theorem 2의 직접 옮김이다. S를 long long으로 잡은 것(라인 6)이 §2의 오버플로 함정 처방 — 적분 영상의 마지막 칸은 격자 전체의 합이라 32비트를 쉽게 넘는다. bestSquare가 보여주는 패턴이 적분 영상의 진가다 — "모든 K×K 정사각형의 합" 같은 질문은 후보가 O(HW)개이고 각 후보의 합을 직접 더하면 O(HW·K²)지만, 적분 영상을 깔면 후보마다 쿼리가 O(1)이라 전체가 O(HW)로 떨어진다 — K² 인자가 통째로 증발한다. S를 1차원 배열로 펴고 인덱스 산술을 직접 하면 캐시 지역성이 좋아져 상수가 더 작아진다.
구축은 S의 모든 칸을 상수 작업으로 한 번씩 채우므로 O(HW). 쿼리는 직사각형 크기와 무관하게 O(1). Q개의 질의 전체는 O(HW + Q)로, 순진한 O(Q·HW) 대비 HW가 통째로 빠진다. 공간은 적분 영상 O(HW). 적분 영상은 전처리-쿼리 트레이드오프의 교과서적 예다 — 격자가 정적이고 질의가 한 번이라도 반복되면, 한 번의 O(HW) 선행 투자가 모든 후속 질의를 O(1)로 만든다. 손익분기점은 질의 한 개 — 그래서 사실상 항상 이득이다.
적분 영상은 1D 접두합의 곧은 일반화다. 1D는 P[i] = P[i−1] + a[i−1]로 채우고 구간합을 P[r+1] − P[l] (항 2개)로 답한다. 2D는 점화식에 "두 번 센 좌상단을 빼는" 보정항이 하나 붙고, 쿼리는 항이 4개가 된다. 이 패턴은 차원을 따라 계속 일반화된다 — d차원 적분 영상의 쿼리는 2^d개의 모서리를 부호와 함께 더한다. 거꾸로, 2D 격자의 각 행에 1D 접두합을 먼저 깔고 그 결과 열에 다시 1D 접두합을 깔아도 똑같은 적분 영상이 나온다 — "행 방향 스캔 후 열 방향 스캔" 2패스 구축은 위 점화식의 1패스 구축과 수학적으로 동치다.
적분 영상이 등장하는 신호는 "정적 격자 + 반복되는 직사각형 영역 질의"다. 기본형은 단순하지만 변형의 폭이 넓다.
Square 문제는 격자 위 모든 가능한 정사각형(또는 직사각형)의 영역합을 따져 어떤 조건을 만족하는 것을 찾는다. 정사각형 후보가 위치·크기에 따라 O(HW·min(H,W))개까지 늘어나는데, 적분 영상을 깔면 후보 하나당 합 계산이 O(1)로 고정된다. 순진한 풀이의 "후보 수 × 후보 크기"가 "후보 수 × 1"로 바뀌어, 후보 크기 인자가 통째로 사라지는 것이 핵심 비틀기다 — §3의 bestSquare가 바로 그 골격이다.
적분 영상을 값 자체뿐 아니라 값의 제곱에 대해서도 하나 더 만들면, 직사각형 영역의 평균뿐 아니라 분산·표준편차까지 O(1)에 얻는다 — Var = E[X²] − E[X]²이고 ΣX와 ΣX²를 둘 다 4-모서리로 뽑을 수 있기 때문이다. 영상 처리의 적응형 이진화(adaptive thresholding)와 정규화 상관(NCC) 템플릿 매칭이 이 트릭에 의존한다.
표준 적분 영상은 축 정렬 직사각형만 다루지만, 45° 기울어진 적분 영상(rotated summed-area table)을 추가로 만들면 대각 방향 직사각형 합도 O(1)에 답한다 — Viola-Jones의 확장 Haar 특징이 이것을 쓴다. 차원을 올려 x×y×z 3D 적분 영상을 만들면 임의 직육면체의 합을 2³=8개 모서리로 O(1)에 — 의료 영상의 볼륨 분석에 쓰인다.
2001년 Viola-Jones 검출기는 적분 영상의 가장 유명한 응용이다. Haar-like 특징은 "인접한 밝은 직사각형 영역의 합 − 어두운 직사각형 영역의 합"인데, 한 이미지에서 평가해야 할 특징이 수만 개다. 적분 영상이 없으면 각 특징이 직사각형 크기에 비례하는 시간을 먹어 실시간이 불가능하다. 적분 영상을 한 번 깔면 어떤 크기·위치의 Haar 특징이든 상수 시간에 평가되어 — 검출기가 비디오 프레임 속도로 동작한다. 적분 영상은 알고리즘 트릭 하나가 응용 분야 전체(실시간 컴퓨터 비전)를 열어젖힌 역사적 사례다.
현대 딥러닝의 평균 풀링(average pooling)은 본질적으로 "겹치지 않는 직사각형 영역들의 평균"이다. 다양한 크기의 영역 평균을 빠르게 뽑아야 하는 ROI 풀링·공간 피라미드 풀링 같은 변형은 내부적으로 적분 영상과 동일한 누적합 발상에 기댄다 — 한 번 누적해두고 직사각형마다 모서리 조합으로 평균을 뽑는 구조가 그대로다.
| 자료구조 | 전처리 / 갱신 | 쿼리 | 쓰임 |
|---|---|---|---|
| 1D Prefix Sum | O(n) / 불가 | O(1) | 정적 1차원 배열 — 가장 단순 |
| Integral Image (2D) | O(HW) / 불가 | O(1) | 정적 2D 격자 직사각형 합 — 최적 |
| Fenwick Tree (1D) | O(n) / O(log n) | O(log n) | 갱신이 잦은 1차원 — 코드 짧음 |
| 2D Fenwick Tree | O(HW) / O(log H·log W) | O(log H·log W) | 갱신되는 2D 격자 직사각형 합 |
| 2D Segment Tree | O(HW) / O(log H·log W) | O(log H·log W) | 갱신 + 비합 연산(min/max 등) |
이 표는 단 하나의 축으로 읽힌다 — 격자가 변하는가. 격자가 정적이면 적분 영상이 1D 접두합의 2D 형제로서 쿼리 O(1)의 절대 우위를 가진다. 갱신이 끼어드는 순간 적분 영상은 무력해진다 — 칸 하나가 바뀌면 그 칸의 오른쪽-아래 영역 전체의 S 값이 갱신되어 최악 O(HW)다. 그때는 펜윅 트리 계열로 갈아타 갱신과 쿼리를 모두 로그 시간에 맞춘다.
적분 영상과 펜윅 트리의 관계는 이렇게 요약된다 — 적분 영상은 "갱신을 포기하고 쿼리를 극한까지 빠르게 한" 펜윅 트리의 정적 특수화다. 비합 연산(직사각형 안의 최댓값·최솟값 등)이 필요하면 둘 다 부족하다 — 최댓값은 뺄셈으로 분해되지 않으므로 포함-배제가 통하지 않는다. 그때는 2D 세그먼트 트리나 2D 희소 테이블(sparse table)을 써야 한다. 적분 영상이 답하는 것은 정확히 — 가산적(덧셈으로 분해 가능)이고, 격자가 정적이며, 직사각형 영역인 질의다. 세 조건이 모두 맞으면 이보다 빠른 것은 없다.