[DL輪読会]A Generalization of Otsu’s Method and Minimum Error Thresholding[ECCV2020]

DEEP LEARNING JP [DL Papers] A Generalization of Otsu’s Method and Minimum Error Thresholding [ECCV2020] Masashi Yokota, RESTAR Inc. http://deeplearning.jp/ 1

• http://deeplearning.jp/

書誌情報 • 著者: Jonathan T. Barron (Google Research) • ECCV2020採択 • Otsu’s BinarizationとMETという有名な二値化アルゴリズムを 一般化し、少ないパラメータかつシンプルなロジック(python で数十行のコード) な手法を提案。DL手法や複雑な前処理をし た手法よりも良いパフォーマンスを達成。 2

1. Introduction 3

1.1 背景 • 二値化は画像内のノイズを 除去し、性能向上に貢献す る重要な前処理 • 二値化アルゴリズムの例: • Otsu’s Binarization [Otsu 1979] • Kittler’s Binarization [Kittler et. al. 1986] • Howe’s Binarization [Howe 2013] 4

1.1 なぜ二値化が必要か？ • 医用画像処理やOCRなど Deep Learningを使う手法 の前処理としても使われる ことがある • DLモデルを構築する際 データ数の制約や、タスク を容易化する必要がある 場合、性能を向上させる 大きな要因となりうる 5

1.2 二値化アルゴリズム クラス1 クラス0 0 しきい値 255 多くの二値化手法は入力画像からヒストグラムを考え、しきい値を何かし らの方法で決定し、ヒストグラムを分割。しきい値の超える場合は白、下 回る場合は黒とすることで画像を二値化する。 6

1.2 二値化アルゴリズム • 何かしらの方法でしき い値を自動決定し二値 化を行う ex: Otsu’s Binarization • Otsu’s Binarization: 画素のヒストグラム内 の黒クラスと白クラス のクラス間分散が最大 となる値をしきい値と して用いて二値化する Ref: http://labs.eecs.tottori-u.ac.jp/sd/Member/oyamada/OpenCV/html/py_tutorials /py_imgproc/py_thresholding/py_thresholding.html 7

• http://labs.eecs.tottori-u.ac.jp/sd/Member/oyamada/OpenCV/html/py_tutorials/py_imgproc/py_thresholding/py_thresholding.html

1.3 Otsu’s Binarizationの限界 上記の例のようにOtsu’s Binarizationでは正確に二値化できない ケースがある。 8

1.4 提案手法概要 提案手法では、Otsu’s BinarizationとMETの二値化アルゴリズムを 一般化し、より正確にしきい値を決定できるアルゴリズムを提案する9

2. 関連研究 10

2.1 Otsu’s Binarization [Otsu 1979] クラス間分散𝜎𝑏2 がもっとも大き くなる値をしきい値とする アルゴリズム: 11

2.2 Minimum Error Thresholding [Kittler et. al. 1986] 𝑃𝑘 𝑇 : クラスkに属するヒストグラムの総カウント 𝜎𝑘 𝑇 : クラスkの分散 http://www.thothchildren.com/chapter/5bc4b10451d930518902af3b Otsu’s Binarizationでは片方の分布が 偏っている場合、しきい値が一方に 極端に偏ってしまうが、この手法は それが起こりにくい。 12

• http://www.thothchildren.com/chapter/5bc4b10451d930518902af3b

3. Preliminary 13

3.1 Preliminary ヒストグラムを示す変数を定義: (このあと使います) 𝑤 (𝑘) : 各クラスのヒストグラムのbin合計 𝑛 1 : すべてのヒストグラムのbin合計 𝜋 (𝑘) : 各クラスのヒストグラムの重み 𝜇 (𝑘) : 各クラスのヒストグラムの平均 𝑑 (𝑘) : 各クラスのヒストグラムのdistortion 14

3.1 Preliminary distortion(𝒅(𝒌))について馴染みがない人もいると思われるので 詳しく見てみる 15

3.1 Preliminary distortion(𝒅(𝒌))について クラスの中心点とそのクラスに属する点との距離の合計 distortionの式は以下の観点を元に設計されている: 1. csum/dsumを使用して期待値計算が可能である 2. 分散は の形で表せること 3. 分散はdistortionに比例する 16

4. Algorithm 17

4.1 Algorithm • 本提案手法では画像の各ピクセルが2つの確率分布から生成さ れていると仮定し、以下の同時確率分布を最大化する: 18

4.1 Algorithm • 本提案手法では画像の各ピクセルが2つの確率分布から生成さ れていると仮定し、以下の同時確率分布を最大化する: ハイパーパラメータ 19

