The pervasiveness of mobile cloud computing promotes increasing applications creating massive screen content data

such as video conference

remote teaching

and desktop virtualization

while these screen contents with high resolution require being transmitted to thin clients in real time. Thus

the cloud server requires an efficient coding algorithm with low complexity and high compression.Palette coding is one of the typical screen content coding methods satisfying the above requirements

which separates the screen content into a palette and an index map. The coding efficiency of an index map directly affects the overall compression performance of palette coding. However

when processing the indices in the gradient or conjunction area of foreground objects and text edges

the efficiency of the state-of-the-art predictive coding methods still requires being improved. Therefore

an index map prediction algorithm is proposed based on the Markov model. This study randomly selected 2 000 indices from those suffering from local prediction failure and divided them into three typical classes of distribution

of which the first two classes constituted more than 70%. These indices belonging to the first two classes of distribution located the smooth grayscale transitional area of an edge

in which an obvious linear change presented between the adjacent index values showed a gradual gradient from dark to bright or from bright to dark. This linear change led to the failure of the typical predictive algorithms. Under these circumstances

a one-order 2D Markov model is adopted to describe this linearity

and a Markov prediction algorithm of the index map of screen content is therefore proposed. Our algorithm consisted of three steps. First

the index values suffering from a directional prediction failure was selected to create a training dataset

in which the correlation coefficient and the color transition probability of the Markov model were calculated on. Second

when an index failed to be directionally predicted

the one-order 2D Markov model was used to compute the linear correlation among the neighboring indices to obtain its initial prediction. Third

the foreground objects and the text edges exhibited a specific color transfer pattern in the anti-aliasing region. A color transition probability was used to present the specific color transfer pattern. Thus

the color transition probability maximization method was used to determine the optimal value of the predicted index. Experimental results showed that the prediction accuracy of the proposed algorithm achieved 97.53%

which was on average 4.33% and 2.10% higher than those of the multi-stage prediction(MSP) method and the local directional correlation-based prediction method

respectively. The proposed method was particularly suitable for the index prediction of the video sequences with multiple text characters and geometric elements. Moreover

the computational complexity of the proposed algorithm was relative to that of the local directional correlation-based prediction method and was significantly lower than that of the MSP method. In particular

the actual running time of our algorithm was 95.08% less than that of the MSP method and increased by 35.46% compared with that of the local directional correlation-based prediction method. The proposed index prediction algorithm based on the Markov model increased the prediction accuracy by exploiting the linear correlation and the special color transition mode of the indices in the edge area while maintaining low computational complexity. The proposed algorithm could be applied in the palette coding of text/graphic blocks in the screen content. The conclusion of this study verifies that the prediction efficiency of the index map can be improved effectively by using the Markov property of index. This algorithm uses only one key frame to train the parameters of the Markov model to ensure low computational complexity

considering that the screen content usually presents higher temporal redundancy than the natural video. However

this method may also relatively affect the accuracy of the trained parameters. Simultaneously

this study uses all of the indices suffering from prediction failure to train the parameters of the Markov model and the color transition probability without additional operations to evaluate whether these indices belong to the first two classes of distribution. If a simple and efficient classification method can be designed

then obtaining accurate model parameters is expected. In addition

this study only addresses the prediction issue of the indices in the first two kinds of distribution. However

given that the indices in the third class of distribution do not present obvious local correlation

these indices cannot be effectively predicted by our proposed Markov model. For these indices

template matching is an optional method that can be used to explore the global color transfer pattern in the edge transition region and thus to realize their non-local prediction.