這篇文章將接續這個系列Part 1及Part 2的說明向大家說明multi-touch背後軟體運作的原理。這篇文章會盡量用簡單的方式說明原理和實做，希望能讓懂得基本程式設計的讀者都能看懂。

這篇文章會說明怎麼從攝影機中擷取圖片，並取得手指所反射出的光點位置，並對每個點做追蹤。下圖是同時追蹤四個手指的範例：

在上一篇已經介紹過我們所需要的硬體，包括紅外線投射燈、紅外線攝影機、及反光貼片。這些硬體很重要的功能是讓我們雙手的手指頭能反射大量紅外線，透過紅外線濾光片的協助，我們的攝影機(iSight)就只會看到手指頭產生的亮點，而不會看到其餘和手指無關的背景。

上圖為我們的攝影機所看到的畫面，畫面中除了手指上兩塊方形反光貼片外，其它什麼都看不到。這樣子的畫面，對於電腦來說遠比一般含有整個手掌、人、背景等圖片還來得容易處理，而我們用紅外線來替代原本的可見光的用意就在這裡。

接下來，我們將開始解說怎麼利用這些影像來取得手指的位置，進而追蹤每隻手指的移動過程。我們將利用C++寫個程式出來分析這些影像，並將結果變成上層應用程式可以接受的event。整個程式需要做的事，簡單說來可以分為以下這些步驟：

1. 從攝影機擷取影像
2. 從影像中找出每個亮點中心的位置
3. 對於之後擷取到的每張畫面追蹤每個亮點位置的變化
4. 產生對應的event，發送給上層的應用程式做處理

從攝影機擷取影像

在這邊我推薦用Intel的OpenCV來做處理。OpenCV是非常有名的電腦視覺函式庫，提供了一大票的電腦視覺及影像處理相關函式，甚至連從攝影機擷取影像都能幫你解決。OpenCV還有個好處是它是跨平台的函式庫，在各大平台都能運作，所以我們接下來寫的程式除了在Mac上外，也能在Linux及Windows上運作。

要開始找出亮點位置前，我先簡單交代一下怎麼用OpenCV從攝影機擷取影像出來(以下程式碼都用C++填寫)。

#include <cv.h>
#include <highgui.h>

int main(int argc, char** argv)
{
   CvCapture* capture;
   IplImage *img;
   capture = cvCaptureFromCAM(0);
   cvNamedWindow("mainWin", CV_WINDOW_AUTOSIZE);
   cvMoveWindow("mainWin", 0, 100);
   while(cvGrabFrame(capture)){
      img=cvRetrieveFrame(capture);
      // process img here ...
      cvShowImage("mainWin", img);
      int key=cvWaitKey(10);
      if(key == 27) // 27=ESC
         break;
   }

   cvReleaseCapture(&capture);
   return 0;
}

上面是OpenCV從攝影機擷取影像並畫在一個視窗內最基本的程式碼，我們之後對於影像所有的處理都插在第14行那裡就可以了。

偵測亮點位置

觀察我們取得的影像可以發現，我們要找的亮點是實心的方形，且沒有特定顏色和圖樣。所以要找出這些亮點中心的位置其實很簡單。第一步，我們可以先去除顏色，將全彩(RGB 24bits)轉為只有兩種顏色（黑白）的影像。而剩下來白色的部份就是我們感興趣的區塊。

在OpenCV中，我們需要先將含有3個channel (RGB)的輸入轉為單一channel的灰階圖。灰階圖的意義是它只包含了亮度的資訊，最亮的地方會是白色(255)，最暗就是黑色(0)。得到灰階圖後，我們就可以設定一個threshold，將一定亮度以上的pixel全變成白色，剩餘的地方全設成黑色。透過這樣子得到的圖片將只剩下黑白兩色，對於我們之後的處理會簡單很多。這部份的程式碼很簡單，我把它寫成了一個稱為convertToBinary的函式，其中設定threshold為40，也就是說值超過40的pixel都會變成255，剩餘都變0。

#define BINARY_THRESHOLD 40

IplImage* convertToBinary(IplImage *in, IplImage *out){
   cvCvtColor(in, out, CV_BGR2GRAY);
   cvThreshold(out, out, BINARY_THRESHOLD, 255, CV_THRESH_BINARY);
}

處理後如下面兩張圖所示，左邊為灰階，右邊為黑白兩色。

下一步我們要掃描整個畫面，找到這些白色區塊的位置和形狀，接著就能計算出中心位置。OpenCV提供了一個函式稱為cvFindContours，這個函式能在畫面中找到白色區塊的輪廓(contour)。有了輪廓後，就能透過cvBoundingRect找到這個輪廓的bounding box，也就是我們所要的白色區塊位置。

下面的函式findBlobs需要一個只含黑白兩色的圖作為輸入，它可以找出圖中所有白色區塊的位置，但目前還不會輸出任何東西。找出輪廓後，可以用14~18行的程式碼把輪廓和bounding box畫在debug_img上。（通常我們會開另一個視窗專門畫這種debug用的畫面）

void findBlobs(IplImage *bin_img, IplImage *debug_img){
   static CvMemStorage *storage = cvCreateMemStorage(0);
   CvSeq * contour;
      
   cvFindContours( bin_img, storage, &contour, sizeof(CvContour),
       CV_RETR_CCOMP, CV_CHAIN_APPROX_NONE);
      
   for(; contour; contour = contour->h_next){
      CvRect rect = cvBoundingRect(contour, 1);
      CvPoint pt1 = cvPoint(rect.x, rect.y),
              pt2 = cvPoint(rect.x+rect.width, rect.y+rect.height);
      // The center of rect is (rect.x+rect.width/2, rect.y+rect.height/2)
      if(debug_img){
         cvRectangle(debug_img, pt1, pt2, CV_RGB(255,0,0),2);
         cvDrawContours(debug_img, contour, 
            CV_RGB(255,0,0), CV_RGB(255, 0, 0), 0, 2, 8);
      }

   }
}

