Département d'informatique, Institut des systèmes informatiques et multimédias ISIM (Laboratoire de systèmes périphériques LSP)

Reproduction couleur par trames irrégulières et semi-régulières

Ostromoukhov, Victor ; Hersch, Roger-David (Dir.)

Thèse Ecole polytechnique fédérale de Lausanne EPFL : 1995 ; no 1330.

Add to personal list
    Summary
    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 halftone 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. Since CombiScreen enables the screen dot frequency or orientation to be chosen independently of the number of gray levels, it has proven to be specially effective when printing at resolutions between 150 to 600 dpi with ink jet printers and at resolutions between 300 and 1200 dpi with xerographic printers. 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 30° 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. Rotated dispersed-dot dither is based on the discrete one-to-one rotation of a Bayer dispersed-dot dither array. 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. This technique has successfully been applied to in-phase color reproduction on ink-jet printers as well as to black and white reproduction on laser printers.
    Résumé
    Les techniques de reproduction d'images noir et blanc ou couleur utilisées dans la plupart des imprimantes de bureau permettent de reproduire plus ou moins fidèlement des images, en mode tout-ou-rien. Cependant, ces techniques conventionnelles sont loin d'être parfaites: les unes souffrent d'un diapason dynamique trop limité, ce qui engendre un effet de bande ou d'autres structures visuellement gênantes; les autres produisent des effets de Moiré intolérables. Ce travail de thèse a été précédé par une analyse des problèmes liés à la nature répétitive des trames lors de la superposition de couches colorées et à la nature discrète des grilles de sortie des dispositifs de visualisation modernes. Cette analyse nous a permis d'identifier et de formuler un certain nombre de conditions à respecter, afin d'assurer une qualité de reproduction acceptable. Après avoir étudié l'état de l'art, nous avons décidé de mener notre recherche dans les directions suivantes: (1) méthode de reproduction d'images par trame pseudo-aléatoire regroupée, (2) technique combinée de génération de points de trame (CombiScreen), (3) méthode de reproduction en demi-ton par rotation discrète bijective d'une trame à points dispersés, et (4) méthode de reproduction en demi-ton par rotation discrète bijective d'une trame à points groupés. La méthode de reproduction d'images par trame pseudo-aléatoire regroupée, se prête bien à la reproduction couleur à haute résolution. Les épreuves en quadrichromie que nous avons pu faire, montrent une qualité acceptable dans la fidélité de rendu de nuances des teintes; elles donnent une bonne impression générale; il n'y pas d'effet de Moiré, ni d'autres artefacts visuels forts, sur les images obtenues. Par rapport à la plupart des implémentations commerciales existantes, notre méthode offre un contrôle accru sur la forme et la dispersion des éléments de trame. La méthode combinée de génération de points de trame (CombiScreen), permettant de minimiser l'effet de bandes, est utilisable dans la plupart des applications graphiques pour la reproduction d'images couleur ou noir et blanc. Cette technique permet d'obtenir des gradations de niveaux d'intensité extrêmement lisses, presque sans textures gênantes. Par ailleurs, elle permet d'utiliser des trames de base de différentes tailles, y compris de toutes petites trames, ce qui représente un avantage considérable. Les trames obtenues par la méthode CombiScreen peuvent également servir de base de départ pour d'autres méthodes de tramage, et, notamment, pour la méthode de reproduction en demi-ton par rotation discrète bijective. Un nouvel opérateur de rotation discrète bijective développé dans le cadre de cette recherche, permet d'appliquer des transformations proches des rotations, sur les ensembles discrets, et, notamment, sur les matrices de seuillage utilisées dans les algorithmes de reproduction. Trois types différents de rotations discrètes bijectives sont décrits en détail: la rotation discrète bijective par bandes rigides, la rotation discrète bijective de type a, b, b+1, et la rotation discrète bijective par cisaillements discrets successifs XYX. Grâce à cet opérateur, et en l'appliquant au plan des valeurs de seuil, on obtient plusieurs variantes de technique de reproduction en demi-ton par rotation discrète bijective, à points groupés ou dispersés. Les trames obtenues par ces techniques peuvent être appelées semi-régulières, car, tout en héritant d'un élément régulier des trames non-tournés, elles présentent une périodicité sur des périodes beaucoup plus grandes que celles de la trame de base. Les erreurs de dicrétisation, inhérentes à la rotation discrète bijective, perturbent la régularité initiale, sans la détruire complètement. La méthode de tramage régulier par matrice de seuillage dispersée tournée offre une qualité d'image améliorée. Les petits détails sont bien rendus et l'aspect visuel est assez plaisant. En outre, la courbe de reproduction obtenue par cette technique est nettement supérieure à celle de la méthode de Bayer, pour s'approcher des courbes de reproduction qui caractérisent les méthodes de reproduction par trame à points regroupés. Différentes méthodes de reproduction en demi-ton par rotation discrète bijective de la trame à points groupés permettent de satisfaire les critères de qualité de trames formulés au début de notre recherche, tels que l'élimination de l'effet de bande et la minimisation de l'effet de Moiré dans la reproduction en quadrichromie. Certains échantillons, produits avec cette méthode, atteignent une qualité visuelle considérable, proche de celle obtenue à résolution élevée.