HAAR TRANSFORM DECODER

Background

When a display device is connected to a computing device, it is often necessary to encode (for example for compression) the display data generated on the computing device before it is transmitted to a display control device, where it is decoded for display on the display device. The display control device may be a docking station. In some cases, the display control device may be designed in hardware (hard-wired) to decode the encoded display data according to a particular process. Thus, in some cases, a display control device may be hard-wired to decode received encoded display data in a particular way, for example, by passing it using an inverse Haar transform a predetermined number of times.

Furthermore, it may be desirable to convert display data generated on the computing device to particular dimensions for display on the display device. This process is known as scaling. In this case, the received compressed (encoded) display data may need to be scaled on the display control device. This requires additional processing engines on the display control device, leading to increased expense and complexity of the display control device.

The invention therefore aims to solve or at least mitigate this problem. Summary

Therefore, in a first aspect the invention provides a method for processing display data at a host device for display on a remote display controlled by a remote display control device, wherein the remote display control device comprises a hardware decoder which is configured to perform a predetermined number of decoding passes using an inverse Haar transform on compressed encoded data, the method comprising: generating, at the host device, at least a portion of a frame of display data to be displayed on the remote display; compressing, at the host device, the generated display data, wherein the compressing comprises at least: determining a scaling factor for at least the portion of the frame of display data, wherein the scaling factor is 4x where x is a positive integer; determining a number of encoding passes of a Haar transform to be performed on the generated display data, the number of encoding passes being at least one but less than the predetermined number of decoding passes by the number x, performing the determined number of encoding passes of the generated display data using the Haar transform, wherein each encoding pass of the generated display data using the Haar transform produces a set of display coefficients, quantising the display coefficients to produce a set of quantised display coefficients, and rounding the quantised display coefficients, wherein the compressed encoded display data comprises rounded quantised display coefficients that have a non-zero value and information regarding rounded quantised display coefficients that have a zero value; transmitting, by the host device, the compressed encoded display data to the remote display control device; receiving, at the remote display control device, the transmitted compressed encoded display data from the host device; decoding, at the remote display control device, the received compressed data using the hardware decoder, wherein the decoding comprises performing the predetermined number of decoding passes of the received compressed encoded data using the inverse Haar transform, the predetermined number of decoding passes being at least two; and sending, from the remote display control device, the decoded display data to the remote display; wherein the number of encoding passes is less than the predetermined number of decoding passes, such that the predetermined number of decoding passes is the number of encoding passes plus one or more additional decoding passes, and wherein the decoding uses display coefficients having a zero value for each additional decoding pass.

According to a second aspect, the invention provides a system comprising: a host device configured to: generate at least a portion of a frame of display data to be displayed on the remote display; and compress the generated display data, wherein the compressing comprises: determining a scaling factor for at least the portion of the frame of display data, wherein the scaling factor is 4 ^X where x is a positive integer; determining a number of encoding passes of a Haar transform to be performed on the generated display data, the number of encoding passes being at least one, performing the determined number of encoding passes of the generated display data using the Haar transform, wherein each encoding pass of the generated display data using the Haar transform produces a set of display coefficients, quantising the display coefficients to produce a set of quantised display coefficients, and rounding the quantised display coefficients, wherein the rounded quantised display coefficients that have a non-zero value and information regarding rounded quantised display coefficients that have a zero value provides compressed encoded display data; and transmit the compressed encoded display data; and a display control device comprising a hardware decoder, the display control device configured to: receive the compressed encoded display data from the host device; decode the received compressed encoded data using the hardware decoder, wherein the decoding comprises performing a predetermined number of decoding passes of the received compressed encoded data using an inverse Haar transform, the predetermined number of decoding passes being at least two, wherein the number of encoding passes is less than the predetermined number of decoding passes by the number x, such that the predetermined number of decoding passes is the number of encoding passes plus the number x additional decoding passes, and wherein the decoding uses display coefficients having a zero value for each additional decoding pass; and send the decoded display data to a display

