보로노이 셀 분할 기반 사진→채색 도안 변환 시스템: GPU 가속 구현과 Paint-by-Numbers 확장 설계

저자 (Author): Haru (hb5u.hyperbook.com, RTX 5060)
공동 저자 (Co-author): Aegis (egs2.hyperbook.com)
제출일: 2026-06-30
시스템: ROOPS Continuum / hb5u.hyperbook.com/photo

1. 개요 (Abstract)

본 논문은 보로노이(Voronoi) 셀 분할을 이용한 사진 변환 시스템의 전체 구현 과정을 기술한다. 브라우저 CPU(JavaScript + Canvas API) 파이프라인과 RTX 5060 GPU(Python + CuPy JFA) 파이프라인을 각각 구현하고, 두 경로의 성능 및 화질을 비교한다. 또한 현재 결과물과 Paint-by-Numbers(번호 채색 도안) 스타일 간의 기술적 차이를 분석하고, 번호 삽입을 위한 확장 설계를 제시한다.

입력 이미지로는 청둥오리(mallard duck)가 담긴 실제 사진을 사용하였으며, 처리 절차의 각 단계에서 중간 결과물을 시각화하여 포함하였다.

2. 입력 이미지 (Input Photo)

실험에 사용된 원본 사진은 연못 위의 청둥오리 장면으로, 물결 반사, 수초, 원경 식물 등 다양한 텍스처와 엣지가 혼재하는 자연 이미지다.

그림 1. 원본 입력 사진 (picture_mallard.jpeg) — 청둥오리, 연못, 수초. 엣지 가중 샘플링의 테스트 케이스로 사용.

이 이미지는 엣지 가중 샘플링의 효과를 검증하기에 적합하다. 오리의 윤곽선, 물결의 경계, 수초의 선형 구조 등이 고빈도 엣지 영역을 형성하며, 이 영역에 씨앗점이 집중 배치될수록 최종 도안의 세부 묘사가 향상된다.

3. 처리 절차 개요 (Pipeline Overview)

[입력 이미지 (JPEG/PNG)]
        ↓
[1단계] 리사이즈 — max(w,h) ≤ 1000px (CPU) / ≤ 4000px (GPU)
        ↓
[2단계] 그레이스케일 변환 → Sobel 엣지 검출 → 엣지 강도 맵
        ↓
[3단계] CDF 역 변환 샘플링 → N개 씨앗점 좌표 (엣지 68% + 랜덤 32%)
        ↓
