CN1520186A - 高速逆离散余弦变换方法和装置 - Google Patents

Abstract

提供一种高速逆离散余弦变换的方法和装置。当具有除0以外值的元素的总数不大于一预定临界值时，以预定的顺序从离散余弦变换(DCT)矩阵的所有元素中，查找具有除0以外值的元素。对具有除0以外值的元素执行二维(2D)IDCT。当具有除0以外值的元素的总数大于所述预定临界值时，对DCT矩阵执行2D IDCT。

Description

高速逆离散余弦变换方法和装置

本申请要求2002年11月20日向韩国知识产权局申请的韩国专利申请号第2002-72384号的优先权，其公开内容全部结合于此作为参考。

技术领域

本发明涉及一种高速逆离散余弦变换方法和装置。

背景技术

诸如图像信号的数字数据的压缩，在支持多媒体应用的环境中是最重要的技术之一。由于图像信号一般包括相当数量的数据，从而限制了有效地传输、存储以及处理图像信号。为了克服所述约束，通过诸如MPEG-2、MPEG-4、H.263和H.26L之类的各种国际标准而提出了许多压缩流量算法和译码技术。

现有两种不同类型的压缩技术，也就是，无损失压缩技术和有损失压缩技术。当采用无损失压缩技术时，诸如字符、图形或其他一般数据之类的数据可以以2∶1的平均压缩率被压缩，并且压缩过的数据能够被完整地恢复。另一方面，当采用有损失压缩技术时，也就是，当压缩图像数据、语音数据或声音数据时，对于个人来说，允许难以察觉的较小的数据损失，并且能够达到10∶1的压缩率。最普通的有损失压缩技术之一是转换编码。在转换编码中，以相互间具有高空间相关的预定方式排列数据，并且对所述数据进行正交转换。在正交转换期间，数据被划分为从低频分量变化到高频分量排列的多个频率分量，然后量化每一频率分量。通过上述操作，频率分量之间的相关性几乎消失，并且信号能量集中在低频范围。在由正交转换得到的低频分量中，在其上集中了更多的能量的分量，即具有较高色散值的分量，将通过附加位的使用而得到更准确地表示。给具有比其他分量色散值大四倍的色散值的低频分量(也就是，具有比其他分量幅度大两倍的幅度的低频分量)分配一个附加位。最终，期望所有的频率分量具有相同的量化误差特性。

在多种类型的正交转换中，因为受控于Karhunen-Loeve变换技术的图像信号具有较高的能量集中特性，所以该变换技术被认为是最有效的压缩技术之一。然而，Karhunen-Loeve变换对于不同的图像需要不同的转换函数，从而为Karhunen-Loeve变换的执行施加了很大的限制。作为难于应用的Karhunen-Loeve变换的一种选择，提出了离散余弦变换(DCT)。由于DCT表现出与Karhunen-Loeve变换几乎相同的执行效果，所述执行结果能够实际的应用，并且可以实现，因而，它被认为是众多国际标准中的核心技术之一。在DCT技术中，8×8象素被集合成一个块，并且对每一个块进行离散余弦变换。随着块的大小的增加，数据压缩的效率变得更高，但是变得难于在每一个块上执行DCT。经过多次实验，确定将8×8的块作为DCT单元，该DCT单元符合有效数据压缩和容易执行的要求。

传统的数据压缩技术使用离散余弦变换来消除在压缩图像时所获得的空间冗余。使用运动估计(ME，motion estimation)和运动补偿(MC，motioncompensation)来消除时间冗余。

图1是说明传统二维逆离散余弦变换(2D-IDCT)的框图。通过减少用于IDCT的必要的计算量来获得高速IDCT。如图1所示，2D IDCT的特征在于对一个块的每一行和每一列执行一维(1D)IDCT。特别是，图1所示的2D IDCT的特征在于沿两个不同的方向执行的1D IDCT、位移、和行列算法。换句话说，在2D IDCT中，在行方向上对块执行N次1D IDCT，所述块被移动，然后在列方向上对所述移动的块执行N次IDCT。

