HK1220531B - Advanced screen content coding solution - Google Patents

Description

Advanced Screen Content Encoding Scheme

Technical Field

The present invention is generally directed to screen content encoding.

Background Art

Compared to traditional natural videos, screen content coding poses new challenges to video compression techniques due to the different signal characteristics. There seem to be several promising techniques for advanced screen content coding, such as pseudo string matching, palette coding, intra-frame motion compensation, or intra-frame block copying.

Among these techniques, pseudo string matching has the highest benefit for lossless coding, but has a large complexity overhead and has difficulties in lossy coding modes. Based on the assumption that non-camera captured content usually contains limited colors rather than continuous tones in natural video, palette coding is developed for screen content. Although the pseudo string matching and palette coding methods show great potential, the working draft (WD) version 4 of screen content coding and the reference software of the HEVC range extension (HEVC RExt) under development use intra-frame motion compensation or intra-frame block copy. This is mainly because motion estimation and compensation methods have been widely studied for decades, and their concept and practical implementation are quite easy (especially for hardware).

However, the coding performance of intra block copy is limited by its fixed block structure. On the other hand, the implementation of block matching, which is sometimes similar to motion estimation for intra images, also significantly increases the computational and memory access complexity of the encoder.

Summary of the Invention

The present invention is directed to an advanced screen content encoding scheme.

In an exemplary embodiment, a method for encoding screen content into a bitstream includes: selecting a palette color table for a coding unit (CU) of the screen content. Creating the palette color table for the CU and creating palette color tables for neighboring CUs. Creating an indexed color index map for the coding unit (CU) of the screen content using the selected palette color table. Encoding/compressing the selected palette color table and the color index map into a bitstream for each of a plurality of CUs.

BRIEF DESCRIPTION OF THE DRAWINGS

For a more complete understanding of the present invention and its advantages, reference is now made to the following description taken in conjunction with the accompanying drawings, wherein like numerals represent like objects and wherein:

FIG1 shows a screen content encoding scheme using a palette color table and an index map mode or a palette mode in an exemplary embodiment of the present invention;

FIG2 shows a screen content decoding scheme for a palette color table and index map mode or a palette mode;

FIG3 shows a process or workflow of a CU's palette color table and screen content scheme in index map mode or palette mode;

Figure 4 shows G, B, R in traditional planar mode (left) entering fill mode (right);

FIG5 shows regenerating a palette color table using adjacent reconstructed blocks;

FIG6 shows an index map parsed from actual subtitle content;

Figure 7 shows a fragment of a 1-D search after a horizontal scan;

Figure 8 shows the U_PIXEL module;

Figure 9 shows the U_ROW module;

Figure 10 shows the U_CMP module;

Figure 11 shows the U_COL module;

Figure 12 shows the U_2D_BLOCK module;

FIG13 illustrates the horizontal and vertical scanning process of an index map of an exemplary CU;

FIG14A shows a 4:2:0 chroma sampling format;

FIG14B shows a 4:4:4 chroma sampling format;

Figure 15 shows interpolation between 4:2:0 and 4:4:4;

FIG16 illustrates index map processing with top/left row buffering;

FIG17 shows an apparatus and method/process applied to current HEVC;

FIG18 shows an example of a communication system;

19A and 19B illustrate exemplary devices provided by the present invention that can implement the methods and concepts described.

DETAILED DESCRIPTION

In the present invention, an advanced screen content coding scheme that is superior to High-Efficiency Video Coding (HEVC) range extension (e.g., HEVC version 2 or HEVC RExt) is described. This new scheme includes multiple algorithms designed specifically for screen content coding. These algorithms include pixel representation using a palette or color table, also referred to herein as a palette color table, palette color compression, color index map compression, string search, and residual compression. The technology is developed in a coordinated manner and can be integrated with HEVC range extension (RExt) and future HEVC extensions to support efficient screen content coding. However, the technology can be implemented using any existing video standard. For simplicity, HEVC RExt is used as an example in the following description to describe and demonstrate compression efficiency using HEVC RExt software. Using a palette color table and index map, defined herein as palette mode, the scheme is integrated as an additional mode in HEVC to demonstrate the performance.

The concepts and descriptions of the present invention are illustrated in the accompanying drawings. According to the present invention, FIG. 1 shows an encoder 10 having a processor 12 including a memory, and FIG. 2 shows a decoder 14 having a processor 16 and a memory, each showing exemplary embodiments of encoding and decoding schemes for the palette mode. As shown, each encoder 10 and decoder 14 includes a processor and a memory and constitutes a coding and decoding scheme. The coding and decoding scheme includes: the processor 12 of the encoder 10 executing a new algorithm or method, the algorithm or method including: Process 1: Creating a palette color table; Process 2: Classifying colors or pixel values using a previously acquired palette color table for corresponding color indexes; Process 3: Encoding the palette color table; Process 4: Encoding the color index map; Process 5: Encoding the residual; Process 6: Writing new syntax elements to the compressed bitstream. The processor 16 of the decoder 14 executes the new algorithm or method including the inverse steps described above. FIG. 3 provides a process or workflow for a screen content solution according to the present invention.

Basically, an efficient color palette compression (CPC) method is performed on each coding unit (CU). A coding unit is the basic unit of operation in HEVC and HEVC RExt, which is a square block of pixels composed of three components (i.e., RGB, YUV, or XYZ).

At each CU level, the CPC method mainly includes two steps: First, in the first step, the processor 12 obtains or generates a palette color table. The table is arranged according to a histogram (i.e., the frequency of occurrence of each color value), its actual color value, or an arbitrary method to improve the efficiency of the following encoding process. Based on the acquired palette color table, each pixel in the original CU is converted into a color index in the palette color table. One contribution of the present invention is a technology for efficiently encoding the palette color table and color index map of each CU into a bit stream through compression, etc. On the receiver side, the processor 16 parses the compressed bit stream to reconstruct the complete palette color table and color index map for each CU, and then further obtains the pixel value at each position by merging the color index and palette color table.

