[go: up one dir, main page]

WO1999045697A1 - Creation de demi-tons avec des cartes etablies par des calculs preliminaires - Google Patents

Creation de demi-tons avec des cartes etablies par des calculs preliminaires Download PDF

Info

Publication number
WO1999045697A1
WO1999045697A1 PCT/SE1999/000282 SE9900282W WO9945697A1 WO 1999045697 A1 WO1999045697 A1 WO 1999045697A1 SE 9900282 W SE9900282 W SE 9900282W WO 9945697 A1 WO9945697 A1 WO 9945697A1
Authority
WO
WIPO (PCT)
Prior art keywords
maps
dots
halftoning
map
image
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Ceased
Application number
PCT/SE1999/000282
Other languages
English (en)
Inventor
Fredrik Nilsson
Björn KRUSE
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Forskarpatent I Linkoping AB
Original Assignee
Forskarpatent I Linkoping AB
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Forskarpatent I Linkoping AB filed Critical Forskarpatent I Linkoping AB
Priority to EP99908033A priority Critical patent/EP1066716A1/fr
Publication of WO1999045697A1 publication Critical patent/WO1999045697A1/fr
Anticipated expiration legal-status Critical
Ceased legal-status Critical Current

Links

Classifications

    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04N—PICTORIAL COMMUNICATION, e.g. TELEVISION
    • H04N1/00—Scanning, transmission or reproduction of documents or the like, e.g. facsimile transmission; Details thereof
    • H04N1/40—Picture signal circuits
    • H04N1/405—Halftoning, i.e. converting the picture signal of a continuous-tone original into a corresponding signal showing only two levels
    • H04N1/4051—Halftoning, i.e. converting the picture signal of a continuous-tone original into a corresponding signal showing only two levels producing a dispersed dots halftone pattern, the dots having substantially the same size

