HOWTO: 在Macbook上DIY窮人的multi-touch (Part 3 – END)

這篇文章將接續這個系列Part 1Part 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更新)

23 thoughts on “HOWTO: 在Macbook上DIY窮人的multi-touch (Part 3 – END)

  1. vgod~不好意思因為我本身就是在做這個的啦…….Orz 專業魂發作

    有沒有考慮手指不帶套的作法呢?..因為根據我的經驗其實紅外線對人肉也是會反射的啦 人肉鹹鹹
    只是你可能要做一些簡單的background removal, 進而抓出移動中的手指這樣…

    另外tracking可能不能只考慮位置(這個你也知道啦)
    如果能加入速度的資訊可能就會比較準一點吧 單南tracking的問題從80年代開始就已經有人做了
    如果真的要認真implement的話 搞不好可以讀完另外一個碩士 XD

  2. 也許tracking可以考慮用optical flow喔,效果應該也不錯,不過能這樣從無到有做出一個prototype,而且單純以興趣為出發點,真的很難得。

  3. wadanabe:
    哈哈 我很需要作vision方面人的指教, 說實在我完全沒接觸過vision的東西, 連這方面的課也沒修XD
    我試過用人肉反射, 效果不是很好. 我想應該是紅外線不夠強的關係.
    但你也看到我才用了48顆LED就那麼大一球了, 我可不想掛個100顆在螢幕上面.. :p

    wadanabe&Season:
    tracking的問題真是博大精深阿, 我後來有找些paper來看.
    能用的方法還蠻多的, 但你們也知道這只是要做個還ok的prototype, 這方面就先不用那麼講究了:p

  4. 很好玩的想法,沒想過鏡頭可以這樣用。
    我想,可以不要將紅外線固定在鏡頭上,而改成是拿在手上旳一支筆的方式,上面可以用三個紅外線 LED 加上一個可見光的 LED ,這樣子就可以直接點螢幕了吧!
    用三個 LED 排成一上二下,是可以作出角度的辦別,而可見光的 LED 是給 人看的。
    這樣就不用在手上貼東西了。

  5. 您好,我有下載您提供的完整原始碼:BlobTracker ,裡頭有四個檔案,是直接執行main就可以了嗎?Debug後仍有錯誤,謝謝。

  6. hello

    我下載你的 code .. compile 後 running 沒有問題
    真是感謝~ 這是我想找的東西
    哈~我已經放棄 install touchlib on mac osx…

    小小小小一個問題~
    請問那個 blob tracker 的 window..要怎麼關掉?!
    我直接按 紅色的 x .. 關掉之後,會出現 error message..
    “the application … quit unexpectedly”..

    thank you..

  7. 阿阿阿阿~~我好蠢~

    對不起~剛剛問了白癡的問題~
    看了一下你的 code 發現原來按 esc 就可以正常關掉了~

    @_@

    哈~給你的留言站位置 -_-

    再次感謝你詳細的資料..

  8. LL:
    希望你玩得開心:p

    順便一提,其實我已經把支援TUIO的版本寫出來了。只是一直沒放上來,如果有人需要我再找時間整理一下放上來。

  9. 你好,请问一下你研究过touchlib的源码吗?touchlib只能读AVI或者摄像机(USB的),我想让它读我的BITMAP,该怎么办,谢谢

  10. guoboxue:
    touchlib是靠OpenCV來讀取動態影像輸入。
    你的Bitmap是靜態影像,如果你想要用很多張串成動態影像的話,只能先用其他軟體把Bitmap合併成影片,再餵給touchlib吃了。

  11. 你好我在WWINDOWS的VC6.0編譯會有錯誤產生,不好意思就是可以給我ㄧ份完整的程式碼或是執行檔嗎?對這方面還蠻有興趣的….感謝

  12. 您好,我載了您的程式,
    在VS2008版建置時顯示Event.h檔有錯誤,
    不知道是否後來有更新過?
    因為現在在做專題有用到視訊這方面的東西,
    和您的程式非常相關,所以希望可以參考程式碼。
    先說聲感謝囉。

    • 目前放程式碼的那台server掛掉了,等它恢復後就可以正常下載了。(我想大概要到星期六才會好吧XD)

    • Hi eddy,
      我的server已經恢復運作了。因為DNS更新的關係,可能要等上24hr才能連到新server的位置。
      如果之後還無法下載,再麻煩通知我囉。

  13. 拜讀你的文章,覺得很有趣,
    不過我是外行,想請教一下,
    自訂的event轉成TUIO message送出 <– how to do it ?
    非常感謝!!

  14. ”因為我不知道怎麼偽裝成OS X的multi-touch event長什麼樣,也不知道怎麼塞到OS的event queue中。說不定Mac OS X根本就還沒有multi-touch event這種東西。“
    你好,上面你说的问题现在研究出来了吗,Mac OS X有没有multi-touch event,或者要怎样才能偽裝成OS X的multi-touch event。

留言給我吧!