In one embodiment, the display coefficients having a zero value used in the decoding are generated at the host device and transmitted to the remote display control device with the compressed encoded display data. Alternately or additionally, the display coefficients having a zero value used in the decoding are generated at the remote display control device and added to the compressed encoded display data prior to the decoding.

In one embodiment, at least the portion of display data may form the whole of the frame and may be scaled prior to compressing. Alternately, the portion of display data may form less than the whole of the frame, and the method may further comprise generating, at the host device, a different portion of the frame of display data to be displayed on the remote display, and the compressing, at the host device, comprises performing a different number of encoding passes of the generated display data of the different portion than the number of encoding passes of the generated display data of the at least one portion, wherein the different number of encoding passes is less than the predetermined number of decoding passes, wherein the portion of display data may be scaled prior to compressing by a different amount than the different portion of display data.

According to a further aspect, an embodiment of the invention provides a method of scaling image data using decompression mechanisms, comprising:

1. Host generates a frame of display data

2. Host performs (i) passes of a Haar transform on the frame

3. Host transmits the display data to the display control device 4. Display control device performs (i+x) passes of a Haar transform on the received display data, using x sets of "0" coefficients for the additional pass(es)

5. Display control device sends the frame for display on a display device

To minimise the reduction of quality in the displayed frame, (x) should be a small number, preferably 1. However, more than 1 additional pass may be performed on the display control device.

This allows decompression to be used for scaling. As a result, hardware scalers can be removed from integrated circuits and scaling can be used in systems that otherwise would not have scaling available. This method is also quicker and simpler than other firmware scaling methods, and does not require additional data to be transmitted.

The "0" coefficients may be transmitted by the host along with the compressed display data, so the display control device is unaware of the fact that this scaling method is in use. This can be done without much additional data being transmitted on the connection between the host and the display control device because a string of 0s can be very efficiently compressed.

Alternatively, the display control device may be arranged to add the "0" coefficients and perform the additional decompression without the host being aware that the method is in use.

Naturally, where more than one additional pass is performed, such methods may be mixed: for example, if two additional passes are performed, one set of "0" coefficients may be transmitted by the host while a second is provided by the display control device.

Brief Description of the Drawings

Embodiments of the invention will now be more fully described, by way of example, with reference to the drawings, of which: Figure 1 shows a block diagram of a system according to the current art;

Figure 2 shows a simplified example of conventional Haar encoding and decoding;

Figure 3 shows a more complex example of conventional Haar encoding and decoding;

Figure 4 shows a block diagram of a system according to an embodiment of the invention; Figure 5 a simplified example of encoding and decoding according to an embodiment of the invention;

Figure 6 shows a general process according to an embodiment of the invention; and

Figures 7 A, 7B, and 7C show more complex examples of encoding and decoding according to embodiments of the invention.

Detailed Description of the Drawings

Figure 1 shows a block diagram overview of a system according to the current art. A host computer [11] is connected to a display control device [12], which is in turn connected to a display device [13]. The host [11] contains an application [14], which produces display data. The display data may be produced and sent for compression either as complete frames or as canvasses, which may, for example, be separate application windows. In either case, they are made up of tiles of pixels, where each tile is a geometrically-shaped collection of one or more pixels.

The display data is sent to a compression engine [15], which may comprise software running in a processor or an appropriate hardware engine. The compression engine [15] first performs an encoding of the data using a Haar transformation as hereinafter described to convert the data into a format that may then be further compressed, minimising data loss.

The compression engine [15] may then further compress the data and thereafter sends the compressed data to an output engine [16]. The output engine [16] manages the connection with the display control device [12] and may, for example, include a socket for a cable to be plugged into for a wired connection or a radio transmitter for a wireless connection. In either case, it is connected to a corresponding input engine [17] on the display control device [12]. The input engine [17] is connected to a decompression engine [18]. When it receives compressed data it sends it to the decompression engine [18] or to a memory from which the decompression engine [18] can fetch it according to the operation of a decompression algorithm. In any case, the decompression engine [18] may decompress the data, if necessary, and performs a decoding operation using a reverse Haar transform. The decompressed data is then sent to a scaler [19]. In the case where the display data was produced and compressed as multiple canvasses, it may be composed into a frame at this point.