In the example of the present invention, it is assumed that a CU has NxN pixels (N=8, 16, 32, 64 to be compatible with HEVC). The CU typically contains 3 chroma components (i.e. G, B, R; Y, Cb, Cr; X, Y, Z) with different sampling ratios (i.e. 4:4:4, 4:2:2, 4:2:0). For simplicity, the present invention shows a 4:4:4 sequence. For 4:2:2 and 4:2:0 video sequences, chroma upsampling can be used to obtain the 4:4:4 sequence, or each color component can be processed separately. The same procedure described in the present invention can then be applied. For 4:0:0 monochrome video, this can be regarded as a single plane of 4:4:4 without the other two planes. All methods for 4:4:4 can be applied directly.

Fill or plane

Figure 1 illustrates this approach for a CTU or CU. First, a flag called enable_packed_component_flag is defined for each CU to indicate whether the CU is being processed in packed mode or in traditional planar mode (i.e., G, B, R or Y, U, V components are processed separately). Figure 4 shows G, B, and R in traditional planar mode (left) transitioning to packed mode (right). YUV or other color formats can be processed in the same manner as shown for RGB content.

The fill mode and the plane mode each have their own advantages and disadvantages. For example, the plane mode supports parallel color component processing of G/B/R or Y/U/V. However, there may be a problem of low coding efficiency. The fill mode can share the header information of the CU (such as the palette color table and index map in the present invention) between different color components. However, parallelism may be interrupted. A simple way to determine whether the current CU should be encoded in a filled form is to measure the rate-distortion (R-D) cost. The enable_packed_component_flag is used to explicitly send the coding mode to the decoder.

In addition, in order to define the enable_packed_component_flag at the CU level for low-level processing, it can be copied at the slice header or even the sequence level (such as sequence parameter set or picture parameter set) to allow slice level or sequence level processing according to specific application requirements.

Palette color table and index map acquisition

As shown in Figure 1, in process 1 and process 3, the pixel position of each CU is horizontal, and the palette color table and index map in the subsequent processing process are obtained. Each different color is arranged in the palette color table according to a histogram (i.e., frequency of occurrence), color value, or any method to improve the efficiency of the subsequent encoding process. For example, if the differential pulse code modulation (DPCM) method is used to encode the difference between adjacent pixels in the encoding process, and if the adjacent pixels are assigned adjacent color indexes in the palette color table, the best encoding result can be obtained.

After obtaining the palette color table, each pixel is mapped to a corresponding color index to form an index map of the current CU. The processing of the index map is described in the subsequent section.

For traditional planar CUs, each color or chroma component can have its own palette color table, such as colorTable_Y, colorTable_U, colorTable_V, colorTable_R, colorTable_G, or colorTable_B, some of which are listed here as examples. At the same time, the palette color table of the main component, such as Y in YUV or G in GBR, can be obtained and shared with all components. Usually after this sharing, other color components except Y or G may have some mismatches with the shared components in the palette color table regarding the original pixel color. The residual engine (such as the HEVC coefficient encoding method) can then be used to encode these mismatched residuals. On the other hand, for a padded CU, a single palette color table is shared among all components.

A pseudo code is provided to prove the acquisition of the palette color table and index map as follows:

deriveColorTableIndexMap()

{

deriveColorTable();

deriveIndexMap();

}

deriveColorTable(src,cuWidth,cuHeight,maxColorNum)

{

//src—Input video resource in plane or fill mode

//cuWidth, cuHeight—the width and height of the current CU

/*maxColorNum—the maximum number of colors allowed in the color table*/

/*horizontal*/

//

//memset(colorHist,0,(1<<bitDepth)*sizeof(UINT))

pos=0;

cuSize = cuWidth * cuHeight;

When (pos < cuSize) {

colorHist[src[pos++]]++;

}

/* Only extract non-zero entries in colorHist[] for the ordered list of color values */

j = 0;

for (i=0; i<(1<<bitDepth); i++)

{

if (colorHist[i]!= 0)

colorTableIntensity[j++]=colorHist[i];

}

colorNum = j;

/*quicksort for histgram*/

colorTableHist=quickSort(colorTableIntensity,colorNum);

/*If maxColorNum>=colorNum, extract all colors*/

/*If maxColorNum < colorNum, only extract maxColorNum colors for colorTableHist. In this case, all pixels will find the best matching color, the corresponding index and the difference encoded by the residual engine (the actual pixel and its corresponding color). */

/*The optimal number of colors in the color table can be determined by iterating the R-D cost. */

}

deriveIndexMap()

{

pos=0;

cuSize = cuWidth * cuHeight;

When (pos < cuSize)

{

minErr = MAX_UINT;

For (i=0; i<colorNum; i++)

{

err=abs(src[pos]–colorTable[i]);

if (err < minErr)

{

minErr = err;

idx=i;

}

}

idxMap[pos] = idx;

}

}

Palette color table processing

For process 1 in FIG1 , the palette color table processing involves the processor 12 encoding the size of the palette color table (i.e., the total number of colors) as well as each color itself. Encoding each color in the palette color table consumes the most bits. Therefore, the focus is on color encoding (or encoding each entry in the palette color table).

The most straightforward way to encode colors in a palette color table is to use a pulse code modulation (PCM)-style algorithm, where each color is encoded separately. Alternatively, the nearest prediction of successive colors can be used, and then the predicted delta can be encoded instead of the default color value, which is the DPCM (Differential PCM) style. Both methods can then be entropy-coded using either an equal probability mode or an adaptive context mode, depending on the trade-off between complexity and coding efficiency.

Another advanced scheme called adjacent palette color table merging is revealed here, in which color_table_merge_flag is defined to indicate whether the current CU uses the palette color table of the left CU or the upper CU. If not, the current CU will explicitly carry the palette color table signaling. For the merging process, another color_table_merge_direction indicates whether the merging direction is from the upper CU or the left CU. Of course, the candidates may not be limited to the current upper CU or the left CU, such as the upper left CU, the upper right CU, and so on. However, the upper CU and the left CU are used in the present invention to prove the point. In either case, each pixel is compared with the entry in the existing palette color table, and through deriveIdxMap(), each pixel is assigned the index that produces the minimum prediction difference (that is, the pixel minus the closest color in the palette color table). For the case where the prediction difference is non-zero, all these residuals are encoded using the HEVC RExt residual engine. It should be noted that whether the merging process is used may depend on the R-D cost.

