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,都是不錯的選擇。

這是我設計的練習題目

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

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

使用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

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

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。

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

diffusion filter:各數值往四周均勻擴散。換句話說,新舊數值差異,設定成「梯度的散度」的倍率,倍率是擴散率。

Image Edge Detection

邊緣偵測。得到形狀邊緣。

進階應用有邊緣強化(銳化)鏤空

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

gradient filter:梯度。X軸Y軸分別一次偏微分,再求長度。中央減左、中央減下,平方和,開根號。

Sobel filter:gradient filter補強中央數值,凸顯邊緣。

Laplace filter:梯度的散度。X軸Y軸分別二次偏微分,再相加。上下左右總和,減去4倍中央。

Image Edge-preserving Smoothing

保留邊緣的平滑化。平滑化,同時盡量保留邊緣。

進階應用有特殊風格圖片去噪

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

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

rolling guidance filter:先做一次Gauss filter;再以原圖當作參考圖片,做很多次joint bilateral filter。

anisotropic diffusion:diffusion filter改良版。當梯度太大,就盡量不擴散,以保留形狀邊緣。效果是塊狀區域。

guided filter:各像素實施相同線性變換,導致各像素的梯度乘以相同倍率,導致邊緣相似。原圖片各像素增減數值(過濾)、參考圖片各像素實施相同線性變換,令兩者平方誤差盡量小,推得線性變換公式。不是摺積,無法直接轉至頻域計算,另有高速算法

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

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

edge detection:先求邊緣,再訂立臨界值以得到邊界。

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

shortest path (geodesic distance transform):

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

geometric flow (active contour model):手繪曲線圈選景物。多目標最佳化,修正曲線形狀(通常簡化成折線)。一、令折線上面的圖片梯度盡量大(通常簡化成折線頂點,讓頂點又多又密)。二、令拉力、張力盡量小(折線一次微分、二次微分盡量小)。三、令線段盡量等長(變異數盡量小)。程式碼

optimization (variational model):承上。平滑化、找邊界,兩者一併處理。平滑與邊界相互對立,平滑之處就不是邊界。多目標最佳化,再令折線以內的新舊像素差距盡量小、梯度盡量小。

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

neural network (dilated convolution):捲積規則(f∗g)(n) = {f(x)g(y) : x+y=n}改成了x+sy=n,製造間隔,避免過擬合。

Image Blending

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

進階應用有臉部剪接

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

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

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

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

Image Matting

去背。保留主角,去除背景。區隔景物,找到邊界。

進階應用有替換背景

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

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

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

Bayes matting:

Poisson matting:求梯度。

Image Inpainting

修補。填補缺漏像素。

進階應用有消除邊緣。

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

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

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

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

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

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

Image Completion

補全。填補大片缺漏像素,重塑景物。

進階應用有填充紋理

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

neural network:根據大量圖片的觀後感,來融合或填補像素。

Image Retargeting

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

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

Image Recomposition(Image Reshuffling)

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

Image Painting(Under Construction!)

簡介

Texture Generation

紋理生成。製造紋理。

noise:以亂數、三角函數生成紋理,以線性內插生成綿延感。

Perlin noise:改以遞迴函數生成紋理。

Gabor noise:改以小波轉換生成紋理。論文一論文二

Texture Synthesis

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

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

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

discrete element textures

stroke pattern

Texture Transfer

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

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

Image Abstraction

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

Image Stylization

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

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

image filtering:濾鏡。組合平滑化、邊緣化濾鏡,製造特效。例如素描風

Image Style Transfer(Image Analogy)

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

Hertzmann's Algorithm

neural network

Image Understanding(Under Construction!)

簡介

圖片的特殊武器:Pyramid

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

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

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

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

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

圖片的特殊武器:Blob

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

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

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

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

difference of Gaussians (DoG):LoG的高速近似算法。改為套用各種寬度的DoG filter。換句話說,圖片縮放成各種尺寸,套用同樣寬度的DoG filter。換句話說,Gauss 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:偵測角。一、擷取一塊區域,求梯度。二、套用窗函數Gauss window,專注於區域中心附近的梯度。三、求得二次動差矩陣總和,實施特徵分解,以兩個特徵值的絕對值大小,判斷該區域是否有角。兩值都足夠大,就表示梯度們有兩個主要方向,就表示有兩條較直的邊緣,就表示有角。四、高速算法是改用det和trace來判斷。五、為何不採用independent component analysis,而是用principal component analysis?我也不知道。

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

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

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

line segment detection:偵測線段。

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 Texture Description

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

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

Image Shape Description

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

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

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

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

Image Reasoning(Under Construction!)

簡介

Image Saliency Detection

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

Image Edge Grouping

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

Image Semantic Segmentation

語義分割。針對人類知覺系統的特性,將圖片像素連結成區域。

neural network:用手動分類的圖片進行訓練。

Image Parsing

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

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

Image Categorization(Image Classification)

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

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

part-based model:

GIST descriptor:

croudsourcing:人工標記,手動分類。找一群網民合作。正確率最高的方法。

neural network:用手動分類的圖片進行訓練。

Image Retrieval

檢索。從大量圖片當中找到想要的圖片。

進階應用有歸納

Image to Image(Image Translation)

圖片轉圖片演算法教學

Image to Text(Image Caption)

圖片轉文字

進階應用有看圖說故事

Text to Image(Image Synthesis)

文字轉圖片

Image to Shape(3D Reconstruction)

圖片轉模型

Video to Video(Video Synthesis)

影片轉影片

Video Tracking(Under Construction!)

概論

圖片的數學運算:Alignment

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

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

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

圖片的特殊武器:Optical Flow

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

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

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

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

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

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

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

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

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。

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。

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

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

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

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

Image Denoising

去雜訊、去噪。訊號受干擾而混亂,必須還原訊號。干擾假定為某種filter。

Wiener deconvolution:假設是mean filter。

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

圖片的數學運算: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 Super-resolution

超解析度。調整像素數值,提高圖片解析度。

neural network:Super Resolution GAN。

Image Watermarking(Image Steganography)

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