A Dynamic Programming Framework for Discovering Count and Values of Multilevel Image Thresholding

기술 요약: 다단계 이미지 임계값의 개수와 값을 발견하기 위한 동적 프로그래밍 프레임워크

문제 제기
다단계 이미지 임계값 설정은 컴퓨터 비전의 근본적인 전처리 단계로, 종종 픽셀 강도를 별도의 그룹으로 분리하는 클러스터링 문제로 규정됩니다. 최첨단 방법들은 일반적으로 최적의 임계값을 찾기 위해 목적 함수 (예: 오츠, 카푸르, 키틀러) 와 탐색 전략에 의존하지만, 중요한 한계가 존재합니다: 대부분의 방법은 사용자가 입력으로 임계값의 개수($n$) 를 수동으로 지정해야 합니다. 적절한 $n$을 결정하는 것은 단순하지 않은데, SSIM 과 PSNR 과 같은 유사도 지표는 이미지 충실도를 극대화하기 위해 임계값의 개수를 높이는 것을 내재적으로 선호하므로, 최적의 $n$을 자동으로 선택하는 데는 적합하지 않습니다. 또한, 고정된 $n$에 대해 최적 해를 보장하는 정확한 탐색 전략인 동적 프로그래밍 (DP) 은 사용자가 여러 후보 값을 반복하여 최적의 $n$을 탐색하려 할 때 실행 시간이 기하급수적으로 증가하는 고통을 겪습니다. 반면, 근사적 메타휴리스틱 방법들은 속도를 제공하지만 확률성과 지역 최적점의 위험으로 인해 신뢰성이 부족합니다.

방법론
저자들은 수정된 최소 오차 임계값 (MET) 기준과 동적 프로그래밍 알고리즘의 특정 변형을 통합한 새로운 방법인 MET-DP를 제안합니다. 방법론의 핵심 기여는 다음과 같습니다:

1. 수정된 MET 기준: 저자들은 전통적인 목적 함수 (오츠, 카푸르) 가 임계값의 개수가 증가함에 따라 값이 단조 증가하는 경향을 보이며, 이로 인해 자동 임계값 개수 선택에 비효율적임을 관찰했습니다. 반면, 키틀러 (MET) 기준은 임계값이 증가함에 따라 엄격하게 감소하지는 않습니다. 저자들은 비용 계산 시 임계값을 하위 클래스와 상위 클래스 모두에 포함되도록 허용하는 "중첩" 형식을 도입하되, 최종 이미지 분할에는 기존의 불연속 할당을 유지하도록 MET 기준을 수정했습니다. 이 수정은 높은 개수 편향 없이 최소값이 최적의 임계값 개수를 나타낼 수 있는 비용 지형을 생성합니다.

2. 동적 프로그래밍 변형: $n$을 입력으로 받아 $j$ 위치의 $i$번째 임계값에 대한 테이블 $dp[i][j]$를 계산하는 전통적인 DP 접근법 (알고리즘 1) 과 달리, 제안된 알고리즘 (알고리즘 2) 은 구간 $[i, j]$에 대해 재귀적으로 작동합니다. 이 알고리즘은 구간을 단일 클래스로 분할하거나 최적의 분할점 $k$에서 분할하는 데 필요한 최소 비용을 결정합니다. 재귀 관계식은 다음과 같이 정의됩니다:
   $$J(i, j) = \min \left( Q(i, j), \min_{k=i+1}^{j-1} \{ Q(i, k) + J(k, j) \} \right)$$
   여기서 $Q$는 단일 클래스의 비용이고 $J$는 총 비용입니다. 이 구조를 통해 알고리즘은 단일 패스 내에서 최적의 임계값 값 집합과 최적의 임계값 개수를 동시에 발견할 수 있습니다.

