Title of Invention

A METHOD OF PROCESSING DATA COMPRISED IN A DIGITAL INPUT IMAGE

Abstract The present invention relates to a method of and an arrangement for processing data comprised in a digital input image. said arrangement comprises a decoder unit (20) intended for transmitting a decoded analog image (s2) to a television receiver (27) via a channel CH (23). The decoder unit includes a device MPD (21) by means of which the encoded digital image (s1) can be decoded and a digital to analog converter DAC (22). The television receiver includes an analog to digital converter ADC (24) intended for supplying a digital input image (s3) to a device DET (25) by means of which it is possible to detect if said digital input image has been encoded in accordance with a block-based encoding technique. A correction or post-processing device COR (26), whose operation depends on the data supplied by the detection device, thus enables the display quality of the digital image to be improved in view of its display on the screen.
Full Text

The present invention relates to a method of processing data comprised in a digital input image.
It may be employed in the detection of blocks in a digital image which has been previously encoded and which is subsequently decoded in accordance with a block-based encoding technique, for example the MPEG standard (Motion Picture Experts Group), and in the correction of the data comprised in the blocks in order to reduce visible artifacts caused by the block-based encoding technique.
*
The article entitled "A projection-based post-processing technique to reduce blocking artifacts using a priori information on DCT coefficients of adjacent blocks", published by Hoon Paek and Sang-Uk Lee, in "Proceedings of 3rd IEEE International Conference on Image Processing, vol 2, Lausanne, Switzerland, 16-19 Sept 1996, pp. 53-56" described a method of processing data comprised in a digital image.
In contrast with most methods currently used said method is employed in the frequency domain, i.e. after a discrete transform has been applied to the digital input image, and not in the spatial domain. This discrete transform is, for example, a discrete cosine transform DCT. It is an object of the processing method to correct DCT coefficients which correspond to block artifacts. In order to find and suppress the frequencies associated with the block artifacts the prior art method consists of the following steps of: • calculating a first discrete cosine transform U of a segment u of N pixels where N = 8 in


• calculating an overall discrete cosine transform W for a segment w of 2N, i.e. 16 pixels

Fig. 1 shows the two adjacent segments u (13) and v (14) belonging respectively to two blocks (11,12) of 8x 8 pixels and situated at opposite sides of a block boundary (16). When it is assumed that the frequency contents of the segments u and v are close and the contents of the segments are uniform, the segment w (15) corresponding to the concatenation of the first and the second segment will include high spatial frequencies beyond those of the segments u and v if a block artifact is present between the segments u and v. Now, W can be expressed as a function of U and V in the following manner:

The predicted maximum frequency kwpred of W, i.e. if no block artifact were present, theoretically depends on the maximum frequencies kumax and kvmax of U and V in the following manner:
kwpred = 2.max( kumax, kvmax) + 2
where
and max is the function which yields the maximum of k values among a set of given values.
The coefficients W(k) corresponding to the frequencies k odd higher than the predicted maximum frequency kwpred are considered to be equivalent to block artifacts and are therefore set to zero.
It is an object of the invention to provide a data processing method by means of which a better display quality can be obtained for the digital image displayed on the screen. The invention takes the following aspects into consideration.
An image which belongs to a digital video signal is split into blocks of 8 rows of 8 pixels in order to be encoded in accordance with the MPEG standard, the first block of

