RIVF 2010 – First day (2/11/2010)

Buổi sáng: Keynote về Security trong Cloud Computing, query on Encrypted Databases etc…

Buổi chiều: Session HCI:

Đặt cục gạch ở đây trước, khi nào rảnh sẽ cập nhật tiếp.

Advertisements

68 comments

  1. Chao Vu, ban co tim hieu ve SIFT kkhong? Minh da hieu so so SIFT la gi roi, nhung van con co mot so cau hoi thac mac? Khong biet ban co tim hieu SIFT chua?

  2. 1) Ah, co nhieu thac mac 🙂 . Theo minh duoc biet thi SIFT bat bien voi scale la vi khi lay maxima, minima cua Gaussians tai mot scale s, thi tai scale khac cai diem day van la maxima va minima, nen no bat bien voi scale. Khong biet minh biet vay dung khong? :).
    2) Tai sao phuong phap lai lam cho anh bat bien trong mot local image region thay vi chi bat bien voi image key thoi?
    3) Minh chua hieu ro lam ve viec gan orientation? Minh gan tuy y so bin? Minh thay tai lieu ghi patch 16×16, do la kkich thuoc chuan?
    4) Minh khong hieu vai tro cua down-sample trong first stage cua SIFT, downsample de lam gi? Downsample xong thi co tim maxima, minima nua khong? Hay chi tim extrema tai anh goc da bi blur thoi? Downsample den level bao nhieu thi stop.
    5) Minh se gan orientation cua anh da bi downsample hay cho anh goc?
    6) Sau khi tinh toan xong, lam cach nao de index va matching cac key nay?
    7) Minh doc mot so tai lieu thay design mot classifier, dua tren tap training data, cho biet mot object co xuat hien trong anh hay khong bang cach threshold mot so SIFT match. Minh khong hieu ky thuat threshold va design classifier nay y tuong chinh la gi? De lam gi? Va nhu the nao?

    Nhieu qua phai khong ban? 🙂 Noi that minh rat can mot so giai thich cua ban de giup minh hieu ro hon ve ly thuyet nay. Cam on ban nhe.

  3. Hi trang,
    Nội dung chính của SIFT là gồm 2 bước:
    – Detector: phát hiện interested points (keypoints). Ở đây SIFT dùng detector là DoG.
    – Descriptor: sau khi phát hiện interested points thì cần có 1 cách để biểu diễn interested point đó thành một feature vector, và đó là nhiệm vụ của Descriptor. Descriptor của SIFT cho ra feature vector có 128 phần tử, như trong paper.
    Ý tưởng chính như vậy, sẽ giúp hiểu rõ hơn về SIFT, cụ thể các câu hỏi của bạn:

    1. Không. SIFT bất biến với scale là do khi tính descriptor, SIFT tính ở scale của keypoint. Tức là trong bước detect, nó phát hiện keypoint ở scale nào, thì sẽ dùng ảnh ở scale đó để tính descriptor. Cái này được nói trong section 5 của paper “Distinctive Image Features from Scale-Invariant Keypoints”.

    2. Bản chất của SIFT là chọn ra 1 số keypoint, rồi dùng descriptor để đặc trưng cho một vùng 16×16 pixel xung quanh keypoint (đặc trưng bằng 1 feature vector 128 phần tử). Nhờ đó các feature vector của SIFT là bất biến với 1 local image region.

    3. 16×16 pixel là kích thước chuẩn. Số bin là 8. Tại mỗi keypoint có 4 x 4 = 16 subregion, mỗi subregion là 4×4 pixel và được chia vào 1 histogram có 8 bin, như vậy mỗi keypoint sẽ tạo ra feature vector có 16×8=128 phần tử. Đây là những số liệu chuẩn mà Lowe dùng.

    4. Câu hỏi về Downsampling cũng hay. Theo mình hiểu thì DoG hoạt động bằng cách liên tục apply Gaussian filter lên ảnh với sigma tăng dần, cuối cùng tạo thành một tập ảnh mà ảnh sau “nhòe” hơn ảnh trước. Trong suốt quá trình này, kích thước ảnh không đổi.
    Tuy nhiên Lowe xấp xỉ quá trình này bằng cách cứ mỗi khi sigma của Gaussian filter tăng gấp đôi thì lại downsampling ảnh 1 lần, và reset sigma lại như ban đầu. Giả sử ban đầu chọn Gaussian filter có variance là \sigma_0, sau đó với các ảnh sau lần lượt là k\sigma_0, k^2\sigma_0, k^3\sigma_0... đến khi nào bằng 2\sigma_0 thì không tăng variance nữa, mà downsampling ảnh còn 1/4, rồi lại dùng Gaussian filter với \sigma_0, k\sigma_0, k^2\sigma_0.... Cứ như vậy. Cứ mỗi một đoạn tăng gấp đôi của sigma thì Lowe gọi là một octave (quãng tám, theo mình cái này gọi là “quãng tám” là bắt nguồn từ âm nhạc: cứ mỗi quãng tám thì tần số âm thanh tăng gấp đôi). Như vậy thay vì tăng thêm sigma, ta downsampling ảnh. Cách này có ý nghĩa tương tự, nhưng lại giảm chi phí tính toán (Vì sau mỗi octave, số pixel giảm xuống 1/4).
    Downsampling liên tục, lâu rồi nên mình không nhớ rõ là Lowe có nói khi nào thì dừng không, nhưng mình đoán là chắc phải có chặn nào đó (tối đa n octave, hoặc khi kích thước ảnh nhỏ hơn nxn nào đó)

    5. Orientation là hướng của mỗi keypoint. Hướng biến thiên gradient (để đặt vào trong histogram) là hướng biến thiên độ sáng của ảnh sau khi đã downsampling và apply Gaussian filter.

    6. Về căn bản, sau khi đã có 1 tập các feature vector, mỗi vector có 128 chiều, thì bạn có thể dùng DBMS hay data structure bất kì để index và search, query… Nhưng Lowe dùng kd-tree và giải thuật nearest neighbors. Đây là những vấn đề kinh điển, bạn có thể đọc thêm trong các sách căn bản về data structures và algorithm.

    7. Về ý tưởng thì một “classifier” có nhiệm vụ phân loại một “đống” dữ liệu. Kiểu như khi gửi xe thì xe máy và ô tô được đưa vào các bãi khác nhau, khi đó người giữ xe đóng vai trò classifier, còn xe máy và ôtô của khách là dữ liệu (dân ML gọi là samples, còn dân Statistics gọi là data).
    Trong trường hợp này, mình chưa rõ lắm nhưng có lẽ classifier có nhiệm vụ phân loại ảnh dựa trên SIFT. Như vậy giả sử bài toán là phân loại ảnh quả táo và ảnh quả lê. Tập training sẽ gồm ảnh táo và lê (biết trước ảnh nào là táo, ảnh nào là lê). Sau đó tập training được đưa vào lấy đặc trưng SIFT. Tất cả các feature vector của táo được cho vào 1 nhóm, tất cả feature vector của lê cho vào một nhóm. Khi một ảnh test mới đưa vào thì nó cũng được tính SIFT, sau đó đem so với nhóm feature vector của táo và lê, match với bên nào nhiều hơn thì ảnh test thuộc nhóm đó.
    Cái này là mình đoán thế thôi, và rất là naive. Do mình không biết dữ liệu và bài toán cụ thể của bạn nên chỉ nói được chung chung.

    Bạn không cần lo lắng, trả lời cũng là cách để mình có dịp xem lại và củng cố kiến thức 😀

  4. Chao Vu, minh van thay con mot so confuse, muc so 5, neu nhu orientation la huong gradient sau khi da downsampling thi theo minh nghi descriptor se duoc tinh toan tai level thap nhat, tuc la tat ca cac patch da duoc downsample xuong cung 1 size 16×16.
    Minh van chua hieu sau khi downsample co tiep tuc tim kiem keypoint nua ko? Vi theo minh nghi, neu o size ban dau vi du 640×640 chang han, ban tim dduoc 20 keypoint, ban downsample xuong size 320×320 thi co tim duoc them key point moi o size nay khong? Hay viec tim kiem la vo nghia (tuc la so keypoint van nhu cu, van vi tri ay, va van la 20 keypoint) Nhu vay downsample o day co the nao la lam cho kich thuoc patch co cung mot chuan la 16×16 hay khong?

  5. Mình chưa rõ lắm tại sao bạn lại confused ở đây. Như mình đã nói, trong bước detection, ảnh ban đầu sẽ vừa được apply Gaussian filter, vừa được downsampling. Trong mỗi octave các ảnh kế tiếp nhau được trừ cho nhau (DoG), và các frame kết quả được dùng để so sánh và tìm local maxima/minima. Như vậy sẽ rất khó có chuyện ở kích thước 640×640 tìm được 20 keypoint thì xuống 320×320 vẫn chỉ có 20 keypoint đó. Tại vì trong ảnh 320×320 thì lượng thông tin đã ít đi (số pixel trên ảnh giảm), đồng thời tác dụng của Gaussian filter với cùng một sigma lên ảnh 640 và ảnh 320 là hoàn toàn khác nhau. Nếu bạn apply gaussian filter có variance là \sigma_0 lên ảnh 320, xong lại upsampling ảnh đó lên 640, thì nhìn sẽ hoàn toàn khác với việc bạn apply Gaussian filter có variance là \sigma_0 lên ảnh 640 ban đầu. Hơn nữa trong bước descriptor, vì kích thước patch lúc nào cũng là 16×16 nên lượng thông tin thu được trong ảnh 320 sẽ khác với trong ảnh 640. Có thể hiểu nôm na là cùng một cảnh vật nhưng nêu nhìn gần (ảnh 640) thì bạn sẽ phát hiện m điểm “quan trọng”, còn khi nhìn từ xa (ảnh 320) thì sẽ phát hiện được n điểm “quan trọng”. (Cùng là một cái cây, nhưng nếu nhìn gần thì có thể phân biệt cành, lá… nhưng nhìn từ xa thì chỉ phân biệt được gốc với ngọn). Cái này có nền tảng từ lí thuyết scale-space (http://en.wikipedia.org/wiki/Scale_space).

    Theo đó thì mình không thấy lí do gì để “descriptor được tính tại level thấp nhất”. Tại vì downsampling trên ảnh, chứ không phải trên patch. Kích thước patch luôn cố định 16×16, do đó ngay cả khi vị trí keypoint là giống nhau thì thông tin trong descriptor cũng không hoàn toàn giống nhau. Thực tế thì descriptor của sift được tính tại scale mà nó phát hiện ra keypoint.

  6. Cho minh hoi vai cau basic, scale invariant la gi, khi minh scale to len, scale nho xuong thi ccai gi khong thay doi? Minh biet feature khong doi, nhung ko biet la khong doi cai gi?

    Rotation invariant cung vay, xoay thi khong doi, nhung cai gi khong doi?

    Neu theo phan tich so so o tren, thi minh khong thay co ly do gi can thiet de downsampling nhi 🙂 Vay co phai no la mot buoc du thua cua giai thuat khong?

  7. Minh xin loi ban, y minh la minh phan tich so so chu khong phai ban. Ban dung hieu nham y minh nhe. Ban phan tich rat ky luong, hieu rat thau dao. Ma minh van con dang lan quan cau hoi muc dich cua downsampling va vi sao dac tinh invariant lai la cua mot patch chu khong phai cua mot keypoint. Minh van chua hieu hien tuong scale invariant va rotation invariant, dieu gi se xay ra, hien tuong gi khien nguoi ta noi no invariant, bat bien o day la bat bien theo nghia gi, hien tuong cu the gi? Ban co the tra loi giup minh duoc khong?
    Many thanks.

  8. Hi trang,
    Scale invariant là đặc tính của đặc trưng sift. Một cách nôm na có thể hiểu là có 2 ảnh cùng chụp 1 cái bàn, ảnh A chụp gần còn ảnh B chụp từ xa hơn (do đó cái bàn trong hình B nhìn sẽ nhỏ hơn hình A). Nếu sift phát hiện 1 đặc trưng tại góc bàn trong hình B thì nó cũng thường cho ra đặc trưng tại góc bàn ở hình A. Và đặc biệt hơn là feature vector tại góc bàn đó trong 2 ảnh là gần bằng nhau. Sở dĩ có điều này là do khi xử lí hình A, hình A dc downsampling liên tục và xét ở nhiều scale khác nhau, nên nếu trong hình B detect dc keypoint thì thế nao tai vị trí đó, trong quá trình xử lí hình A cũng tìm được 1 keypoint tại scale tương tự, và do đó feature vector có giá trị gần như nhau. (“Gần như nhau” có nghĩa là 128 phần tử của 2 feature vector gần bằng nhau).
    Rotation invariant cũng tương tự. Do mỗi keypoint có 1 hướng chính, hướng của gradient thành phần được tính dựa trên hướng chính này nên cùng chụp 1 vật thể, chụp ảnh thứ nhất rồi xoay máy ảnh chụp bức thứ 2 thì gần như các feature vector tại cùng 1 điểm trên vật thể sẽ giống nhau.
    Đây là ý nghĩa nôm na, vàdc giải thích hợp lí trong quá trình thiết lập sift. Trên thực tế mình nghĩ không có cách nào để đo mức độ invariant (bao nhiêu % v.v…) vì nó phụ thuộc vào rất nhiều yếu tố: độ phức tạp về màu sắc (appearance), chất lượng ảnh v.v…

    Tại sao phải downsampling? Downsampling là cách xấp xỉ scale-space, nhờ đó vẫn giữ dc độ chính xác của thuật toán, đồng thời giảm chi phí tính toán. Mình nghĩ các cài đặt hiện có của SIFT (do Lowe cung cấp, trong OpenCV…) tất cả đều bao gồm bước downsampling.

  9. Hi Vu, minh doc tai lieu thi minh hieu la buoc gan orientation, gradient của những điểm lân cận keypoint se được tính, người ta sẽ sử dụng magnitude và orientation,orientation thì sẽ dc trừ với orienation của điểm keypoint, nghĩa là gradient sẽ được so tương đối đối với keypoint, vì vậy, trong trường hợp keypoint bị xoay, gradient tương đối với key point ko đổi, và do đó bất biến với quay, khi keypoint quay thì toàn bộ quay theo, góc tương đối đó ko đổi nên gọi là bất biến doi voi phep quay. Trang hieu vay dung khong?

    Minh rat hieu downsampling se giam chi phi tinh toan, nhung ko biet tinh toan gi o day? Tinh toan histogram, tim peak ?

  10. Hi trang. Cái rotation invariant đúng là như Trang hiểu 😀
    Còn chi phí tính toán tiết kiệm được do downsampling thì bao gồm:
    – Apply Gaussian filter: nhờ downsampling nên kích thước của kernel Gaussian được giữ tương đối nhỏ, so với nếu không downsampling thì phải tăng kích thước kernel Gaussian liên tục. Kernel Gaussian càng lớn thì càng phải convolution nhiều: mỗi pixel trên ảnh được convolution với càng nhiều kernel.
    – Tính DoG: DoG là trừ từng frame ảnh một. Rõ ràng đây là tính toán pixel-wise. Nhờ có downsampling nên số pixel giảm còn 1/4 sau mỗi octave. Rõ ràng chi phí này là khá lớn.
    – Tìm peak: Tìm peak cũng là dạng pixel-wise. Càng có ít pixel thì tính toán càng giảm.
    Có thể còn một số advantages khác mà mình chưa nghĩ đến.

    Ngoài ra để tăng tốc SIFT thì có đặc trưng SUFT. SUFT cho kết quả tương đương nhưng chi phí thấp hơn SIFT.

  11. uhm, nhung truoc khi downsampling, minh da tim ra tat ca keypoint va da tinh tat ca histogram cho keypoint do roi, vay downsampling xong, minh lai di tim keypoint va lai tinh histogram cho keypoint nua ha ban?

  12. Không. Mình nghĩ rằng bất biến với scale là do SIFT duyệt qua tất cả scale có thể có (bằng cách smooth ảnh bằng kernel Gaussian với kích thước ngày càng lớn).
    Theo mình nhớ thì hình như cái này bắt nguồn từ những nghiên cứu về quá trình ghi nhận thông tin thị giác của vỏ não: khi vỏ não ghi nhớ hình ảnh về một vật thể nào đó thì đồng thời nó sao chép hình ảnh đó ở nhiều “scale” khác nhau, nhờ đó sau này nhìn thấy vật thể đó ở khoảng cách xa/gần hơn thì vỏ não vẫn phát hiện được. Nếu mình không lầm thì nhóm của Lowe hồi đó còn làm luôn món nghiên cứu về não người. Tuy nhiên cái này là mình nhớ mang máng, ko chắc lắm 😀
    Còn downsampling chỉ là cách tính xấp xỉ. Trong paper “Distinctive Image Features
    from Scale-Invariant Keypoints”, Lowe cũng nói:
    The accuracy of sampling relative to σ is no different than for the start of the previous octave, while computation is greatly reduced.

  13. SIFT thực thi pha detection trước, sau đó mới đến description. Theo đó đầu tiên [hải apply Gaussian filter, downsampling, tính DoG, tìm local maxima/minima v.v… để có dc một tập các keypoint. Tập các keypoint này được tinh chỉnh thêm một lần nữa để tính lại vị trí/scale chính xác, bỏ các điểm keypoint lỡ detect được trên cạnh. Sau đó trong bước Description mới tính descriptor cho toàn bộ các keypoint đã detect được.

  14. uhm , okie, hieu y ban, nhung truoc khi downsampling, minh da tim ra tat ca keypoint va da tinh tat ca histogram cho keypoint do roi, vay downsampling xong, minh lai di tim keypoint va lai tinh histogram cho keypoint nua ha ban?

  15. ah ha, vay ro roi nhe, downsample de tinh descriptor histogram nhanh hon, tai may lan tra loi truoc ban noi tinh descriptor ko lien quan gi den downsample, nen lam minh confuse lung tung day. Vay ok, tom lai la: khi den gian doan gan orientation, tinh histogram, tinh descriptor, thi se thuc hien tren anh da bi downsample.

  16. Ban co the chi cho minbh phan mem nao co the chay thu de minh co the figure out may thac mac cua minh ve optical flow va SIFT khong, phan mem nao minh co the thay doi nhung thong so nhu alpha, level Gaussian, number of bin , ….

  17. À khoan. Việc tính descriptor trên ảnh gốc hay ảnh đã downsample thì hồi đọc SIFT mình cũng confuse. Nhưng lâu rồi nên cũng bỏ qua mất, với lại cũng không có ý định re-implement hay improve nó nên chỉ đọc để nắm tư tưởng chính thôi. Mình cũng vừa xem lại paper, có vẻ như là việc tính descriptor được thực hiện trên ảnh đã downsample, nhưng mình không chắc lắm. Trong paper hình như cũng không nói rõ.
    Nếu bạn cần thì có thể email hỏi Lowe thử xem 🙂 Cái gì mình không chắc thì không dám nói càn 😀

  18. Site của Lowe ở đây: http://www.cs.ubc.ca/~lowe/
    Bạn dùng email của trường/organization nào đó thì xác suất nhận dc trả lời sẽ cao hơn, so với dùng gmail hay yahoo hay hotmail v.v… 😀 Tất nhiên việc có trả lời hay không còn tùy nhiều lí do khác nữa ^^
    Trang hỏi dc rồi thì inform cho mình với nhé ;))

  19. hi chị, ground truth là tập dữ liệu chuẩn (đã được gán nhãn), dùng để đánh giá độ chính xác của các thí nghiệm. Từ này hơi bị lạm dụng nên phải có ngữ cảnh cụ thể mới nói rõ được 😀
    Chẳng hạn trong ứng dụng image classification (phân lớp ảnh táo và lê) thì ground truth là tập ảnh cả táo và lê, có gán nhãn trước ảnh nào là táo, ảnh nào là lê. Khi thí nghiệm, ta test thuật toán trên tập ảnh đó xem kết quả thế nào, rồi so với ground truth để xem thuật toán đúng/sai bao nhiêu %, tính precision, recall v.v…

  20. De thiet ke mot classifier don gian cho moi object mot cach rieng biet,
    (Tuc la se co mot so object trong database), chu yeu dua tren training data (se co mot tap anh training) va cho biet object co xuat hien trong mot anh hay kkhong bang thresholding so luong SIFT match. Thiet ke mot classifier nghia la mot phuong phap cho may tinh mot threshold dua tren chi duy nhat tap training data, ma se sau cung hoat dong tot tren tap data test. Mot vi du cua phuong phap nhu vay la set threshold den mot con so lon nhat cac matches cho mot an ma khong chua trong object. Mot vi du khac la set threshold den mot so nho nhat cac match cho mot anh ma chua trong object.

    Chi van chua hieu ro lam de thiet ke mot clasifier gom nhung buoc gi, threshold de lam gi. Neu chi co mot tap anh goi la object, mot tap anh goi la training data, mot tap anh test, thi khi thiet ke classifer chi chi lam viec voi tap object va training thoi dung khong? Nhung thiet ke clasifier tung buoc cu the minh se lam gi? Em co tai lieu nao noi ve van de nay khong?

  21. Hi chị,
    Classify là một bài toán rộng, có thể xây dựng classifier bằng rất nhiều cách khác nhau, từ những kĩ thuật trong AI như luật kết hợp, cây quyết định… cho tới tiếp cận máy học với hàng chục loại mô hình xác suất khác nhau. Ứng với mỗi cách tiếp cận lại có cách xây dựng mô hình khác nhau. Cái này rộng quá nên chị hỏi thế thì em chịu rồi. Em nghĩ chị cần có background về AI/Machine Learning/Statistics and Probability… thì mới hệ thống hóa được. Còn hiện nay thì chị nên nói rõ bài toán của chị (data là gì, yêu cầu là gì v.v…) thì mới có thể trả lời cụ thể 😀

  22. Chi muon lam mot classifier don gian de test thu
    chi download duoc cai nay
    http://www.cs.ubc.ca/~lowe/keypoints/
    Chi co mot tap object: vi du: quyen sach, qua tao, …
    Chi co mot tap training va mot tap anh test.
    Chi muon tao mot classifier don gian cho tung object ma chi dua tren tap anh training, classifier se cho biet object co xuat hien trong image hay khong bang cach thresholding mot so SIFT matches.
    Chi khong hieu ro lam ve thresholding number of SIFT matches.
    Em biet threshold va set threshold trong thiet ke classifier la gi khong?

  23. Hi chị,
    “threshold” là ngưỡng, thresholding là đặt ngưỡng, nghĩa là nếu ảnh test có số lượng SIFT match lớn hơn 1 ngưỡng nào đó (400 feature chẳng hạn) thì ảnh thuộc về lớp đó (mỗi lớp lấy ra từ training set, đã được tính sift trước rồi)

  24. Chi hoi ong thay chi ve invariant voi rotation, thi ong giai thich ra truoc khi tinh histogram, se quay 2 cai image cho no co cung huong chinh, goi la remove orientation, sau do tinh histogram dua tren huong nay. Ong giai thich mot hoi chi het hieu luon. Em co y kien gi ve remove orientation khong, ong noi remove orientation la se rotate image mot goc nao do, sau do moi tinh histogram. Sau khi remove orientation thi se bat bien voi phep quay.

  25. Vậy chắc thầy hiểu nhầm ý chị rồi. Nếu là SIFT thì the em biết SIFT không hề rotate ảnh khi tính feature vector. Theo em hiểu thì Rotation invariant là nhờ hướng chính của mỗi keypoint.

  26. Hi em, chi search tren mang thay mot so file ground truth rat kho hieu. Tuc la chi co mot matching thoi ma no cung cho la cai object thuoc image do, nhieu luc chi khong hieu cai chuan ground truth lay tu dau. Chi dung SIFT thi tim duoc giua object va image chi co 1 match. Tuc la thuc su object 1 khong thuoc image A, nhug trong file ground truth thi lai gan nhan rang image A chua object 1. NEu thi gan threshold > 10, tuc la chi bi miss object 1 trong image A. Em hieu khai niem ground truth co can phai chinh xac khong ?

  27. Hi chị, Ground truth dùng để tính toán độ chính xác của thuật toán, do đó yêu cầu phải chính xác tuyệt đối (nếu có thể). Do yêu cầu chính xác cao nên tốt nhất là Ground truth được làm thủ công, tuy nhiên khi csdl lớn thì cách làm thủ công ko ổn nên ngta có thể dùng một số công cụ hỗ trợ, khi đó có thể không còn chính xác tuyệt đối nữa.
    Em thấy chị nên dùng các csdl uy tín, và đọc file help của nó cẩn thận.

  28. Hi em, chi ko hieu cai ground truth mac dich chi dang lam no lai chap nhan object thuoc image khi co 1 match thoi. Ong thay chi keu gan threshold, roi compare voi ground truth. Haizzz, dung la khong the hieu noi, co 1 match ma no cung cho vao tap ground truth, bay gio chang le chi gan threshold la 1 ah. Ong con keu, xac dinh threshold roi vao discuss nua chu. Dung la khong co gi hop ly ca. Gio neu chi gan threshold la 20 di, tho miss rat nhieu so voi ground truth, nhung so voi real world thi lai chinh xac. Gio chi ko con hieu minh dang lam gi nua. Khong biet discuss gi luon. Theo em thi ground truth co can phai thuc te khong? Cai chi dang lam khong thuc te gi ca.

  29. Hi chị,
    Em không hiểu lắm ground truth của chị. Nó gồm những gì? Ảnh có nội dung gì? Có bao nhiêu class?

  30. Hi em trai, chi hieu y ong thay ky truoc roi. Ong giai thich voi chi invariant voi rotation dua tren cai doan nay trong thuat toan mean-shift.

    Orientation assignment: One or more orientations are assigned to each keypoint location based on local image gradient directions. All future operations are performed on image data that has been transformed relative to the assigned orientation, scale, and location for each feature, thereby providing invariance to these transformations.

    Ong lay cai nay ra noi ne. Ma cai nay la ap dung cho moi keypoint, kkeypoint khac nhau thi gan orientation khac nhau phai ko em. Dau phai ap dung de gan orientation cho toan bo cai image dau. Lan truoc ong noi gan cho toan cai image, lam chi ko tai nao hieu noi.

  31. Hi em, chi doc duoc trong tai lieu cua ong tac gia SIFT, co mot cau vay ne

    The quantity of features is particularly important for object recognition, where the ability to detect small objects in cluttered backgrounds requires that at least 3 features be correctly matched from each object for reliable identification.

    Gio chi gan threshold = 3 cho may cai object nho nho, em thay on khong. Theo kinh nghiem lam sift cua em, em co gan threshold = 3 khong?

  32. Dạ không. Theo kinh nghiệm của em thì mấy cái threshold này không nên đoán đại, vì nó thay đổi phụ thuộc dữ liệu. Cách mà e thấy người ta hay làm là dựa vào các độ đo nào đó (precision, recall) hoặc dựa vào đường ROC để chọn ngưỡng thích hợp.

  33. Em trai, giai thich dum chi cho nay voi

    For scale-space extrema detection in the SIFT algorithm, the image is first convolved with Gaussian-blurs at different scales. The convolved images are grouped by octave (an octave corresponds to doubling the value of σ), and the value of ki is selected so that we obtain a fixed number of convolved images per octave. Then the Difference-of-Gaussian images are taken from adjacent Gaussian-blurred images per octave

    Chi hieu la cac image duoc convolve voi Gaussian kernel, voi scale khac nhau. Cac thang octave nay, theo chi hieu , gia su σ = 2 di, thi no se la 2×2 = 4.

    Cai nay chi doc trong bai nay ne. Thay no giai thich ro may cho invariant.
    Ma den cai cho octave nay thi chi confuse.

    http://www.worldlingo.com/ma/enwiki/en/Scale-invariant_feature_transform

  34. Hi em , mot cau hoi hoi bi basic, gio chi co 4 cai DoG, chi muon detect local maxima, va minima. Khi detect duoc maxima va minima o scale space nao thi scale space do goi lai extrema scale space dung khong? (chac chan dung) 🙂

    => Co khi nao 4 cai DoG cua chi deu la extrema scale space khong? Y chi la keypoint nam tren tat ca cac DoG tinh duoc, DoG 1 co 20 cai keypoint, DoG 2 co 20 cai chang han. (Luc nay chua downsample gi ca)

  35. Hi chị,
    Để chọn là maxima hoặc minima thì mỗi điểm trong scale space được so sánh với 27 (?) điểm lân cận, do đó giả sử điểm (x_0, y_0) tại scale \sigma_i là maxima/minima thì điểm (x_0, y_0) không thể là maxima/minima tại scale \sigma_{i-1}\sigma_{i+1}. Extreme là điểm, chứ không phải là cả cái scale. Câu này:
    Khi detect duoc maxima va minima o scale space nao thi scale space do goi lai extrema scale space dung khong?
    không biết chị đọc ở đâu thế?

  36. Oh, dung roi em, y chi la tai cac scale space khac nhau ay ma, minh se detect duoc nhung keypoint khac nhau dung khong? (chua tinh den downsampling) chi la buoc dau thoi day, co nhieu scale space, thi tai moi scale space deu detect ra keypoint. Dung ko em?

  37. Chào Vũ!
    Mình cũng đang làm về SIFT mình đang làm giai đoạn detection candidate keypoint và gán hướng.
    1. Mình dùng sigma bằng căn 2 (như Mr.Lowe đề xuất) và trong cùng 1 octave, apply liên tục cho ảnh vì dụ A1=A*G, A2=A1*G,…. (* là phép convolution)
    nhưng khi tính DoG bằng cách lấy ảnh sau trừ ảnh trước D1=A2-A1,D2=A3-A2, D3=D4-A3,…
    Tìm các point có giá trị min và max bằng cách so sánh với 8 lân cần cùng mức (ví dụ đang xét D2), và 9 lân cân ở mức trên (D1) và mức dưới (D3). Tuy nhiên giá trị point của Di luôn nằm vào khoảng giữa D(i-1) và D(i+1), do đó không có được điểm max và min. DO vậy mình phải lấy giá trị tuyệt đối mới ra được Về cơ bản tương tự như thuật toán mẫu).
    Không biết bước này mình làm có đúng không? Sai chỗ nào?
    2. Khi gán hướng, mình chưa hiểu vì sao tại mỗi keypoint lại có 4 x 4 = 16 subregion, mỗi subregion là 4×4 pixel. Mình chưa tưởng tượng ra.
    Mr. LOWE đề xuất dùng 36 bin để đại diện cho 360 độ, nhưng tại mỗi keypoint thì chỉ tính Mij và Rij, vậy 36BIN đó sẽ lưu giá trị gì? công thức tính.
    Xin chân thành cảm ơn Vũ!

  38. Hi Hoang,
    1. Về cơ bản thì như vậy là đúng với mô tả của Lowe, tuy nhiên “giá trị point của Di luôn nằm vào khoảng giữa D(i-1) và D(i+1)” có thể là do bạn có lỗi gì lúc tính convolution chăng? Giá trị các pixel sau khi apply Gaussian filter chắc luôn nằm trong khoảng 0-255, do đó lấy trị tuyệt đối thì mình cũng không nghĩ là có tác dụng lắm.
    Bạn có thể nói rõ là bạn tính convolution thế nào không? Có thể do tính convoltion (và tạo Gaussian filter) có lỗi gì nên mới dẫn đến hiện tượng trên.
    Ngoài ra SIFT đã được cài đặt sẵn trong OpenCV, nếu bạn đang cài đặt lại SIFT thì có thể tham khảo mã nguồn của OpenCV.

    2. “Tại sao lại có 4×4 = 16 subregion”? Đây là cách tạo descriptor của sift thôi, mục đích là tạo ra 1 vector đặc trưng tại điểm interested point, để sau này có thể dùng nó để matching với các interested point trong ảnh khác (hoặc có thể dùng để phân lớp, nhận dạng v.v…). Còn tại sao lại chọn 4×4=16 subregion thì chắc bạn nên hỏi Lowe thì hơn 😀 Có thể người ta đã thử nghiệm rất nhiều rồi mới chọn cách làm đó. Ngoài ra hình như descriptor này được xạy dựng dựa trên paper cùa Poggio năm 1997, theo đó thì nó dựa trên những nghiên cứu về khả năng nhận dạng của vỏ não. Bạn có thể tìm đọc paper của Poggio để có thêm thông tin chi tiết.
    Về histogram, không biết bạn đọc trong tài liệu nào nói là dùng 36 bin? Theo mình biết thì các histogram hướng chỉ có 8 bin. Tại mỗi keypoint có 4×4 = 16 subregion, mỗi region có 1 histogram 8 bin nên tại mỗi keypoint thì vector đặc trưng sẽ có 4x4x8 = 128 phần tử. Công thức tính là đơn giản: tại mỗi subregion (kích thước 4×4 pixel) ta tính hướng gradient của mỗi pixel, sau đó bỏ nó vào trong histogram bằng cách dùng trilinear interpolation (http://en.wikipedia.org/wiki/Trilinear_interpolation). Để đạt mục tiêu bất biến với phép quay thì một hướng chính được chọn, sau đó hướng của tất cả các pixel còn lại trong subregion sẽ được tính tương đối dựa trên hướng chính.
    Không rõ bạn đang tham khảo tài liệu nào để cài lai SIFT, nhưng paper “Distinctive Image Features from Scale-Invariant Keypoints” năm 2004 của lowe trình bày rất kĩ về SIFT, bạn nên tham khảo thêm trong đó.

  39. Cảm ơn Vũ rất nhiều!
    Mình đang đọc bài bạn đang nói đó và bài năm 1999 của Lowe.
    Việc tính convolution (một số tài liệu VN gọi là tích chập), mình đang dùng Matlab để demo và view kết quả, biết dc rõ hơn, mình cài đặt convolution thấy nó không ra kết quả mong đợi nên cùng hàm conv2(I,G,’same’) có sẵn trong Matlab kết quả cũng tương tự (xin đình kèm code ở phía dưới), nhờ Vũ xem vì sao.

    Còn phần gắn hướng cho cho các keypoint thì ở đầu trang 9 bài báo 2004 viết: “An orientation histogramis formed fromthe gradient orientations of sample pointswithin a region around the keypoint. The orientation histogram has 36 bins covering the 360 degree range of orientations. Each sample added to the histogram is weighted by its gradient magnitude and by a Gaussian-weighted circular window with a σ that is 1.5 times that of the scale of the keypoint”.
    Ở đây mình chưa hiểu ý nghĩa của orientation histogram được tính như thế nào?
    Ngoài 2 bài báo của Lowe, Vũ có bài giảng hay diễn giải chi tiết hơn về SIFT cho mình xin với!
    Cảm ơn Vũ nhiều!

    ===================
    Mình không biết cách đính kèm file nên tạm đưa lên đây, nếu làm Blog loãng đi thì Vũ có thể xóa phần code này cũng dc.
    clear all
    close all;
    im=imread(‘e:\temp\sift(1).jpg’);
    im=0.2989*im(:,:,1)+0.5870*im(:,:,2)+0.1140*im(:,:,3);
    im=double(im);
    im=ScaleUp(im,2,2);
    [h1,w1]=size(im);
    sigma=sqrt(2);
    G=Gau(sigma);
    A{1,1}=im;
    for i=1:4
    if i>1
    A{i,1}=Scale(A{i-1,2},.5,.5);
    else
    A{i,1}=conv2(A{i,1},G,’same’);
    end
    for j=2:5
    A{i,j}=conv2(A{i,j-1},G,’same’);
    end
    for j=1:4
    D{i,j}=A{i,j+1}-A{i,j};
    end
    E{i}=Extrem(D{i,1},D{i,2},D{i,3},D{i,4});
    end
    ===========
    Hàm tìm cực trị, phần so sánh min, max thì dấu <= có thể thay bằng dấu ==
    ===========
    function [E,cout]=Extrem(D11,D12,D13,D14)
    D11=abs(D11);
    D12=abs(D12);
    D13=abs(D13);
    D14=abs(D14);
    [h1,w1]=size(D11);
    E11=zeros(h1,w1);
    cout=0;
    for i=1:h1
    y1=i-1; y2=i+1;
    if i==1
    y1=i;
    end
    if i==h1
    y2=h1;
    end
    for j=1:w1
    x1=j-1; x2=j+1;
    if j==1
    x1=j;
    end
    if j==w1
    x2=w1;
    end
    %%
    min1=min(min(D11(y1:y2,x1:x2)));
    min2=min(min(D12(y1:y2,x1:x2)));
    min3=min(min(D13(y1:y2,x1:x2)));
    min4=min(min(D14(y1:y2,x1:x2)));
    max1=max(max(D11(y1:y2,x1:x2)));
    max2=max(max(D12(y1:y2,x1:x2)));
    max3=max(max(D13(y1:y2,x1:x2)));
    max4=max(max(D14(y1:y2,x1:x2)));
    minE1=min([min1,min2,min3]); %#ok
    minE2=min([min2,min3,min4]); %#ok
    maxE1=max([max1,max2,max3]);
    maxE2=max([max2,max3,max4]);
    if or(D12(i,j)=maxE1)
    E11(i,j)=E11(i,j)+1;
    cout=cout+1;
    else
    if or(D13(i,j)=maxE2)
    E11(i,j)=E11(i,j)+1;
    cout=cout+1;
    end
    end
    end
    end
    E=E11;
    cout %#ok
    end

  40. Hi Hoang,
    Có vẻ hàm của bạn là đúng, tuy nhiên nếu nó vẫn ra số âm thì mình nghi ngờ hàm Gau() để tính Gaussian filter trước khi convolution. Bạn kiểm tra xem ma trận filter có giá trị < 0 không nhé. Ngoài ra bạn cũng nên kiểm tra kích thước của G xem bằng bao nhiêu.

    Phần "gán hướng" mà bạn nói là ở trong section 5? Nếu vậy thì histogram 36 hướng này chỉ dùng để chọn hướng chính, chứ không phải trong bước tính feature vector. Theo đó thì cách tính được mô tả trong paper: Tại mỗi region kích thước 16×16 = 256 pixels xung quanh một keypoint, ta tính 256 giá trị m(x, y) và theta(x, y) cho mỗi pixel. Sau đó histogram của các theta(x, y) sẽ được tính. Giả sử tại pixel (x, y), theta(x, y) được đưa vào bin thứ j trong histogram, thì công thức cập nhật cho Histogram là:
    H\left(j\right) = H\left(j\right) + m\left(x, y\right)*p_{\mathcal{N}}\left(\left[x,y\right];\left[x_0,y_0\right],1.5\sigma\right)

    Trong đó \left[x_0,y_0\right] là vị trí tính theo pixel của keypoint, \sigma là scale hiện tại của keypoint trong pyramid.
    Sau đó histogram H sẽ được xem xét để chọn hướng chính, bằng cách xem trong H, bin nào có giá trị lớn nhất thì sẽ là hướng chính cho keypoint đó. Ngoài ra các bin nằm trong 80% độ lớn của bin lớn nhất cũng được chọn là hướng chính. Cuối cùng dựa vào 3 bin lớn nhất trong H, ta nội suy 1 đường parabol qua 3 điểm này để chọn hướng chính chính xác nhất.

    Mình có slide về SIFT nhưng không phải của mình nên không thể đưa lên đây được, bạn thông cảm 😀

  41. Cảm ơn Vũ nhiều!
    Đúng rồi, mình đang làm phần 5 (bước 3) chọn hướng.
    Nhưng ở bước 1 chọn candidate key point thì theo Lowe dùng ảnh blur sau trừ ảnh blur trước nó, do đó cái Mexican hat wavelet, đỉnh nhọn quay về phía dưới, do đó phần lớn giá trị là âm, những pixel ở cạnh thì có thể có dương (lúc gradient magnitude của nó lớn). Tuy nhiên, điều lạ là thông thường giá trị của DoG ở giữa) luôn nằm giữa giá trị của DoG phía trên và phía dưới nó (D1, D2, D3 thì giá trị của D2 thường nằm giữa, nếu không lấy giá trị tuyệt đối).
    Trong công thức Vũ đưa, PN([x,y];[x0,y0],1.5*sigma) được tính thế nào?
    Vì mỗi bin của histogram sẽ là tổng của các gradient có cùng hướng (chênh lệch trong khoảng 10 độ), sau khi tính H xong thì làm mờ đi bằng Gaussian với sigma mới bằng 1.5sigma khi làm mờ ảnh.
    các pixel lân cận vùng 16×16 thì keypoint này không nằm chính giữa, vì kích thước chẵn. Mình đang phân vân về cái kích thường vùng xung quay keypoint này, vì Lowe ko nói đến.
    Nếu có thể xin Vũ cho mình slide qua email được không? Để đọc cho biết, hiểu cài đặt thôi, không kinh doanh đâu. Mình vừa chuyển qua lĩnh vực Computer Vision nên cũng có khó khăn.
    Xin chân thành cảm ơn!

  42. p_{\mathcal{N}}\left(\mathbf{x};\mu, \sigma^2\right) là giá trị của phân bố Gaussian có kì vọng \mu và phương sai \sigma^2, lấy lại vị trí \mathbf{x}.
    “sau khi tính H xong thì làm mờ đi bằng Gaussian với sigma mới bằng 1.5sigma khi làm mờ ảnh”: Hình như bạn hiểu nhầm ý trong bài rồi. Theo mình hiểu thì khi tính histogram bình thường, mỗi lần cập nhật chỉ là H\left(j\right) = H\left(j\right) + 1, tuy nhiên ở đây Lowe gán trọng số bằng cách dùng m(x, y) và một cửa sổ Gaussian để hạn chế tầm ảnh hưởng của hướng gradient các pixel lên hướng chính: pixel ở càng xa keypoint thì càng ít ảnh hưởng đến hướng chính (giá trị của phân bố Gaussian càng nhỏ khi điểm x càng xa kì vọng). Đây chính là ý nghĩa của việc gán trọng số. Nếu bạn hiểu là lại apply một Gaussian filter nữa lên ảnh trong bước này thì có vẻ bạn hiểu sai rồi.
    Đương nhiên là keypoint không nằm chính giữa, chênh lệch +/- 1 pixel do window có kích thước chẵn. Ý tưởng chính ở đây là lúc tính Histogram, đặt 1 bộ lọc Gaussian có phương sai 1.5\sigma lên tại vị trí keypoint để xác định mức độ ảnh hưởng của hướng gradient của các pixel trong vùng đó.
    Slide không phải của mình nên mình không thể “phân phối” lại được. Hơn nữa nó cũng chỉ dựa trên paper gốc của Lowe cùng với những thông tin khác mà bạn có thể tìm thấy trên internet thôi.

  43. Chào Vũ!
    Mình hỏi thêm chút là trong kỹ thuật detection và matching keypoint thì thông thường người ta hay dùng (tốc độ nhanh và dễ cài đặt) cho một số trường hợp riêng như đối với (1) ảnh không có sự biết đổi nhiều (2 ảnh chụp đồng thời từ máy ánh stereo- máy 2 ống kính. (2) giữa 2 ảnh không có sự thay đổi nhiều và đối tượng keypoint liên quan đến góc/ cạnh, đốm.
    Cảm ơn Vũ nhiều!

  44. Hi Hoàng,
    Mình không hiểu câu hỏi lắm 😀
    SIFT có thể coi là state-of-the-art trong các local feature hiện nay. Ngoài ra thì có thể kể tới các Corner detector khác như Harris, Shi-Tomasi, SUSAN v.v..
    Tuy nhiên do có 2 phần là detection và description, nên SIFT có thể coi là tốt vì chiến lược detection của no dựa trên LoG – có nền tảng lí thuyết vững vàng – và description tỏ ra hiệu quả (bất biến tỉ lệ, quay, thay đổi độ sáng v.v…).
    Các thuật toán matching thì có nhiều, ngay trong paper của Lowe cũng dùng KD-Tree, một cấu trúc dữ liệu kinh điển. Ngoài ra thì có thể dùng bất kì CTDL nào có trong lí thuyết (Hash, BinaryTree, RB-Tree v.v…). Sở dĩ KDTree được dùng là do bản chất vector của các feature vector SIFT.
    Bạn quan tâm đến matching trong trường hợp ảnh không thay đổi nhiều, có lẽ bạn đang làm 3D reconstruction chăng? 😀

  45. Chào Vũ!
    Đúng ah, mình đang làm 3D reconstruction.
    Như Sift thì chạy rất chậm và phức tạp (nó tốt hơn các thuật toán khác trong trường hợp có biến đổi lớn về ánh sáng, quay, scale,….
    Mình đang tìm kiếm thuật toán đơn giản, nhanh hơn (cho các trường hợp đặc biệt trên).
    Vũ thấy hướng nghiên cứu 3D reconstruction hiện nay như thế nào?

  46. Thuật toán tốt thì có “phức tạp” tí cũng không sao mà 😀 Còn nếu bạn quan tâm đến tốc độ thì có thể xem xét SURF (phiên bản nhanh của SIFT): ftp://ftp.vision.ee.ethz.ch/publications/articles/eth_biwi_00517.pdfhttp://people.csail.mit.edu/kapu/papers/mar%5Fmir08.pdf, và SIFT thực thi trên GPU: http://www.cs.unc.edu/~ccwu/siftgpu/
    Nói chung 3D reconstruction theo mình đã đạt được mức độ trưởng thành và có thể coi là cơ bản giải xong. Một số kết quả demo rất ấn tượng (e.g. http://blogs.msdn.com/b/ukmsdn/archive/2011/04/21/converting-regular-images-into-3d.aspx). Các vấn đề khó như texture v.v… cũng đã làm khá tốt trong trường hợp đủ dữ liệu quan sát. Ngay cả 3D reconstruction từ single view cũng đã có kết quả tốt (http://ai.stanford.edu/~asaxena/reconstruction3d/).
    Tuy nhiên mình không có ý offense, lúc nào cũng có thể có những cải tiến mới cho các lĩnh vực nghiên cứu nói chung, và 3d reconstruction nói riêng.

  47. Chào Vũ , mình dùng SURF của OpenCV để detect điểm keypoint và description .
    Nhưng không hiểu lắm 1 số thông số :
    – Phần key point của mình đây :
    214.252747: Huong 1335.028198 : Hess -1 : laplace 49.075619 😡 12.785829 :y 16 : size
    – Phần Description
    -0.003841 0.003863 0.000911 0.000911 -0.002061 0.002665 0.006004 0.006004 -0.036300 0.040836 0.008035 0.009527 -0.020735 0.022738 0.079472 0.079917 0.038460 0.055743 0.007553 0.008405 0.008339 0.046916 0.021858 0.025996 -0.004650 0.004785 0.000380 0.001555 -0.000395 0.000541 0.001170 0.001805 -0.011822 0.013363 0.025991 0.026267 -0.049212 0.054828 0.052217 0.052554 0.187885 0.346256 0.054071 0.120890 -0.071783 0.259652 0.130651 0.207693 0.088501 0.222928 -0.133232 0.266733 0.000366 0.144167 0.020511 0.105556 -0.004924 0.007684 -0.004390 0.005137 0.001434 0.002743 0.004636 0.006825 0.002362 0.004023 0.042489 0.044301 -0.063294 0.073553 0.000808 0.001731 -0.001988 0.070815 0.134888 0.245915 -0.215808 0.250221 -0.038296 0.187613 -0.079992 0.206987 0.162798 0.229861 -0.073975 0.255476 0.048915 0.115978 0.009407 0.020699 0.008149 0.013434 -0.002612 0.024461 -0.001527 0.004831 0.001465 0.001734 -0.000269 0.000280 0.000949 0.000960 -0.000137 0.000139 0.000068 0.005320 0.025510 0.027522 -0.036934 0.045226 0.001218 0.

    Mình không hiểu lắm về cái description . Bạn có thể mô tả chi tiết cho mình phần Description họ lưu những feature nào không ?

  48. Hi Dũng,
    Bạn nên đọc paper của surf để hiểu rõ hơn nhé. Nói chung surf tính descriptor dựa vào kết quả của Haar feature tại mỗi subregion, thay vì gradient tại mỗi pixel như sift. Bạn nên đọc paper để biết thêm chi tiết, hoặc đọc mã nguồn surf để biết cách tính cụ thể

    1. Hi Vũ , mình đang gặp vấn đề ở chỗ
      – Dùng Surf sẵn có ở OpenCV thì đơn giản nhưng của mình dữ liệu là 700.000 cái ảnh ( mỗi cái khoảng 1-2 M) . Query kiểu 128 này thì chết , mình đang có ideas là dùng PCA(Phân tích thành phần chính) cho Surf nhưng mới chỉ thấy PCA cho Sift mà chưa có PCA cho Surf . Liệu giải pháp này theo bạn có khả thi không nhỉ ?

  49. Hi Vũ .
    Bạn có thể cho mình 1 tài liệu nào dễ đọc chút về SIFT(Phần Descriptor) không ? Bản của ông LOWE mình đọc phần Descriptor không hiểu cho lắm + Thêm tài liệu về SURF được thì tốt .
    Thanks

  50. Hi Dũng,
    1. Dùng PCA: theo mình tốt nhất là ko nên dùng PCA, vì có rất nhiều thuật toán có thể query dữ liệu 128 chiều: KD-Tree, KNN v.v… đều là những CTDL cơ bản. Bạn còn có thể sử dụng các cấu trúc dữ liệu khác như B-Tree v.v… 700000 vector 128 chiều không phải là nhiều (tất nhiên còn tùy môi trường bạn dùng: mobile hay desktop…). Thực chất PCA không chỉ giảm chiều mà còn làm mất đáng kể 1 lượng thông tin nhất định, nên bạn nên cố làm tất cả những gì có thể với dữ liệu gốc, rồi sau đó nếu không được hẵng dùng PCA.
    2. Mình không có tài liệu nào “dễ đọc” về SIFT hay SURF cả. Nói chung tài liệu quan trọng và chính thống nhất là paper và mã nguồn, mình nghĩ như thế cũng đủ.

  51. Hi Vũ , vì chương trình của bọn mình làm trên destop ,cấu hình máy ko mạnh . Thử với việc matching giữa 2 ảnh giả sử mỗi ảnh có khoảng 100 feature , nếu mỗi Interested Point có 128 thuộc tính thì thời gian compare giả sử là 2 milisecond . Tính ra với 700000 bức ảnh thì tính ra trung bình mất khoảng 12 phút cho mỗi 1 query ( TH xấu nhất mất 24phuts , trường hợp tốt nhất mất 2 milisecond ) . Time thế là quá to , nếu mình giảm số chiều xuống còn từ 10 – 20 thì hi vọng nó giảm xuống 1 milisecond trong việc matching ( Tức là giảm đi khoảng 6 phút cho 1 query ) .
    Cho mình hỏi về độ ổn định của phương pháp PCA , theo tài liệu cuốn “Phân tích thống kê và dự báo” của Nguyễn Văn Hữu – Nguyễn Hữu Dư thì độ ổn định có thể điều chỉnh lên đến khoảng 90% .

  52. Về nguyên tắc thì với PCA, bạn có thể giữ lại bao nhiêu phần trăm lượng thông tin cần biểu diễn cùng được, giữ càng nhiều chiều thì lượng thông tin càng lớn. Tuy nhiên còn tuỳ vào dữ liệu, đôi khi chỉ giữ lại 2 chiều có thể biểu diễn đến 80% lượng thông tin ban đầu, nhưng đôi khi 10-20 chiều chỉ có thể giữ lại 60-70%, nói chung là phụ thuộc rất nhiều vào dữ liệu.
    Cho vấn đề của bạn, chắc là bạn duyệt và so sánh từng feature một cách thủ công? Vậy thì đương nhiên là chậm rồi (thậm chí không hoạt dộng được vì các descriptor thông thường không thể bằng nhau một cách tuyệt đối, mà thường có sai số nhất định nào đó). Bạn có thể dùng các cấu trúc dữ liệu mình liệt kê ở trên, chắc chắn sẽ nhanh hơn nhiều.

    1. 🙂 Bạn ơi cho mình hỏi trong phần Descriptor của SIFT thì 1 window là 1 khối hình vuong bao nhiêu .
      Thân

  53. Hi Dũng,
    Như trong paper của SURF, kích thước của window là 20s, với s là scale hiện tại trong image pyramid. Ở bước đầu tiên s =1.2, sau đó tăng dần như mô tả trong phần 3 của paper.

  54. Hi Vũ .
    Mình đã thử thay lại bộ Detector và bộ Descriptor . Vẫn đang run trên C# chưa base lại C++
    Kết quả có vẻ tốt hơn trước .
    Thêm nữa mình dùng BruteForceMatcher để compare , time chắc cũng sẽ down so với phương pháp mình đang làm .
    Thank cậu vì thời gian qua đã tích cực comment trả lời mình .

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s