Progressive block encoding using region analysis

CROSS-REFERENCE TO RELATED APPLICATIONS

This application is a continuation of co-pending U.S. patent application Ser. No. 13/722,105, filed Dec. 20, 2012, entitled “Progressive Block Encoding using Region Analysis”. U.S. patent application Ser. No. 13/722,105, filed Dec. 20, 2012, is a continuation of U.S. patent application Ser. No. 11/549,577, filed Oct. 13, 2006, entitled “Progressive Block Encoding using Region Analysis” (now U.S. Pat. No. 8,345,768, issued Jan. 1, 2013). U.S. patent application Ser. No. 11/549,577, filed Oct. 13, 2006, now U.S. Pat. No. 8,345,768 issued Jan. 1, 2013, is (i) a Continuation-in-Part of U.S. Pat. No. 8,107,527, issued Jan. 31, 2012; and is (ii) a Continuation-in-Part of U.S. Pat. No. 7,747,086, issued Jun. 29, 2010, which claims the benefit of U.S. Provisional Patent Application Ser. No. 60/703,767, filed Jul. 28, 2005; and is (iii) a Continuation-in-Part of U.S. Pat. No. 7,822,278, issued Oct. 26, 2010, which claims the benefit of (a) U.S. Provisional Patent Application Ser. No. 60/719,050, filed Sep. 20, 2005, and of (b) U.S. Provisional Patent Application Ser. No. 60/726,418, filed Oct. 12, 2005; and U.S. patent application Ser. No. 11/549,577, filed Oct. 13, 2006, now U.S. Pat. No. 8,345,768 issued Jan. 1, 2013, claims priority to U.S. Provisional Patent Application Ser. No. 60/726,418, filed Oct. 12, 2005. U.S. Pat. No. 8,107,527, issued Jan. 31, 2012, is (I) a Continuation-in-Part of U.S. Pat. No. 7,822,278, issued Oct. 26, 2010, and is (II) a Continuation-in-Part of U.S. Pat. No. 7,747,086, issued Jun. 29, 2010, and (III) claims the benefit of U.S. Provisional Patent Application Ser. No. 60/726,418, filed Oct. 12, 2005. U.S. Pat. No. 7,822,278, issued Oct. 26, 2010 is a Continuation-in-Part of U.S. Pat. No. 7,747,086, issued Jun. 29, 2010. Each of the aforementioned related patent applications is herein incorporated by reference in its entirety.

FIELD

The invention relates generally to methods for encoding graphics signals for communication across a transmission medium. More particularity, the invention relates to methods for encoding persistent regions of a computer display image for progressive transmission to a remote user interface.

BACKGROUND

There is a growing desire in many workplace and other environments to separate the display of a computer system from the application processing parts. In the desired configuration, the display is physically located at the user's desktop, while the processing components of the computer are placed in a central location. The display is then connected to the data processor with some method of communication such as a computer network.

Various methods have been proposed to transfer display content across a network, including transferring graphic commands or encoded pixel maps representing the display image. These methods are acceptable for the transfer of less dynamic content such as text, background and pictures but are poorly suited to the transfer of dynamic video inserts. Video is usually not rendered using graphics commands so such commands aren't available for transfer. The transfer of compressed video would place a burden of full-featured decoding application software and hardware at the remote display and pixel transfer methods would easily saturate a corporate network unless the content was re-compressed.

Optimized methods for transferring areas of rapidly changing image content surrounded by other areas with different image types such as a video insert surrounded by pictures and text have not been addressed by prior art. Video content poses a unique problem in that it generates too much data for raw transfer across a network, is unsuitable for static image compression methods such as JPEG2000 and conventional video encoders such as H.264 or MPEG-4 FGS are complex, intrusive and inefficient to implement, especially considering the infrequent requirement for such encoding in many computing environments. Moreover, a video clip on a computer display is usually derived from a compressed source such as a DVD or broadcast network. A second video encoding phase adds unwanted latency and further reduces image quality. Additionally a standard encoded video stream would mandate a video decoder at the display system which is in conflict with cost and maintenance objectives associated with remote display systems.

Hybrid methods such as MJPEG developed to improve random access are capable of transmitting a series of independent JPEG images without applying inter-frame prediction methods. These methods offer limited compression and tend to consume high network bandwidth in applications such as standard video operating at high frame rates. Therefore they remain best suited to specialized applications like broadcast resolution video editing or surveillance systems where the frame rate is low. One variation on MJPEG uses differential encoding so that only changed DCT coefficients are encoded. However, in a video application, much of the content changes on every frame rendering this method ineffective.

In summary, existing methods developed specifically to transfer computer display images are not effective methods for transferring video. Still image and video compression techniques lack the necessary compression capabilities, require intrusive components or increased complexity. This results in higher equipment and maintenance costs and lower performance. Therefore, it is desirable to innovate new methods for transferring video sequences across computer networks to remote display systems.

SUMMARY

The present invention provides methods for managing the bandwidth required to communicate raster graphics sequences of constant input frame rates across a band-limited transmission channel. One example of a sequence is a video display clip playing on a computer display. In such a case, a rasterized video sequence has content updates that occur at a constant frame rate independent of the computer display refresh rate. The specification describes various progressive encoding sequences that address the unique challenge of re-encoding and transmitting one or more rasterized video sequences in a compound image region comprising different image types.

In one aspect, the present invention describes methods for managing a progressive encoding sequence so that constant bandwidth consumption is achieved. A display area identified as video type is incrementally improved to a perceptually acceptable quality level over a number of display update cycles. Unlike existing methods, this progressive build method defines a progression for the video area that is optimized to operate at a constant bandwidth dictated by the available network bandwidth.

In another aspect, the present invention describes methods for managing a progressive encoding sequence such that a constant video quality at low latency is maintained. Video areas are immediately built to a perceptually acceptable quality level and then maintained at a constant quality until the next frame update occurs. Unlike existing methods, this method provides constant quality while explicitly preserving network bandwidth for other high priority updates in the region.

In another aspect, the present invention describes methods for managing a progressive encoding sequence such that bandwidth waste is minimized. The progressive build of a video frame is curtailed at a perceptually acceptable quality level before content detail expected to be superseded before human recognition is encoded.

In another aspect, the present invention describes methods for managing a progressive encoding sequence so that the perceptual quality at a display is increased by delaying the display of image frames for a period that allows content related to the next frame to be queued at the decoder, thereby maintaining a constant perceived quality.

In another aspect, the present invention describes methods for delaying a progressive encoding sequence that prevents premature engagement of lower quality video encoding. This method is useful for ensuring that complex non-video images are built using high quality encoding methods.

In some cases the described methods may be used to build the quality of an image at a faster rate than the eye can process, enabling the progressive encoding, transmission and remote building of images at a rate that appears perceptually lossless to the viewer.

In summary, the progressive encoding methods described address the unique problem of transferring computer video sequences. Unlike change-detect methods such as video encoders or frame buffer comparison methods, the progressive encoding sequences allows control over bandwidth and quality at a sub-frame level that minimize bandwidth waste by reducing the transmission of imperceptible image information. Unlike other remote display methods such as command transfer or frame buffer copy methods, these sequences operate completely independently from the data processing system.

Many other features and advantages of the present invention will be apparent from reading the following detailed description, when considered in conjunction with the accompanying drawings, in which:

BRIEF DESCRIPTION OF THE DRAWINGS

<figref idref="DRAWINGS">FIG. 1</figref> shows a progressive encoding system connected to an image transfer bus of a CPU sub-system as may be used for the encoding of a computer display image stream;

<figref idref="DRAWINGS">FIG. 2</figref> is a diagram of a progressive encoding system used to encode blocks based on regional progressive encoding priorities;

<figref idref="DRAWINGS">FIG. 3</figref> shows the architecture for an embodiment of a block encoder;

<figref idref="DRAWINGS">FIG. 4</figref> shows a progressive decoding system connected to remote display via a display controller sub-system;

<figref idref="DRAWINGS">FIG. 5</figref> shows a method that enables the progressive encoding of a computer display image stream;

<figref idref="DRAWINGS">FIG. 6</figref> shows an embodiment of a region summary and analysis table;

<figref idref="DRAWINGS">FIG. 7</figref> presents a bandwidth analysis table with a bandwidth estimation method for the progression of a single block;

<figref idref="DRAWINGS">FIG. 8</figref> shows a graph of a progression in coding quality level for a single block;

<figref idref="DRAWINGS">FIG. 9</figref> shows a method for determining update priorities for a region;

<figref idref="DRAWINGS">FIG. 10</figref> presents a bandwidth analysis table and method for progressing the coding quality of a region by moving all changed blocks to a same desired coding quality level;

<figref idref="DRAWINGS">FIG. 11</figref> illustrates a progression for a region of 4×4 blocks to a same quality level;

<figref idref="DRAWINGS">FIG. 12</figref> presents a bandwidth analysis table and method for progressing the coding quality of a region by updating all changed blocks by a same increment;

<figref idref="DRAWINGS">FIG. 13</figref> illustrates a progression for a region of 4×4 blocks using a same coding quality increment for all changed blocks;

<figref idref="DRAWINGS">FIG. 14</figref> presents a bandwidth analysis table and method for progressing the coding quality of blocks using a proportional coding quality increment;

<figref idref="DRAWINGS">FIG. 15</figref> illustrates a progression for a region of 4×4 blocks using a proportional coding quality increment;

<figref idref="DRAWINGS">FIG. 16</figref> presents a bandwidth analysis table and method for progressing the coding quality of blocks such that the progression of low quality blocks to a baseline threshold quality level is prioritized;

<figref idref="DRAWINGS">FIG. 17</figref> illustrates a progression for a region of 4×4 blocks using a proportional coding quality increment;

<figref idref="DRAWINGS">FIG. 18</figref> shows a plot of perceived value of an obsolete image over time;

<figref idref="DRAWINGS">FIG. 19</figref> shows a plot of perceived quality over time for an embodiment where it is acceptable to experience a high quality image that is obsolete even when the input has changed;

<figref idref="DRAWINGS">FIG. 20</figref> shows an embodiment where an obsolete lossless image block is delayed before it is replaced with a changed input image block;

<figref idref="DRAWINGS">FIG. 21</figref> shows a bandwidth analysis table with perceived value compensation;

<figref idref="DRAWINGS">FIG. 22</figref> is prior art diagram that illustrates the bandwidth demand for the transfer of a lossless video sequence;

<figref idref="DRAWINGS">FIG. 23</figref> shows a series of steps used to classify blocks in a region as either video type or other image type;

<figref idref="DRAWINGS">FIG. 24</figref> shows a bandwidth analysis table that may be used to maintain a constant bandwidth sequence;

<figref idref="DRAWINGS">FIG. 25</figref> plots the result of an encoding sequence that maintains constant bandwidth consumption for a series of blocks;

<figref idref="DRAWINGS">FIG. 26</figref> shows a bandwidth analysis table that may be used to maintain a constant quality level video sequence;

<figref idref="DRAWINGS">FIG. 27</figref> plots the results of an encoding sequence that maintains constant quality levels for a series of blocks of video type;

<figref idref="DRAWINGS">FIG. 28</figref> shows a bandwidth analysis table used to maintain a video sequence that minimizes bandwidth waste;

<figref idref="DRAWINGS">FIG. 29</figref> plots the result of an encoding sequence that minimizes bandwidth waste for a series of blocks of video type;

<figref idref="DRAWINGS">FIG. 30</figref> is a variation on a constant video quality sequence that maintains a constant perceived quality after content transition by delaying the decode of the new content by a number of frames;

<figref idref="DRAWINGS">FIG. 31</figref> is a variation on a constant video quality sequence that delays the classification of a series of blocks as video type until a block change interval has stabilized;

<figref idref="DRAWINGS">FIG. 32</figref> is a diagram showing an embodiment of method for classifying a block as video or non-video based on block change rate; and

<figref idref="DRAWINGS">FIG. 33</figref> shows an alternative embodiment that tests a changed block for stability prior to classification.

DETAILED DESCRIPTION

The invention is well suited to the encoding of bit-exact image sequences, where high perceptual quality is important. One example is a computer display image encoding application.

