Image

Pixel與Image

一張電腦圖片、一幅螢幕畫面、一臺電子跑馬燈,都是由許多小光點組成,一個小光點就是一個「像素」、「畫素」。大量的小光點排列整齊,宛如棋盤方格,構成一張「圖片」。

小光點夠小夠密集,或者相對來說,小光點很遠很渺小,那麼觀看圖片時,相鄰的小光點將糊在一起,彷彿是柔順平滑的圖片。

電視機與相機經常強調畫素與解析度。畫素很高,意思是小光點很多;解析度很高,意思是小光點很密,使得圖片清晰銳利。

Red, Green, Blue

電腦當中,以整數0到255,代表小光點的亮度。0是最暗,255是最亮。256種數值已經足夠細膩,超越人類視覺對於亮度的辨別能力!

一個像素擁有三個數值,代表紅光、綠光、藍光的亮度;簡稱RGB,紅綠藍的首字母。

三色光疊合,得到各種顏色。RGB都是255,疊合之後就是白光、呈現白色。RGB都是0,就是無光、呈現黑色。RGB都一樣,則呈現灰色。RGB不一樣,則呈現各式各樣的彩色。

第一張圖片是範例圖片;第二張圖片是保留R值(G值與B值設定為0);第三張圖片是保留G值;第四張圖片是保留B值。右邊三張圖片的對應像素相加之後,就會形成左圖。

舉例來說
第二張圖片裡面,某一個像素的顏色 (255,   0,   0)
第三張圖片裡面,對應的像素的顏色 (  0, 123,   0)
第四張圖片裡面,對應的像素的顏色 (  0,   0, 247)
這三張圖片相加起來,得到第一張圖片裡面,對應的像素的顏色
(255, 0, 0) + (0, 123, 0) + (0, 0, 247) = (255, 123, 247)

熟悉數學的讀者,可以把「RGB值相加」想做是「向量相加」。
但是「RGB值相加」與「向量相加」,兩者背後的原理完全不相干,切莫搞混。

Alpha

有些圖片額外增加一個數值,代表透明程度;簡稱A,alpha的首字母。

0是完全透明、呈現背景底色;255是完全不透明、呈現圖片原色;其餘數值則按比例混合圖片顏色與背景底色。

左圖所有像素的A值都是255,完全不透明,看不到網頁背景的顏色;中圖所有像素的A值是127,透明的程度是50%,看得到一點網頁背景的顏色;右圖中央A值高、外圍A值低。

舉例來說
圖片裡面有一個像素的顏色 (255, 123,  10),透明程度 34
背景裡面對應的像素的顏色 (  0,   0, 255)

按比例混合(加權平均)(線性內插),得到顯示的顏色
  (255, 123, 10) * 34/256   +   (0, 0, 255) * 222/256
= (255*34/256, 123*34/256, 10*34/256 + 255*222/256)

由於RGB值必須是整數,所以計算結果必須再取floor/ceil/round。

Image的資料結構

圖片的資料結構,一般是二維陣列,一個元素儲存三個數字RGB,或者儲存四個數字RGBA。

注意到:存取矩陣元素、存取圖片像素,行列次序剛好顛倒。套用圖片函式庫時,要尤其小心。

UVa 706 10267

使用C/C++處理圖片

C與C++本身沒有處理圖片的函式庫。

你可以土法煉鋼,參考BMP、JPEG、PNG的規格書,自己寫程式讀取圖片擷取像素;然後利用Windows APILinux視窗介面的工具、Cocoa,自己寫程式把圖片像素畫在螢幕上。

你也可以拍手煉成,直接使用現成的函式庫,例如OpenCVCImg,都是不錯的選擇。

這是我設計的練習題目

使用Qt/C#/Java處理圖片

