Method and apparatus for visual lossless pre-processing

134182/2

<img img-format="tif" img-content="drawing" file="IL134182AD00021.tif" id="idf0001" />

pyti iw# xbb ψΛπι iw

METHOD AND APPARATUS FOR VISUAL LOSSLESS PRE-PROCESSING

Applicant: : wpnnn VLS COM LTD.

Dip .ON PN ΛΊ

1392-IL

1392-IL

2883IL

FIELD OF THE INVENTION l

The present invention relates generally to processing of video images and, in particular, to pre-processing of images for later compression by 5 standard compression techniques.

BACKGROUND OF THE INVENTION

There are many types of video signals, such as broadcast television (TV), digital, video conferencing, interactive TV, etc. All of these signals, in their digital form, are divided into frames, each of which consists of many pixels 10 (image elements), each of which requires 8-24 bytes to describe them. The result is megabytes of data per frame.

Before storing and / or transmitting these signals, they typically are compressed, using one of many standard video compression techniques, such as JPEG, MPEG, H-compression, etc. These compression standards use 15 video signal transforms and intra- and inter-frame coding that exploits spatial and temporal correlations among pixels of a frame and across frames.

However, these compression techniques create a number of well-known, undesirable and unacceptable artifacts, such as blockiness, low resolution and wiggles, among others. These are particularly problematic for 20 broadcast TV (satellite TV, cable TV, etc.) or for systems with very low bit rate (video conferencing, video phone).

Much research has been performed to try and improve the standard compression techniques. The following articles and patents discuss various prior art methods to do so: 1 134182/2

Raj Malluri et al, “A Robust, Scalable, Object-Based Video Compression

Technique for Very Low Bit-Rate Coding," IEEE Transactions of Circuit and

Systems for Video Technology, vol. 7, No. 1, Feb. 1997;

Awadkh. Al-Asmari, “An Adaptive Hybrid Coding Scheme for HDTV and 5 Digital Sequences,” IEEE Transactions on Consumer Electronics, vol. 42, No. 3, pp. 926-936, Aug. 1995;

Kwok-tung Lo and Jian Feng, “Predictive Mean Search Algorithms for Fast VQ Encoding of Images,” IEEE Transactions On Consumer Electronics, vol. 41, No. 2, pp. 327-331, May 1995; io James Goel et al. “Pre-processing for MPEG Compression Using

Adaptive Spatial Filtering”, IEEE Transactions On Consumer Electronics, “ vol. 41, No. 3, pp. 687-698, Aug. 1995;

Jian Feng et al. “Motion Adaptive Classified Vector Quantization for ATM Video Coding”, IEEE Transactions on Consumer Electronics, vol. 41, No. 2, p. 15 322-326, May 1995;

Austin Y. Lan et al., “Scene-Context Dependent Reference - Frame Placement for MPEG Video Coding," IEEE Transactions On Circuits and Systems for Video Technology, vol. 9, No. 3, pp. 478-489, Apr. 1999;

Kuo-Chin Fan, Kou-Sou Kan, “An Active Scene Analysis-Based 20 approach for Pseudoconstant Bit-Rate Video Coding”, IEEE Transactions On Circuits and Systems for Video Technology, vol. 8 No. 2, pp. 159-170, Apr. 1998;

Takashi Ida and Yoko Sambansugi, “Image Segmentation and Contour Detection Using Fractal Coding”, IEEE Transactions On Circuits and Systems for Video Technology, vol. 8, No. 8, pp. 968-975, Dec. 1998; 2 1

Liang Shen and Rangaraj M. Rangayyan, “A Segmentation-Based Lossless Image Coding Method for High-Resolution Medical Image Compression,” IEEE Transactions On Medical Imaging, vol. 16, No. 3, pp. 301-316, June 1997; 5 Adrian Munteanu et al., “Wavelet-Based Lossless Compression of

Coronary Angiographic Images”, IEEE Transactions On Medical Imaging, vol. 18, No. 3, p. 272-281, March 1999; and

Akira Okumura et al., “Signal Analysis and Compression Performance Evaluation of Pathological Microscopic Images,” IEEE Transactions on Medical io Imaging, vol. 16, No. 6, pp. 701-710, Dec. 1997. 3

SUMMARY OF THE INVENTION

