直方圖算法 - 快速色彩平衡算法分析

　　N個(gè)像素顏色值排序的時(shí)間復(fù)雜度是O(Nlog(N))。還有一種更高效的方法，即以直方圖為基礎(chǔ)的改編版本，最壞情況下其時(shí)間復(fù)雜度也僅為O(N)。

　　算法流程如下：

　　(1)建立一個(gè)關(guān)于像素顏色值的直方圖

　　橫向i表示顏色值，縱向表示≤i的像素?cái)?shù)量q。

　　(2)確定優(yōu)化數(shù)量和最大最小值

　　根據(jù)直方圖表示的意義，柱的高度>N×s/2的最小顏色值i，即為Vmin;同理，柱的高度≤N×(1-s/2)的最大顏色值i，即為Vmax。如果s=0，那么i的最小值即為Vmin，i的最大值即為Vmax。

　　(3)優(yōu)化像素

　　將顏色值小于Vmin的全部改為Vmin，將顏色值>Vmax的全部改為Vmax。

　　(4)生成顏色值范圍為[min，max]的新圖像

　　假設(shè)新顏色值為f(x)=ax+b(x為舊顏色值)，則有：

?

　　對(duì)于16位像素值，直方圖算法是非常好的算法，只需要大約256 KB的內(nèi)存，得到Vmin和Vmax的速度非?？?，其速度可與二分法媲美。

　　但對(duì)于32位像素值，直方圖算法大約需要耗費(fèi)18 MB內(nèi)存。這種情況下，最好采用排序算法。

　　3 實(shí)驗(yàn)結(jié)果

　　將本文提出的算法用于改善曝光不足或采光條件不好或特殊光線下(如日落)生成的圖像的一種算法。該算法可以運(yùn)用于大部分圖像，即使原圖是在正常光線下拍攝的也同樣適用。

　　圖1分別展現(xiàn)了原圖分別經(jīng)優(yōu)化率為0%、1%、2%和3%的色彩平衡算法優(yōu)化后的結(jié)果。由圖可以看出，其圖像的優(yōu)化率不同，優(yōu)化結(jié)果也不同。

?

　　與基于CCD或CMOS矩陣轉(zhuǎn)換原RGB顏色為更加標(biāo)準(zhǔn)的感性顏色及白平衡算法等傳統(tǒng)的色彩平衡算法不同，本文提出的新型快速色彩平衡算法，通過獲取一個(gè)由優(yōu)化率s決定的區(qū)間[Vmin，Vmax]，然后將這個(gè)區(qū)間外的像素點(diǎn)改在[Vmin，Vmax]內(nèi)，最后再根據(jù)Vmin、Vmax和s按比例來提高區(qū)間[Vmin，Vmax]內(nèi)像素的顏色值。實(shí)驗(yàn)結(jié)果表明，本算法能得到較好的效果，與其他算法相比更為簡(jiǎn)明、快速。