图2是比较不同的传统IDCT算法的计算量的图表。图1中有4种在2D IDCT中使用的不同的传统IDCT算法，即基于稀疏矩阵因式分解的Chen’s算法、Wang’s算法、基于离散傅立叶变换的Lee’s算法、以及AAN算法。图2示出了每一传统IDCT算法所要求的乘法和加法的数量。

图3是说明作为高速IDCT算法之一的Wang’s算法的框图。参考图3，响应输入信号x(0)至x(7)而分别输出信号X(0)至X(7)。在输出信号X(0)至X(7)的处理中，在接触点上所实现的计算结果必须传递给随后的接触点。通过将前一接触点乘以在C0至C7之间的一个常数，来获得一接触点。例如，C0＝x(1)+x(7)。Wang’s算法需要16个加法器和26个乘法器。大部分高速算法或多或少的类似于上述的Wang’s算法。

传统的高速IDCT算法一般能够减少IDCT所必须的计算的复杂度。然而，在恢复压缩数据的处理中，传统的高速IDCT算法需要大量的计算。在当前能够提供多种多媒体服务的移动环境中，译码器，即诸如移动电话或个人数字助理(PDAs)之类的移动通信设备，受到大小和功耗上的约束，然而编码器，即多媒体服务提供者的服务系统则相对地不受那些约束的影响。因此，存在减少在译码器中执行IDCT所需计算量的需求。

发明内容

本发明提供一种高速逆离散余弦变换(IDCT)方法和装置，该方法和装置可通过依赖于具有有效值的元素的数量而以逐元素或逐矩阵为基础对离散余弦变换(DCT)矩阵执行二维(2D)IDCT，来显著地减少IDCT期间的计算量。

根据本发明的一个方面，提供一种高速逆离散余弦变换(IDCT)方法，该方法包括(a)当具有除0以外值的元素总数不大于一预定临界值时，以预定顺序在离散余弦变换(DCT)矩阵的所有元素中查找具有除0以外值的元素；(b)对在(a)中查找到的具有除0以外值的元素执行二维(2D)IDCT；以及(c)当具有除0以外值的元素的总数大于所述预定临界值时，对DCT矩阵执行2D IDCT。

根据本发明的另一方面，提供一种高速IDCT装置，该装置包括元素查找单元、元素方式2D IDCT单元、和矩阵方式2D IDCT单元。当具有除0以外值的元素的总数不大于一预定临界值时，元素查找单元以预定顺序在离散余弦变换(DCT)矩阵的所有元素中查找具有除0以外值的元素。元素方式2D IDCT单元对通过元素查找单元所查找到的、具有除0以外值的元素执行2D IDCT。当具有除0以外值的元素的总数大于所述预定临界值时，矩阵方式2D IDCT单元对DCT矩阵上执行2D IDCT。

附图说明

通过参考附图对典型实施例进行详细描述，使得本发明的上述和其他特征以及优点变得更加的明显，其中：

图1是说明传统二维逆离散余弦变换的框图；

图2是表明不同的传统逆离散余弦变换(IDCT)算法的计算量的图表；

图3是说明作为传统高速IDCT算法之一的Wang’s算法的框图；

图4是根据本发明优选实施例的高速IDCT装置的方框图；

图5是说明典型的8×8离散余弦变换(DCT)矩阵的示例的框图；

图6是图4中元素方式(element-wise)2D IDCT单元的方框图；

图7是根据本发明优选实施例的一种高速IDCT方法的流程图；以及

图8是将根据本发明的高速IDCT所使用的计算量与传统高速IDCT所使用的计算量进行比较的图表。

具体实施方式

以下，通过参考在其中示出了本发明优选实施例的附图，更加详细地描述本发明。