It is preferable for scaling to be carried out on a display control device [12] as this minimises the volume of data to be transmitted from the host [11] to the display control device [12], and the scaler [19] operates to convert the received display data to the correct dimensions for display on the display device [13]. It is then sent to an output engine [110] for transmission to the display device [13]. This may include, for example, converting the display data to a display-specific format such as VGA, HDMI, etc.

The Haar transformation processes according to the current art will now be explained with reference to Figures 2 and 3. As previously mentioned, the Haar transform takes place on the host [11], specifically in the compression engine [15]. Decompression takes place on the display control device [12], specifically in the decompression engine [18], where the data is put through an inverse Haar transform to return it to its original form.

In the example shown in Figure 2, a group of four tiles [21] has been produced by the application [14] and passed to the compression engine [15] as previously described. In this example, each tile [21] comprises one pixel, but may be larger, as previously mentioned. Each pixel [21] has a value indicating its colour, here represented by the pattern of hatching. The first pixel [21 A] is marked with dots and considered to have the lightest colour. The second pixel [2 IB] is marked with diagonal hatching and is considered to have the darkest colour. The third pixel [21C] is marked with vertical hatching and is considered to have a light colour, and the fourth pixel [2 ID] is marked with horizontal hatching and is considered to have a dark colour. The values of the four pixels [21] are combined using the formulae [24] shown to the right of the Figure to produce a single pixel value [22], referred to as "W", which is shaded in grey to indicate that its value is derived from the original four pixels [21], as well as a set of coefficients [23] referred to in Figure 2 as "x, y, z". The pixel value [22] is generated from a sum of the values of all four pixels: ((A+B)+(C+D)). The three coefficients [23] are generated using the other three formulae [24] as follows:

• x: (A-B)+(C-D)

• y: (A+B)-(C+D)

• z: (A-B)-(C-D) Any or all of these values may then be quantised: divided by a constant in order to produce a smaller number which will be less accurate but can be more effectively compressed and rounded.

The reverse transform process is carried out on the single pixel value [22] and coefficients [23] produced in the transform as described above. This process will be carried out after a decompression process, which might involve, for example, multiplying quantised coefficients to restore an approximation of their original values.

The decompression engine [18] combines the coefficients [23] with the value of the pixel value [22] transmitted by the host [11] to recreate the original four pixels [25] using the formulae [26] shown to the right of Figure 2.

• A: W+x+y+z

• B: W-x+y-z

• C: W+x-y-z

• D: W-x-y+z This is repeated the same number of times that the data was transformed. These pixels [25] are then transmitted to the scaler [19].

Figure 3 shows an example of the actual process of a Haar transform according to current art. The top part of the encode section shows 64 tiles, each numbered in order from 0. These numbers are used to indicate the values of the tiles as previously mentioned. The tiles are divided into groups of four: for example, the top-left group comprises tiles 0, 1, 8, and 9.

At each pass, the same calculations are performed on a larger range of tile groups to produce combined pixel values and coefficients. In the first pass, Step S31, the tiles in each group are processed using the previously-mentioned formulae [24]. This converts the values in the circled first group to 18, -2, 16, 0 and these values are stored and used in place of the original values. In this example, 18 is the pixel value "W" [22] described in Figure 2 and -2, -16, and 0 are the coefficients "x", "y", and "z" [23] described in Figure 2. The same process is carried out on all the groups. These results are shown in the second section of the process, after Step S31. The second pass, Step S32, applies the same formulae [24] to the top-left tiles in each set of four tile groups. The values to be used in the top-left quarter of the frame in the second pass are shown circled: 18, from the top-left group, 26 from the group to the immediate right, 82 from the group below, and 90 from the final group in the upper-left quarter. The same formulae [24] are then applied to these values to produce 216, -16, - 128, and 0, which are put in the places of the original values. Again, these values correspond to W [22], x, y, and z [23] as described in Figure 2. The same process is carried out on all four quarters, and all other values are unchanged: for example, in the top-left group the three values not used in the second pass of the transform and not circled are unchanged from -2, -16, and 0.