4.1 Algorithm • 本提案手法では画像の各ピクセルが2つの確率分布から生成さ れていると仮定し、以下の同時確率分布を最大化する: 白・黒の各クラスの mixture probability 20

4.1 Algorithm • 本提案手法では画像の各ピクセルが2つの確率分布から生成さ れていると仮定し、以下の同時確率分布を最大化する: 平均: 𝜇 (𝑘), 標準偏差: 𝜎 (𝑘) の ガウス分布 21

4.1 Algorithm • 本提案手法では画像の各ピクセルが2つの確率分布から生成さ れていると仮定し、以下の同時確率分布を最大化する: 逆カイ二乗分布 →ガウス分布の共役事前分布 22

4.1 Algorithm • 本提案手法では画像の各ピクセルが2つの確率分布から生成さ れていると仮定し、以下の同時確率分布を最大化する: ベータ分布→二項分布の共役事前分布 23

4.1 Algorithm • 求めたいのは、目的関数が最大となるgray scale degreeなので 先の式をヒストグラムの𝑖番目のgray scale degree( 𝑥𝑖 )とbinカ ウント( 𝑛𝑖 )を用いて書き直す: • 上の式のlogをとり、以下の対数尤度を得る: 24

4.1 Algorithm 次に計算容易化のため以下のように仮定を簡略化する。 • 新たな仮定: しきい値 𝑖で2つに分割されて得られたヒストグラムは各クラス のガウス分布からそれぞれ生成されると仮定: • 提案手法は上式で最大となる𝑖を選ぶのため以下のように示せる 25

4.1 Algorithm • 先の式を展開すると以下のようになる: 26

4.1 Algorithm • 先の式を展開すると以下のようになる: • 𝑓 (𝑘) は各クラスのガウス分布、 𝑣 (𝑘) はガウス分布の標準偏差と 見なせる。そのため、𝜈 , 𝜏 2 はガウス分布の分散の大きさに寄与 する 27

4.1 Algorithm • 先の式を展開すると以下のようになる: • 𝜔は、0に近ければ、分布がヒストグラムの始点に近づき、 1に近づけば、ヒストグラムの終点に近づく（後ほど実験も踏 まえて説明します） 28

4.1 Algorithm • 先の式を展開すると以下のようになる: • 𝜅は、𝜔の影響の強さを示し、k=1の場合だと効果はなく、k<1 の場合だと期待するthresholdの値とは逆方向に働く 29

4.1 Algorithm • 提案手法のハイパーパラメータはユーザーにアルゴリズムに対 して事前知識を入れられる余地となる • Ex: OCRであれば白のピクセルが多いので、 𝜔を小さく設定し た方がよい etc 30

4.1 Algorithm 最後に、従来手法ではヒストグラムを標準化する必要がある場合 が多いが、提案手法ではその必要がないため、上記のように生の ヒストグラムをそのまま利用可能。 31

4.2 - 4.5 Special Case 以降は提案手法がOtsu’s BinarizationとMETを一般化していることを示して いきます 32

4.2 Special Case: Minimum Error Thresholding • 2.2 の先行研究であるMETを本論文の変数を用いて表す: • これは、以下の条件のときの提案手法に等しい 33

4.3 Special Case: Otsu’s Method • 本論文の変数を用いてOtsu’s Binarizationを表現する: • クラス間分散は全体の分散から各クラスの分散を引いたものな ので、提案手法と比較しやすいよう、以下のように変形: ヒストグラム全体の分散 各クラスの分散 • （ヒストグラム全体の分散はしきい値によらず一定なので） 上式は− 𝑛 1 (𝑑0 + 𝑑1 )が最小となる時に𝒐は最大となる 34

4.3 Special Case: Otsu’s Method • 提案手法の𝜐を無限に近づけると以下の式になる: • さらに、𝜏を0に近づけると第一項の影響が他の項に比べて 大きいため実質的に以下の式を最小化するのと等しくなる。 • これは 𝑛 1も1/𝜏 2も定数であるため前ページの𝒐を最小化する場合 と結果は同じとなる。そのため、以下のように示せる: 35

4.3 Special Case: Otsu’s Method • 図のヒストグラムに対して、 提案手法をvの値を変化させ て適用した場合のthresholdの 値の変化を確認。 • vが0に近い場合: METの結果に近づく • vが大きい場合: Otsuの結果に近づく • 提案手法は実験的に見ても 先行研究を一般化できている 36

