图像处理(Image Processing) ---------- 碎形压缩(Fractal)(C#实现)
发布时间
阅读量：
阅读量
网上很少关于Fractal压缩的质料，特此记录。
先说说自然界事物构成的一种潜在规则。自然界中一切事物的构成都具有巨大的相似性，包括:山、花、树、人、车 ......。当你仔细观察一个物体时就会发现，此物体许多部分都是由同一个细小的结构构成。下图人造栗子：
一个大的形状可由四个小的相同形状图形构成。
四个小的形状又是由更小的相同形状构成。
因此物体是可以通过找寻其中某种细小的结构，对这种细小结构进过某种重复的迭代系统多次循环后，便可以得到完整的物体。
碎形压缩：
* 在1988年，Barnsley和Sloan提出了一套碎形影像压缩的算法。他们的算法是，对原始图像找出一种特殊的迭代系统，然后便可以使用任意的图像经过此迭代系统多次迭代，生成原始图像。
* 如下图：不同的初始图形，经过同一种迭代方式，多次迭代后，都形成了形状一致的三角形模型。
- 所以根据图形成像的这种特性，碎形压缩诞生了。说白点，碎形压缩和其它压缩不同的就是：改记录pixel变成记录迭代系统数据。这样一来对图像解压缩的灵活性和效果都大幅提升，因为它可以使用任何图案通过压缩档的迭代数据还原压缩图像，并且随着迭代次数的增加，解码的效果会越来越好。
具体步骤：
碎形压缩的总体步骤：先将要压缩的图像按一定大小的块(16X16,8X8,4X4...)分割成定义域区块集和值域区块集，然后将值域的每一块与定义域中所有的块(经过收缩、旋转、偏移参数s/o变换后的块)进行对比，记录与此值域块最相似的定义域块的块号、旋转种类、偏移参数s/o(成为碎形码)。记录值域中每一块的碎形码，就构成了压缩文档。
- 一：分割定义域区块集合(Domain Block)和值域区块集合(Range Block) 。 * 下面使用D和R分别指定义域区块集合和值域区块集合中的某一块。R块是目标块，D块是参考块。
- R是不可重叠的区块，通常由左至右，由上至下，大小为BxB(常用8X8)。假设图像大小LxL，则m和n都为L/B，R有
块。
- R是不可重叠的区块，通常由左至右，由上至下，大小为BxB(常用8X8)。假设图像大小LxL，则m和n都为L/B，R有
* D是重叠区块，大小去R块的两倍，2Bx2B。取D块还有一个关键值，步长：，每次间隔取一个D块。通常去D块边的一半，你也可以1pixel移动一次，但是这样D块就太多压缩非常耗时。 假设图像大小LxL，则D会有 块。- 二：定义域区块D，收缩： * D块要与R块比较，首先要收缩成与R块一样的大小。收缩方式通常用两种：像素均值和欠采样。如图：
-
三：定义域区块D，尺度系数(s)和偏移系数(o): * D块经过收缩后与R块大小相同，可计算s/o。
- 计算s/o公式：
- 解释下公式：s = R块每个Pixel与其均值的差 同 D块每个Pixel与其均值的差 乘积的累加和，除 D块每pixel与其均值差的平方的累加和。 o = R块pixel均值 - D块pixel均值乘上面算出的s。
- 算出s和o之后还要对这两个参数进行比特量化，s的范围通常在[-1,1]之间，超过的可以认为是0。通常s量化乘2bit，即四种：0.25、0.5、0.75、1。o通常量化成7bit，即 0 ~ 128之间。
- 算完s/o后就进行对比：R块与D集合中每一个D块都计算出对应的s/o，然后D块的每个pixel乘上对应的s，再加上o。然后与R块对比，(即：
)，记录与R块差异最小的D块号和此D块的s/o。保存已经*和+上偏移参数的D块进行下一步骤。
- 计算s/o公式：
-
四：定义域区块D，旋转： * 经过偏移参数变换后的D块，就要进行旋转。旋转通常采用8种，如下图：
D块要进行8种旋转，每一种旋转都要与R块比较，找到差异值最小的旋转记录下此旋转种类。
- 五：D块与R块比较的方法：主要两种。 * MAD(Mean Absolute Difference):
, mn即区块总Pixel数，i，j 分别是区块第j行第i列的像素。
- RMSE(Root Mean Square Error):
, mn即区块总Pixel数，i，j 分别是区块第j行第i列的像素。
- RMSE(Root Mean Square Error):
经过上面的步骤，将每一个值域区块都与定义域区块比较，然后找到最合适的区块，记录好此区块在定义域区块中的位置、旋转类型、s/o，就构成了每一个值域区块的分形码，总合后就构成了压缩文档（压缩文档除分形码外，还要记录原图尺寸，块的尺寸的细节）。
解码：
- 取任意一个与原图尺寸一样的图片，按同样D块大小，分割出D块集合。
- 按照压缩文档中的每个R块的分形码，在D块集合中，取对应的D块，同样进行压缩，按记录的旋转方式旋转，乘加上偏移参数s/o，形成R块。对压缩文档中的分形码全部按上面步骤解码后，将所有R块拼接就构成了一副新图。
- 用新图做为新的参考图，分割出D块集合，再按照压缩文档，进行上面同样的步骤，输出新图。
- 经过多次迭代之后，新图会慢慢被还原成原图，并且品质随着迭代次数增加会越来越好。
自己些的C#实现结果，写的有点仓促，很多细节没有调整，效果没有非常好，先看结果：
C#实现：
1、imageOperate 工具类：
//获取定义块池
public void getDomainPool(Bitmap Image, out List<Bitmap> DomainPool)
{
DomainPool = new List<Bitmap>();
int width = Image.Width;
int height = Image.Height;
int domainSize = 8;
//步长
int stepSize = 4;
//块数
int Dx = (width - domainSize) / stepSize + 1;
int Dy = (height - domainSize) / stepSize + 1;
int x2 = 0;
int y2 = 0;
for (int j = 0; j < Dy; j++)
{
for (int i = 0; i < Dx; i++)
{
Bitmap domainBlock = Image.Clone(new Rectangle(x2, y2, domainSize, domainSize), PixelFormat.Format24bppRgb);
//domainblock收缩，欠采样。
Bitmap TdomainBlock = domainBlock.Clone(new Rectangle(1, 1, 4, 4), PixelFormat.Format24bppRgb);
DomainPool.Add(TdomainBlock);
x2 += stepSize;
}
y2 += stepSize;
x2 = 0;
}
}
//获取值域和定义域块池
public void getBlockPool(Bitmap Image, out List<Bitmap> RangePool, out List<Bitmap> DomainPool)
{
RangePool = new List<Bitmap>();
DomainPool = new List<Bitmap>();
int width = Image.Width;
int height = Image.Height;
//Rangeblock和Domainblock的大小(单边)
int rangeSize = 4;
int domainSize = 8;
//步长
int stepSize = 4;
//块数
int Rx = width / rangeSize;
int Ry = height / rangeSize;
int Dx = (width - domainSize) / stepSize + 1;
int Dy = (height - domainSize) / stepSize + 1;
int x1 = 0;
int y1 = 0;
int x2 = 0;
int y2 = 0;
for (int j = 0; j < Ry; j++)
{
for (int i = 0; i < Rx; i++)
{
Bitmap rangeBlock = Image.Clone(new Rectangle(x1, y1, rangeSize, rangeSize), PixelFormat.Format24bppRgb);
RangePool.Add(rangeBlock);
x1 += rangeSize;
}
y1 += rangeSize;
x1 = 0;
}
for (int j = 0; j < Dy; j++)
{
for (int i = 0; i < Dx; i++)
{
Bitmap domainBlock = Image.Clone(new Rectangle(x2, y2, domainSize, domainSize), PixelFormat.Format24bppRgb);
//domainblock收缩，欠采样。
Bitmap TdomainBlock = domainBlock.Clone(new Rectangle(1, 1, 4, 4), PixelFormat.Format24bppRgb);
DomainPool.Add(TdomainBlock);
x2 += stepSize;
}
y2 += stepSize;
x2 = 0;
}
}
//D块*+偏移参数
public Bitmap getAddOSImg( Bitmap D, double o, double s)
{
Bitmap Dnew = D;
for (int j = 0; j < 4; j++)
{
for (int i = 0; i < 4; i++)
{
byte val = (byte)(D.GetPixel(i, j).R * s + o);
if (val > 255)
{
val = 255;
}
Dnew.SetPixel(i, j, Color.FromArgb(val, val, val));
}
}
return Dnew;
}
//MAD计算R/D差异
public double CalculateMin(Bitmap R, Bitmap D, double o, double s)
{
double Min = 0;
for (int j = 0; j < 4; j++)
{
for (int i = 0; i < 4; i++)
{
Min += Math.Abs(R.GetPixel(i, j).R - (D.GetPixel(i, j).R * s + o));
}
}
return Min;
}
//计算o/s
public void CalculateOS(Bitmap R, Bitmap D, out double o, out double s)
{
//o = R − s ⋅D, s =< R − R ⋅1, D− D⋅1 > / || D − D⋅1||2
double sumR = 0;
double sumD = 0;
double aveR = 0;
double aveD = 0;
double inner = 0;
double norm = 0;
for (int j = 0; j < 4; j++)
{
for (int i = 0; i < 4; i++)
{
sumR += R.GetPixel(i, j).R;
sumD += D.GetPixel(i, j).R;
}
}
aveR = sumR / 16.0;
aveD = sumD / 16.0;
for (int j = 0; j < 4; j++)
{
for (int i = 0; i < 4; i++)
{
inner += (R.GetPixel(i, j).R - aveR) * (D.GetPixel(i, j).R - aveD);
norm += Math.Pow(D.GetPixel(i, j).R - aveD, 2);
}
}
s = inner / norm;
o = Math.Round(Math.Abs(aveR - s * aveD) / 255 * 128);
if (s > 1 || s < -1)
{
s = 0;
}
else if (Math.Abs(s) < 0.25)
{
s = 0.25;
}
else if (Math.Abs(s) >= 0.25 && Math.Abs(s) < 0.5)
{
s = 0.5;
}
else if (Math.Abs(s) >= 0.5 && Math.Abs(s) < 0.75)
{
s = 0.75;
}
else
{
s = 1;
}
if (o > 128)
{
o = 128;
}
}
/// <summary>
/// 8种旋转
/// </summary>
/// <param name="D"></param>
/// <returns></returns>
public Bitmap rotateOne(Bitmap D)
{ //对垂直轴旋转
int width = D.Width;
int height = D.Height;
Bitmap rotateOneP = new Bitmap(width, height, PixelFormat.Format24bppRgb);
for (int y = 0; y < height; y++)
{
for (int x = 0; x < width; x++)
{
rotateOneP.SetPixel(x, y, D.GetPixel(width - x - 1, y));
}
}
return rotateOneP;
}
public Bitmap rotateTwo(Bitmap D)
{ //对水平轴旋转
int width = D.Width;
int height = D.Height;
Bitmap rotateTwoP = new Bitmap(width, height, PixelFormat.Format24bppRgb);
for (int y = 0; y < height; y++)
{
for (int x = 0; x < width; x++)
{
rotateTwoP.SetPixel(x, y, D.GetPixel(x, height - y - 1));
}
}
return rotateTwoP;
}
public Bitmap rotateThree(Bitmap D)
{ //对次对角线旋转
int width = D.Width;
int height = D.Height;
Bitmap rotateThreeP = new Bitmap(width, height, PixelFormat.Format24bppRgb);
for (int y = 0; y < height; y++)
{
for (int x = 0; x < width; x++)
{
rotateThreeP.SetPixel(x, y, D.GetPixel(height - y - 1, width - x - 1));
}
}
return rotateThreeP;
}
public Bitmap rotateFour(Bitmap D)
{ //对主对角线旋转
int width = D.Width;
int height = D.Height;
Bitmap rotateFourP = new Bitmap(width, height, PixelFormat.Format24bppRgb);
for (int y = 0; y < height; y++)
{
for (int x = 0; x < width; x++)
{
rotateFourP.SetPixel(x, y, D.GetPixel(y, x));
}
}
return rotateFourP;
}
public Bitmap rotateFive(Bitmap D)
{ //逆时针旋转270°
int width = D.Width;
int height = D.Height;
Bitmap rotateFiveP = new Bitmap(width, height, PixelFormat.Format24bppRgb);
for (int y = 0; y < height; y++)
{
for (int x = 0; x < width; x++)
{
rotateFiveP.SetPixel(x, y, D.GetPixel(y, width - x - 1));
}
}
return rotateFiveP;
}
public Bitmap rotateSix(Bitmap D)
{ //逆时针旋转180°
int width = D.Width;
int height = D.Height;
Bitmap rotateSixP = new Bitmap(width, height, PixelFormat.Format24bppRgb);
for (int y = 0; y < height; y++)
{
for (int x = 0; x < width; x++)
{
rotateSixP.SetPixel(x, y, D.GetPixel(width - x - 1, height - y - 1));
}
}
return rotateSixP;
}
public Bitmap rotateSeven(Bitmap D)
{ //逆时针旋转90°
int width = D.Width;
int height = D.Height;
Bitmap rotateSevenP = new Bitmap(width, height, PixelFormat.Format24bppRgb);
for (int y = 0; y < height; y++)
{
for (int x = 0; x < width; x++)
{
rotateSevenP.SetPixel(x, y, D.GetPixel(height - y - 1, x));
}
}
return rotateSevenP;
}
}
2、编码：
private void FractalEncode(Object Image)
{
List<Bitmap> RangePool;
List<Bitmap> DomainPool;
double s;
double o;
fractalImop.getBlockPool((Bitmap)Image, out RangePool, out DomainPool);
List<double> smin = new List<double>();
List<int> rotaNo = new List<int>();
List<double> oNo = new List<double>();
List<double> sNo = new List<double>();
List<double> fractalMark = new List<double>();
for (int k = 0; k < RangePool.LongCount(); k++)
{
for (int t = 0; t < DomainPool.LongCount(); t++)
{
fractalImop.CalculateOS(RangePool[k], DomainPool[t], out o, out s);
double min0 = fractalImop.CalculateMin(RangePool[k], DomainPool[t], o, s);
Bitmap D1 = fractalImop.rotateOne(DomainPool[t]);
double min1 = fractalImop.CalculateMin(RangePool[k], D1, o, s);
Bitmap D2 = fractalImop.rotateTwo(DomainPool[t]);
double min2 = fractalImop.CalculateMin(RangePool[k], D2, o, s);
Bitmap D3 = fractalImop.rotateThree(DomainPool[t]);
double min3 = fractalImop.CalculateMin(RangePool[k], D3, o, s);
Bitmap D4 = fractalImop.rotateFour(DomainPool[t]);
double min4 = fractalImop.CalculateMin(RangePool[k], D4, o, s);
Bitmap D5 = fractalImop.rotateFive(DomainPool[t]);
double min5 = fractalImop.CalculateMin(RangePool[k], D5, o, s);
Bitmap D6 = fractalImop.rotateSix(DomainPool[t]);
double min6 = fractalImop.CalculateMin(RangePool[k], D6, o, s);
Bitmap D7 = fractalImop.rotateSeven(DomainPool[t]);
double min7 = fractalImop.CalculateMin(RangePool[k], D7, o, s);
double mins = Math.Min(min0, Math.Min(min1, Math.Min(min2, Math.Min(min3, Math.Min(min4, Math.Min(min5, Math.Min(min6, min7)))))));
if (mins == min0)
{
rotaNo.Add(0);
}
else if (mins == min1)
{
rotaNo.Add(1);
}
else if (mins == min2)
{
rotaNo.Add(2);
}
else if (mins == min3)
{
rotaNo.Add(3);
}
else if (mins == min4)
{
rotaNo.Add(4);
}
else if (mins == min5)
{
rotaNo.Add(5);
}
else if (mins == min6)
{
rotaNo.Add(6);
}
else
{
rotaNo.Add(7);
}
smin.Add(mins);
oNo.Add(o);
sNo.Add(s);
}
double min = smin[0];
int motion = 0;
for (int n = 0; n < smin.LongCount(); n++)
{
if (smin[n] < min)
{
min = smin[n];
motion = n;
}
}
fractalMark.Add(motion);
fractalMark.Add(rotaNo[motion]);
fractalMark.Add(oNo[motion]);
fractalMark.Add(sNo[motion]);
smin.Clear();
oNo.Clear();
sNo.Clear();
rotaNo.Clear();
fval++;
}
///
StreamWriter sfile = new StreamWriter(@"F:/VirtualStudioData/ImageProcessing01/fractalCode.txt", true);
double block = 0;
double rotate = 0;
double oValue = 0;
double sValue = 0;
int index = 4;
for (int i = 0; i < RangePool.LongCount(); i++)
{
block = fractalMark[i * index];
rotate = fractalMark[i * index + 1];
oValue = fractalMark[i * index + 2];
sValue = fractalMark[i * index + 3];
sfile.Write(block + "," + rotate + "," + oValue + "," + sValue + ";");
}
sfile.Flush();
sfile.Close();
fthread.Abort();
fractalTimer.Stop();
}
3. 解码：
private Bitmap FractalDecode(Bitmap Image)
{
List<Bitmap> DomainPool;
List<Bitmap> RangePool = new List<Bitmap>();
fractalImop.getDomainPool(Image, out DomainPool);
//打开压缩文档
FileStream file = new FileStream(FrafileName, FileMode.Open, FileAccess.Read);
StreamReader sfile = new StreamReader(file);
string decode = sfile.ReadToEnd();
string[] fdecode = decode.Split(';');
for (int j = 0; j < fdecode.Length - 1; j++)
{
string[] sdecode = fdecode[j].Split(',');
Bitmap D = DomainPool[int.Parse(sdecode[0])];
Bitmap rotateD;
switch (int.Parse(sdecode[1]))
{
case 1:
rotateD = fractalImop.rotateOne(D);
break;
case 2:
rotateD = fractalImop.rotateTwo(D);
break;
case 3:
rotateD = fractalImop.rotateThree(D);
break;
case 4:
rotateD = fractalImop.rotateFour(D);
break;
case 5:
rotateD = fractalImop.rotateFive(D);
break;
case 6:
rotateD = fractalImop.rotateSix(D);
break;
case 7:
rotateD = fractalImop.rotateSeven(D);
break;
default:
rotateD = D;
break;
}
Bitmap terminalD = fractalImop.getAddOSImg(rotateD, double.Parse(sdecode[2]), double.Parse(sdecode[3]));
RangePool.Add(terminalD);
}
int blockSize = 4;
//解码图，长宽有多少块
int Dwidth = Image.Width / blockSize;
int Dheight = Image.Height / blockSize;
//解码图，解码到第几块
int toBlockNumb = 0;
//解码图，解到X轴第几个Pixel
int toXPixelNumb = 0;
//解码图，解到Y轴第几个Pixel
int toYPixelNumb = 0;
Bitmap DecodeImage = new Bitmap(Image.Width, Image.Height, PixelFormat.Format24bppRgb);
Bitmap RangBlock;
for (int y = 0; y < Dheight; y++)
{
for (int x = 0; x < Dwidth; x++)
{
int index = x + toBlockNumb;
RangBlock = RangePool[index];
for (int y1 = 0; y1 < blockSize; y1++)
{
for (int x1 = 0; x1 < blockSize; x1++)
{
int xindex = x1 + toXPixelNumb;
int yindex = y1 + toYPixelNumb;
DecodeImage.SetPixel(xindex, yindex, RangBlock.GetPixel(x1, y1));
}
}
toXPixelNumb += blockSize;
}
toYPixelNumb += blockSize;
toXPixelNumb = 0;
toBlockNumb += Dwidth;
}
return DecodeImage;
}
仅为个人理解，如有不足，请指教。 英俊强健的博客_博客-机器学习,图像处理,编程语言领域博主
全部评论 (0)
还没有任何评论哟~