<figref idref="DRAWINGS">FIG. 1</figref> shows a progressive encoding system connected to an image transfer bus of a CPU sub-system as may be used for the encoding of a computer display image stream. An embodiment of an associated remote system is described below and illustrated in <figref idref="DRAWINGS">FIG. 4</figref>. Standard CPU sub-system <b>100</b> includes one or more processors, a chipset and optional GPU. Standard CPU sub-system <b>100</b> connects to memory sub-system <b>102</b> using memory bus <b>104</b>. Memory <b>102</b> stores a pixel map image.

In one embodiment, standard CPU sub-system <b>100</b> transmits the image as a display signal across image transfer bus <b>106</b> to progressive encoding system <b>108</b> where the image is processed using methods described below. Digital raster embodiments of image transfer bus <b>106</b> include Digital Visual Interface (DVI), Digital Packet Video Link (DPVL), DisplayPort, Unified Display Interface (UDI) and other digital raster formats. A VGA embodiment of image transfer bus <b>106</b> is also feasible in applications where a limited resolution is acceptable. In an alternative embodiment, bus <b>106</b> also communicates additional information such as image type information and bandwidth availability information to system <b>108</b>.

In another embodiment, progressive encoding system <b>108</b> systematically reads the image. In this case, progressive encoding system <b>108</b> accesses memory sub-system <b>102</b> using hardware or software-based screen scraping methods may be tightly integrated with CPU sub-system <b>100</b>. One example of a tightly integrated system is a software method where progressive encoding system <b>108</b> is a software application running on CPU sub-system <b>100</b>.

Progressive encoding system <b>108</b> is connected to network <b>110</b> where network <b>110</b> is a computer network such as a corporate LAN. Packets containing encoded image information are transferred to a remote decoding and display system across network <b>110</b>.

In the present embodiment, image transfer bus <b>106</b> communicates a display image stream comprised of an ongoing sequence of image frames and progressive encoding system <b>108</b> takes a regional approach to encoding the image stream. In the embodiment, an image region (shown as shaded region <b>120</b>) is a “slice” across image frame <b>122</b> where frame <b>122</b> comprises a defined number of sequential rows of a raster. Alternatively, a region may be an entire frame. A single frame may also have different defined regions of different shapes. However, image region <b>120</b> should remain at a constant position from frame to frame so that precisely identified areas may be encoded using the progressive encoding methods described herein. Region <b>120</b> is further divided into a set blocks as shown in insert <b>130</b> where image block <b>132</b> is identified as a typical block. A block defines a unit area for tracking an image and each block is comprised of 8×8 pixels but other embodiments are feasible. By operating at a block level compared to a pixel level, the number of system parameters in progressive encoding system <b>108</b> is reduced and multiple pixels may be combined and encoded together using transform encoding techniques such as DCT coding. Progressive encoding methods may be implemented by defining a block structure for the progressive encoding phase that is physically aligned with the grid structure of a block-transformed image resulting from the transform phase. Alternative embodiment uses smaller block sizes, for example a single pixel, but this requires transform encoding to be managed across multiple blocks.

Pixels of the same pixel type in an image block that change at the same time are managed as a single entity using masks to identify pixels included in a set. In one embodiment pixels are pre-classified as having an identified pixel type such as video, text, picture, or background type using standard image decomposition methods. In the embodiment, all block in a region may be subject to the same progressive encoding sequence but individual blocks may be at different states of progression as a result of pixels changing at different times. In an alternative embodiment, blocks in a region may be subject to different progressive encoding sequences based on image type. In such a case, different progressive sequences may be executing simultaneously and different blocks may be at different states of progression within each sequence method. As an example, a region may be classified as having two picture areas (e.g., JPEG pictures) changing at different times, a text area (e.g., Display of a word processing screen) and a video sequence (e.g., An MPEG clip). In this example, blocks classified as text might be assigned a high priority rapid build sequence to lossless coding quality level, all blocks classified as pictures might be subjected to a slow progression to a high coding quality using a different sequence and blocks classified as video might be subjected to a rapid progression to a lower coding quality level to limit the bandwidth consumed by video. Note that this specification uses the term “coding quality level” to define a numerical value used to set a measurable image quality level at the decoded output of a progressive encoding system.

Many of the advantages of individual pixel state management are gained by using block masks to group pixels and overheads of transmitting and storing the individual pixel information are avoided.

<figref idref="DRAWINGS">FIG. 2</figref> is a diagram of system <b>108</b> in <figref idref="DRAWINGS">FIG. 1</figref> used to encode blocks based on regional progressive encoding priorities prior to transmission across network <b>110</b>. In the embodiment shown, pixel capture module <b>200</b> receives an incoming display signal on bus <b>106</b>. Module <b>200</b> forwards the pixels to change detection module <b>210</b> and block encoder <b>220</b>. Module <b>210</b> detects changes to image block (ref. Block <b>132</b> in <figref idref="DRAWINGS">FIG. 1</figref>) using any efficient pixel block detection method. In one embodiment, module <b>210</b> calculates hash codes for 8×8 pixel blocks, which is a convenient dimension for discrete cosine transformation calculations. The hashing function calculates a partial hash code for a horizontal raster line sequence of 8 incoming pixels from pixel capture module <b>200</b> (i.e., the hashing function is repeatedly executed and a new partial value generated as each pixel is received). Starting with the first line in a horizontal scan, a partial hash code is calculated for the first 8 pixels in the line. Once the partial code has been calculated, it is stored in a local memory buffer and the hashing function calculates and stores a new partial code for the next 8 pixels in the line. This sequence is repeated until the end of the line of pixels in the scan. When the second scan line is initiated, the partial hash code for the first 8 pixels of the first line is retrieved from the memory buffer and the code is updated to include the first 8 pixels in the new line directly below the first line. This sequence is repeated for the rest of the second line and for all 8 lines. Once a hash code has been calculated for an 8×8 block of pixels, the code is compared with a hash code for the same block the previous image frame. A persistent image block is detected if a recent hash code is the same as a previous hash code. If the hash codes differ, module <b>200</b> signals encoder <b>220</b> to initialize a progressive build state for the current block using change detection signal <b>212</b>.

Module <b>210</b> may also incorporate circuitry or embedded software functionality to identify additional image attributes. In one embodiment, module <b>210</b> includes standard image decomposition filters capable of identifying different static properties including image types such as backgrounds, pictures, icons or text. In this case, image type attributes are also forwarded to encoder <b>220</b>. In another embodiment, module <b>210</b> includes a function that analyses block change frequency in order to identify if the block includes a video sequence. In a case where a block is identified as changing at an anticipated video frame refresh rate (e.g., 30 frames per second), module <b>210</b> uses signal <b>212</b> to update encoder <b>220</b> with this additional block information. In another embodiment, graphic commands executing on sub-system <b>100</b> (ref. <figref idref="DRAWINGS">FIG. 1</figref>) that generate the image are monitored for information that describes image type (e.g., Video sequences, photographs, text etc.). These image type indicators are then forwarded over connection <b>106</b> to system <b>108</b>.

Module <b>200</b> also forwards incoming digitized display data to encoder <b>220</b> over pixel bus <b>202</b>. Encoder <b>220</b>, described in detail below and illustrated in <figref idref="DRAWINGS">FIG. 3</figref>, buffers regions of image blocks and uses region summary and analysis table <b>230</b> to determine encoding priorities for each block in a region. Table <b>230</b> is a memory structure that stores pixel and block information enabling an analysis of input change data. One example is information indicating that progressive encoding is underway but image blocks are not in a lossless state. Another example is block change and type information. Pixels that are continuously changing and are of picture type are probably related to a video sequence and may be better suited to video encoding than progressive block encoding methods or they may be suited to variations on progressive encoding that limit bandwidth consumption at the cost of image quality. In this case table <b>230</b> may be decomposed into sub-tables supporting different image types. As another example, transform method may be important. For example, if a DCT transform algorithm is used, the progressive encoding of all pixels in a block may be necessary if any pixels change. Various embodiments of table <b>230</b> are described below and illustrated in <figref idref="DRAWINGS">FIG. 6</figref>.

Encoder <b>220</b> is also provided bandwidth information as signal <b>222</b> to support the computation of encoding levels. Bandwidth information may be a register value initialized to a fixed allocation for each region or it may be a variable that can be updated by sub-system <b>100</b> or external equipment such as traffic management equipment. In one embodiment, available bandwidth is dependent on the status of other regions and is updated once earlier regions have been analyzed.

Image blocks are encoded and forwarded to network interface <b>240</b> across bus <b>224</b>. Network interface <b>240</b> hosts a standard networking protocol stack (e.g., TCP/IP) and provides a physical interface such as Ethernet to network <b>110</b>. Network interface <b>240</b> performs network-layer encapsulation of the encoded data and transmits the data to a remote system such as that described herein and illustrated in <figref idref="DRAWINGS">FIG. 4</figref>.

<figref idref="DRAWINGS">FIG. 3</figref> shows an embodiment of encoder <b>220</b> in <figref idref="DRAWINGS">FIG. 2</figref>. In the embodiment, progression sequencer <b>300</b> controls encoding methods and manages the build states of incoming image blocks. State sequencer <b>300</b> applies one or more of the sequencing methods described herein to determine the next build state for an image block based on signal <b>212</b>, the build state for an image block as stored in build state table <b>310</b>, a regional summary as stored in table <b>230</b> and bandwidth information <b>222</b>. In an alternative embodiment, sequencer <b>300</b> uses additional information such as image type to determine an encoding method and sequence.

In the embodiment shown, block assembler and region buffer <b>320</b> assembles incoming pixels on bus <b>202</b> into image blocks of 8×8 pixels and stores them locally. Note that pixels on bus <b>202</b> arrive at encoder <b>220</b> in advance of change detection signal <b>212</b> for the same block hence the requirement to buffer the pixel stream. Signal <b>212</b> signals which blocks in a region have changed compared with the same blocks in the previous frame and that a new encoding sequence for those blocks should be initiated. If a block has changed, an entry for the block is flagged accordingly using a change detection mask in build state table <b>310</b> that is also used to record the current state of each image block. In an alternative embodiment, table <b>310</b> also records the number of frames that have passed since the input image has changed. Image blocks that changed in a much earlier frame but have not reached a lossless state may receive a higher priority bandwidth allocation as described herein and illustrated in <figref idref="DRAWINGS">FIG. 22</figref>.

Sequencer <b>300</b> retrieves stored region information from table <b>230</b> that provides a build state summary for blocks in the region and bandwidth estimates to advance blocks to higher quality levels. Sequencer <b>300</b> searches the change detection mask in table <b>310</b> for bits indicating changed blocks and updates table <b>230</b>. Sequencer <b>300</b> then performs a bandwidth analysis using the methods described herein and illustrated in <figref idref="DRAWINGS">FIG. 9</figref> and selects a next coding quality level for each block in the region.

Each block is then encoded by encoding engine <b>330</b> under control of sequencer <b>300</b>. In the present embodiment, engine <b>330</b> is a selectable quality encoding engine that obtains a specified encoding method (ref. Encoder method signal <b>302</b>) from sequencer <b>300</b> to process blocks in buffer <b>320</b>. In the embodiment, image blocks are transformed into layered bit-planes using standard DCT transform methods.

Sequencer <b>300</b> specifies a desired coding quality level using desired coding quality signal <b>304</b>. Signal <b>304</b> determines the number of quality levels to be encoded for each block based on the previous quality level (as recorded in table <b>310</b>), available bandwidth <b>222</b>, state of other blocks in the region and selected progression sequence. Sequencer <b>300</b> also specifies an encoding domain using encoder method signal <b>302</b>. Once the region has been processed, the new build state for each block is updated in table <b>310</b> and table <b>230</b> (in <figref idref="DRAWINGS">FIG. 2</figref>) is updated to reflect a summary of the region state.

Packet stream generator <b>340</b> then builds encoded packets for transmission using the designated encoded bit planes and transmits them on bus <b>224</b>. In an alternative embodiment, the remaining bit planes are temporarily stored in buffer <b>320</b> for future transmission. In another alternative, all the layers are encoded each time an incoming scan block is assembled.

In the present embodiment, encoding of non-overlapping image blocks predominantly occurs in the discrete cosine transform (DCT) domain, but overlapping image blocks or the discrete wavelet transforms (DWT) may also be used. Non-transformed encoding methods such as RGB or YCrCb encoding may also be used for part or all of the data. Alternative encoding methods such as spatial sub-sampling methods may be used too. One alternative is a residual encoding method that calculates and transmits a difference value by subtracting a saved copy of the previously decoded image block. Residual encoding is a simpler technique but it is less efficient because at least two bits per pixel must be transmitted and it also requires that encoder <b>220</b> maintains a copy of the data already transmitted.