The third pass, Step S33, is carried out on one value from each quarter, as shown circled in Figure 2: 216 from the top-left quadrant, 280 from the top-right quadrant, 728 from the bottom-left quadrant, and 792 from the bottom-right quadrant. This produces the final results shown at the bottom of the encode section: 2016 (W), -128 (x), -1024 (y), and 0 (z). Once again, all the other values are unchanged.

The values can then be rearranged so that the different coefficients are grouped together. The pixel values at each level are transmitted first, prioritising the results of later passes, followed by the coefficients. This will result in many small numbers, including many identical numbers: for example, there is a 0 in the same position in each group after the third pass, and these can be grouped and sent as a single number. The values may also be quantised: divided by a constant to produce smaller coefficients and rounded, if desired.

At Step S34, the data is transmitted from the host [11] to the display control device [12], where it is decompressed, de-quantised and re-ordered as appropriate prior to decoding. In this example, these processes produce the same data as was generated by the initial transform, and this table is shown at the beginning of the Decode section. A similar process is then performed to reverse the transform process, as previously mentioned.

At Step S35, the first pass is performed and the formulae [26] described in Figure 2 are applied to the circled top-left tile from each quadrant: as mentioned after the third pass of the encode stage, in this pass, and this example, the figures are: 2016 (W [22]), - 128 (x [23]), -1024 (y [23]), and 0 (z [23]). This produces a new W value [22] for each quadrant: 216, 280, 728, and 792. At Step S36, the second pass is carried out. It takes the top-left value from each group in each quadrant (W:216 [22], x: -16, y: -128, z: 0 [23]) and applies the same formulae [26] to them. Finally, the same formulae [26] are applied to every value in each group in the third pass: Step S37. This produces the same values as were input at the beginning of the encode section.

Such a transform is useful because not only does it allow the host [11] to transmit a smaller number of pixels than are present in the full image data, combined with a collection of coefficients, but the coefficients can be compressed more efficiently than pixel data, with less loss of data; they are small numbers and so can be transmitted in fewer bits without any further compression being applied.

Turning now to Figure 4, there is shown a block diagram overview of a system according to one embodiment of the invention. For the most part, Figures 1 and 4 are identical, but the system shown in Figure 4 lacks a separate scaler [19]. This is because this embodiment of the invention allows the scaling functionality to be carried out in the decompression engine [18]. The decompression engine [19] may be hard-wired to carry out the decompression, or may be programmed independently. However, it will usually be the case that the number of passes of the inverse Haar transform will be predetermined and fixed.

Figures 5 and 6 show how this system allows a Haar transform process to be used for scaling.

As shown in Figure 5, similarly to Figure 2, a group of four tiles [51] is produced by the application [14] and transformed to produce pixel values [52] and coefficients [53] which are then transmitted to the display control device [12]. However, either prior to transmission or upon receipt, several more 0 coefficients [54] are added to the pixel values [52]. These are shown below the pixel value [52] in the display control device [12]. It will be apparent that since the decompression engine in the display control device is arranged to perform a predetermined number of decoding passes using the Haar transform, by selecting fewer passes of the Haar transform at the encoding stage, and adding an appropriate number of "0" coefficients, scaling can be achieved at the decompression engine without any further processing or different decoding being performed at the display control device. These added 0 coefficients [54] allow a reverse transform to be used to scale the data generated by the application [14], as shown by the fact that while the conventional process shown in Figure 2 generates a grid of four tiles [25], each with a different pattern, the process according to the present embodiment also generates a grid of four tiles [55], but, where each tile now has four pixels instead of a single pixel, each tile having a different pattern. Accordingly, each tile is now four times as large as the original tile.