4.4 Relationship to Histogram Bin Width • 前処理のテクニックとしてヒストグラムのbinの幅を調整する ことで性能を上げることができる。binの操作は一般に以下の ような効果がある • binの幅を粗くする: 性能が安定する • binの幅を細くする: 正確に局所化されたしきい値を得られる • 画像に対してガウシアンフィルタを適用することは、binの幅 を荒くすることに等しいため、ヒストグラムに対してガウシア ンフィルタを適用した場合を提案手法に適用できるか考える 37

4.4 Relationship to Histogram Bin Width • 分散 𝜎 2 のガウシアンフィルタ𝑓(𝜎) とし、 n ∗ 𝑓(𝜎) はヒストグ ラムに対する畳込みとすると以下のように示せる: かつ • これは、 を提案手法に適用した場合と ほぼ等しい(※ 𝜖: small positive number) • つまり𝜏はヒストグラムのbinの幅を調整していると考えられる 38

4.5 Special Case: Weighted Percentile 中央値などx%分位点でしきい値を決定したい場合を考える。 • 𝜅が十分に大きい時、提案手法は以下のように展開できる: • (0) (0) 上記の式は、𝜋𝑖 で微分したときに、𝜋𝑖 = 𝜔の時0になり、 上に凸となるため100 𝜔パーセンタルの結果と同等となる。 よって、以下のように示せる: • これは、𝜅が十分に大きい時、ベータ分布がthresholdに対して 100 𝜔パーセンタルに近づくように正則化を加える効果がある 39 →白 or 黒側に寄り易いようにバイアスを加えられる

4.5 Special Case: Weighted Percentile • 左は3つの山があるヒストグ ラムの場合の各手法の結果 • wが1/2を境に1/3のポイン トと2/3のポイントにしきい 値を決定できており、しき い値に対して正常にバイア スを加えられている 40

4.6 Special Case まとめ • 提案手法は二値化アルゴリズムを一般化した形であり、パラ メータを調整することで以下のアルゴリズムと同等となる: • → MET • → Otsu’s Binarization • 𝜅 = 0, → ヒストグラムのビン幅の調整 • 𝜅が十分に大きい時 → 分位点によるしきい値決定 すなわち、ハイパーパラメータをチューニングする際にユーザー がアウトプットに対して意図的にバイアスを加えることが可能 41

4.7 実装コード (Python) • 数式でごちゃごちゃ説明したが 実際にpythonに落とし込むと 左のように数十行程度で記述可能 なほどシンプル。 • 実装の詳細を知りたいは論文の appendixを読んで下さい(笑) 42

5. Experiment 43

4.1 実験条件 • データセット: 2016 Handwritten Document Image Binarization Contest (HDIBCO) challenge (20枚の画像を二値化する) • ハイパーパラメター決定方法: H-DIBCO 2013(8枚の画像)を用いて決定 • 評価指標: • F-Measure • PSNR • DRD 𝑊𝑁𝑚のマトリックス R: 画像内の最大値 (8bit gray scale画像なら255) NUBN: 画像中の non-uniform (全ピクセルが白or 黒でない) 8x8blockの数 44

4.2 実験結果: 定量評価 ニューラルネットワークを用いた、Tensmeyer & Martinezらの手 法やOtsuやMET等のベーシックな手法, その他複雑な前処理をし 45 ている先行研究よりも簡単かつ少ないパラメータで性能を上回る。

4.2 実験結果: 定量評価 Oracle Global Thresholdは答えを知っている上で、最適な thresholdを決定した場合の結果(ある意味理論値)。他手法と比 べ、Oracle Global Thresholdと同等の性能を達成。 46

4.3 実験結果: 定性評価 • 提案手法はOracle Global Thresholdと近い値に位置 づけられており、十分に良 いしきい値を設定できてい る。 47

4.3 実験結果: 定性評価 48

4.3 実験結果: 定性評価 49

まとめ • Otsu’s BinarizationとMETを一般化した二値化アルゴリズムで あるGHTを提案 • ハイパーパラメータを調整することで、しきい値にバイアスを 加えられるため、画像の分布が偏っている場合でも適切な しきい値をアウトプットできる 50

感想 • Oracle Binarizationの結果を見る限り、画像全体で単一の thresholdを設定するには限界がある • H-DIBCOの他手法を眺めても、前処理をしてノイズを減らした 上で、二値化する手法がメイン • 一方で、より細かい部分画像ごとに(もっといってしまえば、 pixel単位で)適切なthresholdはあるはずで、そういった方向性 の手法もあってもよさそう（ご存知でしたら教えて下さいw） 51