Đề tài Sử dụng các phương pháp luận sáng tạo để giải quyết bài toán motion detect

PHƯƠNG PHÁP LUẬN SÁNG TẠO KHOA HỌC SỬ DỤNG CÁC PHƯƠNG PHÁP LUẬN SÁNG TẠO ĐỂ GIẢI QUYẾT BÀI TOÁN MOTION DETECT Giảng viên hướng dẫn GS,TS Hoàng Văn Kiếm Sinh viên Nguyễn Hoài Phương - 06520356 TỔNG
QUAN Hiện nay, có rất nhiều phương pháp detect motion trong video. Nhưng hầu hết chúng đều có chung một phương pháp cơ sở là việc so sánh giữa frame hiện tại với một hoặc các frame trước đó. Nói đơn giản hơn là làm việc với các ảnh số, vi vậy chúng ta phải áp dụng một số kỹ thuật của image processing để thực hiện vấn đề này. Để tiếp cận dễ dàng hơn vấn đề của bài viết, ta đi vào tìm hiểu một khái niệm có nhiều diểm tương đồng với motion detect, đó là phương pháp nén video. Một file video gồm 2 phần chính, đó là hình ảnh và âm thanh. Ở đây chúng ta chỉ cần quan tâm đến yếu tố hình ảnh. Chẳng hạn, với cách lưu trữ video theo chuẩn NTSC: cứ mỗi giây së tương ứng 30 frame. Trong quá trình hiển thị, các frame xếp chồng lên nhau với tốc độ rất nhanh, vì vậy ta sẽ có cảm giác các đối tượng trong frame đang chuyển động. Nói như vậy, ta cần phải quan tâm đến vấn đề lưu trữ frame. Nếu như lưu trữ một cách thông thường theo các frame, ta lấy ví dụ chẳng hạn một frame có dung lượng 10 Kb thì để lưu trữ 1 giây thì ta sẽ mất đến 3 Mb. Dung lượng cần để lưu trữ như vậy là quá lớn, chính vì vậy khái niệm nén video đã được ra đời Nhận thấy rằng trong 1 scene sẽ có một số thành phần không thay đổi trong suốt quá trình diễn ra scene đó. Vi vậy dẫn đến ý tưởng ta có thể tách những thành phần không đổi đó ra thành một frame chung, còn được gọi là “background”. Tại những frame còn lại của scene ta chỉ cần lưu trữ các đối tượng còn lại, hay còn gọi là foreground. Thao tác này sẽ giảm bớt việc lưu trữ các “background” lập lại ở mỗi frame. Nhờ đó mà dung lượng lưu trữ sẽ giảm đáng kể. Từ ý tưởng của phương pháp nén video, ta đã có ý niệm tổng quát để xây dựng phương pháp detect motion trong phần còn lại. CÁC PHƯƠNG PHÁP SỬ DỤNG NGUYÊN TẮC PHÂN NHỎ Chia nhỏ đối tượng thành các thành phần độc lập. Tăng mức độ phân nhỏ của đối tượng. Bài toán detect motion được phân thành nhiều vấn đề nhỏ, với mỗi vấn đề nhỏ có phương pháp riêng để giải quyết chúng. Các phương pháp được dùng như sau đây. Một chương trình detect mộtion hiểu hay tiếp cận một cách đơn giản nhất là làm sao để detect được những đối tượng có sự thay đổi giữa các frame. Để thực hiện điều này, ta có thể sử dụng một số phương pháp: Phương pháp tách background, cập nhật background. Phương pháp tách đối tượng (foreground) từ các frame đang xét và background. Phương pháp lấy ngưỡng (threshold) để loại bỏ nhiễu. Phương pháp erosion và dilatation khử nhiễu. Và một số phương pháp khác để tối ưu tốc độ xử lí của chương trình. Trước tiên ta cần xem xét vấn đề làm sao để cải thiện được tốc độ xử lý của chương trình, đồng thời phải tiếp cận được phương pháp lấy ngưỡng. Một frame hay ảnh có nhiều đặc trưng, chẳng hạn như đặc trưng về không gian giữa các pixel, đặc trưng về màu sắc, về texture hay shape. Để có thể áp dụng phương pháp lấy ngưỡng, ta cần phải thực hiện phép so sánh với ít nhất một trong các đặc trưng trên. Mà màu sắc là một yếu tố cơ bản vô cùng quan trọng. Tuy nhiên, ảnh số được lưu trữ bởi không gian màu RGB với mỗi pixel lưu trữ ba giá trị kênh màu rời rạc gồm 256 mức. Chính vì vậy, chúng ta cần phải biến đổi giá trị màu ấy về một dải màu (hay kênh màu) duy nhất. Không gian màu có thể đáp ứng được yêu cầu trên là grayscale. NGUYÊN TẮC TÁCH KHỎI Tách phần gây phiền phức (tính chất gây phiền phức) hay ngược lại, tách phần duy nhất cần thiết (tính chất cần thiết) ra khỏi đối tượng. Ở đây ta tách bỏ các màu sắc không cần thiết và chỉ lại yếu tố màu cần thiết bằng phương pháp lọc grayscale. GRAYSCALE Trong hầu hết quá trình xử lí ảnh, chúng ta chủ yếu chỉ quan tâm đến cấu trúc của ảnh và bỏ qua ảnh hưởng của yếu tố màu sắc. Do đó bước chuyển từ ảnh màu thành ảnh xám là một công đoạn phổ biến trong các qua trình xử lí ảnh vì nó làm tăng tốc độ xử lí là giảm mức độ phức tạp của các thuật toán trên ảnh. Chúng ta có công thức chuyển các thông số giá trị màu của một pixel thành mức xám tương ứng như sau: G = α.CR+ β.CG+ δ.CB Trong đó các giá trị CR, CG, CB lần lượt là các màu đỏ, xanh lá và xanh biển của pixel màu. Các hệ số α, β, và δ là các giá trị thay đổi tùy thuộc hệ màu. Với hệ màu NTSC thì α = 0.29890, β = 0.58662, δ = 0.11448. Ta sẽ được: G = 0.29890CR + 0.58662.CG + 0.ll448.CB PHƯƠNG PHÁP SAI BIỆT FRAME Để định nghĩa phương pháp này, trước tiên ta làm quen với cụm từ “phương pháp trừ ảnh nền” (background subtraction). Đây là phương pháp được sử dụng rộng rãi để nhận diện các đối tượng chuyển động trong video. Để thực hiện việc trừ ảnh nền đầu tiên ta phải học một mô hình của ảnh nền. Sau đó mô hình ảnh nền được dùng để so sánh với ảnh hiện tại, loại bỏ đi những phần ảnh nền đã biết. Các đối tượng sau trừ được xem là không phải nền (foreground). Các đối tượng đó có thể là các đối tượng chuyển động (moving object, mộtion). Một phương pháp trừ ảnh nền phổ biến là phương pháp sai biệt frame. Phương pháp trừ ảnh nền đơn giản nhất là trừ frame này với frame khác, sau đó gán nhãn các vùng khác biệt ‘đủ lớn’ là phần ảnh không phài nền (foreground). Lý do chi gán nhãn cho các vùng khác biệt đủ lớn (threshold) là để loại trừ các trường hợp khác biệt do nhiễu. PHƯƠNG PHÁP NỀN TRUNG BÌNH Tuy nhiên, để tăng hiệu quả, chúng ta có thể giữ lại thông tin thống kê về trung bình và sự khác biệt trung bình của các pixel trong cảnh. Đó là cách làm của phương pháp cải tiến: phương pháp nền trung bình. Nguyên tắc Về cơ bản, phương pháp ảnh nền trung bình học giá trị trung bình và độ lệch chuẩn của từng pixel để xây dựng mô hình của ảnh nền trung bình. Sau đó, ta sử dụng mô hình ảnh nền đã học được để tách ảnh ra làm phần nền (background) và đối tượng không phải nền (foreground). Đối tượng không phải nền đó chính là đối tượng chuyển động. Nhận xét về phương pháp ảnh nền trung bình Đây là phương pháp đơn giản để học ảnh nền và phân tách ành ra làm phần nền và không nên. Tuy nhiên, phương pháp này chi hiệu quả trong các trường hợp ảnh có nội dung là các cảnh không chứa các thành phần nền có chuyển động (vi dụ như một tấm màn phất phơ, hay các cây xanh có lá rung rinh); đồng thời độ sáng tương đối không thay đổi (các ảnh tịnh trong nhà). Ví dụ phương pháp sai biệt frame Cửa sổ 1 : frame hiện tại. Cửa sổ 2 : frame trước đó. Cửa sổ 3 : ảnh sai biệt giữa frame hiện tại và frame trước đó (lấy frame hiện tại trừ cho frame trước đó). Cửa sổ 4 : loại bỏ bớt nhiễu chỉ giữ lại những sai biệt “đủ lớn”. MORPHOLOGY OPERATION Sử dụng ảnh camera, ta sẽ không tránh khỏi trường hợp có “nhiễu” (nhiễu do môi trường, do nhiệt, do không khí...) khi đó vùng foreground của mỗi frame tách ra sẽ xảy ra hiện tượng bị thừa ra ngoài hoặc khuyết một số pixel. Điều đó làm cho việc lấy ngưỡng thiếu chính xác hoặc có thể bị sai lệch. Vì thế ta cần tìm ra phương pháp để “cắt đi” những pixel thừa và “lấp đầy” những pixel khuyết. Bằng các phương pháp Morphology ta có thể thực hiện điều đó; cụ thể với phương pháp Erosion, ta có thể thực hiện thao tác cắt và với phương pháp Dilatation, ta “lấp” được chỗ khuyết. AForge.NET hỗ trợ các đối tượng Erosion, Dilatation, Openning Và Closing để thực hiện việc khử nhiễu. (ImaginglFilterslMorphology/*. Cs). Erosion là phương pháp làm co biên của đối tượng đi một pixel để loại bỏ các pixel thừa; hay nói cách khác, những pixel của foreground mà thuộc background sẽ được chuyển thành pixel của background (hinh b). Dilatation thi ngược lại, nó làm giãn biên của đối tượng thêm một pixel, dựa vào đó mà nhũng lỗ khuyết sẽ được lấp đầy; hay nói cách khác những pixel của background thuộc về foreground nó sẽ được chuyển thành các pixel của foreground. Thao tác Erosion và Dilatation có một khuyết điểm, đó là nó co hay giãn biên 1 pixel, sẽ làm cho đối tượng gốc bị co lại hay giãn ra và từ đó độ lớn của đối tượng sẽ không còn chính xác nữa. Chính vì vậy mà phải xuất hiện thêm hai phương pháp: Openning và Closing để lấy lại độ lớn chính xác của đối tượng. Đây là hai phương pháp sử dụng liên tiếp hai phương pháp cũ. Openning dùng Erosion để cắt bớt những pixel thừa trước rồi dùng Dilatation để làm giãn đối tượng về độ lớn cũ. Còn Closing dùng Dilatation để làm đầy những pixel trước rồi dùng Erosion để co đối tượng về độ lớn cũ. Nếu kết hợp cả hai phương pháp này, ta có thể đồng thời lọai bỏ những pixel thừa và lấp đầy những pixel khuyết. Kết quả mặc dù có chính xác hơn tuy nhiên thao tác lặp lại trong tính toán là rất lớn dẫn đến làm chậm hệ thống, nên tùy theo bài toán mà ta áp dụng một trong bốn phương pháp trên. EDGE DETECTION Trong phần cài đặt trên AForge.NET sắp xét tới đây, chúng ta cần thực hiện thao tác tách biên cho những vùng pixel (region) trả về nhằm xác định đối tượng. Có rất nhiều phương pháp hỗ trỡ cho thao tác nay, và thông thường ta chỉ cần áp dụng mã xích, hoặc mã crack để dò biên là dủ. Tuy nhiên cần chú ý các đối tượng nhận được thường là một cụm các pixel liền kề nên ta có thể áp dụng một số phương pháp thuộc Edge Detection để dò biên. AForge.NET cung cấp cho chúng ta bộ lọc Edge để sử dụng các phương pháp về Edge Detection. Khái niệm: Ta thấy một hình ảnh không phải là một hàm liên tục a(x, y) theo cac biến tọa độ, mà chỉ là những hàm rời rạc a[m, n] với các biến tọa độ nguyên. Vì thế để lấy được các cảnh quan trọng ta cần phải sử dụng việc lấy đạo hàm. Với bộ lọc Edge ta có 4 kĩ thuật phổ biến: - Bộ lọc Sobel. - Bộ lọc Difference of Gauss - Bộ lọc Laplace - Bộ lọc Canny Sobel Bộ lọc sobel sử dụng các mặt nạ để xấp xỉ đạo hàm bậc nhất. Nói cách khác bộ lọc sobel sử dụng gradient theo một hướng (từ thấp đến cao hoặc từ cao đến thấp) tại điểm tâm trong một lân cận được tính theo bộ lọc sobel. Bộ lọc có kích cỡ ma trận 3x3. Khi muốn lấy cạnh của một ảnh nguồn ta sử dụng phép nhân ảnh nguồn với ma trận 3x3. ví dụ ta có ảnh nguồn là A, Gx, Gy là 2 ảnh lọc theo 2 hướng x và y. Laplace Phương pháp vi phân bậc 1 làm việc khá tốt khi độ sáng thay đổi rõ nét. Khi mức grayscale thay đổi chậm, miền chuyển tiếp trải rộng thì phương pháp sobel làm việc không hiệu quả. Và laplace là phương pháp hiệu quả hơn, laplace là phương pháp vi phân bậc 2. Toán tử laplace được định nghĩa : Kỹ thuật laplace sử dụng nhiều ma trận khác nhau để xấp xỉ đạo hàm bậc 2. có 3 kiểu ma trân thường dùng: Trong cài đặt thư viện Aforge ta chỉ sử dụng ma trận H1. Canny Bộ tác sườn ảnh Canny dựa trên cặp đạo hàm riêng bậc nhất với việc làm sạch nhiễu. Mục này được để riêng vì đây là phương pháp tách đường biên khá phổ biến được dùng theo toán tử đạo hàm. Như đã nói phương pháp đạo hàm chịu ảnh hưởng lớn của nhiễu. Phương pháp đạt hiệu quả cao khi xấp xỉ đạo hàm bậc nhất của Gauss. Lấy đạo hàm riêng ta được: Do bộ lọc Gauss là tách được, ta có thể thực hiện riêng biệt các tích chập theo x và y CÀI ĐẶT DỰA TRÊN AFORGE.NET FRAMEWORK Aforge.NET là một C# framework được thiết kế nhằm phục vụ cho các nhà phát triển và các nhà nghiên cứu trong 2 mảng đề tài về tin học : Computer Vision và Artificial Intelligent. Hỗ trợ trực tiếp các lĩnh vực như : image processing, neural network, genetic algorithms, machine learning….Framework này được chia làm 5 mảng chính : AForge.Imaging : thư viện hỗ trợ xử lí ảnh. AForge.Neuro : thư viện hỗ trợ lập trình mạng noron. AForge.Genetic : thư viện hỗ trợ lập trình tiến hóa. AForge.Vision : thư viện hỗ trợ lập trình thị giác máy tính AForge.MachineLearning : thư viện máy học. MODE 1 Mode 1 chỉ đơn giản áp dụng duy nhất phương pháp sai biệt frame trình bày ở trên. Qua trình xử lý của mode 1 gồm 3 bước cơ bản như sau: Ảnh từ camera đưa vào được chuyển đổi sang grayscale. So sánh sự khác biệt giữa frame hiện tại và frame trước đó. Kết thúcquá trình so sánh ta sẽ gán background thành background. Rõ ràng ta có thể thấy đây là sự so sánh các ảnh grayscale của các frame 1 và 2, 2 và 3,... đến frame thứ n – l và frame thứ n. Những pixel khác biệt đó chính là các đối tượng có chuyển độn g. Lưu ý: tại lần 1, do không có background nên không thực hiện quá trình xử lý, cuối lần 1 current frame được gán thành background vi vậy quá trình xử lý ta chi thực hiện từ lần 2 trở đi. Với n frame ta lặp lai thao tác xử lý thì có đụoc n - 2 lần so sánh. Khi so sánh sự khác biệt giữa frame hiện tại và frame trước đó (background). Ta phải sử dụng những bộ lọc sau đây: • Difference • Threshold • Erosion • Merge • ExtractChannel • ReplaceChannel Để có thể báo hiệu khi nào xảy ra motion ta chỉ cần tính số white pixel (số pixel khác biệt hay foreground); nếu vượt qua một ngưỡng đặt sẵn thì có thể nói frame hiện tại có đối tượng chuyển động. Ngưỡng này sẽ hữu ích trong phần cài đặt nâng cao. Trong hệ màu RGB ta có 3 kênh màu riêng biệt 8 bit nên 1 pixel chứa 2563 = 28x3 = 224 bit. Vì thế muốn chuyển từ 1 pixel này sang 1 pixel khác ta phải dịch chuyển sang phải 23 bit. Nhưng trong hệ màu grayscale chỉ sử dụng 8 bit màu tương ứng với 256 nên muốn chuyển từ pixel này sang pixel khác ta chỉ cần dịch phải 7 bit. Ở mode 1 ta thấy có khuyết điểm như sau: nếu đối tượng di chuyển mượt chúng ta sẽ nhận được những thay đổi rất nhỏ giữa hai frame kề nhau. Vì thế sẽ tồn tại rất nhiều đối tượng nhỏ hơn threshold nên không thể nào detect được toàn bộ đối tượng chuyển động. Việc detect sẽ càng trở nên tồi tệ khi đối tượng di chuyển quá chậm, lúc đó thuật toán sẽ không cho ra được bất kì kết quả nào. Bên cạnh đó chuyện gì sẽ xảy ra nếu đối tượng trong 2 frame chuyển động qua nhanh, frame trước còn thể hiện nhưng đến frame thứ hai lại biến mất? Trong trường hợp này ta vẫn có thể khẳng định được đối tượng detect là phần bị mất đi, tuy nhiên đó là trong trường hợp tốt, chuyện gì sẽ xảy ra nếu ngay frame sau xuất hiện một đối tượng tương tự tại cùng vị trí trước, như vậy ta cũng sẽ không detect được đối tượng chuyển động. Cho nên sau khi nhận thấy 2 khuyết điểm trên, chúng ta se có cách tiếp cận khác là so sánh giữa frame hiện thời với frame đầu tiên của chuỗi ảnh thuộc video. Nếu không có những đối tượng trong khung ban đầu, việc so sánh giữa frame hiện thời với frame đầu tiên sẽ cho ta toàn bộ sự chuyển động của đối tượng mà không phụ thuộc vào tốc độ di chuyển của nó. Chúng ta sẽ lấy frame đầu tiên của chuỗi video như là một frame background, và ta se luôn so sánh frame hiện thời với background đó. Tuy nhiên phương pháp này cũng có khuyết điểm nếu background về sau bị thay đổi quá nhiều (hoặc thay đổi cả background). Và kết quả là viêc detect sẽ không chính xác. Nên ta phải sử dụng một phương pháp khác là di chuyển frame background đến frame hiện thời rồi ước lượng sự thay đổi giữa background trước và frame hiện thời, sau đó cập nhật lại background đó. Phương pháp này còn gọi là bộ lọc MoveTowards, sẽ được sử dụng chính trong các mode cài đặt sau. MODE 2 Có được sự cải tiến đáng kể so với mode 1, đó chính là việc tách background ra khỏi đối tượng và xác định đối tượng. Để làm những công việc trên ta vẫn sử dụng 2 bộ lọc Difference và Threashold ở phần trước, tuy nhiên cần sự hỗ trợ của bộ lọc MoveTowards để cập nhật background trong quá trình tiền xử lý, Và Edges dùng để xác định biên đối tượng sau khi đã tách được đối tượng khỏi background như một quá trình hậu xử lý. Ngoài ra, mode 2 ta cần phải chính xác để có thể xác định được đối tượng nên bộ lọc Erosion ở mode 1 đã được thay thế bằng bộ lọc Opening. Ở mode 2 ta áp dụng bộ lọc MoveTowards cho viêc tách background không giống như mode 1 chi là sự so sánh current frame và previous frame để tìm ra sự thay đổi giữa các pixel. Với MoveTowards giữa frame đầu tiên và các frame tiếp theo ta cập nhật liên tục background. Nhờ xác định được background mà ta có thể dễ dàng tách đối tượng (foreground) di chuyển thông qua 2 bộ lọc Difference và Threshold. MODE 3 Ở mode này ta có sự khác biệt hơn cho mode 1 và 2. Chúng ta áp dụng phiên bản pixellate của frame hiện thời và background. Thông qua bộ lọc pixellate- ảnh số được chia thảnh grid mà trong đó các cell là các ô vuông bao gồm tập hợp các pixel, dựa vào đó mà các thao tác xử lý sau ta không cần phài sử dụng thao tác dựa trên giá trị của từng pixel như cũ nữa mà ta thực hiện dựa trên giá trị trung bình của từng cell nhờ vậy mà tốc độ xử lý nhanh hơn rất nhiều lần đây là một giai đọan tiền xử lý thật sự cần thiết. Ví dụ, để áp dụng bộ lọc difference giữa current frame và background biết chiều cao và chiêu dài là 1000 pixel. Nêu độ lớn mỗi cell trong pixellate là 10x10. Thì số bước tính toán chỉ là 100x100 thay cho l000xl000. Giàm 100 lần tính toán. Nhờ pixellate ta có thể phân tách ra được cụ thể những chuyển động. Lưu ý: Nhận thấy với 3 mode trên, 1 và 3 sử dụng erosion và dilatation trong khi đó 2 sử dụng opening. Tại sao 1 và 3 không sử dụng phương pháp opening hay closing để bào toàn độ lớn của đối tượng? Vì ta chỉ cần nhận biết sự sai biêt giữa pixel (mode 1) và cell trong pixellate (mode 3). Đó đó để tiết kiệm thời gian xử lý đồng thời không cần độ chính xác cao nên ta chi áp dụng erosion hay dilatation. MODE 4 Ở mode 4 ta sử dụng BlobCounter trong việc tách biệt các đối tượng so vài ảnh nền. Đó đó ta sẽ bỏ qua các bước khử nhiễu morphology và xác định biên bằng edge detection. Dựa vào đối tượng BlobCounter trong đó đã được tích hợp sẵn bộ lọc co giãn ảnh (erosion, dilatation,...) và bộ lọc edge detection ta đã xác định được các đối tượng tương tự như mode 3 (áp bộ lọc MoveTowards để tách background và áp bộ lọc Difference, Threshold) rồi sử dụng BlobCounter làm nhiệm vụ xác định các đối tượng, sau đó xác định giới hạn trên dưới, trái, phải để đưa ra các rectangle boundary của các đối tượng đồng thời gán các label phân biệt chúng. Lưu ý: tham số PixelChanged dùng để xác định motion level khi sử dụng BlobCounter được tính bởi tổng diện tích của tất cả rectangle boundary chứ không phải là tổng số pixel khác bit (mode 1) hay tổng số pixel nằm trong đường bao (contour) của các đối tượng (mode 2), hay tổng số diện tích các cell khác biệt trong pixellate (mode 3).