一种基于排序理论的精确直方图规定化算法

科技信息

。

博士・专家论坛

一神基孑排序理ｉ＾ｌ均精确直方图规定化算法

田

杨１・２陈辉１徐立艳１・２

（１．山东大学信息科学与工程学院２．通辽职业学院）

［摘要］本文提出了一种基于排序理论的精确直方图规定化的算法，该算法通过把离散情形的统计模型在一个Ｋ维空间里进行转化，在图像像素中诱导出一个严格排序，从而得到一个可逆的累计分布函数，并且给出了实验结果和诱导排序的统计模型．［关键词］像素

精确直方圈规定化严格排序

１．引言

在图像处理中，有时需要对一幅图像进行变换，使其具有希望的直方图形状，这时可以采用比较灵活的直方图规定化方法。即给定原始图像直方图和希望图像直方图，找一个灰度级映射关系得到所需直方图的最佳近似。在连续的情况下，规定化算法可以给出精确的结果，但在离散的情况下，规定化算法只能给出近似结果。对于直方图规定化的一般情况，映射作为原始图像的累积分布函数，它的导出问题很困难。

本文提出了一种基于排序理论的精确直方图规定化的算法，它扩展了我们以前在离散图像上关于严格排序的工作，并介绍了一个理论分析框架。

２．问题在离散情况下，累积分布函数是阶梯函数，因此，除了当像素取不同的值这种情况以外，它们是不可逆的。因为在一个图像中像素的数量通常要比灰度级的数量大很多，所以，不同的像素值是不相关的。随机变量Ｚ的累积分布函数确定了概率

尸｛Ｚ≤ｚ｝，因此它依赖于过去的排序关系。除非另有说明，如果一种新的排序关系，它在图像像素中诱导出了一个严格排

序，取代通常的捧序，一个离散精确直方图规定化问题就被解决了．

３．精确直方图规定化算法３．１原理

设厂是一个Ⅳ×Ｍ离散图像，灰度级总数为三，设日＝｛％，％，…，力¨）是被规定的直方图．注意到日是非归一化

图像的直方图，即岛是灰度级为，的像素个数。进一步假设在７ｆ。的像素中定义了一个序关系一＜，使得诱导序是严格的。这样，

精确直方图规定化简单如下进行［１３］。

１）图像像素排序：

／’（一，ｙ１）＿＜／（秘，坎）一＜…－＜厂（ｘＭ，ｙ删）

（１）

２）从左到右把（１）中的有序链分成三组，使得第，组有厅．个像素。

３）把第，组中的所有像素，分配给灰度级，。

上述的方案产生了精确结果，即，假如这样的直方图是有效的，图像被转换得到精确的希望的直方图。直方图的有效性可理解为

川∑枷

认Ｄ＝

Ⅳ

×

Ｍ

＠

规定一个直方图相当于规定一个确定的分布，这个分布的概率密度函数是精确地归一化的图像直方图。对于一个Ⅳ×＾彳

大小的图像，概率密度函数不能用比

Ｓ＝——

１

（３）

ＮＭ

更好的分辨率来规定了。

３．２排序及排序估计

如果可以诱导出一个图像像素的严格排序，那么离散精确直方图规定化问题就解决了。为了导出这样一个排序，要考虑像

素邻域。设Ｋ是一个取定的整数，形，ｆ＝１，．．．．，Ｋ是一族封闭的邻域使得

彬ｃ％ｃ…ｃ％

（４）对每个厂＠，ｙ），设朋，＠，ｙ）是在彬上灰度级厂的平均值。为了在边界上适合畋，假设图像是通过复制边界像素扩展而

来。设Ｍ＠，．ｙ）表示Ｋ元组（ｍｌ（ｘ，ｙ），ｍ２（ｘ，ｙ），…，ｍＫ（ｘ，ｙ）），且进一步认为Ｋ元组中的分量按字典排序方式定义序。按字典排序定义的序，在Ｋ元组的Ｍ＠，ｙ）的集合上导出一个完全排序。因为一个Ｋ元组和每一个像素已有联系，从而在彤元组集合和图像之间建立了对应・因此，同一个排序也能被扩展到离散图像。当Ｍ（■，Ｍ）＜Ｍ（％，儿）时，我们把它写成