Definitions

  • Halftoning methods based on threshold matrices are very attractive in terms of speed. Moreover, full control over the patterns produced in tints is possible and thus certain less visually pleasant patterns can be avoided. For these methods, however, there is always a trade-off between the quality in the tints produced and the quality of smoothly varying shades. Thus, the principle of the threshold matrix approach does not allow for the highest possible quality in both. The reason for this is that the dot pattern produced for a certain tone value will be present in all tints of less intensity. A pattern at one intensity level will thus restrict the appearance of all other tint values. This means that if there is a certain criterion for optimization of a tint, for instance requiring that the dots are as dispersed as possible, this can not be fulfilled for all tint levels. This restriction is illustrated in Figure 1.
  • Figure 1 An illustration of threshold-matrix-based halftoning techniques.
  • a black micro 2 dot is placed at every image position where the value of the threshold matrix is greater than the image value.
  • the dots produced for one tint value will be present in all darker tint values. This is a severe restriction when designing the tints possible to produce with the matrix.
  • Figure 3a - 3c Examples from the generation of maps.
  • 3a) is a white noise image thresholded to get 20% minority pixels. The resulting pattern is used as the starting pattern.
  • the starting pattern is rearranged to get maximally dispersed dots. This map is stored in the halftoning volume.
  • 3c) extra dots have been added to the dot pattern in 3b) to get the initial map for the next level (25% level in the example). The pattern is rearranged before stored in the volume, 3d). Note that some of the dots in 3b) have been moved to obtain the pattern in 3d). This would not have been possible with a threshold-based-method.
  • FIG. 4a - 4c The test images halftoned with the Pre-Computed Maps method described in text.
  • the tints and ramps are in 100 dpi, the photograph in 150 dpi.
  • the halftoning volume used is optimized with isotropic Gaussian low pass filters.
  • the maps in the volume are of the order 64x64.
  • Figure 5 Some of the kernels used to compute maps with line like micro structures.
  • the kernels gradually change from a Gaussian low-pass filter for maps with fewer than 30% minority dots to a directional band-pass filter.
  • the size of the kernels are 9x9 but have been interpolated to 36x36 for illustration purposes
  • FIG. 6a - 6c The test image halftoned with the Pre-Computed Maps method.
  • the tints and ramps are in 100 dpi, the photograph in 150 dpi.
  • the halftoning volume which is used is optimized with directed Gaussian low pass filters for mid gray maps.
  • the maps in the 3 volume are of the order 64x64.
  • Figure 7 Some of the kernels used to compute maps with curved micro structures.
  • the kernels gradually change from a Gaussian low-pass filter for maps with fewer than 30% minority dots to an isotropic band-pass filter.
  • the size of the kernels are 9x9 but have been interpolated to 36x36 for the purpose of illustration.
  • FIG. 8a - 8c The test images are halftoned with the Pre-Computed Maps method.
  • the tints and ramps are printed in 100 dpi, the photograph in 150 dpi.
  • the halftoning volume is optimized with isotropic band-pass filters for mid gray tints.
  • the maps in the volume are of the order 64x64.
  • the proposed method uses one pre-computed halftoning map for each possible tone value in the image.
  • Each map is derived according to a specific optimization criterion and stored in a halftoning volume.
  • the maps contain only zeros and ones, representing the presence and absence of a halftone dot respectively.
  • the image value is used as an index into the volume.
  • the position in the chosen map is derived from to the image position in the same manner as for matrix-based-methods.
  • the value of the map at this position is then simply copied into the corresponding position in the resulting halftone. Thus, no comparison is necessary when halftoning.
  • Figure 2 illustrates halftoning with the Pre- Computed Maps (PreCoM) technique.
  • PreCoM Pre- Computed Maps
  • PreCoM is easily implemented in a truly parallel manner since no information from neighbouring pixels is required.
  • the technique requires more memory than threshold matrix methods. For instance, given the task of halftoning an image with 256 gray levels (8 bits), the PreCoM method requires 256 one-bit maps whereas a threshold-matrix-based method requires one eight-bits matrix. If the same matrix and map size is used, PreCoM thus requires 32 times as much memory. As an example, assuming a map size of 64x64 pixels, the storage of the halftoning volume will require 128 kilobytes compared with the 4 kilobytes for the threshold matrix. 4
  • the maps in the halftoning volume are derived individually in an iterative manner.
  • the principles of the computation process are shared by all maps. However, by assigning a specific optimization criterion to each map, all maps can be given a specific characteristic.
  • a variety of optimization criteria are possible, but for the production of visually pleasant halftones only some are of interest.
  • One such criterion is to force the dots in a map to be as dispersed as possible which will minimize disturbing patterns as well as graininess in the halftoned images.
  • maps optimized with this criterion will posses the desirable blue noise characteristics.
  • the suggested optimization algorithm is closely related to the void and cluster method presented in [Ulic93] .
  • the principle of the algorithm has also been used when deriving the Blue Noise Mask [YaPa94]. For the sake of completeness, the algorithm in its entirety is described below.
  • the computation of a map starts from any binary pattern with the appropriate ratio of white to black dots (ones and zeros), for instance a thresholded white noise image.
  • the idea of the algorithm is to rearrange the minority dots, i.e. black dots for bright tint values and white ones for dark values, until they are as dispersed as possible. This is done in a iterative manner by successively moving minority dots from the tightest clusters to the largest voids. By representing the minority dots with ones and the majority dots with zeros, the tightest cluster of minority dots is located by finding the maximum of the low-pass filtered dot pattern. The minority dot at the maximum is removed and the low-pass image is updated by a local deconvolution, i.e.
  • the low-pass kernel is subtracted from the low-pass image at that position.
  • the largest void is found by locating the minimum of the low- 5 pass image.
  • the previously removed dot is then placed at this location and the low-pass image is again updated, now by adding the kernel.
  • the process of rearranging minority dots continues until no further change occurs, i.e. the selected minority dot is placed at the very same location it was taken from.
  • the algorithm is straightforward, but there are several factors which must be taken into consideration in order to ensure that the resulting maps behaves well. The two most important of these are discussed below.
  • the characteristics of the low-pass kernel used in the algorithm has great influence on the final dot pattern. Its shape as well as its size is of importance and should be adapted to the current density level. For instance, in bright and dark maps, the distances between the minority dots will be large. Thus, a wide kernel should be used to avoid unevenly spread dots. On the other hand, for maps of around 50% coverage, dots will be placed next to each other. A kernel designed to control the local behaviour of the dot pattern is thus needed.
  • the iterative process described above is fairly time consuming. The time taken depends on the number of minority dots, the initial binary pattern, and the size of the kernel used for the optimization. If, however, the initial binary pattern is close to optimal, the computational cost is dramatically decreased. This is utilised in the correlation process described next. Besides, the computation is done off line and once and for all. The time required for generating the halftoning volume is thus of minor interest.
  • the strength of the PreCoM technique lies in the possibility of producing both near optimal tints and nice transitions between them. Without the correlation between adjacent maps, disturbing irregularities and discontinuities will be detectable at the transitions.
  • the proposed 6 method for the generation of the halftoning volume assigns an unique filter kernel to each map that is to be optimized. By changing the filter kernel gradually between adjacent maps, and by using the previously optimized map as the starting pattern to the next, maps that produce images with both desired properties can be derived.
  • the image material we have been working with has a dynamic range of 8 bits, i.e. 256 gray levels are possible. It is doubtful whether more levels are meaningful for a human observer, at least for images reproduced in print. Possibly, it may be the case that even fewer levels could be acceptable. However, until investigated further, the volumes will contain 256 pre- computed maps, one for each possible intensity level in an 8 bit image.
  • the number of minority dots that differs between two adjacent maps can be computed.
  • a fixed difference in dots between maps results in a linear reflectance function for the digital volume.
  • this linearity does not carry over to the reflectance function for the print.
  • the structure of the PreCoM technique allows dot gain compensation to be performed when the volume is computed. Since each map is designed individually, each map can contain the number of dots that produces the desired linear reflectance function in print. Dot gain compensation can thus be done at the same time as the image is halftoned, making pre-adjustments of the of the original image's histogram unnecessary. With the number of dots for each map decided, the halftoning volume can be calculated. The proposed procedure for this is described below. Examples of results during the process are given in Figure 3. 7
  • the process is initiated by generating a matrix of the desired map size containing white noise in the range [0,1]. By thresholding the matrix at for instance 0.2, a dot pattern with approximately 20% minority dots is obtained, see Figure 3 a). If necessary, extra dots can be added or removed of random to get the exact number of dots that the map should have.
  • the first map of the volume is computed and stored, Figure 3 b). To calculate the next map, the voids of the first map are located and the desired number of extra dots are added iteratively in these positions, still by using the filter assigned to the first map. Note that no rearrangement of the dots is made at this stage. See Figure 3 c) for an example.
  • the new dot pattern may be optimal with respect to the old filter, it will in general not be optimal with respect to the new filter which is assigned to this particular tint value.
  • the dot pattern has to be optimized with the new filter before the new map can be stored, Figure 3 d).
  • This procedure of iteratively deriving the next map from the previous map continues up to the level where the map consists of equally many ones and zeros.
  • the representation of minority and majority dots is switched, and instead of adding dots, dots at the tightest clusters are removed before optimization.
  • the procedure continues until all minority pixels are gone.
  • the maps between 0% and 20% are derived in a similar manner, starting from the first generated map at 20% and removing minority dots.
  • the filter kernel used to make the dots as dispersed as possible in each map is a Gaussian shaped kernel.
  • the width of the kernel function is changed according to the tint value. The fewer the minority dots, the wider the kernel.
  • the filter kernel g(x,y) is defined by
  • T is the number of minority pixel divided with the map size
  • cl and c2 are positive constants chosen to make the expression cl-c2T positive
  • S is the size of the kernel in pixels.
  • the size of the kernel, S could be made dependent on the function g(x,y). While a wide kernel size is necessary for 8 very bright or dark tints, a small kernel size is sufficient for tints around 50% . It is thus not necessary to use the large kernel size for all maps.
  • micro structures may both facilitate the correlation between maps, thus producing smooth transitions, as well as increase the visual quality of the resulting tints.
  • the visually pleasant impression of results from iterative and error diffusion methods could partly be explained by the micro structures introduced. The observer seems to exclude even clearly visible structures and focus on the image information it conveys. 9
  • Figure 6a-c shows the test images halftoned using the halftoning volume derived with these filters.
  • a slight asymmetry can be noticed in the shades, where the line structure is visible further up on the bright side of the 50% level than on the dark side.
  • the reason for this is that the initial binary pattern from which the computation of the volume started was derived at 20% white dots. Since previously derived maps will affect the appearance of the next, the maps above the 50% level will be affected by the heavy line structures in the 50% level. While it may be possible to derive a more symmetrical volume, experiments have shown that if the initial map is derived at the 50% level, unpleasant discontinuity effects are introduced around this level. The reason for this may be that the optimization results in a local minimum from which it is hard to derive the next map without major changes. 10
  • an optimal map for the 50% level could be a perfect chessboard pattern, but the next map derived from this will either be visually unpleasant or have a very different characteristic.
  • the starting map should thus be derived at a level where a stable pattern is the optimum, i.e. a pattern which dots easily can be added to or removed from without really affecting the optimality or the characteristics.
  • Such stable patterns could possibly be found at higher levels than 20% . If this is the case, a more symmetrical halftoning volume than the one used in the above can be computed. We have not yet, however, put any effort in developing such volumes since the general idea of introducing micro structures without losing the smoothness in transitions still holds with the proposed method.
  • Halftoning with PreCoM introduces the possibility of producing well-behaved tints as well as smooth transitions between them without any loss in speed compared to methods based on threshold matrices.
  • the method can be implemented in a truly parallel manner, speeding up the halftoning procedure even further.
  • every map is designed individually, under the constraint that the correlation is not lost, specific characteristics that improves the image quality can be introduced. This, together with the possibility of compensating for the dot gain in the halftoning procedure itself, makes this method attractive in applications where both speed and quality are important. With the print-on-demand concept lying around the corner, the future for the PreCoM technique seems to be very promising.

