이 페이지는 "왜 임의 크기 사각형의 합이 상수 시간인가"를 포함-배제 원리의 바닥까지 따라 내려간다. 2D 누적합의 네 점 공식이 어떻게 면적을 쿼리 비용에서 분리하는지를 귀납으로 증명하고, Naive·행 누적합·FFT 합성곱과의 복잡도를 정밀하게 유도하며, Viola-Jones Haar feature와 CNN receptive field로의 연결까지 구현 수준의 C++ 코드로 라인 단위 해부한다.
Square 문제는 N×N 이미지에서 수많은 K×K(또는 가변 크기) 사각형 영역의 합을 물어본다. 점수와 시간 제약은 "얼마나 많은 영역 합 쿼리를, 얼마나 빨리 처리하는가"로 결정된다.
순진한 접근은 쿼리마다 사각형 안 픽셀을 직접 더하는 것이다 — 쿼리당 O(K²). N=1000, K=50에 쿼리가 N²개면 10⁶ · 2500 = 2.5×10⁹, 다중 스케일까지 겹치면 10¹⁰을 넘어 시간 벽에 막힌다. 베스트 해법은 이 비용 구조를 근본적으로 바꾼다 — 면적 K²을 쿼리 비용에서 완전히 떼어낸다.
II[i][j]를 만든다. 각 칸이 위·왼쪽 칸의 결과를 재사용하므로 표 전체가 O(N²)에 완성된다 — 한 번만.II 표의 네 모서리 점만 더하고 빼서 구한다. 포함-배제 원리의 직접적 귀결이며, 사각형이 5×5든 500×500이든 연산 수는 정확히 4 — 진정한 O(1).핵심 통찰은 전처리가 "모든 가능한 origin-rectangle의 답을 미리 사두는" 1회성 투자라는 것이다. 일단 그 투자가 끝나면, 어떤 사각형이든 그것을 네 개의 origin-rectangle의 가감으로 표현할 수 있으므로 쿼리가 면적과 무관해진다.
II[i][j]를 "왼쪽 위 모서리가 항상 원점 (0,0)에 고정된 직사각형의 합"으로 정의하는 것이 트릭의 전부다. 이렇게 하면 표가 단 두 변수 (i,j)로 인덱싱되어 O(N²) 크기에 들어가고(자유 모서리가 하나뿐), 동시에 임의 사각형은 네 개의 origin-rectangle 차로 정확히 복원된다. "한쪽 모서리 고정"이 저장 비용과 쿼리 비용을 동시에 잡는 설계 결정이다.
이 절은 두 가지를 증명한다. 첫째, 누적합 표 자체가 정의대로 옳게 채워진다(구축의 정당성). 둘째, 네 모서리 공식이 임의 사각형 합을 정확히 준다(쿼리의 정당성). 둘 다 포함-배제 원리에서 나온다.
1-indexed로 가장자리를 0으로 둔 표에서, 다음 점화식으로 채운 II[i][j]는 위 정의를 만족한다:
II[i][j] = img[i−1][j−1] + II[i−1][j] + II[i][j−1] − II[i−1][j−1]
매 칸을 행 우선·열 우선 순서로 채우면, II[i−1][j]·II[i][j−1]·II[i−1][j−1]은 이미 확정된 값이므로 한 번의 패스로 표 전체가 완성된다.
위 점화식으로 채운 II[i][j]는 정확히 Σ_{a≤i, b≤j} img[a][b]와 같다.
origin-rectangle R(i,j)(왼위 원점, 오른아래 (i,j))의 픽셀 집합을 생각하자. 이것은 세 영역의 조합이다.
R(i,j) = R(i−1,j) ∪ R(i,j−1) ∪ {(i,j)}의 픽셀들로 덮이는데, R(i−1,j)와 R(i,j−1)는 교집합 R(i−1,j−1)을 공유한다. 합을 셈할 때 이 교집합이 두 번 더해지므로 한 번 빼야 한다 — 포함-배제 원리:
sum R(i,j) = sum R(i−1,j) + sum R(i,j−1) − sum R(i−1,j−1) + img[i][j]
각 항이 정의상 II의 해당 칸이고, img[i][j]는 두 부분합 어디에도 포함되지 않은 모서리 픽셀이다. 이것이 점화식 그대로다. 기저(i=0 또는 j=0)는 빈 영역 합 0으로 성립하고, 귀납으로 모든 칸에 정확성이 전파된다.
왼위 (r1,c1), 오른아래 (r2,c2)인 임의 사각형(양 끝 포함)의 합은, 1-indexed II에서 정확히 네 번의 lookup으로 구해진다:
sum = II[r2+1][c2+1] − II[r1][c2+1] − II[r2+1][c1] + II[r1][c1]
목표 사각형 Q를 origin-rectangle들로 표현한다. 큰 origin-rectangle A = R(r2,c2)에서 위쪽 띠 B = R(r1−1,c2)와 왼쪽 띠 C = R(r2,c1−1)를 빼면, 둘이 겹치는 왼위 모서리 D = R(r1−1,c1−1)가 두 번 빠진다 — 한 번 도로 더한다.
sum Q = sum A − sum B − sum C + sum D
각 origin-rectangle 합이 II의 한 칸이다. 1-indexed·가장자리 0 표에서 (r2,c2)는 II[r2+1][c2+1]로, (r1−1,c2)는 II[r1][c2+1]로 사상된다(0-index 좌표 x ↦ 1-index 칸 x+1). 부호는 포함-배제 그대로 +,−,−,+. 사각형 크기 K가 식 어디에도 등장하지 않음에 주목하라 — 그것이 O(1)의 원천이다.
Theorem 2의 공식은 정확히 4개의 표 lookup과 3번의 가감으로 구성된다. 이 연산 수는 사각형 면적 K², 변 길이 K, 위치 (r,c) 그 무엇에도 의존하지 않는다.
따라서 한 번 II를 구축하면, 5×5 패치든 500×500 패치든 동일하게 O(1)에 답이 나온다. 이것이 문제 페이지가 "면적이 패치 크기와 분리되는 마법"이라 부른 것의 정확한 의미다 — 마법이 아니라 포함-배제의 산술적 귀결이다.
구현은 Theorem 1·2를 그대로 옮긴 것이다. 1-indexed 표에 0 가장자리를 두면 경계 조건 분기가 사라져 코드가 한 줄로 줄어든다.
#include <vector>using namespace std;struct IntegralImage { int N; vector<vector<long long>> II; // (N+1)×(N+1), 가장자리 0 // ── 구축: O(N²) — 한 번만 ────────────────────── IntegralImage(const vector<vector<int>>& img) { N = img.size(); II.assign(N + 1, vector<long long>(N + 1, 0)); for (int i = 1; i <= N; ++i) for (int j = 1; j <= N; ++j) II[i][j] = img[i-1][j-1] + II[i-1][j] // 위쪽 띠 + II[i][j-1] // 왼쪽 띠 - II[i-1][j-1]; // 겹친 모서리 보정 } // ── 쿼리: O(1) — 모서리 4점 (0-indexed inclusive) ── long long rectSum(int r1, int c1, int r2, int c2) const { return II[r2+1][c2+1] // + 큰 직사각형 A - II[r1 ][c2+1] // − 위쪽 띠 B - II[r2+1][c1 ] // − 왼쪽 띠 C + II[r1 ][c1 ]; // + 두 번 빠진 모서리 D }};// ── 다중 스케일 슬라이딩: 임계 T 이상 패치를 모두 수집 ──vector<int> scanPatches(const IntegralImage& ii, int N, int K, long long T) { vector<int> hits; // 평탄화한 (r,c) 좌표쌍 for (int r = 0; r + K <= N; ++r) for (int c = 0; c + K <= N; ++c) { long long s = ii.rectSum(r, c, r+K-1, c+K-1); if (s >= T) { // 임계 조건 — K와 무관하게 O(1) 판정 hits.push_back(r); hits.push_back(c); } } return hits;}
II[0][*]·II[*][0]이 0이므로 rectSum이 r1=0이나 c1=0에서도 분기 없이 동작한다. 0-index 표를 쓰면 r1−1 < 0 경계 검사가 매 쿼리에 끼어든다. (2) 누적합은 long long — 1000×1000 픽셀에 큰 값이면 int를 넘친다. (3) scanPatches가 K를 바꿔 여러 번 호출돼도 II는 재구축하지 않는다 — 같은 표 위에서 모든 스케일이 O(1) 쿼리를 공유한다.
구축: 이중 루프가 N²개 칸을 각각 O(1)(가감 3회)에 채운다 — O(N²). N=1000이면 10⁶ 연산, 한 번만.
쿼리: rectSum은 표 lookup 4회 + 가감 3회 = 상수 — O(1).
전체 스캔: 한 스케일에서 슬라이딩 위치는 (N−K+1)² ≈ N²개, 각 O(1) — O(N²). M개 스케일이면 O(N²) + O(M·N²)이고 전처리는 한 번이므로 O(N² · M). 문제 페이지가 인용한 "N=1000, K=50, Q=N²일 때 10⁶×4 = 4×10⁶"은 단일 스케일 쿼리 비용만 센 것으로, Naive의 10¹⁰ 대비 약 2500배 — 정확히 K²=2500배 절감이다.
2001년 Viola와 Jones의 얼굴 검출기는 Haar-like feature를 쓴다 — 인접한 두 직사각형 영역의 합의 차(밝은 영역 − 어두운 영역). 한 이미지 윈도에서 수천 개의 Haar feature를 평가해야 하는데, feature 하나가 직사각형 합 두세 개의 가감이다. Integral Image 없이는 feature마다 O(K²) — 실시간이 불가능하다. Integral Image 위에서는 feature 하나가 O(1)(직사각형당 4 lookup)이 되어, 30fps 실시간 검출이 처음으로 가능해졌다. Theorem 2의 4-corner 공식이 그 가능성의 직접적 엔진이었다.
CNN의 average-pooling 층은 본질적으로 "겹치지 않는 K×K 패치의 평균"이다 — 곧 직사각형 합을 K²으로 나눈 것. 다중 스케일 receptive field(같은 입력을 여러 크기 윈도로 보는 것)를 빠르게 계산할 때 Integral Image가 쓰인다: 표 한 번 구축에 모든 윈도 크기가 공짜다. ROI pooling 같은 검출 파이프라인의 영역 집계도 같은 원리에 기댄다.
3D Integral (비디오): 시간 축을 더해 II[t][i][j]를 만들면, 시공간 직육면체의 합이 8개 모서리 점의 포함-배제로 O(1). 차원 d에서 모서리 수는 2ᵈ다.
Tilted Integral (회전 사각형): 45° 기울어진 직사각형 합을 위한 대각선 누적합. Viola-Jones 확장(Lienhart)이 회전 Haar feature를 위해 도입했다.
Squared Integral (분산): img²의 누적합을 함께 들면, 패치의 합과 제곱합을 모두 O(1)에 얻어 분산 Var = E[x²]−E[x]²을 상수 시간에 계산한다. 적응형 이진화·정규화에 쓰인다.
| 접근법 | 전처리 | 쿼리당 | 총 연산 | 평가 |
|---|---|---|---|---|
| Naive — 패치 직접 합산 | 0 | O(K²) | 10¹⁰ | 패치가 커질수록 제곱으로 폭주 — 시간 벽 |
| Row prefix sum — 행별 누적 | O(N²) | O(K) | 5×10⁹ | 한 차원만 분리 — K개 행 부분합을 여전히 더함 |
| 2D Integral Image | O(N²) | O(1) | 4×10⁶ | 면적이 쿼리에서 완전 분리 — 4-corner 공식 |
| FFT convolution | O(N² log N) | — | 커널 고정 시 우수 | 커널이 가변·다중이면 매번 변환 — 오버킬 |
표의 구조는 "쿼리 비용에서 무엇을 분리했는가"의 사다리다. Naive는 아무것도 분리하지 못해 면적 K²이 그대로 쿼리에 실린다. 행 누적합은 한 차원만 분리해 쿼리를 O(K)로 낮추지만 — 여전히 K개 행 부분합을 더해야 한다. 2D Integral Image만이 두 차원 모두 분리해 면적을 쿼리에서 완전히 떼어낸다(Lemma §2). FFT 합성곱은 고정된 단일 커널을 이미지 전체에 합성곱할 때는 강력하지만, Square처럼 임계 판정만 필요하거나 커널(패치 크기)이 다중·가변이면 매번 O(N² log N) 변환을 치르는 오버킬이다. 임의 크기 직사각형 합을 반복 쿼리하는 문제에서 2D Integral Image는 단순함과 O(1) 쿼리를 동시에 주는 정확한 도구다.
II는 1-indexed(가장자리 0), 입력 이미지와 쿼리 좌표는 0-indexed다. rectSum의 네 칸은 II[r2+1][c2+1]·II[r1][c2+1]·II[r2+1][c1]·II[r1][c1] — r2,c2는 +1, r1,c1은 그대로다. 한 칸이라도 어긋나면 사각형이 한 줄씩 밀려 합이 틀린다.
int 범위(약 2.1×10⁹)를 넘길 수 있다. II와 rectSum 반환형을 long long으로 둬라. Squared Integral은 제곱이 들어가 더 빨리 넘친다.
r + K ≤ N(즉 r ≤ N−K)까지만 유효하다. 루프 조건을 r < N으로 두면 이미지 밖을 참조하거나, r + K < N으로 두면 마지막 한 줄을 빠뜨린다.
K가 바뀔 때마다 II를 다시 만들면 전처리 O(N²)이 스케일 수만큼 곱해진다. II는 이미지에만 의존하므로 한 번 구축해 모든 스케일이 공유해야 한다 — 그것이 Integral Image의 핵심 이득이다.
이 풀이의 정확성 주장은 Theorem 1·2의 증명에 더해, Naive 합산과의 직접 대조로 경험적으로 확인된다. 작은 이미지의 모든 사각형에 대해 rectSum과 무식한 이중 합산이 일치하면 구현이 옳다.
rectSum 결과와 이중 루프 직접 합산을 비교한다. 전부 일치하면 4-corner 공식과 1-index 오프셋이 옳다. 문제 페이지의 시각화(8×8 격자, 3×3 패치 (2,3)–(4,5)를 II[5][6]−II[2][6]−II[5][3]+II[2][3]로 평가)가 정확히 이 검증의 한 사례다 — 그 식의 네 칸이 본 구현 rectSum(2,3,4,5)의 II[5][6]·II[2][6]·II[5][3]·II[2][3]과 글자 그대로 일치한다.