the image starting at the position (0,0). As a result of the digital to analog and the analog to digital conversion and as a result of any possible preprocessing algorithms applied to the digital video signal, an original image belonging to this signal may be shifted by a few pixels and the size of a grid corresponding to the MPEG blocks may have changed. The input image appearing at the input of a television set now does not contain any information by means of which it is neither possible to determine the change of the decoded image with respect to the origin nor the change in size of the grid corresponding to the blocks after decoding. Thus, the prior-art data processing method appears to be inefficient if it is used as such because it presumes that the origin of the decoded image is (0, 0) and that the blocks have a size of 8 x 8 pixels.
According to the invention, in order to eliminate these drawbacks, the method of processing data comprised in a digital input image is characterized in that it further
comprises a step of determining a real maximum frequency on the basis of transformed data
*
resulting from the overall transform, and a step of detecting a grid on the basis of a comparison between the real maximum frequency and the predicted maximum frequency for a portion of said digital input image.
This grid detection step makes it possible to determine whether or not the digital input image has been encoded in accordance with a block-based encoding technique, the size of the grid corresponding to the encoding blocks of initially 8 rows of 8 pixels in the case of the MPEG standard, yielding blocks of 8 rows of 10, 12 or 16 pixels in the case of said standard, after a possible resampling of the image during decoding.
These aspects of the invention as well as more detailed other aspects will become apparent more clearly from the following description of a number of embodiments of the invention, which are given by way of example, with reference to the accompanying drawings, in which:
Fig. 1 illustrates the prior-art data processing method,
Fig. 2 is a diagram representing a data processing method in accordance with the invention for processing a digital video signal,
Fig. 3 is a diagram representing a data processing method in accordance with the invention for detecting sequences of images encoded in accordance with a block-based encoding technique,

Fig. 4 is a flow chart of the step of detecting images encoded in accordance with a block-based encoding technique, and
Fig. 5 is a diagram representing a data processing method in accordance with the invention for correcting the encoded digital images.
The present invention relates to a method of processing data comprised in a digital input image, which method serves to improve the display quality of said digital input image when it has been encoded previously in accordance with a block-based encoding technique.
Fig, 2 illustrates a complete system for processing a digital video signal comprising encoded digital images (SI). If this system includes a decoder unit (20), which serves to transmit a decoded analog image (S2) to a television receiver (27) via a channel CH (23). The decoder unit comprises a decoder MPD (21) by means of which the digital video signal, which has been encoded in accordance with the block-based encoding technique, can be decoded, and a digital to analog converter DAC (22). The television receiver includes an analog to digital converter ADC (24), which serves to supply a digital input image (S3) to a device DET (25) which makes it possible to detect if said digital input image has been decoded in accordance with a block encoding technique. A correction or post-processing device COR (26), as opposed to a signal pre-processing performed before the encoding of said signal, now enables the display quality of the digital image to be improved for its display on the screen. The post-processing is performed in dependence on data supplied by the detection device.
The video signal available at the input of a television set comprises images formed by pixels but does not contain any information about possible encoding and decoding parameters of this signal if it has previously been encoded in accordance with a block-based encoding technique. This is why the detection device is adapted to determine the size and the position of a grid corresponding to the blocks which are used by the encoding technique and which may have been resampled during decoding. A proper application of the correction device indeed depends on the detection and the location of the grid.
The data processing method was developed particularly in the scope of digital images encoded and subsequently decoded in accordance with the MPEG standard. However, it remains applicable to any other digital video signal encoded and subsequently decoded in accordance with a block-based encoding technique such as, for example, H.261 or H.263.