3. 복잡도: 제안된 알고리즘의 시간 복잡도는 $O(L^3)$이며 공간 복잡도는 $O(L^2)$입니다. 여기서 $L$은 강도 레벨의 수 (예: 256) 입니다. 저자들은 고정된 $n$에 대해 전통적인 DP 가 $O(n \cdot L^2)$의 복잡도를 갖는 반면, 제안된 방법은 서로 다른 $n$ 값에 대한 반복 실행이 필요하지 않으므로 임계값의 개수에 대해 실행 시간이 실질적으로 일정하다고 지적합니다.

주요 결과
MET-DP 방법은 다양한 데이터셋 (자연, 위성, 의료) 으로 구성된 15 개의 이미지와 통계 분석을 위한 더 큰 718 개의 이미지 세트로 평가되었습니다.

• 자동 임계값 선택: MET-DP 는 다양한 이미지 유형에 적합한 임계값 개수를 성공적으로 결정했습니다. 예를 들어, 전통적인 방법들이 모드를 올바르게 분리하지 못했던 3 개의 모드 히스토그램 (이미지 326085) 의 경우 3 개의 임계값을 정확하게 식별했습니다. 그러나 이 방법은 히스토그램의 미세한 변동에 민감하여 일부 의료 이미지 (예: 이미지 007-Flair-60 의 경우 25 개의 임계값) 에서 "과잉 임계값"을 초래하고, 다른 이미지들 (예: Tile-8-Part-008 에서 뚜렷한 피크를 병합) 에서는 "과소 임계값"을 초래하는 경향을 보였습니다.
• 실행 시간 효율성: 1 에서 15 까지의 임계값 개수에 대해 전통적인 방법들을 반복적으로 실행한 비교 테스트에서 MET-DP 는 훨씬 낮은 총 CPU 실행 시간을 보여주었습니다. 전통적인 방법들의 실행 시간은 테스트된 개수에 따라 다항식적으로 증가 ($O(m^2 \cdot L^2)$) 하는 반면, MET-DP 는 $L$에만 의존하는 고정된 실행 시간을 유지합니다.
• 분할 품질:
  • SSIM: MET-DP 는 복잡한 다중 모드 히스토그램을 가진 이미지 (예: 자연 이미지 147091 및 77200701) 에서 전통적인 방법들을 종종 능가하는 경쟁력 있는 구조적 유사도 지수 (SSIM) 값을 달성했습니다.
  • PSNR: 이 방법은 일반적으로 오츠와 카푸르에 비해 낮은 피크 신호 대 잡음비 (PSNR) 값을 생성했습니다. 저자들은 이 현상을 이 방법이 미세한 변동을 분리하는 경향으로 인해 전통적인 방법들이 생성하는 더 매끄러운 분할에 비해 픽셀 수준의 충실도가 감소하기 때문이라고 설명합니다.

의의 및 주장
이 논문은 MET-DP 가 자동 다단계 임계값 설정을 위한 계산적으로 효율적이고 적응적인 프레임워크를 제공한다고 주장합니다. 그 주요 의의는 자동화된 비전 파이프라인의 일반적인 병목 현상인 사용자 정의 임계값 개수의 필요성을 제거하는 데 있습니다. 저자들은 오츠나 카푸르와 달리 그 값이 임계값의 개수에 따라 단조 증가하지 않기 때문에 수정된 MET 기준이 이 작업에 고유하게 적합하며, 비용 함수에서 "적정 지점"을 식별할 수 있다고 강조합니다.

저자들은 MET-DP 가 계산 효율성과 자동 파라미터 선택 측면에서 우수하지만, 원시 이미지 재구성 품질 (PSNR) 측면에서 전통적인 방법들을 보편적으로 능가하지는 않는다고 겸손하게 결론지었습니다. 그들은 이 방법이 자동 임계값 선택이 필요하고 미묘한 강도 변동을 분리하는 것이 중요한 응용 분야에 특히 적합하며, 높은 PSNR 이나 잡음에 강하고 거친 분할을 우선시하는 작업에서는 전통적인 방법이 여전히 선호될 수 있다고 제안합니다. 이 논문은 새로운 응용 분야를 제안하기보다는 비지도 임계값 개수 결정이라는 특정 문제에 대한 MET-DP 를 견고한 대안으로 위치시킵니다.