|
画像データから特定の対象物に対応する領域を抽出する問題をイメージ切り出し(image segmentation)という。イメージ切り出しは画像処理における重要かつ難しい問題であり,たとえば航空写真から特定の建物などの対象物の抽出,文字などのパターン認識などに応用される。この問題はかなり古くから研究されており多くの手法が開発されているが,最適化問題として定式化して手法の構築を試みているものはあまりみられない。本論文では白黒のディジタル画像に限定し,与えられた画像を二つの領域に分割したい,つまり画像から背景部分を取り除いて対象物を抽出する問題に限定したイメージ切り出しの問題を組合せ最適化問題に定式化し,その高速アルゴリズムを最近で共同開発したので,その方法について解説をおこなう。ここでは,抽出したい対象物は1つの連結領域からなる場合を扱う。計算機実験によるとわれわれの開発した手法はかなり良好であるという結果が得られている。本論文の構成は以下の通りである。2節では本論文で扱うイメージ切り出し問題の定義をおこない,組合せ最適化問題としての定式化を与える。抽出したい領域に対する制約として,"領域が連結である"というだけでは一般にNP困難であることが分かっているので,抽出される領域にさらに制限を加え,抽出領域が一本のx-単調な曲線で区切られている場合(第3節),さらに二本のx-単調な曲線で区切られている場合について考察し(第4節),これらの場合に対する多項式時間アルゴリズムの概略について述べる。
|
