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 [Paper, 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.
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, 2012, pp. 63--76.
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, to appear, 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 Jan 1 2012 by Victor Ostromoukhov
