"""8장 · Deformable DETR: 필요한 곳만 보기 — 변형 어텐션과 미니 Deformable DETR.

무엇을 하나
  1. 쌍선형 보간 bilinear_sample 을 직접 만들고 F.grid_sample 과 대조한다 (본문 손계산 예 포함).
  2. 다중 스케일 변형 어텐션 MSDeformAttn: 질의마다 기준점 주위의 표본점 M·L·K 개만 읽는다.
     기준이 점(2차원)일 때와 박스(4차원)일 때를 모두 만들고, 한 질의의 출력을 손으로 다시 계산해 대조한다.
  3. 보통 교차 어텐션과 변형 어텐션의 연산 수 · 시간을 특징 맵 크기를 키워 가며 비교한다.
  4. MiniDeformableDETR: 7장의 백본 · 매칭을 그대로 쓰고, 디코더 교차 어텐션을 변형 어텐션으로,
     박스 반복 정제, 클래스별 시그모이드 + 포컬 손실, (선택) 2단계 질의 선택을 넣는다.
  5. 실험: 7장 MiniDETR 과 수렴 속도 비교, 박스 반복 정제 · 2단계 · 다중 스케일 · 인코더의 유무 절제(각 시드 1개),
     표본점이 실제로 찍히는 자리, 디코더 층마다 박스가 정제되는 모습.
  6. 체크포인트 ch08_deformable.pt (본 모델) · ch08_two_stage.pt (2단계 절제 모델)와 학습 기록
     ch08_history.json 을 실행 폴더에 저장한다.

실행
  python ch08_deformable.py            # 본문 결과 (노트북 GPU 약 27분 — 다른 작업과 GPU 를 나눠 쓰며 잰 값).
                                       # ch07_history.json 이 같은 폴더에 있으면 7장의 곡선을 겹쳐 그린다
  python ch08_deformable.py --quick    # 연기 시험 (CPU 약 30초)
그림은 --fig-dir (기본 figures/) 에 저장된다.

9장부터의 실습 파일이 이 파일의 inverse_sigmoid · bilinear_sample · MSDeformAttn · DeformableDecoderLayer ·
gen_proposals · sigmoid_focal_loss · FocalSetCriterion · postprocess_sigmoid · MiniDeformableDETR 를 가져다 쓴다.
"""

from __future__ import annotations

import argparse
import json
import math
import os
import time

import numpy as np
import torch
import torch.nn as nn
import torch.nn.functional as F

from ch02_boxes import box_cxcywh_to_xyxy, paired_box_iou
from ch03_metrics import evaluate_ap
from ch07_detr import (MLP, HungarianMatcher, SetCriterion, SmallBackbone, TransformerEncoderLayer, collect_outputs,
                       fit, get_device, layer_report, plot_layers, plot_predictions, sine_embed, sine_position_2d)
from rf_shapes import CLASS_NAMES, NUM_CLASSES, ShapesDataset, draw_boxes, make_loader


# ── 1. 쌍선형 보간 ───────────────────────────────────────────────────────────


# --8<-- [start:inverse-sigmoid]
def inverse_sigmoid(x: torch.Tensor, eps: float = 1e-5) -> torch.Tensor:
    """시그모이드의 역함수 σ⁻¹(x) = log(x / (1 − x)). 0 – 1 의 좌표를 "로짓 공간" 으로 되돌린다.

    x 가 0 이나 1 에 닿으면 값이 ±∞ 가 되므로 분자 · 분모를 eps 이상으로 자른다.
    """
    x = x.clamp(min=0.0, max=1.0)
    return torch.log(x.clamp(min=eps) / (1 - x).clamp(min=eps))
# --8<-- [end:inverse-sigmoid]


# --8<-- [start:bilinear]
def bilinear_sample(feature: torch.Tensor, points: torch.Tensor) -> torch.Tensor:
    """특징 맵의 "칸과 칸 사이" 의 값을 쌍선형 보간으로 읽는다.

    feature: (C, H, W) 특징 맵.  points: (P, 2) — 정규화 좌표 (x, y), 0 – 1. 돌려주는 값: (P, C).

    좌표 규약 (F.grid_sample 의 align_corners=False 와 같다):
      - 특징 맵 전체가 [0, 1] × [0, 1] 이고, 칸 (행 r, 열 c) 은 가로 [c/W, (c+1)/W], 세로 [r/H, (r+1)/H] 를 차지한다.
      - 칸의 값은 칸의 중심 ((c + 0.5)/W, (r + 0.5)/H) 에 놓여 있다고 본다.
      - 그러므로 정규화 좌표 x 를 "열 번호 눈금" 으로 바꾸면 px = x·W − 0.5 (중심이 정수가 되게).
    맵 밖의 칸은 값이 0 이라고 본다 (padding_mode="zeros").
    """
    channels, height, width = feature.shape
    px = points[:, 0] * width - 0.5  # (P,) 열 눈금에서의 위치
    py = points[:, 1] * height - 0.5  # (P,) 행 눈금에서의 위치
    x0, y0 = torch.floor(px), torch.floor(py)  # 왼쪽 위 이웃 칸의 번호
    tx, ty = px - x0, py - y0  # 왼쪽 위 이웃에서 오른쪽 · 아래로 얼마나 갔는가 (0 – 1)
    output = feature.new_zeros(len(points), channels)
    # 네 이웃: (dy, dx) = (0,0) 왼쪽 위, (0,1) 오른쪽 위, (1,0) 왼쪽 아래, (1,1) 오른쪽 아래
    for dy, dx in ((0, 0), (0, 1), (1, 0), (1, 1)):
        col, row = x0 + dx, y0 + dy
        weight = (tx if dx else 1 - tx) * (ty if dy else 1 - ty)  # 가까운 이웃일수록 큰 가중치. 넷의 합은 1
        inside = (col >= 0) & (col < width) & (row >= 0) & (row < height)
        value = feature[:, row.clamp(0, height - 1).long(), col.clamp(0, width - 1).long()].T  # (P, C)
        output += (weight * inside)[:, None] * value  # 맵 밖 이웃은 0 으로 친다
    return output
# --8<-- [end:bilinear]


# --8<-- [start:bilinear-check]
def bilinear_checks():
    """손계산 예와 F.grid_sample 대조."""
    print("[쌍선형 보간] 손계산 예: 3×3 특징 맵 (채널 1개)")
    feature = torch.tensor([[[1.0, 2.0, 4.0], [3.0, 5.0, 7.0], [6.0, 8.0, 9.0]]])  # (1, 3, 3)
    print(feature[0].numpy())
    point = torch.tensor([[0.60, 0.45]])  # (x, y)
    px, py = float(point[0, 0]) * 3 - 0.5, float(point[0, 1]) * 3 - 0.5
    x0, y0 = math.floor(px), math.floor(py)
    tx, ty = px - x0, py - y0
    print(f"점 (x, y) = (0.60, 0.45) → 눈금 좌표 px = 0.60·3 − 0.5 = {px:.2f}, py = 0.45·3 − 0.5 = {py:.2f}")
    print(f"왼쪽 위 이웃 (행 {y0}, 열 {x0}), tx = {tx:.2f}, ty = {ty:.2f}")
    total = 0.0
    for dy, dx, name in ((0, 0, "왼쪽 위"), (0, 1, "오른쪽 위"), (1, 0, "왼쪽 아래"), (1, 1, "오른쪽 아래")):
        weight = (tx if dx else 1 - tx) * (ty if dy else 1 - ty)
        value = float(feature[0, y0 + dy, x0 + dx])
        total += weight * value
        print(f"  {name:6s} (행 {y0 + dy}, 열 {x0 + dx}) 값 {value:.0f} × 가중치 {weight:.4f} = {weight * value:.4f}")
    print(f"  합 = {total:.4f},  bilinear_sample = {float(bilinear_sample(feature, point)):.4f},  "
          f"F.grid_sample = {float(F.grid_sample(feature[None], 2 * point.view(1, 1, 1, 2) - 1, align_corners=False)):.4f}")
    corner = torch.tensor([[0.02, 0.02]])
    print(f"  모서리 근처 (0.02, 0.02): bilinear_sample = {float(bilinear_sample(feature, corner)):.4f} "
          "(맵 밖 이웃 셋은 0 으로 친다)")

    generator = torch.Generator().manual_seed(0)
    feature = torch.randn(8, 12, 9, generator=generator)
    points = torch.rand(1000, 2, generator=generator) * 1.2 - 0.1  # 일부는 맵 밖 (−0.1 – 1.1)
    mine = bilinear_sample(feature, points)
    reference = F.grid_sample(feature[None], 2 * points.view(1, 1, -1, 2) - 1, mode="bilinear",
                              padding_mode="zeros", align_corners=False)[0, :, 0].T
    print(f"check bilinear_sample vs F.grid_sample (8×12×9 맵, 점 1000개, 맵 밖 포함): "
          f"최대 차이 {float((mine - reference).abs().max()):.2e}")
