学生のページ

画像処理：アルゴリズム工学研究者の視点
浅野哲夫
浅野哲夫，正員，北陸先端科学技術大学院大学情報科学研究科

                 !" #   $    %$  & '()*('( % +はじめに
アルゴリズムというと，難しそうだとか常に最悪の場合ばかり考えていて実際には役に立たないのではないかという巷の批判があるが，最近は,役に立つ学問,を目指した研究が活発に行われている．本文では，画像に関係する研究に焦点を当てて，アルゴリズム工学研究者がどのような問題意識で研究を行っているかを分かりやすく述べる．

ディジタルハーフトーニング

濃淡のある画像をレーザプリンタのような本質的に（白黒の）２値の情報しか表現できない出力装置で出力しようとすると，濃淡画像を何らかの方法で２値化することが必要である．２値化の最も簡単な方法は，中間の濃淡レベルを閾値とする２値化であるが，この単純２値化法
では画像の細部が潰れてしまって，非常に悪い画質の画像になってしまうことが多い．そこで，いかにして入力画像とよく似た２値画像を構成するかについて従来から様々な方法が提案されてきた．これらの方法を総称して，ディジタルハーフトーニング #-   + と呼んでいる．
単純２値化法では，各画素を個々に処理したために全体としては入力画像と全く異なる画像になってしまうという欠点があった．入力画像と似た２値画像を得るためには，たとえば，平均濃淡レベルを変えずに２値化することが必要である．誤差伝播法として知られる方法では，各画素における２値化で生じた誤差を周囲の未処理画素に加えることにより平均濃淡レベルを保っている．たとえば，濃淡レベルを . から * までの実数で表すとき，ある画素の濃淡レベルが . ) ならば，中間の値 . / より小さいから . に丸める．このとき，. ) が丸め誤差になるが，この誤差を周囲の未処理画素に適当な係数を掛けて分配するのである．
上に述べた誤差伝播法は出力画像の画質が安定しているために，今では多くのプリンタで採用されている．工学的関心として，誤差伝播係数の調整は重要な問題であり，様々な角度から研究されてきている．図 * は単純２値化法と誤差伝播法の出力を示したものである．
では，アルゴリズム工学の研究者ならどのような視点でディジタルハーフトーニングの研究を行うだろうか．まず大事なことは，既存の技術をよく理解した上で，何にでも疑問を持つこ図 * 画像出力

