[go: up one dir, main page]

WO1996039774A1 - Systeme de mise en antememoire pour traitement d'interpolation - Google Patents

Systeme de mise en antememoire pour traitement d'interpolation Download PDF

Info

Publication number
WO1996039774A1
WO1996039774A1 PCT/US1996/008111 US9608111W WO9639774A1 WO 1996039774 A1 WO1996039774 A1 WO 1996039774A1 US 9608111 W US9608111 W US 9608111W WO 9639774 A1 WO9639774 A1 WO 9639774A1
Authority
WO
WIPO (PCT)
Prior art keywords
values
subspace
color
data
image data
Prior art date
Application number
PCT/US1996/008111
Other languages
English (en)
Inventor
Riaz A. Moledina
Kok S. Chen
Iue-Na Swen
Original Assignee
Apple Computer, Inc.
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 Apple Computer, Inc. filed Critical Apple Computer, Inc.
Priority to AU59574/96A priority Critical patent/AU5957496A/en
Publication of WO1996039774A1 publication Critical patent/WO1996039774A1/fr

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/46—Colour picture communication systems
    • H04N1/56—Processing of colour picture signals
    • H04N1/60—Colour correction or control
    • H04N1/6058—Reduction of colour to a range of reproducible colours, e.g. to ink- reproducible colour gamut

