Quad-Optimized Low-Discrepancy Sequences
Abstract. The convergence of Monte Carlo integration is given by the uniformity of samples as well as the regularity of the integrand. Despite much effort dedicated to producing excellent, extremely uniform, sampling patterns, the Sobol' sampler remains unchallenged in production rendering systems. This is not only due to its reasonable quality, but also because it allows for integration in (almost) arbitrary dimension, with arbitrary sample count, while actually producing sequences thus allowing for progressive rendering, with fast sample generation and small memory footprint. We improve over Sobol' sequences in terms of sample uniformity in consecutive 2-d and 4-d projections, while providing similar practical benefits -- sequences, high dimensionality, speed and compactness. We base our contribution on a base-3 Sobol' construction, involving a search over irreducible polynomials and generator matrices, that produce (1, 4)-sequences or (2,4)-sequences in all consecutive quadruplets of dimensions, and (0, 2)-sequence in all consecutive pairs of dimensions. We provide these polynomials and matrices that may be used as a replacement of Joe & Kuo's widely used ones, with computational overhead, for moderate-dimensional problems.
Citation: Victor Ostromoukhov, Nicolas Bonneel, David Coeurjolly, Jean-Claude Iehl, Quad-Optimized Low-Discrepancy Sequences, ACM SIGGRAPH 2024 Conference Papers, Denver, CO, USA, July 2024.
On-line documents: PDF article Supplementary material source code (C++) ACM Digital Library
Example-Based Sampling with Diffusion Models
Abstract. Much effort has been put into developing samplers with specific properties, such as producing blue noise, low-discrepancy, lattice or Poisson disk samples. These samplers can be slow if they rely on optimization processes, may rely on a wide range of numerical methods, are not always differentiable. The success of recent diffusion models for image generation suggests that these models could be appropriate for learning how to generate point sets from examples. However, their convolutional nature makes these methods impractical for dealing with scattered data such as point sets. We propose a generic way to produce 2-d point sets imitating existing samplers from observed point sets using a diffusion model. We address the problem of convolutional layers by leveraging neighborhood information from an optimal transport matching to a uniform grid, that allows us to benefit from fast convolutions on grids, and to support the example-based learning of non-uniform sampling patterns. We demonstrate how the differentiability of our approach can be used to optimize point sets to enforce properties.
Citation: Bastien Doignies, Nicolas Bonneel, David Coeurjolly, Julie Digne, Lois Paulin, Jean-Claude Iehl, Victor Ostromoukhov, Example-Based Sampling with Diffusion Models, ACM SIGGRAPH-Asia, December, 2023.
On-line documents: PDF article Supplementary material
Generator Matrices by Solving Integer Linear Programs
Abstract. In quasi-Monte Carlo methods, generating high-dimensional low discrep- ancy sequences by generator matrices is a popular and efficient approach. Histori- cally, constructing or finding such generator matrices has been a hard problem. In particular, it is challenging to take advantage of the intrinsic structure of a given numerical problem to design samplers of low discrepancy in certain subsets of di- mensions. To address this issue, we devise a greedy algorithm allowing us to translate desired net properties into linear constraints on the generator matrix entries. Solv- ing the resulting integer linear program yields generator matrices that satisfy the desired net properties. We demonstrate that our method finds generator matrices in challenging settings, offering low discrepancy sequences beyond the limitations of classic constructions.
Citation: Lois Paulin, David Coeurjolly, Jean-Claude Iehl, Nicolas Bonneel, Victor Ostromoukhov, Alexander Keller, Generator Matrices by Solving Integer Linear Programs, in Monte-Carlo and Quasi-Monte Carlo Methods 2022, Springer-Verlag, 2023.
On-line documents: PDF article
MatBuilder: Mastering Sampling Uniformity Over Projections
Abstract. Many applications ranging from quasi-Monte Carlo integration over op- timal control to neural networks benefit from high-dimensional, highly uniform samples. In the case of computer graphics, and more particularly in rendering, despite the need for uniformity, several sub-problems expose a low-dimensional structure. In this context, mastering sampling uniformity over projections while preserving high-dimensional uniformity has been intrinsically challenging. This difficulty may explain the relatively small num- ber of mathematical constructions for such samplers. We propose a novel approach by showing that uniformity constraints can be expressed as an inte- ger linear program that results in a sampler with the desired properties. As it turns out, complex constraints are easy to describe by means of stratification and sequence properties of digital nets. Formalized using generator matrix determinants, our new MatBuilder software solves the set of constraints by iterating the linear integer program solver in a greedy fashion to compute a problem-specific set of generator matrices that can be used as a drop-in replacement in the popular digital net samplers. The samplers created by MatBuilder achieve the uniformity of classic low discrepancy sequences. More importantly, we demonstrate the benefit of the unprecedented versa- tility of our constraint approach with respect to low-dimensional problem structure for several applications.
Citation: Lois Paulin, David Coeurjolly, Jean-Claude Iehl, Nicolas Bonneel, Alexander Keller, Victor Ostromoukhov, MatBuilder: Mastering Sampling Uniformity Over Projections, ACM SIGGRAPH 2022, ACM Trans. Graph. 41(4), pp. 1:1--1:13, 2022.
On-line documents: Complete article, Supplementary material, Source code, Demo, BibTex
Cascaded Sobol' Sampling
Abstract. Rendering quality is largely influenced by the samplers used in Monte Carlo integration. Important factors include sample uniformity (e.g., low discrepancy) in the high-dimensional integration domain, sample uniformity in lower-dimensional projections, and lack of dominant structures that could result in aliasing artifacts. A widely used and successful construction is the Sobol' sequence that guarantees good high-dimensional uniformity and consequently results in faster convergence of quasi-Monte Carlo integration. We show that this sequence exhibits low uniformity and dominant structures in low-dimensional projections. These structures impair quality in the context of rendering, as they precisely occur in the 2-dimensional projections used for sampling light sources, reflectance functions, or the camera lens or sensor. We propose a new cascaded construction, which, despite dropping the sequential aspect of Sobol' samples, produces point sets exhibiting provably perfect dyadic partitioning (and therefore, excellent uniformity) in consecutive 2-dimensional projections, while preserving good high-dimensional uniformity. By optimizing the initialization parameters and performing Owen scrambling at finer levels of binary representations, we further improve over Sobol's integration convergence rate. Our method does not incur any overhead as compared to the generation of the Sobol' sequence, is compatible with Owen scrambling and can be used in rendering applications.
Citation: Lois Paulin, David Coeurjolly, Jean-Claude Iehl, Nicolas Bonneel, Alexander Keller, Victor Ostromoukhov, Cascaded Sobol' Sampling, ACM SIGGRAPH-Asia 2021, ACM Trans. Graph. 40(6), pp. 274:1--274:13, 2021.
On-line documents: Complete article, Supplementary material, Source code, Demo, BibTex
Sliced Optimal Transport Sampling
Abstract. In this paper, we introduce a numerical technique to generate sample distributions in arbitrary dimension for improved accuracy of Monte Carlo integration. We point out that optimal transport offers theoretical bounds on Monte Carlo integration error, and that the recently-introduced numerical framework of sliced optimal transport (SOT) allows us to formulate a novel and efficient approach to generating well-distributed high-dimensional pointsets. The resulting sliced optimal transport sampling, solely involving repeated 1D solves, is particularly simple and efficient for the common case of a uniform density over a d-dimensional ball. We also construct a volume-preserving map from a d-ball to a d-cube (generalizing the Shirley-Chiu mapping to arbitrary dimensions) to offer fast SOT sampling over d-cubes. We provide ample numerical evidence of the improvement in Monte Carlo integration accuracy that SOT sampling brings compared to existing QMC techniques, and derive a projective variant for rendering which rivals, and at times outperforms, current sampling strategies using low-discrepancy sequences or optimized samples.
Citation: Lois Paulin, Nicolas Bonneel, David Coeurjolly, Jean-Claude Iehl, Antoine Webanck, Mathieu Desbrun, Victor Ostromoukhov, Sliced Optimal Transport Sampling, ACM SIGGRAPH 2020, ACM Trans. Graph. 39(4), pp. 99:1--99:17, 2020.
On-line documents: Complete article, Supplementary material, Source code, Demo, BibTex
Blue-noise sampling for human retinal cone spatial distribution modeling
Abstract. This paper proposes a novelmethod formodeling retinal cone distribution in humans. It is based on Blue-noise sampling algorithms being strongly related with themosaic sampling performed by cone photoreceptors in the human retina. Here we present themethod together with a series of examples of various real retinal patches. The same samples have also been created with alternative algorithms and compared with plots of the center of the inner segments of cone photoreceptors fromimaged retinas. Results are evaluated with different distancemeasure used in the !eld, like nearest-neighbor analysis and pair correlation function. The proposedmethod can effectively describe features of a human retinal cone distribution by allowing to create samples similar to the available data. For this reason, we believe that the proposed algorithmmay be a promising solutionwhenmodeling local patches of retina.
Citation: Matteo Paolo Lanaro, Helene Perrier, David Coeurjolly, Victor Ostromoukhov, Alessandro Rizzi, Blue-noise sampling for human retinal cone spatial distribution modeling, Journal of Physics Communications, Vol. 4 (2020), pp. 1--12.
On-line documents: Complete article (PDF)
On Multiple Virtues of Blue Noise Sampling
Abstract. Blue noise sampling distributes samples evenly and isotropically. For a long time, this technique has been used for distribution of elementary graphical marks in stippling, digital halftoning and various NPR applications. In this talk, we shall see other virtues of blue noise sampling for rendering in the context of Monte Carlo Integration. Based on SIGGRAPH 2015 paper [PSC+15], we demonstrate that the variance in Monte Carlo Integration can be expressed in closed form as the integral of the product of power spectra of (1) the integrand and (2) the distribution of samples. This fundamental for- mulation leads to a large number of theoretical and practical conclusions that we shall discuss. We shall also explore a few recent realizations that combine blue-noise properties with low discrepancy.
Citation: Alexander Keller, Per Christensen, Matt Pharr, Abdalla Ahmed, Victor Ostromoukhov, Iliyan Georgiev, My favorite Samples, SIGGRAPH 2019 Course, Los Angeles, USA.
On-line documents: Complete Course Notes
A Low-Discrepancy Sampler that Distributes Monte Carlo Errors as a Blue Noise in Screen Space
Abstract. We introduce a sampler that generates per-pixel samples achieving high visual quality thanks to two key properties related to the Monte Carlo errors that it produces. First, the sequence of each pixel is an Owen-scrambled Sobol sequence that has state-of-the-art convergence properties. The Monte Carlo errors have thus low magnitudes. Second, these errors are distributed as a blue noise in screen space. This makes them visually even more acceptable. Our sampler is lightweight and fast. We implement it with a small texture and two xor operations. Our supplemental material provides comparisons against previous work for different scenes and sample counts.
Citation: Eric Heitz, Laurent Belcour, Victor Ostromoukhov, David Coeurjolly, Jean-Claude Iehl, A Low-Discrepancy Sampler that Distributes Monte Carlo Errors as a Blue Noise in Screen Space, SIGGRAPH 2019 Talk.
On-line documents: Complete article, Supplementary material, Video, Code, BibTex
STAR: Analysis of Sample Correlations for Monte Carlo Rendering
Abstract. Modern physically based rendering techniques critically depend on approximating integrals of high dimensional functions representing radiant light energy. Monte Carlo based integrators are the choice for complex scenes and effects. These integrators work by sampling the integrand at sample point locations. The distribution of these sample points determines convergence rates and noise in the final renderings. The characteristics of such distributions can be uniquely represented in terms of correlations of sampling point locations. Hence, it is essential to study these correlations to understand and adapt sample distributions for low error in integral approximation. In this work, we aim at providing a comprehensive and accessible overview of the techniques developed over the last decades to analyze such correlations, relate them to error in integrators, and understand when and how to use existing sampling algorithms for effective rendering workflows.
Citation: Gurprit Singh, Cengiz Oztireli, Abdalla GM Ahmed, David Coeurjolly, Kartic Subr, Victor Ostromoukhov, Oliver Deussen, Ravi Ramamoorthi, Wojciech Jarosz. STAR: Analysis of Sample Correlations for Monte Carlo Rendering. Computer Graphics Forum (Proceedings of Eurographics), 38(2), 2019.
On-line documents: Complete article, Supplementary material, BibTex
Fourier Analysis of Correlated Monte Carlo Importance Sampling
Abstract. Fourier analysis is gaining popularity in image synthesis, as a tool for the analysis of error in Monte Carlo (MC) integration. Still, existing tools are only able to analyze convergence under simplifying assumptions (such as randomized shifts) which are not applied in practice during rendering. We reformulate the expressions for bias and variance of sampling-based integrators to unify non-uniform sample distributions (importance sampling) as well as correlations between samples while respecting finite sampling domains. Our unified formulation hints at fundamental limitations of Fourier-based tools in performing variance analysis for MC integration. This non-trivial exercise also provides exciting insight into the effects of importance sampling on the convergence rate of estimators because of the introduction or removal of discontinuities. Specifically, we demonstrate that the convergence of multiple importance sampling (MIS) is determined by the strategy that converges slowest. We propose two simple and practical approaches to limit the impact of discontinuities on the convergence rate of estimators: The first one involves mirroring the integrand to cancel out the effect of boundary discontinuities. This is followed by two novel mirror sampling techniques for MC estimation in this mirrored domain. The second approach improves direct illumination light sampling by smoothing out discontinuities within the domain at the cost of introducing a small amount of bias. Our approaches are simple, practical and can be easily incorporated in production renderers.
Citation: Gurprit Singh, Kartic Subr, David Coeurjolly, Victor Ostromoukhov, Wojciech Jarosz. Fourier Analysis of Correlated Monte Carlo Importance Sampling. Computer Graphics Forum, 37(4), 2019.
On-line documents: Complete article, Supplementary material, BibTex
Towards human retinal cones spatial distribution modeling
Abstract. Sampling is the reduction of a continuous signal into a discrete one, or the selection of a subset from a discrete set of signals. In the human retina, the mosaic of the cone photoreceptor cells samples the retinal optical projection of the scene, achieving the first neural coding of the spectral information from the light that enters the eye. To solve the sampling problem, the human retina has adopted an arrangement of photoreceptors that is neither perfectly regular nor perfectly random. Our results show that blue noise sampling can describe features of a human retinal cone distribution with a certain degree of similarity to the available data and can be efficiently used for modeling local patches of retina. Given the nature of blue noise algorithms, it should be possible to develop an adaptive sampling model that spans the whole retina. We hope this work can be useful to understand how spatial distribution affects the sampling of a retinal image, or the mechanisms underlying the development of this singular distribution of neuron cells and the implications it has on human vision.
Citation: Matteo Paolo Lanaro, Helene Perrier, David Coeurjolly, Victor Ostromoukhov, Alessandro Rizzi, Towards human retinal cones spatial distribution modeling, MODVIS Computational and Mathematical Models in Vision, May 2019.
On-line documents: Complete article
Sequences with Low-Discrepancy Blue-Noise 2-D Projections
Abstract. Distributions of samples play a very important role in rendering, affecting variance, bias and aliasing in Monte-Carlo and Quasi-Monte Carlo evaluation of the rendering equation. In this paper, we propose an original sampler which inherits many important features of classical low-discrepancy sequences (LDS): a high degree of uniformity of the achieved distribution of samples, computational efficiency and progressive sampling capability. At the same time, we purposely tailor our sampler in order to improve its spectral characteristics, which in turn play a crucial role in variance reduction, anti-aliasing and improving visual appearance of rendering. Our sampler can efficiently generate sequences of multidimensional points, whose power spectra approach so-called Blue-Noise (BN) spectral property while preserving low discrepancy (LD) in certain 2-D projections. In our tile-based approach, we perform permutations on subsets of the original Sobol LDS. In a large space of all possible permutations, we select those which better approach the target BN property, using pair-correlation statistics. We pre-calculate such ÒgoodÓ permutations for each possible Sobol pattern, and store them in a lookup table efficiently accessible in runtime. We provide a complete and rigorous proof that such permutations preserve dyadic partitioning and thus the LDS properties of the point set in 2-D projections. Our construction is computationally efficient, has a relatively low memory footprint and supports adaptive sampling. We validate our method by performing spectral/discrepancy/aliasing analysis of the achieved distributions, and provide variance analysis for several target integrands of theoretical and practical interest.
Citation: Helene Perrier, David Coeurjolly, Feng Xie, Matt Pharr, Pat Hanrahan, Victor Ostromoukhov, Sequences with Low-Discrepancy Blue-Noise 2-D Projections, Computer Graphics Forum (Proceedings of Eurographics 2018), 37(2), 2018, pp. 339Ð-353.
On-line documents: PDF article Supplementary material
Characterization of bijective digitized rotations on the hexagonal grid
Abstract. Digitized rotations on discrete spaces are usually defined as the composition of a Euclidean rotation and a rounding operator; they are in general not bijective. Nevertheless, it is well known that digitized rotations defined on the square grid are bijective for some specific angles. This infinite family of angles has been charac- terized by Nouvel and RŽmila and more recently by Roussillon and Coeurjolly. In this article, we characterize bijective digitized rotations on the hexagonal grid using arithmetical properties of the Eisenstein integers.
Citation: Kacper Pluta, Tristan Roussillon, David Coeurjolly, Pascal Romon, Yukiko Kenmochi, Victor Ostromoukhov, Characterization of bijective digitized rotations on the hexagonal grid, Journal of Mathematical Imaging and Vision, 60(5), 2018, pp. 707--716.
On-line documents: Complete article, Supplementary material, Companion Video, Source code, Demo, Slides, BibTex
Low-Discrepancy Blue Noise Sampling
Abstract. We present a novel technique that produces two-dimensional low-discrepancy (LD) blue noise point sets for sampling. Using one-dimensional binary van der Corput sequences, we construct two-dimensional LD point sets, and rearrange them to match a target spectral profile without loosing their low discrepancy. We store the rearrangement information in a compact lookup table that can be used to produce arbitrarily large point sets. We evaluate our technique and compare it to the state-of-the-art sampling approaches.
Citation: Abdalla Ahmed, Helene Perrier, David Coeurjolly, Victor Ostromoukhov, Jianwei Guo, Dongming Yan, Hui Huang, Oliver Deussen, Low-Discrepancy Blue Noise Sampling, SIGGRAPH-ASIA 2016, ACM Trans. Graph. 35(6), pp. 247:1--247:13.
On-line documents: Complete article, Supplementary material, Companion Video, Source code, Demo, Slides, BibTex
Variance Analysis for Monte Carlo Integration
Abstract. We propose a new spectral analysis of the variance in Monte Carlo integration, expressed in terms of the power spectra of the sampling pattern and the integrand involved. We build our framework in the Euclidean space using Fourier tools and on the sphere using spherical harmonics. We further provide a theoretical background that explains how our spherical framework can be extended to the hemispherical domain. We use our framework to estimate the variance convergence rate of different state-of-the-art sampling patterns in both the Euclidean and spherical domains, as the number of samples increases. Furthermore, we formulate design principles for constructing sampling methods that can be tailored according to available resources. We validate our theoretical framework by performing numerical integration over several integrands sampled using different sampling patterns.
Citation: Adrien Pilleboue, Gurprit Singh, David Coeurjolly, Michael Kazhdan, Victor Ostromoukhov, Variance Analysis for Monte Carlo Integration, SIGGRAPH 2015, ACM Trans. Graph. 34(4), pp. 124:1--124:14.
On-line documents: Complete article, Supplementary material, Companion Video, Source code, Slides, BibTex
Variance Analysis for Monte Carlo Integration: A Representation-Theoretic Perspective
Abstract. In this report, we revisit the work of Pilleboue et al. [2015], providing a representation-theoretic derivation of the closed-form expression for the expected value and variance in homogeneous Monte Carlo integration. We show that the results obtained for the variance estimation of Monte Carlo integration on the torus, the sphere, and Euclidean space can be formulated as specific instances of a more general theory. We review the related representation theory and show how it can be used to derive a closed-form solution.
Citation: Michael Kazhdan, Gurprit Singh, Adrien Pilleboue, David Coeurjolly, Victor Ostromoukhov, Variance Analysis for Monte Carlo Integration: A Representation-Theoretic Perspective, arXiv:1506.00021. On-line documents: Complete article
Extracting Microfacet-based BRDF Parameters from Arbitrary Materials with Power Iterations
Abstract. We introduce a novel fitting procedure that takes as input an arbitrary material, possibly anisotropic, and au- tomatically converts it to a microfacet BRDF. Our algorithm is based on the property that the distribution of microfacets may be retrieved by solving an eigenvector problem that is built solely from backscattering samples. We show that the eigenvector associated to the largest eigenvalue is always the only solution to this problem, and compute it using the power iteration method. This approach is straightforward to implement, much faster to compute, and considerably more robust than solutions based on nonlinear optimizations. In addition, we provide simple conversion procedures of our fits into both Beckmann and GGX roughness parameters, and discuss the ad- vantages of microfacet slope space to make our fits editable. We apply our method to measured materials from two large databases that include anisotropic materials, and demonstrate the benefits of spatially varying roughness on texture mapped geometric models.
Citation: Jonathan Dupuy, Eric Heitz, Jean-Claude Iehl, Pierre Poulin, Victor Ostromoukhov, Extracting Microfacet-based BRDF Parameters from Arbitrary Materials with Power Iterations, EGSR 2015, Computer Graphics Forum, 34(4), pp. 21-30. On-line documents: Complete article [PDF, 17.4 Mb] Supplemental material [zip, 67.1 Mb]
Fast Tile-Based Adaptive Sampling with User-Specified Fourier Spectra
Abstract. We introduce a novel tile based method for adaptive two-dimensional sampling with user-specified spectral properties. Our approach achieves several orders of magnitude speed improvement over current spectrum-controlled sampling methods through a deterministic, hierarchical construction of self-similar, equi-area tiles whose spatial distribution is free of spurious spectral peaks. A lookup table of sample points, computed offline using any existing procedure that optimizes point sets to shape their Fourier spectrum, is then used to populate the tiles. The result is a linear-time, adaptive, and high-quality sampling of arbitrary density functions that conforms to the desired spectral distribution.
Citation: Florent Wachtel, Adrien Pilleboue, David Coeurjolly, Katherine Breeden, Gurprit Singh, Gael Cathelin, Fernando de Goes, Mathieu Desbrun, Victor Ostromoukhov, Fast Tile-Based Adaptive Sampling with User-Specified Fourier Spectra, SIGGRAPH 2014, ACM Trans. Graph. 33(4), pp. 56:1--56:11. On-line documents: Complete article [PDF, 20.5 Mb] Supplemental material article [PDF, 10.7 Mb] Companion Video [High-Quality video, 63.2 Mb] BibTex, Source code, More examples
Linear Efficient Antialiased Displacement and Reflectance Mapping
Abstract. We present Linear Efficient Antialiased Displacement and Reflectance (LEADR) mapping, a reflectance filtering technique for displacement mapped surfaces. Similarly to LEAN mapping, it employs two mipmapped texture maps, which store the first two moments of the displacement gradients. During rendering, the projection of this data over a pixel is used to compute a noncentered anisotropic Beckmann distribution using only simple, linear filtering operations. The distribution is then injected in a new, physically based, rough surface microfacet BRDF model, that includes masking and shadowing effects for both diffuse and specular reflection under directional, point, and environment lighting. Furthermore, our method is compatible with animation and deformation, making it extremely general and flexible. Combined with an adaptive meshing scheme, LEADR mapping provides the very first seamless and hardware-accelerated multi-resolution representation for surfaces. In order to demonstrate its effectiveness, we render highly detailed production models in real time on a commodity GPU, with quality matching supersampled ground-truth images.
Citation: Jonathan Dupuy, Eric Heitz, Jean-Claude Iehl, Pierre Poulin, Fabrice Neyret, Victor Ostromoukhov, Linear Efficient Antialiased Displacement and Reflectance Mapping, SIGGRAPH-ASIA 2013, ACM Trans. Graph. 32(6), pp. 211:1--211:11. On-line documents: Complete article [Acrobat pdf file] Supplemental material article [Acrobat pdf file] Companion Video [High-Quality video1.m4v, 94.8 Mb] [High-Quality video2.m4v, 37.6 Mb]
Improving Robustness of Monte-Carlo Global Illumination with Directional Regularization
Abstract. Directional regularization offers great potential to improve the convergence rates of Monte-Carlo-based global illumination algorithms. In this paper, we show how it can be applied successfully by combining unbiased bidirectional strategies, photon mapping, and biased directional regularization.
Citation: Guillaume Bouchard, Jean-Claude Iehl, Victor Ostromoukhov, Pierre Poulin, Improving Robustness of Monte-Carlo Global Illumination with Directional Regularization, SIGGRAPH-ASIA 2013 briefs. ISBN: 978-1-4503-2629-2 doi:10.1145/2542355.2542383. pp. 22:1--22:4. On-line documents: Complete article [Acrobat pdf file]
Blue Noise through Optimal Transport
Abstract. We present a fast, scalable algorithm to generate high-quality blue noise point distributions of arbitrary density functions. At its core is a novel formulation of the recently-introduced concept of capacity-constrained Voronoi tessellation as an optimal transport problem. This insight leads to a continuous formulation able to enforce the capacity constraints exactly, unlike previous work. We exploit the variational nature of this formulation to design an efficient optimization technique of point distributions via constrained minimization in the space of power diagrams. Our mathematical, algorithmic, and practical contributions lead to high-quality blue noise point sets with improved spectral and spatial properties.
Citation: Fernando de Goes, Katherine Breeden, Victor Ostromoukhov, Mathieu Desbrun, Blue Noise through Optimal Transport, SIGGRAPH-ASIA 2012, ACM Trans. Graph. 31(6):171:1-171:10. On-line documents: Complete article, Supplemental Material, Source Code, point sets, etc.
Digital Halftones
Abstract. This chapter presents in details how halftoning algorithms are designed and can be implemented. It also presents several halftoning approaches, from the simplest and widely used to the latest improvements. There are two main types of digital halftoning approaches. The first one is amplitude modulation (AM) that clusters micro dots in halftone cells and the second is frequency modulation (FM) which disperses micro dots. Although three algorithmic classes exist to perform digital halftoning point algorithms, neighborhood algorithms, and iterative algorithms. Point algorithms are local processes that use a single original image pixel to decide whether a micro dot should receive ink or not. The majority of algorithms in this class uses a matrix based approach. Input pixel values are compared to threshold values stored into a matrix (an array element that represents an halftone cell). Each comparison is independent from the others, which makes the process highly parallelizable. While small details are lost during this process, it is robust to micro dots misregistration. The second class of digital halftoning approaches uses local neighborhood knowledge to compute the output image. A typical example is error diffusion. Error diffusion is a sequential process: it processes one micro dot after the other, propagating an error value to unprocessed pixels. This process naturally enhances image discontinuities and details, but is not adapted to parallelization. Original error diffusion methods. Improvements have been proposed to remove these artifacts. The last class is iterative algorithms. While point and neighborhood algorithms do not take into account the whole image during the halftoning process, iterative algorithms consider original and output images globally during the computation. The distribution of micro dots becomes a global iterative process. For instance, the halftoning process can be an optimization of micro dots positions regarding a given weight function. Iterative algorithms are generally costly: they take more time and memory than point and neighborhood algorithms, which limits their applications for printing. But resulting the halftones show very good distribution and can take into account complex model of printers and the human visual system.
Citation: David Vanderhaeghe, Victor Ostromoukhov, Digital Halftones, in Michael A. Kriss, Li Yang (eds), Handbook of Digital Imaging, John Wiley & Sons, 2013.
Pointillist video stylization based on particle tracing
Abstract. We present an algorithm that stylizes an input video into a painterly animation without user intervention. In particular, we focus on pointillist animation with stable temporal coherence. Temporal coherence is an important problem in non-photorealistic rendering for videos. To realize pointillist animation, the various characters of pointillism should be considered in painting process to maintain temporal coherence. For this, weused the particle video algorithm which is a new approach to long-range motion estimation in video. Based on this method, we introduce a method to control the density of particles considering the features of frames and importance maps. Finally, the propagation methods of stroke to minimize flickering effects of brush strokes are introduced.
Citation: SangHyun Seo, Victor Ostromoukhov, Pointillist video stylization based on particle tracing, Multimedia Tools and Applications, Springer US, 10.1007/s11042-013-1441-9, pp. 1--10, 2013.
Non-Photorealistic Shading and Hatching
Abstract. The Human visual system performs the task of reconstruction of 3D external world scenes from 2D retinal images. In this complex task, information about natural shading of the objects, which results from the interaction of light with the objects' surfaces, plays crucial role. In Marr's computational model of vision, shading facilitates the building of the primal sketch during the image-based processing phase as well as building the 2.5D sketch during the surface-based processing phase. Thus, shading figure among the most important visual cues. In depiction, which can be considered as inverse vision task, artificial shading does not necessarily mimic physical shading. Very often, artificial shading conveys also some stylistic or pure aesthetical information. Artificial shading may add to the depicted scenes more appropriate and stronger visual cues, thus helping to overcome the limitations of the media. Many skilled artists used such artificial shading in their traditional artwork by exploying various hatching techniques. In this section, we explore the spectrum of possibilities for artificial shading in computer-aided depiction. We describe some artistic shading and hatching techniques that have been proposed during the last 20 years in the field on NPR. We discuss the perspectives for future development of artificial shading in computer-aided depiction, adapted to emerging media.
Citation: Victor Ostromoukhov, Non-Photorealistic Shading and Hatching, in Paul Rosin, John Collomosse (eds), Image and Video-Based Artistic Stylization, Springer-Verlag, pp. 63--76, 2012.
Specular BSDF Approximation for Efficient Specular Scene Rendering
Abstract. We propose a simple and robust adaptive specular BSDF evaluation algorithm based of stochastic progressive photon mapping. This algorithm can handle scenes that are considered difficult for most of current simulation approaches which deal with mixed diffuse and specular objects. By contrast, our approach can handle highly specular scene such as car lamps and light guide. The proposed method is simple to implement, needs very small memory for data structures and the resulting image does not depend on parameters. The method can produce bias- and noise-free images. The contribution of this paper is in two folds. First, we propose a simple and straightforward method for estimation of light transport of highly specular scenes. Then, we demonstrate an efficient approximation of the exact method by a real-time GPU-based implementation. As with progressive photon mapping, the algorithm repeats two passes, the eye-pass and the photon-pass. The first pass traces rays from the observer through the scene and stores a hit-point on the first surface hit. This hit-point is associated with a search radius and the BSDF of the surface. On the second pass, photons are traced from the light sources through the scene and their energy is splatted at each hit-point. The contributed energy for each hit-point depends on its associated BSDF and gathering radius. At the end of each eye-pass the gathering radius of hit-points is reduced. This ensures that the error associated with the light density estimation associated with each hit-point will diminish and that it will converge to the correct value. In our method, the rendering starts with a near-diffuse glossy BSDF and, through passes, the glossiness is raised to converge to a highly glossy BSDF which will converge to a specular BSDF in the limit. This method behaves exactly as progressive photon mapping regarding convergence properties. The trade-off between initial bias and variance is controlled by initial gathering radius. The amount of variance that unbiased method gives on this kind of scene is replaced by initial bias which will converge to zero as more photons are used in the approximation. Because the method relies on storing the hit-points on the first intersected surface, we can do the gathering step in screen-space which perfectly fits on GPU device. If bias-free results are not needed, the algorithm becomes point of view-independent and therefore suitable for real-time visualization of scene with quality only limited by the amount of photons the GPU device can store.
Citation: G. Bouchard, J.-C. Iehl, V. Ostromoukhov, B. Péroche, S. Albin, R. Guenegou, Carmen Uson, Specular BSDF Approximation for Efficient Specular Scene Rendering, Proceedings of International Light Simulation Symposium, 2012.
L-system specification of knot-insertion rules for non-uniform B-spline subdivision
Abstract. Subdivision schemes are based on a hierarchy of knot grids in parameter space. A univariate grid hierarchy is regular if all knots are equidistant on each level, and irregular otherwise. We use L-systems to design a wide class of systematically described irregular grid hierarchies. Furthermore, we give sufficient conditions on the L-system which guarantee that the subdivision scheme, based on the non-uniform B-spline of degree d defined on the initial knot grid, is uniformly convergent. If n is the number of symbols in the alphabet of the L-system, this subdivision scheme is defined with a finite set of masks (at most n^(d+1)) which does not depend on the subdivision step. We provide an implementation of such schemes which is available as a worksheet for Sage software.
Citation: V. Nivoliers, C. Gerot, V. Ostromoukhov, N. F. Stewart, L-system specification of knot-insertion rules for non-uniform B-spline subdivision, Computer-Aided Geometric Design, 29 (2), pp. 150-161, 2012. On-line documents: Complete article [Acrobat pdf file]
Image Recoloring Using Linear Template Mapping
Abstract. We propose an artistic recoloring method that enhances the perception of complex scenes, while preserving the visual quality of the original image. Our algorithm employs the template which contains the information of color theme. The colors of the template are selected based on the Munsell color system and are designed on the a*b* chromaticity plane of the CIE L*a*b* color space. Template can be used to recolor the original image with simpler and more focused color contrasts. The proposed algorithm consists of the three steps. First, we calculate the regression line for the colors on the original image and the template. Then we calculate an interpolation between the two regression lines. This transformation is used to change the color distribution in the source image. Finally, the transformed color distribution is mapped from the chromatic a*b* plane to become the template.
Citation: S. Seo, Y. Park, V. Ostromoukhov, Image Recoloring Using Linear Template Mapping, Multimedia tools and applications, 64 (2), pp. 293-308, 2012.
Structure-Aware Error Diffusion
Abstract. We present an original error-diffusion method which produces visually pleasant halftone images while preserving fine details and visually identifiable structures present in the original images. Our method is conceptually simple and computationally efficient. The source image is analyzed, and its local frequency content is detected. The main component of the frequency content (main frequency, orientation and contrast) serve as lookup table indices to a pre-calculated database of modifications to a standard error diffusion. The modifications comprise threshold modulation and variation of error-diffusion coefficients. The whole system is calibrated in such a way that the produced halftone images are visually close to the original images (patches of constant intensity, patches containing sinusoidal waves of different frequencies/orientations/contrasts, as well as natural images of different origins). Our system produces images of visual quality comparable to that presented in [Pang et al. 2008], but much faster. When processing typical images of linear size of several hundreds of pixels, our error-diffusion system is two to three orders of magnitude faster than [Pang et al. 2008]. Thanks to its speed combined with high visual quality, our error-diffusion algorithm can be used in many practical applications which may require digital halftoning: printing, visualization, geometry processing, various sampling techniques, etc.
Citation: Jianghao Chang, Benoit Alain, Victor Ostromoukhov, Structure-Aware Error Diffusion, ACM Transactions on Graphics, Vol. 28, No. 5, pp. 162:1-162:8, 2009. (Proceedings of SIGGRAPH-ASIA 2009) On-line documents: Complete article [Acrobat pdf file]
Recent Progress in Improvement of Extreme Discrepancy and Star Discrepancy of One-dimensional Sequences
Abstract. In this communication, we report on recent progress in improvement of extreme discrepancy and star discrepancy of one-dimensional sequences. Namely, we present a permutation of "Babylonian" sequences in base 60, which improves the best known results for star discrepancy obtained by Henri Faure in 1981, and a permutation of sequences in base 84, which improves the best known results for extreme discrepancy obtained by Henri Faure in 1992. Our best result for star discrepancy in base 60 is 32209/(35400 log 60) \approx 0.222223 (Faure's best result in base 12 is 1919/(3454 log 12) \approx 0.223585); our best result for extreme discrepancy in base 84 is 130/(83 \log 84) \approx 0.353494 (Faure's best result in base 36 is 23/(35 log 6) \approx 0.366758).
Citation: Victor Ostromoukhov, Recent Progress in Improvement of Extreme Discrepancy and Star Discrepancy of One-dimensional Sequences, in Monte-Carlo and Quasi-Monte Carlo Methods 2008, pp. 561-572, Springer-Verlag, 2009. On-line documents: Complete article [Acrobat pdf file]
Efficient product sampling using hierarchical thresholding
Abstract. We present an efficient method for importance sampling the product of multiple functions. Our algorithm computes a quick approximation of the product on-the-fly, based on hierarchical representations of the local maxima and averages of the individual terms. Samples are generated by exploiting the hierarchical properties of many low-discrepancy sequences, and thresholded against the estimated product. We evaluate direct illumination by sampling the triple product of environment map lighting, surface reflectance, and a visibility function estimated per pixel. Our results show considerable noise reduction compared to existing state-of-the-art methods using only the product of lighting and BRDF.
Citation: Fabrice Rousselle, Petrik Clarberg, Luc Leblanc, Victor Ostromoukhov, Pierre Poulin, Efficient Product Sampling using Hierarchical Thresholding, The Visual Computer, vol. 24(5-7), pp. 465-474, 2008. On-line documents: Complete article [Acrobat pdf file]
Tile-Based Methods for Interactive Applications
Abstract. Many interactive applications could benefit from techniques that rely on tile-based methods, but the state of the art is scattered over several publications, and survey works are not available. This class provides a detailed overview of tile-based methods in computer graphics. It covers theoretical aspects, practical aspects (tiling algorithms), and applications (modeling, sampling, and rendering).
Citation: Ares Lagae, Chi-Wing Fu, Victor Ostromoukhov, Craig S. Kaplan, Johannes Kopf and Oliver Deussen, Tile-Based Methods for Interactive Applications. SIGGRAPH 2008 Class, Los Angeles, USA. On-line documents: Complete Course Notes [Acrobat pdf file, 120 Mb]
Polyomino-Based Digital Halftoning
Abstract. In this work, we present a new method for generating a threshold structure. This kind of structure can be advantageously used in various halftoning algorithms such as clustered-dot or dispersed-dot dithering, error diffusion with threshold modulation, etc. The proposed method is based on rectifiable polyominoes -- a non-periodic hierarchical structure, which tiles the Euclidean plane with no gaps. Each polyomino contains a fixed number of discrete threshold values. Thanks to its inherent non-periodic nature combined with off-line optimization of threshold values, our polyomino-based threshold structure shows blue-noise spectral properties. The halftone images produced with this threshold structure have high visual quality. Although the proposed method is general, and can be applied on any polyomino tiling, we consider one particular case: tiling with G-hexominoes. We compare our polyomino-based threshold structure with the best known state-of-the-art methods for generation threshold matrices, and conclude considerable improvement achieved with our method.
Citation: David Vanderhaeghe, Victor Ostromoukhov, Polyomino-Based Digital Halftoning, Proceedings of IADIS International Conference on Computer Graphics and Visualization, p.57-64, 2008. On-line documents: Complete Course Notes [Acrobat pdf file, 1 Mb]
Sampling with Polyominoes
Abstract. We present a new general-purpose method for fast hierarchical importance sampling with blue-noise properties. Our approach is based on self-similar tiling of the plane or the surface of a sphere with rectifiable polyominoes. Sampling points are associated with polyominoes, one point per polyomino. Each polyomino is recursively subdivided until the desired local density of samples is reached. A numerical code generated during the subdivision process is used for thresholding to accept or reject the sample. The exact position of the sampling point within the polyomino is determined according to a structural index, which indicates the polyomino's local neighborhood. The variety of structural indices and associated sampling point positions are computed during the off-line optimization process, and tabulated. Consequently, the sampling itself is extremely fast. The method allows both deterministic and pseudo-non-deterministic sampling. It can be successfully applied in a large variety of graphical applications, where fast sampling with good spectral and visual properties is required. The prime application is rendering.
Citation: Victor Ostromoukhov, Sampling with Polyominoes, Proceedings of ACM SIGGRAPH 2007, ACM Transactions on Graphics, 26(3), 2007, pp. 78-1--78-6. On-line documents: Complete article [Acrobat pdf file, 7.7 Mb] Companion Video [WMV, 15.9 Mb] Example code in C++
Motion Cues for Illustration of Skeletal Motion Capture Data
Abstract. There are many applications for which it is necessary to illustrate motion in a static image using visual cues which do not represent a physical entity in the scene, yet are widely understood to convey motion. For example, consider the task of illustrating the desired movements for exercising, dancing, or a given sport technique. Traditional artists have developed techniques to specify desired movements precisely (technical illustrators) and suggest motion (cartoonists) in an image. In this paper, we present an interactive system to synthesize a 2D image of an animated character by generating artist-inspired motion cues derived from 3D skeletal motion capture data. The primary cues include directed arrows, noise waves, and stroboscopic motion. First, the user decomposes the animation into short sequences containing individual motions which can be represented by visual cues. The system then allows the user to determine a suitable viewpoint for illustrating the movement, to select the proper level in the joint hierarchy, as well as to fine-tune various controls for the depiction of the cues themselves. While the system does provide adapted default values for each control, extracted from the motion capture data, it allows fine-tuning for greater expressiveness. Moreover, these cues are drawn in real time, and maintain a coherent display with changing viewpoints. We demonstrate the benefit of our interactive system on various motion capture sequences.
Citation: Simon Bouvier-Zappa, Victor Ostromoukhov, Pierre Poulin, Motion Cues for Non-Photorealistic Illustration of Skeletal Motion Capture Data, Proceedings of NPAR'2007, pp.133-140. On-line documents: Complete article [Acrobat pdf file] Companion Video [.avi, 22 Mb]
Fast Generation of Importance-sampled Point Sets with Associated Delaunay Triangulation
Abstract. In this paper, we propose a novel method to generate Delaunay-triangulated point sets from a given density function in 2D. In order to accomplish this, we employ a Penrose-tiling-based importance-sampling strategy, which not only provides a good sampling point pattern with a local blue-noise distribution, but also provides a balanced base geometric structure from which we can efficiently derive a Delaunay triangulation of the underlying point set. We observe linear execution time with respect to the number of points. There are many areas in computer graphics that can benefit from our fast triangulated point set generator. Typical applications include terrain rendering, 3D geometry processing, and image compression.
Citation: Charles Donohue, Victor Ostromoukhov, Fast Generation of Importance-sampled Point Sets with Associated Delaunay Triangulation, Proceedings of GRAPHICON'2007, pp.125-130. On-line documents: Complete article [Acrobat pdf file]
Building 2D Low-Discrepancy Sequences for Hierarchical Importance Sampling Using Dodecagonal Aperiodic Tiling
Abstract. This paper introduces a new method for building 2D low-discrepancy sequences and fast hierarchical importance sampling. Our approach is based on self-similar tiling of the plane with a set of aperiodic tiles having twelve-fold (dedecagonal) rotational symmetry. Sampling points of our low-discrepancy sequence are associated with tiles, one point per tiles. Each tile is recursively subdivided until the desired local density of samples is reached. A numerical code generated during the subdivision process is used for thresholding to accept or reject the sample. A special number system is specially tailored in order to allow linear numbering of the tiles. The resulting point distribution is more even, compared with that of popular Halton and Hammersley 2D low-discrepancy sequences. It can be successfully applied in a large variety of graphical applications, where fast sampling with good spectral and visual properties is required. Typical applications application are digital halftoning, rendering, geometry processing etc.
Citation: Victor Ostromoukhov, Building 2D Low-Discrepancy Sequences for Hierarchical Importance Sampling Using Dodecagonal Aperiodic Tiling, Proceedings of GRAPHICON'07, pp.139-142. On-line documents: Complete article [Acrobat pdf file]
Fast Hierarchical Importance Sampling with Blue Noise Properties
Abstract. This paper presents a novel method for efficiently generating a good sampling pattern given an importance density over a 2D domain. A Penrose tiling is hierarchically subdivided creating a sufficiently large number of sample points. These points are numbered using the Fibonacci number system, and these numbers are used to threshold the samples against the local value of the importance density. Pre-computed correction vectors, obtained using relaxation, are used to improve the spectral characteristics of the sampling pattern. The technique is deterministic and very fast; the sampling time grows linearly with the required number of samples. We illustrate our technique with importance-based environment mapping, but the technique is versatile enough to be used in a large variety of computer graphics applications, such as light transport calculations, digital halftoning, geometry processing, and various rendering techniques.
Citation: Victor Ostromoukhov, Charles Donohue, Pierre-Marc Jodoin, Fast Hierarchical Importance Sampling with Blue Noise Properties, Proceedings of ACM SIGGRAPH 2004, ACM Transactions on Graphics, 23(3), 2004, pp. 488-495. On-line documents: Complete article [Acrobat pdf file, 3.5 Mb] Companion Video [High-Quality MPEG-4 .mov, 50 Mb] [Low-Quality MPEG-4 .mov, 17 Mb] Lookup Tables [8x21, ASCII format] [13x21, ASCII format] [21x21, ASCII format] PowerPoint slides of the SIGGRAPH presentation [HTML] (Better quality with Internet Explorer) Example code in C++ and documentation
Non-Photorealistic Rendering of Hair for Animated Cartoons
Abstract. In cartoon drawings, hair is a strong vehicle of personality, emotions and style. In this paper, we present a powerful pro- cedure to imitate the appearance of cartoon-like hair with a small set of parameters. Our approach is inspired by an inking technique called feathering, which consists of draw- ing hatches along the hair orientation while emphasizing the highlights with ink stains. Our system provides a set of tools to facilitate the positioning of the generated hair over the hand-drawn hair while keeping an intuitive interface for the artists. We can also achieve hair animation by inter- polating various keyframes set by the user. Our approach has proven successful and flexible enough to adapt itself to different styles and is particularly well-suited for traditional animators.
Citation: Martin Côté, Pierre-Marc Jodoin, Charles Donohue, Victor Ostromoukhov, Non-Photorealistic Rendering of Hair for Animated Cartoons, To appear in the Proceedings of GRAPHICON'04. On-line documents: Complete article [Acrobat pdf file, 3.7 Mb] Companion Video [High-Quality DIVX .avi, 8.7 Mb]
Efficient Color For Efficient Web Applications
Abstract. Color management is important for any graphical application. It is even more important in the web world, where a typical application may run on a variety of hardware/software platforms. In addition, web graphical design becomes more and more sophisticated; it requires refined and powerful color management. In this presentation, we shall explore various approaches to color: color in science, art, psychology and technology. We shall show that efficient color engineering based on recent progress in psychophysics of human perception and on color science may bring considerable improvements in quality of web applications.
Citation: Victor Ostromoukhov, Efficient Color For Efficient Web Applications. Invited talk at 8th International Conference on 3D Web Technology, March 9 - 12, 2003, Saint Malo, France. On-line documents: PowerPoint slides [HTML] (Better quality with Internet Explorer)
Halftoning Over a Hexagonal Grid
Abstract. In this contribution, we present an optimal halftoning algorithm that uniformly distributes pixels over a hexagonal grid. This method is based on a slightly modified error-diffusion approach presented at SIGGRAPH 2001. Our algorithm's parameters are optimized using a simplex downhill search method together with a blue noise based cost function. We thus present a mathematical basis needed to perform spectral and spatial calculations on a hexagonal grid. The proposed algorithm can be used in a wide variety of printing and visualization tasks. We introduce an application where our error-diffusion technique can be directly used to produce clustered screen cells.
Citation: Pierre-Marc Jodoin and Victor Ostromoukhov, Halftoning Over a Hexagonal Grid, SPIE Vol. 5008, pp. 443-454, 2003. On-line documents: Complete article [Acrobat pdf file, 1 Mb]
Perceptual and Artistic Principles for Effective Computer Depiction
Abstract. This course presents connections between human visual perception and the art of picture production. Findings from perceptual and cognitive sciences are used to explore pictorial techniques used by artists as they address the challenges raised by the depiction of three-dimensional scenes on a flat media. The course introduces perceptual explanations for a variety of artistic styles. Finally, we present mechanisms that can make an image more effective, and demonstrate the adaptation of these mechanisms to computer graphics. The course is intended for both artists and scientists. Although it offers some practical insights, it is intended more as an in-breadth overview.
Citation: Frédo Durand, Maneesh Agrawala, Bruce Gooch, Victoria Interrante, Victor Ostromoukhov, and Denis Zorin, Perceptual and Artistic Principles for Effective Computer Depiction, Course Notes for SIGGRAPH 2002, San Antonio, Texas, July 2002, ISBN 1-58113-518-1. On-line documents: Complete Course Notes [Acrobat pdf file, 65 Mb] Separate slides can be found here
Hatching by Example: a Statistical Approach
Abstract. We present a new approach to synthetic (computer-aided) drawing with patches of strokes. Grouped strokes convey the local intensity level that is desired in drawing. The key point of our approach is learning by example: the system does not know a priori the distribution of the strokes. Instead, by analyzing a sample (training) patch of strokes, our system is able to synthesize freely an arbitrary sequence of strokes that ``looks like'' the given sample. Strokes are considered as parametrical curves represented by a vector of random variables following a Markovian distribution. Our method is based on Shannon's N-gram approach and is a direct extension of Efros's texture synthesis models [Efros99]. Nevertheless, one major difference between our method and traditional texture synthesis is the use of such curves as a basic element instead of pixels. We define a statistical metric for comparison between different patches containing various layouts of strokes. We hope that our method performs a first step towards capturing a very difficult notion of style in drawing -- hatching style in our case. We illustrate our method by varied examples, ranging from typical hatching in traditional drawing to highly heterogeneous sets of strokes.
Citation: Pierre-Marc Jodoin, Emric Epstein, Martin Granger-Piché and Victor Ostromoukhov, Hatching by Example: a Statistical Approach, To appear in Non-Photorealistic Animation and Rendering 2002 (NPAR '02), Annecy, France, June 3-5, 2002. On-line documents: Complete article [Acrobat pdf file, 350 Kb]
Error-Diffusion with Blue-Noise Properties for Midtones
Abstract. In this contribution, a new error-diffusion algorithm is presented, which is specially suited for intensity levels close to 0.5. The algorithm is based on the variable-coefficient approach presented at SIGGRAPH 2001 [OST01]. The main difference with respect to the latter consists of the objective function that is used in the optimization process. We consider visual artifacts to be anomalies (holes or extra black pixels) in an almost regular structure such as a chessboard. Our goal is to achieve "blue-noise" spectral characteristics in the distribution of such anomalies. Special attention is paid to the shape of the anomalies, in order to avoid very common artifacts. The algorithm produces fairly good results for visualization on displays where the dot gain of individual pixels is not large.
Citation: Pierre-Marc Jodoin and Victor Ostromoukhov, Error-Diffusion with Blue-Noise Properties for Midtones, SPIE Vol. 4663, pp. 293-301, 2002. On-line documents: Complete article [Acrobat pdf file, 350 Kb]
Techniques de rendu non-photoréaliste
Abstract. Depuis quelques années, l'infographie s'intéresse de plus en plus aux techniques de rendu non-photoréaliste (NPR) directement ou indirectement inspirées par les arts graphiques traditionnels. Ces nouvelles techniques élargissent considérablement le champ d'action traditionnel des techniques de synthèse d'images. Certaines techniques NPR permettent de visualiser des arrangements volumiques extrêmement sophistiqués, même si aucune vue de caméra virtuelle n'est capable de rendre un tel objet. D'autres techniques NPR rendent les représentations d'objets synthétiques plus jolies, plus expressives, plus laconiques - autant de facteurs qui d'emblée justifient la démarche non-photoréaliste. Dans ce chapitre, nous analysons quelques techniques connues dans l'infographie non-photoréaliste. Nous nous efforcons de comprendre les raisons d'être de chacune, les moyens techniques spécifiques qu'elles emploient.
Citation: Victor Ostromoukhov, Techniques de rendu non-photoréaliste (NPR), in François X. Sillion (ed.) Synthèse d'images géographiques, pp. 217-250, Editions Hermes Science, 2002. ISBN 2-7462-0450-9. On-line documents: Complete article [Acrobat pdf file, 3.1 Mb]
Decoupling Strokes and High-Level Attributes for Interactive Traditional Drawing
Abstract. We present an interactive drawing system, that allows the user to draw with a variety of traditional styles using an input image as a reference for semi-automatic tonal modeling. It shifts many tedious technical aspect to the computer side, while providing the user with freedom on the creative and aesthetic side. The user has low-level control on stroke placement, and high-level control on the tone, smudging and amount of detail. The drawing is rendered in real-time. The basic component is a thresholding model of strokes that can model a large class of styles (e.g. pencil, charcoal, engraving). It provides a controllable simulation of the variation of pencil pressure or stroke thickness traditionally used for tonal modeling. We introduce a novel fast equilibration approach for the resulting thresholding structure. The user can specify smudging, and controls the amount of detail for each part of the drawing.
Citation: Frédo Durand, Victor Ostromoukhov, Mathieu Miller, François Duranleau, and Julie Dorsey. Decoupling Strokes and High-Level Attributes for Interactive Traditional Drawing. Proceedings of Eurographics Rendering Workshop'01, in S.J. Gortler, K. Myszkowski (eds.), Rendeing Rechniques 2001, Springer Computer Science, pp. 71-82, 2001. On-line documents: Complete article [Acrobat pdf file, 3.3 Mb] A charcoal sample [1200x1200 JPEG 0.37 Mb] [2400x2400 JPEG 1.1 Mb] A sanguine sample [512x768 JPEG 0.15 Mb] [2550x3300 JPEG 1.6 Mb] A dry point sample [1000x1500 JPEG 0.5 Mb] [2000x3000 TIF 0.45 Mb]
A Simple and Efficient Error-Diffusion Algorithm
Abstract. In this contribution, we introduce a new error-diffusion scheme that produces higher quality results. The algorithm is faster than the universally used Floyd-Steinberg algorithm, while maintaining its original simplicity. The efficiency of our algorithm is based on a deliberately restricted choice of the distribution coefficients. Its pleasing nearly artifact-free behavior is due to the off-line minimization process applied to the basic algorithm's parameters (distribution coefficients). This minimization brings the Fourier spectra of the selected key intensity levels as close as possible to the corresponding "blue noise" spectra. The continuity of the algorithm's behavior across the full range of intensity levels is achieved thanks to smooth interpolation between the distribution coefficients corresponding to key levels. This algorithm is applicable in a wide range of computer graphics applications, where a color quantization algorithm with good visual properties is needed.
Citation: Victor Ostromoukhov. A Simple and Efficient Error-Diffusion Algorithm. In Proceedings of SIGGRAPH 2001, in ACM Computer Graphics, Annual Conference Series, pp. 567-572, 2001.
On-line documents: Complete article [Acrobat pdf file, 0.9 Mb] Download C sample code [varcoeffED.tar]
Optimal Halftoning for Network-Based Imaging
Abstract. We introduce a multiple depth progressive representation for network-based still and moving images. A simple quantization algorithm associated with this representation provides optimal image quality. By optimum, we mean the best possible visual quality for a given volume of information under real life constraints such as physical (network load, connection speed), psychological (viewer's expectation and patience), or legal constraints (access privileges). A special variant of the algorithm, multi-depth coherent error diffusion, addresses a specific problem of temporal coherence between frames in moving images. The output produced with our algorithm is visually pleasant because its Fourier spectrum is close to the "blue noise".
Citation: Victor Ostromoukhov. Optimal Halftoning for Network-Based Imaging. SPIE Vol. 4300, pp. 438-443, 2001. On-line documents: Complete article [Acrobat pdf file, .5 Mb]
Artistic Halftoning - Between Technology and Art
Abstract. Halftoning, a technique for producing of an illusion of continuous tones on bi-level devices is widely used in today's printing industry. Different variants of halftoning - clustered and dispersed dither, error-diffusion, blue-noise mask, stochastic clustered dithering - have been extensively studied during last thirty years. In this paper, we focus our attention on different artistic halftoning techniques developed at EPFL (Swiss Federal Institute of Technology, Lausanne, Switzerland). First, we explore Artistic Screening, a library-based approach, which has been presented at SIGGRAPH95. Contour-based generation of halftone screens effectively provides a new layer of information. We show how this layer of information can be used to convey artistic and cultural elements related to the content of the reproduced images. Artistic Screening is basically black-and-white technique. Multicolor and Artistic Dithering, presented at SIGGRAPH99, extends it to multiple colors. This technique permits to print with non-standard colors such as opaque or semi-opaque inks, using traditional or artistic screens of arbitrary complexity. Finally, we draw a way of extension of traditional dithering to purely artistic domain: Digital Facial Engraving presented at SIGGRAPH99. We illustrate the introduced technique by a set of black/white and color engravings.
Citation: (Invited Paper) Victor Ostromoukhov. Artistic Halftoning - Between Technology and Art. SPIE Vol. 3963, p. 489-509, 2000. On-line documents: Complete article [Acrobat pdf file, 16 Mb]
Digital Facial Engraving
Abstract. This contribution introduces the basic techniques for digital facial engraving, which imitates traditional copperplate engraving. Inspired by traditional techniques, we first establish a set of basic rules thanks to which separate engraving layers are built on the top of the original photo. Separate layers are merged according to simple merging rules and according to range shift/scale masks specially introduced for this purpose. We illustrate the introduced technique by a set of black/white and color engravings, showing different features such as engraving-specific image enhancements, mixing different regular engraving lines with mezzotint, irregular perturbations of engraving lines etc. We introduce the notion of engraving style which comprises a set of separate engraving layers together with a set of associated range shift/scale masks. The engraving style helps to port the look and feel of one engraving to another. Once different libraries of pre-defined mappable engraving styles and an appropriate user interface are added to the basic system, producing a decent gravure starting from a simple digital photo will be a matter of seconds. The engraving technique described in this contribution opens new perspectives for digital art, adding unprecedented power and precision to the engraver's work.
Citation: Victor Ostromoukhov. Digital Facial Engraving, In Proceedings of SIGGRAPH'99, in Computer Graphics Proceedings, Annual Conference Series, pp. 417-424, 1999.
On-line documents: Complete article [Acrobat pdf file, 12 Mb] The SIGGRAPH'99 Proceedings back cover image [B/W 3840x5120 TIFF 1200dpi 1.1 Mb]
Multi-Color and Artistic Dithering
Abstract. A multi-color dithering algorithm is proposed, which converts a barycentric combination of color intensities into a multi-color non-overlapping surface coverage. Multi-color dithering is a generalization of standard bi-level dithering. Combined with tetrahedral color separation, multi-color dithering enables printing images made of a set of non-standard inks. In contrast to most previous color halftoning methods, multi-color dithering ensures by construction that the different selected basic colors are printed side by side. Multi-color dithering is applied to generate color images whose screen dots are made of artistic shapes (letters, symbols, ornaments, etc.). Two dither matrix postprocessing techniques are developed, one for enhancing the visibility of screen motives and one for the local equilibration of large dither matrices. The dither matrix equilibration process corrects disturbing local intensity variations by taking dot gain and the human visual system transfer function into account. Thanks to the combination of the presented techniques, high quality images can be produced, which incorporate at the micro level the desired artistic screens and at the macro level the full color image. Applications include designs for advertisements and posters as well as security printing. Multi-color dithering also offers new perspectives for printing with special inks, such as fluorescent and metallic inks.
Citation: Victor Ostromoukhov, Roger D. Hersch. Multi-Color and Artistic Dithering, In Proceedings of SIGGRAPH 99, in Computer Graphics Proceedings, Annual Conference Series, pp. 425-432, 1999.
On-line documents: Complete article [Acrobat pdf file, 5.5 Mb]
Stochastic Clustered-Dot Dithering
Abstract. A new technique for building stochastic clustered-dot screens is being proposed. A large dither matrix comprising thousands of stochastically laid out screen dots is constructed by first laying out the screen dot centers. Screen dot centers are obtained by placing discrete disks of a chosen radius at free cell locations when traversing the dither array cells according to either a discretely rotated Hilbert space-filling curve or a random space-filling curve. After Delauney triangulation of the screen dot centers, the maximal surface of each screen dot is computed and iso-inten- sity regions are created. This iso-intensity map is converted to an anti-aliased grayscale image, i.e. to an array of preliminary threshold values. These threshold values are renumbered to obtain the threshold values of the final dither threshold array. By changing the disk radius, the screen dot size can be adapted to the characteristics of particular printing devices. Larger screen dots may improve the tone reproduction of printers having important dot gain.
Citation: V. Ostromoukhov, R. D. Hersch. Stochastic Clustered-Dot Dithering. Journal of Electronic Imaging, Vol. 8, No. 4, pp. 439-445, 1999.
On-line documents: Complete article [Acrobat pdf file, 4.4 Mb]
Reproducing Color Images Using Custom Inks
Abstract. We investigate the general problem of reproducing color images on an offset press using custom inks in any combination and number. While this problem has been explored previously for the case of two inks, there are a number of new mathematical and algorithmic challenges that arise as the number of inks increases. These challenges include more complex gamut mapping strategies, more efficient ink selection strategies, and fast and numerically accurate methods for computing ink separations in situations that may be either over-or under-constrained. In addition, the demands of high-quality color printing require an accurate physical model of the colors that result from overprinting multiple inks using halftoning, including the effects of trapping, dot gain, and the interreflection of light between ink layers. In this paper, we explore these issues related to printing with multiple custom inks, and address them with new algorithms and physcial models. Finally, we present some printed examples demonstrating the promise of our methods.
Citation: Eric J. Stollnitz, Victor Ostromoukhov, and David Salesin. Reproducing Color Images Using Custom Inks, Proceedings of SIGGRAPH 98, in Computer Graphics Proceedings, Annual Conference Series, pp. 267-274, 1998.
On-line documents: Complete article[Acrobat pdf file, 336 Kb]
Mathematical Tools for Computer-Generated Ornamental Patterns
Abstract. This article presents mathematical tools for computer-generated ornamental patterns, with a particular attention payed to Islamic patterns. The article shows how, starting from a photo or a sketch of an ornamental figure, the designer analyzes its structure and produces the analytical representation of the pattern. This analytical representation in turn is used to produce a drawing which is integrated into a computer-generated virtual scene. The mathematical tools for analysis of ornamental patterns consist of a subset of tools usually used in the mathematical theory of tilings such as planar symmetry groups and Cayley diagrams. A simple and intuitive step-by-step guide is provided.
Citation: (Invited Paper) Victor Ostromoukhov. Mathematical Tools for Computer-Generated Ornamental Patterns, In Electronic Publishing, Artistic Imaging and Digital Typography, Lecture Notes in Computer Science 1375, Springer Verlag, pp. 193-223, 1998.
On-line documents: Complete article[Acrobat pdf file, 743 Kb]
Resolution or more colours Making the choice
Citation: (Invited Talk) Victor Ostromoukhov, Resolution or more colours Making the choice, Proceedings of the GIGA Information Group European Ink Jet and Thermal Printing Conference, Dusseldorf, 1998.
On-line documents: Complete article[Acrobat pdf file, 4.6 Mb]
An interface for the interactive design of artistic screens
Abstract. This work presents the concepts and the tools involved in the interactive design of artistic screens. The screen elements are derived from a small set of analytical contours provided by the screen designer. We present the requirements that these contours must satisfy in order to generate consistent screens. Software tools have been developed which provide automatic means for verifying and enforcing these constraints. They include a way of specifying the periodicity of the screen dot and a graphical interface offering a convenient way of specifying and tuning the growth of the screen dot.
Citation: N. Rudaz, R. D. Hersch, V. Ostromoukhov, An interface for the interactive design of artistic screens, In: Electronic Publishing, Artistic Imaging and Digital Typography, Lecture Notes in Computer Science 1375, Springer Verlag, pp. 1-10, 1998.
On-line documents: Complete article [Acrobat pdf file, 1 Mb]
Structure Artifact Free Multi-Level Error Diffusion Algorithm
Abstract. Error-diffusion is widely used to generate intensity levels between the primary levels of multi-level colour printing devices (ink-jet printers, electrophotographic printers). Standard error-diffusion algorithms produce structure artifacts at rational intensity levels such as 1/3, 1/2 and 2/3. The boundary between structure artifacts breaks the visual continuity in regions of low intensity gradients and generates undesirable false contours. These undesirable structure artifacts are also visible when error-diffusion is used to generate intermediate intensity levels between primary levels. In this contribution, we propose to remove these structure artifacts by introducing small discontinuities in the tone correction curve, thereby avoiding reproducing the intensity levels responsible for the generation of structure artifacts. The method can not be applied to bilevel printing, since the forbidden intensity regions responsible for the structure artifacts would be too large. In multi-level colour printing however, the forbidden intensity regions are small enough and do not produce any visible intensity breaks in varying intensity wedges.
Citation: V. Ostromoukhov, R.D. Hersch, Structure Artifact Free Multi-Level Error Diffusion Algorithm, International Symposium on Electronic Image Capture and Publishing, Zürich, Proceedings Europto Conf. Series, SPIE Vol. 3409, pp. 215-219, 1998.
On-line documents: Complete article [Acrobat pdf file, 512 Kb]
Specifying color differences in a linear color space
Abstract. This work presents a novel way of generating color differenc-es for synthesizing artistically screened color images. A sin-gle color is specified by interacting with the mouse alternately on a constant luminance plane and on a constant hue plane within the LEF color space (the orthogonal space formed by the RGB cube's black-white axis (L) and by its E and F chrominance axes). By interactively selecting a second color point, a color difference is specified. We present a method for extrapolating this color difference throughout all colors of the RGB cube so as to generate consistent color dif-ferences, i.e. smoothly varying similar color differences for different colors. The produced artistically screened color patches show that significant luminance differences always generate significant visually perceived differences, whereas significant hue and/or saturation differences do not always generate significant visually perceived differences.
Citation: N. Rudaz, R. D. Hersch, V. Ostromoukhov, Specifying color differences in a linear color space (LEF), In: Proceedings of the Fifth Color Imaging Conference: Color Science, Systems and Applications, Scottsdale, Scottsdale, 1997.
On-line documents: Complete article [Acrobat pdf file, 1.7 Mb]
Recent Progress in Digital Halftoning for Color Reproduction
Abstract. Due to the proliferation of low-cost color printers during the last few years, converting full-color images to halftoned bi-level separations remains an important issue. A halftoning technique should faithfully reproduce the original color image, while satisfying several quality criteria such as absence of visible artifacts and Moires, providing reliable color reproduction as well as good small detail and texture rendition. Digital halftoning techniques are not limited to classical methods, such as clustered-dot dithering, dispersed dot dithering and error-diffusion methods. In order to obtain the best results, recent algorithms combine the respective advantages of dithering and error diffusion methods. One of the most spectacular progress in color reproduction technology has been made in the domain of ink-jet printers, where microdrops are used to achieve a larger dynamic range without increasing the spatial resolution. Colour rendition techniques specially adapted for these new printing devices are presented. A further advance in printing technology consists of incoporating into the printer more than the traditional 4 process colors. Advanced color separation techniques are required in order to print multicolor images with more than the Cyan Magenta Yellow and Black process colors. One of these advanced techniques combining color separation and halftone generation is error-diffusion in color space. Finally, we give a brief overview of the colour calibration standard proposed by the International Colour Consortium.
Citation: R. D. Hersch, V. Ostromoukhov, Recent Progress in Digital Halftoning for Color Reproduction, In: Proceedings of the 7-th International Graphicon Conference on Computer Graphics and Visualization, Moscow, May 21-24, 1997.
On-line documents: Complete article [Acrobat pdf file, 1 Mb]
Dithering Algorithms for Variable Dot Size Printers
Abstract. Dither-based methods for the halftoning of images on multi-level printing devices such as multi-level inkjet printers are presented. Due to the relatively large size of single droplets, halftoning algorithms are still needed. However, since halftoning occurs between the basic levels attainable by printing one, two or sev-eral droplets at the same position, artefacts are less visible than in equal resolution bilevel printers. When dithering algorithms are used for the halftoning task, the dither threshold tiles should have oblique orientations so as to make the halftoning artifacts less visible. They should be designed so as to break up the inherent artifacts of variable dot size printers, such as for example contin-uous lines made up of elongated elliptic dots. The resulting vis-ual effects are shown by simulating the printed dots of a multi-level inkjet printer.
Citation: V. Ostromoukhov, P. Emmel, N. Rudaz, I. Amidror, R.D. Hersch, Dithering Algorithms for Variable Dot Size Printers, IEEE Signal Processing Society, 1996 Intl. Conf. on Image Processing, Proceedings, Vol. 1, pp. 553-556, 1996.
On-line documents: Complete article [Acrobat pdf file, 1 Mb]
Predicting the spectral behaviour of colour printers for transparent inks on transparent support
Abstract. A spectral colour prediction model is proposed and applied to an ink jet printer. We limit the field of investigation to transparent inks printed on a transparent substrate. The proposed method is based on the computation of the transmittance spectra of colour primaries applying Beer's law, and on the calculation of their respective surface coverage using a high resolution grid. The proposed prediction model requires measuring the transmittance spectra of the inks and approximating the density distribution function of a single printed dot of each ink. We hereby obtain accurate spectral predictions of colour patches, while the number of required sample measurements is reduced to a minimum.
Citation: P. Emmel, I. Amidror, V. Ostromoukhov, R.D. Hersch Predicting the spectral behaviour of colour printers for transparent inks on transparent support. IS&T/SID 96 Color Imaging Conference: Color Science, Systems and Applications, Proceedings, Scottsdale, Arizona, pp. 86-91, 1996.
On-line documents: Complete article [Acrobat pdf file, 96 Kb]
Multi-Level Colour Halftoning Algorithms
Abstract. Methods for the halftoning of images on multi-level printing devices such as multi-level inkjet printers are presented. Due to the relatively large size of single droplets, halftoning algorithms are still needed. However, since halftoning occurs between the basic levels attainable by printing one, two or several droplets at the same position, artefacts are less visible than in equal resolution bilevel printers. When dithering algorithms are used for the halftoning task, the dither threshold tiles should have oblique orientations so as to make the halftoning artifacts less visible. They should be designed so as to break up the inherent artifacts of variable dot size printers, such as for example continuous lines made up of elongated elliptic dots. Error-diffusion in colour space is also appropriate for multi-level halftoning. Visual artifacts can be reduced by introducing dot over dot colour inhibiting constraints.
Citation: V. Ostromoukhov, P. Emmel, N. Rudaz, I. Amidror, R.D. Hersch Multi-Level Colour Halftoning Algorithms. SPIE Vol. 2949, Imaging Sciences and Display Technologies, Symposium on Advanced Imaging and Network Technologies, p. 332-340, 1997. Reprinted in Recent Progress in Digitial Halftoning II (Reiner Eschbach, ed.) IS&T, pp.166-172, 1999.
On-line documents: Complete article [Acrobat pdf file, 2.1 Mb]
Anti-Counterfeiting Feature of Artistic Screening
Abstract. In a recent publication [ScreenArt95], a new image reproduction technique, Artistic Screening, was presented. It incorporates freely created artistic screen elements for generating halftones. Fixed prede fined dot contours associated with given intensity levels determine the screen dot shape's growing behav iour. Screen dot contours associated with each intensity level are obtained by interpolation between the fixed predefined dot contours. A user-defined mapping transforms screen elements from screen element definition space to screen element rendition space. This mapping can be tuned to produce various effects such as dilatations, contractions and non-linear deformations of the screen element grid. Although Artistic Screening has been designed mainly for performing the creation of graphic designs of high artistic quality, it also incorporates several important anti-counterfeiting features. For example, bank notes or other valuable printed matters produced with Artistic Screening may incorporate both full size and microscopic letters of varying shape into the image halftoning process.
Furthermore, Artistic Screening can be used for generating screen dots at varying frequencies and orien tations, which are well known for inducing strong moiré effects when scanned by a digital colour copier or a desktop scanner. Moiré effects due to scanning of frequency modulated dots and lines have been dis cussed by Spannenburg.
However, it is less known that frequency-modulated screen dots have at each screen element size a differ ent reproduction behaviour (dot gain). When trying to reproduce an original by analog means, such as a photocopier, the variations in dot gain induce strong intensity variations at the same original intensity lev els. In this paper, we present a method for compensating such variations for the target printer, on which the original security document is to be printed. Potential counterfeiters who would like to repro duce the original with a photocopying device may only be able to adjust the dot gain for the whole image and will therefore be unable to eliminate the undesired intensity variations produced by variable fre quency screen elements.
Citation: V. Ostromoukhov, N. Rudaz, I. Amidror, P. Emmel, R.D. Hersch Anti-Counterfeiting Feature of Artistic Screening. SPIE Vol. 2951 Holographic and Diffractive Techniques, pp. 126-133, 1996.
On-line documents: Complete article [Acrobat pdf file, 4.2 Mb]
Artistic Screening
Abstract. Artistic screening is a new image reproduction technique incorporating freely created artistic screen elements for generating halftones. Fixed predefined dot contours associated with given intensity levels determine the screen dot shape's growing behavior. Screen dot contours associated with each intensity level are obtained by inter-polation between the fixed predefined dot contours. A user-defined mapping transforms screen elements from screen element definition space to screen element rendition space. This mapping can be tuned to produce various effects such as dilatations, contractions and non-linear deformations of the screen element grid. Discrete screen elements associated with all desired intensity levels are obtained by rasterizing the interpolated screen dot shapes in the screen element rendition space. Since both the image to be reproduced and the screen shapes can be designed independently, the design freedom offered to artists is very great. The interaction between the image to be reproduced and the screen shapes enables the creation of graphic designs of high artistic quality. Artistic screening is particularly well suited for the reproduction of images on large posters. When looked at from a short distance, the poster's screening layer may deliver its own message. Furthermore, thanks to artistic screening, both full size and microscopic letters can be incorporated into the image reproduction process. In order to avoid counterfeiting, banknotes may comprise grayscale images with intensity levels produced by microletters of varying size and shape.
Citation: Victor Ostromoukhov, Roger D. Hersch. Artistic Screening, in Proceedings of SIGGRAPH'95, in Computer Graphics Proceedings, Annual Conference Series, pp. 219-228, 1995.
On-line documents: Complete article [Acrobat pdf file, 3.7 Mb] The SIGGRAPH'95 Proceedings front page image [B/W 4150x5308 TIFF 600pdi 2.5 Mb]
Reproduction couleur par trames irrégulières et semi-régulières. Ph.D. Thesis
Abstract. In the printing industry, one of the most common methods for reproducing halftone images using bilevel printing devices is clustered-dot ordered dithering. The images produced using this method are quite faithful to the original and are visually pleasing. Nevertheless, only rational angles are attainable with clustered-dot dithering, due to the discrete nature of the grids. This phenomenon can become detrimental in the case of four-color printing, when different screen angles and maybe even different screen frequencies are used for separate color planes, thus producing a so-called Moiré phenomenon. Another important drawback, the so-called banding or contouring effect, is related to the limited area of basic screen elements used in traditional dithering. In order to deal with these problems, we have developed, within the scope of our research, several new techniques for digital halftoning: (1) pseudo-random halftone screening, (2) a new method for generating clustered-dot halftone images having a number of reproducible gray or colour levels which is independent of the screen element size (CombiScreen), (3) rotated clustered-dot dithering, based on discrete one-to-one rotation, and (4) rotated dispersed-dot dither. A new method of pseudo-random halftone screening is described. It starts by obtaining the quasi-random distribution of tile centers according to some well-defined spectral characteristics. We then obtain the desired tesselation of the output device space by applying the Voronoi polygonization process. Then, an analytic black-dot curve is calculated according to the resampled input signal level and the area of each given tile. This analytic curve is scan-converted to obtain the blackened pixels. In the second approach, we associate threshold values to all pixels inside every tile according to some specially tailored analytic spot function. Then, the standard threshold comparison process is applied. Unlike known error-diffusion techniques, the pseudo-random half\-tone screening technique can be applied to a high resolution printing process. The characteristic screen element size can be properly chosen so as to ensure the best trade-off between the printing process constraints and the most precise printing. The described halftone algorithm seems to be appropriate for high-resolution color and black&white devices (above 1000 dpi).
A new method (CombiScreen) is proposed for generating clustered-dot halftone images on raster printing devices having a number of reproducible gray or colour levels which is independent of the screen element size. The dither tiles generated by this method may contain several screen elements having any rational orientation and size. Threshold values are distributed among the cells of the dither tile so as to produce a large range of gray values, while at the same time preserving the clustered-dot behavior of individual screen elements. When rendering images at smoothly increasing intensity levels, this new method generates few contouring effects and other visible artifacts. The method works equally well for quadratic, rectangular, parallelogram and hexagonally shaped screen elements. Resulting dither tiles are generally either of parallelogram or of hexagonal shape.
A new operator of discrete one-to-one rotation is described. It offers means previously unknown in the art for generating rotated screens which approximate irrational angles with high-precision, producing much less disturbing interferences and artifacts than other methods. Therefore, a carefully prepared dither tile incorporating screen elements with the desired period, initial orientation, and dither threshold values defining their screen dot shape growth behavior can be rotated by discrete one-to-one rotation and keep the desired screen element period, the number of cells per screen element and the threshold values associated with each screen element cell, thereby preserving the screen dot shape growth behavior of the original dither tile.
Several different discrete one-to-one rotation variants are described: a small angle rotation technique valid for a subset of rational rotation angles, a rigid band technique and a technique based on discrete shearing transformations. The high-quality of the so rotated dither tile is due to the fact that discrete one-to-one rotation preserves the exact number of elementary cells per screen element and their exact dither threshold values.
The described method provides a new range of solutions for obtaining high-quality digital angled halftone screens. High-quality solutions can be found for generating three digital angled halftone screens, each 30o apart from each other, as known from traditional photographic colour screening techniques. Further solutions minimizing Moiré effects may be obtained by halftone screens whose first order frequency component vectors sum up to zero. This new method has turned out to be particularly effective when printing with color ink jet printers at resolutions between 150 and 800 dpi as well as with xerographic printers at resolutions between 300 and 1200 dpi.
Citation: V. Ostromoukhov, Reproduction couleur par trames irrégulières et semi-régulières, Ph.D. Thesis No.1330, EPFL, Lausanne, Switzerland, 1995.
On-line documents: Complete Thesis (ATTENTION: In French!) [Acrobat pdf file, 7.6 Mb]
Halftoning by Rotating Non-Bayer Dispersed Dither Arrays
Abstract. We propose a new operator for creating rotated dither threshold arrays. This new discrete one-to-one rotation operator is briefly explained. We analyze its application to different dispersed-dot dither arrays such as hexagonal dispersed dither arrays and 3x3 matrix-based Bayer-expanded dither arrays and compare the results with the ones obtained by rotating standard Bayer dither arrays. We show that the rotation operator introduces new lower-frequency components which, for example in the case of rotated dispersed-dot Bayer dither, produces a slight clustering effect improving the tone reproduction behavior of the halftone patterns. In other cases, such as hexagonal dispersed dither, these new lower frequency components are responsible for strong interferences in the rotated halftone array. When applied to 3x3 matrix-based Bayer-expanded dither arrays, the rotation operator induces sequences of short horizontal and vertical patterns, which have a very good tone reproduction behavior in the dark tones. Besides their use in black and white printing, rotated dispersed-dot dither halftoning techniques have also been successfully applied to in-phase color reproduction on ink-jet printers.
Citation: V. Ostromoukhov, R.D. Hersch. Halftoning by Rotating Non-Bayer Dispersed Dither Arrays, Proceedings Conf. Human Vision, Visual Processing and Digital Display VI, SPIE Vol. 2411. pp. 180-197, 1995.
Reprinted in Selected Papers on Digitial Halftoning (Jan P. Allebach, ed.) SPIE Milestones Series #154, pp. 238-255, 1999.
On-line documents: Complete article [Acrobat pdf file, 4.4 Mb]
A Grid-Based Method for Predicting the Behaviour of Colour Printers
Abstract. A new grid-based method is proposed for predicting the behaviour of colour printers. The method takes into account the varying density of dots as well as the light diffusion in the paper by defining at different intensity levels different colorimetric values for the printed ink as well as for the paper white. Since the model integrates both the varying density of partly overlapping ink dots and the light diffusion in the underlying substrate, the obtained predictions are more accurate than those obtained with surface based colour prediction methods described in the literature.
Citation: P. Emmel, R.D. Hersch, V. Ostromoukhov, A Grid-Based Method for Predicting the Behaviour of Colour Printers. The third IS&T/SID Color Imaging Conference, Color Science, Systems and Applications, Scottsdale, Arizona, Proceedings, pp. 71-77, 1995. On-line documents: Complete article [Acrobat pdf file, 96 Kb]
Introduction à la génération d'images en demi-tons
Abstract. La plupart des dispositifs d'impression ne sont capables d'imprimer qu'en mode tout ou rien. Soit un point du dispositif de sortie est imprimé, soit il ne l'est pas. Malgré cette limitation, ces dispositifs sont capables de reproduire des images comportant des nuances de gris. La méthode utilisée consiste à produire l'illusion de niveaux de gris, alors qu'on imprime côte à côte des points noirs et blancs. L'illusion de niveaux de gris est obtenue par des éléments de trame regroupant un nombre fixe de points imprimables noirs ou blancs. Le pourcentage de points imprimables blancs dans un élément de trame donne son niveau d'intensité moyen.
Citation: R.D. Hersch, V. Ostromoukhov, Introduction à la génération d'images en demi-tons, Cahiers Gutenberg, Vol. 21, pp. 135-166, 1995.
On-line documents: Complete article [Acrobat pdf file, 1.3 Mb]
Rotated Dispersed Dither: a New Technique for Digital Halftoning
Abstract. Rotated dispersed-dot dither is proposed as a new dither technique for digital halftoning. It is based on the discrete one-to-one rotation of a Bayer dispersed-dot dither array. Discrete rotation has the effect of rotating and splitting a significant part of the frequency im-pulses present in Bayer's halftone arrays into many low-amplitude distributed impulses. The halftone patterns produced by the rotated dither method therefore incorporate fewer disturbing artifacts than the horizontal and vertical components present in most of Bayer's halftone patterns. In grayscale wedges produced by rotated dither, texture changes at consecutive gray levels are much smoother than in error diffusion or in Bayer's dispersed-dot dither methods, thereby avoiding contouring effects. Due to its semi-clustering behavior at mid-tones, rotated dispersed-dot dither exhibits an improved tone reproduction behavior on printers having a significant dot gain, while maintaining the high detail rendition capabilities of dispersed-dot halftoning algorithms. Besides their use in black and white printing, rotated dither halfton-ing techniques have also been successfully applied to in-phase color reproduction on ink-jet printers.
Citation: Victor Ostromoukhov, Roger D. Hersch, Isaac Amidror. Rotated Dispersed Dither: a New Technique for Digital Halftoning, in Proceedings of SIGGRAPH 94, in Computer Graphics Proceedings, Annual Conference Series, pp. 123-130, 1994.
On-line documents: Complete article [Acrobat pdf file, 704 Kb] Rotated matrix of size 80x80 [PGM ASCII format, 26 Kb]
Spectral Analysis and Minimisation of Moiré patterns in Colour Separation
Abstract. Undesired moiré patterns may appear in colour printing for various reasons. One of the most important reasons is interference between the superposed halftone screens of the different primary colours, due to an improper alignment of their frequencies or orientations. In this article we explain the superposition moiré phenomenon using a spectral model which is based on Fourier analysis. After examining the basic case of cosinusoidal grating superpositions we advance, step by step, through the cases of binary gratings, square grids and dot screens, and discuss the implications on moirés between halftone screens in colour separation. Then, based on these results, we focus on the moiré phenomenon from a different angle, the dynamic point of view: we introduce the moiré parameter space, and show how changes in the parameters of the superposed layers vary the moiré patterns in the superposition. This leads us to an algorithm for moiré minimization which provides stable moiré-free screen combinations for colour separation.
Citation: I. Amidror, R.D. Hersch, V. Ostromoukhov, Spectral Analysis and Minimisation of Moiré patterns in Colour Separation, Journal of Electronic Imaging, 3 (3), pp. 295-317, 1994.
Reprinted in Selected Papers on Digitial Halftoning (Jan P. Allebach, ed.) SPIE Milestones Series #154, pp. 207-229, 1999.
On-line documents: Complete article [Acrobat pdf file, 2.3 Mb]
Two approaches in scanner-printer calibration: colorimetric space-based vs. closed-loop
Abstract. The present paper studies two different table-based approaches for the calibration of electronic imaging systems. The first approach, which is the classical one, uses the device-independent CIE-XYZ colorimetric space as an intermediate standard space. Input and output devices such as scanners, displays and printers are calibrated separately with respect to the objective CIE-XYZ space. The calibration process requires establishing a 3-dimensional mapping between a scanner's device-dependent RGB space and a device-independent colorimetric space such as CIE-XYZ. Measured samples belonging to the calibration set are used for splitting the colorimetric space into Delaunay tetrahedrons. The second approach, the so-called closed loop approach, calibrates directly scanner-printer pairs, without any reference to an objective colorimetric space. It enables a 3-D mapping to be built between the scanner's RGB space and the printer's CMY space without requiring any colorimetric measurement. It offers very accurate calibrated output for input samples having the same characteristics (halftone dot, ink spectral reflectance) as the printed samples used for the calibration process. When the desktop scanners' RGB sensibilities are not a linear transform of the CIE x, y, z matching curves, an accurate calibration can only be made if input color patches are based on the same primary inks as the patches used for device calibration.
Citation: V. Ostromoukhov, R.D. Hersch, C. Péraire, P. Emmel, I. Amidror, Two approaches in scanner-printer calibration: colorimetric space-based vs. closed-loop, IS&T/SPIE 1994 International Symposium on Electronic Imaging: Science Technology, SPIE Vol. 2170, pp. 133-142, San Jose, 1994.
On-line documents: Complete article [Acrobat pdf file, 128 Kb]
Pseudo-Random Halftone Screening for Color and Black&White Printing
Abstract. The idea of using pseudo-random spatial structures in graphic arts (color and black&white rendering algorithms) was suggested by psychologists and biologists about ten years ago. They observed that some natural pseudo-random structures such as the spatial distribution of receptors in the human retina play an important part in the perceptual process. Our modelization of pseudo-random spatial structures resembles the retinal mosaic. It starts by obtaining the quasi-random distribution of tile centers according to some well-defined spectral characteristics. We then obtain the desired tesselation of the output device space by applying the Voronoi polygonization process. Two slightly different approaches to the output image computation are being explored. In the first approach, an analytic black-dot curve is calculated according to the resampled input signal level and the area of each given tile. This analytic curve is scan-converted to obtain the blackened pixels. In the second approach, we associate threshold values to all pixels inside every tile according to some specially tailored analytic spot function. Then, the standard threshold comparison process is applied. The quality of the obtained results is analysed using common techniques: the Fourier analysis and the human visual system model. The described halftone algorithm seems to be appropriate for high-resolution color and black&white devices (above 1000 dpi). For low- and medium-resolution devices some important limitations are discussed.
Citation: V. Ostromoukhov, Pseudo-Random Halftone Screening for Color and Black&White Printing. Proceedings of the 9th Congress on Advances in Non-Impact Printing Technologies, Yokohama, pp.579-581, 1993.
Reprinted in Recent Progress in Digitial Halftoning (Reiner Eschbach, ed.) IS&T, pp.130-134, 1994.
Reprinted in Selected Papers on Digitial Halftoning (Jan P. Allebach, ed.) SPIE Milestones Series #154, pp. 195-202, 1999.
On-line documents: Complete article [Acrobat pdf file, 416 Kb]
Chromaticity gamut enhancement by heptatone multi-color printing
Abstract. The present paper studies the chromaticity gamut of multi-color printing processes. Heptatone (7- color) printing ± the most promising variant of multi-color printing ± offers a significantly larger gamut than a conventional CMYK printing process, approaching CRT and film gamuts. The behavior of the process in the device-independent CIE-XYZ and CIE-L*u*v* colorimetric spaces is explored using the compound Neugebauer model developped for this purpose. A simple and straightforward Moire´-free separation process is proposed. The strong point of the proposed separation process is the fact that only 3 different screen layers are needed for any odd number of basic colors including black.
Citation: V. Ostromoukhov, Chromaticity gamut enhancement by heptatone multi-color printing, IS&T/SPIE 1993 International Symposium on Electronic Imaging: Science Technology, SPIE Vol. 1909., pp. 139-151, 1993.
On-line documents: Complete article [Acrobat pdf file, 864 Kb]
Hardware Acceleration of Halftoning
Citation: M.Morgan, R.D.Hersch, V. Ostromoukhov, Hardware Acceleration of Halftoning. Society for Information Display. Digest of Technical Papers. Vol.XXIV. pp. 151-154, 1993.
Hermite approximation for offset curve computation
Abstract. The present paper proposes a new method for calculating the G1-continuous offset curve to a cubic Bézier curve, based on the Hermite approximation technique. This method is improved by preliminary curvature estimation and is intended for use in cpu-time sensitive CAGD applications.
Citation: Victor Ostromoukhov. Hermite approximation for offset curve computation. Proceedings of the International Conference on Computer Graphics ICCG93, (eds. S.P. Mudur and S.N. Pattanaik), IFIP Transactions B: Graphics, Design and Visualisation, North-Holland, pp.189-196, 1993.
On-line documents: Complete article [Acrobat pdf file, 224 Kb]
Abstract. The PUNK font, initialy designed by D. Knuth for METAFONT, has been translated into PostScript. Thanks to the PostScript font machinery, this new font is more dynamic than the genuine one.
Citation: Jacques André and Victor Ostromoukhov, Punk: from METAFONT to PostScript, Cahiers GUTenberg, Vol. 4, pp. 23-48, 1989. On-line documents: Complete article [Acrobat pdf file, 677 Kb]
Issued patents
Last updated on May 1, 2019
