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

技術的概要：多レベル画像閾値処理の個数と値の発見のための動的計画法フレームワーク

問題定義
多レベル画像閾値処理は、コンピュータビジョンにおける基本的な前処理ステップであり、画素強度を異なるグループに分離するクラスタリング問題として定式化されることが多い。最先端の手法は通常、最適閾値を見つけるために目的関数（Otsu、Kapur、Kittler など）と探索戦略に依存しているが、重大な限界が存在する：ほとんどの手法は、閾値の「個数」$n$ を入力としてユーザーが手動で指定することを要求する。適切な $n$ を決定することは容易ではない。なぜなら、SSIM や PSNR などの類似度指標は、画像忠実度を最大化するために閾値の個数を高くする方向に本質的に偏っており、最適な $n$ を自動的に選択するには不適切だからである。さらに、動的計画法（DP）のような厳密な探索戦略は、固定された $n$ に対して最適解を保証するが、ユーザーが複数の候補値を反復して最適な $n$ を探索しようとすると、実行時間が指数関数的に増大するという欠点がある。一方、近似メタヒューリスティック手法は高速であるが、確率性や局所最適解のリスクにより信頼性に欠ける。

手法
著者は、修正された最小誤差閾値法（MET）基準と、動的計画法アルゴリズムの特定のバリアントを統合した新しい手法 MET-DP を提案する。この手法の核心的な貢献は以下の通りである：

1. 修正 MET 基準：著者は、従来の目的関数（Otsu、Kapur）が閾値の個数が増加するにつれて値が単調増加する傾向を示し、閾値個数の自動選択には効果的ではないことを指摘する。これに対し、Kittler（MET）基準は閾値の増加に伴い厳密に減少するわけではない。著者は、コスト計算中に閾値値を下部クラスと上部クラスの両方に含める（「重なり」定式化）ように MET 基準を修正し、最終的な画像セグメンテーションでは従来の非重複割り当てを維持する。この修正により、最小値が閾値個数の偏りなしに最適な閾値個数を示すことができるコストランドスケープが創出される。

2. 動的計画法のバリアント：従来の DP アプローチ（アルゴリズム 1）が $n$ を入力として受け取り、位置 $j$ における $i$ 番目の閾値に対して表 $dp[i][j]$を計算するのに対し、提案アルゴリズム（アルゴリズム 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 は、さまざまな画像タイプに対して適切な閾値個数を正常に決定した。例えば、従来の手法がモードを正しく分離できなかった三峰性ヒストグラム（画像 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 は、競合する構造的類似度指標（SSIM）値を達成し、複雑な多峰性ヒストグラムを持つ画像（例：自然画像 147091 および 77200701）では、従来の手法を上回る性能を示すことが多かった。
  • PSNR：この手法は、一般的に Otsu や Kapur と比較してピーク信号対雑音比（PSNR）の値が低かった。著者は、この原因を、この手法が微細な変動を分離する傾向にあることに起因すると指摘する。これは、従来の手法が生み出すより滑らかなセグメンテーションと比較して、画素レベルの忠実度を低下させる。

意義と主張
本論文は、MET-DP が自動多レベル閾値処理のための計算効率的かつ適応的なフレームワークを提供すると主張する。その主な意義は、自動化されたビジョンパイプラインにおける一般的なボトルネックである、ユーザー定義の閾値個数の必要性を排除することにある。著者は、Otsu や Kapur と異なり、その値が閾値の数とともに単調に増加しないため、修正された MET 基準がこのタスクに特に適しており、コスト関数における「絶妙な点」の特定を可能にすると強調している。

著者は、MET-DP が計算効率と自動パラメータ選択の点で優れている一方、生画像再構成の品質（PSNR）の点では従来の手法を普遍的に凌駕するわけではないと控えめに結論づけている。この手法は、自動閾値選択を必要とし、微妙な強度変動の分離が重要なアプリケーションに特に適していると示唆される一方、高い PSNR やノイズ耐性のある粗いセグメンテーションを優先するタスクでは、従来の手法が好まれる可能性がある。本論文は新しい応用を提案するものではなく、教師なし閾値個数決定という特定の問題に対する堅牢な代替案として MET-DP を位置づけるものである。