Definitions

  • the present invention relates to the interpolation of data values, and, more particularly, to the use of a cache memory in association with data interpolation processing.
  • color image data that represents a certain color in one device may not correspond to the same color when displayed on another device. These differences are due, at least in part, to characteristics of elements such as the inks that are used in ink-jet printers and the phosphors that are used in CRT monitors to produce a visible image.
  • a display device such as a monitor may utilize an RGB color space, in which each color is defined in terms of its red, green, and blue components, whereas another device such as a printer may employ a different color space to define colors, such as CMYK in which a color is represented in terms of cyan, magenta, yellow and black components.
  • RGB color space in which each color is defined in terms of its red, green, and blue components
  • printer may employ a different color space to define colors, such as CMYK in which a color is represented in terms of cyan, magenta, yellow and black components.
  • the color LUT functions to translate color data corresponding to a first I/O device (a source device) to color data corresponding to a second I/O device (a destination device).
  • the LUT stores color values corresponding to the destination device and functions such that when it is indexed, according to source device color image values, it outputs translated color image data values which provide accurate reproduction of the source device color in the destination device.
  • Color image data in a LUT can be graphically represented as an N- dimensional geometric structure, where each dimension (or axis) of a space defined thereby corresponds to one component of an input color value. Hence, a graphical representation may portray a color space defined by N axes disposed in N dimensions.
  • Each axis in a graphical representation may correspond to values associated with a particular range of color values stored in a LUT.
  • the graphical representation may correspond to a three-dimensional lattice structure, or cubic color space, wherein values associated with three color attributes, such as red, green and blue (RGB), each correspond to one of the three axes.
  • RGB red, green and blue
  • a LUT's entire color range may be represented by sampled increments, or indexed, in discrete values.
  • the LUT is accessed according to index data corresponding to the discrete values which are close to exact input values.
  • a number of related discrete output values are produced by the LUT are then interpolated to arrive at the final derived result.
  • Interpolation processing involves the use of calculations based on geometry to determine output values for reliable color reproduction of source device color on a destination device.
  • the objective of the interpolation process is to approximate a color translation transfer function for each represented color.
  • interpolation may operate by taking color image data values for individual pixels from the video display and applying a known transform to determine corresponding color image data values in a device-independent color space, such as the CIE-standard ABC color space. These device- independent values are then further translated into the color space of the printer to provide accurate color reproduction of the pixel in a printed point on the printer.
  • the LUT data is typically stored in the main memory of a computer or printer.
  • Main memory is typically implemented with dynamic random-access memory (DRAM). While inexpensive, this type of memory is relatively slow for the purposes of color translation processing. Cumulatively, the repeated accessing of main memory, in order to access LUT data, results in slow output processing.
  • conventional color data processing systems may store entire color translation LUTs in an associated high speed memory, which usually consists of a high speed static random access memory (SRAM). While offering much faster access to the data values in the LUT, the trade-off in using SRAM is that it is very expensive. Large, high-speed color printers, which use SRAM to provide real-time interpolation of LUT data values, are extremely expensive. Summary
  • the present invention provides methods in accordance with independent claims 1, 3, and 4, an apparatus in accordance with independent claims 6 and 10, and a system in accordance with independent claim 8. Further advantageous features, aspects and details of the invention are set forth in the dependent claims, the following description and the drawings.
  • the claims are to be understood as a first non-limiting approach of defining the invention in general terms.
  • the interpolation process is employed to translate color image data generated in a source device for use in a destination device.
  • a system which incorporates the present invention stores data values in a cache, which define a color unit subspace that surrounds a point to be interpolated, and performs multi-dimensional interpolation in accordance with this space.
  • the cache memory is preferably a single-entry cache, i.e. it stores a single tagged entry that contains the minimal set of parameters needed to define a destination device color subspace for interpolation.
  • the stored subspace is interpolated in concert with input image data, to produce output values for accurate reproduction of input image color on the destination device.
  • the LUT contents are stored in a main memory, such as a DRAM, and only those data values in the LUT corresponding to a source device subspace region surrounding a data point under consideration are loaded into cache memory for interpolation processing.
  • main memory such as a DRAM
  • cache requirements are significantly reduced, while interpolation processing efficiency and speed are maintained.
  • Corresponding cost savings are realized by the reduced requirement for cache memory, because only that amount of high speed memory sufficient to store data which corresponds to the unit subspace of the source device is required to carry out the color translation.
  • Figure 1 depicts a conventional image processing system having a display device and a printer.
  • Figure 2 depicts an image upon which the present invention might operate.
  • Figure 3 depicts a graphically represented color space having a unit subspace which has single integer dimensions and surrounds an image point to be processed.
  • Figure 4 depicts an image processing arrangement incorporating the invention.
  • Figure 1 depicts a conventional color imaging system 20 having a CPU 22, a display monitor 26, and a printer 24.
  • the CPU 22 has an interpolation processor 28 with an attached SRAM memory 30 for storing a look-up table that is used to convert source device color data into device-independent color data.
  • the printer 24 may be a high speed color printer, and contain a color processing circuit 32 with an associated SRAM memory 34 which stores the contents of another LUT for converting device-independent color values into corresponding color values for the printer. Operation of the system 20 for transformation of a color image appearing on the display 26 into color data values for the printer 24 might proceed as follows.
  • the interpolation processor 28 After entering into a print mode, the interpolation processor 28 utilizes the color transformation LUT stored in its associated memory 30 to transform image data corresponding to the display 26 into device-independent color data, which is transmitted to the printer.
  • the color processing circuit 32 accesses the SRAM memory 34 for LUT data to perform color translation processing of the received image data into its color space. Provision of the large SRAM memory 34 enhances color processing speed and printer output speed. However, the cost of the printer 24 can be significant due to the presence of this high-speed memory.
  • input image data can be graphically represented in three-dimensions and corresponds to display pixel color values for red, green, and blue (RGB) content.
  • Output image data also is three-dimensional and corresponds to printed pixel color values for a device- independent color space, e.g., Cie-based ABC, or to cyan, magenta, and yellow components in a CMY color space.
  • a device- independent color space e.g., Cie-based ABC, or to cyan, magenta, and yellow components in a CMY color space.
  • Figure 2 depicts an exemplary image upon which image processing in accordance with the invention might be employed.
  • This image depicts an outdoor scene with mountains in the background.
  • an image can comprise large regions in which the color data may be substantially similar between adjacent image points, such as a blue sky 36.
  • color data for contiguous picture elements, or pixels, 38 in such a region varies only slightly.
  • a system incorporating the invention exploits this phenomenon by using fast memory, e.g. cache memory, to maintain those portions of a color transformation LUT corresponding to a source color space region surrounding an image data point undergoing processing.
  • an arrangement in accordance with the invention utilizes the data corresponding to a preceding input data point to avoid accessing the LUT from the slower main memory.
  • Figure 3 depicts a three-dimensional color space 39 where the X, Y, and Z axes may represent, for example, RGB, CIE-based ABC or CMY values.
  • the color space data can be stored in a LUT.
  • LUTs typically do not contain every value in a color gamut because to do so would consume inordinate amounts of memory. Instead, the range of colors is represented by samples of discrete values shown by the index markings 40 on each of the X, Y, and Z axes.
  • An input image point 42 corresponds to a display value for a given pixel on a video display. The point 42 resides within the source color space. In the depicted example, the X, Y, and Z values for the point 42 are approximately 3.7, 4.4, and 3.6, respectively. These are the input image values.
  • this unit subspace is depicted as a cube 44 which is defined by eight data points.
  • the unit subspace may have a different shape which is defined by a different number of data points.
  • the unit subspace is determined by pairs of adjacent discrete index values on each axis, between which the input data point falls.
  • the X dimension of the unit subspace is defined by the single unit between discrete X values 3 and 4
  • the Y dimension of the unit subspace is defined by the single unit between discrete Y values 4 and 5
  • the Z dimension of the unit subspace is defined by the single unit between discrete Z values 3 and 4.
  • Each of the eight corners of the unit subspace cube 44 represents a boundary point which defines the subspace.
  • the unit subspace boundary points are used to index a transformation LUT which contains corresponding output data for a destination color space.
  • each data point on the cube 44 might contain corresponding component values for cyan, magenta and yellow.
  • the destination device may employ a different color space such as CMYK, in which case the LUT output contains additional information corresponding to K (black) component values.
  • CMYK color space
  • the LUT output contains additional information corresponding to K (black) component values.
  • a conventional cache memory is organized to include a number of cache entries, where each cache entry includes cache data and an address tag.
  • the data held in the cache is selected LUT entries from main memory for a unit subspace.
  • the address tag indicates an address in main memory where the contents of the cache is stored.
  • the cache compares the address with all of its address tags to see if it presently contains a copy of the data. If it does contain the data, it reads the data from its own high speed RAM and delivers it to the processing unit or I/O device. This is termed a "cache hit,” and is usually much faster than reading the same data directly from main memory. If the cache does not contain the data, however, a cache miss occurs and the cache system fetches the data at the corresponding address in the main memory and provides it to the processing unit.
  • the cache memory is a single-entry cache. That is, the cache need only have the capacity required to store a unit subspace of the input data.
  • the cache stores all of the color component values at each of the eight data points that correspond to the respective boundary points of the cube.
  • a cache hit is determined by examining a point which constitutes an origin of the source unit subspace. In the above-described example, the origin of the source unit subspace is the point (3,4,3) (see Figure 3).
  • this is done by first determining the origin of a unit subspace for an input image pixel and making a comparison to see if this unit subspace origin is equal to the origin point of the unit subspace of the preceding input image pixel. If equal, the system uses the destination color space data already stored in the cache. If not equal, the remainder of the unit subspace boundary values are determined for the input data point, and the LUT is indexed accordingly, to obtain new unit subspace values. Alternate techniques for determination of whether cache data is appropriate for subsequent processing may be utilized in order to achieve a desired result. Once the appropriate set of data points has been retrieved from the LUT, they are interpolated to determine the final value for the pixel in the destination device.
  • the fractional portions of the RGB input image values (.7, .4, and .6) can be used for interpolation processing to determine the corresponding CMY output values within the destination device color space.
  • the interpolation process itself is known, and therefore is not described in detail herein.
  • FIG. 4 shows a diagram of a computer system 12 incorporating the present invention.
  • the system 12 includes a CPU 14, a display 15, and a printer 5.
  • color transformation processing is handled by a color interpolation processor 9 which may be located in the printer 5, or within the CPU 14, or in a separate device 19 located between the printer 5 and the CPU 14.
  • the color interpolation processor may, for example, be an application specific integrated circuit (ASIC).
  • the color interpolation processor includes a cache memory 11 which may be provided within the color processor 9, or as a separate device 17.
  • Input image data is provided to the interpolation processor 9.
  • a determination is made whether input image data received by the interpolation processor 9 corresponds to subspace data presently stored in the cache memory 11. If so, processing of the input image data is performed from the information in the cache. If not, the LUT 13 in the main-memory 7 is accessed to fetch the necessary data for a source data subspace corresponding to the new input image data.
  • the interpolation processor 9 performs interpolation processing based upon the newly retrieved data, and stores it in the cache memory 11.
  • both the input and output data are three-dimensional. It should be noted that the input and output data may have any number of dimensions, and that the number of dimensions of input data may not necessarily be equal to the number of dimensions of the output data. It should further be appreciated that, while described with respect to color processing, the invention may be applied to interpolation processing of other image attributes such as grayscale, half tones, hues, and shading.
  • the cache contains a single entry which comprises a unit subspace of the source color space.
  • the properties of images where a large number of successive data points may have values which are the same as, or close to, one another, enables high processing throughput to be achieved with a minimal size cache.
  • a larger cache which stores multiple subspace entries, or data points for a subspace which is larger than a unit subspace, can be used.

