找出二值影像的邊緣並序列化

　　標題提到的「序列化」，意思是依序記錄邊緣上的點，以便之後取出該物體的 Fourier Descriptor。找邊緣的演算法很多：canny、snake 等，不過這些我都不會，所以我先用了 sobel 來做，但由於 sobel 會讓物體的邊緣「增厚」，這樣對於我之後的序列化會有困難。所以必須換別的做法。


　　因為來源是二值影像，所以這邊想到一個更簡潔，效果我覺得一定好的方式 (自我感覺良好:P)，整個過程分三步驟：

1. 對影像做水平掃描，若像素 A 的左或右為背景，則像素 A 為邊緣。
2. 對影像做垂直掃描，若像素 A 的上或下為背景，則像素 A 為邊緣。
3. 將步驟一得到的水平影像和步驟二的垂直影像做「logical OR operation」。

　　這樣一來，就可以將物體的邊緣找出來，且不會有邊緣增厚的問題發生，接下來就是「序列化」的動作。因為物體是連通，所以邊緣不會有斷掉的問題發生，我只要從某一點出發，朝周圍八個方向走訪即可〈Depth First Search 的應用〉，就是一定可以走出迷宮的老鼠..^_^。



程式碼下載 (DFS is non-recursive version)

判斷兩矩形是否重疊

　　這個概念其實和高中數學提到的兩圓交於兩點一樣意思，差別只在矩形有兩個變量：寬與高。不過判斷上同樣簡單，只要計算出兩矩形中心的水平距離和鉛直距離，並滿足以下條件##ReadMore##

(distHor < (W1/2 + W2/2) && distVer < (H1/2 + H2/2))

程式碼下載 (矩形要自己框，框完一個就按任意鍵，再框下一個)

Fourier Descriptor

　　在「Digital Image Processing 2/e」一書中的第 11 章：表示與描述〈Reprentation and Description〉，裡頭介紹幾種描述物體的方法，例如：鏈碼〈chain code〉、骨架〈skeletonizing〉、邊界描述子〈boundary descriptor〉、紋理〈texture〉等，這些動作其實就是在找物體的特徵，一旦決定了特徵，才能透過辨識引擎去做訓練與辨識。

　　上述提到的邊界描述子有幾種描述方式，其中一種稱作「Fourier Descriptor」，這裡先做個簡單的介紹。這個方法是透過一維傅立葉轉換，將邊界資料轉換後，取其頻譜〈spectrum〉來當作特徵。有學過影像處理應該都知道，傅立葉轉換的高頻部份用來描述邊緣、細節、甚至是雜訊；低頻則是描述平滑區域、整體形狀。所以在實際應用上，就是把原始的 N 筆邊界資料，轉換後，取其前 M 筆的頻譜值來當特徵〈M <= N〉。 　　 　　

　　至於該如何量化邊界資料，其實課本說明得很清楚，我們只要把每個點 (x,y) 「視為」x+yi，也就是複數平面上的點，接著，從某點出發，順(或逆)時針依序記錄下來即可。說得更明白一點就是用 Complex[] 陣列紀錄啦！至於將每個點看成一個複數，好處有二(我猜的)：

1. 不改變物體形狀。
2. 用一維傅立葉即可。(降維度的味道，因為本來是影像嘛^_^)
   

　　因為這個演算法蠻簡單得，我就自己實作出來，並且驗證課本的正方形範例，不過，要注意一點，由於程式中的座標系和數學上的直角坐標系，Y 座標是上下顛倒，所以需要轉換一下。






程式碼下載

cv::Mat 與 IplImage 之間的轉換

從「OpenCV 1.1pre」版本開始對以前的 API，以 c++ 包裝，定義成 namespace cv，這意味著想寫 c-style 或 c++ style 的程式皆可。所以，在處理影像的部份，就有「cv::Mat」和「IplImage」，至於該如何轉換，請看以下程式碼片段：

IplImage -> cv::Mat

IplImage* iplImg = cvLoadImage("lena.jpg");
cv::Mat cvMatImg(iplImg, 0);
cv::imshow("cv::Mat Show", cvMatImg);

cv::Mat -> IplImage

