濃淡画像のハーフトーニングの最適化問題としての定式化と計算複雑度解析

Material type: 文書・図像類

Author: 浅野, 哲夫ほか

Publisher: -

Publication date: 2002-03-25

Material Format: Digital

Capacity, size, etc.: -

NDC: -

View All

Notes on use

Note (General)：: 金沢大学 / 北陸先端科学技術大学院大学本研究では,濃淡画像を白黒の2値で出力するための技術であるハーフトーニングを組み合わせ最適化問題として定式化するとともに,その本質的な計算複雑度の解析を行った.この種の技法は,ファクシミリやレーザプリンタのように黒点しか出力できない出力装置で濃淡画像を扱う際に...

Related materials as well as pre- and post-revision versions

https://kaken.nii.ac.jp/search/?qm=90113133

https://kaken.nii.ac.jp/ja/grant/KAKENHI-PROJECT-10680344/

https://kaken.nii.ac.jp/ja/report/KAKENHI-PROJECT-10680344/106803442000kenkyu_seika_hokoku_gaiyo/

Search by Bookstore

Holdings of Libraries in Japan

This page shows libraries in Japan other than the National Diet Library that hold the material.

List of Cooperating Institutions and Databases

Please contact your local library for information on how to use materials or whether it is possible to request materials from the holding libraries.

other

Kanazawa University Repository for Academic Resources
Digital
You can check the holdings of institutions and databases with which 学術機関リポジトリデータベース（IRDB）（機関リポジトリ） is linked at the site of 学術機関リポジトリデータベース（IRDB）（機関リポジトリ）.
Kanazawa University Repository for Academic Resources

Search by Bookstore

Bibliographic Record

You can check the details of this material, its authority (keywords that refer to materials on the same subject, author's name, etc.), etc.

Digital

Material Type: 文書・図像類
Title: 濃淡画像のハーフトーニングの最適化問題としての定式化と計算複雑度解析
Author/Editor: 浅野, 哲夫
Asano, Tetsuo
Author Heading: 浅野, 哲夫
Asano, Tetsuo
Publication Date: 2002-03-25
Publication Date (W3CDTF): 2002-03-25
Alternative Title: Formulating Digital Halftoning of Continuous-tone Images As Optimization Problem with Analysis of its Computational Complexity
Periodical title: 平成12(2000)年度科学研究費補助金基盤研究(C) 研究成果報告書概要 = 2000 Fiscal Year Final Research Report Summary
No. or year of volume/issue: 1998 – 2000
Volume: 1998 – 2000
Pages: 3p.-
Text Language Code: jpn
Subject Heading: アルゴリズム
最適化問題
ハーフトーニング
ネットワークフロー
計算機実験
Algorithm
Optimization problem
Halftoning
Network flow
Computer experiments
Target Audience: 一般
Note (General): 金沢大学 / 北陸先端科学技術大学院大学
本研究では,濃淡画像を白黒の2値で出力するための技術であるハーフトーニングを組み合わせ最適化問題として定式化するとともに,その本質的な計算複雑度の解析を行った.この種の技法は,ファクシミリやレーザプリンタのように黒点しか出力できない出力装置で濃淡画像を扱う際に不可欠であり,実用的な側面から様々な方法が提案されてきた.本研究では,出力の2値画像を評価するのに合理的と思われる数学的基準を設定して,その基準の下で最適な解を求める問題の本質的な計算複雑度を解析した.その結果,妥当な仮定の下では効率よく解くアルゴリズムは存在しないという結論を得ることができた.この結果は理論計算機科学の国際会議でも発表し,高い評価を得た.また,本研究では理論と応用の融合を目指すために,従来から提案されている手法を詳しく調査し,かつそれらの手法をプログラムの形に実現することによって提案手法との比較を行った.さらに,この問題が計算幾何学におけるディスクレパンシーの問題と密接に関連していることを発見し,最悪の場合の性能を保証することができるアルゴリズムを開発した.これとは全く別の方向の手法としてグラフ理論において長年研究されてきたネットワークフローの技術が応用できることを発見し,巨大なネットワーク問題を解くことにより緩和した基準の下では最適な解を多項式時間で求めることができることを証明し,実際にプログラミングをして計算機実験を行った.
In this study we have formulated the problem of digital halftoning to convert a continuous-tone image into a binary image as a combinatorial problem and analyzed it inherent computational complexity under some reasonable mathematical criterion. We obtained a conclusion that there is no efficient algorithm for solving the problem. This result is presented in an international conference with high evaluation. To merge theory and practice we have investigated traditional studies and coded most of them for comparison with our new algorithm. We also found that this problem is closely related to the problem of discrepancy and developed an algorithm with its performance guaranteed. We also found a new algorithm for finding an optimal solution under somewhat relaxed criterion based on a network flow algorithm and made experiments on many image data. The results are quite promising.
研究課題/領域番号:10680344, 研究期間(年度):1998 - 2000
出典：「濃淡画像のハーフトーニングの最適化問題としての定式化と計算複雑度解析」研究成果報告書　課題番号10680344（KAKEN：科学研究費助成事業データベース（国立情報学研究所））（https://kaken.nii.ac.jp/ja/report/KAKENHI-PROJECT-10680344/106803442000kenkyu_seika_hokoku_gaiyo/）を加工して作成
DOI: 10.24517/00061988
Source: https://kanazawa-u.repo.nii.ac.jp/?action=repository_action_common_download&item_id=55713&item_no=1&attribute_id=26&file_no=1
https://kanazawa-u.repo.nii.ac.jp/?action=repository_action_common_download&item_id=55713&item_no=1&attribute_id=26&file_no=1
Access Restrictions: 限定公開
Rights (production): CC BY-NC-ND
Related Material: https://kaken.nii.ac.jp/search/?qm=90113133
https://kaken.nii.ac.jp/ja/grant/KAKENHI-PROJECT-10680344/
https://kaken.nii.ac.jp/ja/report/KAKENHI-PROJECT-10680344/106803442000kenkyu_seika_hokoku_gaiyo/
Data Provider (Database): 国立情報学研究所 : 学術機関リポジトリデータベース（IRDB）（機関リポジトリ）
https://irdb.nii.ac.jp
Original Data Provider (Database): 金沢大学 : 金沢大学学術情報リポジトリKURA