Landscapes

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

Abstract

Système de traitement de données d'image déterminant des valeurs de sortie qui produisent une reproduction exacte d'images de dispositif de source dans un dispositif de destination. Ce système utilise le traitement de l'interpolation simultanément avec une antémémoire à entrée unique, où, pour une valeur donnée d'entrée de source, une région d'espace d'image de dispositif de source est déterminée, ladite région contenant la valeur d'entrée de source. On utilise une table afin de déterminer une région correspondante d'espace d'image de dispositif de destination, dont les données sont mémorisées dans l'antémémoire à entrée unique. L'interpolation s'effectue au moyen des données d'antémémoire et de la valeur d'entrée de source. On analyse les valeurs d'entrée suivantes afin de déterminer si on peut réutiliser les données d'antémémoire mémorisées précédemment.
PCT/US1996/008111 1995-06-06 1996-05-31 Systeme de mise en antememoire pour traitement d'interpolation WO1996039774A1 (fr)

Priority Applications (1)

Application Number Priority Date Filing Date Title
AU59574/96A AU5957496A (en) 1995-06-06 1996-05-31 A caching system for interpolation processing

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
US47872295A 1995-06-06 1995-06-06
US08/478,722 1995-06-06

Publications (1)

Publication Number Publication Date
WO1996039774A1 true WO1996039774A1 (fr) 1996-12-12

