下载文档原格式
稀疏矩阵和图像处理中的奇异值分解算法综述在计算机图像处理领域中，奇异值分解算法可谓是一种非常重要的技术。
而在使用这种技术时，所涉及的稀疏矩阵也是一个非常关键的概念。
接下来，我们将对这两个概念做一个综述，希望能对大家有所帮助。
一、稀疏矩阵稀疏矩阵是指矩阵中大部分元素均为0或者接近于0，其中非零元素数量却相对较少的一类矩阵。
在计算机科学中，稀疏矩阵经常被用来存储大规模数据，例如在搜索引擎中，矩阵中每一列可以表示一篇文章，而每一行对应一个单词，矩阵的非零元素数量就是文章中该单词出现的次数。
因为矩阵中的大部分元素都是0，所以对于大规模的矩阵来说，使用稀疏矩阵可以大幅度节省存储空间，而对于一些需要直接操作矩阵的算法来说，稀疏矩阵的出现也能够大大降低算法运算的复杂度。
二、奇异值分解奇异值分解是一种常见的矩阵分解技术。
对于一个实数矩阵A，其奇异值分解表示为：A = UΣV^T其中，U和V分别是正交矩阵，Σ是一个对角线元素为非负实数的矩阵，对角线上的元素称为奇异值，且按照从大到小的顺序排列。
对于这个分解，有一个特别的性质，就是对于任意矩阵A，它的奇异值分解都是唯一的。
这一性质使得奇异值分解广泛地应用于信号处理、图像处理、机器学习等领域。
在图像处理中，奇异值分解一般用于压缩图像，或者在去除图像噪声的过程中进行降维处理。
通过将原始图像矩阵进行奇异值分解，然后只取其中一部分奇异值，就能够得到一个更加简单的近似矩阵，从而达到压缩图像的效果。
三、稀疏矩阵与奇异值分解在图像处理中，由于图像的数据往往是以稀疏矩阵的形式呈现出来的，因此稀疏矩阵与奇异值分解也有着密切的关系。
通过对稀疏矩阵进行奇异值分解，我们能够更加有效地对图像进行分析和处理。
在图像处理中，最常使用的稀疏矩阵是哈达玛矩阵或者DCT 矩阵，它们都是非常典型的稀疏矩阵，而且只需要进行简单的变换就能够得到。
而对于这些稀疏矩阵，我们可以使用奇异值分解来进行压缩处理或者降噪处理。
稀疏表示与低秩矩阵分解方法在图像重建中的应用近年来，随着科学技术的不断发展，图像处理技术已经得到了广泛的发展和应用。
在图像处理过程中，图像重建是其中十分重要的一个过程，它可以使图像更加清晰，具有更高的质量，并且使人们更加方便地进行图像处理和分析。
这篇文章将主要讨论稀疏表示和低秩矩阵分解方法在图像重建中的应用。
一、稀疏表示在图像重建中的应用稀疏表示是一种数字信号处理中的一个重要方法，它已经被广泛应用于图像处理领域。
稀疏表示的主要思想是将一个向量（或矩阵）表示成若干个基向量的线性组合，其中只有很少的基向量参与了该向量的表示。
稀疏表示的优点在于它可以使高维度的数据变得更加简单和易于处理。
在图像重建中，稀疏表示可以用于处理采样不足或失真严重的图像。
具体的处理方法是利用图像的稀疏性质，将一个稀疏的信号进行压缩表示，然后在原有采样信号的基础上，加上这个压缩信号，从而得到一个更加清晰的图像。
当然，在使用稀疏表示进行图像重建时，我们需要选取合适的基向量，以使得稀疏表示的过程能够更加准确和高效。
二、低秩矩阵分解在图像重建中的应用低秩矩阵分解，也称为矩阵分解低秩近似，是另一种在图像处理中广泛应用的方法。
其主要思想是将一个任意大小的矩阵表示为两个低秩矩阵之和，其中一个矩阵代表该矩阵的平均值，称为秩为1的矩阵，另一个矩阵代表该矩阵的扰动项，通常有较低的秩，也称为低秩矩阵。
相比于稀疏表示方法，低秩矩阵分解方法更加注重矩阵的结构和局部特征的处理，所以在处理图像时起到了较好的效果。
低秩矩阵分解常常用于图像去噪、图像填补和图像重构等方面的处理。
它能够有效地减小噪声和伪像的干扰，同时也能保留图像的细节和轮廓信息。
三、稀疏表示与低秩矩阵分解的结合应用稀疏表示与低秩矩阵分解的组合成了一种新的图像重建方法——稀疏表示与低秩矩阵分解联合重建方法。
该方法主要是将两种基于矩阵结构特点处理的方法结合到一起，以充分利用它们在图像重建中的优势。
具体而言，该方法首先利用稀疏表示方法处理图像的高边缘和高频部分，然后再利用低秩矩阵分解方法对图像的低频和低边缘部分进行处理。
数据结构之稀疏矩阵稀疏矩阵的存储方式和操作分析稀疏矩阵是指矩阵中大部分元素为零的特殊矩阵。
在实际应用中，稀疏矩阵经常出现，如图像处理、网络分析和科学计算等领域。
对于稀疏矩阵的存储和操作是数据结构中的重要内容。
本文将介绍稀疏矩阵的存储方式和相关操作的分析。
一、稀疏矩阵存储方式稀疏矩阵的存储方式有多种，其中三元组顺序表和二维数组是比较常用的方法。
1. 三元组顺序表三元组顺序表是一种基于行优先存储的方式，可以将稀疏矩阵以非零元素的形式存储起来。
主要包括行号、列号和元素值三个信息。
以一个4x5的稀疏矩阵为例，其中有三个非零元素分别为A[1][2]=3, A[2][3]=4, A[3][4]=5。
可以使用三元组顺序表来存储：```行号列号元素值1 2 32 3 43 4 5```三元组顺序表的优点是可以节省存储空间，同时也方便进行矩阵的操作。
但是在进行元素的查找和修改时，效率较低。
2. 二维数组二维数组是一种常见的矩阵表示方法，可以直接使用二维数组来表示稀疏矩阵。
其中非零元素的位置用实际的值表示，其余位置用零值表示。
以同样的4x5的稀疏矩阵为例，使用二维数组存储如下：```0 0 0 0 00 0 3 0 00 0 0 4 00 0 0 0 5```二维数组的优点是简单直观，并且可以快速进行元素的查找和修改。
但当稀疏矩阵的规模较大时，会造成较高的存储资源浪费。
二、稀疏矩阵的操作分析对于稀疏矩阵的操作，主要包括矩阵的转置、相加、相乘等。
1. 转置操作稀疏矩阵的转置是指将原始矩阵的行与列对调。
对于三元组顺序表来说，转置操作主要涉及到行号和列号的交换。
而对于二维数组来说，可以直接在取值的时候将行号和列号对调即可。
2. 相加操作稀疏矩阵的相加操作是指将两个矩阵对应位置的元素相加。
对于三元组顺序表来说，可以通过遍历两个矩阵的非零元素，并将其对应位置的元素相加。
而对于二维数组来说，可以直接将对应位置的元素相加即可。
3. 相乘操作稀疏矩阵的相乘操作是指将两个矩阵相乘得到一个新的矩阵。
稀疏矩阵的特征稀疏矩阵：揭示信息世界中的隐藏规律在信息时代的浪潮下，海量数据的快速传输和处理成为了当下亟待解决的难题。
而稀疏矩阵作为一种重要的数据表示方式，为我们破解信息世界中的隐藏规律提供了有力的工具。
本文将从稀疏矩阵的定义、应用和优势三个方面来探讨其在信息领域的价值。
一、稀疏矩阵的定义稀疏矩阵是指在一个二维矩阵中，大部分元素为0，只有少数非0元素的矩阵。
相对于稠密矩阵，稀疏矩阵具有更高的存储效率和计算效率。
常见的表示稀疏矩阵的方法有三元组表示法、行压缩存储和列压缩存储等。
二、稀疏矩阵的应用1. 图像处理在图像处理中，稀疏矩阵可以用来表示图像的一个重要特征——纹理。
通过提取图像的纹理信息，可以实现图像的分割、识别和重构等操作。
例如，在医学图像的分析中，可以利用稀疏矩阵来提取肿瘤的纹理特征，从而实现对肿瘤的自动检测和诊断。
2. 自然语言处理在自然语言处理中，稀疏矩阵可以用来表示文本的词袋模型。
将文本中的每个词作为矩阵的列，将每个文本样本表示为一个向量，其中非零元素表示该词在文本中的出现次数或权重。
通过对文本矩阵进行聚类、分类和关键词提取等操作，可以实现文本的自动分类和信息检索。
3. 推荐系统在推荐系统中，稀疏矩阵可以用来表示用户和物品之间的关系。
将用户和物品分别表示为矩阵的行和列，将用户对物品的评分作为矩阵中的非零元素。
通过对稀疏矩阵进行矩阵分解和推荐算法，可以实现个性化推荐和精准营销。
三、稀疏矩阵的优势1. 存储效率高由于稀疏矩阵中大部分元素为0，只有少数非零元素，所以可以采用压缩存储的方式，节省存储空间。
相比于稠密矩阵，稀疏矩阵可以节省大量的存储资源。
2. 计算效率高由于稀疏矩阵中大部分元素为0，所以在进行矩阵运算时可以忽略这些0元素，减少了计算量。
对于大规模矩阵的计算，稀疏矩阵的计算效率远高于稠密矩阵。
3. 适用于高维数据在高维数据分析中，数据的维度往往非常高，导致数据稀疏性增加。
而稀疏矩阵可以很好地处理高维稀疏数据，减少了计算和存储的复杂度。
MATLAB中的稀疏矩阵处理技巧一、引言稀疏矩阵在实际的科学和工程问题中经常出现。
相较于密集矩阵，稀疏矩阵具有更高的存储效率和计算效率。
MATLAB作为一种强大的科学计算软件，提供了丰富的稀疏矩阵处理函数和技巧。
本文将介绍一些MATLAB中处理稀疏矩阵的技巧，以及它们在实际问题中的应用。
二、稀疏矩阵的表示稀疏矩阵是指矩阵中绝大多数元素为0，仅有少量非零元素的特殊矩阵。
在MATLAB中，稀疏矩阵的表示可以使用两种方式：完全稀疏表示和压缩稀疏表示。
完全稀疏表示是指将矩阵的每个元素都存储起来，包括0元素。
这种表示方式的好处是可以直接使用矩阵的标准运算，但是会占用大量的存储空间，效率较低。
压缩稀疏表示是指只存储矩阵中非零元素及其对应的行列索引。
这种表示方式可以节省存储空间，提高计算效率。
在MATLAB中，可以使用稀疏矩阵函数sparse()将完全稀疏矩阵转换为压缩稀疏表示。
三、稀疏矩阵的创建和操作1. 创建稀疏矩阵在MATLAB中，可以使用sparse()函数创建一个稀疏矩阵，该函数的参数包括矩阵的行数、列数和非零元素的位置及值。
例如，下面的代码创建了一个3x3的稀疏矩阵：```matlabA = sparse([1 1 2 2 3],[1 2 2 3 1],[1 2 3 4 5],3,3);```2. 稀疏矩阵的基本操作稀疏矩阵在MATLAB中的基本运算和操作与普通矩阵相似，包括加减乘除、转置、逆矩阵等。
例如，可以使用"+"运算符对稀疏矩阵进行加法运算，使用"*"运算符进行矩阵乘法运算。
另外，稀疏矩阵还可以进行像素级的操作，例如在图像处理中，可以将稀疏矩阵的非零元素设置为像素的灰度值，实现图像的旋转、缩放等操作。
四、稀疏矩阵的存储和压缩在MATLAB中，稀疏矩阵的存储和压缩是一项重要的技巧。
当矩阵的维数较大时，完全稀疏表示会极大地占用存储空间，不仅浪费了内存，也会影响计算速度。
稀疏矩阵算法
稀疏矩阵是指矩阵中大部分元素都为零的矩阵。
在实际应用中，很多矩阵都是稀疏矩阵，例如图像处理中的像素矩阵、文本处理中的词频矩阵等。
由于稀疏矩阵中大部分元素都为零，因此常规的矩阵算法会浪费大量时间和空间。
为了高效地处理稀疏矩阵，我们需要使用稀疏矩阵算法。
稀疏矩阵算法可以分为压缩存储和稀疏矩阵运算两部分。
压缩存储是指将稀疏矩阵中的非零元素存储起来，而忽略掉零元素。
常见的压缩存储方式有三种：行压缩存储法（CRS）、列压缩存储法（CCS）和对角线存储法。
其中，CRS和CCS是最常用的两种压缩存储方式。
在CRS中，非零元素按照行的顺序进行存储，同时需要记录每一行的起始位置和非零元素个数。
在CCS中，非零元素按照列的顺序进行存储，同时需要记录每一列的起始位置和非零元素个数。
对角线存储法则是将稀疏矩阵的对角线元素存储下来，其余的非零元素按照行的顺序存储。
稀疏矩阵运算是指对稀疏矩阵进行各种运算，包括加、减、乘、转置、求逆等。
其中，稀疏矩阵乘法是应用最广泛的运算。
稀疏矩阵乘法的基本思想是通过压缩存储方式将矩阵中的非零元素存储下来，然后利用矩阵乘法的基本性质进行计算，最后将结果存储在稀疏矩阵中。
总之，稀疏矩阵算法可以大大提高对稀疏矩阵进行计算的效率。
在实际应用中，我们需要根据具体情况选择合适的压缩存储方式和运
算方法，以达到最佳性能。
Matlab中的稀疏矩阵处理技术介绍在数据处理和算法设计中，矩阵是一种非常常见的数据结构。
然而，在实际应用中，很多矩阵是稀疏的，即大部分元素都是0。
对于稀疏矩阵的处理，传统的方法十分低效，会浪费大量的存储空间和计算资源。
为了提高效率，Matlab中提供了一系列的稀疏矩阵处理技术，可以更高效地处理这类特殊的数据结构。
一、稀疏矩阵的定义和表示在介绍具体的处理技术之前，首先需要了解稀疏矩阵的定义和表示方法。
稀疏矩阵是指矩阵中大部分元素都是0的情况。
为了高效地表示这类矩阵，不必存储所有的元素，只需要存储非零元素以及它们的位置信息即可。
在Matlab中，稀疏矩阵可以通过提供非零元素的行列坐标和值来表示。
具体来说，可以使用sparse函数来创建稀疏矩阵，其语法如下：s = sparse(i, j, v, m, n)其中i和j是非零元素的行列坐标，v是非零元素的值，m和n是矩阵的维度。
通过这种方式，可以高效地存储稀疏矩阵，并且能够提供一些便捷的功能和操作。
二、稀疏矩阵的存储结构在计算机内存中，矩阵通常以行优先或者列优先的方式存储。
然而，对于稀疏矩阵来说，这种方式会浪费大量的存储空间，因为大部分的元素都是0。
为了更加高效地存储稀疏矩阵，Matlab中使用了压缩列（CSC）和压缩行（CSR）两种存储结构。
压缩列存储方式将矩阵按列进行存储。
具体来说，将矩阵分成m个列，每个列存储非零元素的行索引和值。
另外，需要一个向量来记录每个列的起始位置和结束位置。
这种存储方式在列操作中效率高，但在行操作中效率较低。
压缩行存储方式将矩阵按行进行存储。
具体来说，将矩阵分成n个行，每个行存储非零元素的列索引和值。
另外，需要一个向量来记录每个行的起始位置和结束位置。
这种存储方式在行操作中效率高，但在列操作中效率较低。
在Matlab中，可以使用full函数将稀疏矩阵转换为普通的密集矩阵，以便于进行一些特殊操作。
但需要注意的是，将稀疏矩阵转换为普通矩阵会消耗大量的存储空间，因此要谨慎使用。
第8卷第4期 上海大学学报(自然科学版) Vol.8,No.4 2002年8月 JOURNAL OF S HANGHAI UNIVERS ITY(NAT URAL SC IE NCE) Aug.2002文章编号:1007-2861(2002)04-0297-05・研究简报・稀疏矩阵文档图像处理储开颜, 桑宏伟, 马 田, 王朔中(上海大学通信与信息学院,上海200072)摘要:讨论基于稀疏矩阵的文档图像存储及处理方法.采用三向量法或链表法表示稀疏图像,然后在稀疏域直接实现某些基于临域运算的图像处理算法.分析表明,对于具有显著特征的文档图像能有效地节省存储空间并提高计算效率.以卷积运算和一种文档图像处理运算为例,给出实验结果.关键词:图像处理;稀疏矩阵;三向量法;链表法中图分类号:T P391.41 文献标识码:ADocument Image Processing Based on Sparse Matrix RepresentationCHU Kai-y an, SANG Hong-w ei, M A T ian, WANG Shuo-zhong (Scho ol of Co mmunicat ion and Infor matio n Eng ineering,Shang hai U niv ersit y,Shang hai200072,China)Abstract:Storage and pr ocessing o f docum ent im ag es based on spar se m atr ices ar e discussed.The spar se imag e is first co nv erted into a mo re com pact for m consisting of either three v ectors ora linked list.Imag e processing operations featuring neighborhood co mputatio ns are perform ed di-rectly in the sparse-m atrix do main.For images that are sufficiently sparse,the described metho d can effectively save sto rage as w ell as pro cessing time.Finally,sparse-m atr ix domain implemen-tations of2D conv olutio n and a noise removal algor ithm are pr esented.Key words:im age processing;sparse m atr ix;three vecto rs representation;linked list 由于一般图像数据量都比较大,因此在进行空域处理时所涉及的乘法和加法运算次数很多,相应的内存消耗也很大.为了提高效率,可采用并行处理方法,将整个图像处理作业进行适当的分割,分配到许多节点同时处理,然后再将处理结果合成.这一方案可用图像处理的硬件实现[1].如用软件实现则需要并行处理平台的支持,其成本较高,适合于解决大规模图像处理的问题.本系统稀疏化方法所能处理的是一类特定的图像,即文件、表格、图形等资料经过扫描所得到的图像(统称文档图像).当原始资料幅面为A4,扫描分辨率为200dpi时,得到的一幅图像就有将近4×106个像素.在办公自动化或其它现代化文档管理系统中对大量文档图像进行处理时,一般不适宜采用规模巨大的并行计算手段.考虑到文档图像中往往有大片背景区域并不包含任何有用的信息,如采用常规的空域运算将十分浪费.一种有效的方法是将稀疏矩阵理论应用于图收稿日期:2000-12-13 修订日期:2002-04-17 作者简介:储开颜(1972～),男,江苏海安人,博士生,主要从事图像恢复和图像压缩方面的研究.像处理[2].本文在讨论适用于文档图像的稀疏矩阵描述方法的基础上,将此方法应用于该类图像的记录和处理,从而达到节省存贮空间、提高效率的目的.为了叙述方便,我们称这一操作为稀疏化.文中采用了两种稀疏化方法,在此基础上以图像处理中最基本的卷积运算为例,着重研究在稀疏域中直接进行图像处理的技术,并给出计算速度的测试结果.本文还实现了一种基于稀疏矩阵表示方法的文档图像去噪算法.1 稀疏矩阵的两种表示方式设文档图像的稀疏度为p,它代表图像中文字、符号、线条等有意义区域的面积与图像总面积之比.对于采集到的一批文档图像实测结果表明,稀疏度一般在0.05～0.15.设图像尺寸为M×N.对于稀疏矩阵的存储,可以使用逻辑尺、一维数组[3]等方法,考虑到在节约存储空间的同时节约图像处理的运算量,文中使用了以下两种稀疏矩阵表示法.1.1 三向量表示法[4]三向量表示法用Row、Co l、Data三个向量表示稀疏矩阵,其中:(1)Row有M个元素,Row(j)表示第j行中有意义数据的数目,且∑Mj=1Ro w(j)=p M N;(1) (2)Co l有p MN个元素,Col(k)表示第k个有意义数据所处位置的列号;(3)Data也有p M N个元素,Data(k)表示第k 个有意义数据的取值(灰度值).Col和Data中的数据按行依次排列,如图1.图1 稀疏矩阵的三向量结构F ig.1 T hr ee v ector r epr esxentat ion o f spar se m atrix 假设一幅图像的尺寸一般不会超过65536×65536,每一像素灰度值范围为0～255,于是表示Ro w和Col每一元素需用2字节表示,Data中每一元素用1字节,一幅稀疏图像所需总存储量为K=2M+3p MN,(2)因此只要K<MN,即p<M(N-2)3M N≈13(3)就能节省存储空间.如图像稀疏度p=0.1,则所占空间略大于像素直接按矩阵排列的30%.若规定图像最大尺寸为256×256,超过此尺寸可将图像分块处理(但处理时需额外开销),则K=M+2p M N,只需p<0.5就能节省空间.此时稀疏度为0.1的图像只需大约占用原来存储空间的20%.1.2 链表表示法另一种稀疏矩阵的表示方法是用链表[5].定义数据结构:struct{Row,Col,Data,Po int},其中Row为行号,Col为列号,Data为灰度值,Point为指向下一个数据结构的指针,见图2.图2 稀疏矩阵的链表结构F ig.2 Linked list repr esention of sparse mat rix在链表法表示中,以2字节存储Row和Col,1・298・ 上海大学学报(自然科学版) 第8卷字节存储Data.由于在写入文件时结构是按顺序存放,所以在文件中Pointer并不占据空间.链表法的总存储量为5p M N,稀疏度p约小于0.2时可节省存储空间.将图像分割为不大于256×256的块时,存储量减小为3p M N.2 两种方法性能的分析与比较分别用三向量法和链表法对黑白图像进行稀疏化,所需计算次数列于表1.表中同时给出对三幅文档图像(文字、表格、电路图)的测试结果,测试中所用图像尺寸为1024×1024,用C++编程,计算机的CPU为PⅢ500M Hz.由表1可见,三向量法比链表法多p M N次加法,但减少了p MN次赋值操作.由于加法速度远比赋值速度慢,所以三向量法所需计算时间较长.为了在屏幕上显示图像,需要将图像的稀疏表示还原成点阵排列.通过分析两种存储结构可看出,由于三向量法中列号和灰度值分别存放在Col和Data中,均可以直接得到,而行号则需要通过N次赋值运算才能得到,所以要进行p M N+N次赋值和p MN次图像内寻址运算.链表法的行号、列号和灰度值都可以直接得到,在图像还原时要比三向量法要少N次赋值.表2给出两种方法在还原时所需的计算量和实测结果.由表2看出,链表结构所需空间大于三向量结构,但三向量法的稀疏化时间和还原时间都比链表法长.表1 图像稀疏化所需计算量Tab.1 Performance comparison of sparse matrix conversion三向量法链表法备注内存寻址和比较次数M N M N加法次数p M N0赋值次数2p M N3p M N稀疏化时间实测结果图像1:p=0.15 2.883s0.594s文字图像2:p=0.07 2.965s0.408s表格图像3:p=0.05 2.765s0.245s电路图表2 稀疏化图像还原所需计算量Tab.2 Perf ormance comparison of inverse conversion三向量法链表法备注内存寻址次数p M N p M N赋值次数N+p M N p M N图像还原时间实测结果图像1:p=0.150.066s0.047s文字图像2:p=0.070.044s0.041s表格图像3:p=0.050.042s0.037s电路图3 稀疏域中图像的直接处理图像的上述两种稀疏矩阵表示法均给出有效像素的空间位置,所以能在稀疏域中直接进行的图像运算主要是涉及移动窗口(掩模)中邻域运算的各种处理算法,例如根据直方图进行图像灰度变换,利用阈值进行二值分割等,所需的计算次数为直接空域计算的p倍,所以对稀疏度高的文档图像可节省大量的计算时间.当进行基于窗口的邻域运算时,只要窗口中包含有效像素就需进行计算,所以图像处理所涉及的像素会超出p MN个有效像素所在的区域,具体计算量与有效像素的分布和掩模的大小有关.在实际计算中,比较判断、乘法和加法的计算速度远比寻址和赋值慢,从表2可以看出三向量法和链表法内存寻址次数相同,只是赋值次数有所增加,所以在稀疏域中,图像处理的计算量主要和图像的类型以及计算的种类有关,而稀疏图像的存储类型对计算量的影响比较小.以下我们以三向量法为例,用卷积和去噪声两种算法加以说明.3.1 稀疏域卷积将稀疏图像的卷积运算分为两步.第一步是列出一个表,标出所有需要参与计算的像素,然后根据表所标示的位置对相应像素依次进行计算.现在以・299・第4期 储开颜,等:稀疏矩阵文档图像处理3×3掩模为例讨论计算方法.设图像中有两个孤立的相邻非零像素,其周围都是0,如以下阵列所示:00000121600其中除了非零数据点以外,当掩模中心位于它们周围一圈时,卷积运算结果也为非零,因此也需要进行计算.由于所有需参与运算的点都集中在非零值数据周围,因此可动态地建立一个表用于存放特定的标记,将稀疏域中所有数据点及对应于原始图像中周围一圈的点全部标注为1,其余的点则标为0.同时再建立一个动态表用于存放灰度值,把原始图像所有的灰度值都顺序输入.作卷积时先读第一个表取出标记.如读到1,则取出相应9个点的灰度值进行计算,如读到零则跳过.表的结构如图3所示.图3 卷积运算中动态生成的列表Fig.3 Dy namic list gener ated in co nvolutio n 假设两个非零像素分别位于(5,5)和(5,6),存放标记的列表中前4个“1”在整个列表中位于(3M +4)～(3M +7),中间4个“1”位于(4M +4)～(4M +7),最后4个“1”位于(5M +4)～(5M +7).卷积计算时读到(4,4)为1,则取出灰度值列表中对应的9个数值顺序进行运算.由于赋值运算比判断快得多,因此在根据稀疏域数据进行标示列表赋值时不必考虑重复赋值的问题,稀疏域中每个数据对应9次赋值,总共为9p M N 次.两个列表都是在运算时动态生成的,因此不占据存储空间.表3列出用不同大小掩模进行稀疏域卷积时参与计算的像素数目占图像全部像素的百分比,以及在3×3掩模情况下分别进行稀疏域卷积和直接卷积所需时间的比较.所用测试图像和实验条件同上.由表可见,掩模越大所需计算量也越大.一般至少能节省70%左右的计算量,即使在罕见的11×11掩模情况下仍然有50%以上的像素不需要计算.稀疏域卷积算法本质上与直接卷积算法无异,只是避免了大量的无用计算.表3 稀疏域卷积的计算量以及与直接卷积所需时间之比Tab .3 Comparison between computations in the sparse domain and in the originalspace domain参与稀疏卷积计算的像素所占百分比/%3×3掩模时所需计算时间/s 3×35×511×11稀疏卷积直接卷积图像1:p =0.1528.3836.3048.27 1.003 3.905图像2:p =0.0720.8527.5338.77 1.041 3.896图像3:p =0.0520.0227.6041.670.6823.9003.2 一种去噪声算法的稀疏域实现以下以一种去噪算法为例,说明在稀疏域中如何实现对连通区像素性质进行分类的运算.对于一个非零像素,判断它为噪声的依据是与该点相连的非零像素少于某一阈值(噪声容限),所以它的计算不会超出p MN 个非零像素所在的区域.在搜索图像的噪声点中采用8邻域的连通区定义.如果连通区中的非零像素数少于噪声容限,则认为该点是噪声点并去除该连通区.搜索步骤如下:(1) 顺序从稀疏矩阵中读取有效像素,如果该像素已是图像的结尾则结束程序;如果该点已经处理过则继续下一点的运算,直至取到未经判断的像素,进行计算.(2) 判断本行中所有与该点相连通的像素数,如果比噪声容限大,则表明该像素不是噪声点,记录下该点以及所找到的像素灰度值,返回第(1)步.(3) 寻找该像素上一行中是否有与该点相连通的像素,如果有则表明该点不是噪声点,将上一步中找到的点记为有效像素.(4) 在该像素的下面寻找其所在连通区内所有像素的总数,如果小于噪声容限则去除该连通域;如果大于噪声容限则将该连通区记录下来.重复第(1)步.在第(3)步中,如果该像素上一行有连通的点就不需要继续寻找,这是因为上一行连通区中的像素不可能是噪声,而跟非噪声像素相连通的点一定不是噪声.如果该连通区是噪声,那么在判断上一像素是否噪声时,该像素应已被记录成噪声点,所以实际上该点已被去除而不会执行到第(3)步.图4给出一个处理实例,其中灰度值为255的点为背景点,灰度为0的点为图像点或噪声点.图4(a )包括图像区域和孤立噪声.如设置噪声容限为・300・ 上海大学学报(自然科学版) 第8卷3,则只有1和5为图像区域,2、3、4、6、7均为噪声点.处理后的结果如图4(b )所示,其中图像区域1和5被保留,而所有噪声区域的灰度值均被设为背景色255.噪声已被清除.对于在稀疏域中的去噪处理,由于只对p MN 个有效像素进行了计算,因此计算量仅为直接计算的p 倍.4 结 论 文档图像通常有大量的背景像素,在进行图像处理时不必参与运算.在稀疏域中直接进行点运算和基于邻域运算的图像处理仅涉及到较少的数据,不仅节省存储空间,而且可提高运算速度.本文在讨论稀疏图像的两种表示方法基础上,以在稀疏域实现卷积和孤立噪声清除的算法为例,给出了数值计算结果.这类稀疏矩阵处理技术也可推广到其它图像处理运算中去.本文所给出的实验结果都是按照Row 和Col 中每一元素用2字节表示得到的.如果将图像划分为小于256×256的子图像分别进行处理,则像素位置信息所占的存储空间将减少一半,若需要将子图像拼接起来则需要一定的工作量.图4 消除孤立噪声Fig.4 Rem ova l o f isolated no ise参考文献:[1] M ucher oni M L ,M o ro n C E ,Sait o J H .A r chM D SP :U sing D SPs for par allel imag e pro cessing [C ].InP ro c 23r d EU R OM ICRO Co nf :′97New Fr ontiers of I nfo T ech,1997.[2] M allat S .Image pr o cessing w ith sparse representa-tio ns [C ].1999SIA M A nnual M eeting ,A tlanta ,G eor gia,U SA ,1999.[3] 白峰杉.数值分析[M ].武汉:华中科技大学出版社,1999.[4] 朱季讷.稀疏矩阵[M ].北京:北京科学出版社,1981.2-10.[5] Fo rd W ,T o pp W.Dat a structures w it h C++[M ].Englewo od Cliffs :Pr entice -Hall I nc ,1996.383-480.・301・第4期 储开颜,等:稀疏矩阵文档图像处理。
