Hiệu suất OpenCV trên mẫu khớp với

Question

Tôi đang cố gắng thực hiện mẫu khớp về cơ bản trên java. Tôi đã sử dụng thuật toán đơn giản để tìm kết quả phù hợp. Đây là mã:

minSAD = VALUE_MAX; 
// loop through the search image 
for (int x = 0; x <= S_rows - T_rows; x++) { 
    for (int y = 0; y <= S_cols - T_cols; y++) { 
     SAD = 0.0; 

     // loop through the template image 
     for (int i = 0; i < T_rows; i++) 
      for (int j = 0; j < T_cols; j++) { 

       pixel p_SearchIMG = S[x+i][y+j]; 

       pixel p_TemplateIMG = T[i][j]; 

       SAD += abs(p_SearchIMG.Grey - p_TemplateIMG.Grey); 
      } 
    } 

    // save the best found position 
    if (minSAD > SAD) { 
     minSAD = SAD; 
     // give me VALUE_MAX 
     position.bestRow = x; 
     position.bestCol = y; 
     position.bestSAD = SAD; 
    } 
} 

Nhưng đây là cách tiếp cận rất chậm. Tôi đã thử nghiệm 2 hình ảnh (768 × 1280) và ảnh phụ (384 x 640). Điều này kéo dài cho các lứa tuổi. OpenCV có thực thi mẫu khớp nhanh hơn nhiều hay không với hàm cvMatchTemplate()?

Answer 1

Bạn sẽ tìm thấy openCV cvMatchTemplate() nhanh hơn nhiều so với phương pháp bạn đã triển khai. Những gì bạn đã tạo là một phương thức khớp mẫu thống kê. Nó là phổ biến nhất và dễ nhất để thực hiện tuy nhiên là rất chậm trên hình ảnh lớn. Cho phép xem xét các phép toán cơ bản bạn có một hình ảnh là 768x1280 bạn lặp qua từng pixel này trừ đi cạnh vì đây là giới hạn mẫu của bạn như vậy (768 - 384) x (1280 - 640) là 384 x 640 = 245 ' 760 hoạt động mà trong đó bạn lặp qua từng pixel của mẫu của bạn (một hoạt động 245'760) khác trước khi bạn thêm bất kỳ phép toán nào vào vòng lặp của bạn mà bạn đã có (245'760 x 245'760) hoạt động 60'397'977'600. Hơn 60 tỷ hoạt động chỉ để lặp qua hình ảnh của bạn Thật đáng ngạc nhiên khi các máy nhanh có thể thực hiện điều này như thế nào.

Hãy nhớ tuy nhiên 245'760 x (245'760 x Hoạt động Toán học) nên có nhiều thao tác hơn.

Bây giờ cvMatchTemplate() thực sự sử dụng hoạt động khớp mẫu Phân tích Fourier. Điều này hoạt động bằng cách áp dụng Chuyển đổi Fourier Nhanh (FFT) trên hình ảnh trong đó các tín hiệu tạo nên thay đổi điểm ảnh về cường độ được phân đoạn thành từng dạng sóng tương ứng. Phương pháp này khó giải thích tốt nhưng hình ảnh được chuyển thành một biểu diễn tín hiệu của các số phức. Nếu bạn muốn hiểu thêm, vui lòng tìm kiếm trên goggle cho fast fourier transform. Bây giờ hoạt động tương tự được thực hiện trên mẫu các tín hiệu tạo thành mẫu được sử dụng để lọc ra bất kỳ tín hiệu nào khác khỏi hình ảnh của bạn.

Đơn giản, nó ngăn chặn tất cả các tính năng trong hình ảnh không có các tính năng giống như mẫu của bạn. Hình ảnh sau đó được chuyển đổi trở lại bằng cách sử dụng một biến đổi nhanh chóng đảo ngược nhanh chóng để tạo ra một hình ảnh có giá trị cao có nghĩa là một trận đấu và giá trị thấp có nghĩa là ngược lại. Hình ảnh này thường được chuẩn hóa vì vậy 1 đại diện cho một trận đấu và 0 hoặc có nghĩa là đối tượng không ở gần.

Được cảnh báo mặc dù nếu đối tượng không có trong hình ảnh và phát hiện sai chuẩn hóa sẽ xảy ra khi giá trị cao nhất được tính sẽ được coi là đối sánh. Tôi có thể tiếp tục cho mọi lứa tuổi về cách thức hoạt động của phương pháp và lợi ích hoặc các vấn đề có thể xảy ra nhưng ...

Lý do phương pháp này rất nhanh là: 1) opencv được tối ưu hóa cao C++ mã. 2) Chức năng fft rất dễ dàng cho bộ vi xử lý của bạn để xử lý như một đa số có khả năng thực hiện thao tác này trong phần cứng. Thẻ đồ họa GPU được thiết kế để thực hiện hàng triệu hoạt động fft mỗi giây vì các tính toán này cũng quan trọng trong đồ họa chơi game hiệu suất cao hoặc mã hóa video. 3) Số lượng hoạt động yêu cầu là ít hơn nhiều.

Trong phương pháp so khớp mẫu thống kê tóm tắt chậm và mất độ tuổi trong khi opencv FFT hoặc cvMatchTemplate() nhanh chóng và được tối ưu hóa cao.

So khớp mẫu thống kê sẽ không tạo ra lỗi nếu đối tượng không có ở đó trong khi FFT opencv có thể trừ khi việc chăm sóc được thực hiện trong ứng dụng của nó.