IplImage iplImg2;
iplImg2= IplImage(cvMatImg);
cvShowImage("IplImage2 Show", &iplImg2);

在第一個範例中，我們可以看到 cv::Mat 的建構子有兩個參數，比較重要的是第二個參數，如果設定成 0，代表不複製影像，也就是兩個變數的 row data 共用同個記憶體位置，header 則各自有。

接著，第二個範例，從第二行可以看到 cv::Mat 呼叫成員函式 operator IplImage()，至於行為上就沒得選擇，一定是 row data 共用同個記憶體位置，header 各自有。

底下是 operator IplImage() 的實作內容，定義在 cxmat.hpp；類別則宣告在 cxcore.hpp...

inline Mat::operator IplImage() const
{
IplImage img;
cvInitImageHeader(&img, size(), cvIplDepth(flags), channels());
cvSetData(&img, data, (int)step);
return img;
}

製作簡單圖表

開發過程中，常常需要偵錯，方法不外乎下中斷點、印訊息、寫檔，但想動態地觀察資料，就需要視覺化的呈現，像「ZedGraph」和「OWC11」都是不錯的選擇。但殺雞焉用牛刀，所以就自己寫個函式，配合 OpenCV 作呈現(因為他跨平台嘛)。

因為我的需求非常簡單，只要幫助我觀察資料就好，所以實作上非常簡單，在此不多加贅述，只要說明一下函式原型就好：