There are several ways to generate the adjacent palette color table used in the merge process for encoding the current CU. Depending on their implementation, one of them requires updating both the encoder and decoder, while the others are encoder-side only.

Update the encoder and decoder simultaneously: In this method, regardless of the depth, size, etc. of the CU, the palette color table of the adjacent CU is generated based on the available reconstructed pixels. For each CU, the reconstruction is retrieved for the adjacent CU of the same size and depth (assuming that the color similarity is high in this case). For example, as shown in Figure 5, if the current CU is 16x16 and the depth is 2, no matter how its adjacent CU is divided (for example, the left CU is 8x8 and the depth is 3; the upper CU is 32x32 and the depth is 1), the pixel compensation (=16) will start from the current CU and process the left 16x16 block to the left and the upper 16x16 block upward. It should be noted that both the encoder and the decoder should maintain this process.

Only the encoder's process is constrained: For this method, the merging process occurs when the current CU has the same size and depth as the CU above and/or the CU on the left. In subsequent operations, the color index map of the current CU is obtained using the palette color table of the available adjacent CU. For example, for the current 16x16 CU, if its adjacent CU, that is, the CU located above or to the left, is encoded using the palette color table and index method, the current CU directly uses its palette color table to obtain the R-D cost. This merge cost is compared with the case where the current CU explicitly obtains its palette color table (as well as other traditional modes present in the HEVC or HEVC RExt). The mode that produces the smaller R-D cost is selected as the final mode written to the output bitstream. It can be seen that only the encoder needs to try/emulate different potential modes. On the decoder side, the color_table_merge_flag and color_table_merge_direction indicate the merge decision and merge direction, and no additional processing is required.

Color index image processing

For process 3 in Figure 1 , several solutions have been developed for encoding the color index map, such as RUN mode, RUN and COPY_ABOVE, and adaptive neighbor index prediction. In this invention, a 1D string matching method and its 2D variant are disclosed for index map encoding. At each location, a matching point is found, and the matching distance and length for 1D string matching, or the width/height for 2D string matching, are recorded. For non-matching locations, their index value or the delta between the index value and the predicted index value is encoded directly.

Here we present a method for direct 1D search using a color index map. See Figure 6 for an index map parsed from real subtitle content. Figure 7 shows a fragment after a 1D search (i.e., the beginning of the index map).

String matching is applied at the head of the 1-D color index vector. An example of this 1-D string matching is given below. For the first position of each index map, such as 14 shown in Figure 7, since there is no cached reference, the first index is considered a "non-matching pair", where -1 and 1 are assigned to their corresponding distance and length, recorded as (dist, len) = (-1, 1). For the second index, there is another "14", which is the first index encoded as a reference, so dist = 1. Because there is another "14" in the third position, the length is 2, that is, len = 2 (assuming that each index in use can be directly used as a reference for the next index). Moving forward to the 4th position, "17" is encountered, which has not appeared before. Therefore, it is encoded as a non-matching pair again, that is, (dist, len) = (-1, 1). For the non-matching pair, the flag is encoded (for example, "dist == -1"), followed by the actual value of the index (such as the first occurrence of "14", "17", "6", etc.). On the other hand, for the matching pair, the flag is still encoded (eg, "dist!=-1") and is followed by the length of the matching string.

Here is a summary of the encoding process using the exemplary index shown in Figure 7:

dist=-1, len=1, idx=14 (no match)

dist=1, len=2 (match)

dist=-1, len=1, idx=17 (mismatch)

dist=1, len=3 (match)

dist=-1, len=1, idx=6 (mismatch)

dist=1, len=25 (match)

dist=30, len=4 (match) /* because "17" has appeared before*/

….

The pseudo code for obtaining the matching pair is provided as follows:

Void deriveMatchedPairs(TComDataCU*pcCU,Pel*pIdx,Pel*pDist,Pel*pLen,UInt uiWidth,UInt uiHeight)

{

//pIdx is limited to the range of uiWidth*uiHeight idx CU

UInt uiTotal=uiWidth*uiHeight;

UInt uiIdx = 0;

Int j = 0;

Int len = 0;

//If there is no left/top buffer, encode the first pixel as itself

pDist[uiIdx]=-1;

pLen[uiIdx]=0;

uiIdx++;

When (uiIdx < uiTotal)

{

len=0;

dist=-1;

For (j=uiIdx-1; j>=0; j--)

{

//If a match is found, use the current exhaustive search

//You can use fast string search

if (pIdx[j] == pIdx[uiIdx])

{

for (len=0; len<(uiTotal-uiIdx); len++)

{

if (pIdx[j+len]!=pIdx[len+uiIdx])

Break out of the loop;

}

}

If (len>maxLen)/*It is best to change with R-D decision*/

{

maxLen=len;

dist = (uiIdx - j);

}

}

pDist[uiIdx] = dist;

pLen[uiIdx] = maxLen;

uiIdx＝uiIdx+maxLen；

}

}

When utilizing 2D search variations, the following steps are performed:

Identifying the location of the current pixel and the location of the reference pixel as a starting point;

Apply horizontal 1D string matching to the right of the current pixel and the reference pixel. The maximum search length is constrained by the end of the current horizontal line. Record the maximum search length as right_width.

Apply horizontal 1D string matching to the left of the current pixel and the reference pixel. The maximum search length is constrained by the beginning of the current horizontal line. Record the maximum search length as left_width.

Use the pixels below the current pixel and reference pixel as the new current pixel and reference pixel, and perform the same 1D string matching on the next row;

Stop when right_width == left_width == 0;

Now, for each height[n] = {1, 2, 3...}, there is a corresponding width[n] array {{left_width[1], right_width[1]}, {left_width[2], right_width[2]}, {left_width[3], right_width[3]}...};

Define a new min_width array {{lwidth[1], rwidth[1]}, {lwidth[2], rwidth[2]}, {lwidth[3], rwidth[3]}...} for each height[n], where lwidth[n] = min(left_width[1:n-1]), rwidth[n] = min(right_width[1:n-1]);

Then define the size array {size[1], size[2], size[3]...}, where size[n] = height[n] x (lwidth[n] + hwidth[n]);

