中文摘要：

目的 调色板编码是屏幕内容编码的典型方法之一，其索引图的编码效率直接影响到调色板编码算法的总体压缩性能。但是，在处理物体前景和文字边缘的过渡区或连接区索引时，现有索引图预测编码方法的效率仍有待改善。为此提出一种基于马尔可夫模型的索引图预测算法。方法 随机选取了2 000个局部预测失败的索引值并将它们划分为3类典型分布，发现前2类分布的索引值往往处于边缘的灰度平滑过渡区，相邻索引值间呈现较为明显的线性变化，进而提出采用1阶2维马尔可夫随机过程来刻画这种线性性。对于一个待预测索引值，首先利用1阶2维马尔可夫模型计算相邻索引值的线性相关得到初始预测值，再利用颜色转移概率最大化确定其最优预测值。结果 本文算法的预测准确率为97.53%，比多级预测算法（MSP）和基于局部方向相关性的预测算法分别平均提高了4.33%和2.10%，尤其适用于包含大量文字字符和几何图元的视频序列的索引图预测。并且，渐近时间复杂度与基于局部方向相关性的预测算法相当，明显低于MSP。具体地，本文算法的实际运行时间比MSP算法节省了95.08%，比基于局部方向相关性的预测算法增加了35.46%。结论 本文提出的基于马尔可夫模型的索引图预测算法通过发掘索引值在边缘区域的线性相关性和特定的颜色转移模式，提高了索引预测效率，并保持了较低的计算复杂度，可应用在屏幕内容文本/图形块的调色板编码中。

英文摘要：

Objective 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. Method 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 p