图4是根据本发明优选实施例的一种高速逆离散余弦变换(IDCT)装置的方框图。参考图4，高速IDCT装置包括有效元素数量计算单元40、元素查找单元41、元素方式二维(2D)IDCT单元42，和矩阵方式2D IDCT单元43。

如下所示是用于压缩图像数据的过程。首先，对一个图像信号进行离散余弦变换，以将该图像信号划分为多个频率范围。在此，图像数据的能量一般集中在低频范围。因此，通过量化图像数据，有可能使用减少的位数来压缩图像数据。之后，对图像数据进行量化，从而将图像数据划分为相等大小的量子。然后，由一个小于预定数量的值所表示的多个量子被赋予0值，以代替他们各自的原始数据值，以便减少整个数据的大小。同时，由于赋予0值则可能出现数据损失。此后，执行游程长度(run-length)编码，其中字符的重复用相同字符的数量和一个单独字符来代替。当构成每一游程的字符数量增加，并且游程出现的数量增加时，压缩效率增加。此后，执行Huffman编码，在所述Huffman编码中通过锯齿形扫描所获得的整数序列被转换成二进制值。通过这样做，一个8×8矩阵被压缩成许多0和1的组合。为了对这样压缩过的图像数据译码，必须逆向执行上述的压缩处理。

如上所述，在根据对图像数据执行DCT和量化的处理来压缩图像数据的情况中，被压缩数据主要地集中在低频范围，而在高频范围内几乎不存在。当量化尺度变大时，具有0值的元素的数量增加，同时具有除0以外值的元素的数量减少。相反，当量化尺度变小时，具有除0以外值的元素的数量增加。在具有大的量化尺度的情况中，DCT矩阵中具有除0以外值的元素数量将变少。利用传统高速IDCT算法，通过使用传统高速IDCT算法，仅仅对这些元素进行逆离散余弦变换，而不需要对DCT矩阵的所有元素进行逆离散余弦变换。另一方面，在具有小的量化尺度的情况中，存在许多具有除0以外的值的元素，并且使用传统高速IDCT算法是有效的。

在DCT矩阵中具有除0以外值的元素的数量不大于一预定临界值的情况下，元素查找单元41以预定的顺序查找具有除0以外值的元素。元素方式2DIDCT单元42对查找到的元素执行2D IDCT。如上所述，将具有除0以外的值的元素数量与所述预定临界值进行比较，以确定是以逐元素为基础还是以逐矩阵为基础来执行IDCT。所述预定临界值表示具有除0以外值的元素的最大数量，在该值上用于元素方式IDCT的计算量小于用于矩阵方式IDCT的计算量。多次实验已经确定，在量化尺度不大于10时，当临界值设定为15时能够获得最高压缩效率；并且在量化尺度大于10时，当临界值设定为10时能够获得最高压缩效率。

如上所述，对一个压缩文件的译码处理正好与将一个文件编码成压缩文件的处理相反。因此，通过对已压缩的文件顺序地执行Huffman译码、游程长度译码、逆向量化和IDCT来完成译码处理。可以在先于IDCT而执行的游程长度译码期间预先确定DCT矩阵中具有除0以外值的元素的数量。由于游程长度编码用单个0和0序列的长度来代替0序列，因此能够在游程长度译码中算出0序列的长度。通过游程长度译码，也可能识别出具有除0以外的值的元素数量。

换句话说，有效元素数量计算单元40在游程长度译码处理中，仅计数具有除0以外值的元素。例如，假定在编码处理中量化尺度不大于10并且临界值设定为15，以及具有除0以外值的元素的数量不大于15，则以逐元素为基础来执行IDCT要优于以逐矩阵为基础来执行IDCT。

在DCT矩阵中具有除0以外值的元素的数量大于所述预定临界值的情况下，矩阵方式2D IDCT单元43对DCT矩阵执行2D IDCT。在编码处理中量化尺度不大于10并且临界值设定为15，以及具有除0以外值的元素的数量大于15的情况中，则以逐矩阵为基础执行IDCT要优于以逐元素为基础来执行IDCT。矩阵方式2D IDCT单元43使用诸如Wang’s算法、Chen’s算法、Lee’s算法或AAN算法之类的传统高速IDCT算法对DCT矩阵执行诸如2D IDCT。

