Current Issue Cover
屏幕内容索引图的马尔可夫预测算法

宋传鸣,何兴,傅博,王相海(辽宁师范大学;大连理工大学;辽宁师范大学计算机与信息技术学院)

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

Song Chuanming,He Xing,Fu Bo,Wang Xianghai(School of Computer and Information Technology,Liaoning Normal University)

Abstract
Background: The pervasive of the mobile - cloud computing promotes more and more applications creating massive screen content data, such as video conference, remote teaching, and desktop virtualization, while these screen content with high resolution needs to be transmitted to the thin clients in real time. Thus the cloud server requires an efficient coding algorithm with both low complexity and high compression. Objective: The 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. And the coding efficiency of index map directly affects the overall compression performance of the palette coding. But when processing the indexes in the gradient area or conjunction area of foreground objects and text edges, the efficiency of state-of-the-art predictive coding methods still need to be improved yet. So an index map prediction algorithm is proposed based on the Markov model in this study. Method: This study selected randomly 2000 indexes from those suffering from local prediction failure and divided them into three typical classes of distribution, of which the first two classes accounted for more than 70%. And it is founded that these indexes belonging to the first two classes of distribution tended to locate the smooth grayscale transitional area of an edge, in which obvious linear change presented between adjacent index values showing a gradual gradient from dark to bright or from bright to dark. It is this linear change that leads to the failure of typical predictive algorithms. Under such a circumstances, a 1-order 2D Markov model is adopted to describe this linearity and a Markov prediction algorithm of screen content''s index map is therefore proposed in this study. Our algorithm consists three steps. First, select the index values suffering from directional prediction failure to create a training data set which the correlation coefficient and the color transition probability of the Markov model are calculated on. Second, when an index fails to be directionally predicted, the 1-order 2D Markov model is used to compute the linear correlation between neighboring indexes to obtain its initial prediction. Third, it is found that the foreground objects and the text edges often exhibit a specific color transfer pattern in the anti-aliasing region. A color transition probability is employed to present the specific color transfer pattern in this study. Thus a color transition probability maximization method is then used to determine the optimal value of the predicted index. Result: 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 comparative to that of the local directional correlation based prediction method, and significantly lower than that of the MSP method. In particular, the actual running time of our algorithm was 95.08% less than that of MSP algorithm, and increased by 35.46% compared with that of the local directional correlation based prediction method. Conclusion: The proposed index prediction algorithm based on the Markov model increased the prediction accuracy by exploiting both the linear correlation and the special color transition mode of the indexes in the edge area, while keeping low computational complexity. The proposed algorithm could be applied in the palette coding of text/graphics blocks in screen content. Meanings: The conclusion of this study verifies that the prediction efficiency of the index map can be improved effectively by using the index’s Markov property. Considering the screen content usually presents higher temporal redundancy than the natural video, this algorithm only uses one key frames to train the Markov model’s parameters so as to ensure low computational complexity. But this manner may also affect the accuracy of the trained parameters to a certain extent. At the same time, this study uses all of the indexes suffering from prediction failure to train the Markov model’s parameters and the color transition probability, without additional operations to judge whether these indexes belong to the first two classes of distribution. If a simple and efficient classification method can be designed, it is expected to obtain more accurate model parameters. In addition, this study only addresses the prediction issue of the indexes in the first two kinds of distribution. However, since the indexes in the third class of distribution do not present obvious local correlation, they cannot be effectively predicted by our proposed Markov model. And for these indexes, the 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 its non-local prediction.
Keywords
QQ在线


关注微信