# --8<-- [end:bilinear-check]


# ── 2. 변형 어텐션 ───────────────────────────────────────────────────────────


# --8<-- [start:msda-core]
def ms_deform_attn_core(value, spatial_shapes, sampling_locations, attention_weights):
    """변형 어텐션의 핵심: 표본점에서 값을 읽어(쌍선형 보간) 어텐션 가중치로 가중합한다.

    value               (B, M, C/M, ΣHW)      머리별로 나눈 값 (모든 레벨을 이어 붙인 토큰)
    spatial_shapes      [(H_0, W_0), …]       레벨마다의 특징 맵 크기
    sampling_locations  (B, Nq, M, L, K, 2)   표본점의 정규화 좌표 (x, y)
    attention_weights   (B, Nq, M, L, K)      머리마다 L·K 개 표본점에 걸친 합이 1
    돌려주는 값          (B, Nq, C)            머리 M 개의 결과를 이어 붙인 것
    """
    batch, heads, head_dim, _ = value.shape
    num_queries = sampling_locations.shape[1]
    levels = value.split([h * w for h, w in spatial_shapes], dim=-1)
    grids = 2 * sampling_locations - 1  # grid_sample 은 좌표를 −1 – 1 로 받는다
    sampled = []
    for level, (height, width) in enumerate(spatial_shapes):
        value_map = levels[level].reshape(batch * heads, head_dim, height, width)  # 머리를 배치 축으로
        grid = grids[:, :, :, level].transpose(1, 2).flatten(0, 1)  # (B·M, Nq, K, 2)
        # (B·M, C/M, Nq, K): 질의 Nq 개 × 표본점 K 개 자리의 값. bilinear_sample 과 같은 계산을 한꺼번에 한다
        sampled.append(F.grid_sample(value_map, grid, mode="bilinear", padding_mode="zeros", align_corners=False))
    sampled = torch.stack(sampled, dim=-2).flatten(-2)  # (B·M, C/M, Nq, L·K)
    weights = attention_weights.transpose(1, 2).reshape(batch * heads, 1, num_queries, -1)  # (B·M, 1, Nq, L·K)
    output = (sampled * weights).sum(-1)  # (B·M, C/M, Nq): 표본점에 걸친 가중합
    return output.view(batch, heads * head_dim, num_queries).transpose(1, 2)  # (B, Nq, C)
# --8<-- [end:msda-core]