图5是说明作为典型例子的8×8DCT矩阵的框图。在图5中，表示较多集中的图像数据的元素较暗。属于最低频率范围的元素A1是8×8DCT矩阵中最暗的一个。在8×8DCT矩阵中，元素A1的值被称为一个直流(DC)值，并且其他63个元素A2-A64的值被称为交流(AC)值。DC值和与元素A1相邻的元素的值对于判定整个图像的亮度是很重要的。

就元素查找单元41在查找具有除0以外值的元素时所使用的预定顺序而言，元素查找单元41沿着水平方向或垂直方向对DCT矩阵进行查找。由于大部分具有除0以外值的元素集中在DCT矩阵的左上角附近，因此元素查找单元41最好以锯齿形方式，也就是以A1，A2，A3...，A64的顺序去查找DCT矩阵的元素，借此减少计算量。

图6是图4中元素方式2D IDCT单元42的方框图。参考图6，该2D IDCT单元42包括一个部分值计算器61和一个完整值计算器62。

通常，使用以下等式(1)执行2D IDCT。

$V(x,y)=\underset{i=0}{\overset{N-1}{\mathrm{\Σ}}}\underset{j=0}{\overset{N-1}{\mathrm{\Σ}}}C(i,j)T(i,j)\cos \left(\frac{(2x+1)\mathrm{i\π}}{2N}\right)\cos \left(\frac{(2y+1)\mathrm{j\π}}{2N}\right)...\left(1\right)$

如果i≠0并且j≠0， $C(i,j)=\frac{2}{N}$

如果i＝0或j＝0， $C(i,j)=\frac{1}{N}$

在等式(1)中，T(i，j)表示位于DCT矩阵T中(i+1，j+1)的元素的值，并且V(x，y)表示位于矩阵V的(x+1，y+1)的元素的值，其中矩阵V表示通过对DCT矩阵T进行IDCT所获得的恢复的矩阵。如果DCT矩阵T是一个8×8矩阵，则i，j，x和y的每一个均具有0-7之间的值，并且N＝8。

采用一种叠加原则，以选择性地处理DCT矩阵中具有除0以外值的元素。根据该叠加原则，对每一个DCT系数块或每一预定数量的DCT系数块进行逆离散余弦变换，然后对所有IDCT结果进行求和。该处理得到与对所有DCT矩阵的DCT系数块同时执行IDCT之后相同的结果。在本发明中，以逐个的方式查找DCT系数块值，对具有有效值的DCT系数块进行逆离散余弦变换，并且对IDCT结果求和，从而获得一个恢复的矩阵(恢复该DCT矩阵的原始形式)。为了以逐元素为基础执行2D IDCT，必须对DCT矩阵中具有除0以外值的元素执行等式(2)所示的预定计算处理。

IDCT(T)＝IDCT(T(0，0))+IDCT(T(0，1))+IDCT(T(0，2))+...+IDCT(T(0，7))

         +IDCT(T(1，0))+IDCT(T(1，1))+IDCT(T(1，2))+...+IDCT(T(1，7))

         +IDCT(T(2，0))+IDCT(T(2，1))+IDCT(T(2，2))+...+IDCT(T(2，7))

         +...+

         +IDCT(T(7，0))+IDCT(T(7，1))+IDCT(T(7，2))+...+IDCT(T(7，7))

                                                             ...(2)