<img img-format="tif" img-content="drawing" file="IL134182AD00022.tif" id="idf0002" />

An object of the present invention is to provide a method and apparatus for vision compression which is generally lossless vis-a-vis what the human eye perceives. 5 There is therefore provided, in accordance with a preferred embodiment of the present invention, a visual lossless pre-processor for processing a video frame prior to compression by a video encoder. The pre-processor includes a unit which identifies a plurality of threshold levels, one per pixel ofthe video frame, above which a human eye can distinguish the pixel 10 from among the other pixels of the frame, a unit which associates the pixels of the video frame into subclasses and a unit which alters the intensity of each pixel ofthe video frame according to subclass and to whether or not the pixel is distinguished.

BRIEF DESCRIPTION OF THE DRAWINGS

<img img-format="tif" img-content="drawing" file="IL134182AD00023.tif" id="idf0003" />

The present invention will be understood and appreciated more fully from the following detailed description taken in conjunction with the appended drawings in which: 5 Fig. 1 is an example of a video frame;

Fig. 2 is a block diagram illustration of a video compression system having a visual lossless pre-processor, constructed and operative in accordance with a preferred embodiment of the present invention;

Fig. 3 is a block diagram illustration of the details of the visual lossless io pre-processor of Fig. 2;

Fig. 4 is a graphical illustration of the transfer functions for a number of high pass filters useful in the pre-processor of Fig. 3;

Figs. 5A and 5B are block diagram illustrations of alternative embodiments of a filter bank forming part of the pre-processor of Fig. 3; 15 Fig. 6 is a graphical illustration of the transfer functions for a number of low pass filters useful in the filter bank of Figs. 5A and 5B;

Fig. 7 is a graphical illustration of the transfer function for a non-linear filter useful in the filter bank of Figs. 5A and 5B;

Figs. 8A, 8B and 8C are block diagram illustrations of alternative 20 embodiments of an inter-frame processor forming part of the pre-processor of

Fig. 3;

Fig. 9 is a block diagram illustration of a spatial-temporal analyzer forming part of the pre-processor of Fig. 3;

Figs. 10A and 10B are detail illustrations of the analyzer of Fig. 9; and

Fig. 11 is a detail illustration of a frame analyzer forming part of the pre-processor of Fig. 3. 134182/2

DETAILED DESCRIPTION OF THE PRESENT INVENTION 10 15 20 25

Applicants have realized that there are different levels of texture detail in an image and that the human eye perceives these details in different ways. In particular, Applicants have realized the following: 1. Texture details whose detection mainly depends on the level of noise in the image occupy approximately 50 - 80% of an image. 2. A visual perception threshold T for texture details does not depend on the shape of the object in the image. 3. Visual perception threshold T depends on a number of things, including the general brightness of the image. It does not depend on the noise spectrum.

Using the above facts, the present invention is a method for describing, and then encoding, images based on which objects in the image can be clearly perceived by the human eye and which ones can only be detected by it.

Reference is now made to Fig. 1, which is a grey-scale image of a plurality of shapes of a bird in flight, ranging from a photograph of one (labeled 10) to a very stylized version of one (labeled 12). The background of the image is a vignette which is very dark at the top of the image and very light at the bottom of the image.

The human eye can distinguish most of the birds of the image. However, there is at least one bird, labeled 14, which the eye can detect but cannot determine all of its details. Furthermore, there are large swaths of the image (ip the background) which have no objects in them.

The present invention is a method and system for pre-processing images before they are sent to a standard video compression unit. The present 7 invention separates the details of an image into two different types, those that can only be detected (for which only one bit will suffice to describe each of their pixels) and those which can be distinguished (for which at least three bits are needed to describe each of their pixels).

Reference is now made to Fig. 2, which illustrates the present invention within an image transmission system. Thus, Fig. 2 shows a visual lossless (VLS) pre-processor 20 connected to a standard image transmitter 22 which includes a video compression encoder 24, such as a standard MPEG encoder, and a modulator 26. VLS pre-processor 20 preprocesses an incoming video signal such that video compression encoder 24 can significantly compress the video signal, resulting in a reduced size signal to be transmitted. Typical compression ratios for the combined VLS pre-processor / video compression encoder are 60 - 100 which is generally twice that of the video compression encoder by itself.