Assuming size[n] holds the maximum value in the size array, the width and height of the 2D string match are selected using {lwidth[n], rwidth[n], height[n]} respectively.

One way to optimize the speed of the 1D or 2D search is to use a running hash. Described in the present invention is a 4-pixel running hash structure. A running hash is calculated for each pixel in the horizontal direction to generate a horizontal hash array running_hash_h[]. Another running hash is calculated at the head of running_hash_h[] to generate a 2D hash array running_hash_hv[]. Each value match in the 2D hash array represents a 4x4 block match. To perform a 2D match, as many 4x4 block matches as possible are found before comparing the pixel to its neighbors one by one. Since the comparison of pixels one by one is limited to 1 to 3 pixels, the search speed can be greatly increased.

From the above description, it follows that the matching width of each row is different, so each row must be processed separately. To achieve high efficiency and low complexity, a block-based algorithm is developed that can be used in both hardware and software implementations. Much like standard motion estimation, the algorithm processes one rectangular block at a time.

Taking a 4x4 block as an example, as shown in Figure 8, the basic unit in this design is called U_PIXEL. The encoded signal is a flag indicating whether the reference pixel has been encoded in a previous string matching operation. Optionally, the input signal Cmp[n-1] can be set to "0", which allows the final "OR" gate to be removed from the U_PIXEL module.

The first step is to process each row in parallel. Each pixel in a row of the rectangle is assigned to a U_PIXEL block, and this processing unit is called U_ROW. Figure 9 shows an example of the processing unit for the first row.

As shown in Figure 10, 4 U_ROW units are required to process the 4x4 block. Its output is a cmp[4][4] array.

The next step is to process each column of the cmp array in parallel. As shown in Figure 11, the processing unit U_COL processes each cmp in a column of the cmp array.

Four U_COL units are required to process this 4x4 block. As shown in Figure 12, its output is an rw[4][4] array.

Then count the number of zeros in each row of rw[n][0-3] and record the four results in the r_width[n] array. It should be noted that in step #7, r_width[n] is equal to rwidth[n]. l_width[n] is generated in the same way. The min_width array in step #7 can be obtained as: {{l_width[1], r_width[1]}, {l_width[2], r_width[2]}, {l_width[3], r_width[3]}...}.

This hardware structure can be modified to fit any modern CPU/DSP/GPU parallel processing architecture. The simplified pseudo code for a fast software implementation is listed below:

//1. Generate C[][] array

For (y=0; y<height; ++y)

{

For (x=0; x<width; ++x)

{

tmp1 = cur_pixel^ref_pixel;

tmp2＝tmp1[0]|tmp1[1]|tmp1[2]|tmp1[3]|tmp1[4]|tmp1[5]|tmp1[6]|tmp1[7];

C[y][x]=tmp2&(!coded[y][x]);

}

}

//2. Generate CMP[][] array

For (y=0; y<height; ++y)

{

CMP[y][0]＝C[y][0]；

}

For (x=1; x<width; ++x)

{

For (y=0; y<height; ++y)

{

CMP[y][x]＝C[y][x]|CMP[y][x-1]

}

}

//3. Generate RW[][] or LW[][] array

For (x=0; x<width; ++x)

{

RW[0][x]＝CMP[0][x]；

}

For (y=1; y<height; ++y)

{

For (x=0; x<width; ++x)

{

RW[y][x]=CMP[y][x]|RW[y-1][x];

}

}

//4. Convert RW[][] to R_WIDTH[]

For (y=0; y<height; ++y)

{

//Count 0 or leading zero detection

R_WIDTH[y]=LZD(RW[y][0],RW[y][1],RW[y][2],RW[y][3]);

}

There are no data dependencies within each loop, so traditional software parallel processing methods such as loop unrolling and MMX/SSE can be used to improve execution speed.

This method can also be applied to 1D search if the number of rows is limited to 1. The simplified pseudo code for a fast software implementation of a fixed-length 1D search is listed below:

//1. Generate C[] array

For (x=0; x<width; ++x)

{

tmp1 = cur_pixel^ref_pixel;

tmp2＝tmp1[0]|tmp1[1]|tmp1[2]|tmp1[3]|tmp1[4]|tmp1[5]|tmp1[6]|tmp1[7];

C[x] = tmp2&(!coded[x]);

}

//2. Generate RW[] or LW[] array

If (deleted the last "OR" operation in the U_PIXEL module)

Specify RW[] = C[]

otherwise{

RW[0]＝C[0]；

For (x=1; x<width; ++x)

{

RW[x]＝C[x]|RW[x-1]

}

]

//3. Convert RW[][] to R_WIDTH[]

//Count 0 or leading zero detection

If (deleted the last "OR" operation in the U_PIXEL module)

R_WIDTH=LZD(RW[0],RW[1],RW[2],RW[3]);

otherwise

R_WIDTH[y]=COUNT_ZERO(RW[0],RW[1],RW[2],RW[3]);

After both 1D and 2D matches are completed, the largest (ld length, 2d (width x height)) is selected. If the lwidth of the 2D match is not 0, the length of the previous 1D match needs to be adjusted (length = length – lwidth) to avoid overlap between the previous 1D match and the current 2D match. If the length of the previous 1D match becomes 0 after the adjustment, it is deleted from the match list.

If the previous match is a 1D match, the next starting position is calculated using current_location+length, or if the previous match is a 2D match, the next starting position is calculated using current_location+(lwidth+rwidth). When performing a 1D match, if any pixel to be matched belongs to any previous 2D match area, where the pixel position has been covered by a 2D match, the next pixels are scanned until a pixel position that has not been encoded in the previous match is found.

After obtaining these matching pairs, the entropy engine is used to convert these symbols into a binary stream. The example here uses the concept of equal probability context mode. For better compression efficiency, advanced adaptive context mode can also be used.

//For each CU loop, uiTotal = uiWidth * uiHeight, uiIdx = 0;