<figref idref="DRAWINGS">FIG. 4</figref> shows a progressive decoding system connected to a remote display via a display controller sub-system. System <b>450</b> receives encoded progressive image data from system <b>108</b> in <figref idref="DRAWINGS">FIG. 1</figref> across network <b>110</b>. System <b>450</b> also receives information from system <b>108</b> including block type information, a description of which blocks are changing, target quality line information (as illustrated in <figref idref="DRAWINGS">FIG. 7</figref>) and encoding method in embodiments that use different encoding methods for different regions. System <b>450</b> then uses this information to decodes the encoded progressive data using similar methods used by encoder <b>220</b> in <figref idref="DRAWINGS">FIG. 2</figref>. System <b>450</b> maintains region summary table <b>484</b> that is synchronized with table <b>230</b> in <figref idref="DRAWINGS">FIG. 2</figref>.

System <b>450</b> is comprised of standard network interface <b>480</b> connected to network <b>110</b>. A stream of encoded pixel blocks at different states of progressive build are forwarded from interface <b>480</b> to block decoder <b>482</b>. Decoder <b>482</b> includes its own progression sequencer and build state table so it can determine the next build state for each block without a requirement for separate transmission of this information. It decodes incoming bit planes using an equivalent decoding method and engine to encoding engine <b>330</b> in <figref idref="DRAWINGS">FIG. 3</figref>. In one embodiment, blocks that have been encoded using an 8×8 DCT transform are decoded by decoder <b>482</b> using an inverse DCT transform on incoming encoded data. Decoded blocks are then forwarded to standard display controller sub-system <b>460</b> across bus <b>452</b>. Coefficient information is then stored in frame buffer <b>486</b>. When the next refinement level for a block arrives (for example, as a set of DCT coefficient refinements), the stored coefficient information is retrieved from frame buffer <b>486</b>, added to the new refinement information, transformed to the image domain and forwarded to sub-system <b>460</b>. In the case where an image block remains unchanged at system <b>108</b> (in <figref idref="DRAWINGS">FIG. 1</figref>), no pixel data is transferred across network <b>110</b> but rather decoder <b>482</b> retrieves and decodes the coefficients thereby preserving network bandwidth. In an alternative embodiment, decoder <b>482</b> also stores decoded blocks in frame buffer <b>486</b> to reduce processing in the case where a block is unchanged. Sub-system <b>460</b> generates standard display connection <b>462</b> for remote display <b>470</b>. Connection <b>462</b> may be a VGA bus, a Digital Visual Interface Signal (DVI) or other standard display connection.

<figref idref="DRAWINGS">FIG. 5</figref> shows a method that enables the progressive encoding of a computer display image stream as may be executed using system <b>108</b> in <figref idref="DRAWINGS">FIG. 1</figref>. Changes to image content in a region are identified, analyzed and used to determine the encoding specification for the update of each block in the region. Each block identified for update is encoded to a desired coding quality level. The process is repeated for other regions of the display and for ongoing frames in the display stream.

In one embodiment, an image is encoded into a series of bit planes of increasing quality (where the increased quality could be measured using PSNR or other methods). Each encoded bit plane is directly associated with a coding quality level. The lowest quality level may include multiple bit planes necessary to provide a minimum coding quality level (identified as quality level 1 in this specification). Each additional bit plane (or set of bit planes) is associated with an increment in coding quality level. In one embodiment, the highest coding quality level is associated with all of the bit planes necessary to achieve a numerically lossless decoded image including the color space conversion. Bit planes may also be sub divided to create additional quality levels. In an embodiment where data is transformed to the frequency domain, the low frequency data may constitute one sub-plane while the high frequency data constitutes another. If the data is not transformed, groups of bit planes may be segmented along spatial boundaries to create additional quality levels. In alternative embodiments, different encoding methods may be used over different ranges of quality levels. In this case, there may not be a direct relationship between a bit plane and a coding quality level. However, a common coding quality metric can still be scaled and used to control the different encoders and identify incremental improved measurable output quality levels.

Referring to <figref idref="DRAWINGS">FIG. 5</figref>, image information updates for a region are acquired as a first step <b>500</b>. Update information includes updated image content (referred herein as “input change”) and updated image attributes including image type as described herein and illustrated in <figref idref="DRAWINGS">FIG. 2</figref>. Note that image information updates may be acquired in advance of a regional analysis of that region. For example, updates may be acquired for a region that is one or more regions or frames ahead of the region under analysis. This forward looking analysis allows the system to manage the bandwidth over a larger window and reserve bandwidth for large area updates that are detected ahead of the current region being processed. The forward looking analysis is a trade-off between better network bandwidth utilization and latency. The further ahead the system looks, the better the bandwidth utilization at the expense of increased image transfer latency.

As a next step <b>502</b>, regional information describing the number of blocks at each coding quality level is retrieved. The present embodiment stores information using table <b>230</b> in <figref idref="DRAWINGS">FIG. 2</figref>. In the present embodiment, changes are managed at a block level. Any pixel change is identified as a block change and all pixels in the block are re-encoded and transmitted. The first time through the processing loop the stored region information is at an initial state. Which results in all blocks being recognized as changed during the next operation.

As a next step <b>504</b>, update priorities for the region are determined based on available bandwidth and information from table <b>230</b> (in <figref idref="DRAWINGS">FIG. 2</figref>). An embodiment of a table <b>230</b> is presented in <figref idref="DRAWINGS">FIG. 6</figref>. Specific methods for determining update priorities are a major aspect of this specification and are described herein and illustrated in <figref idref="DRAWINGS">FIG. 9</figref>.

As a next series of steps <b>506</b>, blocks that have been identified for update are encoded and prepared for transmission. In one embodiment, a changed block is first fully encoded into a set of independent bit planes containing increasing quality information. In this case, one or more additional encoded bit planes are selected for transmission. In an alternative embodiment, a block is partially encoded to a defined coding quality level and all the encoded information selected for transmission. In yet another embodiment, partial bit planes are transmitted. For example, if a discrete wavelet transform method is used, frequency sub-band information, such as HH, HL, LH or LL sub-band information may be transmitted. Preparation for transmission may include additional standard entropy, arithmetic or other encoding and packetization e.g., IP packetization for transfer across a computer network. This may be done a block or a region at a time.

As a next step <b>508</b>, updated build states following the encoding process are stored for the next analysis of the same region. The present embodiment uses table <b>230</b> in <figref idref="DRAWINGS">FIG. 2</figref>.

As a next step <b>520</b>, a process termination test is conducted. In case <b>522</b>, processing is repeated for the next region of the frame. At the end of a frame the method continues by processing the top region of the next frame and updating the frame count accordingly. In case, <b>524</b>, the method terminates when there is no longer a desire to transfer the image, for example in preparation for a system shutdown.

An alternative embodiment of the method is useful in situations where not all of the allocated bandwidth has been used and there is additional processing bandwidth available. The alternative method reprocesses a region where there has been no change to the input image. This enables the additional bandwidth to be used to improve the coding quality level of the image.

<figref idref="DRAWINGS">FIG. 6</figref> shows an embodiment of region summary and analysis table <b>230</b> in <figref idref="DRAWINGS">FIG. 2</figref>. In <figref idref="DRAWINGS">FIG. 6</figref>, region summary and analysis table <b>600</b> includes summary section <b>602</b> which maintains a record of the number of blocks at each coding quality level and analysis section <b>604</b> which maintains bandwidth estimates on the bandwidth required to move a block from one coding quality level to another.

In the present embodiment, k<b>0</b>-k<b>6</b> are variables that track the number of blocks for each indicated present coding quality level (as previously defined) for a total of K blocks (reference <b>610</b>) in the region. Table <b>600</b> tracks 6 present quality levels and a “0” quality level on separate rows. The 0 level is used to track blocks that have undergone an input change (e.g., frame buffer update or changed input raster information for block), but no content update information has been encoded or transmitted. Alternative embodiments may use fewer or more coding quality levels to enable increased scalability in the encoded stream. In one alternative illustrated by <figref idref="DRAWINGS">FIG. 16</figref>, sixteen levels are used. The greater the number of levels the finer the bandwidth control. Additional bandwidth resolution may be achieved by limiting the number of blocks that transition between two levels during one update cycle.

Columns of section <b>604</b> provides estimates a<b>00</b>-a<b>56</b> in terms of number of encoded bits for the amount of data required to move a block from any present coding quality level to a next desired quality level. A bandwidth estimate in terms of a bits/second or similar metric is easily derived by dividing the total number of encoded bits for a region by the time window allocated to transmit all the encoded bits in the region. Alternatively the desired bandwidth can be defined as the number of bits per region and the values a<b>00</b>-a<b>56</b> can be defined as bits per block. Bandwidth analysis estimates B<b>1</b>-B<b>6</b> (reference <b>612</b> and others shown) provide total estimates of bandwidth requirements to progress all blocks to the indicated desired coding quality level. In one embodiment illustrated in <figref idref="DRAWINGS">FIG. 10</figref>, all blocks are incremented to the same desired coding quality level. Other embodiments are also described herein.

Note that table <b>600</b> is a simplified table that assigns the same estimates (a<b>00</b>-a<b>56</b>) for all image types (picture, text, background video etc) and is based on an entire block change. A more complex table may include different bandwidth values for different image types and scaling factors that account for the number of pixels being encoded. One method of enabling different progressive sequences for image blocks of different types is to decompose table <b>600</b> into a series of sub-tables, each sub-table then maintains a record of the number of blocks of a defined image type (or sub-region) at each present coding quality level (kn) and bandwidth estimates for each image type (or sub-region). An embodiment with a region comprising text, pictures and background may define three sub-tables.

A second simplification applied to table <b>600</b> makes an assumption that the data required to move a block by multiple levels in a single step is the sum of data required to move the block incrementally from the lower to the higher value using multiple steps. For example, it is assumed that a total of a<b>23</b>+a<b>34</b> bits is required to move a block from a present coding quality level of 2 to a desired coding quality level of 4. However, an alternative embodiment is possible where encoding efficiencies may reduce the data in cases of multi-level increments. In this case, table <b>600</b> may be modified to store additional estimates showing transitions between any level and any other prospective level.

In an embodiment where different encoding methods are used for different stages of an encoding progression, the estimates are adjusted to reflect the encoding efficiencies for each encoding method used. One example uses two encoding methods. A set of N−1 coding quality levels is achieved using a first transform-domain encoder. As a final step, a residual encoder is used to transform blocks from a lossy level N−1 to a lossless level N

<figref idref="DRAWINGS">FIG. 7</figref> and <figref idref="DRAWINGS">FIG. 8</figref> provide an example that illustrates how table <b>600</b> is used to estimate bandwidth required to move a block from one level to the next.

<figref idref="DRAWINGS">FIG. 7</figref> presents a bandwidth analysis table and a bandwidth estimation method for the progression of a single block. Bandwidth analysis table <b>700</b> is an abbreviated form of region summary and analysis table <b>600</b> in <figref idref="DRAWINGS">FIG. 6</figref>. Data such as k<b>0</b>-k<b>6</b> in section <b>602</b> of table <b>600</b> in <figref idref="DRAWINGS">FIG. 6</figref> is assumed to be available. The progression of a single block is shown to illustrate an estimation of bandwidth in a simplified progression. Arrow <b>702</b> shows the progression of a block from a present coding quality level of 2 (reference column <b>704</b>) to a desired coding quality of 4 (reference column <b>706</b>) where a vertical line <b>708</b> through column <b>706</b> represents a simple embodiment of a target quality line. A bandwidth estimate for the described block is a<b>23</b>+a<b>34</b>. In the case of a total of k<b>2</b> blocks (reference <figref idref="DRAWINGS">FIG. 6</figref>) starting at coding quality level 2 and ending at a coding quality level of 4, the total bandwidth estimate bwtotal is calculated as <br />bwtotal=<i>k</i>2×(<i>a</i>23<i>+a</i>34)  (1)

In an alternative embodiment where a region has different image types and table <b>700</b> is comprised of a sub-table supporting each image type, each sub-table may have an independent target quality line.