Modulator 26 modulates the reduced size signal and transmits it to a receiver 30, which, as in the prior art, includes a demodulator 32 and a decoder 34. Demodulator 32 demodulates the transmitted signal and decoder 34 decodes and decompresses the demodulated signal. The result is provided to a monitor 36 for display.

It will be appreciated that, although the compression rates are high in the present invention, the resultant video displayed on monitor 36 is not significantly degraded. This is because pre-processor 20 attempts to quantify each frame of the video signal according to which sections of the frame are more or less distinguished by the human eye. For the less-distinguished sections, pre-processor 20 provides pixels of a minimum bit size, thus reducing 134182/2 the overall size (in bits) of the frame. Since the human eye does not distinguish these sections, the reproduced frame does not appear significantly different than the original frame, despite its smaller size (in bits).

Reference is now made to Fig. 3, which details the elements of VLS pre- 5 processor 20. Pre-processor 20 comprises a memory 40, a frame analyzer 42, a processor 44, a frame memory 46 and an interframe updater 48. Analyzer 42 analyzes each frame to separate it into subclasses, where subclasses define areas which are distinguished and those which are not as well as areas which describe objects of large size and which of small size. Processor 44 spatially io filters each pixel of the frame according to its subclass and, optionally, also provides each pixel of the frame with the appropriate number of bits. Interffame updater 48 provides temporal filtering (i.e. inter-frame filtering) and updates frame memory 46 with the elements of the current frame which are different than those of the previous frame. 15 It is noted that frames are composed of pixels, each having three color components, each of which is typically defined by eight bits. VLS pre-processor 20 generally separately processes the three components. The following discusses the operation on the luminance signal Y, it being appreciated that the operation for the chrominance signals Cr and Cb is similar. However, the 20 bandwidth of the chrominance signals is half as wide as that of the luminance signal. Thus, the filters (in the x direction of the frame) for chrominance have a narrower bandwidth. The following discussion shows the filters for the luminance signal.

Frame analyzer 42 comprises a spatial-temporal analyzer 50, a 25 parameter estimator 52, a visual perception threshold determiner 54 and a 9

<img img-format="tif" img-content="drawing" file="IL134182AD00024.tif" id="idf0004" />

subclass determiner 56. Details of these elements are provided in Figs. 9-11, discussed hereinbelow.

As discussed hereinabove, areas which the human eye distinguishes are ones of high contrast or high information content. Areas of high contrast are 5 areas with a lot of high frequency content. Thus, spatial-temporal analyzer 50 generates a plurality of filtered frames from the current frame, each filtered through a different high pass filter (HPF), where each high pass filter retains a different range of frequencies therein.

Fig. 4, to which reference is now briefly made, is an amplitude vs. io frequency graph illustrating the transfer functions of an exemplary set of high pass filters. Four graphs are shown. It can be seen that the curve labeled HPF-R3 has a cutoff frequency of 1 MHz and thus, retains portions of the frame with information above 1MHz. Similarly, curve HPF-R2 has a cutoff frequency of 2 MHz, HPF-C2 has a cutoff frequency of 3MHz and HPF-R1 and HPF-C1 15 have a cutoff frequency of 4MHz. As will be discussed hereinbelow, the terminology “Rx” refers to operations on a row of pixels while the terminology “Cx” refers to operations on a column of pixels.

In particular, the filters of Fig. 4 implement the following finite impulse response (FIR) filters on either a row of pixels (the x direction of the frame) or a 20 column of pixels (the y direction of the frame), where the number of pixels used in the filter defines the power of the cosine. For example, a filter implementing cos10x takes 10 pixels around the pixel of interest, five to one side and five to the other side of the pixel of interest. HPF-R3: 1 - cos10x 25 HPF-R2:1-cos6x 10 HPF-R1: 1-cos2x HPF-C2: 1-cos4y HPF-C1: 1-cos2y

The high pass filters can also be considered as digital equivalents of optical apertures. The higher the frequency range, the smaller the aperture.

Thus, filters HPF-R1 and HPF-C1 retain only very small details in the frame (of 1-4 pixels in size) while filter HPF-R3 retains much larger details (of up to 10 pixels).

In the following, the filtered frames will be labeled by the type of filter (HPF-X) used to create them.