万　

方数据一１一

科技信息

博士・专家论坛’

，Ｌ■，ｙ１Ｊ一＜，Ｌ％，ｙ２Ｊ・

总而言之，通过利用向量算子把一个向量和每个像素相联系，问题从标量图像转换到了Ｋ维空间，然后通过字典方式给向量排序，在图像像素间导出了相同的排序。

针对上面提到的排序关系，当一个像素的局部均值比另一像素的局部均值大的多的时候，结果它比另一个像素更亮。最初的灰度级的序被改进完善。我们的目的是得到一个严格排序，或者在一个较低限制的设置下，得到一个几乎处处严格排序，即在（１）中几乎没有等式。显然，诱导排序依赖于Ｋ和图像：原始的灰度级分布，灰度级的范围和图像的尺寸。我们将假设处理有足够灰度级和足够细节（或噪音）的自然图像。我们希望Ｋ‘取到一个适当的值。

３．３理论分析

为了量化上面给出的相当模糊的条件，即适当的尺寸和足够的灰度级，我们考虑简化的有量化高斯独立同分布（ＩＩＤ）像素的图像模型，估计Ｋ和仃的函数的等像素的概率。灰度级范围￡可以考虑为大约６盯．

设￡表示朋个像素的和之间的等式的概率，ｐｌ（ｚ）表示原始图像像素分布，设ｐ。（ｘ）表示聊个随机变量的和的概率

律。对聊＝１，像素厂（＿，Ｍ）和厂（ｘ２，ｙ２）有相同的灰度级的概率鼻是

鼻＝∑ｐｌ（ｆ）ｐｌ（ｆ）＝∑ｐ１２（ｆ）

（５）

只＝∑硝ｆ）２

（６）

其中概率律尸。（ｘ）是根据卷积来计算的

岛７＝ｐｌ・ｐｌ・…ｐｌ＝ｐｌ・ｐⅢ一ｌ

（７）

显然，鼻≥最≥只≥…≥只，。

设最是在¨邻域上相应像素和有等式的概率，尸（Ｋ）是作为Ｋ的函数的两个像素的等式的概率。仅作为乘积，马上得到ＪＰ（Ｋ）

尸（Ｋ）＝兀二．乞

（８）

需要说明的是，两像素间等式的概率尸（Ｋ）不但依赖于Ｋ，而且还依赖于像素位置。这是由于如果所考虑的两像素很接近，一些共同的像素能出现在概率最的计算中。这样，和等式的概率增加了。因此，对给定的Ｋ，尸（Ｋ）在下界和上界之

如果在气的计算中没有公共像素，则下界就得到了・在这种情形下，气２只，‘吃２吃２乞２吃２只，吃２忍。

如果像素沿对角线方向邻近，则上界也可以得到。这样，尼２鼻，冠，２５只，吃２只，幺２吃２吃２只。

ｎ（ｘ）＝亡ｅｘｐ

ｊ

一坠枣２∥

（９）

其中，ｘ＝０，ｌ，．．．，三一１且五≈１．概率ｐｔ，最，尸（尼）可以利用（７）（８）（９）直接计算。作为选择，它们可以通过考虑连对于两个独立高斯随机变量Ⅳ（％，吒）和Ⅳ（％，％），它们的和Ⅳ（历，盯）的分布也是高斯的，其中：朋＝％＋％，

仃２＝一十西。那么，如果ｐｌ＝Ⅳ（聊，盯），我们马上得到Ｂ＝Ⅳ（聊，，ｑ），其中，，吩＝ｆｍ，ｇ＝√ｆ盯，且１＜ｆ≤８。

尸的概率是ｒ

（Ｊ一，，，『）２、‘

（ｘ一％）２

鼻２刮南唧甫Ｊ－壶莩涮丽唧一前㈣，

因为最后的和式关系到一个分布Ⅳ（聊，，ｑ／２），我们有

’

莓赢唧２∽～２ｒ引

一．．．．．．．．———．．！，——一

（工一帕）２

＇

㈨，

一２一

万　

方数据

科技信息博士・专家论坛

￡２壶

表Ｉ

像素等值概率（类高斯分布）

下限

㈣，