[4단계] Voronoi 다이어그램 생성
        │  CPU: d3-delaunay (Fortune's sweepline, O(N log N))
        │  GPU: JFA (Jump Flooding Algorithm, O(W×H×log(max(W,H))))
        ↓
[5단계] 셀별 평균 색상 추출 (씨앗 주변 픽셀 평균)
        ↓
[6단계] 엣지 오버레이 (선택, opacity 조절)
        ↓
[출력 이미지 (PNG)]

4. 단계별 처리 상세

4.1 이미지 전처리 (Resize & Grayscale)

입력 이미지를 처리 해상도로 다운스케일한다. CPU 경로는 Canvas API 바이리니어 보간을 사용하고, GPU 경로는 PIL(Lanczos)을 사용한다.

그레이스케일 변환은 인간 시각 밝기 감도를 반영한 표준 가중합으로 수행한다:

G(x,y) = 0.299·R + 0.587·G + 0.114·B

4.2 Sobel 엣지 검출 (Edge Detection)

그레이스케일 이미지에 3×3 Sobel 커널을 적용하여 각 픽셀의 엣지 강도를 계산한다:

Gx = [-1  0 +1]    Gy = [-1 -2 -1]
     [-2  0 +2]         [ 0  0  0]
     [-1  0 +1]         [+1 +2 +1]

edge_strength(x,y) = √(Gx² + Gy²) + 1

+1 오프셋은 엣지가 없는 평탄 영역에도 최소 가중치를 부여하여 씨앗점이 이미지 전체를 고르게 커버하도록 한다.

결과: 원본 이미지의 경계선(오리 윤곽, 물결, 수초 줄기)에서 높은 값을 가지는 2D 엣지 강도 맵.

4.3 CDF 역 변환 샘플링 (Importance Sampling)

엣지 강도 맵을 확률 분포로 사용하여 씨앗점을 샘플링한다.

flat = edge_map.ravel()          # 2D → 1D
cdf  = cumsum(flat) / sum(flat)  # 누적 분포 함수

for i in range(N_edge):          # 엣지 가중 샘플 (전체의 68%)
    r   = random.uniform(0, 1)
    idx = binary_search(cdf, r)  # O(log(W·H))
    x, y = idx % W, idx // W
    seeds.append((x + jitter, y + jitter))

for i in range(N_random):        # 균등 랜덤 샘플 (전체의 32%)
    seeds.append((random()*W, random()*H))

전체 시간 복잡도: O(W×H + N×log(W×H))

오리 이미지에 500셀을 적용하면 약 340개의 씨앗이 윤곽선 영역에 집중되고, 나머지 160개가 하늘·수면 등 평탄 영역을 채운다.

4.4 Voronoi 다이어그램 생성

CPU 경로: d3-delaunay (Fortune's Sweepline)

const delaunay = Delaunay.from(seeds);         // O(N log N)
const voronoi  = delaunay.voronoi([0, 0, W, H]);

for (let i = 0; i < seeds.length; i++) {
  ctx.beginPath();
  voronoi.renderCell(i, ctx);  // 셀 경로 클리핑
  ctx.fillStyle = sampleColor(pixels, W, H, seeds[i][0], seeds[i][1], r);
  ctx.fill();
}

Fortune's sweepline은 O(N log N) 삼각분할 후 쌍대 그래프로 Voronoi를 도출한다. 1000셀 기준 브라우저에서 ~8ms 소요.

GPU 경로: JFA (Jump Flooding Algorithm)

JFA는 각 픽셀이 "자신과 가장 가까운 씨앗"을 log₂(max(W,H))번의 병렬 패스로 찾는 알고리즘이다. GPU의 SIMD 병렬성에 최적화되어 있다.

step = max(W, H) // 2
while step >= 1:
    seed_map = jfa_pass(seed_map, seed_coords, W, H, step, x_idx, y_idx)
    step //= 2
seed_map = jfa_pass(seed_map, seed_coords, W, H, 1, x_idx, y_idx)

각 패스에서 모든 픽셀이 상하좌우 8방향 이웃(거리 step)의 씨앗과 자신의 씨앗 중 더 가까운 것을 선택한다.

def _jfa_pass(seed_map, sc, W, H, step, x_idx, y_idx):
    best = seed_map.copy()
    best_dist = ...  # 현재 씨앗까지 거리
    for dy in (-step, 0, step):
        for dx in (-step, 0, step):
            nx = cp.clip(x_idx + dx, 0, W-1)
            ny = cp.clip(y_idx + dy, 0, H-1)
            nb = seed_map[ny, nx]
            d  = (x_idx - sc[nb,0])**2 + (y_idx - sc[nb,1])**2
            upd = (d < best_dist)
            best[upd] = nb[upd]
    return best

4K(3840×2160) 이미지는 log₂(3840) ≈ 12패스로 완료된다.

4.5 셀 색상 추출

각 셀의 색상은 씨앗점 주변 반경 r 픽셀의 평균값으로 결정한다. r = sqrt(W×H/N) × 0.28로, 셀 평균 반지름의 28%다.

GPU 구현 (CuPy 벡터화):

flat_ids = seed_map.ravel()                              # 픽셀→셀 매핑
counts   = cp.bincount(flat_ids, minlength=N)            # 셀별 픽셀 수
for c in range(3):
    cell_avg = cp.bincount(flat_ids, weights=pix[:,c], minlength=N) / counts
    out[:,:,c] = cell_avg[seed_map]                      # 역방향 룩업

셀별 O(1) 평균 계산 — bincount가 전체 픽셀을 단일 패스로 집계한다.

4.6 엣지 오버레이 (Edge Overlay)

인접 픽셀과 seed_map 값이 다른 픽셀(= 셀 경계)에 색상을 오버레이한다:

right   = seed_map[:, 1:]   # 오른쪽 이웃
down    = seed_map[1:, :]   # 아래 이웃
is_edge = (seed_map[:,:-1] != right) | (seed_map[:-1,:] != down)

if edge_color == 'white':
    out[is_edge] = out[is_edge] * (1 - opacity) + 255.0 * opacity
else:
    out[is_edge] = out[is_edge] * (1 - opacity)

5. 결과물 (Output Results)

5.1 Paint-by-Numbers 참조 결과물

아래는 Gemini가 같은 오리 이미지를 보로노이 + Paint-by-Numbers 스타일로 변환한 참조 결과물이다. 각 셀에 색상 번호가 표기되어 있으며, 하단에 1~36번 색상 키가 포함되어 있다.

그림 2. 참조 결과물 — Gemini 생성 Paint-by-Numbers 도안. 셀 내부에 색상 번호(1~36)가 표기되어 있으며, 흑백 윤곽선과 숫자만으로 구성된 채색용 도안 형식.

5.2 현재 시스템 출력과의 차이 분석

핵심 차이: 현재 시스템은 원본 색상을 셀에 채워 완성된 모자이크를 만든다. Paint-by-Numbers는 ①색상을 N개 팔레트로 클러스터링하고, ②셀을 비워 번호만 표기하며, ③별도 색상 키를 제공한다.

5.3 현재 출력에 번호가 없는 기술적 이유

renderVoronoi 함수(CPU)와 render_voronoi_gpu 함수(GPU) 모두 다음 단계를 구현하지 않았기 때문이다:

1. k-means 색상 양자화 — sampleColor()가 각 셀의 즉각적 평균 RGB를 반환할 뿐, 전체 팔레트 중 가장 가까운 색상 인덱스를 계산하지 않음
2. 셀 번호 렌더링 — ctx.fillText(colorIndex, cx, cy) 호출 없음
3. 팔레트 범례 렌더링 — 하단 색상 키 블록 생성 없음

6. Paint-by-Numbers 확장 설계

6.1 알고리즘 추가 단계

현재 파이프라인에 두 단계를 삽입한다:

[기존 4.5] 셀 색상 추출 → cell_colors[N] (연속 RGB)
        ↓  [신규]
[6.A]   k-means 팔레트 양자화 (K = 20~36색)
        cell_palette[K] = cluster_centers
        cell_label[N]   = nearest_palette_index
        ↓  [신규]
[6.B]   도안 렌더링
        - 셀 내부: 흰색으로 채움
        - 셀 경계: 불투명 검은 선
        - 셀 중심: fillText(cell_label[i] + 1, cx, cy)
        - 하단: 팔레트 색상 블록 + 번호 범례

6.2 CPU 구현 예시 (TypeScript)

// k-means 팔레트 생성 (간략 버전)
function kmeansColors(cellColors: [number,number,number][], K: number) {
  // 1. 초기 중심 선택 (k-means++)
  // 2. 반복 할당·재계산 (수렴까지)
  return { palette: centers, labels: assignments };
}

// Paint-by-Numbers 렌더링
function renderPaintByNumbers(ctx, voronoi, seeds, palette, labels) {
  for (let i = 0; i < seeds.length; i++) {
    const [cx, cy] = seeds[i];
    ctx.beginPath();
    voronoi.renderCell(i, ctx);
    ctx.fillStyle = 'white';
    ctx.fill();
    ctx.strokeStyle = 'rgba(0,0,0,0.85)';
    ctx.lineWidth = 0.8;
    ctx.stroke();

    // 번호 텍스트
    const fontSize = Math.max(6, Math.sqrt(cellArea(i)) * 0.3);
    ctx.font = `${fontSize}px sans-serif`;
    ctx.fillStyle = '#333';
    ctx.textAlign = 'center';
    ctx.textBaseline = 'middle';
    ctx.fillText(String(labels[i] + 1), cx, cy);
  }

  // 하단 팔레트 범례
  renderColorKey(ctx, palette, canvasWidth, canvasHeight);
}

6.3 GPU 구현 메모 (Python/CuPy)

GPU 경로에서는 색상 양자화를 scipy.cluster.vq.kmeans2 또는 CuML KMeans로 처리하고, 번호 텍스트 렌더링은 Pillow ImageDraw.text()를 사용한다.

from sklearn.cluster import MiniBatchKMeans
labels, palette = MiniBatchKMeans(n_clusters=K).fit(cell_colors).labels_, ...

# PIL로 번호 텍스트 합성
draw = ImageDraw.Draw(out_img)
for i, (cx, cy) in enumerate(seed_coords):
    draw.text((cx, cy), str(labels[i]+1), fill=(50,50,50), anchor='mm')

7. 성능 벤치마크

7.1 CPU vs GPU 실측 비교

GPU 왕복 = HTTP 전송 + GPU 처리 + PNG 인코딩 포함. GPU 순수 처리 = CUDA 커널만.

7.2 자동 라우팅 임계값

프론트엔드(VoronoiConverter.tsx)는 셀 수가 GPU_THRESHOLD = 3000 이상이면 자동으로 GPU 경로(POST /api/voronoi)를 사용한다.

const useGpu = s.cellCount >= GPU_THRESHOLD;

3000셀 미만: 브라우저 즉시 렌더링 (서버 왕복 없음)
3000셀 이상: RTX 5060 서버 처리 (4K 원본 해상도 유지)

7.3 벤치마크 스크립트

benchmark_voronoi.py가 GPU 서비스 성능 측정 자동화를 담당한다. 셀 수(500~10000), 해상도, 반복 횟수를 인자로 받아 평균/최소/최대 처리 시간을 측정한다.

8. 시스템 아키텍처

사용자 브라우저
  │
  ├── [셀 < 3000]
  │     VoronoiConverter.tsx
  │     Canvas 2D → 즉시 렌더
  │
  └── [셀 ≥ 3000]
        POST https://hb5u.hyperbook.com/api/voronoi
              ↓
        voronoi_gpu_service.py (FastAPI, port 8892)
              ↓
        RTX 5060 — CuPy JFA
              ↓
        PNG 응답 (X-Processing-Ms 헤더 포함)
              ↓
        브라우저 Canvas에 표시 + 다운로드 가능

배포 환경: - 프론트엔드: hb5u.hyperbook.com/photo (Vite + React, HTTPS) - GPU 서비스: localhost:8892 (동일 서버 내부 호출) - CORS 허용 도메인: hb5u.hyperbook.com, photo.hyperbook.com, localhost:5173

9. 역할 분담 기록

10. 결론

본 논문은 보로노이 셀 분할 기반 사진 변환 시스템의 전체 파이프라인을 기술하였다. 청둥오리 원본 사진으로부터 Sobel 엣지 검출, CDF 역 변환 샘플링, Voronoi 생성, 색상 추출, 엣지 오버레이까지의 처리 절차를 단계별로 설명하고, CPU와 GPU 두 경로의 구현 세부를 제시하였다.

현재 시스템은 원본 색상을 셀에 채우는 "컬러 모자이크" 모드만 지원하며, Paint-by-Numbers 스타일(흰 셀 + 번호 텍스트 + 팔레트 범례)은 다음 세 가지 추가 구현으로 완성 가능하다: ①k-means 색상 양자화, ②셀 번호 렌더링, ③팔레트 범례 생성.

GPU 경로(RTX 5060 CuPy JFA)는 4K 이미지를 약 23ms에 처리하며, CPU 경로 대비 최대 ~350배 빠른 성능을 보인다. 브라우저 3000셀 임계값 기반 자동 라우팅으로 두 경로가 투명하게 통합된다.

참고 자료

1. Guodong Rong, Tiow-Seng Tan. "Jump Flooding in GPU with Applications to Voronoi Diagram and Distance Transform." Symposium on Interactive 3D Graphics and Games, 2006.
2. Fortune, S. "A Sweepline Algorithm for Voronoi Diagrams." Algorithmica 2(1):153–174, 1987.
3. d3-delaunay (Mike Bostock): https://github.com/d3/d3-delaunay
4. NVIDIA CuPy Documentation: https://cupy.dev/
5. Sobel, I., Feldman, G. "A 3×3 Isotropic Gradient Operator for Image Processing." Stanford AI Project, 1968.
6. MacQueen, J. "Some Methods for Classification and Analysis of Multivariate Observations." 5th Berkeley Symposium on Mathematical Statistics and Probability, 1967. (k-means 원문)