Landscapes

  • Engineering & Computer Science (AREA)
  • Multimedia (AREA)
  • Signal Processing (AREA)
  • Image Processing (AREA)
  • Facsimile Image Signal Circuits (AREA)
  • Image Analysis (AREA)

Abstract

L'invention concerne un procédé de création de demi-tons reposant sur l'utilisation de cartes établies par des calculs préliminaires, à raison d'une carte pour chaque valeur de ton possible dans l'image. L'opération de création des demi-tons appliquée à la valeur d'image considérée en un emplacement spécifique donne la carte à partir de laquelle les différents pixels sont copiés en demi-tons dans leurs positons respectives. Les cartes à haute ou faible densité ont des points minoritaires à écartement maximum, mais les cartes de densité intermédiaire présentent une transition successive allant des points à écartement maximum aux grappes de points structurées d'un type défini, par exemple comme les lignes droites.
PCT/SE1999/000282 1998-03-05 1999-03-01 Creation de demi-tons avec des cartes etablies par des calculs preliminaires Ceased WO1999045697A1 (fr)

Priority Applications (1)

Application Number Priority Date Filing Date Title
EP99908033A EP1066716A1 (fr) 1998-03-05 1999-03-01 Creation de demi-tons avec des cartes etablies par des calculs preliminaires

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
SE9800686A SE513365C2 (sv) 1998-03-05 1998-03-05 Rastreringsförfarande baserat på förberäknade mallar
SE9800686-9 1998-03-05