這些語言處理圖片的方式都大同小異。首先建立一個圖片物件(Qt的QImage、C#的Image、Java的Image與ImageIO),然後建立一個視窗,覆寫視窗的重繪函式,取其繪圖物件(Qt的QPaint、C#的Graphics、Java的Graphics),把圖片畫在視窗當中。

使用Python處理圖片

Python本身沒有處理圖片的函式庫,必須另行安裝。

知名函式庫是pillow,容易上手。

使用HTML與JavaScript處理圖片

http://www.w3schools.com/tags/canvas_drawimage.asp

將圖片畫在網頁上,只消幾行程式碼。首先在HTML當中,建立一個<img>以及一個<canvas>。然後在JavaScript當中,利用drawImage()將<img>的圖片畫在<canvas>上面。

也可以利用createElement(),動態建立<img>與<canvas>。圖片的部分,也可以利用Image()建構子,動態建立<img>。

我們無法直接從<img>得到像素。必須先將<img>的圖片畫在<canvas>上面,再利用getImageData()得到像素。其成員.data是一條一維陣列,依序存放每個像素的RGBA值。

修改好每個像素的數值之後,最後利用putImageData()將像素畫在<canvas>上面,便大功告成了。

想要宣告像素,可以利用createImageData()。想要拷貝像素,可以直接拷貝陣列。

學會擷取像素之後,就能做一些簡單的實驗了,例如顛倒色彩(255減掉原本的數值)、彩色變灰階(RGB相加除以三)、失焦模糊(取鄰近像素求平均值)。

甚至可以即時處理影片。影片可以想成是很多張圖片組成的。

使用Photoshop/GIMP處理圖片

Image的演算法,早已經製作成套裝軟體。商業軟體,例如Adobe Photoshop;開源軟體,例如GIMP;臺灣人自製的軟體,例如PhotoCapUlead PhotoImpact,都是不錯的選擇。

只要發揮創意,就能做出各種圖片特效。完全不需要學習程式語言與數學,只需要仔細閱讀軟體使用說明書。

Color(Under Construction!)

Color

一道光包含許多個。人類看見一道光,卻只感受到一種

從光到色的機制尚未釐清。目前只知道:一、人類視覺無法解析每一個波,只能感受混和結果。二、不同的光(不同的波的組合),可以是相同的色。彷彿數學術語「投影」。

波有兩個要素:振幅、頻率。一道光的成分,可以畫成頻譜:橫軸是頻率,縱軸是振幅,一個峰是一個波。

振幅平方,決定光能;頻率,決定色相。混和數種光能的宏觀感受,稱作亮度;混和數種色相的宏觀感受,稱作彩度

這只是簡易解釋,人類視覺機制並非如此單純。亮度和彩度會互相干涉,不能分開討論。

人眼擁有四種感光細胞,可以感知頻率和振幅。其中一種無法轉換成彩度,屬於夜視能力,此處不討論。

工程師設計實驗,製造各種頻率、各種振幅的簡諧波,請民眾辨別亮度和彩度。最後以統計學來估計三種感光細胞的感光程度。感光程度偏高之處,是紅綠藍三色。

理應取得感光細胞進行生物實驗,不過至今無人這樣做。

Color Space

色彩空間。人類視覺所能感知的所有顏色,化作數值。

CIE RGB:模仿人眼機制,以三個波,固定頻率(紅綠藍),調整光強,得到一種色,令其數值是光強比例。然而三種單色光,也少於人類所能分辨的色,於是數值有時是負數,模擬那些色,彷彿數學術語「外插」。

工程師假設:三種感光細胞的三個刺激量,決定了色。一個刺激量是每種頻率的光強乘以感光程度之後求和(點積)。以實驗數據反推感光程度,感光程度有時是負數。雖然這個數學模型完全不符合人眼機制,但是方便設計電路、方便計算。

CIE XYZ:調整成非負數。

CIE L*a*b*:數值差距等於顏色差距。

Color Model

色彩模型。數值與顏色的對應方式,通常只對應到人類視覺所能感知的一部分顏色。數值格式符合人類作業需求。

RGB:紅綠藍,螢幕。光的三原色。用於電腦螢幕。

CMYK:青洋紅黃黑,顏料的三原色,外加黑色。用於印刷。

HSL和HSV:色相、飽和度、亮度。用於電腦美術。

YUV:類比視訊。其中YCbCr用於JPEG壓縮。

Color Palette

色盤。記錄一張圖片有哪些顏色。

Color Grading

簡介

調整像素的數值。

圖片的數學運算:Function

新舊圖片,新舊像素值的對應關係,是函數。RGB分開處理,是三個函數。

identical:45°斜線。保持不變。

inverse:翻轉45°斜線,255-x,亮暗顛倒。傳統相機的負片,具備此特性。

gamma correction:模擬人腦依據環境調整亮度。人腦會根據環境亮暗,自動將極亮變暗、極暗變亮。數位相機的硬體,內建此功能。

圖片的數學運算:Histogram

RGB分開處理,得到RGB三個直方圖。一張圖片,像素值(亮度)僅256種,分別統計0到255的出現次數,得到直方圖。甚至再除以總次數,得到機率密度函數PDF。

先前透過函數,訂立新舊亮度的對應關係:每種舊亮度,對應每種新亮度。現在透過直方圖,訂立新舊亮度的對應關係:舊直方圖,對應新直方圖。

histogram equalization:調整直方圖間距。兩兩相鄰亮度,舊亮度的出現次數相差越多,新亮度相差越多,成正比。預先計算出現次數的前綴和(甚至再除以總次數,得到累積分布函數CDF),方便計算新亮度。實際應用:在亮者恆亮、暗者恆暗的前提下,讓亮暗層次更分明。

histogram matching:以CDF來建立新舊亮度的對應關係。實際應用:一張圖片,求出CDF;自訂另一個CDF,以自由調整新亮度。

histogram comparison:求出兩個直方圖的差距,以判斷圖片相似程度。方法很多。

Image Thresholding

門檻化。區分像素數值大小,依照大小分別處理。可以進一步製造黑白化(二值化)單色化等效果。

binary thresholding:自訂臨界值。大於臨界值、小於臨界值,實施不同處理。

Otsu's thresholding:窮舉臨界值,找到最佳臨界值。大於臨界值為前景,小於臨界值為背景,求前景PDF、背景PDF,求前景變異數、背景變異數相加最小者。

Color Reduction(Color Quantization)

刪減。減少顏色種類,讓圖片依然清楚。每個顏色重新設定顏色;把不同的顏色,重新設定成相同的顏色。

令壓縮圖片的效果更好、傳遞圖片的速度更快。另外,當顏色種類很少,可塑造特殊風格,例如色調分離色帶等效果。

左圖是原圖,中圖是只有256種顏色的圖,右圖是選中的256種顏色。

k-means clustering:要幾種顏色就分幾群。形成Voronoi Diagram,各群中心是新顏色。

median cut:所有像素置於RGB三維空間。反覆分割空間,不斷取寬度(或體積)最大的區塊,從最寬的那一個維度、從中位數分割。如果原圖片要降低為256種顏色,就切出256個區塊。區塊內所有像素,新顏色一律是平均值。

Color Dithering

顫化。減少顏色種類,讓圖片觀感與原先相仿。每個像素依序重新設定顏色;每個像素的先後顏色誤差,分攤給鄰近的像素。

dithering是印刷液晶顯示的重要技術。報紙上的圖片就用了dithering,用少量的單調顏色,調合出原本顏色;在原本像素的周圍點上單調顏色,宏觀望去宛如原本顏色。

左圖是原圖,中圖是先轉灰階再處理,右圖是RGB三個值分開處理。新顏色只有兩種,要嘛是255、要嘛是0。

Floyd-Steinberg dithering:先後誤差的7/16傳給右、3/16給左下、5/16給下、1/16給右下。所有像素依行列順序處理,具有遞推效果,一傳十十傳百。

Color Halftoning(Color Stippling)

半色調化。僅使用基本原色,讓圖片觀感與原先相仿。以墨水點的尺寸、間距、數量,取代像素值。

AM halftoning:墨水點尺寸不同、間距相同。像素值越高越亮,墨水點越小越淡。

FM halftoning:墨水點尺寸相同、間距不同。像素值越高越亮,墨水點越散越淡。

Color Correction

校正。重新著色,呈現真實顏色,不受色彩模型影響。

校準。重新著色,呈現真實顏色,不受攝影設備、顯示設備影響;同時求出設備的影響力。

平衡。著重於亮度,為了更加清晰。比方來說,室內用傳統燈泡,白紙會泛黃;室內用日光燈,白紙會泛藍。白紙理當是白色,以白紙為基準,重新調整圖片當中每一種顏色,移除燈光造成的影響,還原成理想顏色。亦稱「白平衡」。

調色(調光)。著重於色調,為了改變風格。製片必備絕技,屬於美術設計師、調光師的專業。

Color Harmonization

調和。重新著色,視覺上和諧。

Color to Grayscale

彩色轉灰階。重新著成灰色,讓圖片依然清楚。

簡易的方式是把每一種顏色的RGB值更改為平均亮度:floor((R+G+B)/3)。缺點是無法區分平均亮度相同的顏色。當人生是黑白的時候,可能會看到不一樣的景色。

另外還有很多簡易的方式。至於高竿的方式,是採用其他的色彩模型,例如將RGB轉換成CIE L*a*b*或者HSV等等,根據人類擅於感受的亮度及彩度,決定灰色深淺。

Grayscale to Color(Colorization)

灰階轉彩色。重新著成彩色,讓圖片依然清楚。

高竿的方法請讀者自行參考。一些古老的電視劇、影劇作品,就是如此重新上色的。又例如醫學影像,利用超音波觀察腹中胎兒,只能得到密度資訊,不能得到色彩資訊。密度資訊頂多只能轉換成灰階圖片,所以我們看到的超音波影像大多是灰色的。我們可以利用灰階轉彩色的演算法,將圖片上色,以便清楚地看到胎兒,方便醫生診視。

灰階轉彩色不是電腦專用的技術。在水墨畫當中,也有先上墨色、再上彩色的作畫技巧。

Image Filtering

簡介

調整像素的數值,依據鄰近像素的數值。

圖片的數學運算:2D Convolution

一張圖片,可以表示成RGB三個陣列,三個陣列分開處理。教科書則是表示成RGB三個函數。

圖片具有地域性,鄰近像素關係匪淺。鄰近像素的平均值、相差值(梯度),各有功效。這些計算,可以統一成加權平均值,又可以統一成點積:對應項相乘,加總。

一種位移量、一次點積,得到一個新像素。窮舉各種位移量、一一點積,即摺積,得到新圖片。時間複雜度為O(XYMN)。

【註:摺積規定其中一條數列必須頭尾顛倒;方便起見,此處不顛倒圖片和濾波器。】

超過圖片邊界時,有許多種應對方式,例如不計算、補零、複製邊界數值、線性內插。旁枝末節,不重要。

先算橫條,再垂直整合,一如區域總和區域最小值的計算手法,時間複雜度降為O(XY(M+N)),但是需要大量額外空間。

空域循環摺積,就是頻域乘法。時間複雜度降為O(XYlogXY + MNlogMN)。然而濾波器通常很小,不必大費周章、弄巧成拙。

設計濾波器、套用濾波器,便能製造各種圖片特效。亦得在特定區域之內套用濾波器,而不是整張圖片都套用濾波器。

濾波器是線性的。倍率性:一個濾波器(的每個值)乘上倍率,等於新圖片(的每個像素)乘上倍率。加法性:兩個濾波器相加減,等於兩張新圖片相加減。想要揉合多張新圖片,可以預先揉合濾波器,降低計算量。

新圖片像素數值必須介於0到255,須normalization。

Image Smoothing(Image Blurring)

平滑化霧化。消滅邊緣。失焦模糊。可以進一步製造動態模糊去噪抗鋸齒打馬賽克等效果。

人眼感知到的平滑,就是亮度暨彩度相差很少。相鄰像素取平均值,讓彼此數值更接近、更平滑。

mean filter:平均值,矩陣所有數值設定為1/NM。

Gaussian filter:矩陣是一個二維常態分布。有高速算法

bilateral filter:當像素數值差距太大,就盡量不列入平均值計算,以保留形狀邊緣。不是摺積,無法直接轉至頻域計算,另有高速算法

median filter:原本數值替換為鄰近數值們的中位數,可移除脈衝。不是摺積,無法直接轉至頻域計算,另有高速算法

Image Edge Detection

邊緣偵測。產生邊緣。得到形狀邊緣。可以進一步製造邊緣強化(銳化)鏤空等效果。

人眼感知到的邊緣,就是亮度暨彩度相差很多。相鄰像素取差值,差值較大的地方就是邊緣。

gradient filter:X軸、Y軸分別一次偏微分。即是梯度。

Sobel filter:gradient filter補強中央數值,讓邊緣更明顯。

Laplacian filter:X軸、Y軸分別二次偏微分,然後相加。即是梯度的散度。

Image Template Matching

匹配。給定圖片片段,找到正確位置。概念等同字串匹配

完全相等:窮舉所有位移量;針對每一種位移量,對應位置判斷相等後求AND。缺點是像素數值不准有一丁點誤差。

平方誤差最小:對應位置相減平方後求和。

相關係數最大:對應位置相乘後求和(即摺積)。憑感覺瞎搞,但是算得快。圖片預先銳化、圖片預先保留高頻,結果較佳。

Chamfer distance最小:特色是比對邊緣,而且邊緣形狀不必完全相同。圖片與片段,預先求得邊緣、二值化(邊緣為1,非邊緣為0)。圖片求distance map。套用相關係數最大的演算法。

圖片的數學運算:Mathematical Morphology

圖片視作三個函數,以數學形態學調整函數形狀,例如dilation令亮處擴散黏結、erosion令暗處擴散黏結。亦可先求梯度再處理。

Image Warping(Under Construction!)

簡介

調整像素的位置。

圖片的數學運算:Geometric Transformation

訂立每個像素的新座標,或者只訂立每個像素的移動方向,然後移動像素。這麼做可以營造一些圖片特效。

一一設定每個像素,實在太累人。我們可以直接運用優美的數學工具,運用幾何變換,一口氣移動所有像素。計算幾何線性代數談過線性的幾何變換,例如平移、縮放、旋轉、鏡射。

正向處理(直接法):窮舉原圖片每個像素的座標,一一變換,得到新座標。新座標四捨五入,讓像素座標是整數。然而,有些地方密集重疊、有些地方稀疏留白,無法構成圖片。這種方式行不通。

逆向處理(試誤法):窮舉新圖片每個像素的座標,一一逆向變換,得到原座標。實施二維內插,例如近鄰內插(恰為四捨五入)雙線性內插sinc內插,求得理想的像素數值。

Image Scaling(Image Resizing)

縮放。調整圖片尺寸。可以進一步製造Depixelation的效果。

Image Rotation

旋轉。除了內插,亦得用shear達成圖片旋轉,避免誤差。

圖片的數學運算:Weighted Average Coordinates

移動像素亦可運用加權平均座標系統。釘選幾個對應點,就能在原圖片與新圖片上面訂立座標系統,立即完成每個像素的座標對應關係。

三角形內插:

四邊形內插:

Image Warping

扭曲。扭曲外形。可以進一步製造驗證的效果。

function-based warping:制定一個函數,二維到二維,輸入是像素原始位置,輸出是像素移動目的地。

feature-based warping:標記數條對應線段,以線段長度、點線距離,做為內插比重。特色是容易操作。

mesh warping:手動或者自動建立網格,網格頂點是控制點。原圖片網格呈整齊等分,新圖片網格供用戶調整。隱藏原圖片暨網格,顯示新圖片暨網格。對應網格實施座標內插

Image Deformation

形變。保持架構,扭曲外形。

Image Morphing

變形。從一個外形變化為另一個外形。可以進一步製造美化、變臉、補幀的效果。

標記數個對應點,符合五官特徵、四肢關節。

像素位置逐步變化,僅改變形狀。warping。

像素數值逐步變化,僅淡入淡出。cross dissolving。

像素位置、像素數值一齊逐步變化,達成變形的效果!morphing = warping + cross dissolving。

變形就是兩張圖做內插,像素位置、像素數值都要內插。

Image Editing(Under Construction!)

簡介

Image Compositing

合成。兩張圖片相疊覆蓋,成為一張圖片。

copy-and-paste:直接覆蓋。建議先去背。弄得好是剪貼藝術拼貼藝術

Image Segmentation

分割。區隔景物,找到邊界。

gradient:求梯度、訂立臨界值。

watershed transform:區域極小值分別注水。相連水域,推定為相同景物。高速算法是四元樹,求每塊區域的平均值與變異數。分割過程中,當變異數太高則分割區域。分割結束後,當平均值相近則合併區域。

curvature flow:手動圈景物,手繪曲線沿曲率方向移動,不斷縮小範圍,遇到梯度較大處則停止。效果等同前者,特色是會動。甚至考慮張力和拉力,透過regularization併入最佳化對象,控制手繪曲線的大小和形狀。

GrabCut:手動圈景物,求最小割。像素之間的權重:梯度絕對值倒數。源點(匯點)到像素的權重:前景(背景)像素理想值與實際值的差距的倒數。倒數通常改成高斯分布或者左右翻轉的sigmoid,以避免倒數趨近無限大。

手動劃記:一、手動劃記前景與背景。前景劃記處求PDF,背景劃記處求PDF。二、圖片每個像素,區分前景與背景,根據PDF機率大小。然而前景與背景不一定連通。三、圖片每個像素,重新區分前景與背景,根據最短路徑長度。分別找到每個像素到前景劃記處、背景劃記處的最短路徑,點是像素,邊是八方向,邊的權重分別是前景PDF機率差、背景PDF機率差。前景與背景多半會連通。四、於邊界兩旁,分別擷取前景與背景的像素,做為新的劃記。反覆執行演算法,直到邊界收斂。

Image Blending

合成。兩張圖片相疊揉合,成為一張圖片。可以進一步製造臉部剪接的效果。

compositing和blending都是合成,但是有點差別。compositing是聚合,拼湊在一起。blending是融合,摻雜在一起。運用blending得以製做自然美觀的compositing。

alpha blending:RGB加權平均。鬼影。

pyramid blending:兩圖分別求Laplacian pyramid,每層分別拼接,最後疊合還原。

Poisson blending:新圖梯度,儘量等於底圖梯度(或者儘量等於兩圖梯度較大者)。左右兩式相減平方最小,就是左右兩式一次微分相等;縱向與橫向加總,就是左右兩式散度相等。新圖梯度與底圖梯度的平方誤差最小,就是梯度的散度相等,此即微分方程經典公式Poisson equation。化做線性方程組求解亦有頻域的高速算法(限矩形區域)

Image Matting

去背。保留主角,去除背景。區隔景物,找到邊界。可以進一步製造替換背景的效果。

segmentation與matting都是區隔景物,但是有點差別。segmentation著重大體,matting著重細部。

有人認為blending與matting互為反運算。blending是疊合兩張圖片,matting是剝離兩張圖片。

blue screen matting:主角背後放個藍幕或藍牆壁進行拍攝,圖片中的藍色就是背景。俗擱有力,又快又準。攝影棚必備道具。

Bayesian matting:

Poisson matting:求梯度。

Image Inpainting

修補。填補缺漏像素。可以進一步製造擦拭邊緣的效果。

smoothing:依照行列順序,逐一填補像素。取得已知的鄰近像素,求亮度平均值(平滑化),甚至採用其他的平滑化濾波器。缺點是平滑化所帶來的模糊化、邊緣偏移、誤差累進。

fluid dynamics:周界往內推進,逐一填補像素。周界像素視作粒子,沿著梯度的垂直方向移動(沿著邊緣移動),速度是二階微分。可表示成偏微分方程PDE。詳細內容是個謎!

fast marching:周界往內推進,逐一填補像素。填補順序是自創的最短距離,填補數值是自創的加權平均值。缺點是邊緣破損

填補順序。周界為起點,求周界到內部像素們的最短距離。label setting algorithm,像素視作節點。最短路徑分兩類:由正上/正下/正左/正右走來,距離加一;由上左/上右/下右/下左走來,距離如下圖。

填補數值。針對一個已知鄰點,其亮度加梯度(取出朝向填補點的分量,求其長度),是填補點理論上的亮度。針對所有已知鄰點,個別求出理論上的亮度,再求加權平均值,權重是這三項相乘

一、修補後的周界的法線(即最短距離的梯度),取出朝向像素的分量,求其長度。二、鄰點與填補點,二維直線距離的倒數。三、鄰點與填補點,前述最短距離的差的倒數。

Image Completion

補全。填補大片缺漏像素,重塑景物。可以進一步製造填充紋理的效果。

data-driven:從資料庫找到最相像的圖片,剪接上去。Image Retrieval檢索,Image Matching匹配,Image Blending合成。

Image Retargeting

重新定位。縮小圖片長寬,裁剪多餘像素,但是保留景物原本形狀。

seam carving:屢次刪除不穿過邊緣的路徑,路徑以縱向或橫向跨越圖片,使得圖片長或寬屢次減一。使用動態規劃或大量隨機散步,找到一條梯度絕對值總和最小的路徑。梯度可換成Sobel、Canny。

Image Recomposition(Image Reshuffling)

重新合成。移動景物位置,無縫接軌。

Image Painting(Under Construction!)

簡介

Texture Generation

紋理生成。製造紋理。

noise:亂數產生紋理,內插產生綿延感。

Texture Synthesis

紋理生成。延展紋理,由窄變廣。

Voronoi diagram:素材隨機取出片段,隨機散佈,相鄰素材片段的中央地帶求加權平均。程式範例

image quilting:素材隨機取出方格,整齊拼接,部分交疊,交疊處誤差盡量小。誤差可定義為:所有對應像素誤差總和、最小割(平面圖最小割即最短路徑)。

discrete element textures

stroke pattern

Texture Transfer

紋理轉印。拼接紋理,構成圖形,宛如拓印。

image quilting:紋理與新圖片交疊處的誤差(最小割),紋理與原圖片的匹配誤差,兩者加權平均值最小。

Image Abstraction

抽象化。保留圖片大致的輪廓、大致的色調。

Image Stylization

風格化。重新繪製圖片,呈現特殊風格。已有彙整書籍彙整文章

Hertzmann's Algorithm:畫線。每個像素大致朝著相同方向移動一段距離,沿途不斷貼上。調整筆畫粗細、下筆間距,可以營造印象派畫風。亦得沿梯度的垂直方向移動,遇到邊緣就停住,讓邊緣明顯。畫筆與像素,顏色差異太大就停住。算法在此

Image Analogy

類比。擷取兩圖之間的風格差異,套用至其他圖片。

Hertzmann's Algorithm

convolutional neural network

Image Understanding(Under Construction!)

簡介

圖片的特殊武器:Pyramid

人眼有著觀(失焦、視野廣)看(對焦、視野窄)的差別。由觀到看、由看到觀的過程當中,人腦似乎能夠快速擷取圖片特點。

一種模擬的方式是:圖片分別套用各種寬度的mean filter。換句話說:圖片縮放成各種尺寸,套用相同寬度的mean filter。

mean pyramid:圖片長寬屢次縮小一半,得到許多張圖片,形成金字塔。縮小時,每四個像素合併成一個像素(田變口),取平均值。此步驟即mean filter,具有模糊化效果,彷彿人眼失焦。

Gaussian pyramid:縮小時改採Gaussian filter,消滅邊緣。

Laplacian pyramid:縮小時改採Laplacian filter,強調邊緣。

圖片的特殊武器:Blob

針對人類視覺系統的特性,擷取圖片引人注目的地方。

Laplacian of Gaussian filter (LoG filter):先做Gaussian filter,再做Laplacian filter。先去噪,再求邊緣,效果更佳。

difference of Gaussian filter (DoG filter):LoG filter的高速近似算法。兩個Gaussian filter,平均值相同、變異數為0.3和1.0,相減之後恰好近似Laplacian filter。

Laplacian of Gaussians (LoG):圖片套用各種寬度(變異數)的LoG filter。針對一種寬度,找到區域極大值,推定為圖片重點,重點的半徑範圍是LoG filter的變異數。

difference of Gaussians (DoG):LoG的高速近似算法。改為套用各種寬度的DoG filter。換句話說,圖片縮放成各種尺寸,套用同樣寬度的DoG filter。換句話說,Gaussian pyramid,從中選擇尺寸足夠大的圖片來縮小(因為放大會失真),以得到各種尺寸的圖片;寬度最接近的兩兩圖片,直接相減。【尚待確認:直接相減】

圖片的特殊武器:橢圓形Blob

引人注目的地方,莫名其妙是圓形。由於尺寸、形狀皆不夠精準,所以調整成橢圓形。不過還是很莫名其妙。

automatic scale selection:調整blob尺寸。一、找到一個blob之後,微調blob尺寸。二、計算blob裡面(或者周圍)所有像素的梯度的長度的平均值。三、平均值依照blob尺寸排列,形成一串數列。四、區域極大值所在之處,表示梯度變化最大,推定為正確尺寸。當區域極大值不只一個,推定blob不存在。

高速近似算法:一、各種寬度的blob,改成各種尺寸的圖片(實務:邊長屢乘0.7倍)。二、微調blob尺寸,改為尺寸相鄰的兩張圖片的線性內插(實務:微調範圍是該圖的0.7至1.4倍,自行設定間距)。三、統計blob內部的梯度平均值,改為擷取blob中心的DoG值。四、簡單一句話歸納:長、寬、縮放尺寸,在三維空間中求得DoG區域最小值。

affine shape adaptation:調整blob形狀。取得blob內的像素,求得二次動差矩陣總和,實施特徵分解,得到橢圓形,設為新blob。重複上述動作,直至blob形狀不變。

另類觀點:取得blob內的像素。一個像素的X梯度、Y梯度,視作一個二維座標點;所有像素的X梯度、Y梯度,視作一群二維座標點。計算principal component analysis(不必預先減去平均值),得到橢圓形。

Ix(x,y) = I(x,y) - I(x-1,y) = x gradient at (x,y)
Iy(x,y) = I(x,y) - I(x,y-1) = y gradient at (x,y)

P = [ Ix(x,y) Ix(x,y+1) Ix(x,y+2) ... Ix(x+1,y) Ix(x+1,y+1) ... ]
    [ Iy(x,y) Iy(x,y+1) Iy(x,y+2) ... Iy(x+1,y) Iy(x+1,y+1) ... ]

PᵀP = [ ∑IxIx ∑IyIx ] = ∑C(x,y) 
      [ ∑IxIy ∑IyIy ]

C(x,y) = [ IxIx IyIx ] = second monent matrix = structure tensor
         [ IxIy IyIy ]

Image Feature Detection

特徵偵測。找到圖片所含有的特殊結構、邊邊角角。

Hessian keypoint detection:偵測頂點、端點、臨界點。一、求每個像素的det(Hessian matrix)。二、由於綜合了X梯度與Y梯度,因此數值偏高者,多半為頂點、端點、臨界點。

I(x,y) = R/G/B pixel value at (x,y)
Ix(x,y) = I(x,y) - I(x-1,y) = x gradient at (x,y)
Iy(x,y) = I(x,y) - I(x,y-1) = y gradient at (x,y)
Ixy(x,y) = Ix(x,y) - Ix(x,y-1)
         = [I(x,y) - I(x-1,y)] - [I(x,y-1) - I(x-1,y-1)]
         = y gradient of x gradient at (x,y)

     ∂I          ∂²I    
Ix = ――   Ixy = ―――――   H = [ Ixx Iyx ]   det(H) = Ixx Iyy - Ixy Iyx
     ∂x         ∂x ∂y       [ Ixy Iyy ]          = Ixx Iyy - (Ixy)²

Harris corner detection:偵測角。一、擷取一塊區域,求梯度。二、套用窗函數Gaussian window,專注於區域中心附近的梯度。三、求得二次動差矩陣總和,實施特徵分解,以兩個特徵值的絕對值大小,判斷該區域是否有角。兩值都足夠大,就表示梯度們有兩個主要方向,就表示有兩條較直的邊緣,就表示有角。四、高速算法是改用det和trace來判斷。五、為何不採用independent component analysis,而是用principal component analysis?我也不知道。

Canny edge detection:偵測邊緣。一、平滑兼去噪:Gaussian filter。二、求邊緣:求得梯度長度、梯度方向。三、找到最明顯的邊緣:若梯度長度為區域極大值,則保留,否則設為零。區域極大值是依照梯度方向取得前後兩個像素,僅三個像素比較梯度長度。四、清除不明顯的邊緣:設定門檻,梯度長度太短者設為零。五、銜接邊緣。

Hough line transform:偵測直線,甚至偵測線段。一、求邊緣:求得梯度長度,設定門檻。二、針對一個像素(x,y),窮舉穿過此像素的直線們,求得原點在直線上的投影點,再換成極座標表示法(r,θ),一條直線對應一個點,直線們對應一條曲線r = xcosθ + ysinθ。一個像素得到一條曲線。三、圖片每個像素皆換成曲線。曲線們的交點,即是穿過大量像素的直線!四、建立細膩方格紙(離散化),曲線穿過方格,則投票加一,得票多的方格當作交點。五、轉換過程是三步驟:對偶、轉成極座標、投票。

Hough cycle transform:偵測圓。窮舉各種半徑。針對一個像素(x,y),窮舉穿過此像素的所有圓;圓穿過像素,則投票加一,得票多的像素就是圓心。

UVa 12599

Image Feature Detection再進化

例如corner,只有位移不變、旋轉不變。現在還要縮放不變。方法是把corner補強為橢圓形blob。

Harris affine region detector:圖片縮放成各種尺寸,每張圖都找corner。每一個corner,以自己為中心,嘗試找橢圓形blob。

Hessian affine region detector:找corner改為找keypoint,其餘相同。

maximally stable extremal regions

Kadir-Brady saliency detector

Image Feature Description

特徵描述。將圖片獨特之處寫成數值,以供辨識比對。

histograms of oriented gradients (HOG):一個像素進行投票,梯度長度是持票數,梯度角度(無視正反方向,僅0°到180°)決定投票箱編號。180°等分成9個箱子。一個像素投票給最鄰近的兩個箱子,與箱子中心的距離(角度差)做為投票比例。

圖片分解成大量16×16區域,交疊一半。一個區域256個像素實施投票,得到9個數字,RGB分開就是9×3個數字。一個區域的數字,依序串成一串,當作特徵描述。

scale-invariant feature transform (SIFT):一個像素進行投票,梯度長度是持票數,梯度角度決定投票箱編號。360°等分成8個箱子。一個像素投票給一個箱子。

實施Harris affine region detector,得到大量區域。針對一個區域,切成4×4宮格,一個宮格所有像素實施投票,得到8個數字,所有宮格就是4×4×8=128個數字,RGB分開就是128×3個數字。一個區域的數字,依序串成一串,當作特徵描述。

speeded up robust features (SURF):SIFT的高速算法。

BRIEF – Binary Robust Independent Elementary Features
BRISK – Binary Robust Invariant Scalable Keypoints
ORB   – Oriented FAST and Rotated BRIEF
FREAK – Fast Retina Keypoint

Image Feature Matching

特徵匹配。兩張圖片,找到引人注目的地方,找到對應。

KNN Match
Radius Match
Flann Based Matcher
RANSAC

Image Object Detection

物體偵測。判斷圖片內容是否為預設物體。

Viola-Jones framework:最初用來偵測人臉。一、已知是何物的圖片,窮舉位置、範圍、窗函數(仿照Harr小波,此處使用四種),一種情況當做一個特徵,得到大量特徵。二、因此圖片必須尺寸一致、正面照、無留白,如此位置和範圍才對的上。三、一個特徵,求區域和,得到一個分數,當作特徵描述。區域和的高速算法是前綴和相減。四、實施classification,取得關鍵特徵,捨棄無效特徵。五、不知是何物的圖片,窮舉位置、區域,全部特徵都通過檢驗才視為正確。

integral channel features (ChnFtrs):Viola-Jones framework豪華版,最初用來偵測行人。一、像素數值,除了灰階值以外,還可以是梯度方向的投票數(仿照HOG,此處使用六個箱子)、梯度長度、LUV值。二、窗函數,除了原本四種以外,還可以是簡單的矩形窗、自訂的零散的區域。三、區域和,還可以是histogram。

Image Object Recognition

物體辨識。判斷圖片內容是哪種物體。

Image Saliency Detection

重點偵測。針對人類視覺系統的特性,找到圖片引人注目的地方。引人注目的地方,不一定是與眾不同的地方。

Image Edge Grouping

邊緣整合。針對人類視覺系統的特性,將圖片邊緣銜接成區域。

Image Texture Description

紋理描述。將紋理獨特之處寫成數值,以供辨識比對。

local binary pattern:八個相鄰像素值,分別減去中央像素值,取其正負號,變成8-bit二進位數值。旋轉視為相同,剩下36種數值。圖片所有像素都實施此計算,統計每種數值的數量。

Image Shape Description

形狀描述。將形狀獨特之處寫成數值,以供辨識比對。平移旋轉後,數值需相同。

principal component analysis:憑感覺亂搞。座標軸不實用,中心則可用。

shape histogram:選定中心,同心圓、放射線。

spherical harmonics decomposition:選定中心,分解成球諧函數

Image Reasoning(Under Construction!)

簡介

Image Categorization

歸類。解讀圖片內容,將大量圖片分門別類。

bag-of-words model:列舉世上各種物品,編纂百科全書。一張圖片,從中找到每種物品的出現次數(或者相似程度),得到一個直方圖。所有直方圖實施clustering建立分類;分群時,以histogram comparison得到兩兩直方圖距離。

part-based model:

GIST descriptor:

convolutional neural network:專門用來分類圖片的數學模型。手動分類大量圖片,灌入模型,進行訓練。之後就能找到某圖片的類別,也能找到某類別的圖片。

Image Retrieval

檢索。從大量圖片當中找到想要的圖片。可以進一步製造歸納的效果。

Image Parsing

剖析。建立圖片當中每個物品的從屬關係。

binary partition tree:把一張圖片裡的物件依照區域分類,儲存於二元樹之中。

Image to Text(Image Caption)

圖片轉文字。可以進一步製造看圖說故事的效果。

Text to Image

文字轉圖片。

Video Tracking(Under Construction!)

概論

圖片的數學運算:Registration

物體不斷移動,物體於每張圖片的位置、形狀都略有差異。我們可以透過前面章節的feature detection、feature description,擷取物體的大致範圍,但是如何精準得到物體移動軌跡呢?

想像像素們一齊移動,欲求軌跡。像素們一齊實施函數變換,欲求函數。此問題即是registration,每個點(像素)另外附帶數值(像素值);點的位置要盡量對齊,點的數值也要盡量相同。

Kanade-Lucas-Tomasi algorithm:一、假設只有translation。二、令兩張圖的平方誤差最小。三、泰勒展開式,以零階與一階導數,近似原式。四、實施gradient descent或者Euler extrapolation。

圖片的特殊武器:Optical Flow

Kanade-Lucas-Tomasi algorithm的高速近似算法。一、增加了時間維度。二、假設像素們位移之後完全相符,原式與零階導數完全相等。兩者相消後,得到「泰勒展開式一階導數等於零」的結論,得到一道簡潔的線性方程式。

一個像素構成一道線性方程式,所有像素構成一個線性方程組(矩陣恰是二次動差矩陣總和)。求解,即得位移量。

然而,正常情況下,像素們位移之後不可能完全相符。前述假設,邏輯錯誤,最後得到歪解。憑感覺瞎搞,但是算得快。

「泰勒展開式一階導數等於零」,整個式子除以時間,就得到像素速度與亮度的關係式。計算學家取了一個文雅的名稱叫做「光流」。以光流的角度,重新解釋整件事:

假定像素亮度不變、位置會變;欲求像素的移動速度,移動速度表示成向量。三個維度:長、寬、時間。像素位置改變,泰勒展開式取到一階導數,原式與零階導數相消:梯度在「像素的移動距離向量」上的點積(投影)等於零。整個式子除以一單位時間:梯度在「像素的移動速度向量」上的點積(投影)等於零。此投影量,理想狀態是零,但是通常不是零。我們希望投影量越小越好。

Lucas-Kanade algorithm:「投影量」越小越好。一、因為是歪解,所以只好用遞推法趨近正解。二、遞推法,以當前移動速度來移動像素,再求得新的移動速度,直到收斂。三、縮放法,Gaussian pyramid,從最小的圖片(最大的範圍)開始實施,逐步縮小範圍。四、translation可以推廣成affine transform。請參考這篇講義

Horn-Schunck algorithm:「投影量」與「速度向量的長度」越小越好。scalarization。

EpicFlow:「投影量」與「速度向量的長度」與「邊緣匹配的差異」越小越好。scalarization。

Video Stabilization

安定。攝影過程中相機震動搖晃,相機位置不斷改變。攝影之後令影片擺正對齊。

Image Template Tracking

範本追蹤。給定圖片片段,找到移動軌跡。

Lucas-Kanade algorithm

Image Feature Tracking

特徵追蹤。給定圖片特徵,找到移動軌跡。

Kanade-Lucas-Tomasi algorithm

Video Object Tracking(Video Object Matching)

物體追蹤。指定圖片當中物體,找到移動軌跡。可以進一步達到複數物體追蹤群眾計數的效果。

dense tracking:warping + template matching + template tracking。

sparse tracking:feature detection + feature matching + feature tracking。

online optimization:以histogram或SIFT的相似程度做為函數,實施mean shift或particle filter。

convolutional neural network:

Video Magnification

放大。以高速、高解析度的攝影機進行拍攝,觀察物體極短時間、極小範圍的微小變化。應用範圍很廣

Image Coding(Under Construction!)

簡介

像素數值,視作純粹的數字、訊號、碼。

圖片的數學運算:Vector與Linear Transformation

一張圖片,可以表示成RGB三條向量。

像素的運算,想成是函數。若是線性變換,可以寫成矩陣。

線性變換有許多優美的性質。例如矩陣加減,等價於新圖片加減。例如一連串線性變換,可以簡化成一次線性變換;多個矩陣預先相乘(複合),簡化成一個矩陣。

Image Representation

表示法。以簡略數據,紀錄圖片,用於特徵描述、辨識。

eigenimage:圖片表示成向量。兩兩點積,求相關矩陣(實數對稱矩陣),得到特徵值(實數)、特徵基底(正規正交矩陣)。

sparse coding:圖片表示成向量。求一套基底,其線性組合涵蓋所有向量(圖片)。處理一張圖片:解Ax = b,A的一個直條是一張樣式圖片,x是加權平均值,b是一張完整圖片,請最小化x的1-norm。處理多張圖片:加總起來,或者把向量推廣成矩陣。

圖片的數學運算:Fourier Transform

聲音處理是一維訊號,影像處理是二維訊號,道理相通。

圖片亦有spatial domain與frequency domain的概念。實施正向的二維Fourier transform,空域轉頻域。實施逆向的二維Fourier transform,頻域轉空域。時間複雜度為O(XYlogXY)。

空域當中,平均值具備平滑效果,聲音處理得齆聲,影像處理得霧化;差分具備差異效果,聲音處理得尖聲,影像處理得邊緣。

頻域當中,低頻數值具備主體,聲音處理得母音,影像處理得形體;高頻數值具備細節,聲音處理得爆音,影像處理得特徵。

聲音處理,頻域符合人類感知;影像處理,空域符合人類感知。因此影像處理不適合採用頻域。早期的影像處理教科書,是訊號學者主導,所以才會非常強調頻域。

如果不關心圖片內涵,只想把圖片當作訊號來處理,那麼頻域就可發揮功效。

Image Noise

雜訊。像素值異動、有誤差,不是原始數值。簡單起見,習慣假設:每個像素獨立產生雜訊,不會互相影響。

不同的雜訊,有不同的補救方式。兵來將擋、水來土掩。

salt-and-pepper noise:各個像素以固定機率丟失。要嘛正常,要嘛變成0或255。數位傳輸經常出現。破法是median filter。

Gaussian noise:相素值添加誤差,誤差呈Gaussian distribution,簡稱Gaussian error。類比傳輸經常出現。破法是mean filter。

clipped noise:感光設備收集過多亮度,數字爆表,僅得255。好比電玩遊戲傷害上限9999。亮處攝影經常出現。無法破解。

shot noise:感光設備偶然加收一些亮度。好比公車正要離站,剛好有人陸續趕上車,公車無法立即關門、準時行駛。即是Poisson error。暗處攝影經常出現。破法是mean filter。

quantization noise:像素值捨去小數變成整數,導致誤差。我們合理假設,小數部分任何可能性一律均等,呈uniform distribution。捨去小數,即是減去一個隨機數字,即是添加誤差,即是uniform error。數位設備必然出現。不必破解。

Image Denoising

去雜訊、去噪。

Wiener deconvolution

Richardson-Lucy deconvolution:假設位移誤差是Gaussian noise,亮度誤差是Poisson noise。

anisotropic diffusion

圖片的數學運算:Wavelet

http://www.jjj.de/fxt/fxtbook.pdf

Gabor filter

Image Compression

壓縮。主要用途是圖片檔案格式。目標是減少檔案容量、避免畫面失真

BMP:無壓縮。添加表頭。

JPEG:失真壓縮。8x8、RGB2YUV、DCT(KLT if 1-markovian)、quantization、zig-zag、Huffman。

JPEG 2000:失真壓縮。發展當中。

PNG:無失真壓縮。delta filtering = finite difference、DEFLATE = LZ77 + Huffman、CRC。

GIF:無失真壓縮,只有256色,已退流行。LZW。

DjVu:失真壓縮,專門處理文件。黃鐘毀棄,瓦釜雷鳴,故不流行。分三層:前景、背景、文字。前景、背景,IW44。文字視作黑白圖片,JB2。

Video Compression

壓縮。影像壓縮標準的兩大陣營是國際標準HEVC、谷歌VP9。主要用途是影片檔案格式。可以進一步製造串流廣播的功能。

MPEG:繼承JPEG。在前後幀找到相似區塊,增進壓縮效果。區分IPB三種幀。

Image Transmission

傳輸。傳送圖片資訊,儘量不失真。

progressive transmission:設定成不同解析度,分別傳輸。

Image Watermarking(Image Steganography)

浮水印。訊息隱藏至圖片當中,無法察覺差異。用來判斷圖片是否被私下改造。

Image Acquisition

擷取。運用各種器材,獲得資訊,將資訊轉換成像素數值。諸如數位相機、監視器、掃描器、顯微鏡、太空望遠鏡、聲納、超音波攝影、核磁共振攝影等等。詳情請洽電機系。

注意到資訊不一定要是光線的頻率、光線的強度,也可以是物質密度、聲音頻率等其他東西。

http://en.wikipedia.org/wiki/Coherent_diffraction_imaging