When (uiIdx < uiTotal) {

//*pDist: stores distance values for each matching pair

//*pIdx: stores index values for each matching pair

//*pLen: Stores the length value for each matching pair

//encodeEP() and encodeEPs() both reuse HEVC or similar bypass entropy coding.

if (pDist[uiIdx] == -1)

{

Each binary is encoded with an equal probability pattern to indicate

//Whether the current pair matches.

unmatchedPairFlag = TRUE;

encodeEP(unmatchedPairFlag);

//uiIndexBits is controlled by the size of the color table

// That is: for 24 different colors, we need 5 bits, for 8 colors, we need 3 bits

encodeEPs(pIdx[uiIdx],uiIndexBits);

uiIdx++;

}

otherwise

{

unmatchedPairFlag = FALSE;

encodeEP(unmatchedPairFlag);

/*Use the maximum possible limit to binarize*/

UInt uiDistBits = 0;

//Compensation is used to add additional references from adjacent blocks

//Here, first make the compensation equal to 0;

When ((1<<uiDistBits)<＝(uiIdx+offset))

{

uiDistBits++;

}

encodeEPs(pDist[uiIdx],uiDistBits);

/*Use the maximum possible limit to binarize*/

UInt uiLenBits = 0;

When ((1<<uiLenBits)<=(uiTotal-uiIdx))

{

uiLenBits++;

}

encodeEPs(pLen[uiIdx],uiLenBits);

uiIdx+=pLen[uiIdx];

}

}

The following is the encoding process of each matching pair. Correspondingly, the decoding process of the matching pair is as follows:

//For each CU loop, uiTotal = uiWidth * uiHeight, uiIdx = 0;

When (uiIdx < uiTotal) {

//*pDist: stores distance values for each matching pair

//*pIdx: stores index values for each matching pair

//*pLen: Stores the length value for each matching pair

// Both parseEP() and parseEPs() reuse HEVC or similar bypass entropy coding.

//Parse non-matching pair flags

parseEP(&uiUnmatchedPairFlag);

if (uiUnmatchedPairFlag)

{

parseEPs(uiSymbol,uiIndexBits);

pIdx[uiIdx]＝uiSymbol；

uiIdx++;

}

otherwise

{

/*Use the maximum possible limit to binarize*/

UInt uiDistBits = 0;

//Compensation is used to add additional references from adjacent blocks

//Here, first make the compensation equal to 0;

When ((1<<uiDistBits)<＝(uiIdx+offset))

uiDistBits++;

UInt uiLenBits = 0;

When ((1<<uiLenBits)<=(uiTotal-uiIdx))

uiLenBits++;

parseEPs(uiSymbol,uiDistBits);

pDist[uiIdx] = uiSymbol;

parseEPs(uiSymbol,uiLenBits);

pLen[uiIdx]＝uiSymbol；

for (UInt i=0; i<pLen[uiIdx]; i++)

pIdx[i+uiIdx]=pIdx[i+uiIdx-pDist[uiIdx]];

uiIdx+=pLen[uiIdx];

}

}

It should be noted that only pixels in non-matching positions are encoded into the bitstream. In order to have a more accurate statistical model, only these pixels and their adjacent pixels are used for palette color table acquisition, rather than all pixels in the CU.

These indexes or delta outputs typically include a limited number of special values for some coding modes. This invention introduces a second delta palette table to take advantage of this discovery. This delta palette table can be built after all text data is available in the CU and is explicitly sent in the bitstream. Alternatively, the delta palette table can be built adaptively during the encoding process so that the table does not need to be included in the bitstream. The delta_color_table_adaptive_flag is defined for this option.

Another advanced scheme called adjacent incremental palette color table merging is provided. For adaptive incremental palette generation, the encoder can use the incremental palette of the upper CU or the left CU as the initial starting point. For non-adaptive palette generation, the encoder can also use the incremental palette of the upper CU or the left CU and compare the RD costs between the upper CU, the left CU, and the current CU.

Define delta_color_table_merge_flag to indicate whether the current CU uses the delta palette color table of the left CU or the upper CU. Only when delta_color_table_adaptive_flag==0 and delta_color_table_merge_flag==0, the current CU will explicitly carry the delta palette color table signaling.

For the merging process, if delta_color_table_merge_flag is determined, another delta_color_table_merge_direction is defined to indicate whether the merge candidate is from the upper CU or the left CU.

An example of the encoding process for adaptive delta palette generation is shown below. On the decoding side, whenever the decoder receives text data, it regenerates the delta palette based on the reverse steps:

Define palette_table[] and palette_count[];

Initialize palette_table(n) to n (n=0...255). Optionally, palette_table[] of the upper CU or the left CU can be used as the initial value.

Initialize palette_count(n) to 0 (n=0...255). Optionally, palette_count[] of the upper CU or the left CU can be used as the initial value.

For any increment value c':

Position n so that palette_table(n) == delta c';

Set n as the new index of delta c’;

++palette_count(n);

Sort palette_count[] so that palette_count[] is in descending order;

Sort palette_table[] accordingly;

Return to step 1 until all delta c' in the current LCU are processed.

For any block including text and graphics, a shielding mark is used to separate the text portion from the graphics portion. The text portion is compressed using the above method, and the graphics portion is compressed using another compression method.

It should be noted that because the values of any pixels covered by the shielding mark have been losslessly encoded by the text layer, the pixels in the graphic portion can be regarded as "insignificant pixels". When compressing the graphic portion, arbitrary values can be assigned to insignificant pixels to achieve optimal compression efficiency.

Because the palette color table acquisition can handle lossy parts, the index map must be losslessly compressed. This allows efficient processing using 1D or 2D string matching. In the present invention, the 1D or 2D string matching is constrained to the current LCU, but the search window can extend beyond the current LCU. It should also be noted that the matching distance can be encoded using a pair of motion vectors in the horizontal and vertical directions, i.e. (MVy=matched_distance/cuWidth, MVy=matched_distance-cuWidth*MVy).

Assuming that images may have different spatial structures in local areas, the color_idx_map_pred_direction directive is defined to allow for 1D searches in either the horizontal or vertical direction. The optimal index scan direction can be determined based on the R-D cost. Figure 6 shows the scan direction starting from the first position. Figure 9 also illustrates the horizontal and vertical scan modes. An 8x8 CU is used as an example. For both horizontal and vertical scan modes, the deriveMatchPairs() and related entropy coding steps are performed twice. The final scan direction is then selected based on the minimum RD cost.