Returning to Fig. 3, analyzer 50 also generates difference frames between the current frame and another, earlier frame. The previous frame is typically at most 15 frames earlier. A “group” of frames is a series of frames for which difference frames are generated.

Parameter estimator 52 takes the current frame and the filtered and difference frames and generates a set of parameters that describe the information content of the current frame. The parameters are determined on a pixel-by-pixel basis or on a per frame basis, as relevant. It is noted that the parameters do not have to be calculated to great accuracy as they are used in combination to determine a per pixel, visual perception threshold THD,.

At least some of the following parameters are determined:

Signal to noise ratio (SNR): this parameter can be determined by generating a difference frame between the current frame and the frame before it, filtering out the high frequency content of the difference frame and summing the intensities of the pixels in the filtered frame. 11

<img img-format="tif" img-content="drawing" file="IL134182AD00025.tif" id="idf0005" />

Normalized amount of change ΝΔ,: this measures the amount of change Δ,, per pixel i, from the current frame to its previous frame, normalized by the maximum intensity Imax possible for the pixel. If the frame is a television frame, the maximum intensity is 255. 5 Normalized volume of change ΝΙχγ: this measures the volume of change in a frame Ιχγ, normalized by the maximum possible amount of information MAXinfo within a frame (i.e. 8 bits per pixel x N pixels per frame). Since the highest frequency range indicates the amount of change in a frame, the volume of change Ιχγ is a sum of the intensities in the filtered frame having io the highest frequency range, such as filtered frame HPF-R1.

Normalized volume of interframe changes NIf: this measures the volume of changes If between the current frame and its previous frame, normalized by the maximum possible amount of information MAXinfo within a frame. The volume of interframe changes If is the sum of the intensities in the 15 difference frame.

Normalized volume of change within a group of frames NIgop: this measures the volume of changes Igop over a group of frames, where the group is from 2 to 15 frames, as selected by the user. It is normalized by the maximum possible amount of information MAXinfo within a frame and by the 20 number of frames in the group.

Normalized luminance level ΝΥμ Y, is the luminance level of a pixel in the current frame. It is normalized by the maximum intensity Imax possible for the pixel. 12

Color saturation ρμ this is the color saturation level ofthe ith pixel and it

<img img-format="tif" img-content="drawing" file="IL134182AD00026.tif" id="idf0006" />

is determined by: 0.78 ,-128 V ../G,.-128 -|l/2 160 + 0.24 -'ά,Ζ 126 where Cri is the amount of red in the ith pixel and Cb,i is the amount of blue in the ith pixel.

Hue h,: this is the general hue of the ith pixel and is determined C,-128' 5 by: arctan 1.4- Q,-128

Visual perception threshold determiner 54 determines the visual perception threshold THD| as follows:

