並列タイトル等A Study on Computational Complexity and Efficient Implementation of Region Segmentation Problem of an Image under Various criteria
タイトル（掲載誌）平成9(1997)年度 科学研究費補助金 基盤研究(C) 研究報告書概要 = 1997 Fiscal Year Final Research Report Summary
一般注記金沢大学 / 北陸先端科学技術大学院大学
本研究では,画像認識の基礎となる領域分割についてアルゴリズム理論の立場から考察を行った.すなわち,様々な数学的基準に対して,その基準における最適解を求める問題がどの程度の計算手間を必要とするかを解析し,さらに多項式時間のアルゴリズムを得るためにはどのような制約条件を付加する必要があるかを考察した.特に,判別分析の基準に基づいて,画像を連結な2つの部分に最適な形で分割する多項式時間のアルゴリズムを得ることに成功した.様々な種類の画像に適用した結果,かなり安定な分割を得ることができたので,所期の目的を達成できたものと思われる.このアルゴリズムの基本的な道具は動的計画法であるが,申請者が現在専門にしている計算幾何学における技法,特に,ハンドプロービングとパラメトリック探索法がが高速化に威力を発揮した.従来の領域分割の方法は、人間の直観に基づいた曖昧な基準に基づく発見的法が多く見受けられ、性能が対象画像によって大きく異なった.また,経験的知識に頼り過ぎるために多数の例外処理を含む複雑な方法になってしまうことが多かった.本研究で提案した方法は、既に実績のある判別分析法に基づいており、しかも計算幾何学で開発されたアルゴリズム設計技法に則っているのが特筆すべき点である。本研究での成果は,ギリシャ,ドイツおよび米国における国際会議と,応用数理学会などで発表し,アルゴリズム理論家から高い評価を受けた.今後は更に多くの画像で実験を行うことにより,実用的側面からの検討を強化していきたいと考えている.
In this study we considered regions segmentation problem which is a basis for image understanding from as viewpoint of algorithm theory. First, for each of various criteria for regions segmentation we analyzed the computational complexity of the problem of finding an optimal solution under the criterion together with consideration on requirements for polynomial-time implementation. One of the main results is that we obtained a polynomial-time algorithm for finding an optimal segmentation based on discriminant analysis. Experimental results suggest practical application of the algorithm. Especially various algorithmic techniques developed in computational geometry made great contributions to the algorithm.The research results were presented in several international conferences and accepted for publication in international journals. One of the future plans is to do more computer experiments for really practical applications.
研究課題/領域番号:08680382, 研究期間(年度):1996 - 1997
出典：「様々な基準の下での画像の領域分割問題の計算複雑度と処理の高速化に関する研究」研究成果報告書 課題番号08680382（KAKEN：科学研究費助成事業データベース（国立情報学研究所）） （https://kaken.nii.ac.jp/ja/report/KAKENHI-PROJECT-08680382/086803821997kenkyu_seika_hokoku_gaiyo/）を加工して作成
一次資料へのリンクURLhttps://kanazawa-u.repo.nii.ac.jp/?action=repository_action_common_download&item_id=55712&item_no=1&attribute_id=26&file_no=1
関連情報https://kaken.nii.ac.jp/search/?qm=90113133
https://kaken.nii.ac.jp/ja/grant/KAKENHI-PROJECT-08680382/
https://kaken.nii.ac.jp/ja/report/KAKENHI-PROJECT-08680382/086803821997kenkyu_seika_hokoku_gaiyo/
連携機関・データベース国立情報学研究所 : 学術機関リポジトリデータベース（IRDB）（機関リポジトリ）