<figref idref="DRAWINGS">FIG. 8</figref> presents graph <b>800</b> that plots coding quality level on vertical axis <b>802</b> against time on horizontal axis <b>804</b>. Graph <b>800</b> shows the increase in coding quality level for a block subjected to the progression described herein and illustrated in <figref idref="DRAWINGS">FIG. 7</figref>.

At time <b>810</b>, the described block progresses from a present coding quality level 2 (reference <b>806</b>) to desired coding quality level 4 (reference <b>808</b>). It is worth noting that vertical quality level axis <b>802</b> shows equal measured quality level increments for each of the defined coding values shown. However, the bandwidth required to move a block from one level to the next increases as the measured quality level increases. For example a<b>45</b> (reference <b>820</b>)&gt;a<b>34</b> (reference <b>822</b>) in <figref idref="DRAWINGS">FIG. 8</figref>. In fact, an increase of 2× per bit plane may be found in a representative embodiment. It is this non-linear increase in bandwidth requirement that prevents the use of a simple formula for incrementing all blocks towards a lossless state at the same rate and forms the basis for the more sophisticated progression priority schemes introduced in <figref idref="DRAWINGS">FIG. 9</figref>.

<figref idref="DRAWINGS">FIG. 9</figref> shows an embodiment of step <b>504</b> in <figref idref="DRAWINGS">FIG. 5</figref> for determining update priorities for a region. In a simple embodiment, update priorities for a region are determined by the state of the current region as described by a region summary and analysis table such as table <b>600</b> in <figref idref="DRAWINGS">FIG. 6</figref> using fixed available bandwidth constraints. In more sophisticated embodiments, update priorities are also influenced by bandwidth forecasts, the state of other regions, and decoder or network error conditions which override the progressive encoding sequence by forcing retransmission or transmission of initial update information.

Referring to <figref idref="DRAWINGS">FIG. 9</figref>, the available bandwidth for a region is determined as a first step <b>900</b>. In one embodiment, a fixed available bandwidth for a frame is evenly distributed across the regions comprising the frame. In an alternative embodiment, one or more regions demanding a high bandwidth (e.g., a video sequence as determined by hints from the application software or change patterns at a block level) are allocated additional bandwidth at the expense of less dynamic regions. In another embodiment, traffic shaping methods are used to spread the bandwidth fairly over different regions.

As a next step <b>910</b>, a regional summary is generated so that progressive build requirements may be determined based on the regions most recent change information. In the present embodiment, table <b>600</b> is updated such that blocks that have changed are reset to a present coding quality level of 0 (entry “k<b>0</b>” in column <b>602</b> of table <b>600</b> in <figref idref="DRAWINGS">FIG. 6</figref>). In an embodiment that enables a dynamic selection between different target quality line styles as described by the different target quality line embodiments below, step <b>910</b> may include the selection of a style of target quality line based on available bandwidth or region summary. In an alternative embodiment, an initial style is selected for each identified image type but is subject to change based on a bandwidth analysis (step <b>940</b> below). In an embodiment where step <b>500</b> identifies blocks as being of video type, one or more target quality lines may be selected during that step.

As a next series of steps <b>920</b>, the desired coding quality level for the blocks in the region is determined. Several embodiments using different target quality lines are illustrated by later figures below. In an embodiment supporting multiple target quality lines associated with different image types or independent sub-regions of the same type but with different target quality lines, steps <b>920</b> are repeated for each areas target quality line represented.

A minimum target quality line is selected as step <b>930</b>. There are many possible methods for selecting a minimum target quality line. In one embodiment, historic estimates are used to determine the starting point for a new estimation. In another embodiment, a current block distribution is used as a starting point for a first estimate. The bandwidth required to meet the target quality is calculated as next step <b>940</b>. Different embodiments use different formulae as described below.

As next step <b>950</b>, a check is performed to test if the required bandwidth is within the available bandwidth. In case <b>952</b>, bandwidth is available so a higher target quality line is selected as step <b>960</b> and step <b>940</b> is repeated using the higher target. In case <b>954</b>, the required bandwidth exceeds the available bandwidth so the desired coding quality is set to the previous (lower) target quality line as final step <b>970</b>.

<figref idref="DRAWINGS">FIG. 10</figref> and <figref idref="DRAWINGS">FIG. 11</figref> describe an embodiment that loops through step <b>920</b> using target quality lines that bring changed blocks to the same desired coding quality level. <figref idref="DRAWINGS">FIG. 12</figref> and <figref idref="DRAWINGS">FIG. 13</figref> describe an embodiment that loops through step <b>920</b> using target quality lines that increments changed blocks by the same coding quality increment. <figref idref="DRAWINGS">FIG. 14</figref> and <figref idref="DRAWINGS">FIG. 15</figref> describe an embodiment that loops through step <b>920</b> and more recent updates are prioritized by assigning them proportionally larger increments. <figref idref="DRAWINGS">FIG. 16</figref> and <figref idref="DRAWINGS">FIG. 17</figref> describe an embodiment that loops through step <b>920</b> and recent updates are prioritized by establishing a baseline quality threshold used for all blocks ahead of improving the quality level of blocks over the threshold. In <figref idref="DRAWINGS">FIG. 19</figref>, blocks are incremented at different rates, dependent on current perceived quality levels. Other embodiments are also possible.

<figref idref="DRAWINGS">FIG. 10</figref> presents a bandwidth analysis table and method for progressing the coding quality of a region by moving all changed blocks to a same desired coding quality level. Bandwidth analysis table <b>1000</b> is an abbreviated form of table <b>600</b> in <figref idref="DRAWINGS">FIG. 6</figref>. Data such as k<b>0</b>-k<b>6</b> in section <b>602</b> of table <b>600</b> in <figref idref="DRAWINGS">FIG. 6</figref> is assumed to be available. In the present embodiment, a pre-determined available bandwidth value is assumed. This may be a constant value or a variable value provided in advance by an independent processing method.

Total data and associated bandwidth requirements are determined for each desired coding quality level, indicated by target quality lines <b>1010</b>, <b>1012</b>, <b>1014</b>, <b>1016</b>, <b>1018</b> and <b>1020</b> shown. Zero bandwidth line <b>1030</b> represents a baseline target where no blocks are updated and consequently no bandwidth is consumed. A highest target quality line within the available bandwidth is then selected using the method described by step <b>920</b> in <figref idref="DRAWINGS">FIG. 9</figref> and all blocks in the region below the target are encoded to the selected target quality line. All blocks at the target or above the target remain unchanged. Table 1 presents a set of equations used by this embodiment in step <b>940</b> (ref. <figref idref="DRAWINGS">FIG. 9</figref>) for calculating bandwidth requirements for target quality lines at different desired coding quality levels.

<tables id="TABLE-US-00001" num="00001"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="1"><colspec colname="1" colwidth="217pt" align="center" /><thead><row><entry namest="1" nameend="1" rowsep="1">TABLE 1</entry></row></thead><tbody valign="top"><row><entry namest="1" nameend="1" align="center" rowsep="1" /></row><row><entry>Bandwidth Estimation for Blocks Increased to Same Coding Quality</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="3"><colspec colname="1" colwidth="28pt" align="center" /><colspec colname="2" colwidth="49pt" align="center" /><colspec colname="3" colwidth="140pt" align="left" /><tbody valign="top"><row><entry /><entry>FIG. 10</entry><entry /></row><row><entry>Desired</entry><entry>Target</entry><entry /></row><row><entry>Coding</entry><entry>Quality</entry><entry /></row><row><entry>Quality</entry><entry>Line</entry><entry>Estimated</entry></row><row><entry>Level</entry><entry>Reference</entry><entry>Bandwidth Requirement</entry></row><row><entry namest="1" nameend="3" align="center" rowsep="1" /></row><row><entry>0</entry><entry>1030</entry><entry>0</entry></row><row><entry>1</entry><entry>1010</entry><entry>bw₀₁= k₀× a₀₁</entry></row><row><entry>2</entry><entry>1012</entry><entry>bw₀₂= bw₀₁+ (k₀+ k₁) × a₁₂</entry></row><row><entry>3</entry><entry>1014</entry><entry>bw₀₃= bw₀₂+ (k₀+ k₁+ k₂) × a₂₃</entry></row><row><entry>4</entry><entry>1016</entry><entry>bw₀₄= bw₀₃+ (k₀+ k₁+ k₂+ k₃) × a₃₄</entry></row><row><entry>5</entry><entry>1018</entry><entry>bw₀₅= bw₀₄+ (k₀+ k₁+ k₂+ k₃+ k₄) × a₄₅</entry></row><row><entry>6</entry><entry>1020</entry><entry>bw₀₅= bw₀₅+ (k₀+ k₁+ k₂+ k₃+ k₄+ k₅) × a₅₆</entry></row><row><entry namest="1" nameend="3" align="center" rowsep="1" /></row></tbody></tgroup></table></tables>

<figref idref="DRAWINGS">FIG. 11</figref> shows three consecutive progression states in a region where all blocks are increased to a same coding quality level. The example uses initial assumptions that blocks in the region are at initial progression state <b>1100</b> with initial present coding quality levels as indicated by the values associated with each block. Under the illustrative constrains of the example, the available bandwidth (bwregion) for the region is <br />bw04&lt;=bwregion&lt;bw05  (2)

where bw<b>04</b> and bw<b>05</b> are previously defined in Table 1.

In the example, area <b>1102</b> is subjected to an input change. The changed blocks are therefore assigned a present coding quality level of 0 as shown in progression state <b>1110</b>. Note that no updates have been encoded or transmitted at this time. In the example, the other blocks in the region remain unchanged. Ideally, changed area <b>1102</b> is immediately updated to a coding quality level of 6 in a single step corresponding with an ideal desired coding quality for area <b>1102</b>. However, due to the available bandwidth limitations imposed by equation (2), the highest target quality line within the limit is bw<b>04</b> (reference target quality line <b>1018</b> in <figref idref="DRAWINGS">FIG. 10</figref>). Therefore a first update using a desired coding quality value of 4 for changed area <b>1102</b> and other partially progressed blocks is chosen as shown in progression state <b>1120</b>.

The described example illustrates a simple method whereby all blocks are updated to a same desired coding quality level. In a practical application, each region is subjected to multiple changes at different times and alternative prioritization methods, such as those introduced below, are useful in ensuring that blocks at a low coding quality are updated while blocks at higher coding quality levels do not stagnate in a partially encoded state due to insufficient bandwidth.

<figref idref="DRAWINGS">FIG. 12</figref> presents a bandwidth analysis table and method for progressing the coding quality of a region by updating all changed blocks by the same increment. One method of ensuring that blocks at higher coding quality levels do not stagnate in a lossy progression state is to increment all changed blocks by the same increment, independent of their present coding quality levels.

Bandwidth analysis table <b>1200</b> is an abbreviated form of table <b>600</b> in <figref idref="DRAWINGS">FIG. 6</figref>. Data such as k<b>0</b>-k<b>6</b> in section <b>602</b> of table <b>600</b> in <figref idref="DRAWINGS">FIG. 6</figref> is assumed to be available as before. Total data requirements are determined for each desired coding quality level, indicated by target quality lines <b>1202</b>, <b>1204</b>, <b>1206</b>, <b>1208</b>, <b>1210</b> and <b>1212</b> shown in bandwidth analysis table <b>1200</b> of <figref idref="DRAWINGS">FIG. 12</figref>. As before, zero bandwidth line <b>1220</b> represents a baseline target where no blocks are updated and consequently no bandwidth is consumed. The highest target quality line within the available bandwidth is then selected and all blocks in the region below the target quality line are encoded to the selected target quality line. All blocks at the target or above the target remain unchanged. Note that the target lines turn and run vertically downwards at the maximum quality column to prevent the constant increment from setting any quality levels above maximum coding quality level 6 (e.g., For target quality line <b>1204</b>, blocks at present coding quality level 5 (reference k<b>5</b> in <figref idref="DRAWINGS">FIG. 6</figref>) increase to desired coding quality level 6).

Table 2 presents a set of equations used by this embodiment in step <b>940</b> (ref. <figref idref="DRAWINGS">FIG. 9</figref>) for the calculation of estimate values for a set of target quality lines, a selection of which are shown in <figref idref="DRAWINGS">FIG. 12</figref>.

