浏览量:5,842

八叉树颜色量化

本文简单的介绍了颜色量化的几种方法,重点介绍八叉树颜色量化算法,并实现了该算法。算法实现的下载地址(参见下载)。

一. 颜色量化介绍(Color Quantization

计算机图形学中,常采用的一种方法是把颜色看成是基于红、绿、蓝三种颜色的混合,也可以采用色度、彩度、亮度等描述颜色,用多种不同的描述符来表示颜色,就称为颜色模型(Color Model),如果有人能量化这三种不同的描述符的数值,就可以用一个三元组来表示一种颜色,例如(r,g,b),这就形成了一个描述颜色的三维坐标系统,选择不同的颜色模型能形成不同坐标系统,坐标系统上所有颜色的集合就称为颜色空间(Color Spaces)。 在图形学中,颜色量化是为了减少一张图像中的颜色数并且使用它尽可能的与原始图像一样,在一些由于内存限制只能显示有限颜色的设备上,颜色量化就显得特别的重要,根据参考【5】的总结,介绍几种颜色量化方法,最后重点介绍八叉树颜色量化方法。

1.1   统一颜色量化(Uniform Quantization

在RGB颜色模型,颜色可以表示成三维空间中的一个坐标,颜色空间可以表示为X,Y,Z轴都在[0,1]范围的值,这样颜色空间就相当于一个正方体。统一颜色量化的基本思想就是独立的看待颜色空间中的每个坐标轴,把它们平均分成N条线段,这样就能形成一个个小方块,每个方块当作一种颜色。有时候把红和绿的坐标轴分成8段,把蓝色的坐标轴分成4段,这样就可以生成256个小方块,即256种颜色;除此之外,当然还有别的划分方法,例如可以把红色和蓝色分成6段,绿色分成7段,这样就能产生252种颜色。每个方块内的颜色值,可以取该方块所有颜色值的平均值。这种方法实现非常的简单快速,但是产生的结果并不好。

1.2   流行色算法(Popularity Algorithm

通过某种颜色在图像中发生的频率来进行颜色量化,频率越高的赋予越大的优先级,这种方法不考虑常用的颜色之间是否是相似的,即可能频率较高的几种颜色很相近,但是确实又有不同的颜色坐标。流行色算法基本的做法通过两次扫描来处理:第一次扫描图像,创建一个包括颜色和颜色计数的表,以颜色计数从大到小排序,选择前K种颜色作为这张图像的调色板,别的颜色都丢弃掉;第二次扫描,需要计算图像上的颜色在调色板上的索引值,例如颜色(red,green,blue),通过计算它与调色板上所有颜色距离的平方值dist,找到dist值取最小时的索引i值,就是图像上该种颜色的索引值。

dist=(red - red [i])^2 + (green - green [i])^2 + (blue - blue [i])^2

1.3   中值切割法(Median Cut Algorithm

与统一颜色量化方法有些相似,也是把颜色空间分成K个子块,使得每个了块尽可能的估计出相同数量的颜色。为了简化说明,这里用二维的平面来解释这个过程,如下图所示。原始图像上的颜色值放到颜色坐标系统上,沿着它最长的维度的中位数位置分成两半,剩下的子块按照类似的方法进行处理,得到右边那张图所示的结果。注意:中位数跟中点不是相同的概念。 2013-11-21 19-18-41

图1. 中值切割

算法的基本过程如下所示:

(1)       找到包含所有图像颜色的最小方块

(2)       把密闭在小方块内的颜色,沿着方块最长坐标轴方向进行排序,例如有4种颜色(0,0,0),(1,0,0),(0.2,0.4,0.5),(0.6,0.4,0.7)确定一个密闭的小方块,该方块在x轴方向的长度是1,Y轴和Z轴方的长度分别是0.4,0.7,所以沿着X轴方向进行排序。

(3)       取出中位数,把方块划分成两半

(4)       重复2~3过程,直到颜色被划分成256个区域

 二. 八叉树颜色量化(Octree

最后介绍八叉树颜色量化方法,该算法最早见于文章最早是在1988, M. Gervautz 和 W. Purgathofer 发表的论文《A Simple Method for Color Quantization: Octree Quantization》,算法的最大优点是效率高,占用内存少(仅需要不超过(颜色数量+1)个节点,加上一些中间节点所占用的内存),选出的调色板最合理,显示效果最好。         

代码实现参考了【3】作者写的代码,对他的代码进行了简单的修改和封装。网上有很多八叉树进行颜色量化的理论介绍,参考【1】,【3】,【4】,接下来,结合具体的代码实现,来解释下算法的基本思想。         

实现中采用的八叉树节点,设计成如下结构:

typedef struct  _OctreeNode
{
	bool			blIsLeaf;					// TRUE if node has no children
	unsigned char	inColorIndex;						// Index of the pallette
	unsigned int	uiPixelCount;						// Number of pixels represented by this leaf
	unsigned int	uiRedSum;						// Sum of red components
	unsigned int	uiGreenSum;						// Sum of green components
	unsigned int	uiBlueSum;						// Sum of blue components
	_OctreeNode*	ptrChild[8];						// Pointers to child nodes
	_OctreeNode*	ptrNext;						// Pointer to next reducible node
}OctreeNode;

算法过程的伪码如下所示:

void  buildOctree(array,numArray,maxColors)
{
      //把图像的像素保存在数组array中,大小是numArray
      for( color=array[i] ; i<numArray ; i++ )
      {
			addColor( color );      //往八叉树中加入一个颜色
			while(leafNum> maxColors)    //如果八叉树叶节点数超过最大允许的颜色数,合并八叉树,以减小叶节点数
				reduceTree();
      }
}

当往八叉树中增加一个新的结点的时候,调用addColor()方法,该方法的实现代码如下所示:

bool addColor(OctreeNode*& ptrTreeNode,unsigned char byRed,unsigned char byGreen,unsigned char byBlue,int inLevel)
{
	int nIndex, shift;
	static unsigned char mask[8] = { 0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01 };
	// 结点不存在,创建一个新的结点
	if (ptrTreeNode== NULL)
		ptrTreeNode = createNode (inLevel);
	if( ptrTreeNode==NULL )
		return false;

	//如果是叶结点,更新颜色信息
	if (ptrTreeNode->blIsLeaf) 
	{
		ptrTreeNode->uiPixelCount++;
		ptrTreeNode->uiRedSum += byRed;
		ptrTreeNode->uiGreenSum += byGreen;
		ptrTreeNode->uiBlueSum += byBlue;

		if(ptrTreeNode->uiPixelCount > m_inMaxPixelCount)
			m_inMaxPixelCount = ptrTreeNode->uiPixelCount;
	}
	//如果不是叶结点,递归下一层
	else 
	{
		shift = 7 - inLevel;
		nIndex = (((byRed & mask[inLevel]) >> shift) << 2) |
			(((byGreen & mask[inLevel]) >> shift) << 1) |
			((byBlue & mask[inLevel]) >> shift);
		if( !addColor (ptrTreeNode->ptrChild[nIndex], byRed, byGreen,byBlue,inLevel + 1) )
			return false;
	}
	return true;
}

这里参考【4】中的图片,来演示下这个方法的基本思想。当插入颜色值(109,204,170)的时候,插入第0层,取R、G、B颜色值的最高位,通过或操作,得到一个小于8的值3(011),作为下一次递归的位置;进入第2层,继续进行或操作,得到值6(110),第6个孩子节点就是下一层要递归的位置。依次类推,直到找到叶子节点,把颜色计算值uiPixelCount加1,同时把(109,204,170)加到OctreeNode结构(uiRedSum ,uiGreenSum,uiBlueSum)中。下图简化了过程,只演示了几层,在实现的算法中每种颜色分量占8位,所有共有9层。

2013-11-21 19-19-01

图2. 往八叉树插入颜色

如果叶节点的数量超过了允许的最大颜色数,则需要进行合并操作,以减少叶节点数,如下所示:

void reduceTree ()
{
	int i;
	OctreeNode* pNode;
	unsigned int nRedSum = 0, nGreenSum = 0 , nBlueSum = 0;
	int nChildren = 0;

	// Find the deepest level containing at least one reducible node
	for ( i=7 ; (i>0) && (m_ptrReducibleNodes[i] == NULL); i--);

	// Reduce the node most recently added to the list at level i
	pNode = m_ptrReducibleNodes[i];
	m_ptrReducibleNodes[i] = pNode->ptrNext;

	for (i=0; i<8; i++) 
	{
		if (pNode->ptrChild[i] != NULL) 
		{
			nRedSum				+= pNode->ptrChild[i]->uiRedSum;
			nGreenSum			+= pNode->ptrChild[i]->uiGreenSum;
			nBlueSum			+= pNode->ptrChild[i]->uiBlueSum;
			pNode->uiPixelCount += pNode->ptrChild[i]->uiPixelCount;

			free(pNode->ptrChild[i]);
			pNode->ptrChild[i] = NULL;
			nChildren++;
		}
	}
	pNode->blIsLeaf = true;
	pNode->uiRedSum	= nRedSum;
	pNode->uiGreenSum = nGreenSum;
	pNode->uiBlueSum = nBlueSum;

	//更新节点的最大像素数量。
	if(pNode->uiPixelCount > m_inMaxPixelCount)
		m_inMaxPixelCount = pNode->uiPixelCount;

	//更新叶节点数
	m_inLeafCount -= (nChildren - 1);
}

合并的基本思想,用参考【4】中的图片演示,在第n层的节点上有两个叶节点,现在完成的合并操作就是把叶节点的颜色分量和计数值都加到它们的父节点上,同时裁剪掉两个叶节点,这步操作就减少了一个叶节点。

2013-11-21 19-19-11

图3. 合并八叉树

程序中有一个设计技巧,就是一层的所有节点都用一个链表存储起来,m_ptrReducibleNodes[i]记录了链表的头节点,每一次合并操作都是从最底层开始,从下到上依次进行的。

三. 参考

【1】       http://en.m.wikipedia.org/wiki/Color_quantization

【2】       http://web.cs.wpi.edu/~matt/courses/cs563/talks/color_quant/CQindex.html

【3】       http://www.cnblogs.com/hoodlum1980/archive/2010/10/27/1862955.html

【4】       http://www.microsoft.com/msj/archive/S3F1.aspx

【5】       Hill, F. S. Jr. 《Computer Graphics Using OpenGL, Second Edition》

 

下载地址

spacer

3 comments on “八叉树颜色量化

  1. Anonymous

    感谢您的分享,写的很透彻,已经成功移植成java代码

  2. happyfire

    八叉树reduce的时候,是reduce了最后创建的节点,但是这个不一定是像素最小的节点,速度是优化了,但是效果可能要打个折扣吧

  3. Pingback: 浅谈GIF的编解码和在Android上的实现 | succlz123

Leave a reply