进而，利用（８）式和上面讨论的气和Ｃ的关系，就可以计算出尸（Ｋ）的下界和上界・可以看出，上界大约是下界的二

倍，当Ｋ增加时，两个概率都变得很小。当Ｋ＝２，…，６的情形，列在表Ｉ中了。

Ｐ（露）

‘

一卜限

Ｐ（２）ＪＰ（３）

Ｐ（４）Ｐ（５）

５．６２盯一２１Ｏ一２９．１６盯－３１０．３１．２９盯－４１０－３１．８２盯－５１０－４２．５７仃“１０—５

表ＩＩ

３．９７仃一２１０—２５．６ｌ盯＿３１０＇３７．９ｌ仃－４１０—７．８９盯－ｓｌＯ一５１．１ｌ盯“１０—５

Ｐ（６）

盯

严格排序概率（类高斯分布）

Ｎ

２５６２５６２５６２５６２５６２５６２５６２５６２５６２５６

Ｂ掰６ｌｂ“６ｌｂⅣ６ｌｂⅣ６ｌｂ“６ｌｂ“６汤Ｈ６ｔｂｌ，６协“６强Ⅳ６ｌｂ

Ｐ（２）

０．０００００００．００００００‘Ｏ．０００００２Ｏ．０００００００．００３０１２０．０００２８５Ｏ．０３８８９４０．０１０１３３Ｏ．２３６２０９Ｏ．１２９９２７

Ｐ（３）

Ｏ。２３０９７ｌＯ．０９１３４４Ｏ．８３２６１９０．７４１４６２Ｏ．９４７１７ｌＯ．９１５１８３０．９７７３６３Ｏ．９６３２９９０．９９３２３９Ｏ．９８８９８２

Ｐ（４）

０．９５９５０４Ｏ．９３４７２２Ｏ．９９７４２０Ｏ．９９５７９００．９９９４９０Ｏ．９９９１６７Ｏ．９９９８３９０．９９９７３６０．９９９９６８Ｏ．９９９９４８

Ｐ（５）

Ｏ．９９９１７６Ｏ．９９８０９７Ｏ．９９９９７４Ｏ．９９９９４００．９９９９９７０．９９９９９２０．９９９９９９Ｏ．９９９９９８１．００００００１．００００００

Ｐ（６）

Ｏ．９９９９７７Ｏ．９９９９４６１．００００００Ｏ．９９９９９９１．ＯＯ００００１．００００００１．００００００１．００００００１．００００００１．００００００

５５

１０１０１５１５２０２０３０３０

５５

１０１０１５１５Ｚ０２０３０３０

５１２５１２５１２５１２５１２５１２５１２５１２５１２５１２

０．ＯＯＯＯＯＯＯ．００００００Ｏ．００００００Ｏ．００００００Ｏ．００００００Ｏ．００００００Ｏ．０００００２０．００００００Ｏ．００３０７８Ｏ．０００２８０

Ｏ．００２８１３Ｏ．００００６８０．４７９９１ｌ０．３０１５３４Ｏ．８０４５０６Ｏ，７０１０１９Ｏ．９１２３１６Ｏ．８６０８３０Ｏ．９７３１７６Ｏ．９５６５６９

０．８４７３１７０．７６２９５６Ｏ．９８９６９８Ｏ．９８３２３２０．９９７９５７Ｏ．９９６６６５０．９９９３５３０．９９８９４４Ｏ．９９９８７２０．９９９７９１

Ｏ．９９６７０ｌ０．９９２３９７Ｏ．９９９８９７０．９９９７６２Ｏ．９９９９８６０．９９９９６９Ｏ．９９９９９７０．９９９９９３１．００００００Ｏ．９９９９９９

Ｏ．９９９９０７０．９９９７８５Ｏ．９９９９９９Ｏ．９９９９９７１．００００００１．００００００１．Ｏ０００００１．００００００１．００００００１．００００００

，２、

对于一个Ⅳ×Ｍ图像有Ｒ

２

Ｉ＾ｒ＾，１个像素对・如果根据所提到的排序有两个相等像素的概率是Ｐ（Ｋ），则有两个不

＼ｏ¨¨／

同像素的概率是ｌ一尸（Ｋ）。从而，所有对都不同的概率是

尸≈（１一尸（Ｋ））月