<tables id="TABLE-US-00002" num="00002"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="1"><colspec colname="1" colwidth="217pt" align="center" /><thead><row><entry namest="1" nameend="1" rowsep="1">TABLE 2</entry></row></thead><tbody valign="top"><row><entry namest="1" nameend="1" align="center" rowsep="1" /></row><row><entry>Bandwidth Estimation for Blocks Increased by Same Increment</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="3"><colspec colname="1" colwidth="42pt" align="center" /><colspec colname="2" colwidth="35pt" align="center" /><colspec colname="3" colwidth="140pt" align="left" /><tbody valign="top"><row><entry>Quality</entry><entry>FIG. 12</entry><entry /></row><row><entry>Increment</entry><entry>Reference</entry><entry>Estimated Bandwidth Requirement</entry></row><row><entry namest="1" nameend="3" align="center" rowsep="1" /></row><row><entry>0</entry><entry>1220</entry><entry>0</entry></row><row><entry>1</entry><entry>1202</entry><entry>ibw₁= (k₀× a₀₁) + (k₁× a₁₂) + (k₂× a₂₃) + </entry></row><row><entry /><entry /><entry>(k₃× a₃₄) + (k₄× a₄₅) + (k₅× a₅₆)</entry></row><row><entry>2</entry><entry>1204</entry><entry>ibw₂= ibw₁+ </entry></row><row><entry /><entry /><entry>(k₀× a₁₂) + (k₁× a₂₃) + (k₂× a₃₄) + (k₃× a₄₅) +</entry></row><row><entry /><entry /><entry>(k₄× a₅₆)</entry></row><row><entry>3</entry><entry>1206</entry><entry>ibw₃= ibw₂+ </entry></row><row><entry /><entry /><entry>(k₀× a₂₃) + (k₁× a₃₄) + (k₂× a₄₅) + (k₃× a₅₆)</entry></row><row><entry>4</entry><entry>1208</entry><entry>ibw₄= ibw₃+ </entry></row><row><entry /><entry /><entry>(k₀× a₃₄) + (k₁× a₄₅) + (k₂× a₅₆)</entry></row><row><entry>5</entry><entry>1210</entry><entry>ibw₅= ibw₄+ (k₀× a₄₅) + (k₁× a₅₆)</entry></row><row><entry>6</entry><entry>1212</entry><entry>ibw₆= ibw₅+ (k₀× a₅₆)</entry></row><row><entry namest="1" nameend="3" align="center" rowsep="1" /></row></tbody></tgroup></table></tables>

A progression example for a region using the target quality lines of <figref idref="DRAWINGS">FIG. 12</figref> is shown in <figref idref="DRAWINGS">FIG. 13</figref>. <figref idref="DRAWINGS">FIG. 13</figref> illustrates a progression for a region of 4×4 blocks using a same coding quality increment for all changed blocks. <figref idref="DRAWINGS">FIG. 13</figref> shows six consecutive states of progression in a region where all blocks are increased using the same coding quality increment. A simplified example case using an increment of 1 coding quality level for all updates has been chosen. In a practical application, the highest possible increment within the available bandwidth is selected for each update (using bandwidth estimation formulae in Table 2), taking the number of blocks at each coding quality level into consideration.

The example assumes initial progression state <b>1300</b> with all blocks in the region at maximum present coding quality level 6. In the example, area <b>1302</b> shown is subjected to an input change. The changed blocks are therefore assigned a present coding quality level of 0 as shown in progression state <b>1310</b>. In the example, the other blocks in the region remain unchanged.

The constraints imposed by the example dictate a desired coding quality increment of 1 for change area <b>1302</b> for a first update. Therefore changed blocks progress to a coding quality level of 1 in a first update step as shown in progression state <b>1320</b>. Progression state <b>1330</b> shows different area <b>1304</b> subjected to a second input change and set to a present coding quality level of 0. A desired coding quality increment of 1 for the change areas <b>1302</b> and <b>1304</b> is once again chosen per constraints of the example. All changed blocks progress by a single coding quality increment in a second update step as shown in progression state <b>1340</b>. Progression state <b>1350</b> shows a third time the region is updated but where no input changes are present. In the third update step all the changed blocks that have not reached final coding quality level 6 are incremented again. The sequence is assumed to continue until all blocks once again reach a present coding quality level of 6 or additional input changes trigger additional progressions.

The described example illustrates a simple method whereby all blocks are incremented at the same rate. Given sufficient bandwidth availability, this results in a perceptually constant update rate for all changed regions of an image. However, in many applications, perceptual quality of a display is improved by providing a higher coding priority to blocks at a lower present coding quality levels. This may be accomplished using various strategies, two of which are detailed below.

<figref idref="DRAWINGS">FIG. 14</figref> presents a bandwidth analysis table and method for progressing the coding quality of blocks using a proportional coding quality increment. One problem with incrementing all blocks by the same rate is that blocks at higher coding quality levels require a significant proportion of the available bandwidth for a low additional improvement in perceptual quality. At the same time, this prevents the rapid progression of blocks at a low perceptual quality. Some of this bandwidth may be more effectively utilized by allocating it to blocks at a low coding quality. In most instances, a progression from a low quality level to a medium coding quality level has higher perceptual value than an incremental improvement between two higher coding quality levels.

Bandwidth analysis table <b>1400</b> is an abbreviated form of table <b>600</b> in <figref idref="DRAWINGS">FIG. 6</figref>. Data such as k<b>0</b>-k<b>6</b> in section <b>602</b> of table <b>600</b> in <figref idref="DRAWINGS">FIG. 6</figref> is assumed to be available as before. The bandwidth is estimated for target quality lines <b>1402</b>, <b>1404</b>, <b>1406</b>, <b>1408</b> and others implied. Target quality lines converge at point <b>1404</b> as shown. As before, zero bandwidth line <b>1420</b> represents a baseline target where no blocks are updated. The highest target quality line within the available bandwidth is then selected as before. All blocks in the region below the target are encoded to the selected target quality line. All blocks at the target or above the target remain unchanged. Note that in the present embodiment, the encoder operates to integer quality levels and therefore the lines are rounded to the closest desired integer quality level for each present coding quality level. A progression example for a region using the target quality lines of <figref idref="DRAWINGS">FIG. 14</figref> is shown in <figref idref="DRAWINGS">FIG. 15</figref>.

<figref idref="DRAWINGS">FIG. 15</figref> illustrates a progression for a region of 4×4 blocks using a proportional coding quality increment. <figref idref="DRAWINGS">FIG. 15</figref> shows six consecutive states of a progression in a region where all blocks are increased using a proportional coding quality increment. For illustration purposes, a simple 3&gt;2&gt;1 increment sequence for all updates is used in this example to move blocks from an initial coding quality level of 0 to a final coding quality level of 6 (i.e., Changed blocks are first move to quality 3 on a first update, then to quality 5 on a second update and finally to quality 6 on a third update (3&gt;2&gt;1)). In a practical application, the fastest possible increment sequence within the available bandwidth is selected for each update, taking the number of blocks at each coding quality level into consideration as before.

The present embodiment uses an initial assumption that all blocks in the region are at an initial maximum present coding quality level of 6 as shown in progression state <b>1500</b>. In the example, area <b>1502</b> shown is subjected to an input change. The changed blocks are therefore assigned a present coding quality level of 0 as shown for next progression state <b>1510</b>. In the example, the other blocks in the region remain unchanged.

The target quality line for a first update (approximated by line <b>1402</b> in <figref idref="DRAWINGS">FIG. 14</figref>) translates to a desired coding quality increment of 3 for change area <b>1502</b> per constraints of the example. The changed blocks progress to a coding quality level of 3 in a first update step as shown in progression state <b>1520</b>. In the example, a different area <b>1504</b> of the region is subjected to an input change and set to a present coding quality level of 0 shown in next progression state <b>1530</b>. In a second update step shown (the target line is still approximated by line <b>1402</b> in <figref idref="DRAWINGS">FIG. 14</figref>) as progression state <b>1540</b>, change area <b>1504</b> is incremented by 3 levels while change area <b>1502</b> is only incremented by 2 levels. Final progression state <b>1550</b> shows a third update step where the changed blocks are incremented again. Change area <b>1504</b> is incremented by 2 levels while change area <b>1502</b> is incremented by a single level. The sequence is assumed to continue until all blocks once again reach a present coding quality level of 6 or additional input changes trigger additional progressions.

<figref idref="DRAWINGS">FIG. 16</figref> presents a bandwidth analysis table and method for progressing the coding quality of blocks such that the progression of low quality blocks to a baseline threshold quality level is prioritized. While incremental increases in coding quality levels at the lower end of the perceptual quality spectrum offer measurable quality improvements, image content may remain perceptually unintelligible or unacceptable below a baseline coding quality threshold. This limitation is particularly pertinent to applications such as computer display images where text and icons may have very fine resolutions. In such applications, it becomes important to prioritize the progression of changed input blocks to a baseline coding quality level that is perceptually significant over the improvement of blocks that have already reached the threshold. <figref idref="DRAWINGS">FIG. 16</figref> describes a method of prioritizing the progression of blocks below a baseline coding quality threshold. Bandwidth analysis table <b>1600</b> in <figref idref="DRAWINGS">FIG. 16</figref> is similar to previously shown bandwidth analysis tables with the exception that the number of significant coding quality levels is increased to 15. The introduction of a higher resolution system offers finer scalability over coding quality and more efficient use of available bandwidth.

Rather than constructing linear target quality lines as previously described, the lines shown in the present embodiment are segmented such that baseline coding quality threshold <b>1602</b> is established at a desired coding quality level of 4. In alternative embodiments, other baseline threshold values may be used to meet the perceptual quality requirements of the system. In other alternative embodiments the baseline may be variable, allowing a trade-off between latency and quality such that over a low bandwidth connection, the low quality baseline may be more acceptable then the additional latency required to get to a higher quality.

The present embodiment shows up to three segments for each target quality line. For example, identified target quality line <b>1608</b> is comprised of a first vertical segment that move blocks of present coding quality 0-4 to a desired coding quality of 12, followed by a second segment that increments blocks with a present coding of 5-7 in a proportional manner similar to that described by <figref idref="DRAWINGS">FIG. 14</figref>. Lastly, a third vertical segment moves all blocks with a present coding quality of 8-14 to a final coding quality level 15. In alternative embodiments, each target quality line may be constructed of multiple segments. Other alternative embodiments may combine lossy and lossless coding methods such that a series of constructed target quality lines is used to enable the progression of a block to a maximum lossy coding quality level. Thereafter, a state machine or other appropriate method is used to enable the progression of the block to a lossless coded quality level.

<figref idref="DRAWINGS">FIG. 16</figref> shows insufficient bandwidth quality lines in area <b>1604</b> where there is not sufficient bandwidth to encode changed blocks to a minimum desired coding quality threshold <b>1602</b>. In this case, changed blocks may only be progressed to desired coding quality levels 1, 2 or 3. Furthermore, unchanged blocks would not be improved in this scenario. On the next frame these blocks receive equal priority to newly changed blocks in the progression to coding quality threshold <b>1602</b>.

Bandwidth requirements for the target quality lines shown is estimated using the described methods. As before, zero bandwidth line <b>1606</b> represents a baseline target where no blocks are updated. The highest target quality line within the available bandwidth is then selected as before. All blocks in the region below the target are encoded to the selected target quality line. All blocks at (or above) the target remain unchanged. The consequence of the segmented target quality lines is that blocks in the region with a coding quality level below the baseline quality threshold are moved to the threshold before any blocks are advanced beyond the threshold.

A progression example for a region using the target quality lines of <figref idref="DRAWINGS">FIG. 16</figref> is shown in <figref idref="DRAWINGS">FIG. 17</figref>. <figref idref="DRAWINGS">FIG. 17</figref> illustrates a progression for a region of 4×4 blocks using a proportional coding quality increment. <figref idref="DRAWINGS">FIG. 17</figref> shows eight consecutive states of a progression in a region where all blocks below baseline coding quality threshold <b>1602</b> (reference <figref idref="DRAWINGS">FIG. 16</figref>) are prioritized over blocks that have reached threshold <b>1602</b>.

For illustration purposes, a simple 4&gt;1&gt;1&gt;1 increment sequence for all updates is used in this example to move blocks from an initial coding quality level of 0 to a final coding quality level of 15. In a practical application, the highest possible increment within the available bandwidth is selected for each update, taking the number of blocks at each coding quality level into consideration as before.