在等式(2)中，IDCT(T)表示一个从8×8DCT矩阵T所恢复的8×8矩阵V。IDCT(T(0，0))表示一个8×8矩阵，该8×8矩阵是通过用DCT矩阵T中第一行和第一列上的元素的坐标(i＝0并且j＝0)和值T(0，0)以及恢复的8×8矩阵V中每一个元素的坐标(x和y在0-7之间取值)来替代等式(1)中的变量而得到的。IDCT(T(0，0))说明恢复的8×8矩阵V的一部分。换句话说，根据所述叠加原则，通过对为具有除0以外值的元素而产生的所有矩阵进行求和，来获得恢复的矩阵V。在本发明中，为具有除0以外值的元素而产生的每一矩阵以表格的形式存储在存储器中，并且对定位在存储器地址上的值以及对应于存储器中所存储的所有表格的值进行求和，从而获得恢复的矩阵V。

上述算法可以应用在以下情况：具有除0以外值的元素的数量不大于临界值，所述临界值取决于量化尺度可以是6，10或15，该临界值用于确定是以逐元素为基础来执行IDCT，还是以逐矩阵为基础来执行IDCT。在具有除0以外值的元素数量大于临界值的情况下，能够使用传统的高速算法。诸如MPEG-2，MPEG-4以及H.261之类的各种图像压缩算法一般产生不多于10个具有除0以外值的元素。

例如，当具有除0以外值的元素的数量是10时，通过以下等式(3)来表示元素方式2D IDCT。

IDCT(T)＝IDCT(T(0，0))+IDCT(T(0，1))+IDCT(T(0，2))+IDCT(T(0，3))

       ＝IDCT(T(1，0))+IDCT(T(1，1))+IDCT(T(1，2))

       ＝IDCT(T(2，0))+IDCT(T(2，1))

       ＝IDCT(T(3，0))                                 ...(3)

