Alternative method for synthesis of multidimensional low-discrepancy point sets
A.N. Kalouguine, N.A. Kalugin

Image Processing Systems Institute of the RAS,
Samara State Aerospace University

Full text of article: Russian language.

Modern approaches to solving the problems of the photorealistic image synthesis are based on use of the quasi-Monte Carlo methods. Effectiveness of these methods is based on the properties of the multidimensional point sets. The existing synthesis methods generate the low-discrepancy multidimensional point sets with the discrepancy growing as the number of dimensions of the used space grows. In the paper the authors suggest an alternative synthesis method that is based on use of canonical number systems. It is shown, that the suggested approach allows in certain sense to get over the ‘curse of dimensionality’.

Key words:
photorealistic image synthesis, low-discrepancy point sets, canonical number systems.


  1. Ermakov S. M. The Monte-Carlo method and associated issues // S. M. Ermakov. - Moscow, 1971 (in Russian)).
  2. Sobol, I. M. Numerical Monte-Carlo methods / I. M. Sobol - Moscow, 1973 (in Russian).
  3. Metropolis, N., Ulam, S. The Monte Carlo Method, J. Amer. statistical assoc. 1949 44 № 247 335—341.
  4. Knut. D. Semi-numerical algorithms / D. Knut. - The Art of Computer Programming. Vol. 2. — 3rd edition — Moscow: Williams Publishing, 2007. – Pp. 832.
  5. Rubinstein, R.Y. Simulation and the Monte Carlo Method (second edition) / R. Y. Rubinstein, D.P. Kroese. - New York: John Wiley & Sons, 2007.
  6. Niederreiter, H. Random Number Generation and Quasi-Monte Carlo Methods / H. Niederreiter. - SIAM, Philadelphia, 1992.
  7. Tezuka, Sh. Financial Applications of Monte Carlo and Quasi-Monte Carlo methods / Shu Tezuka // Random and Quasi-Random Point Sets, P. Hellekalek, G. Larcher, Eds, Lecture notes in statistics, 138. - Springer, 1998.
  8. Keller, A. Myths of Computer Graphics / A. Keller // H. Niederreiter and D. Talay, eds. Monte Carlo and Quasi-Monte Carlo Methods 2004, pp. 217-243. - Springer, 2006.
  9. Drmota, D. Sequences, Discrepancies and Applications / D. Drmota, R. F. Tichy // Lecture Notes in Mathematics, vol 1651. - Berlin: Springer, 1998.
  10. Faure, H. Discrepancy and diaphony of digital (0,1)-sequences in prime base/ H. Faure // Acta Arith, 117, pp. 125–148, 2005.
  11. Ninomiya, S. Constructing a new class of low-discrepancy sequences by using the -adic transformation/ S. Ninomiya // Mathematics and Computers in Simulation, Vol. 47, 2, pp. 403 – 418. – Elsevier, 1998. 
  12. Kuipers, L. Uniform Distribution of Sequences /  L. Kuipers, H. Niederreiter. Translated from English.  Ed. by S. M. Ermakov. – Moscow: Nauka Publishers, Fizmatlit, 1985 – 408 Pp.
  13. Random and Quasi-Random Point Sets / P. Hellekalek, G. Larcher, Eds // Lecture notes in statistics, 138. - Springer, 1998.
  14. Kátai, I. Canonical number systems in imaginary quadratic fields / I. Kátai, B. Kovács // Acta Mathematica Academiae Scientarium Hungaricae. 37 (1-3), 1981,  pp. 159-164.
  15. Kátai, I. Generalized Number Systems in Euclidean Spaces / I. Kátai // Mathematical and Computer Modeling, 38, 2003, pp. 883-892.
  16. Kovács, A.  Generalized binary number systems / A. Kovács // Annales Univ. Sci. Budapest, Sect. Comp. 20, 2001, pp. 195-206.
  17. Kovács,  A. On number expansions in lattices / A. Kovács // Proc. 5th Internation Conference on Applied Informatics. - Eger, Hungary, 2001.
  18. Kovács, B. Canonical number systems in algebraic number fields / B. Kovács // Acta Math. Acad. Sci. Hungar., 37 (1981), pp. 405-407.
  19. Akiyama, S. New criteria for canonical number systems / S. Akiyama, H. Rao// Acta Arithm., 111 (2004), pp. 5—25.
  20. Kovács, B. Canonical number systems in algebraic number fields / B. Kovács // Acta Math. Acad. Sci. Hungar., 37 (1981), 405-407.
  21. Kalugin, А. N.,  An LSFR-CNS generator: analytic study of distribution uniformity / A. N. Kalugin // Computer Optics. Vol. 31. – Samara, Image Processing Systems Institute of the RAS, 2007 (in Russian).
  22. Kalugin, А. N. Development and study of multidimensional pseudorandom vector generators using data representation in algebraic field / А. N. Kalugin. Thesis for Candidate Degree in Physics and Mathematics. Manuscript (in Russian).
  23. Chernov, V.M.  Fast uniform distribution of sequences for fractal sets / V. M. Chernov // Proceedings of International Conference on Computer Vision and Graphics, 2004, September 22-24, 2004, Warsaw, Poland, Computational IMAGING AND VISION SERIES. - Kluwer Academic Press.

© 2009, ИСОИ РАН
Россия, 443001, Самара, ул. Молодогвардейская, 151; электронная почта: ; тел: +7 (846) 332-56-22, факс: +7 (846 2) 332-56-20