第" *卷第((期年月小型微型计算机系统
A " *h 59((@52
一种基于颜色聚类特征的色彩量化算法
周
(西安交通大学
兵(沈钧毅" 彭勤科" --系统所-陕西西安) (##H I ,
’
电子与信息工程学院软件所-陕西西安) (##H I ,
" 西安交通大学
’
摘
要! 色彩量化是数字图像处理中的基本技术之一-因此得到广泛的研究与应用9提出了一种基于颜色聚类特征的
色彩量化方法9该算法采用分层聚类技术-具有简单易行-运行速度快-色彩量化质量高等特点-是一种较好的色彩量化方法9
关键词! 色彩量化; 聚类特征; 八叉树; 图像处理
中图分类号! J 文献标识码! $I (K L
文章编号! (###%(" " #’" ##H , ((%(I I +%#H
M NM O P Q R S T U V W X Y Z [QN\Q O Q R \O ]Y T Z R ^Z X T ]R Z _Q R \Q O Q R ‘]X N T S a X T S Q N
-g %-%b c d e f 1@G c . h i 6@=1K . h j k 1@E ?
(
’-" }#-" }#(##H I -, l m n o o p o qr o s t u v w x y z {|z q o x s y v }o z~z ! }z w w x }z ! y z $}y o v o z !%z }&w x ’}v (y z ) r n }z y
"
’-" }#-" }#-) (##H I -r , |z ’v }v u v w o ql (’v w s ~z ! }z w w x }z ! y z $}y o v o z !%z }&w x ’}v (y z n }z y
! 9. 9M ) Y T R X *T +525, D 60@B 130B 15@1>0@1/F 5, B 0@B B ? :4@525G =5-1/0G ? F , 5:? >>1@G B 40>7? ? @>B 6C =/12C 2=1@025B 5--1? 2C >9J J 41>F0F ? , F , 5F 5>? >0@02G 5, 1B 4/70>? C5@:525, :26>B ? ,-? 0B 6, ? -5, :525, D 60@B 130B 15@41>02G 5, 1B 4/1>0E1@C5-9d 641? , 0, :41:02:26>B ? , 1@G/? B 45C , ? A F ? , 1/? @B >45/>B 40B B 41>02G 5, 1B 4/40>, 0B 4? , G 55C F ? , -5, /0@:? /1B 441G 4>F ? ? C 90@C25/:5/F 2? A 1B =
! ; :; 5; 10Z 12Q R [Y :525, D 60@B 130B 15@26>B ? , -? 0B 6, ? :B , ? ? /0G ? F , 5:? >>
3引
言
量化方法9
随着计算机技术的不断发展-图像信号起着越来越重要的作用-许多信息均可通过图像方式进行存储和传送9由于存储空间和信道容量的限制-图像信息必须经过压缩或量化处对一幅" 其颜色总理后再进行存储或传递9H 位的彩色图像-+++
数可以达到(而实际上-这些颜色有些并&" 5" 5" , 94种’未使用-有些可以用相近的颜色代替9所以压缩彩色图像的一个重要手段是减少颜色的冗余信息9这可以使用色彩量化技术9
色彩量化是数字图像处理中的基本技术之一-它的任务就是从自然界中色彩斑斓的原始图像中-根据图像处理的偏重需要-结合人眼的视觉特性-选择最优的6种颜色-作为调色板组合-使得根据这种调色板所得到的重建图像失真度最小9色彩量化的过程有两步-第一步是选择合适的调色板-第二步是用调色板中的颜色代替像素的原来颜色-得到重建图像9而其中的第一步是决定重建图像质量的关键9
色彩量化需要综合考虑最小失真问题7算法的复杂程度问题和人类视觉特性问题-所以还没有一个十分令人满意的算法9本文提出了一种基于颜色聚类特征的色彩量化算法9理论分析和试验表明该算法具有简单易行7所需存储空间少7执行时间短和图像显示质量好的特点-是一种有效的彩色图像
8相关工作
(:
目前常用的一些色彩量化方法有! 统一量化法9频度序7" :$:H :*:
列法9中位切割法9中值裂分法9八叉树法9和聚类777&:
我们对它们进行一下简单的介绍9法99
893统一量化法
是直接对色彩空间进行划分-挑选一组红7蓝7绿颜色分然后将各像素按照颜色量分布均匀的色彩表为调色板颜色-最相近的原则-用调色板中的颜色代替9最简单的表示方法首先分离; 使之在每一维上分成相等的片-用是! j f 空间-每个原色色彩层的相交体-产生多种基本原色的代表色-这样例如在6为" 考可选出一组用途广泛的颜色9*&的情况下-虑到人眼对不同颜色的敏感度-将颜色空间中的红色和绿色分量各分$个位面-蓝色分量分" 个位面-这样红色+种7绿
蓝色H 种-可组合得到+采用色+种7
这种统一量化方法-一幅图像选择颜色值时-是通过舍入某些这种方法使用颜色固定的调色板-而不成分而得到近似表示9
所以要求调色板中的有限色彩是根据图像内容选择调色板-但由于一幅真实的图片并不是包与要显示图像的色彩无关9
含均匀分布的所有色彩-这样-统一量化尽管方法简单7速度但实际图像中微妙变化的层次感不能描述9快-
收稿日期! 国家自然科学基金项目’资助作者简介! 周兵-博士研究生-研究方向为为数据挖掘-基于" ##$%#$%" &基金项目! &#() $#*+,
内容的图像检索系统等沈钧毅教授博士生导师研究方向为数据库系统与数据挖掘%! (&$(8(&$9----%! 8/09. /01234567:5/; . /0124? @12万方数据-教授-研究方向为集群并行计算与集群服务-99; 彭勤科-%! 8A 999A
H H 期
周
一种基于颜色聚类特征的色彩量化算法兵等%
H b b b
! " ! 频度序列法
是以图像色彩直方图为基础" 首先选择图像中使用频率最高的#种色彩作为调色板$然后再把其余颜色按最小距离准则映射到调色板中" 该方法的特点是根据不同的图像选择不同的调色板$因此重建图像显示效果有较大改善" 但该方法时空开销大$且常会出现一幅图像某些色彩由于出现频率小而被丢失的现象$使图像显示失真$效果不够理想" 例如一幅图像是绿色草原中的一朵小红花$那么红色可能会由于像素点太少而被丢弃$导致小红花的红色着色不正确"
中位切割法简称中分法" 该方法试图选择一个色彩均衡的集合来表示图像" 其基本思想是%把色彩空间正方体分成分类$直到合理为止" 动态聚类法有#均值算法(+, -. /0算
法(事实上$上述1-234算法以及颜色选择的563算法等" 的聚类方法均为迭代算法$处理较费时$对初始聚类中心的选择也各法不一$效果不够理想" 例如#均值算法对色彩压缩不均衡及色彩失真度较大&而+, -. /0算法入口参数太多且难于确定$其计算也非常繁琐" 为了克服上述算法的不足之处$本文提出一个使用分层聚类技术的彩色图像量化方法" 对比试验表明$该算法简单易行$运行速度快$色彩量化质量高"
’算法介绍
9:;
我们的算法参考了6+278聚类算法中的聚类特征和#个包含相等数量像素的长方体$选择每个长方体的中心作为调色板" 具体做法是%每次将长方体外围不包含像素的无用部分切除$并沿其最长边做中位切割$即在此边上所有值的有序表里取中值做切割$使原来一个长方体变成两个包含等量像素的小长方体" 如此重复进行$直到色彩空间被分成#个包含大致相同像素的长方体为止" 每个长方体的中心就是一个调色板颜色" 在立方体的点密集区域$将有更多的长方体$从而相应的有更多的调色板颜色处于其中&而点稀少的地方$调色板颜色也稀少" 没有哪种颜色会被忽略$但出现更频繁的颜色将得到优先处理" 这种算法考虑到具体图像的色彩分布$所得到的图像的层次感较丰富$但局部细节却较模糊$效果仍不够理想"
! " ’中值裂分法
同中位切割法类似$也是一种分裂法" 但它是在像素集合中$选取红(绿(蓝分量中方差最大的那个分量的中值作为裂分标准$不断地把颜色空间裂分成越来越小的区域$直至最终得到#个集合$各集合中心点的颜色即为调色板的色彩" 由于该算法采用最大方差准则作为裂分标准$故所得到的调色板既能最大程度地反映图像色彩的使用频率$又能保证图像中使用较少却非常特殊的色彩不被丢失$是一种较好的量化方法" 但该算法计算复杂程度较高$时空开销大$不便于图像的实时处理"
! " ) 八叉树量化方法
顺序读入图像文件中的像素$并以先被读入的前#种不同色彩作为初值" 一旦不同颜色的数量超过#时$则将出现频率最小的颜色同相近的颜色归并$以保证色彩数目不超过#"
在这种方法中$借助于八叉树实现代表色彩选择$每当处理源图像文件中的一个新色彩时$若其颜色数目小于#$就在色彩八叉树上插入一个新叶子结点" 若颜色数超过#$则在八叉树上进行相邻色彩归并运算$以减少叶子结点数目$保证其叶子结点数目不超过#" 该算法在选择合并颜色时$以像素频度为准$所以仍会出现某些色彩由于出现频率小而被丢失的现象$使图像显示失真"
! " *聚类方法
大致可分为两类%系统聚类法和动态聚类法" 前者是先选择若干个样本$然后按准则函数逐步聚合$类别由多到少$直到合适的分类为止万方数据&后者则是先选择若干样本点向各个聚类中心聚合$从而得到新的分类$若新的分类不合理$则修改此
聚类特征树的概念" 下面我们先简单介绍这两个概念"
’"
聚类特征71=>? $@B A $, , C $是一个三元组$其中? 是点EF
的个数&@B A
=D J 是它反应了这簇点的G =H I G $? 个点的线性和$F
重心&, ,
=D J =H
I G K
$, , 是? 个点的平方和它反应了这簇点的G $直径大小$, , 越小$这簇点聚得越紧" 聚类特征总结了一簇个体的有关信息$从而使得一簇点的表示可以总结为对应的一个聚类特征$而没必要再用具体的这一组点来表示" 这样$聚类特征既能正确(有效(充分地表示一簇数据点$又能节省大量空间"
聚类特征树71L 0M N N 是一个类似6
O 树的多叉平衡树" 其非叶节点有6个子项$子项的格式是%971P $7Q P R S P ; $P =HT 6&7Q P R S P 是指向第P 个子节点的指针$71P 总结了第P 个子节点所代表的子树的聚类特征" 叶节点有5个子项$子项的格式是%971P ; $P =HT 5" 每个叶节点的子项代表一个聚类" 6+278算法要求所有节点的大小等于页面大小U V 如H W K X 字节Y " 那么当数据空间的维数确定后$节点的子项的大小就可以知道$那么6和5就可以确定" 所以可以通过调节U 的大小$改变6和5的大小" ’" ! 量化算法
6+278算法用于处理多维空间数据的聚类$而像素的颜色可以看作红绿蓝三维空间的一个点" 所以完全可以用聚类
图H 色彩聚类特征树的构造过程1P Z " H 6[P R S P \Z]M ^_N S [M N ^‘_^R ^M 71L a M N N
特征来表示颜色的聚类$则称其为色彩聚类特征V 7^R ^M 71
Y $
/d d d
小型微型计算机系统
/d d Q 年
那么相应的称聚类特征树为色彩聚类特征树! ’" #$#%"&*+(%) )
用色彩聚类特征树实现色彩量化的过程就是构造一棵色彩聚类特征树的过程, 并且使所有叶节点的子项个数等于-+方法是选取最先读入的-种不同颜色作为初始聚类, 以后读入的颜色按照距离最近, 即颜色差别最小原则, 同合适的叶节点子项合并, 直到处理完所有像素+最后用各个子项的质心作为调色板的代表色+
构造色彩聚类特征树的过程如图. 所示+
定-为/对算法的运行时间和重构图像质量做了测O P 和P Q ,
定+我们用图像失真度来反映图像质量的好坏+失真度定义如其中H 2下?
S. T V
向量和新颜色向量+我们的算法用Y 运Z [Z 和" 语言实现+行环境是一台个人电脑, 内存O Q. +^. /" N \是]:3) $N _, ‘+
用于测试的原图和结果如图L 所示?
表. /O P 色时的算法性能/O P ; (6a $) . b 96$23c#5#$#%
我们的算法
O P -S/运行时间! 0失真度
/d ! *,N S . a c 3)
F S Q . f /.
S/. P , N F S e . f . f
O P d , N S . Q F S P /P . f
/. /L T
图/0函数451$23637) %+/&
如下? 函数0! , *45637) %5637) %:) =" 72$>1$23
一个叶节点可以有@个颜色聚类, 所以总共有A 个E B C D 叶节点+那么色彩聚类特征树的高度为$从根E G. +F A #8B C D 向下找到最近的叶节点子项要经过$E G. 个节点, F A B C D #8每个节点要进行F 次比较, 以找到距离最近的子项, 所以总共的时间代价是H ! 其中I 为像J! $E G. **, F A I J F #8B C D 素总数+
S. /d , SQ N F S/. P , Se N F
K 效果分析
为了验证该算法的效果作者做了如下试验+首先测试了
八叉树S. O P d , SP Q N F
由以上测试结果可以看出, 随着N 的增大, 算法的运算时间也增大, 但量化效果也同时提高+这在P Q 色时表现较为明显+这是因为N 增大后, 相应的一个节点中的比F 也增大, 较次数就多, 但搜索精度也相应提高, 所以量化质量要好一些+
表/P Q 色时的算法性能P Q ; (6a $) /b 96$23c#5#$#%
我们的算法
Q -SP
/d ! *,N S . a c 3)
F S Q
运行时间! 0失真度
. O L d
S/. P , N F S e . O /Q
O P d , N S . Q F S P Q O /.
. ^L O 图L 原始图像+L H %&2828%:6$2M 68)
算法对参数页面大小N 的敏感性, 即N 的大小对算法性能? , 万方数据
的影响+其次把八叉树量化法同本的算法进行了对比测试+设
同八叉树法对比可以看出, 算法在运行时间和失真度方
’’期
周
一种基于颜色聚类特征的色彩量化算法兵等.
() ) ’
面要略胜一筹! 八叉树法在合并颜色时" 要选择像素频率最小的颜色" 这会导致较长的运算时间" 同时会使一些像素少但重要的颜色丢失! 在#可以明显看出脸部的粉红色消失$色时" 了! 而我们的算法则较好的保留了这些色彩细节!
像中丰富的色彩层次感" 则会失去图像中的某些关键细节" 如绿色草原中一朵红花的红色点着色不正! 反之" 若要使重建图像的各种细节保留完整" 则必会失去图像整体色彩的层次感! 例如中国的水墨画不但黑色层次丰富" 而且还有细微的色调变化! 又如某些图像的平滑部分/如人的脸部0粗糙的量化会" 造成明显的伪轮廓1而对于图像的边缘部分" 由于人眼的视觉特性" 对该部分的敏感程度较低" 所以对该区域进行精细的量化反而会造成调色板项的浪费! 因此" 如何使得重建图像具有丰富的色彩层次感" 而细节失真度又最小" 以及如何根据人眼的视觉特性对图像的各个区域进行适当的量化等问题" 迄今未有好的解决方法! 我们下一步的工作将力图解决这一问题! %&’() " *&$%&(’#" *
&+%&’, #) " *
&#$八叉树
-结
论
本文首先分析和讨论了现有的几种常用的色彩量化方法" 并指出了它们的优缺点" 然后提出了一种采用分层聚类技术的" 基于颜色聚类特征的色彩量化方法! 最后的试验表明该算法简单易行" 运行速度快" 色彩量化质量高" 是一种较好的色彩量化方法!
在目前的色彩量化算法中有一个矛盾. 若要保留重建图
万方数据
2343536738
. ’9:; ? %! @A B A >C D E F :G H E I ? C J E ? C A IK A >K >E D :=H K K :>:LL C M N B E O
P Q R ! @A D N H ? :>S >E N T C ; M
"’U +("’#/(0. (U V W X ) V ! (S :I FS H A W T H E " Y T A HZC I F W G H E I ! [I E B O J C I F? T :GH E B C ? OA K M A D :; A D D A IH M :LE B F A >C ? T D MA K; A B A >GH E I ? C J E ? C A I P Q R ! ZC I C W ZC ; >A \O M ? :D M " ’U U +" ’U /U 0. $#W $U ! X
[I L >:E L " *>A ]I :Z ! [! ^D E F :N C _:B ; B E M M C K C ; E ? C A I =O ; T >A D E ? C ; C ? OE I E B O M C M P Q R ! %E ? ? :>I‘:; A F I C ? C A Ia :? ? :>M !’U U ) " /’’0. , (W , +!
$b >; T E >LZ c " *A H D E I@[! @A B A >GH E I ? C J E ? C A IA K C D E F :P Q
R ! ^d d dc >E I M \C F I E B %>A ; :M M C I F " ’U U ’"X U /’(0. (#V V W (#U ) ! , S :>>E H ? J Z " %H >F E ? T A K :>e ! [M C D N B :D :? T A L K A >; A B A >
G H E I ? C J E ? C A I . A ; ? >::G H E I ? C J E ? C A I P @R ! %>A ; ::L C I F M A K @S ^I ? :>I E ? C A I E B
f ++"(’U W (X ) ! #a C I Fa C I F ! ‘:M :E >; TA I; A B A >CD E F :GH E I ? C J E ? C A ID :? T A L :M P Q R ! Q A H >I E B A K \A H ? T@T C I E g I C h :>M C ? O A K c :; T I A B A F O /i E ? H >E B \; C :I ; :d L C ? C A I
0" () ) ) " (+/’0. +’W +, ! 附中文参考文献.
(耿国华" 周明全! 常用色彩量化算法的性能分析P Q R ! 小型微型计算机系统" ’U U +" ’U /U 0. $#W $U !
#凌玲! 彩色图象量化方法的研究P Q R ! 华南理工大学学报/自然科学版0" () ) ) " (+/’0.+’W +, !
一种基于颜色聚类特征的色彩量化算法
作者：作者单位：刊名：英文刊名：年，卷(期)：被引用次数：
周兵， 沈钧毅， 彭勤科
周兵(西安交通大学,电子与信息工程学院,软件所,陕西,西安,710049)， 沈钧毅,彭勤科(西安交通大学,系统所,陕西,西安,710049)小型微型计算机系统MINI-MICRO SYSTEMS2004,25(11)12次
1. Heckbert P Color image quantization for frame buffered display 1982(02)
2. Geng Guo-hua;Zhou Ming-quan Analyzing the quality of some common used algorithms of colorquantization 1998(09)
3. Andread;Browne M. A Image pixel classification by chromaticity analysis 1990(11)4. Orchard M T;Bouman C A Color quantization of image[外文期刊] 1991(12)
5. Gerrautz M;Purgathofer W A simple method for color quantization:octree quantization6. Ling Ling Research on color image quantization methodes 2000(01)7. 耿国华;周明全 常用色彩量化算法的性能分析 1998(09)
8. 凌玲 彩色图象量化方法的研究[期刊论文]-华南理工大学学报(自然科学报) 2000(01)
1. 李志学. 芦伟. Li Zhixue. Lu Wei 油田生产成本项目的聚类特征及其动因研究[期刊论文]-国际石油经济2009,17(4)
2. 奚浩波. 曹理宇. Xi Haobo. Cao Liyu 色彩量化算法的研究与评价标准[期刊论文]-山西科技2007(5)3. 王传玺. WANG Chuan-Xi 色彩失真现象浅析[期刊论文]-印刷世界2007(10)
4. 陈立亭. 邓中民. 徐造坤. CHEN Li-ting. DENG Zhong-min. XU Zhao-kun 颜色量化在提花织物CAD中的应用[期刊论文]-武汉科技学院学报2006,19(2)
5. 鲁力. 颜钢锋 基于色彩量化的自动配色新算法及其应用[期刊论文]-计算机工程与应用2003,39(20)
6. 张鑫. 王晖. 曹源. 吴玲达. ZHANG Xin. WANG Hui. CAO Yuan. WU Ling-da 一种用于色彩量化的调色板快速搜索算法[期刊论文]-计算机应用2006,26(11)
7. 徐峻岭. 徐宝文. 张卫丰. 崔自峰. Xu Junling. Xu Baowen. Zhang Weifeng. Cui Zifeng 一种启发式聚类特征选择方法[期刊论文]-东南大学学报(英文版)2006,22(2)
8. 陈卫东. 张强. 杨丽. CHEN Wei-dong. ZHANG Qiang. YANG Li 一种改进的快速中位切割彩色图像量化算法[期刊论文]-计算机工程与应用2007,43(33)
9. 王迎化. 李云波. WANG Ying-hua. LI Yun-bo 中国企业500强基于网站的客户关系管理聚类特征研究[期刊论文]-华东经济管理2007,21(6)
10. 刘妹琴. 程红梅. LIU Mei-jin. CHENG Hong-mei 基于扩展"变球法"的颜色量化分析[期刊论文]-工程设计学报2006,13(3)
1. 周鲜成. 申群太. 王俊年 基于微粒群的颜色量化算法[期刊论文]-微电子学与计算机 2008(3)
2. 王自立. 何通能 一种基于核的聚类色彩量化算法[期刊论文]-机电工程 2008(1)3. 柳峰 实时目标跟踪的分析研究与系统实现[学位论文]硕士 2005
4. 张庆海. 倪瑛 消防侦察机器人视觉系统的设计[期刊论文]-电视技术 2011(23)5. 廖娥媚. 胡建平 基于八叉树颜色量化的OpenGL实现[期刊论文]-信息技术 2010(5)
6. 王向阳. 胡峰丽. 刘春辉 一种基于图像内容的自适应色彩量化算法[期刊论文]-辽宁师范大学学报（自然科学版） 2007(3)
7. 黄元元. 刘宁钟 一种新的基于颜色特征的图像检索方法[期刊论文]-小型微型计算机系统 2012(3)8. 杨欣欣. 李声威. 周兵 基于颜色差异的色彩量化算法[期刊论文]-河南大学学报（自然科学版） 2011(2)9. 黄元元. 何云峰 一种基于颜色特征的图像检索方法[期刊论文]-中国图象图形学报 2006(12)10. 王东. 蒋炯辉. 周世生 基于局部矢量匹配的颜色特征快速传递算法[期刊论文]-信息与控制 2010(2)11. 黄元元. 刘宁钟 一种新的基于颜色特征的图像检索方法[期刊论文]-小型微型计算机系统 2012(3)
12. 胡子付 彩色图像的颜色归并与边界勾绘的计算机化研究——卫星图像目视解译半自动化问题[学位论文]硕士2006
引用本文格式：周兵. 沈钧毅. 彭勤科 一种基于颜色聚类特征的色彩量化算法[期刊论文]-小型微型计算机系统2004(11)