Family

ID=23901114

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/US1996/008111 WO1996039774A1 (fr) 1995-06-06 1996-05-31 Systeme de mise en antememoire pour traitement d'interpolation

Country Status (2)

Country Link
AU (1) AU5957496A (fr)
WO (1) WO1996039774A1 (fr)

Cited By (9)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
GB2333921A (en) * 1997-12-12 1999-08-04 Hewlett Packard Co Non-symmetric radial and non-symmetric pruned radial interpolation
US6028683A (en) * 1997-12-12 2000-02-22 Hewlett-Packard Company Common pruned radial and pruned tetrahedral interpolation hardware implementation
US6031642A (en) * 1997-12-12 2000-02-29 Hewlett-Packard Company Tetrahedral and pruned tetrahedral interpolation
US6040926A (en) * 1997-12-12 2000-03-21 Hewlett-Packard Company Common non-symmetric pruned radial and non-symmetric pruned tetrahedral interpolation hardware implementation
US6040925A (en) * 1997-12-12 2000-03-21 Hewlett-Packard Company Radial and pruned radial interpolation
US6049400A (en) * 1997-12-12 2000-04-11 Hewlett-Packard Company Non-symmetric tetrahedral and non-symmetric pruned tetrahedral interpolation
EP3107062A1 (fr) * 2004-04-16 2016-12-21 Apple Inc. Système et procédé permettant d'exécuter des opérations graphiques à l'aide d'unité de traitement graphique
US10402934B2 (en) 2004-04-16 2019-09-03 Apple Inc. System for optimizing graphics operations
US10410572B2 (en) 2017-11-22 2019-09-10 Samsung Electronics Co., Ltd. Display device including timing controller

