JAIST Repository >
b. 情報科学研究科・情報科学系 >
b10. 学術雑誌論文等 >
b10-1. 雑誌掲載論文 >

このアイテムの引用には次の識別子を使用してください: http://hdl.handle.net/10119/13756

タイトル: Base location problems for base-monotone regions
著者: Chun, Jinhee
Horiyama, Takashi
Ito, Takehiro
Kaothanthong, Natsuda
Ono, Hirotaka
Otachi, Yota
Tokuyama, Takeshi
Uehara, Ryuhei
Uno, Takeaki
キーワード: pixel grid
image segmentation
computational geometry
base-monotone regions
発行日: 2013-02-14
出版者: Springer
誌名: Lecture Notes in Computer Science
巻: 7748
開始ページ: 53
終了ページ: 64
DOI: 10.1007/978-3-642-36065-7_7
抄録: The problem of decomposing a pixel grid into base-monotoneregions was first studied in the context of image segmentation. It is known that for a given n × n pixel grid and baselines, one can compute in O(n^3) time a maximum-weight region that can be decomposed into disjoint base-monotone regions [Chun et al. ISAAC 2009]. To complement this fact, we first show the NP-hardness of the problem of optimally locating k baselines in a given pixel grid. Next we present an O(n^3)-time 2-approximation algorithm for this problem. We also study some polynomial-time solvable cases, and variants of the problem.
Rights: This is the author-created version of Springer, Jinhee Chun, Takashi Horiyama, Takehiro Ito, Natsuda Kaothanthong, Hirotaka Ono, Yota Otachi, Takeshi Tokuyama, Ryuhei Uehara, and Takeaki Uno, Lecture Notes in Computer Science, 7748, 2013, 53-64. The original publication is available at www.springerlink.com, http://dx.doi.org/10.1007/978-3-642-36065-7_7
URI: http://hdl.handle.net/10119/13756
資料タイプ: author
出現コレクション:b10-1. 雑誌掲載論文 (Journal Articles)

このアイテムのファイル:

ファイル 記述 サイズ形式
19058.pdf1041KbAdobe PDF見る/開く

当システムに保管されているアイテムはすべて著作権により保護されています。

 


お問い合わせ先 : 北陸先端科学技術大学院大学 研究推進課図書館情報係