Research on data rounding based on discrete systems.

本研究基于图和超图的离散数学概念，对质量度量方面的模拟数据进行高质量的数字化（舍入）生成。这样的研究对于图像处理中的一个重要课题——数字半色调以及其他许多数字化应用都具有重要的应用价值。特别地，我们考虑了与超图相关的差异距离，并研究了与输入的差异距离最多为1的全局轮询空间。在全局舍入空间的组合结构的数学研究范畴中给出了最重要的产出。我们给出了一个猜想，对于连通图的最短路径度量生成的超图，其全局舍入空间确实是一个单纯形。对于路径图、环图、网格图、串并联图、一致k树图等图类，我们已经肯定地证明了这一猜想。作为副产物，我们设计了高效的多项式时间算法来枚举这类超图的全局舍入。我们还证明了计算几何中几个范围空间的类似性质。此外，我们还研究了由次次图定义的图上的几个性质/算法，因为我们的猜想似乎将通过使用图次理论在这样的图上得到证明。在此期间我们发表了10篇国际期刊论文和几篇会议论文。我们还研究了矩阵的子矩阵对应的超图的差值的下界/上界，这在数字半调的应用中是重要的。利用本文提出的方法对数字半调实例进行了实验。

The research pursue the generation of high-quality digitization (rounding) of analogue data with respect to quality measures based on discrete mathematical concept of graphs and hypergraphs.Such research has important applications to digital halftoning that is a major topic in image processing, as well as other many digitization applications.In particular, we consider discrepancy distances associated with hypergraphs and investigate on the space of global roundings that have the discrepancy distance at most one from the input.The most important outputs are given in the category of mathematical investigation of the combinatorial structure of the space of global roundings. We have given a conjecture that for the hypergraph generated from the shortest path metric of a connected graph, the space of global roundings is indeed a simplex. We have affirmatively proven this conjecture for several classes of graphs such as paths, cycles, mesh, series-parallel graphs, uniform k-trees, and so on.As byproducts, we have designed efficient polynomial-time algorithm for enumerating global roundings for such hypergraphs. Also we have proven a similar property for several range spaces considered in computational geometry.Moreover, we have investigated several properties/algorithms on graphs defined by minors, since it seems that our conjecture will be proven on such graphs by using graph-minor theory. We have published 10 international journal papers and several cnference papers during the period.We have also investigated lower/upper bounds of discrepancies of hypergraphs corresponding to submatrices of a matrix that are important in application to digital halftoning. We have done some experiments on digital halftoning instances by using our methodology.