📄 doublecode.cpp
字号:
#include "stdafx.h"
#include <math.h>
#include "DoubleCode.h"
/*
关于行尾大误差数的编码规则
概率模型: <1>各象素相互独立,<2>每象素是大误差的概率为 p
模型估计: 主要是估计 p 值,定初值为 1/8,每行编码结束时累计象素数(PixN)与大误差数(ErrN),p=ErrN/PixN
实际使用值为 DoubleN=(PixN*16)/ErrN 意义是每(DoubleN/16)象素中含有一个大误差,
*16 目的是提高精度
二项分布的半概率点确定:
设某行尾累积待检大误差的象素数为 N, 已检出大误差数为 en, 半概率点位置在 K
K=(N*16+[DoubleN/4])/DoubleN
半概率点所在区宽度确定:
此宽度由半概率点 K 决定, 由于函数关系不好列出, 采用查表方法, 建立对应表.
编码过程: <1> 由象素数 N 和概率倒数值 DoubleN, 求 K 值.
<2> 由 K 值求 Huffman编码的宽度表.
<3> 检测待编码的大误差象素数所处的区间, 并编出首码(0...01)0的个数是区间号.以1比特表示上下区.
<4> 根据区间的位置与宽度, 编码大误差数在区间的精确位置, 采用Huffman编码, 这是尾码部分.
<5> 更新PixN、ErrN值.
补充: 构造不同项数的 Huffman 码表, 概率是按大到小排队的, 但相差并不大, 这个表在几何分布的编码中也可用.
HuffcodingBit[6][7]存放码表, HuffcodingL[6][7]存放码长, 大于等于8时用自然二进
*/
CDoubleErrorNumberFastCoding::CDoubleErrorNumberFastCoding()
{
Init();
Reset();
}
void CDoubleErrorNumberFastCoding::Reset()
{
PixN=8;
ErrN=1;//初始概率1/8
BitNumber=0;
}
void CDoubleErrorNumberFastCoding::Init()
{
int i;
UsingBinaryCode=FALSE;
for(i=0;i<PART_WIDTH1_HALF_PROBABILITY_FAST_SEAT;i++){PartW[i]=1;PartBit[i]=0;}
for(;i<PART_WIDTH2_HALF_PROBABILITY_FAST_SEAT;i++){PartW[i]=2;PartBit[i]=1;}
for(;i<PART_WIDTH4_HALF_PROBABILITY_FAST_SEAT;i++){PartW[i]=4;PartBit[i]=2;}
for(;i<PART_WIDTH8_HALF_PROBABILITY_FAST_SEAT;i++){PartW[i]=8;PartBit[i]=3;}
}
int/*返回编码比持数*/ CDoubleErrorNumberFastCoding::OneEncodePass(int Number/*总象素数*/,int ErrorN/*待编码的大误差数*/,LPBYTE lpCodeBit,int Bitcp)
{
/* 编码过程: <1> 由象素数 N 和概率倒数值 DoubleN, 求 K 值.
<2> 由 K 值求区间宽度和区间内编码比特数.
<3> 检测待编码的大误差象素数所处的区间, 并编出首码(0...01)0的个数是区间号.以1比特表示上下区.
<4> 根据区间的位置与宽度, 编码大误差数在区间的精确位置, 这是尾码部分.
<5> 更新PixN、ErrN值.
*/
int DoubleN=(PixN<<4)/ErrN;
int W,Code,D,d,n,CodeL,N,K,bitn;
N=Number;
// <1> 由象素数 N 和概率倒数值 DoubleN, 求 K 值.
if(UsingBinaryCode==FALSE)K=((N<<4)+(DoubleN>>2))/DoubleN;
else K=MAX_HALF_PROBABILITY_FAST_SEAT+1;
if(K<=MAX_HALF_PROBABILITY_FAST_SEAT)
{//采用二项分布快速编码
//<2> 由 K 值求区间宽度和区间内编码比特数.
W=PartW[K];
bitn=PartBit[K];
if(K<1)
{
if(ErrorN<MAX_0_NUMBER){Code=1<<ErrorN;CodeL=ErrorN+1;}
else
{//采用自然二进制编码
for(n=0;n<14&&(1<<n)<Number;n++);
Code=(1<<MAX_0_NUMBER)|(ErrorN<<(MAX_0_NUMBER+1));
CodeL=MAX_0_NUMBER+1+n;
}
}
else
{
if(ErrorN>=K)
{
D=ErrorN-K;
//<3> 检测待编码的大误差象素数所处的区间, 并编出首码(0...01)0的个数是区间号.以1比特表示上下区.
n=D/W;
d=D%W;
if(n<MAX_0_NUMBER)
{
Code=(3<<n);CodeL=n+2;//包含上下位区间的指示比特1
Code|=d<<CodeL;
CodeL+=bitn;
}
else
{//采用自然二进制编码
for(n=0;n<14&&(1<<n)<Number;n++);
Code=(1<<MAX_0_NUMBER)|(ErrorN<<(MAX_0_NUMBER+1));
CodeL=MAX_0_NUMBER+1+n;
}
}
else
{
D=K-1-ErrorN;//K值本身是在下区间编码的,上区间将不含它
//<3> 检测待编码的大误差象素数所处的区间, 并编出首码(0...01)0的个数是区间号.以1比特表示上下区.
n=D/W;
d=D%W;
if(n<MAX_0_NUMBER)
{
Code=(1<<n);CodeL=n+2;//包含上下位区间的指示比特1
Code|=d<<CodeL;
CodeL+=bitn;
}
else
{//采用自然二进制编码
for(n=0;n<14&&(1<<n)<Number;n++);
Code=(1<<MAX_0_NUMBER)|(ErrorN<<(MAX_0_NUMBER+1));
CodeL=MAX_0_NUMBER+1+n;
}
}
}
}
else
{//采用自然二进制编码
for(n=0;n<14&&(1<<n)<Number;n++);Code=ErrorN;CodeL=n;
}
//<5> 更新PixN、ErrN值.
PixN+=N;
ErrN+=ErrorN;
if(PixN>0x1000000)
{
PixN>>=1;
ErrN>>=1;
}
if((Bitcp&7)+CodeL<32)(*((int *)(lpCodeBit+(Bitcp>>3))))|=(Code<<(Bitcp&7));
else
{
(*((int *)(lpCodeBit+(Bitcp>>3))))|=((Code&0xff)<<(Bitcp&7));
(*((int *)(lpCodeBit+(Bitcp>>3)+1)))|=((Code>>8)<<(Bitcp&7));
}
BitNumber+=CodeL;
return CodeL;
}
int/*返回大误差数*/ CDoubleErrorNumberFastCoding::OneDecodePass(int Number/*总象素数*/,LPBYTE lpCodeBit/*码流指针*/,int Bitcp/*码流比特位*/,int &CodeL)
{
int DoubleN;
int W,n,ErrorN,ZeroN;//初始区间宽度
int N,K,bitn;
N=Number;
int UpDown;
if(ErrN>0)DoubleN=(PixN<<4)/ErrN;//<<4是统一乘以16，提高精度，最后再统一除以16。
else DoubleN=(PixN<<4);
// <1> 由象素数 N 和概率倒数值 DoubleN, 求 K 值.
if(UsingBinaryCode==FALSE)K=((N<<4)+(DoubleN>>2))/DoubleN;
else K=MAX_HALF_PROBABILITY_FAST_SEAT+1;
if(K<=MAX_HALF_PROBABILITY_FAST_SEAT)
{//采用二项分布译码
//<2> 由 K 值求 Huffman编码的宽度表.
W=PartW[K];
bitn=PartBit[K];
ZeroN=ReturnZeroBitNumber(lpCodeBit,Bitcp);
if(K<1)
{
if(ZeroN<MAX_0_NUMBER){ErrorN=ZeroN;CodeL=ErrorN+1;}
else
{//采用自然二进制译码
for(n=0;n<14&&(1<<n)<Number;n++);
ErrorN=GetFromBitStream(lpCodeBit,Bitcp+MAX_0_NUMBER+1,n);
CodeL=MAX_0_NUMBER+1+n;
}
}
else
{
UpDown=GetFromBitStream(lpCodeBit,Bitcp+ZeroN+1,1);
CodeL=ZeroN+2;
if(UpDown)
{
//<3> 检测待编码的大误差象素数所处的区间, 并编出首码(0...01)0的个数是区间号.以1比特表示上下区.
if(ZeroN<MAX_0_NUMBER)
{//在编码允许范围内,0 的个数就是跳过的区间数
ErrorN=K+ZeroN*W+GetFromBitStream(lpCodeBit,Bitcp+CodeL,bitn);
CodeL+=bitn;
}
else
{//采用自然二进制译码
for(n=0;n<14&&(1<<n)<Number;n++);
ErrorN=GetFromBitStream(lpCodeBit,Bitcp+MAX_0_NUMBER+1,n);
CodeL=MAX_0_NUMBER+1+n;
}
}
else
{
//<3> 检测待编码的大误差象素数所处的区间, 并编出首码(0...01)0的个数是区间号.以1比特表示上下区.
if(ZeroN<MAX_0_NUMBER)
{//在编码允许范围内,0 的个数就是跳过的区间数
ErrorN=K-1-ZeroN*W-GetFromBitStream(lpCodeBit,Bitcp+CodeL,bitn);
CodeL+=bitn;
}
else
{//采用自然二进制译码
for(n=0;n<14&&(1<<n)<Number;n++);
ErrorN=GetFromBitStream(lpCodeBit,Bitcp+MAX_0_NUMBER+1,n);
CodeL=MAX_0_NUMBER+1+n;
}
}
}
}
else
{
for(n=0;n<14&&(1<<n)<Number;n++);
ErrorN=GetFromBitStream(lpCodeBit,Bitcp,n);
CodeL=n;
}
//<5> 更新PixN、ErrN值.
PixN+=N;
ErrN+=ErrorN;
if(PixN>0x1000000)
{
PixN>>=1;
ErrN>>=1;
}
return ErrorN;
}
int CDoubleErrorNumberFastCoding::ReturnZeroBitNumber(LPBYTE lpCodeStream,int CodeBitcp)
{//在当前的码流位置上,检查连续'0'的个数。
int a,i,j;
a=(*((int *)(lpCodeStream+(CodeBitcp>>3)))>>(CodeBitcp&7))&0xffffff;
if(a==0)
{
i=24;
a=(*((int *)(lpCodeStream+(CodeBitcp>>3)+3))>>(CodeBitcp&7))&0xffffff;
if(a==0)
{
i+=24;
a=(*((int *)(lpCodeStream+(CodeBitcp>>3)+6))>>(CodeBitcp&7))&0xffffff;
for(j=1;(a&j)==0&&j<0x1000000;j<<=1,i++);
}
else for(j=1;(a&j)==0&&j<0x1000000;j<<=1,i++);
}
else for(j=1,i=0;(a&j)==0&&j<0x1000000;j<<=1,i++);
return i;
}
int CDoubleErrorNumberFastCoding::GetFromBitStream(LPBYTE lpCodeStream,int CodeBitcp,int b)
{//在当前的码流位置上取出 b 比特，比特放入低位作为返回值。一般不能大24比特。
return (*((int *)(lpCodeStream+(CodeBitcp>>3)))>>(CodeBitcp&7))&~((-1)<<b);
}
/*
关于行尾大误差游程的编码规则
概率模型: <1>各象素相互独立,<2>每象素是大误差的概率为 p,<3> 0 游程长为l时的概率为p*(1-p)^l
模型估计: 主要是估计 p 值, 设象素数为 N, 大误差数为 en, p=en/N, 每编码一个大误差en与N各减1,
几何分布的半概率点确定:
编码区间宽度的估算 K=(N*log2)/en, (log2可以转化为两个整数的比值),
当 K>8 时, K 取最小的大于K的2幂
编码过程: <1> 由象素数 N 和大误差数 en, 求 K 值.
<2> 检测待编码的大误差游程所处的区间, 并编出首码(0...01)0的个数是区间号.以1比特表示大误差的符号.
<3> 根据区间的宽度, 编码大误差数在区间的精确位置, 采用Huffman编码, 这是尾码部分.
<4> 更新N、en值.
补充: 构造不同项数的 Huffman 码表, 概率是按大到小排队的, 但相差并不大, 这个表在几何分布的编码中也可用.
HuffcodingBit[8][8]存放码表, HuffcodingL[8][8]存放码长, 大于等于8时用自然二进
*/
CDoubleErrorRunFastCoding::CDoubleErrorRunFastCoding()
{
Init();
Reset();
}
void CDoubleErrorRunFastCoding::Reset()
{
BitNumber=0;
}
void CDoubleErrorRunFastCoding::Init()
{
UsingBinaryCode=FALSE;
}
int CDoubleErrorRunFastCoding::GetHalfProbabilityWidth(int Number,int ErrorN,int &Bitn)
{
// int W=(int)((Number*log(2))/ErrorN);
// int W=(Number*69314)/ErrorN/100000;
int W=(Number*709)/ErrorN/1024;
for(Bitn=0;(1<<Bitn)<W;Bitn++);
if(W<(1<<Bitn)&&Bitn>1)Bitn--;
W=(1<<Bitn);
return W;
}
int/*返回编码比持数*/ CDoubleErrorRunFastCoding::OneEncodePass(int Number/*总象素数*/,
int ErrorN/*待编码的大误差数*/,
int RunL,
LPBYTE lpCodeBit,int Bitcp)
{
/* 编码过程: <1> 由象素数 N 和大误差数 en, 求 K 值.
<2> 检测待编码的大误差游程所处的区间, 并编出首码(0...01)0的个数是区间号.以1比特表示大误差的符号.
<3> 根据区间的宽度, 编码大误差数在区间的精确位置, 采用Huffman编码, 这是尾码部分.
<4> 更新N、en值.
*/
if(ErrorN<=0||Number<ErrorN)return 0;
int W,Code,n,CodeL,Bitn,ZeroN,Seat;//初始区间宽度
// <1> 由象素数 N 和大误差数 en, 求 W 值.
if(UsingBinaryCode==FALSE)W=GetHalfProbabilityWidth(Number,ErrorN,Bitn);
else W=MAX_HALF_PROBABILITY_FAST_WIDTH+1;
if(W<1)W=1;
if(W<=MAX_HALF_PROBABILITY_FAST_WIDTH)
{//采用几何分布编码
ZeroN=RunL/W;
Seat=RunL%W;
// for(ZeroN=0,Seat=RunL;Seat>=W;ZeroN++)
// {
// Seat-=W;
// if(ZeroN>8)
// {
// W<<=1;
// Bitn++;
// }
// }
if(ZeroN<MAX_0_NUMBER)
{
Code=1<<ZeroN;
CodeL=ZeroN+1;
Code|=(Seat<<CodeL);
CodeL+=Bitn;
}
else
{//采用自然二进制编码
for(n=0;n<14&&(1<<n)<Number;n++);
Code=(1<<MAX_0_NUMBER)|(RunL<<(MAX_0_NUMBER+1));
CodeL=MAX_0_NUMBER+1+n;
}
}
else
{//采用自然二进制编码
for(n=0;n<14&&(1<<n)<Number;n++);Code=RunL;CodeL=n;
}
if((Bitcp&7)+CodeL<32)(*((int *)(lpCodeBit+(Bitcp>>3))))|=(Code<<(Bitcp&7));
else
{
(*((int *)(lpCodeBit+(Bitcp>>3))))|=((Code&0xff)<<(Bitcp&7));
(*((int *)(lpCodeBit+(Bitcp>>3)+1)))|=((Code>>8)<<(Bitcp&7));
}
BitNumber+=CodeL;
return CodeL;
}
int/*返回大误游程*/ CDoubleErrorRunFastCoding::OneDecodePass(int Number/*总象素数*/,
int ErrorN/*待编码的大误差数*/,
LPBYTE lpCodeBit/*码流指针*/,int Bitcp/*码流比特位*/,
int &CodeL)
{
if(ErrorN<=0||Number<ErrorN)return 0;
int W,n,ZeroN,Seat,RunL,Bitn;//初始区间宽度
if(UsingBinaryCode==FALSE)W=GetHalfProbabilityWidth(Number,ErrorN,Bitn);
else W=MAX_HALF_PROBABILITY_FAST_WIDTH+1;
if(W<1)W=1;
if(W<=MAX_HALF_PROBABILITY_FAST_WIDTH)
{//采用几何分布译码
//<2> 由 K 值求 Huffman编码的宽度表.
ZeroN=ReturnZeroBitNumber(lpCodeBit,Bitcp);
if(ZeroN<MAX_0_NUMBER)
{
CodeL=ZeroN+1;
RunL=ZeroN*W;
// RunL=0;
// if(ZeroN>0)for(n=0;n<ZeroN;n++)
// {
// RunL+=W;
// if(n>8)
// {
// W<<=1;
// Bitn++;
// }
// }
Seat=GetFromBitStream(lpCodeBit,Bitcp+ZeroN+1,Bitn);
RunL+=Seat;
CodeL+=Bitn;
}
else
{//采用自然二进制译码
for(n=0;n<14&&(1<<n)<Number;n++);
RunL=GetFromBitStream(lpCodeBit,Bitcp+MAX_0_NUMBER+1,n);
CodeL=MAX_0_NUMBER+1+n;
}
}
else
{
for(n=0;n<14&&(1<<n)<Number;n++);
RunL=GetFromBitStream(lpCodeBit,Bitcp,n);
CodeL=n;
}
return RunL;
}
int CDoubleErrorRunFastCoding::ReturnZeroBitNumber(LPBYTE lpCodeStream,int CodeBitcp)
{//在当前的码流位置上,检查连续'0'的个数。
int a,i,j;
a=(*((int *)(lpCodeStream+(CodeBitcp>>3)))>>(CodeBitcp&7))&0xffffff;
if(a==0)
{
i=24;
a=(*((int *)(lpCodeStream+(CodeBitcp>>3)+3))>>(CodeBitcp&7))&0xffffff;
if(a==0)
{
i+=24;
a=(*((int *)(lpCodeStream+(CodeBitcp>>3)+6))>>(CodeBitcp&7))&0xffffff;
for(j=1;(a&j)==0&&j<0x1000000;j<<=1,i++);
}
else for(j=1;(a&j)==0&&j<0x1000000;j<<=1,i++);
}
else for(j=1,i=0;(a&j)==0&&j<0x1000000;j<<=1,i++);
return i;
}
int CDoubleErrorRunFastCoding::GetFromBitStream(LPBYTE lpCodeStream,int CodeBitcp,int b)
{//在当前的码流位置上取出 b 比特，比特放入低位作为返回值。一般不能大24比特。
return (*((int *)(lpCodeStream+(CodeBitcp>>3)))>>(CodeBitcp&7))&~((-1)<<b);
}
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -