LEYNADIER, Christophe Antoine (100 rue Marc Sangnier, Maison Alfort, Maison Alfort, F-94700, FR)
SOBCZAK, Philippe Jean-Michel (9 rue Port à l'Anglais, Alfortville, Alfortville, F-94140, FR)
LE GLAUNEC, Vincent Jean-Marie Noël (Résidence le Clos de Soulins, 2bis avenue de Gallieni, Brunoy, F-91800, FR)
LEYNADIER, Christophe Antoine (100 rue Marc Sangnier, Maison Alfort, Maison Alfort, F-94700, FR)
SOBCZAK, Philippe Jean-Michel (9 rue Port à l'Anglais, Alfortville, Alfortville, F-94140, FR)
1 . Method for generating print data for a digital colour image having pixels, the method comprising the steps of
- determining for each pixel in the digital colour image a value of a characteristic feature, and
- selecting an available conversion method for processing the pixels of the digital colour image into print data, based on the determined characteristic values of the pixels, characterized in that the step of selecting comprises the steps of
- deriving from the digital colour image at least two subimages (S2), in each of which the pixels have a value that represents another characteristic feature of the pixels in the digital colour image,
- establishing a class for each pixel in the digital colour image (S5) by combining the at least two values of the corresponding pixels in the subimages, and
- selecting a conversion method based on a statistic of classes of the pixels in the digital colour image (S1 1 ).
2. Method according to claim 1 , wherein the at least two subimages comprise a gradient subimage, in which each pixel indicates a local variation in a value of a pixel relative to a value of at least one pixel located in a neighbourhood of said pixel, and a non-uniformity subimage, in which each pixel determined to be comprised in a uniform area is provided with a predetermined value.
3. Method according to claim 1 or 2, wherein the digital colour image is divided into a number of windows (S4), each window comprising a number of pixels, and the step of establishing a class for each pixel in the digital colour image is based on establishing a class for each window in the digital colour image by combining average values of the pixels in corresponding windows of the at least two subimages. 4. Method according to claim 3, wherein the step of selecting a conversion method comprises the steps of determining a number of windows for each class relative to the total number of windows (S7), forming a fraction, and comparing this fraction to a threshold (S9).
5. Method according to claim 4, wherein the threshold for selecting a conversion method is established by processing a number of preselected images in a learning mode.
6. Colour printer system comprising a controller for scheduling and interpreting print jobs and a printing engine for marking support material, the controller comprising modules for generating print data for a digital colour image having pixels (61 , 62) characterized in that the controller further comprises at least two modules for processing the digital colour image into subimages (51 , 52), a module for establishing a class for each pixel in the digital colour image by combining the at least two values of the corresponding pixel in the subimages (54) and a module (56) for selecting a conversion method based on a statistic of classes of the pixels in the digital colour image.
7. Colour printer system according to claim 6, wherein the controller further comprises a module for dividing the digital colour image into a number of windows (53) and corresponding windows in the at least two subimages.
8. Colour printer system according to claim 7, wherein the controller further comprises a module for calculating a number of windows for each class relative to the total number of windows (55).
9. Colour printer system according to claim 8, wherein the controller further comprises a module for establishing thresholds in a learning mode, the thresholds being used by the module for selecting a conversion method (56).
In the state of the art, colour printer systems are applied for producing high quality reproductions of images on a receiving material. These images exist in the form of a digital representation and originate from a computer application, from a camera, from a scanner, or any other source. At the time of reproduction, the images are prepared to be part of a print job that is sent to the printer system. The printer system comprises a printing engine and a controller for scheduling and interpreting print jobs. In the controller an image of a print job is converted to print data that is sent to the printing engine for marking the receiving material. A printing engine comprises e.g. an electrophotograhic process, wherein an illumination system is used to imagewise discharge a charged photoconducting material. Thereafter the photoconducting material is developed by dry coloured powder which is transferred to the receiving material. Another printing engine comprises an inkjet process in which inkjet heads release imagewise small ink drops of various colours from nozzles on a side of the printhead where the receiving material is brought close to. In support of each printing process the image is converted in a number of processing steps to print data that is suitable for the printing process. This is called a conversion method and comprises e.g. background reduction, to reduce the amount of ink or toner that is rendered in the background of the information in the image, contrast enhancement, to accomodate the contrast in the image to the contrast that is available with the toner or ink on the receiving material, filtering for sharpness improvement and prevention of moire, halftoning for deciding where the dots that form the reproduction of the image on the receiving material are placed and print strategy masking, which is used to determine which pixel positions are printed at which printing process pass. These processing steps are well known in various forms.
A colour printer system as indicated is capable of processing and printing many kinds of colour images. Some of the images have only lines and text on a white background, other images comprise photographic images or maps. Maps comprise images that have text on a coloured background. If the image does not have pixels, the digital
representation of the image is processed to a pixel-based digital representation. Each pixel is characterized by a combination of numbers for a number of channels. In one case each pixel is characterized by three numbers, one for the amount of red in the R- channel, one for the amount of green (G-channel) and on for the amount of blue (B- channel). In another case each pixel is characterized by four numbers for cyan, mangenta, yellow, and black. In each case the combination of numbers for the channels is called the value of the pixel. It has been found that each type of image has an optimal conversion method for generating print data. Therefore it is advantageous to select the appropriate conversion method for an image of a defined type. Usual image types include 2D CAD, which comprise line drawings and text, 3D CAD/maps, which comprise business graphics, model drawings and geographic maps, and photographic images, which comprise images with real-life scenes.
In the current state of the art, the user of the print system is asked to select a
conversion method for a print job. If the print job comprises only one image type, the most appropriate one may be selected, assuming the user is aware of the possibilities of the printer system. In mixed print jobs, which comprise various image types, the user has the choice to either use a print conversion method that is suboptimal for some of the images in the job, or to split the print job into several print jobs, each involving a single type of image.
In the US Patent Application US 2005/0163385 a method is described to classify images using a concentration ratio which is compared to one or more classification thresholds. This concentration ration is determined from histogram data of the lightness of the pixels in the image. The classification can be used to select appropriate settings, i.e. the appropriate conversion method, for printing the image. However, the lattitude of this method is rather limited, since all characteristic features of the image are expressed in one number. The goal of the present invention is to automatically select the optimal conversion method for generating print data for an arbitrary image in a print job. The present invention reaches this goal by adding to the method according to the preamble the steps of deriving from the digital colour image at least two subimages, in each of which the pixels have a value that represents another characteristic feature of the pixels in the digital colour image, establishing a class for each pixel in the digital colour image by combining the at least two values of the corresponding pixels in the subimages, and selecting a conversion method based on a statistic of classes of the pixels in the digital colour image. A characteristic feature of the pixels comprises the lightness of the pixel, its colourfulness, its similarity to other pixels in the direct environment etc. A class of a pixel indicates a most probable kind of pictorial surrounding the pixel is an element of. Such a class may be a white uniform area, a coloured uniform area, a photograph, or a line. This last class comprises text elements.
At least two subimages are obtained by processing the digital colour image by state-of- the-art image processing methods. This has the advantage that characteristic features of the image in at least two dimensions are used to determine the image type. A subimage, which usually comprises one channel, is an image of the same size as the original image, having pixels that have values that are mathematically derived from the values of the pixels in the original image or in other subimages and that indicate a feature of pixels on a corresponding position in the original image. Such a feature may be a lightness, indicating the perceived amount of light at the position of the pixel, a gradient, indicating a change in the pixel value at the position of the pixel, or a quantized part of the pixel value at the position of the pixel.
In a further improved embodiment of the method according to the invention the at least two subimages comprise a gradient subimage, in which each pixel indicates a local variation in a value of a pixel relative to a value of at least one pixel located in a neighbourhood of said pixel, and a non-uniformity subimage, in which each pixel determined to be comprised in a uniform area is provided with a predetermined value. When making a histogram of values that occur for pixels in the digital colour image, the relation between a pixel value and the values in the immediate surroundings of the pixel is lost. Therefore a number of pixels representing a local, uniform background is not distinguished from a similar number of pixels having the background value that are scattered all over the image. From experiments it shows that the lattitude of the method increases when pixels in uniform areas, such as background for text, are provided with a predetermined value to obtain a non-uniformity subimage. Another example of a subimage is a gradient subimage, in which each pixel indicates a local variation in a value of a pixel relative to a value of at least one pixel located in a neighbourhood of said pixel. A gradient subimage indicates the fluctuations in pixel value, which are usually high for pictorial surroundings and low for surroundings with uniform areas.
In a further embodiment the digital colour image is divided into a number of windows, each window comprising a number of pixels. In this way the amount of memory and the processing time can be adjusted to the availability of these resources. A window in image processing is a connected area of pixels from the set of pixels of an image. Especially large images, comprising more than 100 million pixels, are processed in a reasonable amount of time using windows. In the subimages corresponding windows are determined. The class of a window in the digital colour image is established by combining average values of the pixels in corresponding windows of the at least two subimages. The class of a pixel equals the class of a window that comprises the pixel. The use of corresponding windows in the subimages also has the advantage that fluctuations in the attribution of classes to pixels are reduced, because the values of several pixels are combined to establish a class.
In a further embodiment the number of windows for each class relative to the total number of windows is determined. This fraction is compared to a threshold to classify the digital colour image as a type of image for which a conversion method is selected. It is possible to overrule this automatic selection of an image type, but in usual circumstances it is convenient to have the digital colour image automatically classified before the printing starts. With the selection of an image type, a conversion method is enclosed. In a further embodiment a learning mode is provided in which an original type is defined and a number of preselected images are processed in order to establish thresholds to which the percentages of occurring classes are compared. If, for example, a number of images is processed which are CAD-drawings with lines, most of the windows belong to the class of white uniform area and some to the class of lines. The thresholds will be chosen in such a way that for each class the percentages of windows of the preselected CAD-drawings fall within a range limited by the thresholds. A number of original types is predefined, and the conversion methods are fixed, but the user may also be able to define its specific original type and its corresponding conversion method, using the learning mode to set the thresholds for this image type.
The invention is also embodied in a colour printer system comprising a controller for scheduling and interpreting print jobs and a printing engine for marking support material, the controller comprising modules for generating print data for a digital colour image having pixels by adding at least two modules for processing the digital colour image into subimages, a module for establishing a class for each pixel in the digital colour image by combining the at least two values of the corresponding pixel in the subimages and a module for selecting a conversion method based on a statistic of classes of the pixels in the digital colour image. The controller can handle mixed print jobs without interaction of the user and select the optimal module for generating print data for each image in the print job.
Further embodiments comprise modules that are enabled to perform the methods that are described earlier. These modules may refer to implementations that are primarily software based for general purpose hardware, or to implementations that use special purpose hardware for fast execution of the methods.
The invention is further elucidated using the following figures:
Figure 1 is a colour printing system in which the method is applicable.
Figure 2 is a flow chart that shows the various steps in the image processing method. Figure 3 is a number of reduced images that indicate how a gradient subimage is derived from the original digital colour image.
Figure 4 is a number of reduced images that indicate how a non-uniformity image is derived from the original digital colour image.
Figure 5 is the division of the image in windows and the analysis of the windows in various classes.
Figure 6 is a computer system that is used in embodiments of this invention.
The colour printing system of Figure 1 comprises a wide format ink jet printer (14) and a document printer (18) for office size print output. For both type of printers the print data is generated by a controller (16) that is connected to a network (N). It is equally well possible to have two controllers, one for each printer. Access to this network is made by computers of all kind, such as personal computers, workstations, servers etc., also designated as client computers (2,4,6). Not shown is a scanner that converts hardcopy originals into digital colour images that may be part of the system. The digital colour images, that are part of a print job, are sent to the controller via the network to be printed on one of the available printers. The controller uses a method of the invention to classify the digital colour image and to select the appropriate conversion method for generating the print data. The flow chart in Figure 2 shows the steps of a preferred embodiment of the invention: first a decision is made about the number of subimages that is generated (S1 ). At least two subimages are used. These subimages are generated using known methods (S2), until all subimages are available (S3, "N"). In an embodiment two subimages (n=2) are deduced from the digital image. In one subimage, called a gradient subimage, the value of the pixel, comprising one channel, is indicative for the local variation in the lightness of the pixel in the digital image (cf. Figure 3) and in a second subimage, called a non- uniformity subimage, the value of the pixel is indicative for the feature that the pixel in the digital image is comprised in a uniform area, whether coloured or white (cf. Figure 4). For a reproduction, white means that no ink or toner will be deposited for that pixel. If not all subimages are generated, the branch marked "Y" will be followed back to step 2 (S2). In step 4 the images and subimages are divided into windows of about 10 to about 30 pixels in both directions (S4). An average value of the pixels of each window of each subimage is calculated and arranged in one of three levels: "low", "medium", or "high". This results in nine possible combinations of values of windows in the
subimages. For all these combinations a class is established. For example a
combination of a low gradient value and a high value in the non-uniformity image indicates a window with primarily uniform area pixels. On the other hand a combination of a high gradient value and a low value in the non-uniformity image indicates a window with primarily photographic pixels. This step of determining a class for each window (S5) is repeated until all windows are finished (S6: Y). Then the fraction of windows of each class is determined (S7). When this has been carried out for all classes (S8: Y), these fractions are compared to the thresholds (S9) that are related to an image type with a corresponding conversion method. When all comparisons have been executed (S10: Y) one of the image types is selected (S1 1 ) and the method ends. Figure 3 shows a number of reduced images, representing an original image (31 ), a lightness subimage (32), and a gradient subimage (33). These subimages are derived by conventional image processing steps (30). The pixels in the original image are characterized by three numbers for the channels R, G, and B to indicate a coloured picture element. However, other channels may also be used to indicate a colour. From these numbers a lightness, L, is deduced, e.g. by linearly combination :
L = (5 R + 9 G + 2 B) / 16
but there are many other ways, including non-linear transformations. Making a new subimage in which every pixel has the value of the lightness of the corresponding pixel in the original image is a common procedure in image processing. The lightness subimage has only one channel. From the lightness subimage a gradient subimage is derived by applying a high-pass filter, such as a filter characterized by the kernel
indicating that for every pixel a value is calculated that equals four times the present value minus the value of the neighbouring pixel above, under, to the left and to the right. In a homogeneous part all pixels have the same value and the resulting value will be zero. In the gradient subimage this is shown as black. If the indicated pixels have different values, the resulting value will be unequal to zero. The resulting value is limited to fall in a predetermined range from zero (black) to a maximum value (white). Noise in the image may lead to small resulting values, indicating small gradients, which are to be discarded.
In Figure 4 a similar sequence of reduced images is shown, where the image processing deduces from the original image (31 ) a quantified subimage (34) and subsequently a non-uniformity subimage (35). The first step comprises the reduction of the available colour values of the pixels. In the original image every pixel is
characterized by three numbers, ranging from 0 to 255. Therefore 256 3 = 16,777,216 possible combinations exist. Each combination indicates a different colour, although some of these colours will be indiscernable upon rendering. In the quantified subimage every number is rounded to a multiple of 16, reducing the number of colours to 16 3 = 4096. When rendered, all these colours will be discernable, but in areas where the colour changes gradually contours will be visible. A histogram of the colours in the quantified subimage is made to obtain the occurrence frequency of each colour. The colour having the highest frequency is selected. The pixels having the selected colour are subjected to an opening operation. This is a morphological operation comprising an erosion and dilation operation that are executed in that order. The first operation, erosion, is generally used to remove the outer pixels of a set of pixels and in this case removes the pixels of the selected colour that have a neighbouring pixel that is not of the selected colour. The second operation, dilation, adds four neighbouring pixels to a pixel of the selected colour. As a result of the two operations, uniform areas of the selected colour will lose the pixels on the edge of the area in the erosion operation, but these pixels will largely be restored by the dilation operation. Therefore the ratio between the number of pixels before the opening operation and the number of pixels after the opening operation will be close to one. In contrast, if the pixels of the selected colour occur in a scattered way in the image, many pixels of the selected colour will disappear in the erosion operation, since they frequently have a neighbouring pixel of a different colour and these pixels will not reappear by the dilation operation. Therefore the ratio mentioned above will in this case not be close to one. In this way a distinction is made between colours that occur in uniform coloured areas and colours that occur in scattered pixels. To compose a non-uniformity subimage the pixels that belong to a uniform area are given the value 0, which corresponds to black in the reduced image (35) of Figure 4. These pixels are found by selecting pixels that belong to the frequently occurring colours in uniform coloured areas and find the corresponding pixels in the gradient subimage. If this gradient is below a threshold, the pixel in the subimage is given the value 0. The other pixels in the non-uniformity subimage are given the maximum value, usually 255, which corresponds to white in the reduced non-uniformity subimage (35). Pixels occurring in pictures in the original image will often have non- frequently occurring colours, and if they have frequently occurring colours, the pixels will be scattered. Therefore the corresponding pixels in the non-uniformity subimage will often have the maximum value. An alternative way to make a non-uniformity subimage, which is executed much faster, is found in selecting the most frequently occurring colour and computing an average value of the gradient of the pixels that have that colour in the quantified subimage. If this value is lower than a threshold, the pixels of the selected colour belong to a uniform area and are made black in the non-uniformity subimage. Otherwise they are white. In both methods to compose a non-uniformity subimage, the image may be processed in bands. The most frequently occurring colour is then calculated for each band and the uniform area determination is performed for the selected colour of the current band and for the selected colours of neighbouring bands. In this way the image can be processed more efficiently without having the complete image available in memory.
Figure 5 shows the division of the gradient subimage (33) and the non-uniformity subimage (35) into corresponding windows of pixels. An enlarged part of the subimages (36, 37) is showing the individual windows comprising about 20 pixels in both directions. An average value of the pixels within each of the windows is determined and compared against the tresholds LNU, HNU, and TG. LNU indicates a low threshold for the non- uniformity subimage and has a value of about 15, HNU indicates a high threshold for the non-uniformity subimage and has a value of about 175, and TG indicates a threshold for the gradient subimage and has a value of about 25. The values of these thresholds refer to the situation in which the values in the subimages range from 0 to 255. For each window a class is established according to the following table:
Table 1. Division of the classes uniform, line / text or photo depending on the averages of the values of pixels within the windows of the subimages.
After establishing a class for each window, a segmented subimage (39) is obtained with every window in the class "photo" having a white colour, every window in the class "line / text" having a gray colour and every window in the class "uniform" having a black colour, as shown in the enlarged part of the subimage (38).
If a window is established as a uniform area, an average value of the pixels in the corresponding window of the original image is used to distinguish a white uniform window from a coloured uniform window. Therefore four classes of windows, representing the dominant type of pixels, are discerned. The relative frequency of the occurrence of the class of the windows is used to determine an original type and the corresponding conversion method. In the case of the image of Figures 3, 4 and 5 it was found that 1 1 % of the pixels belong to the class of uniform white area, 3% of the pixels is of the class uniform coloured area, 37% of the pixels is line / text , and 49% of the pixels is photo.
By supplying a number of test originals for which an image type has been determined, the criterions as given in Table 2 were derived. Table 2. Criterions to classify an image into one of four image types for which
corresponding conversion methods have been established. The class relative freqency is the number of pixels which fall in a class. The criterions are successively checked with an 'AND' relation for the limits listed in a row. If no limit is given for a class, any percentage will do. Several rows refer to one image type. When no distribution of classes as given fits the distribution for an original image, the image will be printed as having a mixed content.
class relative frequency
image type photo white uniform coloured uniform line / text photographic image > 65 %
> 30 % < 50 % < 30 %
> 20 % > 35 % < 30 %
> 18 % < 50 % < 25 %
2D CAD / lines / text < 10 % > 65 %
< 10 % > 50 %
< 10% > 37 % > 40 %
< 10 % > 40% > 20 %
3D CAD / Map / > 65 %
Business graphic < 15 % > 30 % > 30 %
> 22% > 50%
> 30% > 20%
< 12% > 10% > 40%
Mixed content all other distributions Figure 6 shows a computer system (16) that is configured to act as a controller for receiving print jobs through the network (N). It acts as the digital interface of the print engine (14) and is also called a digital front-end. The system comprises a central databus (44) that couples to a network adapter (40), a central processing unit (41 ), a random access memory (42), where data is kept as long as the system is turned on and a hard disk that comprises non-volatile memory. In this system modules are provided that are able to perform the methods as described earlier. The new modules are indicated by a box (50). Various conversion modules for converting different type of originals to print data are provided. In this system they are automatically selected at the time an original is offered in a print job for output on the print engine (14). From the rasterized image at least two subimage are derived by the subimage processors (51 , 52). These original image and the subimages are divided in windows by the windows divisor module (53). For every window a class is determined in a processor (54). After determining the percentage of windows belonging to a class in the percentage calculator (55), the image classificator (56) determines the image type of the original, which is the basis for selecting one or the other conversion module (61 , 62). These modules are e.g. implemented by field programmable gate arrays (FPGA).
The skilled person will recognise that other embodiments are possible within the scope of the appended claims.