All blocks in the region are assumed to be at an initial maximum present coding quality level of 15 as shown in progression state <b>1700</b>. Area <b>1702</b> is subjected to an input change and the changed blocks are assigned a present coding quality level of 0 shown in progression state <b>1710</b>. In the example, the other blocks in the region remain unchanged.

The target quality line for the first update translates to a desired coding quality increment of 4 for the change area <b>1702</b> (once again per sequence constraints of the example) and the changed blocks progress to a coding quality level of 4 in a first update step shown as progression state <b>1720</b>.

This is followed by progression states <b>1730</b> and <b>1740</b> corresponding to second and third update steps in which the changed blocks incrementally progress to a coding quality level of 5 an then level 6. Progression state <b>1750</b> shows a different area <b>1704</b> of the region subjected to an input change and set to a present coding quality level of 0 followed by progression state <b>1760</b> after a forth update step where change area <b>1704</b> is incremented by 4 levels. However, unlike previous examples, change area <b>1702</b> is not incremented but remains at a present coding quality level of 6. This step illustrates the prioritization of the progression of area <b>1704</b> to a baseline threshold over the additional progression of area <b>1702</b>. Finally, progression state <b>1770</b> shows the results of a fifth update step where all the changed blocks are incremented by a single level again. Change area <b>1704</b> is incremented by 1 to level 5 while blocks exclusive to change area <b>1702</b> are incremented to level 7. The sequence is assumed to continue until all blocks once again reach a present coding quality level of 15 or additional input changes trigger additional progressions.

<figref idref="DRAWINGS">FIG. 18</figref> is a graph illustrating the decline in perceived image quality over time for blocks that have not reached a lossless state. The bandwidth analysis tables and related block progression sequences described above operate according to measurable present and desired coding quality levels. In practice, image quality levels as perceived by the human brain have a temporal dependency. This aspect of the present invention modifies the bandwidth analysis table to compensate for the temporal dependency of perceived quality levels. Note that the present invention uses the term “perceived value” to refer to a human perceived quality level compared with “coding quality level” used to refer to a quality level that is measurable using PSNR or other means.

<figref idref="DRAWINGS">FIG. 18</figref> shows a plot of perceived value over time. Lossless perceived value <b>1800</b> remains constant over time as shown while lower perceived values typically decline at increasing rates. This may be seen in <figref idref="DRAWINGS">FIG. 19</figref> by comparing plot <b>1802</b> with a starting perceived value of 6 and slowly declining compared to plot <b>1804</b> with a starting perceived value of 1 and rapidly declining. Values starting at 0 and declining in the negative domain (reference perceived quality line <b>1806</b>) represent the perceived quality of image content that has not been updated at all and therefore the displayed content is obsolete and inaccurate.

Note that the slope of the curves on the graph, especially in the negative perceptual value domain are dependent on the perceptual nature of the application. In one case, it may be both pleasing to the human brain and functionally acceptable to experience a high quality image that is obsolete because the input has changed. A sequence of photographs is one specific example where this may be true. In this case, the perceptual value of obsolete image content remains relatively high over time. Note that the actual period of time that content is “obsolete” using the present invention is usually less than 1 second and more typically less than 100 ms. In another case more typical of a computer display environment, while visually less appealing, it is more important to replace obsolete content with updated content, even if the updated content is presented at a lower quality level. A simple example is a stock trader monitoring real-time trading data. In this case, the perceptual value of obsolete declines very quickly over time. Initial perceived values immediately following an update may be directly correlated with present coding quality levels previously discussed. This direct relationship between a coding quality level and a time-dependent perceived value enables the temporal compensation of block progression based on mapping of compensated quality levels into a bandwidth analysis table as described by <figref idref="DRAWINGS">FIG. 16</figref>.

<figref idref="DRAWINGS">FIG. 19</figref> shows a plot of perceived quality over time for an embodiment where it is acceptable to experience a high quality image that is obsolete even when the input has changed. In <figref idref="DRAWINGS">FIG. 19</figref>, line <b>1806</b> of <figref idref="DRAWINGS">FIG. 18</figref> is replaced with lines <b>1842</b>, <b>1844</b>, <b>1846</b> and <b>1848</b> to remove the limitation in <figref idref="DRAWINGS">FIG. 18</figref> that obsolete data starts at a perceived quality of 0. Plot <b>1842</b> shows a block at lossless perceived quality at time <b>0</b> when the input image changes. The perceived value drops to an initial positive value and then deteriorates over time. <figref idref="DRAWINGS">FIG. 19</figref> shows that it may be more important to improve a poorly coded image then it is to start sending updates for an obsolete but lossless image.

<figref idref="DRAWINGS">FIG. 20</figref> shows an embodiment where an obsolete lossless image block is delayed before it is replaced with a changed input image block and plots a progression in perceived value from time <b>1870</b> for a block at lossless perceived quality <b>1880</b> when the input changes. As a first stage <b>1882</b> in the progression after the input changes, the block drops to a new perceived quality. In fact, the viewer may not perceive the obsolete status of the block at this time. As a next stage in the progression <b>1884</b>, the perceived quality follows curve <b>1862</b> until time <b>1872</b>. At time <b>1872</b>, it is determined that it more valuable to use available bandwidth to encode the new content to perceived value of 4 than to allow further deterioration of the obsolete image. The changed input is encoded to a perceived value of 4 as stage <b>1886</b> shown. Finally, the changed input deteriorates as predicted by curve <b>1864</b> during stage <b>1888</b>. Stage <b>1888</b> lasts until either the content is improved or a new changed input is encoded.

<figref idref="DRAWINGS">FIG. 21</figref> shows a bandwidth analysis table with perceived value compensation. A method for compensating for time dependent perceived quality is described by a variation on the method described by <figref idref="DRAWINGS">FIG. 5</figref> in which step <b>500</b> includes a recording of the time (for example, in number of frames) each block remains at a build state and step <b>504</b> uses bandwidth analysis table <b>1900</b> in <figref idref="DRAWINGS">FIG. 21</figref> as described below. Table <b>1900</b> enables the progression of blocks in a manner similar to the method used by table <b>1600</b> in <figref idref="DRAWINGS">FIG. 16</figref>. However, a perceived value compensation graph translates quality levels between a measurable coding quality domain as used in earlier embodiments of the present invention and a time-dependent perceived value domain used by table <b>1900</b>. Target quality line <b>1902</b> in table <b>1900</b> is similar to target quality line <b>1608</b> described for <figref idref="DRAWINGS">FIG. 16</figref>, comprising three segments. However, the first vertical segment extends to an nth negative perceived quality value corresponding with an nth negative perceived quality value for the graph shown in <figref idref="DRAWINGS">FIG. 21</figref>.

State information including present coding quality level and time since last update is maintained for each block (as captured in step <b>500</b> in <figref idref="DRAWINGS">FIG. 5</figref>). During region analysis (step <b>504</b> in <figref idref="DRAWINGS">FIG. 5</figref>), a perceived value compensation table is used to retrieve an equivalent perceived value for each block in the region. In the present embodiment, a look-up table derived from the graph in <figref idref="DRAWINGS">FIG. 21</figref> is used. In other embodiments, different perceptual value trends are used, each trend pertinent to the specific application of the embodiment. Translation between domains occurs as follows. As a first step, bandwidth estimates for target quality lines are calculated as described by step <b>940</b> in <figref idref="DRAWINGS">FIG. 9</figref> and a desired perceived quality level for each block is determined. As a next step, a next coding level for each block is determined by mapping the perceived values back to real desired coding quality levels using a reverse table look up procedure. Note that perceived quality levels in <figref idref="DRAWINGS">FIG. 21</figref> need to be quantized to integer perceived quality levels in embodiments where an encoder only supports integer coding quality levels.

The description above discloses a system and methods for prioritizing the progressive transfer of blocks based on regional priorities as determined using bandwidth analysis tables. These methods are useful for controlling the bandwidth of remote computer display applications and enabling prioritization of different content types; for example a high priority content changes such as a text image area update is readily prioritized over the final build stages of a picture area in the same region. Bandwidth analysis may also be combined with motion detection methods to control the bandwidth necessary to update positional changes in constant content, as might occur when a window is scrolled or dragged. Once again, the progressive build of high priority subjects to high quality levels may be prioritized over lower priority subjects once the image has become constant.

In an environment that communicates video sequences to a remote system, further improvements in a user's perceptual experience may be gained using the progression methods described below. These specifically identify image blocks of a video type so that video content may be treated using different bandwidth analysis methods to other image types in a region.

<figref idref="DRAWINGS">FIG. 22</figref> is a prior art graphical representation describing a practical limitation associated with the communication of raster graphics sequences across a network. Unlike synthetic computer display images, rasterized video sequences are characterized by large areas of content change on every video frame update. In fact, a fractional lighting change caused by camera motion will likely change the pixel value associated with the digitized representation of a perceptually static scene. Upper graph <b>2000</b> in <figref idref="DRAWINGS">FIG. 22</figref> shows a plot of lossless coding quality level <b>2010</b> of a video display sequence that starts at time <b>2020</b> and ends at time <b>2028</b>, with periodic frame updates at times <b>2022</b>, <b>2024</b>, <b>2026</b> and <b>2028</b> as shown. Note that the term “lossless” as used in this specification refers to a coding quality level that may be lossless in a binary sense or some other perceptually lossless final coding quality level. While 30 frames per second is a commonly used frame rate, other rates are also possible. Lower graph <b>2050</b> shows the network bandwidth demand required to achieve a lossless display over the same period of time. Due to the large content changes, high levels of instantaneous bandwidth <b>2060</b>, <b>2062</b>, <b>2064</b> and others shown are required to communicate the data. In a practical application, data transmission may be distributed over a full 33 mS frame period but even then a lossless update far exceeds link capacity level <b>2070</b> offered by typical existing transmission systems such as corporate LANs or last mile connections. While the bandwidth demands of rasterized video content presents one problem, a related problem arises in the prioritization of other high priority information and trade-off in perceptual quality between different image types. For example, a foreground text editor on a computer display may be of higher interest and warrant higher display quality than a background video insert.

A solution to these problems lies in the positive identification of video sequences and the application of bandwidth management strategies that preserve bandwidth for other applications while also maximizing the perceptual quality of the video content. Methods for applying the regional analysis methods described herein and illustrated in <figref idref="DRAWINGS">FIG. 5</figref> to support bandwidth management in a region containing one or more areas of video are discussed below.

The methods described are of particular relevance to remote display or other applications where the frame rate for the image content is lower than the display refresh rate. An example of such an application is a video sequence with a 30 fps content frame rate that is displayed on a CRT computer monitor with an 85 frame per second CRT refresh rate. In applications where the frame rate for the image content matches the refresh rate (for example, a 30 fps TV signal matching a 30 fps display refresh rate), the encoding methods described may still be applied without interfering with natural image motion although the same quality may not be achieved.

<figref idref="DRAWINGS">FIG. 23</figref> shows an alternative embodiment of step <b>500</b> in <figref idref="DRAWINGS">FIG. 5</figref> (‘Acquire image information updates for region’) labeled in <figref idref="DRAWINGS">FIG. 23</figref> as step <b>2100</b> comprised of a series of smaller steps. Step <b>2100</b> classifies image blocks as either video type or another image type (such as text, picture or background previously discussed) so that video-related bandwidth analysis methods and progressive sequences may be applied to blocks of video type. As a first step <b>2110</b>, image type and change information is acquired. Image type may be determined using image decomposition methods or graphical information provided by CPU sub-system <b>100</b> in <figref idref="DRAWINGS">FIG. 1</figref>, change detection module <b>210</b> in <figref idref="DRAWINGS">FIG. 2</figref> or another method. In one embodiment, CPU <b>100</b> informs progressive encoding system <b>108</b> of the co-ordinates and timing of video sequences. Change information is provided by change detection module <b>210</b> in <figref idref="DRAWINGS">FIG. 2</figref>.

As a next step <b>2120</b>, video sequence information is retrieved from memory such as a memory structure local to progression sequencer <b>300</b> in <figref idref="DRAWINGS">FIG. 3</figref>. In one embodiment, video sequence information comprises one or more region update counter values used to monitor for video refresh rates (as described by step <b>2130</b> below). In an embodiment described below and illustrated in <figref idref="DRAWINGS">FIG. 31</figref>, one or more video sequence stabilization counters are also retrieved for use in step <b>2130</b> below.