部分值计算器61，通过用由图4中元素查找单元41所查找到的具有除0以外值的元素的坐标(i，j)和恢复的矩阵V中每一元素的坐标(x，y)代替公式(1)中的变量，而获得构成恢复的矩阵V一部分的IDCT(T(i，j))。完整值计算器62使用叠加原则并且获得一个对应于恢复的矩阵V中每一个元素的完整值V(x，y)。通过对IDCT((T(i，j))求和来获得该完整值，所述IDCT(T(i，j))是由部分值计算器61关于由元素查找单元41所查找到的、具有除0以外的值的每一元素而产生的。

图7是一个根据本发明优选实施例的高速IDCT方法的流程图。参考图7，在步骤70，在游程长度译码期间，计数DCT矩阵中具有除0以外值的元素的数量，所述游程长度译码是预定压缩文件的译码处理过程的一部分，并且在IDCT之前被执行。

在步骤71中，如果具有除0以外值的元素的数量不大于一预定临界值，则在步骤72中以预定的顺序逐个查找具有除0以外的值的元素。在此，在IDCT之前执行的游程长度译码处理中发现具有除0以外值的元素的数量。另外，将临界值设定成具有除0以外值的元素的最大数量，在该值上，元素方式IDCT的计算量小于矩阵方式IDCT的计算量。而且，对具有除0以外值的元素的查找包括一个从DCT矩阵第一列和第一行的元素开始越过DCT矩阵所有元素的锯齿形查找。

此后，在步骤73中，对具有除0以外值的元素进行逆离散余弦变换。换句话说，通过用具有除0以外值的元素的值和坐标以及恢复的矩阵中每一元素的坐标来代替IDCT公式中的变量，而获得恢复的矩阵中每一元素的部分值。此后，根据叠加原则，对关于恢复的矩阵的所有元素而得到的部分值进行求和，从而获得恢复的矩阵的每一元素的完整值。

在步骤71中，如果DCT矩阵中具有除0以外值的元素的数量大于临界值，则在步骤74对DCT矩阵进行2D IDCT。换句话说，使用诸如Wang’s算法、Chen’s算法、Lee’s算法或AAN算法之类的传统高速IDCT算法对DCT矩阵执行二维逆离散余弦变换。

图8是用于将根据本发明的高速IDCT所必需的计算量与传统高速IDCT所必需的计算量进行比较的表。图8表示当量化尺度较大时的实验结果。如上所述，在小量化尺度的情况中，需要使用传统的2D IDCT算法。

本发明的上述实施例能够以计算机程序的形式实现，该计算机程序能够被记录在计算机可读记录介质上，并且能够在数字计算机上执行。

计算机可读记录介质包括诸如ROM、软盘或硬盘之类的磁存储介质；诸如CD-ROM或DVD之类的光记录介质；以及诸如经由Internet的数据传输之类的载波。

根据本发明，可以通过消除对于占DCT矩阵元素大部分的具有0值的元素的不必要的计算来最小化计算量。另外，本发明提供一种用于不同量化尺度的最佳IDCT算法。例如，当数据压缩率低并且具有除0以外值的元素的数量少时，采用传统高速IDCT算法。即使本发明的元素方式2D IDCT算法和传统IDCT算法都被使用，因为几乎80％的目标图像信号使用本发明的元素方式2D IDCT算法，因此IDCT的计算量仍将显著地减少。可使用优于传统高速IDCT算法的本发明的元素方式2D IDCT算法进行处理的图像数据的百分比基于情况而变化。此外，根据本发明，可以通过显著地减少由IDCT模式执行的计算量来设计一种具有增强的性能的固定视频译码器或具有减低的功耗的紧凑型移动视频译码器，所述计算量相当于在视频译码器中所执行的全部计算量的25-30％。

在现有技术中，高速DCT算法中的计算均参考块结束符(EOB)来执行，并且对于不同的扫描方法要求不同的高速IDCT算法。然而，本发明能够不考虑扫描的类型而得到应用，无论所述扫描类型是锯齿形扫描、水平扫描或垂直扫描。另外，本发明最大化了在计算中其所应用的有效数量。换句话说，因为在本发明中IDCT仅执行了一轮，因而，本发明的峰值信噪比将高于现有技术中的峰值信噪比。

虽然已经通过参考典型实施例特别示出和描述了本发明，但是本领域技术人员应当理解，可以在不脱离由随后的权利要求书所限定的本发明的精神和范围的情况下，对本发明在形式和细节上作出变化。

Claims (18)

1.一种高速逆离散余弦变换(IDCT)的方法，包括：

(a)当具有除0以外值的元素的总数不大于一个预定临界值时，以预定的顺序从离散余弦变换(DCT)矩阵的所有元素中查找具有除0以外值的元素；

(b)对在(a)中查找到的具有除0以外值的元素执行二维(2D)IDCT；和

(c)当具有除0以外值的元素的总数大于所述预定临界值时，对DCT矩阵执行2D IDCT。

2.如权利要求1所述的方法，其中(b)包括：

(b1)通过用具有除0以外值的每一元素各自的值和各自的坐标以及恢复的矩阵中每一元素各自的坐标代替IDCT公式中的变量，来获得与DCT矩阵相对应的恢复的矩阵中每一元素各自的部分值；以及

(b2)通过对在(b1)中获得的关于恢复的矩阵的元素的部分值进行求和，得到恢复的矩阵的元素的完整值。

3.如权利要求1所述的方法，其中在(c)中，使用一种高速IDCT算法对DCT矩阵执行2D IDCT，其中所述高速IDCT算法是Wang’s算法、Chen’s算法、Lee’s算法和AAN算法之一。

4.如权利要求1所述的方法，进一步包括：

(a-1)通过在对预定的压缩文件进行游程长度译码期间计数具有除0以外值的元素的数量来获得具有除0以外值的元素的总数，所述游程长度译码在进行从离散余弦变换(DCT)矩阵的所有元素中查找具有除0以外值的元素之前执行。

5.如权利要求1所述的方法，其中所述预定临界值设定为具有除0以外值的元素的最大数，在该值上，用于元素方式IDCT的计算量少于用于矩阵方式IDCT的计算量。

6.如权利要求1所述的方法，其中从DCT矩阵的第一列和第一行的元素开始，以锯齿形方式顺次查找DCT矩阵的元素。

7.一种高速IDCT装置，包括：

元素查找单元，当具有除0以外值的元素的总数不大于一预定临界值时，以预定的顺序从离散余弦变换(DCT)矩阵的所有元素中查找具有除0以外值的元素；

元素方式2D IDCT单元，对由元素查找单元查找到的具有除0以外值的元素执行二维2D IDCT；以及

矩阵方式2D IDCT单元，当具有除0以外值的元素的总数大于所述预定临界值时，对DCT矩阵执行2D IDCT。

8.如权利要求7所述的装置，其中所述元素方式2D IDCT单元包括：

部分值计算器，其通过用具有除0以外值的每一元素各自的值和各自的坐标以及恢复的矩阵中每一元素各自的坐标代替IDCT公式中的变量，来获得与DCT矩阵相对应的恢复的矩阵中每一元素各自的部分值；以及

完整值计算器，其通过对由所述部分值计算器获得的恢复的矩阵的元素的部分值进行求和，而得到恢复的矩阵的元素的完整值。

9.如权利要求7所述的装置，其中矩阵方式2D IDCT单元使用高速IDCT算法对DCT矩阵执行2D IDCT，其中所述传统高速IDCT算法是Wang’s算法、Chen’s算法、Lee’s算法和AAN算法之一。

10.如权利要求7所述的装置，进一步包括一个有效元素数量计算单元，其在游程长度译码处理期间，通过计数具有除0以外值的元素来获得具有除0以外值的元素的总数，所述游程长度译码处理是预定压缩文件译码处理的一部分，并且在IDCT之前被执行。

11.如权利要求7所述的装置，其中所述预定临界值被设定为具有除0以外值的元素的最大数量，在该数量上，元素方式IDCT的计算量少于矩阵方式IDCT的计算量。

12.如权利要求7所述的装置，其中从所述DCT矩阵的第一列和第一行的元素开始，以锯齿形方式依次查找该DCT矩阵的元素。

13.一种用于记录计算机程序代码的计算机可读记录介质，所述计算机程序代码用于使能计算机提供高速逆离散余弦变换(IDCT)服务，所述服务包括：

(a)当具有除0以外值的元素的总数不大于一预定临界值时，以预定的顺序从离散余弦变换(DCT)矩阵的所有元素中查找具有除0以外值的元素；

(b)对在(a)中查找到的具有除0以外值的元素执行二维(2D)IDCT；和

(c)当具有除0以外值的元素的总数大于预定临界值时，对DCT矩阵执行2D IDCT。

14.如权利要求13所述的计算机可读记录介质，其中(b)包括：

(b1)通过用具有除0以外值的每一元素各自的值和各自的坐标以及恢复的矩阵中每一元素各自的坐标代替IDCT公式中的变量，来获得一个与DCT矩阵相对应的恢复的矩阵中每一元素各自的部分值；以及

(b2)通过对在(b1)中获得的关于恢复的矩阵的元素的部分值进行求和，得到恢复的矩阵的元素的完整值。

15.如权利要求13所述的计算机可读记录介质，其中在(c)中使用高速IDCT算法对DCT矩阵执行2D IDCT，其中所述高速IDCT算法是Wang’s算法、Chen’s算法、Lee’s算法和AAN算法之一。

16.如权利要求13所述的计算机可读记录介质，进一步包括：

(a-1)通过在对预定的压缩文件进行游程长度译码期间计数具有除0以外值的元素的数量来获得具有除0以外值的元素的总数，所述游程长度译码在进行从离散余弦变换(DCT)矩阵的所有元素中查找具有除0以外值的元素之前执行。

17.如权利要求13所述的计算机可读记录介质，其中所述预定临界值被设定为具有除0以外值的元素的最大数量，在该数量上，用于元素方式IDCT的计算量少于用于矩阵方式IDCT的计算量。

18.如权利要求13所述的计算机可读记录介质，其中从所述DCT矩阵的第一列和第一行的元素开始，以锯齿形方式依次查找该DCT矩阵的元素。

Images