Broken Line(點我一下>///<)

bool BrokenLineGraph(IplImage *blImg, int *data,
int *range, int dataNum, bool reset);

1. 1st parameter：秀資料的圖檔。
2. 2nd parameter： 原始資料。
3. 3th parameter：資料範圍，range[0] = min；range[1] = max。
4. 4th parameter：資料量。
5. 5th parameter：是否刷新圖檔。

Histogram(點我一下>///<)

bool HistogramGraph(IplImage *hgImg, int *data,
int *range, int dataNum, bool reset, CvRNG *rng);

1. 1st ~ 5th：同上。
2. 6th parameter：亂數種子，用來取色。　

所以是非常簡單，對我而言夠用了。至於餵進來的資料多寡，會影響繪圖的結果，所以要提醒一點，圖檔寬度要大於等於資料量，或者分批丟進來！

為了加強跨平台的特性、與維持原始碼的"乾淨"，我使用 CMake 這個工具來產生 makefile，不過我只完成一半(windows)，有興趣的可以把另一半完成，至於詳細語法可以自行 google。

程式碼下載

參考資料：

• 井民全觀點(Jing's Perspective): [C++] 如何用CMake 來編譯最簡單的 OpenCV 範例 – open image
• [程式設計] 最簡單的 CMake 使用說明 – how to use cmake
• 貓也會的 CMake 備份
  

不同版本之滑鼠事件設定

OpenCV 在一兩個月前發布最新的 v2.0，對我而言，最大的差異就是「function prototype」，數量可說是不勝枚舉，但我們僅需了解其不同之處，修改應該不成問題，設定滑鼠事件就是一例。

滑鼠事件不外乎就是「左右鍵按下、放開」、「滑鼠移動」，不過這些都是簡單卻很重要的工具，例如：我們可以

1. 框出指定區域作物體追蹤。
2. 框出指定區域作直方圖統計。
3. 框出指定區域作影像擷取。

甚至這個方框可以動態讓使用者作調整，所以他的確是很重要的東西。恩！底下就針對差異點說明：

Set mouse callback function

• OpenCV b3.1

cvSetMouseCallback(const char* window_name, CvMouseCallback on_mouse);

• OpenCV 2.0

cvSetMouseCallback(const char* window_name, CvMouseCallback on_mouse, void* param CV_DEFAULT(NULL));

Mouse callback function prototype

• OpenCV b3.1

void MouseCallback(int event, int x, int y, int flags);

• OpenCV 2.0

void MouseCallback(int event, int x, int y, int flags, void *param);

很明顯地，新版多了一個參數「void* param」，這樣一來，就可以傳入一個結構，來記錄滑鼠座標，毋須定義全域變數。另外，還有一個外表看不出來的差異，就是舊版(b3.1)取得的滑鼠座標需要上下顛倒，但新版不用，詳細可以看原始碼。

Source Code Download

• GetRect by OpenCV b3.1
• GetRect by OpenCV b2.0

手動安裝 NVIDIA 顯示卡驅動程式

　　每次裝完 Ubuntu，驅動程式都會自動安裝完畢，即使沒安裝到的，也可以從「受限制的驅動程式」去啟動它(像是我的工作機)，不過，這次安裝 8.10 的機器，顯示卡是 GeForce 9700M GTS，受限制的驅動程式(173和177)都無法正常啟動，所以必須手動安裝。參考這裡，有詳細的說明，底下把重要的部份列舉出來：##ReadMore##

1. 到 NVIDIA 驅動程式下載中心找到你要的版本，像我就是下載 GeForce 9M 系列的。下載的檔明為 NVIDIA-Linux-x86-185.18.36-pkg1.run。
2. 修改檔案權限：chmod +x NVIDIA-Linux-x86-185.18.36-pkg1.run。
3. 移除安裝過的 NVIDIA 套件：csudo apt-get --purge remove nvidia-*。
4. 按 Ctrl+Alt+F1 進入文字模式。
5. 關閉 X window：sudo /etc/init.d/gdm stop。
6. 開始安裝驅動程式：sudo sh ./NVIDIA-Linux-x86-185.18.36-pkg1.run。過程中會去下載 kernel header，不過會下載失敗(我的 /usr/src/ 底下明明就有了)，但沒關係，還是可以編譯並安裝成功。
   
7. 重啟 X window：sudo /etc/init.d/gdm start。
8. 大功告成，利用 glxinfo | grep "OpenGL version string: 看到顯式卡的型號、以及 NVIDIA X Server Settings 修改解析度以及刷新率。

　　終於給這台 17 吋寬螢幕的 NB「1440x900」和「73 Hz」最後要提醒的一點是，如果有更新 kernel，記得要重新安裝驅動程式。

Mgestyk Gesture Based Control

　　Mgestyk 是加拿大的公司，利用 3D Camera 來做到三維影像的辨識，我只能說做得非常好...冏>。另外，Toshiba 出了「Cell-based SpursEngine」在 NB 和 LCD TV 上面利用手勢操作以吸引買家。從 Eij的碎碎唸 這篇看來，似乎 Toshiba 和 Mgestyk 有合作關係，還是說，根本是關係企業...。以下是 demo 影片：

Reference

1. Mgestyk Gesture Based Control
2. Toshiba 發佈手勢控制的 Cell-based 電視

diff && patch

　　這兩個指令一起使用等同於大陸人所說的「補丁」，目的就是當程式有新版的時候，用來替換舊版的做法之一，如果一個專案有需要多人一起修改，使用 patch 配合有意義的檔名，如：camera_preview.patch 會變得比較好管裡，因為可以掌握到底改過哪些地方。

首先，假設有兩個資料夾：

-baijuyi- [/home/Bachelor_91/linly/old] -13:48- ls
a.cc git
-baijuyi- [/home/Bachelor_91/linly/old] -13:48- cat a.cc
#include <iostream>

using namespace std;

int main()
{
    a = 3;
}

-baijuyi- [/home/Bachelor_91/linly/new] -13:49- ls
a.cc git
-baijuyi- [/home/Bachelor_91/linly/new] -13:49- cat a.cc
#include <iostream>

using namespace std;

int main()
{
    b = 3;
}

　　在兩個資料夾都有 a.cc 和 git，而 new 資料夾的 a.cc 檔案中，把 a = 3; 改成 b = 3;，現在要做 patch：

-baijuyi- [/home/Bachelor_91/linly] -13:52- diff -ruN old/ new/ -x git > my.patch
-baijuyi- [/home/Bachelor_91/linly] -13:53- cat my.patch
diff -ruN -x git old/a.cc new/a.cc
--- old/a.cc    2009-09-17 13:48:36.000000000 +0800
+++ new/a.cc    2009-09-17 13:48:04.000000000 +0800
@@ -4,5 +4,5 @@

int main()
{
-    a = 3;
+    b = 3;
}

　　其中有一個參數：-x git，是省略這個檔案不比，有時候會有一些說明檔在裡頭，沒有必要去 patch 它。接著就是打 patch：

-baijuyi- [/home/Bachelor_91/linly] -13:59- patch -p0 < my.patch
-baijuyi- [/home/Bachelor_91/linly] -14:16- cat old/a.cc
using namespace std;

int main()
{
    b = 3;  // =>改變了
}

　　這樣就完成程式碼的更新了，如果說我到 old/ 這個資料夾打 patch 的話，由於是往下一層，所以要把 -p0 改成 -p1。最後，因為我的用 patch，它會幫我把原先的舊檔案，以原檔名加上 .orig，所以想把這些檔案都刪除的話，可以利用 find 去做：

-baijuyi- [/home/Bachelor_91/linly] -14:03- ls old/
a.cc      a.cc.orig git
-baijuyi- [/home/Bachelor_91/linly] -14:03- find . -name '*.orig' -exec rm -f {} ';'
-baijuyi- [/home/Bachelor_91/linly] -14:03- ls old/
a.cc git

CUDA 簡介

　　最近受命去弄個 GPGPU(General-purpose computing on graphics processing units) 的 demo，對象就是 Nvidia 的 CUDA，這裡我找到一個還不錯的簡介，以 VS2005 來說明如何設定，雖然僅有兩個範例，但作者循序漸進，一步步地說明如何加快平行運算的速度。我只有看完第一個範例，另一個矩陣乘法有空再看:P。針對第一個範例「平方相加」，作者說明的流程依序如下：(GeForce 8800GT 1.5GHz)

1. 一個區塊與一個執行緒 -- 640M clock cycles (約0.43秒)
2. 一個區塊與 256 個執行緒 -- 8.3M clock cycles (約 0.0055 秒)
3. 同上，但改變執行緒讀取資料的方式 -- 2.6M clock cycles (約 0.0017 秒)
4. 32 個區塊與 256 個執行緒 -- 150K clock cycles (約 0.0001 秒)
5. 同上，但個別區塊先利用 shared memory 做加總 -- 164K clock cycles (約 0.00011 秒)
6. 同上，但改變在 shared memory 的加總方式 -- 136K~140K clock cycles (約 0.00009 秒)
   

　　這個網頁後面還有介紹支援 CUDA 的 GPU 架構，包含 global memory、shared memory、multi-processor 和一些 cache。像要給 GPU 處理的資料就會先複製到 global memory，而執行緒在存取這個記憶體時會有 latency，所以需要建立多一點執行緒來隱藏延遲；shared memory 相當於 cache，比起前者，延遲可以忽略，但是，當多個執行緒存取同一個 bank(4 bytes) 就會發生衝突，所以就要重新考慮資料的擺放方式；還有，精確度、運算單元、和其它 cache 的介紹、總之，這個網頁值得看看。

　　我手邊拿到的筆電，顯示卡為「GeForce 9700M GTS」，搭配的驅動程式版本是 177.19，但是，官網針對 Windows Vista 32 bits 提供的 CUDA 版本至少是 2.0(驅動程式版本為 178.08)，幸好可以安裝，不過安裝 CUDA 2.3 失敗啦！而顯示卡資訊如下圖：(雖然安裝 2.0 版，不過顯示結果只支援到 1.1 版)


矩陣乘法之時間比較：(單位：秒)

               CPU            GPU
500x500        0.188          0.109
1000x1000      6.131          0.202
3000x3000      200.819        5.241
5000x5000      1222.182       12.480

　　如果你的筆記型電腦或者桌機的顯示卡不支援CUDA，那麼，cudaGetDeviceProperties 只能抓到一個虛擬裝置「device 0」，而該裝置內容如下：


　　做平行計算所探討的議題、思考的方向和做法，是我以前沒有接觸，或者甚少接觸的部分，即使看得懂，也需要許多的時間去消化吸收，爾後才能靈活運用(高微看得懂和寫得出來是兩回事)。而且，最好要能掌握顯示卡提供的硬體資訊，例如：最多可以產生幾個區塊、幾個執行緒、shared memory 有多大、有幾個暫存器，因為這些資訊都會影響資料的切割、存取，及演算法的修改，可以說是針對板子去寫平行的程式，所以像是 cublas、cufft 這些函式庫，我猜硬體資訊都已參數化。最後，開越多的執行緒或許越能隱藏 latency，但相對地，每個執行緒能分配到的資源就會越少，這是需要衡量的地方。

參考資料：

• 支援 CUDA 的顯示卡列表
• CUDA Zone Taiwan
• CUDA in Ubuntu ref 1
• CUDA in Ubuntu ref 2
  
• 批踢踢 VideoCard 板 a5000ml 的文章

其它膚色模型

　　除了之前介紹的 Bayesian膚色模型(YCbCr)，其實還有許多不同色彩空間的膚色模型，如：RGB、YUV、YCbCr、HSV、HSL、Normalize RGB 等等，底下再秀兩個膚色模型。

● YCbCr

Y = 0.299*data[2] + 0.587*data[1] + 0.114*data[0];
Cb = -0.1687*data[2] - 0.3312*data[1] + 0.5*data[0];
Cr = 0.5*data[2] - 0.4183*data[1] - 0.0816*data[0];

if(60 < Y && Y < 255)
{
    if(-25 < Cb && Cb < 0)
    {
        if(10 < Cr && Cr < 45)
        {
            // skin
        }
        else
        {
            // non-skin
        }
    }
    else
    {
        // non-skin
    }
}
else
{
    // non-skin
}

● Normal RGB

double r;
double g;
double b;
double F1;
double F2;
double w;
int size = 320*240;
Byte* data = (Byte*)scan0.ToPointer();

for(int i = 0; i < size; ++i, data += 3)
{
    if(data[0] == 0 && data[1] == 0 && data[2] == 0)
    {
        r = g = b = 0;
    }
    else
    {
        r = (double)data[2]/(data[2]+data[1]+data[0]);
        g = (double)data[1]/(data[2]+data[1]+data[0]);
    }

F1 = -1.3767*r*r + 1.0743*r + 0.1452;
F2 = -0.776*r*r + 0.5601*r + 0.1766;
w = (r-0.33)*(r-0.33) + (g-0.33)*(g-0.33);

if((g < F1) && (g > F2) &&
   (w > 0.0004) &&
   (data[2] > data[1]) &&
   (data[1] > data[0]) &&
   (data[2] - data[1] >= 16))
    {
        // skin
    }
    else
    {
        // non-skin
    }
}

　　後者是我目前用過效果最好的膚色模型，在白光或者黃光的環境都表現得不錯。但是，不論多麼好的膚色模型，想要應付各種外在因素的影響，還是顯得不足，畢竟拿到的影像，顏色都被干擾了。

相關閱讀：

• Baysian 膚色模型

Baysian 膚色模型

　　在做人臉、手勢辨識時，最直覺的做法就是先找膚色，這裡就介紹一下 Bayes 膚色模型。這篇論文是利用條件機率，將每對 (Cb,Cr) 都賦予一個「是否為膚色」的標籤，待訓練完後，每給定一個 (R,G,B)，只要轉換到 YCbCr 就可以知道是否為膚色。

　　論文中所提及的一些式子，如式 (3)、式 (4)，是用成本的概念來說明，如樣本 X 判斷成膚色的成本小於判斷成非膚色的成本，就把樣本 X 決定成膚色。至於其它係數就不用管他，只要知道最後一個實驗出來的結果值：Alpha = 2，剩下就是條件機率的使用了。

　　至於要如何訓練，首先要收集一堆 training data，並且把每一張圖片都一分為二：膚色 & 非膚色，也就是說針對某一張圖片，把膚色以外的區域弄成白色，產生一筆 skin data；非膚色以外的區域弄成白色，產生一筆 non-skin data，這裡需要的是人工篩選的動作。接著，開始一一統計以下四個變量：

1. 膚色點的總數。
2. 非膚色點的總數。
3. 每對 (Cb,Cr) 膚色點的數量。
4. 每對 (Cb,Cr) 非膚色點的數量。
   

　　然後根據論文的式 (10) 與式 (11) 計算每對 (Cb,Cr) 膚色和非膚色的機率，歸類完即可產生一個 225x225 的 training model 了。

　　Bayes 條件機率是不錯的觀念，不少演算法以此為核心發展出來，如：Bayes Classifier，甚至有寫成一個函式庫，裡頭都是用條件機率去做的。不過，用條件機率，很大的問題會取決於所收集的資料特性，甚至當正反兩個結果的機率差不多時，準確度就會大大下降。

程式碼下載

相關閱讀：

• 其他膚色模型
  

花蓮行第三天

早上起來，將窗簾拉開，群山連綿，還有白雲做點綴，放眼望去景色超棒的。我們盥洗完就去一樓大廳排隊吃早餐，這裡中、西式種類非常齊全，真是享受。吃完就去飯店內的店家逛逛，以及到外面的草坪、人工瀑布照照相。














有鑒於昨天頂著太陽騎車的辛勞，今天決定搭接駁車去兆豐農場，大約12點20分，我們到花蓮火車站附近的旅客服務中心等車，接駁車一趟要150元，大約40分鐘的車程，那到邊買完票、安置行李，就去租一台電動車，因為兆豐占地七百多公頃，不可能用走的啦...|||。這裡很像是動物園、植物園和昆蟲園(有這種東西嗎=_=)的綜合體，我們就走走停停，看到有趣的東西就下車看看，我們有餵鴿子、餵山羊，看別人餵小牛XD，讓我驚訝的是，才出生一天的小牛就可以長得這麼大！我們還吃了$40的牛奶冰淇淋，不錯吃耶，兆豐農場值得來一次。











回到市區，我們就去買名產，我和Jerry合買一盒大麻糬，我另外買了一包黑糖小麻糬，而且拿過期的交大學生證打九折ＸＤ。吃完晚餐，就去車站等七點多的自強號，這次沒機會搭到太魯閣號，所以需要兩小時四十分的車程，差好多冏>。

這次三天兩夜花蓮旅遊還算玩的盡興，也有好有壞，好是好在享受自行規劃的樂趣，想去哪就去哪；壞是壞在沒有人會開車就只能搭車或者騎機車，而且花費會高一點。明年員工補助有$7500，也許就跟團了，另外，公司快點把三人成行的狗屁規定給取消掉(／‵Д′)／~ ╧╧。


花蓮行第一天
花蓮行第二天
三天兩夜花蓮行程

花蓮行第二天

一整夜都被鼾聲吵到無法入眠，所以一大清早就起床看棒球，外勞大約九點把早餐送來，是三明治加奶茶，吃完休息一下就打包行李準備離開，前往美崙飯店放行李。今天的行程會先去鯉魚潭，然後再去東華大學，這兩處都在壽豐鄉。

去鯉魚潭的過程挺辛苦的，因為頂著大太陽騎機車，實在是熱得要死。這裡的優點是風景不錯，可以騎著水上腳踏車四處欣賞，不過一人要一兩百塊，而且肚子餓又不想流汗，所以就放棄了XD。





晃了一個小時左右，就去附近的海產店吃飯(還是吹冷氣比較實在)，等到太陽沒那麼烈，就離開前往東華大學，這是第二次到這間學校，不過上次有車可以開進去，這次就沒這麼幸運，因為學校規定除非是學生的機車，否則只有汽車可以換證進入，掯！學校這麼大，要我們累死在裡頭就對啦ˋˊ。不過，既來之，則安之，就硬著頭皮「逛校園」吧！喔，對了，逛校園之前有先去咖啡廳坐了一下，等太陽不見了再出來，哈哈。這裡頭的景色還是挺不賴的，我們四處拍照，以及玩飛盤，在學校耗了將近兩個半小時才離開。













至於晚餐，我們決定吃歐鄉牛排西餐，這家牛排館在北部僅永和有分店，消費範圍從$320到$640不等，我則是鱈魚併沙朗牛排($460)。這裡的東西吃起來都還算不錯，特別要提的是，他們的紅茶超好喝的，非常甘甜，但我猜其它分店就沒這個優點了。吃完也已經九點，我們回到美侖飯店，去打了一下桌球和壁球。這次行程的一個缺點就是，應該要在美侖飯店待上一整天，做SPA、游泳玩水、玩裡頭的設施，可惜阿～。









花蓮行第一天
花蓮行第三天