Figure 6 shows an example of the process from the initial generation of the frame.

At Step S61, the host [11] determines the scaling factor to be used. This will always be a power of 4 - for example, four times, sixteen times, etc., and is used to determine the quantisation and the size of the initial frame to be generated. It may be hard-coded in the compression engine [15] or may depend on the size of the connected display panel [13], and there may be different scaling factors for each part of the frame. In this case, this process will be repeated as appropriate for each part of the frame. At Step S62, the application [14] generates the downscaled frame. This is done in the conventional way, except at a smaller size and resolution than is conventional. The size and resolution are determined by the scaling factor, such that if the scaling factor is 4 (i.e. 4 ¹ ) then the downscaled frame will be generated at one-quarter size; if it is 16 (4 ² ) the downscaled frame will be generated at one-sixteenth size, etc. The exponent mentioned acts to determine the difference between the number of passes of the Haar transform used to encode the data and the number of passes of the reverse Haar transform used to decode the data. For example, if the scaling factor is 4, the difference between the number of passes is 1, since 4 is 4 ¹ . Correspondingly, 16 is 4 ² , so the difference between the number of passes is 2, and so forth; in the example shown in Figure 7, two passes are used at encoding and three are used in decoding; the data is then scaled by 4.

At Step S63, the compression engine [15] encodes the frame using a Haar transform as described with reference to Figure 7 A or Figure 7B. The encoded frame can then be further quantised and compressed. It is then transmitted to the display control device [12] at Step S64.

The display control device [12] receives the compressed data and decompresses it as appropriate, according to the compression used. In the decompression engine [18], it then decodes the received data as described below in Figure 7C at Step S65. This decoding process will increase the dimensions of the frame by the scaling factor as described with reference to Figure 5 and elaborated with reference to Figure 7C. Finally, at Step S66, it transmits the up-scaled frame to the display panel [13] for display.

A more detailed description of this embodiment using the Haar transform is shown in Figures 7A, 7B, and 7C, where Figures 7A and 7B show encoding transform methods and 7C shows the inverse transform used in decoding.

Figure 7A shows a method of encoding where the additional 0 coefficients [54] are added on the host [11], prior to reordering and further compression. First, the application [14] generates a frame of display data at one quarter the size that will be required for display. This may mean generating a frame at full resolution for a large display or, as in this example, which uses the same frame with the same numbering as in the previous examples, generating it at one quarter resolution. This is shown in Figure 7A by the fact that only even-numbered tiles are generated.

The quarter-sized frame [51] is divided into square tiles of width and height of 2 ¹ pixels. For each tile at Step S7A1, a first-pass Haar transform is carried out on the quarter-size frame [51]. This will operate as previously described in Figure 3, by applying the formulae [24] given in Figure 2 to the tiles in each group of four tiles and replacing the actual values with the results.

At Step S7A2, a second-pass Haar transform is carried out, using values from the four quadrants of the frame as previously described.

Naturally, in a larger frame more tiles will be needed, but, in any case, fewer tiles and fewer passes will be required than for a full-sized frame. The number of passes of the Haar transform to be carried out is predetermined when the encoder is programmed. The simplest case, as here, is for the same number of passes to be carried out on each part of the frame. However, in some embodiments, different parts of the frame may be generated at different sizes and resolutions such that part of the frame is generated at quarter size, as described here, and part is generated at one-sixteenth size. A relatively smaller number of passes may then be carried out on the one-sixteenth-size part of the frame compared to the one-quarter-size part at the encoding stage. Quantisation is then performed at Step S7A3, but in this method instead of dividing each tile value by the quantisation value (in this case, 4, though in practice different quantisation values may be used and the quantisation value may change within the frame) the quantisation value is first divided by 4 since the display data values are a quarter of the size due to the use of a smaller frame. This means that in this example no change is made to the data by quantisation, which in turn means that smaller values can be transmitted without any further data loss: if the values at this stage in the transform are compared to the values after the third pass in Figure 2, they can be seen to be smaller: for example, the top-left value in Figure 2 is 2016 while in Figure 7A it is 432. This means that less data is transmitted. To reduce the size of the values in the conventional method, quantisation is necessary: 2016 divided by 4 is 540, which in this case is a larger value and in other parts of the frame data will have been lost as small coefficients are converted to 0s.