Improved Binarization

As shown in FIG13 , the matching information pair of the palette color table and the color index map is encoded. This encoding is performed using fixed-length binarization. Alternatively, variable-length binarization can be used.

For example, for palette color table encoding, the table can have 8 different color values. Therefore, the color index map only contains 8 different indices. Instead of using fixed 3 binary digits to equally encode each index value, only 1 bit, such as 0, can be used to represent the background pixel. The remaining 7 pixel values are then encoded using fixed-length codewords such as 1000, 1001, 1010, 1011, 1100, 1101, and 1110 to encode the color index. This is based on the fact that the background color may occupy the largest percentage, so there are special codewords for this purpose to store the total number of binary digits. This situation often occurs for screen content. Taking a 16x16 CU as an example, binarization of the fixed 3 binary digits requires 3x16x16=768 binary digits. Alternatively, let the 0 index be the background color occupying 40%, and the other colors be evenly distributed. In this case, only 2.8x16x16<768 binary digits are required.

For matching pair encoding, assuming a constrained implementation of the method within the region of the current CU, a maximum value can be used to limit the binarization. Mathematically, in each case, the matching distance and length can be as long as 64x64=4K. But this does not happen together. For each matching position, the matching distance is limited by the distance between the current position and the first position in the reference cache (e.g., the first position in the current CU), such as L. Therefore, the maximum number of bins binarized for this distance is log2(L)+1 (instead of a fixed length), and the maximum number of bins binarized for the length is log2(cuSize-L)+1, where cuSize=cuWidth*cuHeight.

In addition to the palette color table and index map, the residual coding can be significantly improved by different binarization methods. For HEVC Rex and HEVC versions, it is assumed that the residual fluctuations after prediction, conversion and quantization should be small, and the conversion coefficients are binarized using variable-length coding. However, after the introduction of conversion jumps, especially for conversion jumps based on different colors on the screen content, there will usually be residuals with large random values (smaller values that are not close to "1", "2", "0"). If the current HEVC coefficient binarization is used, very long codewords will be generated. Optionally, a fixed-length binarization is used to save the coding length for the residuals generated by the palette color table and index coding mode.

Adaptive Chroma Sampling for Mixed Content

Various techniques for efficient screen content encoding under the HEVC/HEVC-RExt architecture are provided above. In practice, in addition to pure screen content (such as text and graphics) or pure natural video, there is also content that includes screen material and natural video captured by a camera, which is called mixed content. Currently, 4:4:4 chroma sampling is used to process mixed content. However, for the natural video portion captured by the embedded camera in such mixed content, the 4:2:0 chroma sampling is sufficient to provide lossless perceptual quality. This is because the human visual system is not very sensitive to spatial variations of the chroma component compared to spatial variations of the luminance component. Therefore, the chroma portion is usually subsampled (for example, the ordinary 4:2:0 video format) to achieve a significant reduction in bit rate while preserving the same reconstruction quality.

The present invention provides a new flag (ie, enable_chroma_subsampling) that is defined at the CU level and sent recursively. For each CU, the encoder determines whether to encode it using 4:2:0 or 4:4:4 based on the rate-distortion cost.

As shown in FIG. 14A and FIG. 14B , FIG. 14A and FIG. 14B are 4:2:0 and 4:4:4 chroma sampling formats.

On the encoder side, for each CU, assuming the input is a 4:4:4 source as shown above, the rate-distortion cost is obtained directly using the 4:4:4 encoding process, where enable_chroma_subsampling = 0 or FALSE. The process then subsamples 4:4:4 from the 4:2:0 sample to obtain its bit cost. The reconstructed 4:2:0 format is inserted back into the 4:4:4 format for distortion measurement (using SSE/SAD). When the CU is spatially encoded in 4:2:0, the distortion rate cost is obtained along with the bit cost, and this distortion rate cost is compared with the cost when the CU is encoded in 4:4:4. Whichever encoding has the lower distortion rate cost is selected as the final encoding.

As shown in Figure 15, Figure 15 shows the interpolation process from 4:4:4 to 4:2:0 and the interpolation process from 4:2:0 to 4:4:4. Generally, such a video color sampling format conversion process requires a large number of interpolation filters.

To reduce the complexity of the implementation, the HEVC interpolation filter (i.e., DCT-IF) can be used. As shown in Figure 15, the "square boxes" represent the original 4:4:4 samples. From 4:4:4 to 4:2:0, DCT-IF is used to vertically insert half pixels ("circles") for the chroma components. For ease of illustration, quarter-pixel positions ("diamonds") are also shown. Gray shaded "circles" are extracted to form 4:2:0 samples. For interpolation from 4:2:0 to 4:4:4, the process starts with the gray "circles" in the chroma components, horizontally inserts half-pixel positions to obtain all "circles", and then uses DCT-IF to vertically insert the "square boxes". All inserted "square boxes" are selected to form the reconstructed 4:4:4 source.

Encoder control

As discussed in the previous section, several flags are exposed to control low-level processing. For example, the enable_packed_component_flag is used to indicate whether the current CU is encoded using padded or traditional planar encoding. Whether padded mode is enabled can depend on the R-D cost calculated at the encoder. For a practical encoder implementation, as shown in Figure 3, a low-complexity solution is achieved by analyzing the CU's histogram and finding the optimal threshold for decision making.

The size of the palette color table has a direct impact on complexity. maxColorNum is introduced to control the balance between complexity and coding efficiency. The most direct approach is to choose the one that produces the lowest R-D cost.

The index image encoding direction can be determined by R-D optimization or using local spatial positioning (such as direction estimation based on the Sobel operator).

The present invention limits the processing within each CTU/CU. In practice, this constraint can be relaxed. For example, for color index map processing, the row caches of the upper CU and the left CU can be utilized, as shown in Figure 16. By utilizing the upper and left caches, the search can be extended to further improve coding efficiency. Assuming that the upper/left caches are composed of reconstructed pixels of adjacent CUs, these pixels (and their corresponding indices) can be referenced before processing the current CU index map. For example, after rearrangement, the current CU index map can be 14, 14, 14, ... 1, 2, 1 (as shown in 1D). Without the row cache reference, the first "14" will be encoded as a non-matching pair. But with the adjacent row caches, the string matching can start from the first pixel, as shown below (both horizontal and vertical scan modes are shown).

