（计算机软件与理论专业论文）djvu技术及其应用.pdf

abs t r a c t w i t h l i b r a r i e s t h e f a s t e me r g e n c e o f t h e i n t e r n e t , t h e d i g i t a l i z a t i o n o f t r a d i t i o n a l i s u n d e r wa y d j v u i s a d i g i t a l l i b r a r i e s _ s p e c i f i e d i m a g e p r o c e s s i n g t e c h n o l o g y a r c h i t e c t u r e p r o p o s e d b y a t u n s i g n e d i n t w i d t h ( ) ; u n s i g n e d i n t h e i g h t ( ) ; u n s i g n e d i n t g e t l e f t ( ) ; u n s i g n e d i n t g e t t o p ( ) ; u n s i g n e d i n t g e t r i g h t ( ) ; u n s i g n e d i n t g e t b o t t o m( ) ; p r o t e c t e d : u n s i g n e d i n t l e f t ; u n s i g n e d i n t r i g h t ; u n s i g n e d i n t t o p ; u n s i g n e d i n t b o t t o m; t i m a g e 的定义如下: 刀 只支持灰度图像和黑白图像两种格式。 刀 灰度图像，一个像素占一个字节。 / 黑白图像，一个像素占一个比特。 刀 代表整个图像。 c l a s s t i ma g e p u b l i c : t l m a g e ( u n s i g n e d i n t n r o w s，u n s i g n e d i n t n c o l u m n s b s e g = f a l s e ) ; u n s i g n e d i n t r o w s ( ) ; u n s i g n e d i n t c o l u m n s ( ) ; / 设置是否为黑白图像格式。 v o i d s e t mo n o ( b o o l b mo n o ) ; / 设置是否为灰度图像格式。 v o i d s e t g r a y ( b o o l b g r a y ) , 刀 设置分段情况下的行指针数组的首地址。 v o i d s e t l i n e p o i n t e r s ( u n s i g n e d c h a r * * p p l i n e s ) ; 2 6 b oo l 刀 设置不分段情况下像素数据 的首地址 。 v o i d s e t b y t e s ( u n s i g n e d c h a r * b y t e s ) ; 刀 设置不分段情况下每行所 占的字节数。 v o i d s e t r o w b y t e s ( u n s i g n e d i n t n r o w b y t e s ) ; 刀 返回第 r o w行的行指针。 u n s i g n e d c h a r * o p e r a t o r ( i n t r o w ) ; p r o t e c t e d : u n s i g n e d i n t n r o ws ; u n s i g n e d i n t n c o l u m n s ; / 是否为黑白图像格式。 b o o l b mo n o ; 刀 是否为灰度图像格式。 b o o l b g r a y ; 刀 是否分段。 b o o l b s e g ; 刀 用于分段情况下行指针数组的首地址。 u n s i g n e d c h a r * * p p l i n e s ; 刀 用于不分段情况下每行所占的字节数。其中可能包括填充的字节。 / 这样对各种图像数据格式有很好的适应性。如b m p格式文件的双 / 字对齐，o f格式文件的字节对齐等等。同时既可用于灰度图像， / 又可用于黑白图像。 u n s i g n e d i n t n r o wb y t e s ; 刀 用于不分段情况下像素数据的首地址。 u n s i g n e d c h a r * b y t e s ; ， t mo n o s c a l e r 的定义如下: 刀 实现了高分辨率黑白图像到低分辨率灰度图的直接快速缩放。 / 只处理高分辨率黑白图像直接缩放到低分辨率灰度图像的情况。 / 支持分段，可指定缩放的区域。对局部区域的缩放不会出现 刀 衔接方面的问题。 c l a s s tmo n o s c a l e r p u b l i c 2 7 / / s r c w为原图像的宽度，d s t w为目标图像的宽度。 / / d s t w必须不大于 s r c w。因为我们只处理缩放率 / 不小 于 1 0 0 %的情 况 。 t mo n o s c a l e r ( u n s i g n e d i n t s r c w, u n s i g n e d i n t d s t w) ; / / i n p u t 对应原图像，( 整个，但只有需要区域的数据才 刀 需要在内存中。) i n p u t 必须是黑白图像。 / / o u t p u t 对应目 标图像，( 整个，但只有需要计算的区域 / 才被分配内存。) o u t p u t 必须是灰度图像。 / / r c d s t 对应目标图像中需要计算的区域。 v o i d s c a l e ( t i m a g e 中，结果无论是速度还是效果都可与“ 映 象” 相比，从而解决了这个问题。 第五章 有关 d j v u应用于中文数字化图书馆的一点尝试 伴随着因特网的迅速崛起 ，人类社会开始进入信息社会。与此相适应， 以印刷媒体为主的图书馆正在向数字化图书馆迈进。数字化图书馆是 2 1世 纪图书馆发展的必然趋势。数字化图书馆的研制始于 8 0年代末的西方发达 国家，随后向全球扩展。 “ 有关统计资料表明， 目前在因特 网的信息中，9 0 %以上是英文，中文 信息少得可怜，而这有限的中文信息还大多是港台制作的。”( 文【 1 0 )为改 变因特网上中文信息极度匾乏的状况，数字化图书馆的建设与研究己成为国 内图书馆研究的重要课题。 前面己经提到，d j v u是一项旨在推动数字化图书馆发展的技术而且在 世界各地己经有很多成功的应用。那么它在我国数字化图书馆的建设中是否 会 占有一席之地? 汉字是图形文字，不象英文字母，大小写加在一起才 5 2个。可以想象 的到，尽管同一页文档的字体和字号通常是一样的，但中文文档中的汉字重 复出现的频率比起英文文档中的英文字母重复出现的频率要小的多。由于 j b 2 利用的就是相同s h a p e重复出现造成的冗余，这样一来优势可能就体现 不出来，需要作一些试验。也有可能需要作一些改进，比如用分形算法取代 j b2。 中文古籍的数字化是中文数字化图书馆的一个重要组成部分，对通过网 络向全球宏扬我国悠久的历史和灿烂的文化有着重要的意义。 中文古籍的特点是: 一、背景通常不是白色，也可能有纹理。但多数情况下背景具有连续色 调或者颜色均一，适合小波压缩。 二、字号较大。( 也就是说连通体较大，注意这里的连通体是指笔画， 当然也包括连笔，同时连通体内部的黑像素较为密集。)d j v u的思想是 用掩码层把不具有连续色调的图像分割成各 自具有连续色调的背景层和 前景层，然后分别用小波压缩，其中使用了投影算法来避免重复编码。 而连通体较大这一特点对于投影算法是有利的，因为会有更多的小波系 数的支撑区域仅包含前景像素。 三、字体较多，而且笔法变化较大。更重要的是，一个汉字往往对应多 个连通体。所有这一切都使得 j b 2赖以得到高压缩比的字符形状间的冗 余究竟在中文古籍数字化方面还能发挥多大作用成为一个疑 问。 我用d j v u s o l o 3 . 0 ( n o n c o m e r i c a l e d t i o n ) 对图5 . 1 所示的中文古籍样张 ( b m p文件格式，3 8 5 k b e) 进行了压缩。压缩后得到的 d j v u文件的大小是 7 . 6 4 k b ，效果如图 5 . 2 所示。而该位图对应的 g i f格式的文件和 j p e g格式 2 9 的文件的大小分别是 2 4 . 2 k b和 6 6 . 4 k b 。这说明 d j v u技术在中文古籍的数 字化方面还 是有一定应用前景的。 另外，将中文 o c r技术和 d j v u的 h i d d e n t e x t l a y e r 结合起来可以实 现中文文档图像的检索。另外，d j v u的分层传输、渐进显示、h y p e r l i n k . 快速的无级缩放和平滑拖动等特性都有可能在中文数字化图书馆 中发挥作 用 。 第六章 有关投影算法和图像分层等方面的一点尝试 关于投影算法的效果，我找到 了一个极端的例子。 选择图6 . 1 所示的c o l o r . b m p ， 用d j v u s o l o 3 . 0 ( n o n c o m m e r c i a l e d i t i o n ) 进行压缩后得到的d j v u 文件的大小是4 5 . 9 k b 。 而采用边缘提取得到了图6 . 2 所示的 e d g e . b m p ，将其用d j v u s o l o 3 . 0 ( n o n c o m m e r c i a l e d i t i o n ) 压缩后得 到的d j v u 文件的大小是2 . 1 7 k b 。两者所使用的分辨率都是 9 6 d p i s e d g e . b m p中的轮廓将 c o i o r . b m p分成了若干个平面区域。事实上，此时 c o l o r . b m p可以被看作是一个色数为 2的平面图。所有内平面是一种颜色， 而外平面本身是一种颜色。这样就可以考虑根据平面区域的颜色分层，在这 个例子中恰好只有两层。我们把所有内平面作为前景层，把外平面作为背景 层，采用包含投影算法的 i w4 4压缩。 图 6 . 3 和图6 . 4 分别是使用 d j v u o p e n s o u r c e c o d e 对前述的前景层和背 景层分别进行压缩后得到的 f g . i w 4 ( 文件的大小是 3 . 1 2 k b o) 和 b g . i w 4 ( 文件 的大小是 1 . 8 2 k b o) 。 f g . i w 4 , b g . i w 4和 e d g e . d j v u三个文件的大小加在一起是 7 . 1 1 k b ，远远 小于 c o l o r . d j v u文件的大小。( 4 5 . 9 k b ) 从这个例子来看，在类似的场合中将边缘提取和包含投影算法的小波压 缩结合起来的考虑很可能会有用武之地。关键在于，我们把边缘作为高频成 分提取出来之后，原图像被这些边缘分割成若干个连通体。这样的话原图像 就可以被看作是一个平面图，而对平面图染色最多需要 4种颜色，一种颜色 对应一层。我的考虑是这样的:不同颜色的两个区域，如果相邻，它们在平 面图中对应的区域必定不同色，也就是说它们不在同一层中。如果不相邻但 又在同一层中的话，那么它们之间通常应该有较大的距离足以使投影算法完 成平滑化处理，从而得到较高的压缩比。而边缘可以以链码的方式存储。在 这里，我直接使用d j v u s o l o 3 . 0 ( n o n c o m m e r c i a l e d i t i o n ) . 在下面的一个例子中，我给出了一个中文文档图像的例子。原图像的位 图文件的大小是 1 . 1 5 m b ，直接用 d j v u s o l o 3 . 0 ( n o n c o m m e r c i a l e d i t i o n ) 压缩后得到的 d j v u文件的大小是 1 7 . 7 k b 。而用我的方法一共得到三个文 件，三个文件的大小加在一起也只有 8 . 7 k b a 我的方法的流程如下: 1 、用二值化的方法将原图像分成前景层和背景层并同时得到掩码层。( 事实 上，这一步是可选的。因为我实际上是用边缘检测来进行图像分割的，加上 这一步只是为了方便边缘检测。所以二值化的过程对像素进入前景层的要求 应定的宽一些。) 2 、对掩码层进行边缘检测得到若 干个 区域 3 1 。( 其中某些区域可能不封闭。 这既可能是边缘检测的问题，也可能是采样的问题。) 在这个例子中我使用 k i r s c h 算子得到很好的结果。 3 、再根据需要对边缘检测后得到的掩码层( 只含边缘。) 进行数学形态学方 面的处理( 膨胀和收缩) 以图恢复未检测出的边缘点。 4 、用 f 1 o o d f i l l 的方法对每一个区域进行填充并试图恢复最初的掩码层。如 果这其间有某个区域的恢复失败，则可对其进行例外处理( 如用对连通体找 边缘而不是用边缘检测的方法。) 或者干脆存区域本身。只要这样的区域能 够控制在极少数，整个方法仍将会有较高的效率 。 5 、对前景层和背景层进行平滑化处理。 以下我以背景层为例进行说明。在这里我没有使用投影算法，而是使用 一般的平滑化处理。我的考虑是这样的，投影算法的目的也无非就是使图像 在保持未被屏蔽像素的前提下尽可能平滑，从而使得小波压缩能够有较高的 效率。 而在这个目 的上， 平滑化处理利用小波压缩的” 平滑假设 ( s m o o t h n e s s a s s u m p t i o n )，更具有一般性，而且没有投影算法可能会遇到的由于置零像 素选择不当而导致算法不收敛的问题。 我在这里使用的平滑算法与通常的稍有不同，因为需要保持未被屏蔽的 像素的值。我使用的方法还是很简单的，就是用迭代的方法将未被屏蔽的像 素的值逐次扩散到被屏蔽的区域中。 具体做法就是先初始化一个包含所有未被屏蔽的像素的集合 p 。然后不 断的迭代。每次都循环地对每一个像素进行判断，如果该像素的 4 一 邻域中 有属于集合 p的像素，就将它们的算术平均值赋给该像素，并把该像素加 到集合 p中。 如果某次迭代没有新的像素被加到集合 p中，迭代结束。 我发现用这种方法得出来的结果仍然保留了原前景层的轮廓。( 虽然己 经很模糊。) 这绝不是我希望的结果，因为这样意味着图像仍不够平滑。尽 管就这个例子而言，用这种算法处理后的图像再用 d j v u s o l o 3 . 0 ( n o n c o m m e r c i a l e d i t i o n ) 压缩后得到的 d j v u文件的大小为 1 4 . 4 k b ，已经大大 好于用不分层的选项直接存原图像时的结果。 ( d j v u 文件的大小为4 6 . 9 k b . ) 但还是有 必要尝试一下解决这个问题 。 为了解决不够平滑的问题，我考虑了这样一种思路，当计算前景层的像 素值 的时候 ，只用背景层的像素值 。 具体可以这么做，对每一个需要计算的前景层的像素，先在与它的 。 i t y b l o c k距离为 1的像素中找，如果其中包含背景层像素，就结束查找。否则 继续在与它的 c i t y b l o c k 距离为2的像素中找，依次类推，直到找到背景层 像素为止。然后用找到的背景层像素计算该前景层像素。 采用上述算法得出的背景图像的确要平滑得多。但是，得到 d j v u文件 的大小为 1 5 . 4 k b ，压缩比反而不如上面的结果。 后来我又尝试第三种做法 第三种 做法 是这 样进行 的 也就是说，先尽量用背景层的像素值 对 每一个 需要计算的前景层 的像素，我们 沿 上下左右 四个方 向去找背景层像素 ，如果找到的话 ， 平均值( 取归一化后的 c i t y b l o c k距离的倒数作为权。 就把背景层像素的加权 ) 赋给它。 趟下来就可 以结束 了。这种 方法 处 理后得 到的背 景层相 当平滑 这 样至 多两 而 且得 到 d j v u文件的大小为 1 4 . 2 k b ，略强于第一种方法。 上述三种方法在用 d j v u s o l o 3 . 0 ( n o n c o m m e r c i a l e d i t i o n ) 压缩的时 候，使用的是完全相同的压缩选项，而且就恢复后的原图像的外观而言也没 有什么较 明显的差别。值得注意的是 ，在三种方法 中得到背景层最平滑 的压 缩效果却是最差的，也就是说平滑化并不是使得压缩比最高的唯一指标。就 这个例子而言，因为背景层较复杂， 第二种方法平滑后前景层也变得较复杂， 这样一来反倒比保持一点轮廓但同时得到的前景层较简单的第一种方法更不 利于压缩 。 经过对上述三种方法效果的比较和鉴别，我最终采用类似双线性插值的 方法实现第三种做法。时间复杂度是 n阶( n为图像像素的个数。) ，压缩之 后的 d j v u文件的大小与投影算法得到的相仿，而投影算法在最坏情况下的 时间复杂度是 n l o g n o 6 、掩码层的保存。这种方法的一个想法就是对一个连通体只存轮廓。( 注意 一个连通体可能会对应多个各自 封闭的边缘。) 我使用的方法就是 8 - 邻域链 码，这样除每个边缘的起点外，其它边缘点都只需要 3个 b i t e 作为例子的中文文档图像本身( 图 6 . 5 ) ，以及边缘检测的结果( 图 6 . 6 ) 和 平滑化处理后的背景图像( 图 6 . 7 ) 列在本文最后。其中前景层经平滑化之后 变成一幅全黑图像，被d j v u s o l o 3 . 0 ( n o n c o m m e r c i a l e d i t i o n ) 存成了一个 大小为 1 5 0 b y t e s的文件，而平滑化后的背景层被 d j v u s o l o 3 . 0 ( n o n c o m m e r c i a l e d i t i o n ) 存成t一个大小为 1 . 0 4 k b的文件，加上轮廓文件一 共约为 8 . 7 k b 。还不到用d j v u s o l o 3 . 0 ( n o n c o m m e r c i a l e d i t i o n ) 直接存原 图像得到的文件大小的一半，说明这种方法还是有前途的。目前急需解决的 问题就是如何能够保证高效地保存掩码层的轮廓。这方面还有待于进一步探 1 寸。 结论 我入学后不久开始接触到 d j v u ，从那时起一直到现在先后做过若干个 与 d j v u有关的项目。在做项目的同时，对整个 d j v u体系的了解逐步加深。 当然，这其间也阅读了不少有关的论文。 我从 d j v u中得到的启示就是，整个 d j v u体系中，撇开实现不提，大 部分东西不是第一次提出的。 诸如分层压缩的思想、 小波压缩、 投影算法、隐 马尔科夫链模型 ( h m m) . j b 2的 s h a p e d i c t i o n a r y等等，大都是在前人的 基础上加以改进或修改使之能够被纳入到 d j v u这个体系中。但它确实取得 了成功。这也许是整个 d j v u 体系中最值得吸取的东西。 我在参考 d j v u o p e n s o u r c e c o d e 的基础上实现了高分辨率黑白位图到 低分辨率灰度位图的快速直接缩放，并将其整合进 t y p e r e a d e r中，从而解 决了该软件存在的问题。这件事情对我来说是一次有益的实践，因为这是我 第一次在独立解决图像算法问题方面的成功尝试。 后来，我又对其中的投影算法产生了兴趣。经过一些思考和试验，我发 现投影算法的作用完全可以用经过修改的平滑化算法代替。 最后我在 d j v u用于中文文档图像压缩的性能方面做了一些试验，希望 这些工作能对中文数字化图书馆的建设有帮助。 第六章有关图像分层压缩的内容仅仅是一点尝试，还有很多工作要做。 比如说，寻找高效的轮廓压缩算法。在这方面，相信分形算法很有希望。 主要参考文献 文 1 l e o n b o t t o u , p a t r i c k h a f f n e r , p a u l g . h o w a r d , p a t r i c e s i m a r d , y o s h u a b e n g i o a n d y a n n l e c u n , hi g h q u a l i t y do c u me n t i ma g e c o mp r e s s i o n wi t h d j v u , j u l y 1 3 , 1 9 9 8 文 2 l e o n b o t t o u a n d s t e v e n p i g e o n , l o s s y c o m p r e s s i o n o f p a r t i a l l y ma s k e d s t i l l i ma g e s , a p r i l 3 , 1 9 9 8 文 3 p a t r i c k h a f t n e t , y a n n l e c u n , l e o n b o t t o u , p a u l h o w a r d , p a s c a l v i n c e n t a n d b i l l r i e me r s , c o l o r d o c u me n t s o n t h e we b wi t h d j v u 文 4 s p e c i f i c a t i on o f d j v u i ma g e c omp r e s s i o n f or ma t ve r s i o n o f 1 9 9 9 0 4 2 9 1 5 : 4