（１３）

利用（１３）和表Ｉ，可以估计严格排序的概率的上界和下界。它们依赖于Ｋ的邻域的数量，图像的尺寸Ⅳ×＾彳，灰度

级范围￡，或者等价的盯．这样，概率随着Ｋ的增大而增大，随着Ⅳ×Ｍ和三（盯）的增加而减小。在表格Ⅱ中，列出了对于两种典型的图像尺寸（２５６×２５６，５１２×５１２），口∈【５，３０］，２≤Ｋ≤６的相应的结果。对于每种情形，通过考虑下界（脑）上界＠６），估计了Ｐ（Ｋ）的概率。结果精确到小数点后七位数字，误差小于５×１０～，这比ｓ小的多，即当Ⅳ＝Ｍ＝２５６时，是占＝１．５×ｌＯ．１。当Ⅳ＝Ｍ＝５１２时，占＝３．８ｘ１０＿６．

从表Ⅱ可得到几个结论，最重要的结果是：Ｋ取一个适当小的值，即Ｋ＝６，可以确保严格序。另外，只要Ｋ＞４，

Ｐ（Ｋ）的上界和下界的结果之间的差异是很小的。仃＝５时得到的结果并不很重要一一图像的灰度级范围应该足小于３０，

所以它是一个不好的灰度级分辨率。只要仃一增加，就可由高斯分布模型给出非常好的结果。

４．实验结果

统计分析表明，在Ｋ≥６时，可以达到严格排序。在实像上的排序估计也给出很好的结果．对于Ｋ＝６几乎严格排序被

万方数据　

一３一

科技信息

博士・专家论坛

诱导出。例如，对于２５６×２５６的莉娜像和Ｋ＝５的新排序，只有８对相等像素，对于Ｋ＝６的排序就是严格的。正如所预期的那样，对于同一个像，但是尺寸是５１２×５１２，在结果中稍有减少。对于Ｋ＝５，就有３５２对相等像素；当Ｋ＝６，相等像素减少到６对。到目前为止，在各种实验项目都得到十分相似的结果。在最差的情形，对于５１２×５１２像，发现了一对具有十像素对的不可分离的像素。与尺寸（２６２１４４像素）的像对比，这意味着几乎所有严格排序都得到了。

在实像中，像素的统计独立通常不令人满意。相反，像素是相互关联的，这提高了相等的概率。无论怎样，迄今为止根据得到的结果，对于Ｋ＝６所得到的排序适于一些应用。

。

和２６２１４４像素的图像相比，至多十个等像素对的量意味着一个

非常好的图像像素分离，并且如果像素对在序链中的区问限不同，那么在规定化结果上没有实际的影响。这样，提高Ｋ值的讨论毫无意义。

５．在图像增强方面的应用举例其中图１和图２为原始图像及其直方图，原始图像较暗且动态范围小；图３和图４分别是对原始图像进行均衡化处理的结果，可以看到处理后图像亮度值出现的频数趋于平衡，灰度的动态范围和对比度差都得到了增强；图５和图６为需要规定化处理的图像及其直方图；图７和图８是采用直方图规定化处理后的结果，可以看到规定化处理将原来较暗区域的一些细节得到增强而变得更加清晰了。

图ｌ原始图ｌ图２原始图１的直方图图３均衡处理结果图图４均衡处理后的直方图

图５原始图２６．结论

图６原始图２的直方图

图７规定化处理结果图图８规定化处理后的直方图

精确直方图作为一个不适定问题被解决了。我们的方法是基于在图像像素上定义的排序关系，它可诱导出几乎严格排序。严格排序的存在性在理论上和实验中的结果都给出来了。一旦得到这个排序，像素马上就被分类并且分配给一个期望的灰度级。所提到的严格排序和自然排序是一致的，这样，图像的信息内容基本上都被保留了。参考文献

【１】Ｒ．ｃ．Ｇｏｎｚａｌｅｓ等著，阮秋琦等译，数字图像处理．电子工业出版社，２００３．

【２】

＾．

ＲｏｓｅｎｆｅｌｄａｎｄＡ．

Ｋａｋ，

刀，占ｆｆ盘』．，Ｙｃｆ‘，，ｅ．Ｐ，口ｆｅｓＪ坞

