Đồ án Sử dụng lưới hai chiều để theo vết đối tượng trong video

TRƯỜNG ĐH KHOA HỌC TỰ NHIÊN TP.HCM KHOA CÔNG NGHỆ THÔNG TIN oOo Luận văn tốt nghiệp Đề tài : Sử Dụng Lưới Hai Chiều Để Theo Vết Đối Tượng Trong Video Giáo viên hướng dẫn : Th.S Phạm Phạm Tuyết Trinh Sinh viên thực hiện : Lê Thành Trung (9912087) TP. Hồ Chí Minh, 7/2003 Lời cảm ơn Sau hơn bốn tháng nghiên cứu và thực hiện , luận văn đã được hoàn tất và đã đạt được những kết quả nhất định . Nhìn lại quãng đường đã qua , tôi cảm thấy vô cùng biết ơn các thầy cô , xin cảm ơn các thầy các cô đã trang bị cho chúng tôi một nền tảng tri thức vững vàng , giúp chúng tôi có thể tự mình thực hiện việc nghiên cứu khoa học . Xin cảm ơn cô Phạm Phạm Tuyết Trinh , người đã hướng dẫn tôi trong suốt quá trình thực hiện luận văn . Cô đã chỉ ra cho tôi những định hướng hết sức quan trọng . Xin cảm ơn bạn bè trong nhóm , cảm ơn các bạn Trương Thiên Đỉnh , Nguyễn Thanh Sơn , Trần Hồng Thái đã giúp đỡ tôi rất nhiều trong quá trình thực hiện luận văn cũng như trong suốt bốn năm học . Và cuối cùng , con xin cảm ơn ông , cảm ơn mẹ và chị , những người thân yêu đã luôn là chỗ dựa cho tôi trong những năm tháng qua . Tổng Quan Vấn đề theo vết đối tượng trong video đã và đang thu hút được nhiều sự quan tâm của cộng đồng nghiên cứu bởi nó có nhiều ứng dụng hữu ích trong lĩnh vực giải trí , truyền thông , thị giác máy tính và đa phương tiện , chẳng hạn như ứng dụng trong xử lý và biên tập video số , trong nén video , trong các thư viện số , trong các hệ thống giám sát giao thông .v.v… Đối tượng trong video , hay ngắn gọn là đối tượng video , là những thành phần có ý nghĩa đầy đủ của một khung cảnh . Theo vết đối tượng bao gồm việc theo vết đường biên , theo vết những chuyển động cục bộ và những biến đổi về cường độ (độ sáng tối , độ tương phản) của đối tượng đó . Nội dung chính của luận văn này là nghiên cứu và thực hiện việc theo vết đối tượng theo hướng tiếp cận mới : sử dụng lưới hai chiều . Theo đó , vấn đề theo vết đường biên , theo vết những chuyển động cục bộ và những biến đổi về cường độ sẽ được hợp nhất lại thành vấn đề theo vết lưới 2 chiều . Lưới ở đây được thiết kế dựa theo nội dung của đối tượng giúp cho việc theo vết đối tượng được chính xác hơn . Quá trình ước lượng chuyển động tại các node của lưới được ràng buộc chặt chẽ để bảo toàn kết cấu của lưới Mục lục 1 Giới Thiệu 1.1 Động lực thúc đẩy 1.2 Một số hướng tiếp cận 1.3 Bố cục luận văn 2 Một Số Khái Niệm Nền Tảng 2.1 Một số lĩnh vực liên quan 2.2 Biến dạng ảnh số 2.3 Video , video tương tự , video số 2.4 Đối tượng video , chuyển động của đối tượng video , ước lượng chuyển động 2.5 Hiện tượng che phủ 3 Mô Hình Theo Vết Đối Tượng Video 3.1 Tạo lưới 3.2 Ước lượng chuyển động tại các node của lưới 3.3 Lan truyền lưới 4 Cài Đặt và Thử Nghiệm 4.1 Chi tiết cài đặt 4.2 Kết quả thử nghiệm 5 Kết Luận và hướng phát triển 1 Chương 1 Giới Thiệu Vấn đề theo vết đối tượng trong video đã và đang thu hút được sự quan tâm của cộng đồng nghiên cứu bởi nó có nhiều ứng dụng hữu ích trong lĩnh vực giải trí , truyền thông , thị giác máy tính và đa phương tiện , chẳng hạn như ứng dụng trong xử lý và biên tập video số , trong nén video , trong các thư viện số , trong các hệ thống giám sát giao thông .v.v… Xét một đoạn video quay một khung cảnh , đối tượng trong đoạn video , hay ngắn gọn là đối tượng video , là những thành phần có ý nghĩa đầy đủ trong khung cảnh đó . Theo vết đối tượng bao gồm việc theo vết đường biên , theo vết những chuyển động cục bộ và những biến đổi về cường độ (độ sáng tối , độ tương phản) của đối tượng . Nội dung chính của luận văn này là nghiên cứu và thực hiện việc theo vết đối tượng theo hướng tiếp cận mới : sử dụng lưới hai chiều . Với hướng tiếp cận này , ba vấn đề : theo vết đường biên , theo vết những chuyển động cục bộ và theo vết những biến đổi về cường độ sẽ được hợp nhất lại thành vấn đề theo vết lưới 2 chiều . Theo thuật ngữ thông dụng , mặt phẳng alpha của một đối tượng video là tập hợp tất cả các điểm ảnh thuộc đối tượng đó . Luận văn này đề ra một phương pháp theo vết đối tượng bán tự động , theo đó mặt phẳng alpha của đối tượng video sẽ được xác định bằng tay tại một số frame quan trọng , sau đó mặt phẳng alpha sẽ được tự động xác định ở những frame còn lại bằng 2 cách sử dụng mô hình theo vết lưới 2 chiều . Lưới ở đây được thiết kế dựa theo nội dung của đối tượng giúp cho việc theo vết đối tượng được chính xác hơn . Phần tiếp theo của chương này sẽ trình bày những động lực thúc đẩy việc nghiên cứu vấn đề theo vết đối tượng , những hướng tiếp cận đã được đề ra , và cuối cùng là giới thiệu bố cục của luận văn . 1.1 Động lực thúc đẩy Có thể dễ dàng nhận ra rằng phần lớn thông tin mà con người thu nhận từ bên ngoài là thông qua thị giác . Bằng cách quan sát , con người thu nhận những hình ảnh từ môi trường xung quanh , nhận dạng và đưa ra những phản hồi thích hợp . Một cách tự nhiên , hình ảnh trở thành một trong những dạng thông tin giữ vai trò quan trọng trong đời sống con người . Câu châm ngôn từ xa xưa “một hình ảnh có giá trị hơn vạn lời nói” hay “trăm nghe không bằng một thấy” đã phần nào nói lên ý nghĩa to lớn của hình ảnh trong việc truyền tải thông tin . Vấn đề nảy sinh là làm sao có thể biểu diễn , lưu trữ và trao đổi được dạng thông tin này . Bằng lao động và sáng tạo , con người đã tìm ra những giải pháp cho vấn đề trên , từ giản đơn như những hình thù khắc trên đá , những kí hiệu trên tấm da thú .v.v…cho đến những bức tranh , tấm ảnh đầy màu sắc , những hình ảnh video sinh động ngày nay . Ra đời vào những năm 30 của thế kỉ 20 , video , hiểu một cách đơn giản , là một chuỗi các ảnh tĩnh (còn được gọi là khung hình - frame) liên tiếp , sắp xếp theo trật tự thời gian . Một đoạn video chứa đựng được nhiều thông tin trực quan hơn một ảnh tĩnh , do video có khả năng thu giữ được chuyển động . Một ảnh tĩnh chỉ có thể cung cấp cho người xem những thông tin tĩnh 3 về một khung cảnh trong khi một đoạn video có thể đem lại cho người xem phần động trong khung cảnh đó . Ban đầu video ở dạng tương tự , và do bản chất tương tự nên nó có rất ít khả năng xử lý cũng như tương tác , chỉ có thể đơn giản như chuyển kênh truyền hình hay quay tới quay lui một đoạn băng . Sự phát triển mạnh mẽ của công nghệ phần cứng đã góp phần hướng người sử dụng đến với video số , vốn gắn liền với một khả năng xử lý tương tác tốt hơn . Ta có thể dễ dàng thu nhận , lưu trữ , xử lý tín hiệu video dưới định dạng số , cũng như trao đổi và chia sẻ nó giữa các nền tảng và lĩnh vực ứng dụng khác nhau . Theo nguyên thủy , video số được biểu diễn dựa trên cơ sở khung hình , tức là mỗi đoạn video bao gồm nhiều khung hình , mỗi khung hình là một tập hợp các điểm ảnh . Cách biểu diễn như vậy chỉ mới thể hiện được chiều thời gian của video , trong khi lại làm ẩn đi phần rất quan trọng , đó là nội dung , là những thông tin mà video chứa đựng , là các đối tượng video . Những nhu cầu mới xuất hiện gần đây đã làm bộc lộ những hạn chế của cách biểu diễn này . Những thư viện số , nơi chứa số lượng khổng lồ dữ liệu video số , đòi hỏi phải được trang bị tính năng truy xuất , rút trích và phân tích dữ liệu ở mức đối tượng , việc thực hiện theo từng frame tốn chi phí quá lớn và không khả thi . Công việc xử lý hậu kì , biên tập video đòi hỏi khả năng kết hợp các đối tượng , các khung cảnh tự nhiên và nhân tạo để tạo ra hiệu ứng . Việc tương tác với các đối tượng trong môi trường trực quan hiện chỉ mới giới hạn trong đồ họa máy tính và mong muốn đưa khả năng này vào các ứng dụng multimedia , truyền thông , giải trí ngày càng lớn . Rõ ràng , kiến trúc frame và pixel không đủ để thỏa mãn các nhu cầu trên , cần có một cách biểu diễn video số cấp cao hơn . Và biểu diễn video dựa trên cơ sở đối tượng là lời giải rất thích hợp cho bài toán . Trên cơ sở đối tượng , 4 mỗi frame của video sẽ bao gồm nhiều lớp chồng lên nhau , mỗi lớp tương ứng với một đối tượng video khác nhau . Hình 1.1 : Biểu diễn video dựa trên cơ sở đối tượng Để có thể chuyển video từ frame-based sang object-based cần phải thực hiện việc phân vùng video , tức là phân mỗi frame của video thành nhiều vùng , mỗi vùng sẽ tương ứng với một đối tượng video khác nhau . Cách lý tưởng để thực hiện việc phân vùng là sử dụng phông nền xanh . Theo đó , từng đối tượng video riêng lẻ sẽ được ghi nhận trên phông nền 5 xanh , việc tách đối tượng ra khỏi phông nền xanh là dễ dàng , và cuối cùng ta chỉ việc chồng các đối tượng này lên nhau để tạo ra hình ảnh video mong muốn . Cách này đòi hỏi phải có những trang thiết bị kĩ thuật , những phần cứng chuyên dụng và nhất là phải thực hiện ngay trong giai đoạn thu nhận hình ảnh . Với những điều kiện phức tạp như vậy , kĩ thuật phông nền xanh thường chỉ được sử dụng trong việc tạo các kĩ xảo điện ảnh hay trong các chương trình truyền hình . Phân vùng bằng tay là một công việc rất tốn thời gian và công sức . Với tốc độ chiếu 24 hình / giây , để phân vùng một đoạn video dài 5 phút ta phải thực hiện thủ công trên 24×60×5 = 7200 frame . Hơn nữa , kết quả phân vùng lại không ổn định và thường thay đổi theo chủ quan của mỗi người . Đã có những phương pháp phân vùng video hoàn toàn tự động được đề ra , tuy nhiên các phương pháp này chỉ có thể sử dụng trong những điều kiện nhất định và mới chỉ dừng ở mức phân vùng các đối tượng video đơn giản , rất khó có thể áp dụng cách này cho những đoạn video thông thường hàng ngày . Giải pháp thích hợp được lựa chọn hiện nay là thực hiện phân vùng bán tự động . Với sự trợ giúp của máy tính , việc phân vùng sẽ được thực hiện bằng tay ở một số frame quan trọng , kết quả thu được , tức là các đối tượng video , sẽ được theo vết ở các frame còn lại . Ở đây , có thể hiểu “theo vết” là xác định xem trong các frame tiếp theo thì đối tượng xuất hiện ở đâu và xuất hiện như thế nào . Cuối cùng ta sẽ thu được bản đồ phân vùng cũng như các lớp đối tượng tại từng frame và quĩ đạo chuyển động của từng đối tượng theo thời gian . Theo vết đối tượng trở thành vấn đề cốt lõi trong việc biểu diễn video dựa trên cơ sở đối tượng . Nó giữ một vai trò hết sức quan trọng trong việc 6 giúp cho máy tính “hiểu” các cảnh động , giúp thiết lập mối dây liên kết giữa các đối tượng video trong quá trình chuyển động theo thời gian . Không chỉ giữ vai trò trên , trong thực tế , việc theo vết đối tượng còn được ứng dụng theo kiểu thời gian thực trong các hệ thống giám sát giao thông , giám sát an ninh , điều khiển robot .v.v… Hầu hết các phương pháp theo vết đối tượng trước đây đều thu được kết quả không cao , do chỉ sử dụng những mô hình đơn giản để mô tả chuyển động của đối tượng video , chẳng hạn như mô hình so khớp khối , mô hình so khớp vùng .v.v…Để cải thiện được kết quả , cần tìm ra những mô hình chuyển động thích hợp hơn , mạnh mẽ hơn . Sử dụng mô hình lưới 2 chiều được xem như một hướng tiếp cận mới đầy hứa hẹn . Theo mô hình này , mỗi phần tử của lưới (tức là các mắt lưới) được giả thiết là vùng có chuyển động đồng nhất và chuyển động này có thể được biểu diễn chính xác bằng một phép biến đổi không gian (affine , bilinear , …) . Phép biến đổi này có thể được suy ra từ vectơ chuyển động tại các đỉnh của mắt lưới đang xét . Thực tế đã cho thấy , biểu diễn đối tượng và theo vết đối tượng bằng cách sử dụng lưới 2 chiều cho ra kết quả chính xác hơn và ổn định hơn . Xét về mặt lý thuyết , đáp án tốt nhất cho bài toán theo vết đối tượng là sử dụng các mô hình theo vết 3 chiều . Tuy nhiên , việc sử dụng các mô hình 3 chiều đòi hỏi chi phí tính toán quá cao , đồng thời phải biết rõ cấu trúc 3 chiều của đối tượng được quan tâm . Sử dụng lưới 2 chiều là một giải pháp cân bằng giữa chi phí tính toán và kết quả thu được . Giải pháp này không đòi hỏi phải biết trước về cấu trúc của đối tượng , không đòi hỏi chi phí tính toán cao , đồng thời cho ra kết quả đầy hứa hẹn . 7 1.2 Một số hướng tiếp cận Đã có nhiều phương pháp theo vết được đề ra , theo Toklu [5] , các phương pháp này có thể được phân thành bốn nhóm : Theo vết điểm đặc trưng (feature-point tracking) , Theo vết đường biên (boundary tracking) , Theo vết vùng (region tracking) và Theo vết dựa trên cơ sở mô hình (model- based tracking ) . Việc phân loại này chỉ mang tính tương đối . Theo vết điểm đặc trưng (feature-point tracking) Trong nhóm phương pháp này , một số điểm đặc trưng (theo một tiêu chuẩn nào đó) của đối tượng được chọn ra và việc theo vết trở thành việc xác định quĩ đạo chuyển động của các điểm này theo thời gian Theo vết đường biên (boundary tracking) Nhóm phương pháp này tập trung vào việc xác định chuyển động của đường biên đối tượng . Điều này có nghĩa là các chuyển động cục bộ bên trong đối tượng bị bỏ qua . Tiêu biểu cho nhóm này là phương pháp đường viền động (active contour model hay ngắn gọn là snake) do M. Kass , A. Witkin và D. Terzopoulos đề ra năm 1988 . Theo vết vùng (region tracking) Xuất phát từ ý tưởng theo vết một nhóm điểm sẽ cho kết quả tốt hơn theo vết một điểm riêng lẻ , nhóm phương pháp này thực hiện việc phân đối tượng thành các vùng và thực hiện ước lượng chuyển động cho từng vùng . Theo vết dựa trên cơ sở mô hình (model-based tracking) Nhóm phương pháp này thường được sử dụng để theo vết mặt người , thân người , xe cộ …Nhóm phương pháp này đòi hỏi phải được trang bị tri thức về đối tượng , chẳng hạn như tri thức về cấu trúc ba chiều , các điểm 8 đặc trưng của khuôn mặt , tính đàn hồi .v.v… Nhóm phương pháp không được sử dụng rộng rãi và thường chỉ dùng trong các trường hợp chuyên biệt. Những năm gần đây , các phương pháp theo vết sử dụng lưới đang thu hút được nhiều sự chú ý . Theo mô hình này , mỗi phần tử của lưới (tức là các mắt lưới) được giả thiết là vùng có chuyển động đồng nhất và chuyển động này có thể được biểu diễn chính xác bằng một phép biến đổi không gian (affine , bilinear , …) . Phép biến đổi này có thể được suy ra từ vectơ chuyển động tại các đỉnh của mắt lưới đang xét . Thực tế đã cho thấy , biểu diễn đối tượng và theo vết đối tượng bằng cách sử dụng lưới 2 chiều cho ra kết quả chính xác hơn và ổn định hơn. Việc xác định vectơ chuyển động tại từng node riêng lẻ thường đem lại kết quả không như ý do các vectơ tìm được có thể đan chéo nhau . Để giải quyết vấn đề này , Nakaya [22] đề ra một phương pháp so khớp sáu cạnh , theo đó một lưới đồng dạng (các phần tử tức các mắt lưới có hình dạng và kích thước giống nhau – hình 1.3a) được áp lên đối tượng , các node bên trong sẽ được di chuyển trong một vùng giới hạn bởi 6 cạnh (hình 1.2) để dò ra vị trí tương ứng trong frame tiếp theo . Toklu [5] mở rộng phương pháp này bằng cách sử dụng mô hình lưới đồng dạng phân cấp , theo đó việc ước lượng chuyển động sẽ được thực hiện trên lưới có mật độ từ thưa đến dày . Hình 1.2 : phương pháp so khớp sáu cạnh 9 Hình 1.3 : lưới : a) đồng dạng , b) dựa theo nội dung khung cảnh Tuy nhiên , cả Toklu và Nakaya đều sử dụng lưới đồng dạng , bản thân dạng lưới được tạo bằng cách chia ảnh ra thành các phần bằng nhau do đó không phản ánh được nội dung của khung cảnh , mỗi phần tử của lưới có thể chứa nhiều chuyển động cùng một lúc . Altunbasak giải quyết vấn đề này bằng cách sử dụng lưới có thiết kế dựa theo nội dung đối tượng (hình 1.3b) . Tuy nhiên , trong phương pháp này , đối tượng được xem là toàn bộ frame 10 chứ không riêng một đối tượng cụ thể nào . Từ những nghiên cứu trên , luận văn đề ra một mô hình theo vết đối tượng bán tự động cho phép người dùng chọn ra đối tượng bất kì , đối tượng sẽ được biểu diễn bằng một lưới tam giác hai chiều được thiết kế dựa theo nội dung của đối tượng và được theo vết một cách hoàn toàn tự động ở các frame tiếp theo . Quá trình ước lượng chuyển động tại các node được ràng buộc chặt chẽ để bảo toàn kết cấu của lưới . 1.3 Bố cục luận văn Trong chương 1 này , luận văn đã trình bày những động lực thúc đẩy nghiên cứu vấn đề theo vết đối tượng , trình bày một số hướng tiếp cận đã được đề ra . Phần còn lại của luận văn sẽ được tổ chức như sau : – Ở chương 2 , luận văn sẽ trình bày những khái niệm và nội dung nền tảng liên quan đến vấn đề theo vết đối tượng . – Trong chương 3 , luận văn sẽ trình bày chi tiết về mô hình theo vết đối tượng sử dụng lưới hai chiều mà luận văn đã nghiên cứu và đề ra . – Ở chương 4 , luận văn sẽ trình bày về phần cài đặt thử nghiệm thực tế . – Cuối cùng , trong chương 5 , luận văn sẽ đưa ra kết luận và hướng phát triển tương lai . 11 Chương 2 Những khái niệm và nội dung nền tảng 2.1 Một số lĩnh vực liên quan Các phương pháp theo vết đối tượng trong video số thường sử dụng những kĩ thuật thuộc nhiều lĩnh vực khác nhau . Kết quả của việc theo vết cũng được ứng dụng trở lại trong nhiều lĩnh vực khác nhau . Trong phần này , luận văn sẽ giới thiệu sơ qua một số lĩnh vực quan trọng có liên quan , bao gồm xử lý ảnh số (digital image processing) , đồ họa máy tính (computer graphics) , thị giác máy tính (computer vision) , đa phương tiện (multimedia) và xử lý video số (digital video processing) . Riêng biến dạng ảnh số (digital image warping) , một nhánh của xử lý ảnh , là một lĩnh vực mới được biết đến và có những nội dung quan trọng nên sẽ được trình bày trong một phần riêng . Xử lý ảnh số (digital image processing) Xử lý ảnh số , đúng như tên gọi của nó , bao gồm việc phân tích và xử lý các ảnh số bằng máy tính . Mục đính chính của xử lý ảnh là tăng cường mức độ thu nhận thông tin của con người từ nguồn dữ liệu ảnh và làm cho máy tính có thể tự động xử lý (lưu trữ , biểu diễn , trao đổi …) các hình ảnh thu nhận từ môi trường tự nhiên . 12 Hình 2.1 : Xử l ý ảnh Đồ họa máy tính Đồ họa máy tính bao gồm tất cả những gì liên quan đến việc sử dụng máy tính để phát sinh ra hình ảnh . So với xử lý ảnh thì đồ họa máy tính đóng vai trò như một họa sĩ , còn xử lý ảnh đóng vai trò như một thợ chụp ảnh . Thị giác máy tính (computer vision) Thị giác máy tính là hướng ngược lại của đồ họa máy tính . Trong khi đồ họa lấy thông tin mô tả cảnh bên ngoài (scene discription) để tạo ra ảnh trong máy tính thì thị giác máy tính lại từ ảnh bên trong máy tính để suy ra thông tin mô tả cảnh bên ngoài . 13 Hình 2.2 : Tương quan giữa xử lý ảnh , đồ họa máy tính và thị giác máy tính Đa phương tiện (multimedia) Thuật ngữ “đa phương tiện” diễn đạt ý tưởng các thông tin trong máy tính có thể được biểu diễn bằng các âm thanh , hình ảnh video sinh động chứ không chỉ giới hạn trong những cách biểu diễn truyền thống (văn bản , ảnh tĩnh.v.v…) . Lĩnh vực multimedia đề cập đến việc sử dụng máy tính để tích hợp các dạng dữ liệu như văn bản , hình ảnh tĩnh , hình ảnh động (video) , âm thanh hay bất kì dạng dữ liệu số nào . Xử lý video số Xử lý video số tức là xử lý luồng dữ liệu video số (digital video bitstream) , bao gồm các công việc như thu nhận , lưu trữ , phân tích , tổng hợp , trao đổi .v.v… 14 2.2 Biến dạng ảnh số (digital image warping) Biến dạng ảnh số , hay rõ hơn là biến đổi (về mặt hình học) ảnh số , là một nhánh của xử lý ảnh . Biến đổi về mặt hình học (geometric transformation) là thao tác xác lập lại mối tương quan về vị trí giữa các điểm trên ảnh . Cốt lõi của biến đổi hình học là ánh xạ một hệ tọa độ này sang một hệ tọa độ khác . Điều này được thực hiện thông qua một biến đổi không gian (spatial transformation) , đây là một hàm ánh xạ thiết lập sự tương ứng giữa các điểm trên ảnh đầu vào và các điểm trên ảnh đầu ra . Hàm ánh xạ này có thể biểu diễn theo hai cách sau : [x , y] = [X(u,v) , Y(u,v)] hay : [u , v] = [U(x,y) , V(x,y)] Trong đó [u , v] chỉ vị trí của điểm ảnh trên ảnh input tương ứng với điểm ảnh ở vị trí [x , y] trên ảnh output ; còn X , Y , U , V là các hàm ánh xạ đặc trưng cho từng phép biến đổi cụ thể . Do X và Y thực hiện việc ánh xạ từ ảnh input sang ảnh output nên được gọi là các ánh xạ tiến (forward mapping) , tương tự , U và V được gọi là các ánh xa lùi (backward mapping) hay ánh xạ ngược (inverse mapping) . Ánh xạ tiến thực hiện việc sao chép từng pixel trên ảnh input sang ảnh output tai các vị trí do ánh xạ xác định . Còn ánh xạ ngược thì thực hiện việc đối chiếu từng vị trí trên ảnh output sang ảnh input , sau đó sao chép pixel tại vị trí vừa tìm được trên ảnh input sang vị trí tương ứng trên ảnh output . 15 Một vấn đề phát sinh là các giá trị vị trí lúc ban đầu là số nguyên , sau khi qua hàm ánh xạ thì trở thành số thực . Điều này gây ra hiện tượng lỗ hổng và hiện tượng chồng lên nhau . Lỗ hổng ở đây chỉ những pixel không có đối tượng nào tương ứng . Còn hiện tượng chồng lên nhau là hiện tượng nhiều pixel cùng được ánh xạ tương ứng vào một pixel . Hình 2.3 : Ánh xạ tiến 16 Hình 2.4 : Ánh xạ ngược Ta có thể giảm bớt hiện tượng này bằng cách chia ảnh ra thành các vùng nhỏ (patch) , chẳng hạn như chia thành các vùng hình vuông . Việc ánh xạ khi đó sẽ không thực hiện trên đơn vị điểm ảnh mà thực hiện tại từng vùng . Cách này giúp bảo toàn kết cấu liền lạc của ảnh . Trong phần tiếp theo , luận văn sẽ trình bày các phép biến đổi không gian được sử dụng trong mô hình theo vết đối tượng . Ở đây ta chỉ xét các phép biến đổi 2 chiều . Việc biểu diễn phép biến đổi được thực hiện trong hệ tọa độ thuần nhất (Homogeneous Coordinates) , đây là hệ tọa độ do tác giả Roberts đề ra năm 1965 trong lĩnh vực đồ họa máy tính nhằm đảm bảo tính nhất quán trong cách biểu diễn các phép biến đổi . 17 2.2.1 Biến đổi affine (Affine transformation) Phép biến đổi affine là phép biến đổi tuyến tính , thuận nghịch , có dạng biểu diễn tổng quát như sau : [ ] 11 1221 22 31 32 0 , ,1 [ , ,1] 0 1 a a x y u v a a a a   =     Từ đó suy ra : 11 21 31 12 22 32 x a u a v a y a u a v a = + + = + + Những tính chất quan trọng của phép biến đổi affine là : – Bảo toàn đường thẳng : ảnh của một đường thẳng qua phép biến đổi affine là một đường thẳng – Bảo toàn tính song song của các đường thẳng : ảnh của hai đường thẳng song song là hai đườn song son – Bảo toàn tỉ lệ về khoảng cách : giả sử C là điểm chia đoạn AB theo tỉ số t . Nếu A’ , B’ , C’ lần lượt là ảnh của A , B , C qua phép biến đổi affine thì C’ cũng sẽ chia A’B’ theo tỉ số t . 18 Hình 2.5 : Phép biến đổi affine Một số trường hợp đặc biệt của phép biến đổi affine là : phép tịnh tiến (translation) , phép quay (rotation) , phép biến đổi tỉ lệ (scale) , phép kéo xiên (shear) . Tịnh tiến (Translation) Gọi Tu , Tv là độ dời tương ứng với u , v , dạng biểu diễn của phép tịnh tiến là : [ ] 1 0 0 , ,1 [ , ,1] 0 1 0 1u x y u v T Tv   =     Quay (Rotation) Gọi θ là góc quay , dạng biểu diễn của phép quay là : 19 [ ] cos sin 0 , ,1 [ , ,1] sin cos 0 0 0 1 x y u v θ θ θ θ   = −    Biến đổi tỉ lệ (Scale) Gọi Su , Sv là các hệ số tỉ lệ tương ứng với u và v , dạng biểu diễn của phép biến đổi tỉ lệ là : [ ] 0 0 , ,1 [ , ,1] 0 0 0 0 1 u v S x y u v S   =     Kéo xiên (Shear) Gọi Hu hệ số kéo xiên theo phương trục hoành , dạng biểu diễn của phép kéo xiên theo phương trục hoành có dạng : [ ] 1 0 , ,1 [ , ,1] 0 1 0 0 0 1 uH x y u v   =     Gọi Hv hệ số kéo xiên theo phương trục tung , dạng biểu diễn của phép kéo xiên theo phương trục tung có dạng : 20 ' ' xx w = ' ' yy w = [ ] 1 0 0 , ,1 [ , ,1] 1 0 0 0 1 vx y u v H   =     2.2.2 Biến đổi phối cảnh (Perspective transformation) Dạng biểu diễn tổng quát của phép biến đổi phối cảnh là : [ ] 11 12 1321 22 23 31 32 33 ', ', ' [ , , ] a a a x y w u v w a a a a a a   =     Với : , Từ đó suy ra : 11 21 31 13 23 33 ' ' a u a v axx w a u a v a + += = + + 12 22 32 13 23 33 ' ' a u a v ayy w a u a v a + += = + + 21 Hình 2.6 : Phép biến đổi phối cảnh 2.3 Video , video tương tự , video số Việc theo vết đối tượng được thực hiện trên dữ liệu video , chính xác là trên dữ liệu video số , nên hiểu rõ về dạng dữ liệu này là điều cần thiết . 2.3.1 Video Thuật ngữ video dùng để chỉ nguồn thông tin hình ảnh trực quan (pictorial visual information) , bao gồm một chuỗi các ảnh tĩnh (still image) liên tiếp nhau , được sắp xếp theo chiều thời gian . Video còn được gọi là ảnh thay đổi theo thời gian (time-varying image) , kí hiệu là s( x1 , x2 , t ) , trong đó x1 , x2 là các biến chỉ vị trí trong không gian , còn t là biến thời gian . Một ảnh tĩnh là một phân bố cường độ theo không gian và phân bố này là không đổi theo thời gian . Trong khi ảnh thay đổi theo thời gian là một phân 22 bố cường độ theo cả không gian lẫn thời gian . Xét về mặt vật lý , ở cấp thấp nhất , video tồn tại dưới dạng các tín