Publications (1)

Publication Number Publication Date
WO1999045697A1 true WO1999045697A1 (fr) 1999-09-10

Family

ID=20410402

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/SE1999/000282 Ceased WO1999045697A1 (fr) 1998-03-05 1999-03-01 Creation de demi-tons avec des cartes etablies par des calculs preliminaires

Country Status (3)

Country Link
EP (1) EP1066716A1 (fr)
SE (1) SE513365C2 (fr)
WO (1) WO1999045697A1 (fr)

Cited By (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
EP1650955A1 (fr) * 2004-10-18 2006-04-26 Software 2000 Ltd. Système de génération de masques binaires
EP1480445A3 (fr) * 2003-05-20 2007-09-26 Software 2000 Ltd. Système de génération de masques binaires et pilotes d'imprimante et procédés d'impression utilisant de tels masques
EP1956824A1 (fr) * 2007-02-09 2008-08-13 Dainippon Screen Mfg., Co., Ltd. Procédé et appareil de génération de matrice de seuil
US20120200590A1 (en) * 2009-10-28 2012-08-09 Xuemei Zhang Determining a layout of graphic objects according to a layout density map

Citations (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO1991012686A1 (fr) * 1990-02-07 1991-08-22 Eastman Kodak Company Obtention de demi-teinte numerique a l'aide de configurations de modulations visuelles minimum correlees
US5276535A (en) * 1991-12-24 1994-01-04 Levien Raphael L Method and apparatus for halftoning of images using grayscale error diffusion
US5579457A (en) * 1994-07-29 1996-11-26 The Harlequin Group Ltd. Image display apparatus and method using irregularly placed curving structures
US5583660A (en) * 1990-09-14 1996-12-10 Minnesota Mining And Manufacturing Company Non-perpendicular, equal frequency non-conventional screen patterns for electronic halftone generation
US5802212A (en) * 1996-02-09 1998-09-01 Seiko Epson Corporation Clustered-dot dither with white-fleck suppression

Patent Citations (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO1991012686A1 (fr) * 1990-02-07 1991-08-22 Eastman Kodak Company Obtention de demi-teinte numerique a l'aide de configurations de modulations visuelles minimum correlees
US5583660A (en) * 1990-09-14 1996-12-10 Minnesota Mining And Manufacturing Company Non-perpendicular, equal frequency non-conventional screen patterns for electronic halftone generation
US5276535A (en) * 1991-12-24 1994-01-04 Levien Raphael L Method and apparatus for halftoning of images using grayscale error diffusion
US5579457A (en) * 1994-07-29 1996-11-26 The Harlequin Group Ltd. Image display apparatus and method using irregularly placed curving structures
US5802212A (en) * 1996-02-09 1998-09-01 Seiko Epson Corporation Clustered-dot dither with white-fleck suppression

Non-Patent Citations (4)

* Cited by examiner, † Cited by third party
Title
DIGITAL TECHNICAL JOURNAL, Volume 5, No. 2, 1993, ROBERT ULICHNEY, "Video Rendering". *
R. ULICHNEY, "Filter Design for Void-and-Cluster Arrays", SOC. FOR INFORMATION DISPLAY INTERNATIONAL SYMPOSIUM DIGEST OF TECH. PAPERS, Vol. 25, San Jose, CA, 14-16 June 1994, pages 809-812. *
R. ULICHNEY, "Spatial Extent of Void and Cluster Finding Filters", IS&T'S ELEVENTH INTERNATIONAL CONGRESS ON ADVANCES IN NON-IMPACT PRINTING TECHNOLOGIES, Hilton Head, SC, 29 Oct.-3 Nov. 1995, pages 430-433. *
R. ULICHNEY, Human Vision, Visual Processing and Digital Display IV, J. ALLEBACK and B. ROGOWITZ, Eds., PROC. SPIE 1913, 1993, pages 332-343. *

Cited By (7)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
EP1480445A3 (fr) * 2003-05-20 2007-09-26 Software 2000 Ltd. Système de génération de masques binaires et pilotes d'imprimante et procédés d'impression utilisant de tels masques
EP1650955A1 (fr) * 2004-10-18 2006-04-26 Software 2000 Ltd. Système de génération de masques binaires
US8705131B2 (en) 2004-10-18 2014-04-22 Software Imaging Technology Limited Bit mask generation system
EP1956824A1 (fr) * 2007-02-09 2008-08-13 Dainippon Screen Mfg., Co., Ltd. Procédé et appareil de génération de matrice de seuil
US8004719B2 (en) 2007-02-09 2011-08-23 Dainippon Screen Mfg. Co., Ltd. Threshold matrix generation method, threshold matrix generating apparatus, and recording medium
US20120200590A1 (en) * 2009-10-28 2012-08-09 Xuemei Zhang Determining a layout of graphic objects according to a layout density map
US9024965B2 (en) * 2009-10-28 2015-05-05 Hewlett-Packard Development Company, L.P. Determining a layout of graphic objects according to a layout density map

Also Published As

Publication number Publication date
EP1066716A1 (fr) 2001-01-10
SE9800686D0 (sv) 1998-03-05
SE513365C2 (sv) 2000-09-04
SE9800686L (sv) 1999-09-06

Similar Documents

Publication Publication Date Title
US5343309A (en) Image processing system and method employing adaptive filtering to provide improved reconstruction of continuous tone images from halftone images including those without a screen structure
US5239390A (en) Image processing method to remove halftone screens
CA1241606A (fr) Systeme de reproduction d'images mixtes
DE69132104T2 (de) Dither matrix zur Halbtonwiedergabe von Grautonbildern unter Verwendung einer Maskierung mit blauem Rauschen
EP0838940B1 (fr) Traitement utilisant plusieurs canaux spatiaux
DE69228917T2 (de) Halbtonrasterung mit Fehlerrückkopplung und bildabhängiger Verbesserung
US5543941A (en) Method and apparatus for halftone rendering of a gray image using a blue noise mask
US6937365B2 (en) Rendering images utilizing adaptive error diffusion
JPH0696198A (ja) エラー拡散を利用したビットマップ画像の非量子化解像度変換
WO1993026116A2 (fr) Procede et appareil de reproduction d'une image avec impression de niveaux de gris
JP4107059B2 (ja) 画像処理方法および画像処理装置
US7262879B2 (en) Method for screening of halftone images
DE69712572T2 (de) Fehlerdiffusionsverfahren mit symmetrischer Verbesserung
DE69817473T2 (de) Halbtonrasterungssystem
US20050008245A1 (en) Image processing method, image processor, image forming apparatus and memory product
JP3933354B2 (ja) ハーフトーンイメージ生成方法
WO1999045697A1 (fr) Creation de demi-tons avec des cartes etablies par des calculs preliminaires
US5602971A (en) Multilevel halftoning using a randomised bayer matrix
JP2001203890A (ja) 画像処理方法および誤差拡散のためのノイズパターン生成方法
Nilsson Digital halftoning using pre-computed maps
Zhang Adaptive ordered dither
Nilsson Precomputed frequency modulated halftoning maps that meets the continuity criterion
Wu et al. Supercell dither masks with constrained blue noise interpolation
Mitsa et al. Wavelets as a tool for the construction of a halftone screen
CA2231816C (fr) Methode et dispositif de rendu demi-tons d'une image a niveaux de gris au moyen d'un masque a bruit bleu

Legal Events

Date Code Title Description
AK Designated states

Kind code of ref document: A1

Designated state(s): JP US

AL Designated countries for regional patents

Kind code of ref document: A1

Designated state(s): AT BE CH CY DE DK ES FI FR GB GR IE IT LU MC NL PT SE

121 Ep: the epo has been informed by wipo that ep was designated in this application
DFPE Request for preliminary examination filed prior to expiration of 19th month from priority date (pct application filed before 20040101)
WWE Wipo information: entry into national phase

Ref document number: 1999908033

Country of ref document: EP

WWP Wipo information: published in national office

Ref document number: 1999908033

Country of ref document: EP

WWW Wipo information: withdrawn in national office

Ref document number: 1999908033

Country of ref document: EP