An image belonging to a digital video signal encoded in accordance with the MPEG standard is divided into blocks of 8 rows of 8 pixels, the first block of the image starting at the position (0,0). As a result of digital to analog and analog to digital conversions and as a result of the possible use of algorithms for pre-processing the digital video signal an original image belonging to said signal may have been shifted by a few pixels. On the other hand, the original image may have been encoded in accordance with different horizontal encoding formats in order to maintain a satisfactory display quality at low transmission rates. In that case, the original image is down-sampled horizontally before it is encoded and is subsequently up-sampled horizontally during decoding in order to recover its initial format. This results in a change of the size of the grid owing to the up-sampling, encoding being still performed on blocks of 8 rows of 8 pixels.
In order to eliminate this drawback the data processing method in accordance with aims at detecting digital video signals encoded in accordance with the block-based encoding technique. For this purpose, said method, which is illustrated in Fig. 3, comprises the following steps:
• A step of calculating a first discrete transform DCT1 (31), for example a cosine transform, for a first data set u (13). In the preferred variant this data set is formed by the luminance values of N pixels, where N = 8 in the present example. The data processing method is applied in one dimension, i.e. along a row of N pixels in order to detect the width of the grid and along a column of N pixels in order to detect the height of said grid.
• A step of calculating a second discrete transform DCT1 (32) for a second data set v (14) adjacent to the first set. In the preferred variant this second data set is also formed by N pixels.
• A step of calculating an overall discrete transform DCT2 (33) for a data set w (15) corresponding to the concatenation CON (30) of the first and the second set and consequently formed by 2N pixels in the present case.
• A step of determining PRED (34) a predicted maximum frequency kwpred (37) on the basis of the transformed data U (13') and V (141) resulting from the first (31) and the second (32) transform DCT1, which is calculated in the following manner: kwpred = 2.max( kumax, kvmax) + 2
where kumax = max( k€ {0,.. .,N-1} / abs(U(k)) > T), kvmax - max( ke {0,.. .,N-1} / abs(V(k)) > T ), abs(x) is the function giving the absolute value of x, and where T is a threshold value greater than or equal to zero

• A step of determining RE A (35) a real maximum frequency kwmax (38) on the basis of
the transformed data W (15') resulting from the overall transform, which is calculated in
the following manner:
kwmax - max( ke {0,.. .,2N-1} / abs(W(k)) > T)
• A detection step GRI (36) which makes it possible to determine if the digital input image
has been encoded in accordance with a block-based encoding technique, which is effected
by means of a comparison between the real maximum frequency kwmax (38) and the
predicted maximum frequency kwpred (37) for a portion of the digital input image. In the
preferred variant said portion is formed by one row of every twenty rows of an image in
order to detect the width of the grid and by one column of every twenty columns of this
image in order to detect the height of the grid. Such a method requires minimal
calculating resources while it ensures a satisfactory detection quality. Subsequently, the
values kwpred(j) and kwmax(j) are calculated for each pixel j of the row or the column
through iteration of the calculation of the transforms DCT1 and DCT2 after each
incrementation by one pixel. The detection step thus indicates if a grid has been detected
and, if this is so, it gives the size and the location of this grid (39).
Fig. 4 is a flow chart which illustrates the detection step (36) in greater detail. This detection step comprises a sub-step COMP (40) of computing a quantity X(j) such that:
X(j) = kwpred(j) - kwmax(j).
On a block boundary the value of X(j) is greater than a threshold XT. In the preferred variant the value of the threshold XT is 4. In order to detect the position and the size of the grid the values j of X which meet this requirement are stored and a histogram of these modulo 8 values is generated. The grid is detected if one value of the histogram is high and distinctly preponderates over the 7 other values, i.e. in the preferred variant if:
• the first maximum of the histogram is greater than 1 and equal to 3 times the second maximum of this histogram, and
• the first maximum of the histogram is greater than 10.
A first test HG (401) is then performed in the horizontal direction in order to determine if a grid having a width of 8 pixels has been detected. If this is the case, the detection step is terminated, which yields the result HG1 (43), which indicates that a grid having a width of 8 or of 16 pixels has been detected, the last-mentioned width corresponding to an image format of Vz. In the opposite case, a first sub-step FC1 (41) of converting the format is performed in order change from an original image having a width of 720 pixels to

an image having a width of 540 pixels, i.e. an image format of %. For this purpose, a row of an image is up-sampled by a factor of 3 by adding two zeros between two pixels of the original image and by filtering with the aid of a filter Fl. The filter Fl has, for example, 19 coefficients and is as follows:
Fl = [9,6,0,»21,-9,0,103,220,295,330,295,220,103,0,-9,-21,0,6,9]
The signal thus obtained is subsequently down-sampled by selecting one out of four pixels.
The frame detection method is then applied again to the converted digital video signal. Then a second test HG (402) is performed in the horizontal direction in order to determine if a grid having a width of 8 pixels has been detected in the image after format conversion. If this is the case, the detection step is terminated, which yields the result HG2 (44), which indicates that a grid having a width of 10 pixels has been detected in the initial image before the format conversion. In the opposite case, a second sub-step FC2 (42) of converting the format is performed in order to change from an original image having a width of 720 pixels to an image having a width of 480 pixels, i.e. an image format of 2/3. For this purpose, the row of an image is up-sampled by a factor of 2 by adding a zero between two pixels of the original image and by filtering with the aid of a filter F2. The filter F2 has, for example, 15 coefficients and is as follows:
F2 = [-3,-37,-41,-20,52,163,248,300,248,163,52,-20,-41,-37,-3]
The signal thus obtained is subsequently down-sampled by selecting one out of three pixels.
The frame detection method is then again applied to the digital video signal thus converted. A third test HG (403) is then performed in the horizontal direction in order to determine if a grid having a width of 8 pixels has been detected in the image after image conversion. If this is the case, the detection step is terminated, which yields the result HG3 (45) which indicates that a grid having a width of 12 pixels has been detected in the original image. In the opposite case, the result NHG (46) corresponds to the fact that no grid has been detected in the horizontal detection.
At the same time, the frame detection method is applied to the digital input image in the vertical direction. A test VG (404) is performed in order to determine if a grid having a height of 8 pixels has been detected. If this is the case, the detection step is terminated, which yields the result VG (47) which indicates that a grid having a height of 8 pixels has been detected. In the opposite case, the result NVG (48) corresponds to the fact that no grid has been detected in the vertical direction.

The grid detection method has been described for the image formats used in the MPEG standard. However, the method is not limited to these formats and can be used with other image formats without departing from the scope of the invention.
The detection method just described makes it possible to detect if a video signal received by a television set has been encoded in accordance with a block encoding method. Said method also indicates the size and the location of the grid which corresponds to the blocks on the basis of which encoding has been effected. A post-processing method is then applied as a function of the data provided by the detection method, preferably to the image after format conversion, which is in order to process blocks of 8 rows of 8 pixels. The image is subsequently reconverted to full-screen format (i.e. 720 pixels) after processing for the purpose of being displayed on the screen.
In an advantageous variant the post-processing method employs steps common to the detection method in accordance with the invention. Fig. 5 illustrates such a method of post-processing of digital video data. Said method comprises:
• a step of calculating a first discrete transform DCT1 (31) for a first set of N data u (13),
• a step of calculating a second discrete transform DCT1 (32) for a second set of N data v (14) adjacent to the first set,
• a step of calculating an overall discrete transform DCT2 (33) for a set of 2N data w (15) corresponding to the concatenation (30) of the first and the second set and yielding a set of transformed data W (15!),
• A step of determining PRED (34) a predicted maximum frequency kwpred (37) on the basis of the transformed data U (13!) and V (14') resulting from the first (31) and the second (32) transform DCT1, which frequency is calculated in the following manner: kwpred = 2.max( kumax, kvmax) + 2

where T is a non-zero threshold value.
The determining step in accordance with the invention provides a refinement of the calculation of the critical maximum frequency on the basis of the introduction of the threshold value T. This refinement enables a more effective correction of the image to be achieved. The threshold value T is a function of the number of pixels belonging to the sets of data u and v.
The post-processing method also includes a correction step PROC (51) which itself has a sub-step for the detection of natural contours on the basis of the initial data values

u and v and the transformed data values U and V. This sub-step enables said natural contours to be distinguished from block boundaries caused by encoding artifacts. A natural contour is then detected if two conditions are fulfilled:
• the average values u et v of the sets of data u and v at opposite sides of a
block boundary differ by a substantial value greater than M, i.e. :
|TJ - v| > M, and
• the sets of data u and v exhibit a low activity, which manifests itself in that
the values of kumax and kvmax are low and smaller than kO, i.e. kumax kO and kvmax The correction step PROC also includes a sub-step of truncation that zeroes the transformed data W (15') resulting from the overall discrete transform whose frequency is odd and higher than the predicted maximum frequency, yielding truncated data (15").
The postprocessing method finally includes a step of calculating the inverse discrete transform IDCT2 (52) of the truncated data, yielding decoded data (15'"), which are subsequently intended to be displayed on the screen.
Unlike the detection method described hereinbefore, which can be applied to a portion of the image, for example some rows and some columns, the post-processing method is preferably applied to the whole image.
Moreover, this post-processing method may be applied either after the detection method or at the output of a decoder (21), the parameters supplied by the decoder making it possible to know the position of the frame corresponding to the encoding blocks.
The post-processing method also includes two successive phases whose order of application does not matter:
• the correction of vertical artifacts, which corresponds to a row-by-row processing of the data,
• the correction of horizontal artifacts, which corresponds to a column-by-column processing of the data.
Finally, in the case of interlaced image sequences, the image is de-interlaced so as to form two fields. Each of the two fields is subsequently subjected to the postprocessing method. After processing the two fields are then re-interlaced.
In a first variant of the post-processing method in accordance with the invention the sets of data u (13) and v (14) contain luminance values associated with N = 8 successive pixels. The step of determining PRED (34) the predicted maximum frequency kwpred (37) on the basis of the transformed data U (13') and V (14') resulting from the first




• a sub-step of truncation of the transformed data Wf or W" resulting from the overall discrete transform whose frequency is higher than the predicted maximum frequency kw'pred or kw"pred.
This variant enables the processing complexity to be reduced while at the time the correction efficiency of the first variant is maintained. The sub-step for the detection of natural contours is not essential for a good working of the post-processing method in accordance with the third variant.
The above description with reference to Figs. 1 to 5 illustrates rather than limits the invention. It is evident that there are numerous alternatives within the scope of the appended Claims.
There are numerous ways of implementing the described functions by means of software. In this respect, it is to be noted that Figs. 2 to 5 are highly diagrammatic, each Figure representing merely a single variant. Thus, although a Figure shows different functions as separate blocks, this does not exclude the possibility that a single item of software performs a plurality of functions. This by no means excludes the possibility that a function may be carried out by a group of software items.
These functions may be realized by means of a television receiver circuit or by means of a suitably programmed set top box circuit in the case of the post-processing method. A set of instructions contained in a program memory can cause the circuit to carry out the different operations described hereinbefore with reference to Figs. 2 to 5. The set of instructions can also be loaded into the program memory by reading a data carrier, such as for example a disc which carries the set of instructions. Reading may also be effected via a communication network such as, for example, the internet. In this case, a service provider will make the set of instructions available to those interested.
Any reference signs given in parentheses in a claim shall not be construed as limiting said claim. The use of the verb "to comprise" does not exclude the presence of any elements or steps other than those defined in a claim. The use of the indefinite article "a" or "an" preceding an element or step does not exclude the presence of a plurality of these elements or these steps.




WE CLAIM :
1. A method of processing data comprised in a digital input image, said method
comprising the steps of:
calculating a first discrete transform (31) of a first set (13) of N pixels values of a row or column of the digital input image,
calculating a second discrete transform (32) of a second set (14) of N pixels values of a row or column of the digital input image, said second set being adjacent to the first set,
calculating an overall discrete transform (33) of a third set (15) corresponding to the concatenation (30) of the first and the second set,
determining (34) a predicted maximum frequency (37) on the basis of the transformed data resulting from the first and the second transform (13!,14'), said processing method being characterized in that it further comprises a step of determining (35) a real maximum frequency (38) on the basis of the transformed data (15') resulting from the overall transform,
calculating a difference between the real maximum frequency and the predicted maximum frequency,
iterating the calculations of the predicted maximum frequency, the real maximum frequency and the difference for different pixel positions within rows or columns of a portion of the digital input image,
detecting a block boundary if a value of the difference is higher than a threshold, and storing the corresponding pixel position, and
detecting a grid based on the stored pixel position modulo k that preponderates, where k is a possible dimension of a block in a block-based encoding technique.
2. A method as claimed in claim 1, wherein the step of detecting a grid
comprising building a histogram of the stored pixel position modulo k, and

wherein a grid is detected if the maximum value of the histogram is higher than a threshold and is substantially higher than the second maximum value of the histogram.
3. A method as claimed in claim 1, comprising a step of converting the digital image into another image format if no grid has been detected, the preceding steps being applied once again to the converted digital input image.
4. A method as claimed in claim 1, comprising a step of correcting the digital input image if a grid (39) has been detected, the correction step being applied taking into account a size and a position of said grid.
5. A method of processing data comprised in a digital input image encoded in accordance with a block encoding technique, said method comprising the steps of:
calculating a first discrete transform (31) of a first set (13) of N pixels values of a row or column of the digital input image,
calculating a second discrete transform (32) of a second set (14) of N pixels values of a row or column of the digital input image, said second set being adjacent to the first set,
calculating an overall discrete transform (33) of a third data set (15) corresponding to the concatenation (30) of the first and the second set,
determining (34) a predicted maximum frequency (37) on the basis of the transformed data resulting from the first and the second transform (13!,14'),
truncating (51) the transformed data resulting from the overall discrete transform (15f) and having a frequency higher than the predicted maximum frequency, said processing method being characterized in that the first and the second sets u (13) and v (14) are divided into two sub-sets u', u" and v', v", respectively, the sub-sets u?, v' containing the data of odd rank and the sub-sets

u" and v" containing the data of even rank, the steps of calculating the discrete transforms (31, 32, 33), of determining (34) the predicted maximum frequency, and of truncating (51) the transformed data resulting from the overall discrete transform being applied to the sub-sets u\ V, on the one hand, and u", v", on the other hand.
dated this 9 day of October 2001


Documents:

0829-mas-2000 abstract-duplicate.pdf

0829-mas-2000 claims-duplicate.pdf

0829-mas-2000 description (complete)-duplicate.pdf

0829-mas-2000 drawings-duplicate.pdf

829-mas-2001-abstract.pdf

829-mas-2001-claims.pdf

829-mas-2001-correspondence others.pdf

829-mas-2001-correspondence po.pdf

829-mas-2001-description complete.pdf

829-mas-2001-drawings.pdf

829-mas-2001-form 1.pdf

829-mas-2001-form 26.pdf

829-mas-2001-form 3.pdf

829-mas-2001-form 5.pdf

829-mas-2001-other documents.pdf


Patent Number 221310
Indian Patent Application Number 829/MAS/2001
PG Journal Number 37/2008
Publication Date 12-Sep-2008
Grant Date 20-Jun-2008
Date of Filing 09-Oct-2001
Name of Patentee KONINKLIJKE PHILIPS ELECTRONICS N.V
Applicant Address GRONEWOUDSEWAG 1, 5621 BA EINDHOVEN,
Inventors:
# Inventor's Name Inventor's Address
1 CAROLINA MIRO SOROLLA 31 AVENUE DU MARECHAL DE LATTRE DE TASSIGNY, F-94440 VILLECRESNES,
2 ARNAUD GESNOT 1 RUE DE CHEMBERY, F-78180 MONTIGNY LE BRETONNEUX,
3 JORGE E CAVIEDES 3100 DALLA COURT, YORKTOWN HEIGHTS, NY 10598,
PCT International Classification Number H04N7/00
PCT International Application Number N/A
PCT International Filing date
PCT Conventions:
# PCT Application Number Date of Convention Priority Country
1 0012936 2000-10-10 France