1,720,982 research outputs found
Studies on Realistic Solutions to Theoretically Hard Problems
Get PDF本研究では,従来アルゴリズム理論で重視されてきた漸近的解析の枠内では計算困難と思われてきた問題に対して積極的に取り組んできた.具体的には最適な網点の形状を設計する問題とクラスタリングに関する問題に取り組んだ.前者に対しては,計算幾何学において精力的に研究されてきたディスクレパンシの理論が適用できることに気がつき,従来の手法とは全く異なる解法を提案することができた.さらに,これをグラフ理論におけるマッチングの概念と結合することにより,さらに解の性能を向上させることに成功した.実験的にも良い結果が得られており,今後論文として発表する予定である.クラスタリングについては,特に画像データベースからの画像検索の問題に取り組み,従来の結果を凌駕する実験結果を得ることが出来た.これについても近いうちに論文として投稿する予定である.In this study we have been engaged in several problems which were thought to be computationally Hard within the traditional framework of asymptotic analysis popular in the theory of algorithms. More concretely, we have studied the problem of designing optimal dot patterns for printing and that of clustering. For the former problem, we have noticed that the discrepancy theory can be applied to the problem. The discrepancy theory has been rigorously studied and is full of important theoretical results. Combining it with the notion of matching in the graph theory, we have succeeded in improving the performance of the solutions obtained. Since we also had satisfactory experimental results, we intend to submit the result to some journal. For the problem of clustering, we have applied an algorithmic approach to image query system On image database with good experimental results that exceed results by traditional Approaches. We are planning to summarize the results in a paper to be submitted to some International journal in near future.研究課題/領域番号:10205207, 研究期間(年度):1998 - 2000出典：「理論的には計算困難な問題の現実的解法に関する研究」研究成果報告書 課題番号10205207
（KAKEN：科学研究費助成事業データベース（国立情報学研究所））
（https://kaken.nii.ac.jp/ja/report/KAKENHI-PROJECT-10205207/102052072001kenkyu_seika_hokoku_gaiyo/）を加工して作成金沢大学 / 北陸先端科学技術大学院大学research repor
幾つかの画像関連問題の計算複雑度の解析と効率的な解決法の提案
Get PDF研究課題/領域番号:16092209, 研究期間(年度):2004 - 2007出典：「幾つかの画像関連問題の計算複雑度の解析と効率的な解決法の提案」研究成果報告書 課題番号16092209
（KAKEN：科学研究費助成事業データベース（国立情報学研究所））
（https://kaken.nii.ac.jp/ja/grant/KAKENHI-PROJECT-16092209/）を加工して作成金沢大学 / 北陸先端科学技術大学院大学research repor
入力に依存した専用回路による問題解法の高速化の研究
Get PDF研究課題/領域番号:14658090, 研究期間(年度):2002 - 2004出典：「入力に依存した専用回路による問題解法の高速化の研究」研究成果報告書 課題番号14658090
（KAKEN：科学研究費助成事業データベース（国立情報学研究所））
（https://kaken.nii.ac.jp/ja/grant/KAKENHI-PROJECT-14658090/）を加工して作成金沢大学 / 北陸先端科学技術大学院大学research repor
Going Beyond Counting First Authors in Author Co-citation Analysis
Get PDFThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
A Study on Computational Complexity and Efficient Implementation of Region Segmentation Problem of an Image under Various criteria
Get PDF本研究では,画像認識の基礎となる領域分割についてアルゴリズム理論の立場から考察を行った.すなわち,様々な数学的基準に対して,その基準における最適解を求める問題がどの程度の計算手間を必要とするかを解析し,さらに多項式時間のアルゴリズムを得るためにはどのような制約条件を付加する必要があるかを考察した.特に,判別分析の基準に基づいて,画像を連結な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/）を加工して作成金沢大学 / 北陸先端科学技術大学院大学research repor
Development of a general method for detecting a specified family of curves in a digital image
Get PDF濃淡画像からエッジ部分が2値で検出された画像に含まれるすべての直線成分および曲線成分を抽出する問題は、パターン認識における基本問題として多くの研究者によって研究されてきた。特に、直線成分の抽出に関してはハフ変換の名前の下に多数の方法が提案されているが、検出すべき直線成分、曲線成分に対する厳密な定義が見当らないという問題点があった。本研究では、放物線や楕円と言った曲線族のディジタル像の定義から始めて、計算幾何学の技法を用いれば少ない記憶領域で従来より高速に、かつ定義の条件を満たすすべてのディジタル点集合を求めるアルゴリズムを構築し、さらに計算機実験を行なってその有効性を検証した。具体的には、双対変換とアレンジメントの概念を利用して、指定された曲線の成分を残らず検出できる性能が保障されたアルゴリズムを提案した。従来からも曲線成分抽出の方法は種々提案されているが曲線ごとに固有の方法が考案されていた。本研究の特色は、曲線族を指定するための代数は構造を明確にすることによって、曲線族の複雑度を自由パラメータと呼ばれる概念で定量化し、その上で可能な限り効率のよいアルゴリズムを提案したことである。研究成果については国内外の理論系の学会と実用重視の学会の双方で発表したが、実用面と基礎理論を結びつける研究として高い評価を受けた。
理論的な検討だけでなく実際的な面からの検討も行うために、実際の画像について計算機実験も行なった。その結果、実用的には直線・曲線成分に含まれない雑音成分をいかにして除去するかが重要であることが判明し、雑音成分除去の前処理として、各点を中心にある方向の領域に存在する黒点の個数を定数時間でカウントし、雑音かどうかを判定する処理方法を確立した。この結果については近い将来に報告する予定である。The problem of detecting all digital line components contained in a black-white image is one of the most fundamental problems in pattern recognition. In this study we have developed efficient algorithms for detecting all of digital line components. We also developed space-efficient algorithms for detecting all of digital curve components. This is the first linear-space algorithm for the purpose for detecting curve components and in addition the first to define a family of digital curves using least possible number of parameters. More concretely, key ideas are duality transform between points and lines and efficient search in an arrangment of lines. One advantage of the proposed algorithms to be distinguished from the existing ones is that they can detect all possible line and curve components satisfying the conditions without missing one. We also analyzed the computational complexity of the problem itself and algorithms to establish the optimality of the proposed algorithms. Experimental results show the practical usefullness and effectiveness of the proposed methods.研究課題/領域番号:06680334, 研究期間(年度):1994 - 1995出典：「ディジタル画像から指定された曲線成分を抽出する一般的な方法の開発」研究成果報告書 課題番号06680334
（KAKEN：科学研究費助成事業データベース（国立情報学研究所））
（https://kaken.nii.ac.jp/ja/report/KAKENHI-PROJECT-06680334/066803341995kenkyu_seika_hokoku_gaiyo/）を加工して作成金沢大学 / 大阪電気通信大学research repor
Solving Computationally Hard Problems Based on Fast Algorithms for Fixed-Parameter Problems
Get PDF本研究の目的は、最近の計算機環境の下で固定パラメータ問題を高速に解決するための方法論を確立することである。そのために、単なるプログラムテクニックとして解析に反映されなかった側面を数学的に厳密に評価し、従来の解析方法とは全く異なる立場から計算の効率評価を行うことであった。
今年度は、トライセクター曲線に関する研究に時間を割いた.平面上に与えられた2点に対する2等分線は容易に計算できるが,2点間に等距離の曲線を描くのは困難である.正確には,任意の精度で近似解を得ることはできるが,正確に曲線上の点を求めることは不可能(代数的でない)であることが予想される.本研究では,そのような曲線が常に存在し,ユニークに定まることを数学的にかつ構成的に証明した.それ以外にも様々な興味深い構造的な性質を明らかにした.この研究の成果は,5月に開かれた理論計算機科学では最高峰の国際会議であるSTOCにおいて発表すると共に,Advances in Mathematicsという数学ではトップクラスのジャーナルにも論文を発表した.非常に基本的な問題でありながら,これまでに全く類似の研究がなかったということはむしろ驚きである.
計算幾何学においてボロノイ図は重要な研究課題のひとつである.本研究では,従来のボロノイ図の概念を一般化して,三角形に関する評価尺度に基づいた様々なボロノイ図を定義したが,特に角度ボロノイ図に興味をもち,その構造と複雑さに関する研究を行った.具体的には,線分の集合が与えられたとき,どの線分に対して定義される視角が最も小さいかという関係で平面を分割したものである.この研究では,角度ボロノイ図が通常のボロノイ図と極めて異なる性質をもつことを証明し,さらに最小の視角を最大にする点を効率よく求めるためのアルゴリズムを示している.この結果にっいては,7月に開かれたボロノイ図に関する国際ワークショップにおいて報告した.現在は,そのジャーナルバージョンを執筆中であり,近い将来にジャーナル誌に投稿をする予定である.The purpose of this research is to establish methodology for solving fixed parameter problems in an efficient way under latest computer environment. For the purpose we mathematically evaluate some aspects of programming which has not been reflected to analysis as just simple programming techniques and then analyze computational performance from a completely different standpoint from the existing ones.
In this year we spent much time for the study of distance trisector curves. Given two points in the plane, it is easy to draw perpendicular bisector, but it is hard to draw two curves equidistant from each other. More exactly, we can approximate points on the curves at any precision, but it is impossible to compute their coordinates exactly without any error. In fact we conjecture that the curves are non-algebraic. In this research we proved that such curves exist and they are unique, mathematically in a constructive manner. We also found many interesting properties of the curves. The resu lts were presented at an international symposium STOC, one of the top conference in the world in this area and also published in a top mathematical journal, Advances in Mathematics. It is rather surprising that it is quite simple and fundamental problem while there is no study on the curves. We also applied the idea to Voronoi diagrams, which is one of the most important research topics in computational geometry. In this research we defined various Voronoi diagrams based on criteria on goodness of triangles by generalizing the traditional Voronoi diagrams. More concretely, given a set of line segments in the plane, an angular Voronoi diagram is a partition of the plane into regions by the relation on which line segment gives the smallest visual angle. We have shown that this Voronoi diagram has properties which are quite different from those of the exisiting ones. We also gave an efficient algorithm for finding a point that maximizes the smallest visual angle. The results were presented at an international symposium on Voronoi diagrams We are now preparing journal version of those papers to submit them to international journals.研究課題/領域番号:15300003, 研究期間(年度):2003 - 2006出典：「固定パラメータ問題に対する高速算法に基づく計算困難問題の解決」研究成果報告書 課題番号15300003
（KAKEN：科学研究費助成事業データベース（国立情報学研究所））
（https://kaken.nii.ac.jp/ja/report/KAKENHI-PROJECT-15300003/153000032006kenkyu_seika_hokoku_gaiyo/）を加工して作成金沢大学 / 北陸先端科学技術大学院大学research repor
A study on geometric transformation preserving grid points and its applications
Get PDFコンピュータの画面に代表されるようなグリッド平面上では、直線はグリッド点の系列として、塗りつぶし図形はグリッド点の集合として表現される。直線や2次曲線をいかにグリッド点の系列として表現するかについては多くの研究がなされているが、問題の計算複雑度に関する理論的な解析はあまりなされていないのが現状である。本研究の目的は、グリッド平面上に任意の閉図形が与えられたとき、その内部に含まれるグリッド点を効率よく列挙するアルゴリズムを開発することであった。
最初に、グリッド点を保存する幾何学的変換に基づいて効率のよいアルゴリズムを考案し、計算機実験を行なってその有効性を確認した。基本的なアイディアは、グリッド点をグリッド点に写す変換を用いて素朴な方法で効率よくグリッド点を列挙できる部分(密な部分)とグリッド点が疎な部分に分割するという操作を後者の部分が十分小さくなるまで繰り返すというものである。この繰り返し回数は与えられた図形のディメンジョンの対数をとったものになるから、効率のよい実行が可能になる訳である。また、この変換法をうまく用いて2変数の整数計画問題に対する効率のよいアルゴリズムも与えた。これについても計算機実験を行なった。計算機実験に用いたプログラムのリストの一部(主要部分のみ)は報告書に含めておいた。
さらに他方面への応用例として、画像のディジタル・ハーフトーニングの問題さらにはディジタル画像から直線や円のような基本図形の成分を検出する問題についても考察し、効率のよいアルゴリズムを得ることに成功した。これらの問題に対して従来から様々な方法が提案されているが、問題の計算複雑度が厳密に解析されたことがなかった。その意味で本研究は重要な一石を投じたものと思われる。In this research we have developed efficient algorithms for reporting all the grid points within a given convex polygon in optimal time and also applied the algorithm for two-dimensional integer programming. We have also implemented those algorithms using C language and evaluated their practical efficiencies.
The results were quite satisfactory. We further extended the similar idea to some other problems : digital halftoning of pictures of multiple brightness levels and that of detecting all possible digital components of a specified curve in a digital picture.研究課題/領域番号:04650331, 研究期間(年度):1992 - 1993出典：「グリッド点を保存する幾何学的変換とその応用に関する研究」研究成果報告書 課題番号04650331
（KAKEN：科学研究費助成事業データベース（国立情報学研究所））
（https://kaken.nii.ac.jp/ja/report/KAKENHI-PROJECT-04650331/046503311993kenkyu_seika_hokoku_gaiyo/）を加工して作成金沢大学 / 大阪電気通信大学research repor
Development of Geometric Clustering Algorithms and Applications to VLSI Design
Get PDF本研究では、最初に対毎に類似度が与えられたとき、距離が類似度に反比例するように対象を2次元の平面に写像する方法について考察し、主軸変換法がこの目的に適していることを確かめ、実際にプログラムを作成した。次に平面に与えられた多数の点に対して、最も一様に点が分布するようにこれらを直線上に写像する問題について考察し、従来の結果を非常に改善する結果を得た。
本研究では平面上分点集合を2分割する問題を主に考察したが、そのままの形で扱うよりも双対平面上で考えた方が見通しがよい。実際、点を直線に、直線を点に変換すると、点集合は直線の集合に変換されるが、同じ分割を与える直線に対応する点は直線で区切られた同じ小領域に属するので、小領域を全て調べれば全ての(直線による)分割を調べたことになる。そのためにそれらの小領域を順序よく訪問する算法が必要になるが、従来は効率のよいものがなかった。本研究で開発した算法は、直線の本数に比例する記憶量さえあれば小領域の個数に比例する時間で探索を終えることができるので非常に効率がよい。
本研究で開発された算法はVLSIの設計に応用することができる。実際、回路分割問題に適用した結果を論文の形にまとめ、近く投稿する予定である。この論文では、VLSIを構成するブロックとブロックを結ぶネットの集合が与えられたとき、ブロックの集合を2分割して2つの部分にまたがるネットの本数を最小にする問題について論じる。従来の方法はグラフ理論を用いていたが、いずれも定式化の段階ですでに問題を含んでいた。これに対して、本研究ではブロック間の接続度を計算した後、その情報に基づいて密接に連結されているブロックは近くに配置されるように写像を施す。その後で幾担学的変換法によって点を直線に変換し、トポロジカルウォ-クの算法を利用して最適な分割を求める。Grouping similar objects is called cluster analysis. There have been considered a lot of algorithms. When we formulate this problem as a problem in Graph Theory, it may often become NP-complete. Therefore, we rely on heuristic algorithms. In this research we first presented an algorithm for mapping objects into points in the plane so that similar objects are placed closely, based on Principal Coordinate Analysis. Then, applying Geometric Transform, points are mapped into lines. Using Topological Walk Algorithm developed in the research, we can examine all possible regions defined by those lines. This corresponds to examination of all possible partitions of those points in the dual plane. The idea was applied to Circuit Partitioning in VLSI design.研究課題/領域番号:01550295, 研究期間(年度):1989 - 1990出典：「幾何学的クラスタリング算法の開発とVLSI設計への応用」研究成果報告書 課題番号01550295
（KAKEN：科学研究費助成事業データベース（国立情報学研究所））
（https://kaken.nii.ac.jp/ja/report/KAKENHI-PROJECT-01550295/015502951990kenkyu_seika_hokoku_gaiyo/）を加工して作成金沢大学 / 大阪電気通信大学research repor
- …