Decoder Syntax

The following information can be used to describe the decoder shown in Figure 2. The syntax of the present invention complies with the committee draft of HEVC RExt.

7.3.5.8 Code unit syntax:

FIG17 shows an apparatus and method/process applied to current HEVC.

The above identification method/process and device can be applied to wireless, wired or a combination of wireless and wired communication networks, and implemented in the devices described below and the following figures.

FIG18 illustrates an example of a communication system 100 utilizing signaling to support advanced wireless receivers in accordance with the present invention. Generally, the system 100 enables multiple wireless users to transmit and receive data and other content. The system 100 can implement one or more channel access methods, such as code division multiple access (CDMA), time division multiple access (TDMA), frequency division multiple access (FDMA), orthogonal frequency division multiple access (OFDMA), or single-carrier frequency division multiple access (SC-FDMA).

In this example, the communication system 100 includes user equipment (UE) 110a-110c, radio access networks (RAN) 120a-120b, a core network 130, a public switched telephone network (PSTN) 140, the Internet 150, and other networks 160. Although a specific number of components or units are shown in FIG18 , any number of these components or units may be included in the system 100.

The UEs 110a-110c are configured to operate and/or communicate within the system 100. For example, the UEs 110a-110c are configured to transmit and/or receive wireless signals or wired signals. Each UE 110a-110c represents any suitable end-user device, and may include (or be referred to as) the following: user equipment/device (UE), wireless transmit/receive unit (WTRU), mobile station, fixed or mobile subscriber unit, pager, cellular phone, personal digital assistant (PDA), smartphone, laptop, computer, touchpad, wireless sensor, or consumer electronic device.

The RANs 120a-120b described herein include base stations 170a-170b, respectively. Each base station 170a-170b is configured to wirelessly connect to one or more UEs 110a-110c to enable the UEs to access the core network 130, the PSTN 140, the Internet 150, and/or the other networks 160. For example, the base stations 170a-170b may include (or be) one or more well-known devices, such as a base transceiver station (BTS), a Node-B (NodeB), an evolved NodeB (eNodeB), a home base station, a home evolved base station, a site controller, an access point (AP), a wireless router, a server, a router, a switch, or other processing entities in a wired or wireless network.

In the embodiment shown in FIG18 , the base station 170 a forms part of the RAN 120 a, which may include other base stations, units, and/or devices. Additionally, the base station 170 b forms part of the RAN 120 b, which may include other base stations, units, and/or devices. Each base station 170 a-170 b operates within a specific geographic area or region to transmit and/or receive wireless signals, where the specific geographic region is sometimes referred to as a “cell.” In some embodiments, multiple-input multiple-output (MIMO) technology using multiple transceivers may be applied to each cell.

The base stations 170a-170b communicate with one or more UEs 110a-110c using wireless communication links over one or more air interfaces 190. The air interfaces 190 may utilize any suitable radio access technology.

It is contemplated that the system 100 may utilize multiple channel access capabilities, including the schemes described above. In certain embodiments, the base station and UE implement LTE, LTE-A, and/or LTE-B. Of course, various other access schemes and wireless protocols may be utilized.

The RANs 120a-120b communicate with the core network 130 to provide voice, data, applications, Voice over Internet Protocol (VoIP), or other services to the UEs 110a-110c. It will be appreciated that the RANs 120a-120b and/or the core network 130 may communicate directly or indirectly with one or more other RANs (not shown). The core network 130 may also serve as a gateway to access other networks (e.g., PSTN 140, Internet 150, and other networks 160). Furthermore, some or all of the UEs 110a-110c may include functionality to communicate with different wireless networks over different wireless links using different wireless technologies and/or protocols.

Although Figure 18 shows an example of a communication system, there are many variations of Figure 18. For example, the communication system 100 may include any number of UEs, base stations, networks, or other components in a suitable configuration, and may also include the EPC shown in any of the figures herein.

Figures 19A and 19B illustrate exemplary devices that can implement the methods and concepts provided by the present invention. Specifically, Figure 19A illustrates an exemplary UE 110, and Figure 19B illustrates an exemplary base station 170. These components can be used in the system 100 or any other suitable system.

As shown in FIG19A , the UE 110 includes at least one processing unit 200. The processing unit 200 performs various processing operations for the UE 110. For example, the processing unit 200 may perform signal encoding, data processing, power control, input/output processing, or any other function that enables the UE 110 to operate in the system 100. The processing unit 200 also supports the methods and concepts detailed above. Each processing unit 200 includes any suitable processing or computing device for performing one or more operations. For example, each processing unit 200 may include a microprocessor, a microcontroller, a digital signal processor, a field programmable gate array, or an application-specific integrated circuit.

The UE 110 also includes at least one transceiver 202. The transceiver 202 is configured to modulate data or other content for transmission by at least one antenna 204. The transceiver 202 is also configured to demodulate data or other content received by the at least one antenna 204. Each transceiver 202 includes any suitable structure for generating wireless transmission signals and/or processing wireless reception signals. Each antenna 204 includes any suitable structure for transmitting and/or receiving wireless signals. One or more transceivers 202 may be used in the UE 110, and one or more antennas 204 may be used in the UE 110. Although shown as a single functional unit, the transceiver 202 may also be implemented using at least one transmitter and at least one separate receiver.

The UE 110 also includes one or more input/output devices 206. The input/output devices 206 facilitate interaction with the user. Each input/output device 206 includes any suitable structure for providing information to the user or receiving information from the user, such as a speaker, microphone, keypad, keyboard, display screen, or touch screen.

In addition, the UE 110 includes at least one memory 208. The memory 208 stores instructions and data used, generated, or collected by the UE 110. For example, the memory 208 may store software or firmware instructions executed by the processing unit 200 and data used to reduce or eliminate interference between incoming signals. Each memory 208 includes any suitable volatile and/or non-volatile storage and retrieval device. Any suitable form of memory may be used, such as random access memory (RAM), read-only memory (ROM), a hard disk, an optical disk, a subscriber identity module (SIM) card, a memory stick, a secure digital (SD) memory card, and the like.