Tôi hy vọng điều này mang lại cho bạn một sự hiểu biết cơ bản và trả lời câu hỏi của bạn.

Cheers

Chris

[EDIT]

Để trả lời thêm câu hỏi của bạn:

Hi,

cvMatchTemplate thể làm việc với CCOEFF_NORMED và CCORR_NORMED và SQDIFF_NORMED bao gồm cả phi phiên bản chuẩn hóa của chúng. Here hiển thị loại kết quả bạn có thể mong đợi và cung cấp cho mã của bạn để chơi cùng.

http://dasl.mem.drexel.edu/~noahKuntz/openCVTut6.html#Step%202

Ba phương pháp được trích dẫn tốt và nhiều giấy tờ có sẵn thông qua Google scholar. Tôi đã cung cấp một vài giấy tờ dưới đây. Mỗi phương pháp đơn giản sử dụng một phương trình khác nhau để tìm mối tương quan giữa các tín hiệu FFT tạo thành mẫu và tín hiệu FFT có trong hình ảnh. Hệ số tương quan có xu hướng mang lại kết quả tốt hơn trong kinh nghiệm của tôi và dễ tìm hơn. Tổng của sự khác biệt bình phương là một phương pháp khác có thể được sử dụng với các kết quả có thể so sánh. Tôi hy vọng một số trong những trợ giúp này:

Fast normalized cross correlation for defect detection Du-Ming Tsai; Chien-Ta Lin; Chữ công nhận mẫu Tập 24, Số phát hành 15, tháng 11 năm 2003, Trang 2625-2631

Template Matching using Fast Normalised Cross Correlation Kai Briechle; Uwe D. Hanebeck;

Relative performance of two-dimensional speckle-tracking techniques: normalized correlation, non-normalized correlation and sum-absolute-difference Friemel, B.H .; Bohs, L.N .; Trahey, G.E .; Hội nghị chuyên đề Ultrasonics, 1995. Kỷ yếu., 1995 IEEE

A Class of Algorithms for Fast Digital Image Registration Barnea, Daniel I .; Silverman, Harvey F .;
Máy vi tính, Giao dịch IEEE vào tháng 2 năm 1972

Thường được ưu tiên sử dụng phiên bản bình thường của các phương pháp này bằng bất kỳ giá trị nào tương đương với 1. Phương thức này hoạt động nhanh chóng đơn giản chỉ vì cách nó được xúi giục bằng ngôn ngữ máy tính. Các hoạt động liên quan là lý tưởng cho kiến ​​trúc bộ vi xử lý có nghĩa là nó có thể hoàn thành từng hoạt động với một vài chu kỳ đồng hồ thay vì chuyển bộ nhớ và thông tin xung quanh một vài chu kỳ đồng hồ. Bộ vi xử lý đã giải quyết vấn đề FFT trong nhiều năm biết và như tôi đã nói có phần cứng sẵn có để làm như vậy. Phần cứng dựa trên luôn luôn nhanh hơn so với phần mềm và phương pháp thống kê của mẫu phù hợp là trong phần mềm cơ bản dựa.Tốt đọc cho phần cứng có thể được tìm thấy ở đây:

Digital signal processor Mặc dù một trang Wiki tài liệu tham khảo có giá trị một cái nhìn một cách hiệu quả này là phần cứng mà thực hiện tính toán FFT

A new Approach to Pipeline FFT Processor Shousheng Anh; Mats Torkelson; Yêu thích của tôi khi nó hiển thị những gì xảy ra bên trong bộ xử lý

An Efficient Locally Pipelined FFT Processor Liang Yang; Kewei Zhang; Hongxia Liu; Jin Huang; Shitan Huang;

Những giấy tờ này thực sự cho thấy FFT phức tạp như thế nào khi được triển khai tuy nhiên lớp lót ống của quy trình là điều cho phép thao tác được thực hiện trong một vài chu kỳ đồng hồ. Đây là lý do các hệ thống dựa trên thị giác thời gian thực sử dụng FPGA (đặc biệt là các bộ vi xử lý thiết kế mà bạn có thể thiết kế để thực hiện một tác vụ) vì chúng có thể được thiết kế cực kỳ song song trong kiến ​​trúc và ống lót dễ thực hiện hơn.

Mặc dù tôi phải đề cập rằng đối với FFT của một hình ảnh bạn đang thực sự sử dụng FFT2 là FFT của đồng bằng ngang và FFT của đồng bằng dọc, do đó không có nhầm lẫn khi bạn tìm thấy tham chiếu đến nó. Tôi không thể nói rằng tôi có một kiến ​​thức chuyên môn về cách thức các phương trình được thực hiện và FFT được thực hiện mà tôi đã cố gắng tìm kiếm các hướng dẫn viên tốt nhưng việc tìm kiếm một hướng dẫn tốt là rất khó. ít nhất). Một ngày nào đó tôi có thể hiểu họ nhưng biết rằng tôi hiểu rõ cách họ làm việc và loại kết quả có thể được mong đợi. Ngoài việc này, tôi không thể giúp bạn nhiều hơn nếu bạn muốn thực hiện phiên bản của riêng bạn hoặc hiểu nó hoạt động như thế nào khi đến thư viện nhưng tôi cảnh báo bạn mã opencv được tối ưu hóa tốt, bạn sẽ phải vật lộn để tăng hiệu suất của nó tuy nhiên những người hiểu biết bạn có thể tìm ra một cách để đạt được kết quả tốt hơn tất cả tốt nhất và may mắn

Chris