§ 1문제 정의
N×N 이미지에서 어떤 조건을 만족하는 K×K(또는 가변) 사각형을 모두 찾아라. 사각형 안 픽셀의 합/평균/패턴이 임계 조건을 만족해야 한다.
핵심 통찰: 모든 위치에서 모든 패치 크기를 검사해야 하므로 시간 복잡도가 폭주한다. Naive는 O(N² × K²) — N=K=1000이면 10¹². 불가능.
해법은 Integral Image (누적합). 사전 계산 O(N²) 한 번, 이후 임의의 사각형 합을 O(1)에 4번의 lookup으로. CNN의 max-pooling, Viola-Jones face detection의 기반.
사각형의 합은 모서리 4점 차로 구해진다 — 면적과 무관한 상수 시간. 이게 모든 이미지 처리의 비밀.
§ 2Integral Image 구축 + 슬라이딩
8×8 격자에서 누적합 표 생성. 3×3 패치를 4번의 lookup으로 평가하는 모습.
FIG. 21 — integral image and 4-corner trick
STEP 01 / 5
SPACE play/pause · ← → step · R reset
§ 3왜 Integral이 최적인가
| 접근법 | 전처리 | 쿼리당 | 총 (N=1000, K=50, Q=N²) |
|---|---|---|---|
| Naive | 0 | O(K²) | 10¹⁰ 연산 |
| Row prefix sum | O(N²) | O(K) | 5×10⁹ |
| 2D Integral Image | O(N²) | O(1) | 10⁶ × 4 = 4×10⁶ |
| FFT convolution | O(N² log N) | O(N² log N) | 커널 고정 시 좋음 |
다중 스케일이 진짜 위력: CNN의 다중 receptive field, Viola-Jones의 Haar-like features 모두 이 트릭에 기반. 한 번 II 구축하면 K가 5든 500이든 동일 O(1) 쿼리.
확장: 3D Integral (비디오), Tilted Integral (회전된 사각형), Squared Integral (분산 계산용).
전처리 O(N²)는 한 번. 쿼리는 모서리 4번. 면적이 패치와 분리되는 마법.
§ 4알고리즘 골격
build_integral(img, N):
II = new int[N+1][N+1] # 1-indexed, 가장자리는 0
for i in 1..N:
for j in 1..N:
II[i][j] = img[i-1][j-1]
+ II[i-1][j]
+ II[i][j-1]
− II[i-1][j-1]
rect_sum(II, r1, c1, r2, c2): # 0-indexed inclusive
# 1-indexed로 변환
return II[r2+1][c2+1]
− II[r1 ][c2+1]
− II[r2+1][c1 ]
+ II[r1 ][c1 ]
solve(img, N, K, threshold):
II = build_integral(img, N)
results = []
for r in 0..N-K:
for c in 0..N-K:
s = rect_sum(II, r, c, r+K-1, c+K-1)
if s >= threshold:
results.append((r, c))
return results
# 다중 스케일
for K in K_list:
for r in ...: for c in ...:
rect_sum(II, r, c, r+K-1, c+K-1) # 여전히 O(1)