As shown in FIG19B , the base station 170 includes at least one processing unit 250, at least one transmitter 252, at least one receiver 254, one or more antennas 256, and at least one memory 258. The processing unit 250 performs various processing operations of the base station 170, such as signal encoding, data processing, power control, input/output processing, or any other functions. The processing unit 250 may also support the methods and concepts detailed above. Each processing unit 250 includes any suitable processing or computing device for performing one or more operations. For example, each processing unit 250 may include a microprocessor, a microcontroller, a digital signal processor, a field programmable gate array, or an application-specific integrated circuit.

Each transmitter 252 includes any suitable structure for generating signals for wireless transmission to one or more UEs or other devices. Each receiver 254 includes any suitable structure for processing signals wirelessly received from one or more UEs or other devices. Although shown as separate components, at least one transmitter 252 and at least one receiver 254 can constitute a transceiver. Each antenna 256 includes any suitable structure for transmitting and/or receiving wireless signals. The common antenna 256 shown here is coupled to the transmitter 252 and the receiver 254, one or more antennas 256 can be coupled to the transmitter 252, and one or more separate antennas 256 can be coupled to the receiver 254. Each memory 258 includes any suitable volatile and/or non-volatile storage and retrieval device.

Other details about UE 110 and base station 170 are known to those skilled in the art and are therefore not described in detail here.

It is helpful to define certain terms and phrases used in this patent document. The terms "include" and "comprising," and their derivatives, mean inclusion without limitation. The term "or" is inclusive, meaning and/or. The phrases "associated with," and "associated therewith," and their derivatives, mean to include, be included within, be interconnected with, include, be contained within, be connected to or connected with, be coupled to or coupled with, be communicable with, cooperate with, intertwine, be juxtaposed with, be proximate to, be bound to or bound with, have, have the property of, and the like.

Although the present invention has been described in terms of certain embodiments and generally related methods, various modifications and variations to the embodiments and methods will be apparent to those skilled in the art. Therefore, the foregoing description of the exemplary embodiments does not limit or restrict the present invention. As defined in the following claims, other modifications, substitutions, and variations are possible without departing from the spirit and scope of the present invention.

Claims (25)

1. A method for encoding screen content into a bitstream, characterized in that the method comprises: Create a palette color table for the first coding unit (CU) of the screen content; A first color index map with an index is created for the first CU using the color palette color table, and the index in the first color index map is contained in the color palette color table; A second color index map with an index is created for the second CU of the screen content using the color palette color table, and the index in the second color index map is contained in the color palette color table; The color palette color table, the first color index map of the first CU, and the second color index map of the second CU are encoded into a bit stream. 2. The method according to claim 1, wherein the method is performed using a planar color format or an interlaced color format. 3. The method according to claim 2, wherein the method is performed at a level selected from CU level, strip level, image level or sequence level. 4. The method according to claim 1, wherein the color palette is obtained from the CU or an adjacent CU. 5. The method according to claim 4, wherein the color palette is obtained from adjacent CUs using CUs reconstructed in the pixel domain. 6. The method according to claim 5, further comprising: generating a palette color table of the adjacent CUs based on available reconstructable pixels, regardless of the depth and size of the CU. 7. The method according to claim 4, characterized in that it further comprises: generating a palette color table for the adjacent CUs, wherein the adjacent CUs are encoded using a palette pattern. 8. The method according to claim 4, wherein the adjacent CUs are not encoded using a palette pattern, and the palette color table of the adjacent CUs is passed from the CUs that were previously encoded using a palette pattern. 9. The method according to claim 1, wherein the palette color table is obtained in the pixel domain of the decoder, wherein the encoded bitstream is parsed to reconstruct the palette color table and color index map for the CU. 10. The method according to claim 6, wherein pixel values are obtained at each position of the CU by merging the color index and the palette color table. 11. The method according to claim 1, characterized in that it further comprises: classifying the color or pixel value of the CU based on the previously acquired color palette for the corresponding index. 12. The method according to claim 1, characterized in that it further comprises: writing new syntax elements into the encoded bit stream. 13. The method according to claim 1, characterized in that the color table of the palette is generated and arranged according to the bar chart or its actual color values. 14. The method according to claim 1, wherein each pixel of the CU is converted into a color index in the color palette color table. 15. The method according to claim 1, wherein a flag is defined for the CU to indicate whether the CU is processed in a filled form or a planar mode. 16. The method according to claim 1, wherein the palette color table is processed by encoding the size of the palette color table and each color in the palette color table. 17. The method according to claim 1, further comprising: generating a flag indicating whether the CU utilizes a palette color table of the left CU or the upper CU. 18. The method according to claim 1, characterized in that the index map is encoded using string matching selected from the group consisting of: one-dimensional (1-D) string matching, mixed 1-D string matching, and two-dimensional (2-D) string matching, wherein: The string matching is performed using matching pairs. 19. The method according to claim 17, wherein the string matching is performed using a hashing method. 20. The method according to claim 1, characterized in that a two-dimensional (2D) search method is performed on the color index map by identifying the position of the current pixel and the position of the reference pixel in the CU as the starting point. 21. The method according to claim 1, wherein the CU has a 4:4:4 format processed using a downsampling 4:2:0 sampling format. 22. The method according to claim 21, wherein the downsampling format is processed at a level selected from CU level, strip level, image level, or sequence level. 23. A processor for encoding screen content into a bitstream, characterized in that the processor is used to: Create a palette color table for the first coding unit (CU) of the screen content; A first color index map with an index is created for the first CU using the color palette color table, and the index in the first color index map is contained in the color palette color table; A second color index map with an index is created for the second CU of the screen content using the color palette color table, and the index in the second color index map is contained in the color palette color table; The color palette color table, the first color index map of the first CU, and the second color index map of the second CU are encoded into a bit stream. 24. The processor according to claim 23, wherein the color palette is obtained from the CU or an adjacent CU. 25. The processor according to claim 24, wherein the color palette is obtained from adjacent CUs using CUs reconstructed in the pixel domain.