?? doublecode.cpp
字號(hào):
#include "stdafx.h"
#include <math.h>
#include "DoubleCode.h"
/*
關(guān)于行尾大誤差數(shù)的編碼規(guī)則
概率模型: <1>各象素相互獨(dú)立,<2>每象素是大誤差的概率為 p
模型估計(jì): 主要是估計(jì) p 值,定初值為 1/8,每行編碼結(jié)束時(shí)累計(jì)象素?cái)?shù)(PixN)與大誤差數(shù)(ErrN),p=ErrN/PixN
實(shí)際使用值為 DoubleN=(PixN*16)/ErrN 意義是每(DoubleN/16)象素中含有一個(gè)大誤差,
*16 目的是提高精度
二項(xiàng)分布的半概率點(diǎn)確定:
設(shè)某行尾累積待檢大誤差的象素?cái)?shù)為 N, 已檢出大誤差數(shù)為 en, 半概率點(diǎn)位置在 K
K=(N*16+[DoubleN/4])/DoubleN
半概率點(diǎn)所在區(qū)寬度確定:
此寬度由半概率點(diǎn) K 決定, 由于函數(shù)關(guān)系不好列出, 采用查表方法, 建立對(duì)應(yīng)表.
編碼過(guò)程: <1> 由象素?cái)?shù) N 和概率倒數(shù)值 DoubleN, 求 K 值.
<2> 由 K 值求 Huffman編碼的寬度表.
<3> 檢測(cè)待編碼的大誤差象素?cái)?shù)所處的區(qū)間, 并編出首碼(0...01)0的個(gè)數(shù)是區(qū)間號(hào).以1比特表示上下區(qū).
<4> 根據(jù)區(qū)間的位置與寬度, 編碼大誤差數(shù)在區(qū)間的精確位置, 采用Huffman編碼, 這是尾碼部分.
<5> 更新PixN、ErrN值.
補(bǔ)充: 構(gòu)造不同項(xiàng)數(shù)的 Huffman 碼表, 概率是按大到小排隊(duì)的, 但相差并不大, 這個(gè)表在幾何分布的編碼中也可用.
HuffcodingBit[6][7]存放碼表, HuffcodingL[6][7]存放碼長(zhǎng), 大于等于8時(shí)用自然二進(jìn)
*/
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/*返回編碼比持?jǐn)?shù)*/ CDoubleErrorNumberFastCoding::OneEncodePass(int Number/*總象素?cái)?shù)*/,int ErrorN/*待編碼的大誤差數(shù)*/,LPBYTE lpCodeBit,int Bitcp)
{
/* 編碼過(guò)程: <1> 由象素?cái)?shù) N 和概率倒數(shù)值 DoubleN, 求 K 值.
<2> 由 K 值求區(qū)間寬度和區(qū)間內(nèi)編碼比特?cái)?shù).
<3> 檢測(cè)待編碼的大誤差象素?cái)?shù)所處的區(qū)間, 并編出首碼(0...01)0的個(gè)數(shù)是區(qū)間號(hào).以1比特表示上下區(qū).
<4> 根據(jù)區(qū)間的位置與寬度, 編碼大誤差數(shù)在區(qū)間的精確位置, 這是尾碼部分.
<5> 更新PixN、ErrN值.
*/
int DoubleN=(PixN<<4)/ErrN;
int W,Code,D,d,n,CodeL,N,K,bitn;
N=Number;
// <1> 由象素?cái)?shù) N 和概率倒數(shù)值 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)
{//采用二項(xiàng)分布快速編碼
//<2> 由 K 值求區(qū)間寬度和區(qū)間內(nèi)編碼比特?cái)?shù).
W=PartW[K];
bitn=PartBit[K];
if(K<1)
{
if(ErrorN<MAX_0_NUMBER){Code=1<<ErrorN;CodeL=ErrorN+1;}
else
{//采用自然二進(jìn)制編碼
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> 檢測(cè)待編碼的大誤差象素?cái)?shù)所處的區(qū)間, 并編出首碼(0...01)0的個(gè)數(shù)是區(qū)間號(hào).以1比特表示上下區(qū).
n=D/W;
d=D%W;
if(n<MAX_0_NUMBER)
{
Code=(3<<n);CodeL=n+2;//包含上下位區(qū)間的指示比特1
Code|=d<<CodeL;
CodeL+=bitn;
}
else
{//采用自然二進(jìn)制編碼
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值本身是在下區(qū)間編碼的,上區(qū)間將不含它
//<3> 檢測(cè)待編碼的大誤差象素?cái)?shù)所處的區(qū)間, 并編出首碼(0...01)0的個(gè)數(shù)是區(qū)間號(hào).以1比特表示上下區(qū).
n=D/W;
d=D%W;
if(n<MAX_0_NUMBER)
{
Code=(1<<n);CodeL=n+2;//包含上下位區(qū)間的指示比特1
Code|=d<<CodeL;
CodeL+=bitn;
}
else
{//采用自然二進(jìn)制編碼
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
{//采用自然二進(jìn)制編碼
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/*返回大誤差數(shù)*/ CDoubleErrorNumberFastCoding::OneDecodePass(int Number/*總象素?cái)?shù)*/,LPBYTE lpCodeBit/*碼流指針*/,int Bitcp/*碼流比特位*/,int &CodeL)
{
int DoubleN;
int W,n,ErrorN,ZeroN;//初始區(qū)間寬度
int N,K,bitn;
N=Number;
int UpDown;
if(ErrN>0)DoubleN=(PixN<<4)/ErrN;//<<4是統(tǒng)一乘以16，提高精度，最后再統(tǒng)一除以16。
else DoubleN=(PixN<<4);
// <1> 由象素?cái)?shù) N 和概率倒數(shù)值 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)
{//采用二項(xiàng)分布譯碼
//<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
{//采用自然二進(jìn)制譯碼
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> 檢測(cè)待編碼的大誤差象素?cái)?shù)所處的區(qū)間, 并編出首碼(0...01)0的個(gè)數(shù)是區(qū)間號(hào).以1比特表示上下區(qū).
if(ZeroN<MAX_0_NUMBER)
{//在編碼允許范圍內(nèi),0 的個(gè)數(shù)就是跳過(guò)的區(qū)間數(shù)
ErrorN=K+ZeroN*W+GetFromBitStream(lpCodeBit,Bitcp+CodeL,bitn);
CodeL+=bitn;
}
else
{//采用自然二進(jìn)制譯碼
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> 檢測(cè)待編碼的大誤差象素?cái)?shù)所處的區(qū)間, 并編出首碼(0...01)0的個(gè)數(shù)是區(qū)間號(hào).以1比特表示上下區(qū).
if(ZeroN<MAX_0_NUMBER)
{//在編碼允許范圍內(nèi),0 的個(gè)數(shù)就是跳過(guò)的區(qū)間數(shù)
ErrorN=K-1-ZeroN*W-GetFromBitStream(lpCodeBit,Bitcp+CodeL,bitn);
CodeL+=bitn;
}
else
{//采用自然二進(jìn)制譯碼
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)
{//在當(dāng)前的碼流位置上,檢查連續(xù)'0'的個(gè)數(shù)。
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)
{//在當(dāng)前的碼流位置上取出 b 比特，比特放入低位作為返回值。一般不能大24比特。
return (*((int *)(lpCodeStream+(CodeBitcp>>3)))>>(CodeBitcp&7))&~((-1)<<b);
}
/*
關(guān)于行尾大誤差游程的編碼規(guī)則
概率模型: <1>各象素相互獨(dú)立,<2>每象素是大誤差的概率為 p,<3> 0 游程長(zhǎng)為l時(shí)的概率為p*(1-p)^l
模型估計(jì): 主要是估計(jì) p 值, 設(shè)象素?cái)?shù)為 N, 大誤差數(shù)為 en, p=en/N, 每編碼一個(gè)大誤差en與N各減1,
幾何分布的半概率點(diǎn)確定:
編碼區(qū)間寬度的估算 K=(N*log2)/en, (log2可以轉(zhuǎn)化為兩個(gè)整數(shù)的比值),
當(dāng) K>8 時(shí), K 取最小的大于K的2冪
編碼過(guò)程: <1> 由象素?cái)?shù) N 和大誤差數(shù) en, 求 K 值.
<2> 檢測(cè)待編碼的大誤差游程所處的區(qū)間, 并編出首碼(0...01)0的個(gè)數(shù)是區(qū)間號(hào).以1比特表示大誤差的符號(hào).
<3> 根據(jù)區(qū)間的寬度, 編碼大誤差數(shù)在區(qū)間的精確位置, 采用Huffman編碼, 這是尾碼部分.
<4> 更新N、en值.
補(bǔ)充: 構(gòu)造不同項(xiàng)數(shù)的 Huffman 碼表, 概率是按大到小排隊(duì)的, 但相差并不大, 這個(gè)表在幾何分布的編碼中也可用.
HuffcodingBit[8][8]存放碼表, HuffcodingL[8][8]存放碼長(zhǎng), 大于等于8時(shí)用自然二進(jìn)
*/
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/*返回編碼比持?jǐn)?shù)*/ CDoubleErrorRunFastCoding::OneEncodePass(int Number/*總象素?cái)?shù)*/,
int ErrorN/*待編碼的大誤差數(shù)*/,
int RunL,
LPBYTE lpCodeBit,int Bitcp)
{
/* 編碼過(guò)程: <1> 由象素?cái)?shù) N 和大誤差數(shù) en, 求 K 值.
<2> 檢測(cè)待編碼的大誤差游程所處的區(qū)間, 并編出首碼(0...01)0的個(gè)數(shù)是區(qū)間號(hào).以1比特表示大誤差的符號(hào).
<3> 根據(jù)區(qū)間的寬度, 編碼大誤差數(shù)在區(qū)間的精確位置, 采用Huffman編碼, 這是尾碼部分.
<4> 更新N、en值.
*/
if(ErrorN<=0||Number<ErrorN)return 0;
int W,Code,n,CodeL,Bitn,ZeroN,Seat;//初始區(qū)間寬度
// <1> 由象素?cái)?shù) N 和大誤差數(shù) 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
{//采用自然二進(jìn)制編碼
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
{//采用自然二進(jìn)制編碼
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/*總象素?cái)?shù)*/,
int ErrorN/*待編碼的大誤差數(shù)*/,
LPBYTE lpCodeBit/*碼流指針*/,int Bitcp/*碼流比特位*/,
int &CodeL)
{
if(ErrorN<=0||Number<ErrorN)return 0;
int W,n,ZeroN,Seat,RunL,Bitn;//初始區(qū)間寬度
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
{//采用自然二進(jìn)制譯碼
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)
{//在當(dāng)前的碼流位置上,檢查連續(xù)'0'的個(gè)數(shù)。
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)
{//在當(dāng)前的碼流位置上取出 b 比特，比特放入低位作為返回值。一般不能大24比特。
return (*((int *)(lpCodeStream+(CodeBitcp>>3)))>>(CodeBitcp&7))&~((-1)<<b);
}
?? 快捷鍵說(shuō)明
復(fù)制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號(hào)
Ctrl + =
減小字號(hào)
Ctrl + -