о뷢չ
JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
1999Vol.36No.7P.888-891



ڰĵͼĸ߱ѹ
䡡񡡺ɽ
ժҪڰĵͼͬڳıļͼļʹóѹ㷨ȡýϸߵѹ.з˳ĵԼʹó㷨ȱ㣻ԣһʧѹ㷨ѹķֿγ̱Ļϱ뷽.ʵ֤÷ѹֵѹARJPKZIPLZWȣԼ0.51.2ȳγ̱Լ0.30.8.
ؼʣʧѹأγ̱룬ֿ
ţTP391
DOCUMENT BINARY IMAGE EFFECTIVE
LOSSLESS COMPRESSION 
REN Ming-Wu
Department of Computer Science, Nanjing University of Science and Technology, Nanjing 210094
CAO Yu-Long
Department of Computer Science, Nanjing University of Science and Technology, Nanjing 210094
TANG Zhen-Min
Department of Computer Science, Nanjing University of Science and Technology, Nanjing 210094
HU Zhong-Shan
Department of Computer Science, Nanjing University of Science and Technology, Nanjing 210094
YANG Jing-Yu
Department of Computer Science, Nanjing University of Science and Technology, Nanjing 210094
AbstractDocument binary image is different from text file and general image file. It's very difficult to reach high compress ratios using general compressing algorithms. In this paper, the characteristic of document is analyzed and a lossless mixed coding algorithm is proposed, which uses the block coding and run length coding (RLC). Experiments prove it can increase higher compress ratios by 0.5 to 1.2 compared with dictionary-based coding (ARJ, LZW, PKZIP etc.) and by 0.3 to 0.8 compared with general RLC.
Key wordslossless compression, entropy, run length coding, block coding
1
Ϣֻĸٽиѹصս.ڲͬ򣬳˸ָѹ15ݣصͳƱ루Huffman롢Shannon롢ȣ25ݣֵARJLZHPKZIPѹ2ݣα롢С任ȱ任1,3ݣֿ5ݣԼJPEGMPEG3ݵ.
رͻֵѹѹıļͻҶͼʧѹ.ıļдʾظֵѹܱͨرȡøõıļѹЧʣα롢С任ȱ任ҪڻҶͼͲɫͼʧѹڶֵͼıͼѹֿҪڶֵͼѹJPEGMPEGרھֹ˶ͼʧѹ.
ĵͼĴΪϢҪӦ֮һ.еڶַ˶ֵĵͼصͳѹ㷨Уһָ߱ѹķĲʵܽ.
2ֵĵͼѹ
6ֵָͼѹĲڰױϸռձȡڳͰ׳γ̸Ŀ˶ֵĵͼԣȽϷ˳WPSֿ롢ر롢ֵ롢γ̱ȶֵͼѹ.ذش洢.
2.1ֵĵͼص
ĵɨֱһܲʧʻСֱʣʻΪ12أһֱͼ.ֵĵͼ6治ͬ볣ĻҶͼ񡢶ֵͼıĵҪ¼.
1 ϸ.ΪɫԴַıʻҷֱ.ñԵռȫɫıʾϸҲԲƽʻʾϸ.
2 ڳ̫ٶ׳̫.ɫַıʻ಻ࣻмհסСұ߽硢ҳͷҳβڿհ׵ȵĴڣ׳쳣ḻ.
3 γĿڶ.һַһַ֮ڼ϶ַڲһıʻ֮Ҳڼ϶ڰƵγĿڶ.
4 ĿС.һַܾһĿ꣬һʻһͨĿ.
5 ɫֻռȫмСıһ5%20%֮.
6 ɫصɢΧ.ĵɺɫַɣеķֲΧͷβºɫصɢΧ.ǲNNķȫ׿ĸʱʾ.пΪWrмΪWgN=Wr+Wg.
2.2ѹ
ֵͼʧѹоѹ5ݣ׿WBSγ̳ȱRLCͷֿȶַ.2ͼ1ͼ2ѹȼƽ볤.


ͼ1Ӣ(ĲԻɫʾ)


ͼ2ļ(ĲԻɫʾ)
1ֵĵͼͼ1ͼ2

ͼ񳤿пмʻȺɫɫɢϸںڳ׳γ̸Ŀ
ͼ115099.6132.1710%57%80%23773993954898
1059
ͼ210471710.61.427%51%79%52386345931505
760


2ֵĵͼͼ1ͼ2ѹ

WBSֿARJRLCѹ
224418222324Bitbyte
ͼ12.72.463.272.923.463.854.143.33.94.975.35
ͼ23.52.743.983.354.364.835.174.15.96.436.90


ڶֵĵͼһֱͼ߿Ϊ12أ̫࣬Ŀ̫.ʹóĶֵͼ룬ΪԵظٺʹ㣬ﲻһѹЧ.
WBSڶֵͼкɫֻռͼкСıȫԷȫֱӱ.ĵͼУȻɫֻռͼкСıɫصɢΧǳ󣬵òߵѹ.
WBSȣֿѱ䳤붨ÿصĲָͬʵĲͬб䳤룬ѹȸWBS.ĵͼУϸڷǳḻɫرǳСɢΧǳ󡢺ɫкͰɫм佻ֿ֯Сʱʹóȫ׿̫ȫڿ̫⣬ĸ󣬴ӶòϸߵѹӦֲ.
ڶֵͼУһȤԾǺڰ׽֯.ֵıЧáB0B1BnW0W1WmB0B1BkԽֵб.ںڳٶ׳༫֪࣬СһĺڳʹСһİ׳ԺСֵнϳ鱻ʹõĸʽСԴﵽߵѹ.2зֱbit1أByteΪλ8أֵõѹ.
RLCĵͼѹгõķѹȸWBSͷֿ룬ܳĵͼԣ1ڳַıʻʻʹȻǲȵģҺڳ٣ʹѱ䳤붨2ʹð׳ܰѶмհסҳͷҳβհסһеұ߿հ׺һ߿հ׵ĽʾΪһ׳.ѹȸڻֵ룬׳̫࣬ѹõİ׳ƽ볤ϴһ̶Ͻѹ. ͼ1ͼ2İ׳ͺڳƽ볤ֱΪ4.06/2.414.64/2.51. 
3߱ѹ
һֻڼٰ׳ࡢӶС׳ƽ볤RLCѹȵķ.ʹ÷ֲ룬пмࡢʻȵȲѡһĿСͼֳ2㣬ÿֱʹRLC.һ¼Ϣȫ׿鸳1ء0ȫ׿鸳1ء1.ڶֻѱΪ1Ŀμγ̵ļ㣬ӶЧؼС˰׳׳.
мհסСұ߽硢ҳͷҳβڿհ׵ȵĴڣְɫصռձȴﵽ80%90%İ׿飬ʹ׳.ڼ£׿պںڳ֮İ׳Ϊ׿鴦γ̸䡢ڳ಻.
hbΪֱӶԺڳأhwΪֱӶ԰׳أNwΪ׳ĸNbΪڳĸSΪͼصbΪͼƽ볤rΪͼѹȣУ
|Nw-Nb|1(1)
(2)
(3)
ʽ(3)֪ͼѹȷڰ׳ƽ볤ڳƽ볤֮.֪׿鴦׳NwСԭͼа׳Nwn=Nw-Nw,hwΪ׿ͼİ׳ƽ볤piΪ1Ḷ́򾭹p1p2pn-1󣬰׳NwNw.hiwΪpi׳ƽ볤صĽԣ1ݣɵãhw>h1w>h2w>>֣hn-1w=hw,׿ͼİ׳ƽ볤Сԭͼİ׳ƽ볤.
r1Ϊ׿õѹȣIΪԭͼѹĳȣI1Ϊ׿ѹõĳȣУ
(4)
(5)
Ϊhw<hwI1<I.
I2ΪϢѹĳȣI2<I-I1֤׿ͼѹ.ΪI-I1>0ֻҪѡʵķֿСNMѹ.ԭͼ񳤿ֱΪTbTwУ
(6)
r2ǷֿϢѹr2>1ۣݱʾȡӽ.
ɴ˿ֿ֪ԽI2ԽС׳ļٿԽСI1Խ.ضӦñѡ̶ķֿСȡŵѹ.
3ͼ2ѹ

ԭʼͼ3344881010
׺Ϣ׺Ϣ׺Ϣ׺Ϣ
׳38685152961181257313559
ڳ525592554052425245
ƽ볤4.643.093.333.503.234.103.634.203.56
ƽ볤2.512.603.102.553.422.513.882.513.91
γ̸345933340569053402137053459684534589593
ѹ6.438.363.977.724.026.963.896.863.56
6.786.906.786.73

׿ԭǾĵͼемհסСұ߽硢ҳͷҳβڿհ.пΪWrмΪWgʻΪWpֿΪWwӦ
Wp<N<min{Wg,Wr}(7)
Wp<M<Ww(8)
ʹͶӰHough任Ժ6.3ͼ2ѹ.
4С
㷨ڳĵʧѹĵͼѹȴڳĶֵͼ뷽رͻֵʧѹڰ׳Ĵ٣һ180֣ӶʹúĶγ̳ȵԿ.ķۺʵеõ֤ʹзԺ鼮Ӣ¡֧Ʊдĸ塢Ӣֵȳĵͼѹ֤ѹȸڳARJ㷨Լ0.51.2ڳRLCԼ0.30.8.
߼飺䣬У19696˶ʿоϾѧϵʦҪоΪͼӾͼѹ.
У19653ڣоΪͼӾ.
У19614ڣоΪͼ˵.
ɽУ1973ʿооΪͼʶַ.
1941ڣоΪ˹ܡ˵.
ߵλ䣨Ͼѧѧ빤ϵϾ210094
Ͼѧѧ빤ϵϾ210094
Ͼѧѧ빤ϵϾ210094
ɽϾѧѧ빤ϵϾ210094
Ͼѧѧ빤ϵϾ210094
οף
1֯. ѹ. ҵ磬1990
(Xu Zhixin. Data Compression (in Chinese). Beijing: National Defense Industry Press, 1990)
2Nelson M. Featuring Fast, Efficient Data Compression Techniques in C. M & T Books Company, USA. 1992
3. ͼѹ뼼CԳ. : ѧԷ磬1994
(Li Hongsong. Digital Image Compression and Coding, C Samples (in Chinese). Beijing: Xueyuan Press, 1994)
4Castleman K R. Digital Image Processing. Englewood Cliffs, NJ: Prentice Hall, 1996
5ݳ꣬͢. ͼ. : ʵ磬1991
(Chen Tingbiao, Xia Liangzheng. Digital Image Processing (in Chinese) Beijing: People's Post Press1991)
6Schurman J, Bartnect N, Bayer T et al. Document analysisfrom pixels to contents. Proc IEEE, 1992 80(7): 11011119
ոڣ1998-11-06
޸ڣ1999-03-12