As next step <b>2130</b>, block changes are analyzed along with previously image type information and blocks are further classified. In one embodiment, sequencer <b>300</b> incorporates a video block identification state machine that classifies blocks as video type based on image type and block change rate. In the embodiment, one or more region update counters count pre-defined integer multiples of the region update rate which may then be used as a basis for identifying expected video frame rates. As a simple example, consider a popular video frame rate of 30 frames per second. If the region update rate is known to be 90 updates per second, a region update counter that identifies a block change every 3 passes through step <b>2100</b> signals that the changed block may be classified as video type. In another embodiment, multiple region update counters monitor a block or sub-region for different possible video frame rates. In yet another embodiment, multiple region update counters monitor different areas of a region for different video frames that may be out of synchronization or at different frame rates. One method of accomplishing this is to associate a counter with each block.

In the above embodiments, one or more update counter values retrieved in step <b>2120</b> are incremented. If the block has changed, the counter is compared against expected video timing. If the timing matches, the block is classified as video. In an embodiment where additional image type information is available, a second criterion for video identification is that a changed block consistently be of picture type. When a block changes, it is only classified as video type when it meets both frame timing and picture type requirements. If a block changes at a count that is not related to an expected video frame rate, the update counters are reset. In an embodiment described herein and illustrated in <figref idref="DRAWINGS">FIG. 31</figref>, an additional stabilization counter is incremented each time a block at a location changes at an expected video frame rate. The counter is then compared with a stabilization value and the block is only classified as video type once the video is identified as stable. The stabilization counter is reset if the block changes at a count that is not related to an expected video frame rate. In all cases, a block previously identified as video is re-classified as non-video if it is identified as not changing at the expected frame rate. <figref idref="DRAWINGS">FIG. 30</figref> shows an embodiment of a method for classifying changed blocks using the logic described above. <figref idref="DRAWINGS">FIG. 33</figref> shows an alternative embodiment including a stabilization analysis.

As a next step <b>2140</b>, the updated video sequence information is stored. Updates include increments to update and stabilization counters. Note that updates to block classification need not be processed during step <b>2140</b> because block attributes are stored in build state table <b>310</b> at step <b>508</b> in <figref idref="DRAWINGS">FIG. 5</figref>.

<figref idref="DRAWINGS">FIG. 24</figref> shows bandwidth analysis table <b>2200</b> that is an alternative embodiment to bandwidth analysis table <b>1200</b> in <figref idref="DRAWINGS">FIG. 12</figref> using a single target quality line to maintain a constant bandwidth video sequence. In a constant bandwidth sequence, target quality line <b>2210</b> is used in step <b>930</b> of <figref idref="DRAWINGS">FIG. 9</figref> for blocks classified as video type. Rather than maximizing image quality as described in step <b>920</b>, the desired coding quality for video type blocks is set to a value specified by line <b>2210</b>, i.e., the method uses an alternative embodiment to step <b>920</b> in which step <b>930</b> is followed directly by step <b>970</b> rather than maximizing the quality. Other embodiments are useful as well. For example step <b>920</b> may select between executing a maximum quality method or minimum bandwidth method based on additional configuration parameters. In another alternative embodiment, step <b>920</b> may use target quality line <b>2210</b> for early build stages but curtail encoding of higher coding quality increments when the next expected video frame is imminent. In one method, step <b>920</b> evaluates a region update counter (retrieved in step <b>2120</b>) to determine whether to increment the coding quality level or hold the present level.

<figref idref="DRAWINGS">FIG. 25</figref> is a graphical representation of the results of an encoding sequence that maintains constant bandwidth consumption for a series of blocks governed by the methods of <figref idref="DRAWINGS">FIG. 5</figref> in conjunction with bandwidth analysis table <b>2200</b> in <figref idref="DRAWINGS">FIG. 24</figref>. The constant bandwidth encoding sequence shown uses table <b>2200</b> throughout and may be applied to a block of any type i.e., blocks are not necessarily of video type. (Later examples include a step which first identifies a video frame rate before a block is classified as video type and processed using a different table.)

Upper graph <b>2300</b> plots a change in coding quality level for a block of video type over time while lower graph <b>2350</b> has plot <b>2360</b> representing the bandwidth consumed to transmit the video block over the same period of time. Referring to graph <b>2300</b>, each tick on the horizontal axis represents the arrival of a new frame of a rasterized image. The content of each block in the new frame may be a repeat of the content in a block at the same location of the previous frame or blocks may have updated content. In the described embodiment, the rasterized frame rate is higher than the video sequence frame rate and the content is shown to change every 7 frames. The vertical axis of graph <b>2300</b> represents increasing coding quality, for example using a peak signal to noise ratio (PSNR) metric. Referring to plot <b>2310</b> on graph <b>2300</b>, an initial lossless state at lossless coding quality level <b>2302</b> is assumed, during which no bandwidth is consumed (as indicated during time period <b>2362</b> shown).

When a different block is first encountered at time <b>2332</b>, the present coding quality level drops to initial coding quality level <b>2306</b> and a constant bandwidth progression using bandwidth analysis table <figref idref="DRAWINGS">FIG. 24</figref> is initiated. In the example shown, blocks arriving at times <b>2334</b>, <b>2336</b>, <b>2338</b> and <b>2340</b> each interrupt the previous progression (i.e., periods <b>2320</b>, <b>2322</b>, <b>2324</b> and <b>2326</b> are shorter than period <b>2328</b> required to build a block to a final coding quality). Table <b>2200</b> is used for the progressive encoding of each block using same constant bandwidth <b>2352</b> in each case. In the example, the last block arriving at time <b>2340</b> is not interrupted and continues to increment using constant bandwidth <b>2352</b> until final coding quality level <b>2302</b> is reached at time <b>2342</b>. While plot <b>2310</b> shows approximately equal increments in coding quality after each frame update cycle, equal coding quality increments may demand higher bandwidth at higher absolute quality levels. Therefore, in order to maintain constant bandwidth level <b>2352</b>, the coding quality increment typically decreases as the absolute coding quality level of the block increases.

Benefits of the method described herein and illustrated in <figref idref="DRAWINGS">FIG. 25</figref> include a simple progression and constant nominal network bandwidth consumption. The method may be applied to any incoming block sequence with a rapid block change rate (including video) to limit bandwidth consumption. However, in spite of each frame reaching a perceptually acceptable quality level for a brief period, the average quality level (quality level <b>2304</b> shown) may be too low to provide an overall acceptable perceived quality, especially in the case of an ongoing sequence such as a video stream. One obvious way of boosting average quality level <b>2304</b> is to increase bandwidth consumption level <b>2352</b> by allowing an increased number of quality increments for each frame update (using the different target quality lines as shown in <figref idref="DRAWINGS">FIG. 12</figref>). However, in applications where bandwidth availability is limited, other management methods such as those discussed below may provide improved performance.

<figref idref="DRAWINGS">FIG. 26</figref> shows bandwidth analysis table <b>2400</b>, an alternative embodiment to bandwidth analysis table <b>1000</b> in <figref idref="DRAWINGS">FIG. 10</figref> with a single target quality line used to maintain a constant quality level video sequence. Target quality line <b>2410</b> is used in step <b>930</b> of <figref idref="DRAWINGS">FIG. 9</figref> for blocks classified as video type. Rather than maximizing image quality as described in step <b>920</b>, the desired coding quality for video type blocks is set to a value specified by line <b>2410</b>, i.e., the method uses an alternative embodiment to step <b>920</b> in which step <b>930</b> is followed directly by step <b>970</b> rather than maximizing the quality. Other embodiments as described herein and illustrated in <figref idref="DRAWINGS">FIG. 24</figref> are also useful.

<figref idref="DRAWINGS">FIG. 27</figref> is a graphical representation of the results of an encoding sequence that maintains constant quality levels for a series of blocks of video type governed by bandwidth analysis table <b>2400</b> and step <b>2100</b> in <figref idref="DRAWINGS">FIG. 23</figref>. The sequence shown in <figref idref="DRAWINGS">FIG. 27</figref> uses bursts of data to ensure a constant nominal video quality level as specified by target quality line <b>2410</b> in <figref idref="DRAWINGS">FIG. 24</figref> is maintained. While the method demands high peak data rates, only part of the total available bandwidth is consumed which allows other high priority traffic to share the link.

As with <figref idref="DRAWINGS">FIG. 25</figref>, upper axes <b>2500</b> plots a change in coding quality over time and each tick on the horizontal axis represents the arrival of a new frame of a rasterized image as before. Plot <b>2560</b> on lower axes <b>2550</b> shows the bandwidth consumed to transmit the block over the same period of time. Referring to plot <b>2510</b> on graph <b>2500</b>, an initial lossless state at lossless coding quality level <b>2502</b> is assumed, during which no bandwidth is consumed (time period <b>2562</b> shown). When a different block is first encountered at time <b>2532</b>, a constant bandwidth progressive encoding sequence as described herein and illustrated in <figref idref="DRAWINGS">FIG. 25</figref> is initiated and the present coding quality level drops to an initial coding quality level <b>2506</b>. Progressive encoding is then used to encode and transmit the new block using constant bandwidth level <b>2552</b>. However, a new block arrives at time <b>2534</b> following elapsed period <b>2520</b> where in the embodiment, period <b>2520</b> is an expected video frame period using methods described herein and illustrated in <figref idref="DRAWINGS">FIG. 23</figref>. The block arriving at time <b>2534</b> is classified as video type and a constant quality encoding sequence using table <b>2400</b> in <figref idref="DRAWINGS">FIG. 26</figref> to govern a progression is initiated. In the described progression, the block is immediately encoded to desired coding quality level <b>2504</b> (corresponding with target quality line <b>2410</b>) and then held constant until either another block arrives at the expected video frame rate (in which case the progression is repeated for the new block) or another block arrives at a different frame interval and is classified as non-video.

In <figref idref="DRAWINGS">FIG. 27</figref>, new blocks arriving at times <b>2536</b> and <b>2538</b> after periods <b>2522</b> and <b>2524</b> match the expected frame rate determined by period <b>2520</b> and are classified as video type. The blocks are encoded to coding quality level <b>2504</b> using bursts at bandwidth at level <b>2554</b> on graph <b>2550</b>. After the last scene change at time <b>2538</b>, the block at time <b>2540</b> arrives after period <b>2526</b> that is longer than the expected video frame period. The block is classified as non-video and encoding is completed using incremental steps (governed by table <b>2200</b>) and constant bandwidth level <b>2552</b> once again. The result of the constant quality encoding method is that a perceptually acceptable constant quality level is delivered while the display latency is maintained at a low level at the expense of bursts in network bandwidth consumption. In the embodiment shown, the latency is single frame update period <b>2564</b> but higher latencies using lower bandwidth peaks are possible. In many applications, average bandwidth consumption level <b>2556</b> ensures that in spite of the traffic bursts, the average level is sufficiently low that the data stream may be multiplexed with other network traffic without causing congestion.

Note that the embodiment described by <figref idref="DRAWINGS">FIG. 27</figref> shows one embodiment for achieving the objective of prioritizing the initial build steps for each frame in a video sequence. Other embodiments are also contemplated. For example, any of the bandwidth analysis tables described may be extended to include a weighing factor that favors the initial progression of new blocks of video type. As a second example, the inflection point on target quality line <b>2610</b> is governed by the video frame period to curtail encoding of higher coding quality increments when the next expected video frame is imminent.

<figref idref="DRAWINGS">FIG. 28</figref> shows bandwidth analysis table <b>2600</b> used to maintain a video sequence that minimizes bandwidth waste. In the described sequence, target quality line <b>2610</b> is used in step <b>930</b> of <figref idref="DRAWINGS">FIG. 9</figref> for blocks classified as video type. Rather than maximizing image quality as described in step <b>920</b>, the desired coding quality for video type blocks is set to a value specified by line <b>2610</b>, i.e., the method uses an alternative embodiment to step <b>920</b> in which step <b>930</b> is followed directly by step <b>970</b> rather than maximizing the quality. Other embodiments are also contemplated. For example, step <b>920</b> may select between executing a maximum quality method or minimum bandwidth method based on additional configuration parameters. In another alternative embodiment, step <b>920</b> may use target quality line <b>2610</b> as a minimum target quality line and then use methods described by <figref idref="DRAWINGS">FIG. 14</figref> to maximize the coding quality during the incremental build stages.