200 Ί SNR J THDi =THDA 1 + ΝΔ; + ΝΙχγ + NIf + NIgop + NY( + Pi +1η +

Subclass determiner 56 compares each pixel i of each high pass io filtered frame HPF-X to its associated threshold THD, to determine whether or not that pixel is significantly present in each filtered frame, where “significantly present” is defined by the threshold level and by the “detail dimension” (i.e. the size of the object or detail in the picture of which the pixel forms a part).

Subclass determiner 56 then defines the subclass to which the pixel belongs. 15 For the example provided above, if the pixel is not present in any of the filtered frames, the pixel must belong to an object of large size or it. If the pixel is only found in the filtered frame of HPF-C2 or in both frames HPF-C1 and HPF-C2, it must be a horizontal edge (an edge in the Y direction of the frame). If it is found in filtered frames HPF-R3 and HPF-C2, it is a single small detail. If 20 the pixel is found only in filtered frames HPF-R1, HPF-R2 and HPF-R3, it is a very small vertical edge. If, in addition, it is also found in filtered frame HPF-C2, then the pixel is a very small, single detail. 13

<img img-format="tif" img-content="drawing" file="IL134182AD00027.tif" id="idf0007" />

The above logic is summarized and expanded in Table 1.

<img img-format="tif" img-content="drawing" file="IL134182AD00028.tif" id="idf0008" />

Table 1

High Pass Filters Subclass Rl R2 R3 Cl C2 Remarks 1 0 0 0 0 0 Extended detail or detail detected only 2 0 0 0 0 1 Horizontal edge 3 0 0 0 1 1 Horizontal edge 4 0 0 1 0 0 Vertical edge 5 0 0 1 0 1 Single small detail 6 0 0 1 1 1 Single small detail 7 0 1 1 0 0 Vertical edge 8 0 1 1 0 1 Single small detail 9 0 1 1 1 1 Single small detail 10 1 1 1 0 0 Very small vertical edge 11 1 1 1 0 1 Very small single detail 12 1 1 1 1 1 Very small single detail

The output of subclass determiner 56 is an indication of the subclass to 5 which each pixel of the current frame belongs. Processor 44 performs spatial filtering of the frame, where the type of filter utilized varies in accordance with the subclass to which the pixel belongs. Processor 44 changes the intensity of the pixel by an amount less than the visual distinguishing threshold for that pixel. Pixels whose contrast is lower than the threshold are transformed with the io non-linear filters. If desired, the data size of the pixel can be reduced from 8 bits to 3 or 4 bits, depending on the visual threshold level and the detail dimension for the pixel.

Processor 44 comprises a filter bank 60 and a filter selector 62. Filter bank 60 comprises a set of low pass and non-linear filters, shown in Figs. 5A 15 and 5B to which reference is now made, which filter selector 62 activates, based on the subclass to which the pixel belongs. Selector 62 can activate more than one filter, as necessary.

Figs. 5A and 5B are two, alternative embodiments of filter bank 60.

Both comprise two sections 64 and 66 which operate on columns and rows, 20 respectively. In each section 64 and 66, there is a choice of filters, each 14 134182/2 controlled by an appropriate switch, labeled SW-X, where X is one of CO, C1,

C2, RO, R1, R2, R3 (selecting one of the low pass filters (LPF)) or D-C, D-R (selecting to pass the relevant pixel directly). Filter selector 62 switches the relevant switch, thereby activating the relevant filter. It is noted that the non-linear 5 filters (NLF) are activated together with low pass filter LPF-R3 and the outputs of the two filters are summed.

Filter bank 60 also includes time adjusters (TA) which add any necessary delays to ensure that the pixel currently being processed remains at its appropriate location within the frame. io The low pass filters (LPF) are associated with the high pass filters used in analyzer 50. Thus, the cutoff frequencies of the low pass filters are close to those of the high pass filters. The low pass filters thus pass that which their associated high pass filters ignore.

Fig 6, to which reference is now briefly made, illustrates exemplary low 15 pass filters for the example provided hereinabove. Low pass filter LPF-R3 has a cutoff frequency of 0.5MHz and thus, generally does not retain anything which its associated high pass filter HPF-R3 (with a cutoff frequency of 1MHz) retains. Filter LPF-R2 has a cutoff frequency of 1MHz, filter LPF-C2 has a cutoff frequency of 1.25MHz and filters LPF-C1 and LPF-R1 have a cutoff frequency of 20 about 2MHz. As for the high frequency filters, filters LPF-Cx operate on the columns of the frame and filters LPF-Rx operate on the rows of the frame.

Fig. 7, to which reference is now briefly made, illustrates an exemplary transfer function for the non-linear filters (NLF). The transfer function defines an output value Vout normalized by the threshold level THDj as a function of an 25 input value Vin also normalized by the threshold level THDj. As can be seen in 15 9 the figure, the input - output relationship is described by a polynomial of high order. A typical order might be six, though lower orders, of power two or three, are also feasible.

Table 2 lists the type of filters activated per subclass, where the header 5 for the column indicates both the type of filter and the label of the switch SW-X of Figs. 5A and 5B.

Table 2

Low Pass Filters Subclass Rl R2 R3 Cl C2 D-R D-C 1 0 0 1 0 1 0 0 2 0 0 1 1 0 0 0 3 0 0 1 0 0 0 1 4 0 1 0 0 1 0 0 5 0 1 0 1 0 0 0 6 0 1 0 0 0 0 1 7 1 0 0 0 1 0 0 8 1 0 0 1 0 0 0 9 1 0 0 0 0 0 1 10 0 0 0 0 1 1 0 11 0 0 0 1 0 1 0 12 0 0 0 0 0 1 1

Fig. 5B includes rounding elements RND which reduce the number of 10 bits of a pixel from eight to three or four bits, depending on the subclass to which the pixel belongs. Table 3 illustrates the logic for the example presented hereinabove.

Table 3 RND-PO(Zl) RND-P1 (Z2) RND-P2 (Z3) RND-L0 (Z4) RND-L1 (Z5) subclass "1" equal 8 bit "1" equal 8 bit "1" equal 8 bit " 1" equal 8 bit "1" equal 8 bit "0" equal 3 bit "0" equal 4 bit "0" equal 4 bit "0" equal 3 bit "0" equal 4 bit 1 1 1 1 1 1 2 1 1 1 1 0 3 1 1 1 1 1 4 1 1 1 1 1 5 1 1 0 1 0 6 1 1 1 1 1 7 1 1 1 1 1 8 1 0 1 0 1 9 1 1 1 1 1 10 1 1 1 1 1 11 1 1 1 1 1 12 1 1 1 1 1 16 134182/2

The output of processor 44 is a processed version of the current frame, typically having fewer bits than the original version.

Reference is now made to Figs. 8A, 8B and 8C, which illustrate three alternative embodiments for interframe updater 48 which provides temporal filtering (i.e. 5 inter-frame filtering) to further process the current frame. Since the present invention provides a full frame as output and since frame memory 46 stores the previous frame, interframe updater 48 determines which pixels have changed significantly from the previous frame and amends those only, storing the new version in the appropriate location in frame memory 46. io The embodiments of Figs. 8A and 8B are open loop versions while the embodiment of Fig. 8C is a closed loop version. All of the embodiments comprise a summer 68, a low pass filter (LPF) 70, a high pass filter (HPF) 72, two comparators 74 and 76, two switches 78 and 80, controlled by the results of comparators 74 and 76, respectively, and a summer 82. is Summer 68 takes the difference of the processed current frame, produced by processor 44, and the previous frame, stored in frame memory 46. The difference frame is then processed in two parallel tracks.

In the first track, it is low pass filtered with either a cos6x filter (for broadcast frames) or a cos10x filter (for video conferencing). Each pixel of the filtered frame is 20 compared by comparator 74 to a general threshold THD-LF which is typically set to 5% of the maximum expected intensity for the frame. Thus, the pixels which are kept (i.e. for which switch 78 is set to pass the pixel) are only those which changed by more than 5%.

In the second track, the difference frame is high pass filtered with either a 1-cos6x filter (for broadcast frames) or a 1-cos10x filter (for video 25 conferencing). Since high pass filtering retains the small details, each pixel of 17 the high pass filtered frame is compared to the particular threshold THD, for that pixel, as produced by threshold determiner 54. If the difference pixel has an intensity above the threshold THD, (i.e. the change in the pixel is significant), it is allowed through (i.e. switch 80 is set to pass the pixel). 5 Summer 82 adds the filtered difference pixels passed by switches 78 and I or 80 with the pixel of the previous frame to produce the new pixel. If switches 78 and 80 did not pass anything, the new pixel is the same as the previous pixel. Otherwise, the new pixel is the sum of the previous pixel and one or more difference pixels. io Reference is now briefly made to Figs. 9, 10A, 10B and 11 which detail elements of frame analyzer 42. In these figures, the term "ML" indicates a line of the current frame, "MP" indicates a pixel of the current frame, "MF" indicates a frame, "VD" indicates the vertical drive, "TA" indicates a time adjustment, e.g. a delay, and CNT indicates a counter. 15 Fig. 9 generally illustrates the operation of spatial-temporal analyzer 50 and Figs. 10A and 10B provide one detailed embodiment for the spatial analysis and temporal analysis portions 51 and 53, respectively. Fig. 11 details parameter estimator 52, threshold determiner 54 and subclass determiner 56. As these figures are deemed to be self-explanatory, no further explanation will 20 be included here.

The methods and apparatus disclosed herein have been described without reference to specific hardware or software. Rather, the methods and apparatus have been described in a manner sufficient to enable persons of ordinary skill in the art to readily adapt commercially available hardware and 25 software as may be needed to reduce any of the embodiments of the present 18

<img img-format="tif" img-content="drawing" file="IL134182AD00029.tif" id="idf0009" />

invention to practice without undue experimentation and using conventional techniques.

It will be appreciated by persons skilled in the art that the present invention is not limited by what has been particularly shown and described 5 herein above. Rather the scope of the invention is defined by the claims that follow: 19