Citations (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
EP0501942A1 (fr) * 1991-03-01 1992-09-02 Barco Graphics N.V. Procédé et dispositif de conversion d'un ensemble de coordonnées chromatiques
EP0647061A1 (fr) * 1993-10-04 1995-04-05 Xerox Corporation Conversion de l'espace couleur
US5450216A (en) * 1994-08-12 1995-09-12 International Business Machines Corporation Color image gamut-mapping system with chroma enhancement at human-insensitive spatial frequencies
WO1995024682A1 (fr) * 1994-03-07 1995-09-14 Silicon Graphics, Inc. Procede d'integration de memoire de textures et de logique d'interpolation

Patent Citations (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
EP0501942A1 (fr) * 1991-03-01 1992-09-02 Barco Graphics N.V. Procédé et dispositif de conversion d'un ensemble de coordonnées chromatiques
EP0647061A1 (fr) * 1993-10-04 1995-04-05 Xerox Corporation Conversion de l'espace couleur
WO1995024682A1 (fr) * 1994-03-07 1995-09-14 Silicon Graphics, Inc. Procede d'integration de memoire de textures et de logique d'interpolation
US5450216A (en) * 1994-08-12 1995-09-12 International Business Machines Corporation Color image gamut-mapping system with chroma enhancement at human-insensitive spatial frequencies

Cited By (10)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
GB2333921A (en) * 1997-12-12 1999-08-04 Hewlett Packard Co Non-symmetric radial and non-symmetric pruned radial interpolation
US6028683A (en) * 1997-12-12 2000-02-22 Hewlett-Packard Company Common pruned radial and pruned tetrahedral interpolation hardware implementation
US6031642A (en) * 1997-12-12 2000-02-29 Hewlett-Packard Company Tetrahedral and pruned tetrahedral interpolation
US6040926A (en) * 1997-12-12 2000-03-21 Hewlett-Packard Company Common non-symmetric pruned radial and non-symmetric pruned tetrahedral interpolation hardware implementation
US6040925A (en) * 1997-12-12 2000-03-21 Hewlett-Packard Company Radial and pruned radial interpolation
US6049400A (en) * 1997-12-12 2000-04-11 Hewlett-Packard Company Non-symmetric tetrahedral and non-symmetric pruned tetrahedral interpolation
GB2333921B (en) * 1997-12-12 2002-04-10 Hewlett Packard Co Non-symmetric radial and non-symmetric pruned radial interpolation
EP3107062A1 (fr) * 2004-04-16 2016-12-21 Apple Inc. Système et procédé permettant d'exécuter des opérations graphiques à l'aide d'unité de traitement graphique
US10402934B2 (en) 2004-04-16 2019-09-03 Apple Inc. System for optimizing graphics operations
US10410572B2 (en) 2017-11-22 2019-09-10 Samsung Electronics Co., Ltd. Display device including timing controller

Also Published As

Publication number Publication date
AU5957496A (en) 1996-12-24

Similar Documents

Publication Publication Date Title
EP0700198B1 (fr) Système pour la correction de données d'image couleur avec interpolation tétraédrique sur un grillage hexagonal
US5517334A (en) Indexed processing of color image data
US7310167B2 (en) Color converting device emphasizing a contrast of output color data corresponding to a black character
EP0793377B1 (fr) Table de consultation mélangée pour imprimer des images avec à la fois des éléments d'image et d'inscription
US7933045B2 (en) Color conversion system and method
US20030052895A1 (en) Image data processing method and apparatus, storage medium product, and program product
JP2000196909A (ja) ルックアップテ―ブルの精度の改良方法
US5678033A (en) Multi-stage interpolation processor
US20020031258A1 (en) Image processing method, image processing apparatus, and storage medium
US8891144B2 (en) Color management method, module, and program product, and printer using said method
US6707938B2 (en) Principal axis look-up for color correction
WO1995031794A1 (fr) Systeme de gestion de la couleur pour infographie
JPH07184078A (ja) 色空間変換システム
US8237735B2 (en) Caching for color management systems performing a gamut mapping function
WO1996039774A1 (fr) Systeme de mise en antememoire pour traitement d'interpolation
US6989837B2 (en) System and method for processing memory with YCbCr 4:2:0 planar video data format
US7443544B2 (en) Accelerating color conversion using a temporary palette cache
US6621498B1 (en) High-speed non-separable color table lookup
US20050140994A1 (en) Image processing apparatus, image processing method and image processing program
JP2004032140A (ja) 色域マッピング方法、色域マッピング装置、プログラム、記憶媒体
EP1093630A2 (fr) Inversion et reconversion de donnees couleur
US8054518B2 (en) Color imaging devices, color imaging methods, and color separation methods
JP2007166562A (ja) 色変換装置および色変換方法、色変換プログラム、記憶媒体
US20060268298A1 (en) Color space conversion by storing and reusing color values
JPH09186898A (ja) 画像処理装置及びその方法

Legal Events

Date Code Title Description
AK Designated states

Kind code of ref document: A1

Designated state(s): AL AM AT AU AZ BB BG BR BY CA CH CN CZ DE DK EE ES FI GB GE HU IS JP KE KG KP KR KZ LK LR LS LT LU LV MD MG MK MN MW MX NO NZ PL PT RO RU SD SE SG SI SK TJ TM TR TT UA UG UZ VN AM AZ BY KG KZ MD RU TJ TM

AL Designated countries for regional patents

Kind code of ref document: A1

Designated state(s): KE LS MW SD SZ UG AT BE CH DE DK ES FI FR GB GR IE IT LU MC NL PT SE BF BJ CF CG CI CM GA GN ML

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)
REG Reference to national code

Ref country code: DE

Ref legal event code: 8642

NENP Non-entry into the national phase

Ref country code: CA

122 Ep: pct application non-entry in european phase