On simultaneous optimal segmentation of digital objects

摘要

Motivated from the image segmentation problem, we consider the problem of finding the maximum weight region with a shape decomposable into elementary shapes in n x n pixel grid where each pixel has a real valued weight. We give efficient algorithms for several interesting cases, extending our previous paper [13]. This shows a strong contrast with the NP-hardness results on finding the maximum weight union for the corresponding cases.%イメージ切り出し問題を動機として，基本図形分割可能領域に関する最大重み領域問題について考える．論文［13］の結果を拡張し，本論文では，いくつかの基本図形を考え，それぞれの基本図形に分割可能な領域族に対して効率的なアルゴリズムを与える．また，基本図形の和集合領域に関する最大重み領域問題に対する既存結果であるNP 困難性との対比も与える．