<figref idref="DRAWINGS">FIG. 29</figref> is a graphical representation of the result of an encoding sequence that minimizes bandwidth waste for a series of blocks of video type governed by bandwidth analysis table <b>2600</b> and step <b>2100</b> in <figref idref="DRAWINGS">FIG. 23</figref>. <figref idref="DRAWINGS">FIG. 29</figref> is a variation on the constant quality sequence shown in <figref idref="DRAWINGS">FIG. 27</figref> that minimizes wasted bandwidth by using nominal bandwidth to reach a nominal initial desired coding quality level and then delaying the completion of the progression. Upper axes <b>2700</b> plots a change in coding quality over time and each tick on the horizontal axis represents the arrival of a new frame of the rasterized image as before. Plot <b>2760</b> on lower axes <b>2750</b> shows the bandwidth consumed to transmit the image block over the same period of time.

Referring to plot <b>2710</b> on graph <b>2700</b>, an initial lossless state at lossless coding quality level <b>2702</b> is assumed, during which no bandwidth is consumed as before. When a different block is first encountered at time <b>2732</b>, a constant bandwidth progressive encoding sequence as described herein and illustrated in <figref idref="DRAWINGS">FIG. 25</figref> is initiated and the present coding quality level drops to an initial coding quality level. Progressive encoding is then used to encode and transmit the new block using constant bandwidth level <b>2752</b>. However, a new block arrives at time <b>2734</b> following elapsed period <b>2720</b> where in the embodiment, period <b>2720</b> is an expected video frame period using methods described herein and illustrated in <figref idref="DRAWINGS">FIG. 23</figref>. The block arriving at time <b>2734</b> is classified as video type and a minimum bandwidth waste encoding sequence using table <b>2600</b> in <figref idref="DRAWINGS">FIG. 28</figref> is used to govern a progression. In the described progression, the block is incrementally encoded to desired coding quality level <b>2704</b> and then held constant until either another block arrives at the expected video frame rate (in which case the progression is repeated for the new block) or another block arrives at a different frame interval and is classified as non-video.

In <figref idref="DRAWINGS">FIG. 29</figref>, new blocks arriving at times <b>2736</b> and <b>2738</b> after periods <b>2722</b> and <b>2724</b> match the expected frame rate determined by period <b>2720</b> and are classified as video type. The blocks are incrementally encoded to coding quality level <b>2704</b> using bandwidth level <b>2752</b> on graph <b>2750</b>. After the last scene change at time <b>2738</b>, the block at time <b>2740</b> arrives after period <b>2726</b> that is longer than the expected video frame period. The block is classified as non-video and encoding is completed using incremental steps governed by table <b>2200</b> in <figref idref="DRAWINGS">FIG. 24</figref> in the embodiment shown. This low waste method has lower peak and average bandwidth levels than the methods presented in <figref idref="DRAWINGS">FIG. 25</figref> and <figref idref="DRAWINGS">FIG. 27</figref>. The advantage is that bandwidth is not wasted transmitting minor image quality improvements that are only present for a perceptually insignificant number of frame updates before a change in image content occurs. However, once the frame is stable, the image is improved to a final quality state.

<figref idref="DRAWINGS">FIG. 30</figref> shows a variation of the embodiment described herein and illustrated in <figref idref="DRAWINGS">FIG. 29</figref> that maintains a constant perceived quality after a block transition by delaying the decoding operation for a new block data by a number of frames after a transition. Upper axes <b>2800</b> plots a change in coding quality as measured at the output of an encoder. Each tick on the horizontal axis represents the arrival of a new frame of the rasterized image as before. Center plot <b>2860</b> on axes <b>2850</b> plots the change in quality over time at the output of a decoder as perceived by the viewer of the image using an equivalent quality scale. For convenience and without loss of generalization, the described embodiment assumes that the encoder and decoder are synchronized and that changes at the output of the encoder are immediately visible to a user. Plot <b>2890</b> on lower axes <b>2880</b> shows the bandwidth consumed to transmit the image block over the same period of time. Referring to plot <b>2810</b> on graph <b>2800</b>, an initial lossless build state at lossless coding quality level <b>2802</b> is assumed, during which no bandwidth is consumed. When a different block is first encountered at time <b>2830</b>, a constant bandwidth progressive encoding sequence as described herein and illustrated in <figref idref="DRAWINGS">FIG. 25</figref> is initiated and the present coding quality level drops to an initial coding quality level as before.

Perceived quality plot <b>2860</b> starts at initial quality level <b>2852</b> which is an equivalent level to measured initial coding quality level <b>2802</b> for coding quality plot <b>2810</b>. It also follows the same quality pattern as plot <b>2810</b> when the new block arrives at time <b>2830</b>. A constant bandwidth progressive encoding sequence as described herein and illustrated in <figref idref="DRAWINGS">FIG. 25</figref> uses bandwidth level <b>2882</b> on axes <b>2880</b> shown. When a new block arrives at time <b>2832</b> before final coding quality level <b>2802</b> has been reached, a constant perception quality sequence is initiated and the progressive encoding sequence described herein and illustrated in <figref idref="DRAWINGS">FIG. 29</figref> is applied.

At the decoder, the new block is coded to coding quality level <b>2804</b> after three-frame delay <b>2884</b> rather than being decoded immediately. Output image quality graph <b>2860</b> is displayed at perceptually acceptable quality level <b>2854</b> after transition delay <b>2870</b> once all the build data required for the new block is received. Note that transition delay <b>2870</b> appears to be only two frames because data is still being communicated during the third frame. The sequence is repeated for each new block arriving at the expected video frame rate described herein and illustrated in <figref idref="DRAWINGS">FIG. 27</figref>. In the example shown, the new block arriving at time <b>2834</b> is displayed after 3 frames delay period <b>2886</b> and the block arriving at time <b>2836</b> is displayed after 3 frames delay period <b>2888</b>. Other embodiments with different constant perceived quality levels and corresponding frame delays are also contemplated.

The result of the method shown in <figref idref="DRAWINGS">FIG. 30</figref> is that constant perceptually acceptable quality level <b>2854</b> is maintained and the saw tooth quality pattern of <figref idref="DRAWINGS">FIG. 25</figref> is eliminated at the expense of additional display latency. Because human perception cannot detect a delay in the frame sequence, perceptually acceptable quality level <b>2854</b> can be maintained during delayed decoding in spite of measured coding quality (plot <b>2810</b>) being low over the same period due to the decoder not displaying the latest image block. Transition to the constant perception quality sequence may be dependent on available network bandwidth. If there is significant bandwidth available, there is no need to delay the image because acceptable quality may be obtained on the first frame change. In the case of limited bandwidth availability, delay <b>2870</b> is introduced. Care needs to be taken to limit the duration of delay <b>2870</b> as significant frame delays in video or video conferencing applications trigger a requirement for additional audio and video synchronization methods.

<figref idref="DRAWINGS">FIG. 31</figref> shows a variation of the method described herein and illustrated in <figref idref="DRAWINGS">FIG. 27</figref> where the transition from constant bandwidth encoding to constant quality encoding is delayed until the block change interval has stabilized. This ensures that a transition to constant quality encoding is not falsely triggered by a slow drawing operation in sub-system <b>100</b> (shown in <figref idref="DRAWINGS">FIG. 1</figref>), as might occur during the drawing of a complex still image.

Upper axes <b>2900</b> plots a change in coding quality over time and each tick on the horizontal axis represents the arrival of a new frame of the rasterized image as before. Plot <b>2960</b> on lower axes <b>2950</b> shows the bandwidth consumed to transmit the image block over the same period of time. Referring to plot <b>2910</b> on graph <b>2900</b>, an initial lossless build state at lossless coding quality level <b>2902</b> is assumed, during which no bandwidth is consumed. When a different block is first encountered at time <b>2930</b>, a constant bandwidth progressive encoding sequence as described by <figref idref="DRAWINGS">FIG. 25</figref> is initiated and the present coding quality level drops to an initial coding quality level. Progressive encoding is then used to encode and transmit the new block using constant bandwidth level <b>2952</b>.

However, unlike previously described embodiments, the block arriving at time <b>2930</b> contains initial image content associated with a complex still image that takes multiple frame updates to stabilize. During this time the image encoding is restarted multiple times (over time period <b>2920</b> shown) until the image stabilizes and builds to final level <b>2902</b> after several frames. Each time additional data arrives at a period not aligned with an expected video frame, a stabilization counter (as described in step <b>2130</b>) is re-initialized.

The arrival of a new block at time <b>2932</b> represents the start of a video sequence. The quality drops as before and the encoder restarts a constant bandwidth progressive encoding on each block change (over time period <b>2922</b> shown). After a pre-defined number of frame counts at which a block changes at an expected video frame rate (the embodiment shown in <figref idref="DRAWINGS">FIG. 31</figref> uses a stabilization counter of three frames), at time <b>2934</b> the block is identified as a video type and is encoded using a constant quality sequence governed by table <b>2400</b> (in <figref idref="DRAWINGS">FIG. 26</figref>) or another video-related encoding sequences such as the sequence governed by table <b>2600</b> in <figref idref="DRAWINGS">FIG. 28</figref>. The constant coding quality sequence continues over period <b>2924</b> until time <b>2936</b> where a non-video block is detected and the sequence transitions back to the constant bandwidth sequence, where a progression to final quality level <b>2902</b> is executed.

<figref idref="DRAWINGS">FIG. 32</figref> is a diagram showing an embodiment of method <b>2130</b> in <figref idref="DRAWINGS">FIG. 23</figref> for classifying a block as video or non-video based on block change rate. As a first step <b>3100</b>, a block is tested for change. In case <b>3102</b>, the block has not changed so it is tested for the expiry of a counter that detects the end of an expected video frame period as step <b>3110</b>. In case <b>3110</b>, the counter has expired so the block is classified as non-video in step <b>3120</b>. In case <b>3114</b>, the counter has not expired so the counter is updated as step <b>3116</b> and the block is left in its previously classified state.

In case <b>3104</b>, the block has changed so a counter test is conducted as step <b>3130</b> to determine if the change is at an expected video frame period. For example, a table may be used to store multiple values that correspond to expected update counts at multiples of expected frame rates. In case <b>3132</b>, the period since the previous block change is within a time window corresponding with a video frame period so the block is classified as video in step <b>3140</b> and the frame counter is reset as step <b>3160</b>. In case <b>3134</b>, the period since the previous block change is outside a video frame period window so the block is classified as non-video in step <b>3150</b> and the frame counter is reset as step <b>3160</b>.

Note that step <b>3180</b> classifies a changed block as video or non-video immediately after a single block transition at an expected frame rate. In an alternative embodiment such as the embodiment described below and illustrated in <figref idref="DRAWINGS">FIG. 34</figref>, a frame stability test is conducted before a block is classified.

<figref idref="DRAWINGS">FIG. 34</figref> shows an alternative embodiment to step <b>3180</b> in <figref idref="DRAWINGS">FIG. 33</figref>. Step <b>3280</b> show a classification method for changed blocks that includes a stability check. Case <b>3204</b> is equivalent to case <b>3104</b> in <figref idref="DRAWINGS">FIG. 33</figref> where a block is identified as changed. In step <b>3230</b>, a counter test is conducted in the same way as step <b>3130</b> in <figref idref="DRAWINGS">FIG. 33</figref>. In case <b>3232</b> the period since the previous block change is within an expected video frame period window so the stability counter is incremented as step <b>3260</b> and stability test <b>3220</b> is conducted to determine if the video block is stable. In the described embodiment, a pre-requisite number of sequential frames that meet the video block period criterion is counted by the stability counter.

In case, <b>3222</b>, the video block is stable so it is classified as video as step <b>3240</b>. In case <b>3224</b>, the video block is not yet stable so it is classified as non-video in step <b>3250</b>.

In case <b>3234</b>, the period since the previous block change does not match a video frame period so the stability counter is reset as step <b>3210</b> and the block is classified as non-video in step <b>3250</b>.

While a method and apparatus for progressive block encoding using region analysis has been described and illustrated in detail, it is to be understood that many changes and modifications can be made to various embodiments of the present invention, without departing from the spirit thereof.