下面兩張圖即是OpenCV找到的輪廓和bounding box。

光點追蹤

經過上面兩個函式的處理，我們已經能在攝影機擷取出的每個frame標定出光點的位置。但我們要做的可是multi-touch的介面，也就是說每個frame會有不定個數的亮點，可能只有1個，也可能有2個，甚至有10個。我們必須持續追蹤這些亮點的變化，包括每個點是什麼時候出現、中間移動的軌跡、以及什麼時候消失的。在OpenCV中有提供現成的tracker CAMSHIFT，但它實在太複雜，我還沒有時間把它搞懂，所以我決定自己寫一個簡易版的tracker。（所謂的簡易版就是沒那麼完美，可是大部分情況是work的）

如果我們的tracker只面對一個點，那麼問題很簡單。在下圖中，圓形為前一個frame光點的位置，方形為目前這個frame的位置。在單一個點的情況，可以直接斷定圓形和方形是同一個光點，並且移動路徑是A。

但如果是多點，情況就沒這麼單純了。下圖展示了兩個點的情況，我們要怎麼判斷兩個光點是走了路徑A或路徑B呢？也就是說這兩個方形，到底誰是光點1？誰是光點2？

其實上圖還有更複雜的可能，像是光點2其實已經消失，而某個方形是新出現的光點3。在每個光點都是相同的情況下，其實我們是沒辦法區別這種奇怪的可能性，所以為了簡化我們先暫時忽略這種可能。在這個問題上，我用一個簡單的策略來解決：在兩個frame間，相對位移距離越短就越可能是相同的一個點。也就是說在上圖中，上方的方形應該是點1，下方是點2，因為這樣子兩個點移動的距離都比較短。

這個問題如果要求全域的最佳解（讓每個點移動的距離和最短），可以轉化成圖論中的Bipartite matching問題來解。但在這篇以簡單易懂為前提的教學中，我們還是用簡單的方法吧。我的配對方法如下：

1. 假設前一個frame的所有光點集合為A，目前frame的則為B
2. 對於A中的所有點a，計算出到B中所有點b的edge長度，並放進一個陣列E中
3. 把陣列E中距離太遠的edge剔除掉
4. 將E按edge長度排序，從小排到大
5. 從E的開頭開始，每取出一條edge前先看看edge的兩端點是否已經配對成功過，若兩端沒有則標記兩端點為同一光點
6. 重複上一步直到取出所有edge為止

跑完上面的演算法，我們就可以標記出兩個frame中所有對應的光點，並且可以產生出對應的FINGER_MOVE event。而A和B中剩下來沒被配對到的點，就代表這些點只存在其中一個frame，要不是剛消失就是剛出現，所以我們就能把它們分別對應到FINGER_UP及FINGER_DOWN event。

採用這個簡單的策略，就能很快解決這個配對問題，還能順便產生出對應的event出來。詳細的程式碼太長就不列在這邊，有興趣的可以看下載整個原始碼回去看BlobTracker.cpp。

與multi-touch應用程式的結合

到此我們已經能順利辨識並追蹤畫面上的多個光點，並產生出上層應用程式所需的event。但要怎麼把這些event送出去呢？這部份目前仍是一片迷霧，因為主流作業系統都還不支援multi-touch API。在缺乏有力的標準下，目前許多multi-touch應用程式是使用TUIO protocol。但我比較想直接和作業系統結合，所以我還在研究這部份要怎麼解決。

下載

這篇文章所用的完整原始碼：BlobTracker (有人需要執行檔嗎？）
2008-07-27更新: 釋出支援TUIO的BlobTracker(這個版本需要oscpack，我已經附在裡面，但注意非OS X平台必須自己重新make過oscpack內的lib。)
基本上在各個平台只要有g++和opencv，打make就能編譯完成。
在Mac OS X下需要另外安裝xcode和opencv。opencv可以用darwin ports安裝。

相關討論

這篇文章所敘述的演算法並不是完美的，已知有下列問題：

• 當兩個光點相黏在一起時會變成一個。這是因為我們直接找connected component的輪廓當作光點的關係，比較好的作法進一步是比對光點的形狀。
• 光點追蹤的演算法算出來的配對不是全域最佳解。改用CAMSHIFT可能(?)會比較好。

FAQ

Q: 這三篇文章介紹的東西能在Macbook以外的notebook上用嗎？
A: 當然可以。硬體跟作業系統無關，軟體是跨平台的，只要有OpenCV就能跑。唯一要注意的是有的攝影機內建了IR-block filter，會把紅外線擋掉，碰到這種就不能用了。實驗方法是隨便拿個遙控器對著攝影機按，看會不會發光就知道了。

Q: 這樣做出來的multi-touch能操作Mac裡支援multi-touch的程式嗎？
A: 目前還不可以。因為我不知道怎麼偽裝成OS X的multi-touch event長什麼樣，也不知道怎麼塞到OS的event queue中。說不定Mac OS X根本就還沒有multi-touch event這種東西。

Q: 那做出來的東西可以幹麼？
A: 只要把我自訂的event轉成TUIO message送出，就可以驅動所有支援TUIO的multi-touch應用程式。但如果沒寫這段，就…….只能給自己娛樂用。

Q: 之後會釋出支援TUIO的程式嗎？
A: 如果我沒研究出來怎麼送Mac OS X的event應該就會改用TUIO。
A: 已經釋出。(2008-07-27更新)