Naturally, because in this example no actual change to the data occurs on quantisation, this step can be omitted entirely. This will save on unnecessary processing, but will make the method less flexible. The values will still need to be multiplied by the quantisation value prior to decoding, as hereinafter described. This multiplication is preferably performed at the decompression engine [18] and the quantisation value or values can be stored on the decompression engine [18] or transmitted with the data. Alternatively, the multiplication can be performed on the compression engine [15].

At Step S7A4, the additional 0 coefficients [54] are added to the data. In this example, this means adding 48 0s, making each tile from the frame after quantisation into a tile group with itself and three 0s. The resulting frame is then reordered at Step S71 to group the additional 0s at the end of the data, meaning that during compression they can be rendered as a single number: a count of the number of collected 0s.

The compressed data is then transmitted to the display control device [12] at Step S72, along with the quantisation value if this is not already available on the display control device [12]. Figure 7B shows an alternative transform method. This method is largely identical: two passes of the Haar transform are carried out on a quarter-sized frame at Steps S7B1 and S7B2 to produce the same values as described in Figure 7A. Similarly, at Step S7B3 the quantisation value 4 is used, but it is divided by 4 before being used as a divisor for the data, and thus there is no change to the data.

Unlike Figure 7A, however, the 0 coefficients [54] are not added as part of the transform process. Instead, the data is reordered before the 0 coefficients are added, and they may either be added during or after compression as a simple count of 48 0s, since they will be transmitted at the end of the data stream in either case. Alternatively, they may be added on the display control device [12] after the data is transmitted and received.

In any case, the data is transmitted at Step S72, along with the quantisation value if necessary, and received by the display control device.

Figure 7C shows the reverse transform that could be used after either of the transform methods described in Figures 7 A and 7B. This part of the process begins after the display data has been received and decompressed by the display control device [12]. This includes restoring the original data order, which means that if the additional 0 coefficients [54] described with reference to Figure 7B were added after reordering they will be added to the frame here. Likewise, if they are added on the display control device [12], they will be added at this point.

As a result, regardless of the exact encoding method used, the decoding process begins with the data as produced at the end of the encoding method described in Figure 7A, including additional 0 coefficients [54]. It can therefore be decoded as a frame [55] four times larger than the frame [51] that was originally generated.

At Step S73, the frame is de-quantised using the quantisation value, which might be transmitted with the display data at Step S72 or stored on the decompression engine [18]. Each value is multiplied by the un-modified quantisation value, which in normal cases would reverse the reduction in data size produced by quantisation. The display control device [12] does not need to be aware that the transform and initial quantisation was carried out in an unconventional way.

In some embodiments, Step S73 could be omitted, but this would result in significant data loss. Accordingly, at Steps S74, S75, and S76 three passes of the Haar transform are carried out at described with reference to Figure 2; an additional pass is required because of the increase in size of the frame. The number of decoding passes is also predetermined, but at least one more pass must be made during the decoding process than was made during the encoding process for scaling to occur, so if one encoding pass was made, at least two decoding passes must be made, and so forth. The 0 coefficients indicate a large amount of repetition in the data, and as a result after the final pass each tile group contains four identical pixels. This means that the data [51] generated on the host [11] has been increased in size by a factor of four without any additional scaler [19] being required.

Finally, the decoded display data is sent to the display panel [13] for display.

This method therefore reduces the hardware required on the display control device and allows display data to be generated and transmitted with maximum efficiency both in terms of the amount of processing required for the initial transform and the efficiency of compression to minimise the volume of data transmitted.

Although only one particular embodiment has been described in detail above, it will be appreciated that various changes, modifications and improvements can be made by a person skilled in the art without departing from the scope of the present invention as defined in the claims.