Shao Chin Sung
所属 青山学院大学 理工学部 経営システム工学科 職種 教授
|標題||Distributing Distinct Inegers Uniformly over a Square Matrix with Application to Digital Halftoning|
|掲載誌名||Journal HERMIS - International Journal of Computer Mathematics and its Application|
|著者・共著者||T. Asano, S. Choe, S. Kashima, Y. Kikuchi, *S.C. Sung|
|概要||This paper considers how to distribute n2 integers between 0 to n2-1 as uniformly as possible over an n × n square matrix. We introduce a discrepancy-based measure to evaluate the uniformity. More precisely, we take a sum of matrix elements over every k × k contiguous submatrix and define the discrepancy of the matrix as the matrix as the largest difference among those sums. It is known that if n and k are both even integers then we can construct zero-discrepancy matrices. In this paper we present a scheme for achieving a new discrepancy bound 2n when n is odd and k is 2. This is an improvement from the previous bound 4n. We borrow basic ideas behind orthogonal Latin squares and semi-magic squares. An n-ary number system also plays an improtant part.
This problem is closely related to digital halftoning. Low discrepancy matrices would impprove the quality of commonly used ordered dither algorithm.