ｏｎ

ＵｐｐｅｒＳａｄｄｌｅＲｉｖｅｒ。ｉｍａｇｅ８

ａｎｄ

ＮＪ：

Ｐｒｅｎｔｉｃｅ—Ｈａｌｌ。

１９８２．

【３】Ｄ．Ｃｏｌｔｕｃ

ＴｏｋｙＯ，

Ｊａｐａｎ，Ｌ．

ａｎｄＰｈ．Ｂｏｌｏｎ，１９９９，

ｐｐ．

１５０

“Ｓｔｒｉｃｔｏｒｄｅｒｉｎｇ１５３．

～

ｄｉｓｃｒｅｔｅ

ａｐｐｌｉｃ８ｔｉｏｎｓ。。ｉｎ．ＰｒＤｃ．，ＣｙＰ’夕只ｖ０１．ＩＩＩ，

ｖ０１．

２３，

【４】

Ｅ．

Ｈａｌｌ，

“Ａｌｍｏｓｔ

ｕｎｉｆｏｒｍｄｉｓｔｒｉｂｕｔｉｏｎｓ

ｆｏｒ

ｃｏｍｐｕｔｅｒ

ｉｍａｇｅｅｎｈａｎｃｅｍｅｎｔ。。』：曰：占冒７＇，丑刀ｊ：Ｃｊ口Ｉ口妒￡，ｆ．，

ｎｏ．２，ｐｐ．２０７

２０８，Ｆｅｂ．１９７４－

【５】胡学龙。许开宇编著，数字图像处理．电子工业出版社，２００６．

——４——

万方数据　

一种基于排序理论的精确直方图规定化算法

作者：作者单位：刊名：英文刊名：年，卷(期)：

田杨， 陈辉， 徐立艳

田杨,徐立艳(山东大学信息科学与工程学院;通辽职业学院)， 陈辉(山东大学信息科学与工程学院)

科技信息（学术版）

SCIENCE & TECHNOLOGY INFORMATION2008(7)

参考文献(5条)

1. R.C.Gonzales;等;阮秋琦 数字图像处理 2003

2. A.Rosenfeld;A.Kak Digital Picture Processing 1982

3. D.Coltuc;Ph.Bolon Strict ordering on discrete images and applications 19994. E.L.Hall "Almost uniform distributions for computer image enhancement 1974(02)5. 胡学龙;许开宇 数字图像处理 2006

本文读者也读过(9条)

1. 费风长. 方志军. 曾卫明. 章琳. FEI Fengchang. FANG Zhijun. ZENG Weiming. ZHANG Lin 基于区间映射规则的数字直方图处理[期刊论文]-计算机工程2006,32(19)

2. 胡正平. 刘博. HU Zheng-ping. LIU Bo 基于自适应直方图规定化函数引导的动态分层图像增强算法[期刊论文]-燕山大学学报2009,33(6)

3. 张秉仁. 陈里铭. 高游 运动模糊图像的降质过程分析与恢复技术研究[期刊论文]-中国图象图形学报A辑2004,9(7)

4. 田杨 精确直方图规定化[学位论文]2008

5. 肖斌. 王晅. 毕秀丽. 王振邦. XIAO Bin. WANG Xuan. BI Xiu-li. WANG Zhen-bang 一种基于高斯函数的直方图规定化算法[期刊论文]-铁道学报2006,28(4)

6. 李绍君. 甘岚. LI Shao-jun. GAN lan 两种直方图规定化实现算法的分析[期刊论文]-电脑知识与技术（学术交流）2007,3(18)

7. 韩殿元. 陈子富. HAN Dian-yuan. CHEN Zi-fu 一种直方图规定化中的组映射算法[期刊论文]-潍坊学院学报2005,5(6)

8. 王昊鹏. 王卫东. 李森 基于元数据的科技论文分类方法[期刊论文]-山东师范大学学报（自然科学版）2008,23(3)

9. 左长进. 姜世恩 直方图规定化描述直观算法及其应用[期刊论文]-铁路计算机应用2003,12(5)

引用本文格式：田杨. 陈辉. 徐立艳 一种基于排序理论的精确直方图规定化算法[期刊论文]-科技信息（学术版）2008(7)