単純２値化法と誤差拡散法の出力．とである．誤差伝播法ではラスター順に画像を走査するが，なぜラスター順なのだろう？平均濃淡レベルを保つことは分かっているが，何かの基準で最適なものを求めようとしているだろうか？計算時間についてはどうだろう？疑り深いと言えば聞こえが悪いが，子供のように,なぜ？,の疑問を発するところから研究は始まるのである．
最初の疑問である画像の走査順については，ラスター順を一般化することが考えられる．必要なことは，全画素をもれなく走査する順序を与えることであるが，更に誤差を伝播するには隣り合う画素を順につなぐことも大事なので，結局，全画素をちょうど一度ずつ訪問するツアーを考えることになる．そのようなツアーは，空間充填曲線，あるいは  0  1 という名前で呼ばれるものであり，ヒルベルト曲線やペアノ曲線などが知られている．しかし，従来の曲線は再帰的に定義されたものが多く，パターンの規則性から生じる問題を避けることが難しいという問題がある．これに対して，筆者はランダムスペースフィリングカーブという概念を導入し，その問題を避けることに成功している．さらに，すべての空間充填曲線の間の変換可能性にも着目し，どんな２つの空間充填曲線についても，局所的な経路の入れ替えだけで一方を他方に変換できることも示している 2* )3２番目の疑問は最適化に関するものである．もちろん，様々なテスト画像に対する出力結果を人間の目によって判断するというのが最も確実な評価法であろうが，このアプローチでは，たとえ良さそうな方法を考え付いても，それ以上に良い方法があるのかどうかは判定できない．
これがアルゴリズム工学研究者にとっては最大の悩みである．そこで，何らかの数学的な基準を定めて，その基準で最適な出力を得るという問題を定式化し，その計算困難さの解析を行うことになる．もし効率良く解けそうなら，どこまで効率を改善できるかが問題であり，どんな方法でも最適解を求めることが不可能そうであれば（つまり，問題がＮＰ困難であれば），次善の策として近似アルゴリズムを考えることになる．ただ，すぐにヒューリスティックな方法に走るのではなく，近似性能を保証できるアルゴリズムをまず考えるというのがアルゴリズム
工学研究者の視点である．
筆者の場合には，まずディジタルハーフトーニングの問題を最適化問題として定式化することから始めた．人間が画像を見るとき，視点を中心とする領域での平均濃淡レベルしか知覚することができないと考えるのは妥当であろう．そこで，画像上で多数の小領域を考えて，各小領域における平均濃淡レベルが入力画像と出力画像でどれだけ異なるかを求めて，それをその領域における誤差と考えることにする．全領域での誤差を適当な形で（絶対値の和とか２乗和など）加えたものを画像間の非類似度と定義するとき，問題は入力との非類似度が最小となる２値画像を求めよという最適化問題になる．この問題の計算複雑度は近傍の取り方によって変わる．実際，すべての ( ( の近傍を考えたとき，この組み合わせ最適化問題はＮＰ完全であることが最近証明された 243．しかしながら，すべての ( ( の近傍ではなく，左上の画素の座標値の和が偶数になるような近傍だけを考えると（ほぼ半分の近傍だけを考えることになる），この問題が多項式時間で解けることが判明した．基本的なアイディアは，問題をネットワークフロー問題に変換することである．ネットワークフローはアルゴリズムの分野で精力的に研究されてきた分野であり，様々な手法を駆使して効率の改善が図られて来た．特に，容量制約が整数で与えられる場合には，実行可能解があれば必ず整数解が存在するという性質がこの場合には重要である．
ここでは紙数の制約のために述べることができなかったが，最近になってディジタルハーフトーニングには様々な組み合わせ最適化問題や離散幾何的問題が関連していることが判明し，「アルゴリズム工学」の多数の研究者を魅了している．興味のある方は，特定研究「アルゴリズム工学」（代表者は京都大学の茨木教授）の報告書を参照されたい．

画像の領域分割与えられた画像に含まれる対象物を認識するための第１歩は，画像からそれらの対象物を切り出すことであるが，これを画像の領域分割という．この問題はパターン認識の基本問題として古くから注目を集め，これまでに実に様々な方法が提案されてきたが，多くの方法はある基準の下で最適な分割を求めるのではなく，画像の性質に応じて発見的に分割を行うというものであった．ここでは，筆者らが以前に計算幾何学のアルゴリズムに基づいて提案した方法について説明する．この方法は，画像の領域分割を最適化問題として定式化した上で，判別分析の基準で最適な領域を求めるものである 2(3．図 ( に領域分割の一例を示す．

図 ( 画像の領域分割
濃淡図形の中に一つの明るい物体が含まれていることが分かっているものとしよう．背景と物体との間の明るさに十分な差があれば，ある閾値を決めて明るい部分と暗い部分に分割すれば領域分割が完成するという場合もあるだろうが，ここではそのような楽観的な場合は考えない．分かっているのは，物体の部分が背景に比べて明るいということと，物体は一つの連結領域を形成しているということである．明るさの差に基づいた方法としては，画像平面内に一つの連結領域の中で，その領域内部の平均濃淡レベルと外部（背景）の平均濃淡レベルの差が最大になるような連結領域（あるいは，その境界）を求めるという方法が考えられる．ただし，単純な平均値の差だけでは１点だけ非常に明るい点があると，その点だけからなる領域が出力されてしまうこともありうるので，物体と背景の領域の面積の釣り合いも大切な要素である．したがって，面積のバランスも考慮して明るさの差を最大にする分割を求めることが要求されるが，このような基準を判別分析に基づく基準という．
問題は，判別分析の基準で最適な分割を効率よく求めることができるかどうかである．確かに，領域を定めれば平均濃淡レベルの差などを計算することは容易である．しかし，考えないといけない領域の形は非常に沢山あり，すべての可能な形状を列挙して，最適なものを選ぶという単純な方法は計算時間の点で破綻してしまう．実際，筆者らは最適な分割を求める問題はＮＰ困難であることを証明した 2(3．したがって，このままでは効率の良い解法は期待できない．
しかし，驚くべきことに，領域の形状を水平または垂直方向に単調なものに限定すると，アルゴリズムの技法を用いて効率良く最適解を求めることができるのである．ここで，水平方向に単調な図形とは，上下部の境界がどちらも左から右へと単調に変化するものを言う．最悪の場
合には画素数の２乗に比例する時間が必要になるが，実際の画像に適用した場合には画素数に比例する時間だけでよいことが実験的に分かっている 2(3．



おわりにアルゴリズムというと，計算時間を短縮するための技法だと思われているふしがある．もちろん，高速化は大きな目標の一つであるが，最大の目標は問題の本質を理解し，その本質的な計算複雑さを探ることである．本文で述べたハーフトーニングや領域分割の問題は，多項式時間で解けるかどうかの境界にある問題であり，今まで多項式時間で解けるかどうかすら検討されなかったものである．それだけに，実用的にはまだまだ不完全であってもアルゴリズム工学研究者としては大きな発見であったと自負しているところである．

参考文献

2*3    56 7     - 8 -  0  1 ,$ $   0 -    9(  )  //)//: ! *'''
2(3   6 ;   <   -   & 5 Æ     = - 8   , $    %     >   -   ** (  *4/*:: (..*2)3    <  7 &  -   & 5 1"   - ? 
1 ,        #*''9+  ).@A)*:
243    !  -   & 5   B    8  -
  C "  D   - ! ,  - %     *@ )  4*94(@(...