# --8<-- [start:msda]
class MSDeformAttn(nn.Module):
    """다중 스케일 변형 어텐션 (Deformable DETR). 매개변수 이름 · 초기화는 공식 구현과 같다.

    질의 하나가 하는 일 (머리 m = 1 … M, 레벨 l = 1 … L, 표본점 k = 1 … K):
      1) 오프셋 Δp_mlk = Linear(질의)            — 기준점에서 얼마나 떨어진 곳을 볼지 (2차원)
      2) 가중치 A_mlk  = softmax(Linear(질의))   — 머리마다 L·K 개에 걸쳐 합이 1
      3) 값     x(p + Δp_mlk)                    — 값 투영을 거친 특징 맵에서 쌍선형 보간으로 읽는다
      4) 출력   = 출력 투영( 머리마다 Σ_l Σ_k A_mlk · x_l(p_l + Δp_mlk) 를 이어 붙인 것 )
    열쇠와의 내적이 없다: "어디를 볼지" 도 "얼마나 볼지" 도 질의만 보고 정한다.
    """

    def __init__(self, d_model: int = 128, n_levels: int = 2, n_heads: int = 8, n_points: int = 2):
        super().__init__()
        assert d_model % n_heads == 0
        self.d_model, self.n_levels, self.n_heads, self.n_points = d_model, n_levels, n_heads, n_points
        self.sampling_offsets = nn.Linear(d_model, n_heads * n_levels * n_points * 2)
        self.attention_weights = nn.Linear(d_model, n_heads * n_levels * n_points)
        self.value_proj = nn.Linear(d_model, d_model)
        self.output_proj = nn.Linear(d_model, d_model)
        self._reset_parameters()

    def _reset_parameters(self):
        # 오프셋: 가중치는 0, 편향만 정해 준다 → 처음에는 어떤 질의든 같은 무늬로 표본점을 찍는다.
        # 머리 m 은 각도 2πm/M 방향을 맡고(최댓값 노름으로 나눠 정사각형 테두리 위의 8방향이 된다),
        # k 번째 표본점은 그 방향으로 k 칸 떨어진 곳 → 기준점 주위를 골고루 본다.
        nn.init.constant_(self.sampling_offsets.weight, 0.0)
        thetas = torch.arange(self.n_heads, dtype=torch.float32) * (2.0 * math.pi / self.n_heads)
        grid = torch.stack([thetas.cos(), thetas.sin()], -1)  # (M, 2)
        grid = grid / grid.abs().max(-1, keepdim=True)[0]
        grid = grid.view(self.n_heads, 1, 1, 2).repeat(1, self.n_levels, self.n_points, 1)  # (M, L, K, 2)
        for k in range(self.n_points):
            grid[:, :, k, :] *= k + 1
        with torch.no_grad():
            self.sampling_offsets.bias = nn.Parameter(grid.view(-1))
        # 어텐션 가중치: 가중치 · 편향 모두 0 → 소프트맥스를 거치면 모든 표본점이 1/(L·K) 로 같다
        nn.init.constant_(self.attention_weights.weight, 0.0)
        nn.init.constant_(self.attention_weights.bias, 0.0)
        nn.init.xavier_uniform_(self.value_proj.weight)
        nn.init.constant_(self.value_proj.bias, 0.0)
        nn.init.xavier_uniform_(self.output_proj.weight)
        nn.init.constant_(self.output_proj.bias, 0.0)

    def forward(self, query, reference_points, value, spatial_shapes, return_details: bool = False):
        """query            (B, Nq, C)
        reference_points (B, Nq, L, 2) 기준점 (x, y)  또는  (B, Nq, L, 4) 기준 박스 (cx, cy, w, h) — 정규화 0 – 1
        value            (B, ΣHW, C)  레벨 0 의 토큰 H_0·W_0 개, 레벨 1 의 토큰 … 을 차례로 이어 붙인 것 (행 우선)
        spatial_shapes   [(H_0, W_0), …, (H_{L−1}, W_{L−1})]
        돌려주는 값: (B, Nq, C).  return_details=True 면 (출력, 표본점 (B, Nq, M, L, K, 2), 가중치 (B, Nq, M, L, K)).
        """
        batch, num_queries, _ = query.shape
        heads, levels, points = self.n_heads, self.n_levels, self.n_points
        assert value.shape[1] == sum(h * w for h, w in spatial_shapes)

        value = self.value_proj(value)  # (B, ΣHW, C)
        value = value.transpose(1, 2).reshape(batch, heads, self.d_model // heads, -1)  # (B, M, C/M, ΣHW)
        offsets = self.sampling_offsets(query).view(batch, num_queries, heads, levels, points, 2)
        weights = self.attention_weights(query).view(batch, num_queries, heads, levels * points)
        weights = weights.softmax(-1).view(batch, num_queries, heads, levels, points)

        if reference_points.shape[-1] == 2:
            # 기준이 점: 오프셋의 단위는 "그 레벨 특징 맵의 칸". (W_l, H_l) 로 나눠 정규화 좌표로 바꾼다
            normalizer = torch.tensor([[w, h] for h, w in spatial_shapes], dtype=query.dtype, device=query.device)
            locations = reference_points[:, :, None, :, None, :] + offsets / normalizer[None, None, None, :, None, :]
        elif reference_points.shape[-1] == 4:
            # 기준이 박스: 오프셋의 단위는 "박스 절반 크기의 1/K". 박스가 크면 넓게, 작으면 좁게 본다.
            # 초기 편향(k 번째 점이 k 칸)에서는 k/K · (w/2, h/2) → 처음 표본점은 모두 박스 안에 있다.
            locations = (reference_points[:, :, None, :, None, :2]
                         + offsets / points * reference_points[:, :, None, :, None, 2:] * 0.5)
        else:
            raise ValueError("reference_points 의 마지막 차원은 2 또는 4 여야 한다")

        output = self.output_proj(ms_deform_attn_core(value, spatial_shapes, locations, weights))
        return (output, locations, weights) if return_details else output
# --8<-- [end:msda]


# --8<-- [start:msda-check]
def msda_checks():
    """MSDeformAttn 의 출력을, 질의 하나에 대해 bilinear_sample 로 식 그대로 다시 계산해 대조한다."""
    torch.manual_seed(0)
    dim, heads, points = 32, 4, 2
    shapes = [(6, 6), (3, 3)]
    attn = MSDeformAttn(dim, n_levels=2, n_heads=heads, n_points=points)
    with torch.no_grad():  # 초기값(가중치 0)이면 질의와 무관해지므로, 대조를 위해 무작위 값으로 흔든다
        attn.sampling_offsets.weight.normal_(0, 0.5)
        attn.attention_weights.weight.normal_(0, 0.5)
    value = torch.randn(1, 6 * 6 + 3 * 3, dim)
    query = torch.randn(1, 5, dim)
    for name, reference in (("기준점 (2차원)", torch.rand(1, 5, 1, 2).expand(-1, -1, 2, -1)),
                            ("기준 박스 (4차원)", torch.cat([torch.rand(1, 5, 1, 2), torch.rand(1, 5, 1, 2) * 0.4 + 0.1],
                                                       -1).expand(-1, -1, 2, -1))):
        with torch.no_grad():
            output, locations, weights = attn(query, reference, value, shapes, return_details=True)
            projected = attn.value_proj(value)[0]  # (ΣHW, C)
            head_dim = dim // heads
            manual = torch.zeros(dim)
            q, start = 3, 0  # 질의 3번
            for level, (height, width) in enumerate(shapes):
                level_map = projected[start:start + height * width].T.reshape(dim, height, width)  # (C, H, W)
                start += height * width
                for m in range(heads):
                    sampled = bilinear_sample(level_map[m * head_dim:(m + 1) * head_dim], locations[0, q, m, level])
                    manual[m * head_dim:(m + 1) * head_dim] += (weights[0, q, m, level][:, None] * sampled).sum(0)
            manual = attn.output_proj(manual)
        print(f"check MSDeformAttn vs 손으로 다시 계산 [{name}]: 최대 차이 {float((output[0, q] - manual).abs().max()):.2e}, "
              f"가중치 합(머리마다) {weights[0, q].sum((-1, -2)).numpy().round(4)}")

    fresh = MSDeformAttn(dim, n_levels=1, n_heads=8, n_points=2)
    bias = fresh.sampling_offsets.bias.detach().view(8, 1, 2, 2)
    print("오프셋 편향의 초기값 (머리 8개 × 표본점 2개, 단위: 칸):")
    for m in range(8):
        print(f"  머리 {m}: k=1 ({bias[m, 0, 0, 0]:+.0f}, {bias[m, 0, 0, 1]:+.0f})   "
              f"k=2 ({bias[m, 0, 1, 0]:+.0f}, {bias[m, 0, 1, 1]:+.0f})")
# --8<-- [end:msda-check]


# ── 3. 계산량 비교 ───────────────────────────────────────────────────────────


# --8<-- [start:complexity]
@torch.no_grad()
def complexity_table(device, sizes=(12, 24, 48, 96, 192), num_queries=100, dim=128, heads=8, points=2, batch=2,
                     repeats=50):
    """교차 어텐션 한 번의 "읽는 자리 수" 와 걸린 시간. 특징 맵 한 변을 키워 가며 잰다 (단일 레벨, L = 1)."""
    standard = nn.MultiheadAttention(dim, heads, batch_first=True).to(device).eval()
    deform = MSDeformAttn(dim, n_levels=1, n_heads=heads, n_points=points).to(device).eval()

    def clock(fn):
        times = []
        for _ in range(repeats + 10):
            start = time.perf_counter()
            fn()
            if device == "cuda":
                torch.cuda.synchronize()
            times.append(time.perf_counter() - start)
        return float(np.min(times[10:])) * 1000  # 처음 10번은 준비 운동으로 버리고 최솟값 (ms): 다른 일에 덜 흔들린다

    rows = []
    print(f"[계산량] 질의 {num_queries}개, 머리 M = {heads}, 레벨 L = 1, 표본점 K = {points}, D = {dim}, 배치 {batch}")
    print("특징 맵 | 토큰 HW | 보통: 질의×토큰 | 변형: 질의×M·L·K |  비   | 보통 ms | 변형 ms")
    for side in sizes:
        tokens = side * side
        memory = torch.randn(batch, tokens, dim, device=device)
        query = torch.randn(batch, num_queries, dim, device=device)
        reference = torch.rand(batch, num_queries, 1, 2, device=device)
        ms_standard = clock(lambda: standard(query, memory, memory, need_weights=False))
        ms_deform = clock(lambda: deform(query, reference, memory, [(side, side)]))
        pairs_standard, pairs_deform = num_queries * tokens, num_queries * heads * points
        rows.append((side, tokens, pairs_standard, pairs_deform, ms_standard, ms_deform))
        print(f"{side:3d}×{side:<3d} | {tokens:7d} | {pairs_standard:13,d} | {pairs_deform:14,d} | "
              f"{pairs_standard / pairs_deform:5.1f} | {ms_standard:7.2f} | {ms_deform:7.2f}")
    return rows
# --8<-- [end:complexity]


# ── 4. 미니 Deformable DETR ──────────────────────────────────────────────────


# --8<-- [start:decoder-layer]
class DeformableDecoderLayer(nn.Module):
    """Deformable DETR 디코더 한 층: 질의끼리 자기 어텐션 → 변형 교차 어텐션 → FFN (각각 뒤에 더하고 층 정규화).

    7장의 디코더 층과 다른 곳은 ② 하나뿐이다: nn.MultiheadAttention 대신 MSDeformAttn.
    """

    def __init__(self, dim: int, heads: int, ffn_dim: int, n_levels: int, n_points: int, dropout: float = 0.0):
        super().__init__()
        self.self_attn = nn.MultiheadAttention(dim, heads, dropout=dropout, batch_first=True)
        self.norm1 = nn.LayerNorm(dim)
        self.cross_attn = MSDeformAttn(dim, n_levels, heads, n_points)
        self.norm2 = nn.LayerNorm(dim)
        self.ffn = nn.Sequential(nn.Linear(dim, ffn_dim), nn.ReLU(), nn.Dropout(dropout), nn.Linear(ffn_dim, dim))
        self.norm3 = nn.LayerNorm(dim)
        self.dropout = nn.Dropout(dropout)

    def forward(self, tgt, query_pos, reference_points, memory, spatial_shapes):
        """tgt (B, N, D), query_pos (B, N, D) 또는 (N, D), reference_points (B, N, L, 2 또는 4), memory (B, ΣHW, D).

        돌려주는 값: 새 tgt (B, N, D), 표본점 (B, N, M, L, K, 2), 어텐션 가중치 (B, N, M, L, K).
        """
        q = tgt + query_pos
        attended, _ = self.self_attn(q, q, tgt, need_weights=False)  # ① 자기 어텐션 (7장과 같다)
        tgt = self.norm1(tgt + self.dropout(attended))
        attended, locations, weights = self.cross_attn(tgt + query_pos, reference_points, memory, spatial_shapes,
                                                       return_details=True)  # ② 기준점 주위 M·L·K 곳만 읽는다
        tgt = self.norm2(tgt + self.dropout(attended))
        tgt = self.norm3(tgt + self.dropout(self.ffn(tgt)))  # ③ FFN
        return tgt, locations, weights
# --8<-- [end:decoder-layer]


# --8<-- [start:proposals]
def gen_proposals(spatial_shapes, base_scale: float = 0.05, device=None) -> torch.Tensor:
    """2단계의 1단계: 특징 맵의 칸마다 "제안 박스" 하나를 놓는다. 돌려주는 값: (ΣHW, 4) 정규화 (cx, cy, w, h).

    중심은 칸의 중심 ((c + 0.5)/W, (r + 0.5)/H), 너비 · 높이는 레벨 l 에서 base_scale · 2^l 로 고정
    (RF-DETR 공식 구현의 gen_encoder_output_proposals 와 같다. 해상도가 낮은 레벨일수록 큰 박스를 맡는다).
    토큰 순서(레벨 0 의 행 우선, 이어서 레벨 1 …)는 memory 와 같다. 모델은 이 박스에 델타를 더해 고친다.
    """
    proposals = []
    for level, (height, width) in enumerate(spatial_shapes):
        ys = (torch.arange(height, dtype=torch.float32, device=device) + 0.5) / height
        xs = (torch.arange(width, dtype=torch.float32, device=device) + 0.5) / width
        grid_y, grid_x = torch.meshgrid(ys, xs, indexing="ij")
        size = torch.full_like(grid_x, base_scale * 2.0**level)
        proposals.append(torch.stack([grid_x, grid_y, size, size], dim=-1).reshape(-1, 4))
    return torch.cat(proposals)
# --8<-- [end:proposals]


# --8<-- [start:model]
class MiniDeformableDETR(nn.Module):
    """미니 Deformable DETR. 그림 (B, 3, 96, 96) → 질의 N 개마다 (클래스 로짓 K 개, 박스 4개). ∅ 칸이 없다.

    특징: 7장의 백본(12×12) → 레벨 0 = 1×1 합성곱(12×12), 레벨 1 = 3×3 스트라이드 2 합성곱(6×6). 각각 GroupNorm.
    인코더: 기본은 없음(enc_layers=0) — 백본 특징을 그대로 디코더에 준다. enc_layers > 0 이면 7장의 전역 자기
           어텐션 인코더 층을 그만큼 쌓는다 (LW-DETR · RF-DETR 에서 ViT 가 하는 역할).
    디코더: DeformableDecoderLayer × dec_layers.
    box_refine=True  : 층마다 박스 머리가 따로 있고, 층 d 의 박스 = σ(Δ_d + σ⁻¹(기준_{d−1})). 그 박스를 기울기를
                       끊어(detach) 다음 층의 기준 박스로 넘긴다 → 박스 반복 정제.
    box_refine=False : 모든 층이 처음 기준을 그대로 쓰고, 머리도 함께 쓴다.
    two_stage=False  : 기준점 = σ(Linear(학습되는 질의 위치 임베딩)) — 그림과 무관한 N 개의 점 (2차원).
    two_stage=True   : 모든 칸에서 제안 박스와 클래스 점수를 내고, 점수 상위 N 개의 박스를 기준 박스(4차원)로 쓴다.
    """

    def __init__(self, num_classes: int = NUM_CLASSES, num_queries: int = 12, dim: int = 128, heads: int = 8,
                 dec_layers: int = 3, ffn_dim: int = 256, n_levels: int = 2, n_points: int = 2,
                 box_refine: bool = True, two_stage: bool = False, enc_layers: int = 0, backbone_width: int = 32):
        super().__init__()
        assert n_levels in (1, 2)
        self.num_classes, self.num_queries, self.dim, self.n_levels = num_classes, num_queries, dim, n_levels
        self.box_refine, self.two_stage = box_refine, two_stage
        self.backbone = SmallBackbone(backbone_width)
        channels = self.backbone.out_channels
        self.input_proj = nn.ModuleList([nn.Sequential(nn.Conv2d(channels, dim, 1), nn.GroupNorm(32, dim))])
        if n_levels == 2:  # 더 거친 레벨은 백본 출력에 스트라이드 2 합성곱을 한 번 더 해서 만든다
            self.input_proj.append(nn.Sequential(nn.Conv2d(channels, dim, 3, 2, 1), nn.GroupNorm(32, dim)))
        self.encoder = nn.ModuleList(TransformerEncoderLayer(dim, heads, ffn_dim) for _ in range(enc_layers))
        self.level_embed = nn.Parameter(torch.randn(n_levels, dim) * 0.02) if enc_layers else None
        self.decoder = nn.ModuleList(DeformableDecoderLayer(dim, heads, ffn_dim, n_levels, n_points)
                                     for _ in range(dec_layers))

        self.query_feat = nn.Embedding(num_queries, dim)  # 질의의 내용: 디코더의 첫 입력 (학습됨)
        if two_stage:
            self.enc_output = nn.Sequential(nn.Linear(dim, dim), nn.LayerNorm(dim))
            self.enc_class_embed = nn.Linear(dim, num_classes)  # 칸마다의 클래스 로짓
            self.enc_bbox_embed = MLP(dim, dim, 4, num_layers=3)  # 칸마다의 박스 델타
            self.ref_point_head = MLP(2 * dim, dim, dim, num_layers=2)  # 기준 박스의 사인 임베딩 → 질의 위치 임베딩
        else:
            self.query_pos = nn.Embedding(num_queries, dim)  # 질의 위치 임베딩 (학습됨)
            self.reference_points = nn.Linear(dim, 2)  # → 시그모이드 → 기준점
            nn.init.xavier_uniform_(self.reference_points.weight)
            nn.init.constant_(self.reference_points.bias, 0.0)

        # 머리. box_refine 이면 층마다 따로, 아니면 하나를 함께 쓴다 (같은 모듈을 여러 번 넣으면 가중치를 함께 쓴다)
        num_heads = dec_layers if box_refine else 1
        class_heads = [nn.Linear(dim, num_classes) for _ in range(num_heads)]
        bbox_heads = [MLP(dim, dim, 4, num_layers=3) for _ in range(num_heads)]
        self.class_embed = nn.ModuleList(class_heads[i % num_heads] for i in range(dec_layers))
        self.bbox_embed = nn.ModuleList(bbox_heads[i % num_heads] for i in range(dec_layers))
        prior_bias = -math.log((1 - 0.01) / 0.01)  # σ(편향) = 0.01: 처음에는 모든 칸이 "객체일 확률 1%" 라고 답한다
        for head in class_heads + ([self.enc_class_embed] if two_stage else []):
            nn.init.constant_(head.bias, prior_bias)
        for head in bbox_heads + ([self.enc_bbox_embed] if two_stage else []):
            nn.init.constant_(head.layers[-1].weight, 0.0)  # 처음의 Δ 는 0 → 박스 = 기준 그대로
            nn.init.constant_(head.layers[-1].bias, 0.0)
        if not two_stage:  # 기준이 점이면 w, h 는 머리가 통째로 예측한다: σ(−2) ≈ 0.12 에서 출발
            nn.init.constant_(bbox_heads[0].layers[-1].bias[2:], -2.0)

    def encode(self, images: torch.Tensor):
        """그림 → memory (B, ΣHW, D) 와 spatial_shapes [(12, 12), (6, 6)]."""
        feature = self.backbone(images)
        maps = [proj(feature) for proj in self.input_proj]  # [(B, D, 12, 12), (B, D, 6, 6)]
        spatial_shapes = [tuple(m.shape[-2:]) for m in maps]
        memory = torch.cat([m.flatten(2).transpose(1, 2) for m in maps], dim=1)  # (B, ΣHW, D)
        if len(self.encoder):
            pos = torch.cat([sine_position_2d(h, w, self.dim, device=images.device) + self.level_embed[level]
                             for level, (h, w) in enumerate(spatial_shapes)])  # (ΣHW, D)
            for layer in self.encoder:
                memory = layer(memory, pos)
        return memory, spatial_shapes

    def select_queries(self, memory, spatial_shapes):
        """2단계 질의 선택. 돌려주는 값: 기준 박스 (B, N, 4) — 기울기 차단, 그리고 손실에 넣을 제안 예측."""
        proposals = gen_proposals(spatial_shapes, device=memory.device)  # (ΣHW, 4)
        feature = self.enc_output(memory)  # (B, ΣHW, D)
        logits = self.enc_class_embed(feature)  # (B, ΣHW, K)
        boxes = (self.enc_bbox_embed(feature) + inverse_sigmoid(proposals)).sigmoid()  # 제안 + 델타 (로짓 공간에서)
        top = logits.max(-1).values.topk(self.num_queries, dim=1).indices  # (B, N): 클래스 로짓의 최댓값 상위 N 칸
        top_logits = torch.gather(logits, 1, top[..., None].expand(-1, -1, logits.shape[-1]))
        top_boxes = torch.gather(boxes, 1, top[..., None].expand(-1, -1, 4))
        return top_boxes.detach(), {"pred_logits": top_logits, "pred_boxes": top_boxes}, top

    def forward(self, images: torch.Tensor, return_details: bool = False):
        """돌려주는 값: {"pred_logits": (B, N, K), "pred_boxes": (B, N, 4), "aux_outputs": [...],
                       "enc_outputs": {…} (two_stage 일 때만 — 선택된 제안 N 개의 로짓 · 박스)}
        return_details=True 면 "references": [층마다 그 층이 쓴 기준 (B, N, 2 또는 4)],
        "sampling": [층마다 (표본점 (B, N, M, L, K, 2), 가중치 (B, N, M, L, K))] 도 넣는다.
        """
        memory, spatial_shapes = self.encode(images)
        batch = images.shape[0]
        outputs = {}
        if self.two_stage:
            reference, outputs["enc_outputs"], _ = self.select_queries(memory, spatial_shapes)  # (B, N, 4)
            query_pos = self.ref_point_head(sine_embed(reference, self.dim // 2))  # (B, N, 4·D/2) → (B, N, D)
        else:
            query_pos = self.query_pos.weight  # (N, D)
            reference = self.reference_points(query_pos).sigmoid()[None].expand(batch, -1, -1)  # (B, N, 2)
        tgt = self.query_feat.weight[None].expand(batch, -1, -1)  # (B, N, D)

        layer_outputs, references, sampling = [], [], []
        for i, layer in enumerate(self.decoder):
            references.append(reference)
            reference_input = reference[:, :, None].expand(-1, -1, self.n_levels, -1)  # 모든 레벨에 같은 기준
            tgt, locations, weights = layer(tgt, query_pos, reference_input, memory, spatial_shapes)
            sampling.append((locations, weights))
            delta = self.bbox_embed[i](tgt)  # (B, N, 4)
            if reference.shape[-1] == 4:
                box = (delta + inverse_sigmoid(reference)).sigmoid()  # 기준 박스를 조금 고친다
            else:  # 기준이 점이면 중심만 기준점에서 출발하고, 너비 · 높이는 머리가 직접 낸다
                box = torch.cat([delta[..., :2] + inverse_sigmoid(reference), delta[..., 2:]], -1).sigmoid()
            layer_outputs.append({"pred_logits": self.class_embed[i](tgt), "pred_boxes": box})
            if self.box_refine:
                reference = box.detach()  # 다음 층의 기준 박스. 기울기는 Δ 로만 흐르게 여기서 끊는다
        outputs.update(layer_outputs[-1])
        outputs["aux_outputs"] = layer_outputs[:-1]
        if return_details:
            outputs["references"], outputs["sampling"] = references, sampling
        return outputs
# --8<-- [end:model]


# --8<-- [start:focal]
def sigmoid_focal_loss(logits: torch.Tensor, targets: torch.Tensor, alpha: float = 0.25, gamma: float = 2.0):
    """포컬 손실 (4장). logits · targets 는 같은 모양이고 targets 는 0 또는 1. 칸마다의 손실을 돌려준다.

    FL = −α_t (1 − p_t)^γ log p_t,   p_t = p (목표 1) 또는 1 − p (목표 0),   α_t = α 또는 1 − α.
    """
    prob = logits.sigmoid()
    ce = F.binary_cross_entropy_with_logits(logits, targets, reduction="none")  # −log p_t
    p_t = prob * targets + (1 - prob) * (1 - targets)
    alpha_t = alpha * targets + (1 - alpha) * (1 - targets)
    return alpha_t * (1 - p_t) ** gamma * ce


class FocalSetCriterion(SetCriterion):
    """Deformable DETR 의 집합 손실. 7장의 SetCriterion 에서 분류 손실만 바꾼다.

    클래스마다 따로 시그모이드: 목표는 (B, N, K) 의 0/1 행렬이고, 짝이 있는 질의의 정답 클래스 칸만 1 이다.
    ∅ 클래스가 없다 — 짝이 없는 질의는 "모든 칸이 0" 이 목표다. 합을 객체 수로 나눈다. 계수는 (2, 5, 2).
    """

    def __init__(self, num_classes: int, matcher: HungarianMatcher, focal_alpha: float = 0.25,
                 focal_gamma: float = 2.0, loss_ce: float = 2.0, loss_bbox: float = 5.0, loss_giou: float = 2.0):
        super().__init__(num_classes, matcher, loss_ce=loss_ce, loss_bbox=loss_bbox, loss_giou=loss_giou)
        self.focal_alpha, self.focal_gamma = focal_alpha, focal_gamma

    def loss_labels(self, outputs, tgt_labels, matched, num_boxes):
        logits = outputs["pred_logits"]  # (B, N, K)
        batch_idx, query_idx, tgt_idx = matched
        target = torch.zeros_like(logits)
        target[batch_idx, query_idx, tgt_labels[tgt_idx]] = 1.0
        return sigmoid_focal_loss(logits, target, self.focal_alpha, self.focal_gamma).sum() / num_boxes
# --8<-- [end:focal]


# --8<-- [start:postprocess]
@torch.no_grad()
def postprocess_sigmoid(outputs, num_select: int | None = None):
    """Deformable DETR 방식 후처리. outputs: {"pred_logits": (B, N, K), "pred_boxes": (B, N, 4)}.

    (질의, 클래스) N·K 쌍의 시그모이드 확률을 한 줄로 펴서 점수 상위 num_select 개를 예측으로 낸다
    (기본값 N). 한 질의가 두 클래스로 두 번 뽑힐 수도 있다. NMS 는 없다.
    돌려주는 값: 길이 B 의 목록, 각각 {"boxes": (num_select, 4), "scores": (num_select,), "labels": (num_select,)}.
    """
    prob = outputs["pred_logits"].sigmoid()  # (B, N, K)
    batch, num_queries, num_classes = prob.shape
    scores, index = prob.flatten(1).topk(num_select or num_queries, dim=1)  # (B, num_select)
    query, labels = index // num_classes, index % num_classes
    boxes = torch.gather(outputs["pred_boxes"], 1, query[..., None].expand(-1, -1, 4))
    return [{"boxes": b, "scores": s, "labels": c} for b, s, c in zip(boxes, scores, labels)]
# --8<-- [end:postprocess]


# --8<-- [start:build]
def build_optimizer(model, lr: float, weight_decay: float = 1e-4):
    """AdamW. Deformable DETR 처럼 오프셋 · 기준점을 내는 Linear 는 학습률을 1/10 로 한다 (표본점이 날뛰지 않게)."""
    slow = [p for n, p in model.named_parameters() if "sampling_offsets" in n or "reference_points" in n]
    slow_ids = {id(p) for p in slow}
    fast = [p for p in model.parameters() if id(p) not in slow_ids]
    return torch.optim.AdamW([{"params": fast}, {"params": slow, "lr": lr * 0.1}], lr=lr, weight_decay=weight_decay)


def build_criterion(device):
    """매칭 비용도 포컬 방식으로: C = 2·C_cls(포컬) + 5·C_L1 + 2·C_GIoU."""
    matcher = HungarianMatcher(cost_class=2.0, cost_bbox=5.0, cost_giou=2.0, class_cost="focal")
    return FocalSetCriterion(NUM_CLASSES, matcher).to(device)
# --8<-- [end:build]


def focal_checks():
    logits = torch.tensor([2.0, -1.0, 0.5, -3.0])
    targets = torch.tensor([1.0, 0.0, 0.0, 1.0])
    plain = sigmoid_focal_loss(logits, targets, alpha=0.5, gamma=0.0) * 2  # α = 1/2, γ = 0 이면 BCE 의 절반
    bce = F.binary_cross_entropy_with_logits(logits, targets, reduction="none")
    print(f"check 포컬 손실(γ = 0, α = 0.5) × 2 vs BCE: 최대 차이 {float((plain - bce).abs().max()):.2e}")
    prob = logits.sigmoid()
    manual = torch.where(targets == 1, -0.25 * (1 - prob) ** 2 * prob.log(), -0.75 * prob**2 * (1 - prob).log())
    print(f"check 포컬 손실(γ = 2, α = 0.25) vs 식 그대로: 최대 차이 "
          f"{float((sigmoid_focal_loss(logits, targets) - manual).abs().max()):.2e}")
    proposals = gen_proposals([(12, 12), (6, 6)])
    print(f"gen_proposals([(12, 12), (6, 6)]): {tuple(proposals.shape)}, 첫 칸 {proposals[0].numpy().round(4)}, "
          f"레벨 1 의 첫 칸 {proposals[144].numpy().round(4)}")


# ── 5. 그림 ──────────────────────────────────────────────────────────────────

LEVEL_COLORS = ("#ffd92f", "#00e5ff")  # 레벨 0 (12×12), 레벨 1 (6×6)


def plot_complexity(rows, path):
    import matplotlib.pyplot as plt

    tokens = [r[1] for r in rows]
    fig, axes = plt.subplots(1, 2, figsize=(10, 3.6))
    ax = axes[0]
    ax.plot(tokens, [r[2] for r in rows], "o-", color="#D55E00", label="standard: Nq x HW")
    ax.plot(tokens, [r[3] for r in rows], "s--", color="#0072B2", label="deformable: Nq x M x L x K")
    ax.set_ylabel("(query, location) pairs read")
    ax.set_title("locations read by one cross-attention", fontsize=10)
    ax = axes[1]
    ax.plot(tokens, [r[4] for r in rows], "o-", color="#D55E00", label="standard (nn.MultiheadAttention)")
    ax.plot(tokens, [r[5] for r in rows], "s--", color="#0072B2", label="deformable (MSDeformAttn)")
    ax.set_ylabel("time per forward pass [ms]")
    ax.set_title("measured time", fontsize=10)
    for ax in axes:
        ax.set_xscale("log")
        ax.set_yscale("log")
        ax.set_xticks(tokens)
        ax.set_xticklabels([f"{r[0]}x{r[0]}\n{r[1]}" for r in rows], fontsize=8)
        ax.minorticks_off()
        ax.set_xlabel("feature map size (H x W, tokens)")
        ax.grid(alpha=0.3)
        ax.legend(fontsize=8)
    fig.tight_layout()
    fig.savefig(path, dpi=120, facecolor="white")
    plt.close(fig)


def plot_offset_init(path, heads=8, points=2):
    """초기화 직후의 표본점 무늬: 기준이 점일 때(칸 단위)와 박스일 때(박스 크기에 비례)."""
    import matplotlib.pyplot as plt

    attn = MSDeformAttn(128, n_levels=1, n_heads=heads, n_points=points)
    query = torch.zeros(1, 1, 128)
    value = torch.zeros(1, 144, 128)
    fig, axes = plt.subplots(1, 2, figsize=(8.4, 4.3))
    markers = ("o", "s", "^", "D")
    with torch.no_grad():
        for ax, reference, title in (
                (axes[0], torch.tensor([[[[0.5, 0.5]]]]), "point reference: offsets in feature-map cells"),
                (axes[1], torch.tensor([[[[0.5, 0.5, 0.5, 0.3]]]]), "box reference: offsets scale with the box")):
            _, locations, _ = attn(query, reference, value, [(12, 12)], return_details=True)
            locations = locations[0, 0, :, 0]  # (M, K, 2)
            for edge in np.arange(13) / 12:  # 12×12 특징 맵의 칸 경계
                ax.axhline(edge, color="#cccccc", lw=0.5)
                ax.axvline(edge, color="#cccccc", lw=0.5)
            if reference.shape[-1] == 4:
                cx, cy, w, h = reference.flatten().tolist()
                ax.add_patch(plt.Rectangle((cx - w / 2, cy - h / 2), w, h, fill=False, edgecolor="#D55E00", lw=2,
                                           label="reference box"))
            for k in range(points):
                ax.scatter(locations[:, k, 0], locations[:, k, 1], s=45, marker=markers[k], color="#0072B2",
                           alpha=0.6 + 0.4 * k / max(points - 1, 1), label=f"sampling point k = {k + 1}", zorder=3)
            ax.scatter([0.5], [0.5], s=90, marker="*", color="#D55E00", label="reference point", zorder=4)
            ax.set_xlim(0.15, 0.85)
            ax.set_ylim(0.85, 0.15)
            ax.set_aspect("equal")
            ax.set_xlabel("x (normalized)")
            ax.set_ylabel("y (normalized)")
            ax.set_title(title, fontsize=9)
            ax.legend(fontsize=7, loc="upper right")
    fig.suptitle(f"sampling points at initialization ({heads} heads x {points} points, 12x12 feature map)", fontsize=10)
    fig.tight_layout()
    fig.savefig(path, dpi=120, facecolor="white")
    plt.close(fig)


def plot_convergence(histories, path, title, styles=None):
    """여러 실행의 검증 AP 곡선을 겹쳐 그린다. histories: 이름 → 기록 사전 (ap_epoch · AP · AP75)."""
    import matplotlib.pyplot as plt

    palette = ["#D55E00", "#0072B2", "#009E73", "#CC79A7", "#E69F00", "#56B4E9"]
    lines = ["-", "--", "-.", ":", (0, (5, 1)), (0, (3, 1, 1, 1))]
    markers = ["o", "s", "^", "D", "v", "P"]
    fig, axes = plt.subplots(1, 2, figsize=(11, 3.9))
    for ax, key in zip(axes, ("AP", "AP75")):
        for i, (name, history) in enumerate(histories.items()):
            ax.plot(history["ap_epoch"], history[key], linestyle=lines[i % 6], marker=markers[i % 6], markersize=3,
                    color=palette[i % 6], label=name)
        ax.set_xlabel("epoch")
        ax.set_ylabel(f"validation {key}")
        ax.set_ylim(0, 1)
        ax.grid(alpha=0.3)
        ax.legend(fontsize=8, loc="lower right")
    fig.suptitle(title, fontsize=10)
    fig.tight_layout()
    fig.savefig(path, dpi=120, facecolor="white")
    plt.close(fig)


@torch.no_grad()
def plot_sampling_points(model, dataset, index, path, device):
    """그림 한 장에서 점수가 가장 높은 질의 하나를 골라, 디코더 층마다 기준(점 · 박스)과 표본점을 그린다.

    표본점의 색은 레벨, 크기는 어텐션 가중치에 비례한다.
    """
    import matplotlib.pyplot as plt

    model.eval()
    image, target = dataset[index]
    size = image.shape[-1]
    outputs = model(image[None].to(device), return_details=True)
    scores = outputs["pred_logits"][0].sigmoid().max(-1).values  # (N,)
    query = int(scores.argmax())
    num_layers = len(outputs["sampling"])
    fig, axes = plt.subplots(1, num_layers, figsize=(num_layers * 3.6, 4.0))
    report = []
    for layer, ax in enumerate(axes):
        draw_boxes(ax, image)
        locations, weights = (t[0, query].cpu() for t in outputs["sampling"][layer])  # (M, L, K, 2), (M, L, K)
        reference = outputs["references"][layer][0, query].cpu()
        if len(reference) == 4:
            cx, cy, w, h = reference.tolist()
            ax.add_patch(plt.Rectangle(((cx - w / 2) * size - 0.5, (cy - h / 2) * size - 0.5), w * size, h * size,
                                       fill=False, edgecolor="white", linestyle="--", linewidth=1.3))
        ax.scatter([reference[0] * size - 0.5], [reference[1] * size - 0.5], marker="*", s=130, color="white",
                   edgecolors="black", linewidths=0.6, zorder=4)
        for level in range(locations.shape[1]):
            points = locations[:, level].reshape(-1, 2) * size - 0.5
            ax.scatter(points[:, 0], points[:, 1], s=weights[:, level].reshape(-1) * 600 + 4,
                       color=LEVEL_COLORS[level], edgecolors="black", linewidths=0.4, alpha=0.9, zorder=3)
        ax.set_xlim(-0.5, size - 0.5)
        ax.set_ylim(size - 0.5, -0.5)
        kind = "point" if len(reference) == 2 else "box"
        ax.set_title(f"decoder layer {layer + 1} (reference = {kind})", fontsize=9)
        spread = (locations - reference[:2]).abs().amax()
        inside = ((locations >= 0) & (locations <= 1)).all(-1).float().mean()
        report.append((kind, float(spread), float(inside), float(weights.max()), weights.sum((0, 2)) / weights.shape[0]))
    handles = [plt.Line2D([], [], ls="", marker="*", markersize=11, color="white", markeredgecolor="black",
                          label="reference point"),
               plt.Line2D([], [], ls="--", color="gray", label="reference box"),
               plt.Line2D([], [], ls="", marker="o", color=LEVEL_COLORS[0], markeredgecolor="black",
                          label="sampling point, level 0 (12x12)")]
    if locations.shape[1] > 1:
        handles.append(plt.Line2D([], [], ls="", marker="o", color=LEVEL_COLORS[1], markeredgecolor="black",
                                  label="sampling point, level 1 (6x6)"))
    fig.legend(handles=handles, loc="lower center", ncol=4, fontsize=8, frameon=False)
    label = CLASS_NAMES[int(outputs["pred_logits"][0, query].argmax())]
    fig.suptitle(f"val #{index}, query {query} ({label}, score {float(scores[query]):.2f}): "
                 "where the deformable cross-attention samples (marker area = attention weight)", fontsize=9)
    fig.tight_layout(rect=(0, 0.06, 1, 1))
    fig.savefig(path, dpi=120, facecolor="white")
    plt.close(fig)
    return query, report


@torch.no_grad()
def plot_refinement(model, dataset, indices, path, device, score_threshold=0.5):
    """디코더 층마다의 박스. 열 0 은 처음 기준(점 또는 제안 박스), 열 1 … 은 각 층이 낸 박스."""
    import matplotlib.pyplot as plt

    model.eval()
    num_layers = len(model.decoder)
    fig, axes = plt.subplots(len(indices), num_layers + 1, figsize=((num_layers + 1) * 2.5, len(indices) * 2.6),
                             squeeze=False)
    for row, index in enumerate(indices):
        image, target = dataset[index]
        size = image.shape[-1]
        outputs = model(image[None].to(device), return_details=True)
        keep = (outputs["pred_logits"][0].sigmoid().max(-1).values >= score_threshold).cpu()  # 마지막 층 기준
        layers = [o["pred_boxes"][0].cpu() for o in outputs["aux_outputs"]] + [outputs["pred_boxes"][0].cpu()]
        initial = outputs["references"][0][0].cpu()
        ax = axes[row, 0]
        draw_boxes(ax, image, target["boxes"], color="white", linestyle="--", linewidth=1.0)
        if initial.shape[-1] == 4:
            draw_boxes(ax, image, initial[keep], color="#ff9d00", linewidth=1.3)
        ax.scatter(initial[~keep, 0] * size - 0.5, initial[~keep, 1] * size - 0.5, s=14, color="#bbbbbb",
                   edgecolors="black", linewidths=0.3, zorder=3)
        ax.scatter(initial[keep, 0] * size - 0.5, initial[keep, 1] * size - 0.5, s=90, marker="*", color="#ff9d00",
                   edgecolors="black", linewidths=0.4, zorder=4)
        ax.set_xlim(-0.5, size - 0.5)
        ax.set_ylim(size - 0.5, -0.5)
        ax.set_title(f"val #{index}: initial reference", fontsize=8)
        for layer, boxes in enumerate(layers):
            ax = axes[row, layer + 1]
            draw_boxes(ax, image, target["boxes"], color="white", linestyle="--", linewidth=1.0)
            draw_boxes(ax, image, boxes[keep], color="#39ff14", linewidth=1.4)
            ax.set_title(f"after decoder layer {layer + 1}", fontsize=8)
    fig.suptitle("boxes of the queries that end with score >= 0.5 (green), ground truth (white dashed);\n"
                 "left: initial references of all queries (orange star = those queries)", fontsize=9)
    fig.tight_layout()
    fig.savefig(path, dpi=120, facecolor="white")
    plt.close(fig)


def matched_iou_per_layer(layers, dataset, matcher):
    """층마다, 헝가리안 매칭으로 정답과 짝지어진 예측 박스의 평균 IoU (박스가 층을 거치며 얼마나 맞아 가는가)."""
    values = []
    for layer in layers:
        indices = matcher(layer, dataset.targets)
        ious = [paired_box_iou(box_cxcywh_to_xyxy(layer["pred_boxes"][b][rows]),
                               box_cxcywh_to_xyxy(dataset.targets[b]["boxes"][cols]))
                for b, (rows, cols) in enumerate(indices)]
        values.append(float(torch.cat(ious).mean()))
    return values


# ── 6. 본 실행 ───────────────────────────────────────────────────────────────


# --8<-- [start:run]
def run_experiment(name, train_set, val_set, epochs, lr, batch_size, device, seed, **model_kwargs):
    """모델 하나를 처음부터 학습한다. 시드 · 데이터 순서는 실행마다 같다. 돌려주는 값: (모델, 학습 기록)."""
    torch.manual_seed(seed)
    model = MiniDeformableDETR(**model_kwargs).to(device)
    criterion = build_criterion(device)
    optimizer = build_optimizer(model, lr)
    scheduler = torch.optim.lr_scheduler.StepLR(optimizer, step_size=max(int(epochs * 0.8), 1), gamma=0.1)
    loader = make_loader(train_set, batch_size, shuffle=True, seed=seed)
    print(f"\n── {name}: 매개변수 {sum(p.numel() for p in model.parameters()):,}개, {model_kwargs}")
    history = fit(model, criterion, optimizer, scheduler, loader, val_set, epochs, device,
                  postprocess_fn=postprocess_sigmoid)
    return model, history
# --8<-- [end:run]


def first_epoch_reaching(history, level):
    reached = [e for e, ap in zip(history["ap_epoch"], history["AP"]) if ap >= level]
    return reached[0] if reached else None


# --8<-- [start:main]
def main():
    parser = argparse.ArgumentParser(description="8장: 변형 어텐션과 미니 Deformable DETR")
    parser.add_argument("--quick", action="store_true", help="아주 작게 돌려 오류만 확인")
    parser.add_argument("--epochs", type=int, default=60, help="본 모델의 에폭 수 (7장과 같게)")
    parser.add_argument("--ablation-epochs", type=int, default=15, help="절제 실험 한 번의 에폭 수")
    parser.add_argument("--train-size", type=int, default=4000)
    parser.add_argument("--val-size", type=int, default=500)
    parser.add_argument("--batch-size", type=int, default=32)
    parser.add_argument("--lr", type=float, default=2e-4)
    parser.add_argument("--num-queries", type=int, default=12)
    parser.add_argument("--seed", type=int, default=0)
    parser.add_argument("--fig-dir", default="figures")
    args = parser.parse_args()
    if args.quick:
        args.epochs, args.ablation_epochs, args.train_size, args.val_size = 2, 1, 192, 48

    import matplotlib

    matplotlib.use("Agg")
    os.makedirs(args.fig_dir, exist_ok=True)
    torch.manual_seed(args.seed)
    np.random.seed(args.seed)
    device = get_device()
    if device == "cpu":
        torch.set_num_threads(min(4, os.cpu_count() or 1))
    print(f"장치: {device}")
    start = time.time()

    # 1. 직접 만든 연산의 check
    bilinear_checks()
    print()
    msda_checks()
    focal_checks()
    plot_offset_init(os.path.join(args.fig_dir, "ch08-offset-init.png"))

    # 2. 계산량
    print()
    rows = complexity_table(device, sizes=(12, 24) if args.quick else (12, 24, 48, 96, 192),
                            repeats=3 if args.quick else 50)
    plot_complexity(rows, os.path.join(args.fig_dir, "ch08-complexity.png"))

    # 3. 본 모델: 박스 반복 정제 + 2레벨, 1단계(학습되는 기준점). 7장과 같은 데이터 · 에폭 · 학습률 · 배치
    train_set = ShapesDataset(args.train_size, seed=0)
    val_set = ShapesDataset(args.val_size, seed=1)
    common = dict(train_set=train_set, val_set=val_set, lr=args.lr, batch_size=args.batch_size, device=device,
                  seed=args.seed, num_queries=args.num_queries)
    print(f"\n학습 {len(train_set)}장 · 검증 {len(val_set)}장, 배치 {args.batch_size}, 학습률 {args.lr} "
          "(오프셋 · 기준점 Linear 는 1/10), 에폭의 80% 뒤 학습률 1/10")
    model, history = run_experiment("Deformable DETR (본 모델)", epochs=args.epochs, **common)
    torch.save({"model": model.state_dict(),
                "config": {"num_queries": args.num_queries, "box_refine": True, "two_stage": False, "n_levels": 2}},
               "ch08_deformable.pt")
    with open("ch08_history.json", "w") as f:
        json.dump(history, f)
    print("ch08_deformable.pt · ch08_history.json 저장")

    # 3-1 7장 MiniDETR 과 수렴 비교 (7장의 기록이 실행 폴더에 있을 때)
    histories = {"MiniDeformableDETR (ch08)": history}
    if os.path.exists("ch07_history.json") and not args.quick:
        with open("ch07_history.json") as f:
            detr_history = json.load(f)
        histories = {"MiniDETR (ch07)": detr_history, **histories}
        print("\n[수렴 비교] 같은 에폭에서의 검증 AP (7장 기록 ch07_history.json)")
        print("에폭 | MiniDETR AP  AP75 | Deformable AP  AP75")
        detr_at = {e: i for i, e in enumerate(detr_history["ap_epoch"])}
        for i, epoch in enumerate(history["ap_epoch"]):
            if epoch in detr_at and (epoch <= 10 or epoch % 10 == 0):
                j = detr_at[epoch]
                print(f"{epoch:4d} |   {detr_history['AP'][j]:.4f}  {detr_history['AP75'][j]:.4f} |"
                      f"     {history['AP'][i]:.4f}  {history['AP75'][i]:.4f}")
        for level in (0.5, 0.8, 0.9):
            print(f"검증 AP {level} 에 처음 닿은 에폭(채점한 에폭 가운데): MiniDETR "
                  f"{first_epoch_reaching(detr_history, level)}, Deformable {first_epoch_reaching(history, level)}")
        print(f"학습 시간: MiniDETR {detr_history['time'][-1]:.0f}초 / {len(detr_history['epoch'])} 에폭, "
              f"Deformable {history['time'][-1]:.0f}초 / {len(history['epoch'])} 에폭")
    else:
        print("\nch07_history.json 이 없거나 --quick 이라 7장과의 비교는 건너뛴다")
    plot_convergence(histories, os.path.join(args.fig_dir, "ch08-convergence.png"),
                     "convergence on Shape World: same data, epochs, batch size and learning rate")

    # 4. 본 모델 분석
    layers = collect_outputs(model, val_set, device)
    predictions = postprocess_sigmoid(layers[-1])
    final = evaluate_ap(predictions, val_set.targets, NUM_CLASSES)
    print(f"\n[최종] 검증 AP {final['AP']:.4f}, AP50 {final['AP50']:.4f}, AP75 {final['AP75']:.4f}, 클래스별 AP "
          + ", ".join(f"{n} {v:.4f}" for n, v in zip(CLASS_NAMES, final["per_class"])))
    print("\n[디코더 층별 예측과 중복]")
    layer_rows = layer_report(layers, val_set, postprocess_fn=postprocess_sigmoid)
    plot_layers(layer_rows, os.path.join(args.fig_dir, "ch08-layers.png"), title="MiniDeformableDETR")
    matcher = HungarianMatcher(2.0, 5.0, 2.0, class_cost="focal")
    ious = matched_iou_per_layer(layers, val_set, matcher)
    print("[박스 반복 정제] 층마다 매칭된 예측 박스와 정답의 평균 IoU: "
          + ", ".join(f"{i + 1}층 {v:.4f}" for i, v in enumerate(ious)))
    plot_predictions(val_set, predictions, os.path.join(args.fig_dir, "ch08-predictions.png"), list(range(8)))
    index = next((i for i, t in enumerate(val_set.targets) if len(t["labels"]) >= 3), 0)
    plot_refinement(model, val_set, [index, index + 1], os.path.join(args.fig_dir, "ch08-refinement.png"), device)
    query, report = plot_sampling_points(model, val_set, index, os.path.join(args.fig_dir, "ch08-sampling.png"), device)
    print(f"\n[표본점] 검증 그림 #{index}, 질의 {query}: 층마다 표본점 {model.decoder[0].cross_attn.n_heads}×"
          f"{model.n_levels}×{model.decoder[0].cross_attn.n_points}개")
    for i, (kind, spread, inside, largest, level_share) in enumerate(report):
        print(f"  {i + 1}층 (기준 = {'점' if kind == 'point' else '박스'}): 기준에서 가장 먼 표본점까지 {spread:.3f} "
              f"(그림 한 변 = 1), 그림 안에 있는 표본점 비율 {inside:.2f}, 가장 큰 가중치 {largest:.3f} "
              f"(고르면 {1 / (model.n_levels * model.decoder[0].cross_attn.n_points):.3f}), "
              f"레벨별 가중치 몫 {level_share.numpy().round(3)}")
    init_ref = model.reference_points(model.query_pos.weight).sigmoid().detach().cpu().numpy()
    print("학습된 기준점 (질의 12개의 x, y):", " ".join(f"({x:.2f},{y:.2f})" for x, y in init_ref))

    # 5. 절제 실험: 각각 시드 1개로 한 번씩, 짧은 일정(ablation-epochs)으로 처음부터 학습
    print(f"\n[절제] 에폭 {args.ablation_epochs} 의 짧은 일정, 각 설정 시드 1개 (차이가 작으면 우연일 수 있다)")
    variants = [
        ("refine, 2 levels (base)", dict()),
        ("no box refinement", dict(box_refine=False)),
        ("two-stage", dict(two_stage=True)),
        ("single level (12x12)", dict(n_levels=1)),
        ("+ 3 encoder layers", dict(enc_layers=3)),
    ]
    ablation, summary = {}, []
    for name, kwargs in variants:
        variant_model, variant_history = run_experiment(name, epochs=args.ablation_epochs, **common, **kwargs)
        ablation[name] = variant_history
        variant_layers = collect_outputs(variant_model, val_set, device)
        result = evaluate_ap(postprocess_sigmoid(variant_layers[-1]), val_set.targets, NUM_CLASSES)
        first = evaluate_ap(postprocess_sigmoid(variant_layers[0]), val_set.targets, NUM_CLASSES)
        summary.append((name, result, first, first_epoch_reaching(variant_history, 0.8), variant_history["time"][-1]))
        if kwargs.get("two_stage"):  # 2단계 모델은 뒤 장이 이어 쓸 수 있게 따로 저장한다
            two_stage_model = variant_model
            torch.save({"model": variant_model.state_dict(),
                        "config": {"num_queries": args.num_queries, "box_refine": True, "two_stage": True,
                                   "n_levels": 2}}, "ch08_two_stage.pt")
    print(f"\n[절제 요약] 에폭 {args.ablation_epochs} 뒤의 검증 성능 (시드 1개)")
    print("설정                      | AP     AP50   AP75  | 1층만의 AP  AP75 | AP≥0.8 첫 에폭 | 학습 시간")
    for name, result, first, reached, seconds in summary:
        print(f"{name:25s} | {result['AP']:.4f} {result['AP50']:.4f} {result['AP75']:.4f} | "
              f"{first['AP']:.4f}   {first['AP75']:.4f} | {str(reached):>8s}       | {seconds:5.0f}초")
    plot_convergence(ablation, os.path.join(args.fig_dir, "ch08-ablation.png"),
                     f"ablations of MiniDeformableDETR ({args.ablation_epochs} epochs each, one seed)")

    # 5-1 2단계 모델: 제안이 처음부터 객체 근처에 놓이는가
    two_stage_model.eval()
    with torch.no_grad():
        images = val_set.images[:250].to(device).float() / 255.0
        enc = two_stage_model(images)["enc_outputs"]
    enc_result = evaluate_ap(postprocess_sigmoid({k: v.cpu() for k, v in enc.items()}), val_set.targets[:250],
                             NUM_CLASSES)
    print(f"[2단계] 디코더를 거치기 전, 선택된 제안 {args.num_queries}개만으로 채점한 AP (검증 앞 250장): "
          f"AP {enc_result['AP']:.4f}, AP50 {enc_result['AP50']:.4f}, AP75 {enc_result['AP75']:.4f}")
    plot_refinement(two_stage_model, val_set, [index, index + 1],
                    os.path.join(args.fig_dir, "ch08-two-stage.png"), device)
    print(f"\n전체 걸린 시간 {time.time() - start:.0f}초")
# --8<-- [end:main]


if __name__ == "__main__":
    main()
