Sử dụng lưới hai chiều để theo vết đối tượng trong Video

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 hiệu . Tín hiệu là một hàm chứa đựng thông tin [3] , hay nói một cách khác , tín hiệu là một mô tả chi tiết sự phụ thuộc của một tham số này vào một tham số khác [2] . Nếu miền giá trị của 2 tham số này là liên tục thì tín hiệu được gọi là tương tự , nếu miền giá trị là rời rạc thì tín hiệu được gọi là rời rạc hay gọi là được số hóa . Cũng có những trường hợp , miền giá trị của tham số này là rời rạc , của tham số kia lại là liên tục , nhưng những trường hợp này rất hiếm khi xảy ra và tín hiệu lúc đó cũng không có một cách gọi tổng quát nào . Hầu hết các tín hiệu tương tự xuất hiện trong thế giới tự nhiên , còn các tín hiệu rời rạc (số) thì xuất hiện trong thế giới máy tính . Cần nhấn mạnh là máy tính chỉ hiểu được các tín hiệu đã được số hóa . Ban đầu video được thu nhận , lưu trữ và truyền dẫn dưới dạng tương tự . Những năm gần đây , sự phát triển mạnh mẽ của công nghệ phần cứng , công nghệ xử lý ảnh , cùng với những ưu điểm nổi bật của định dạng số đang hướng người sử dụng đến với video số . 2.3.2 Video tương tự (analog video) Tín hiệu tương tự là tín hiệu điện tử một chiều biến đổi theo thời gian , kí hiệu là f(t) . Cho một ảnh biến đổi theo thời gian ở dạng tương tự (tương ứng với hình ảnh trong tự nhiên) , kí hiệu là sc( x1 , x2 , t) . Tín hiệu video tương tự thu được bằng cách lấy mẫu sc( x1 , x2 , t) theo chiều dọc x2 và chiều thời gian t . Tiến trình lấy mẫu được thực hiện theo chu kì và được gọi là tiến trình quét (scanning) . Phương pháp quét thường được sử dụng nhất là 23 quét liên tiếp (progressive scanning) và quét luân phiên (interlaced scanning). Trong phương pháp quét liên tiếp , cứ sau một khoảng thời gian ∆t , việc quét lại được thực hiện trên toàn ảnh (hình 1.1) . Phương pháp này thường được sử dụng đối với các màn hình có độ phân giải và tấn số quét cao . Hình 2.7 : Phương pháp quét liên tục Trong phương pháp quét luân phiên , cứ sau một khoảng thời gian ∆t/2 , việc quét lại được thực hiện trên các dòng hoặc là chẵn , hoặc là lẻ , nếu ở lần quét trước là dòng chẵn thì ở lần quét này là dòng lẻ và ngược lại (hình 2.2) . Phương pháp này thường được sử dụng đối với các màn hình có độ phân giải và tần số quét thấp Hình 2.8 : Phương pháp quét luân phiên 24 Các thông số kĩ thuật quan trọng của tín hiệu video tương tự là độ phân giải theo chiều dọc (vertical resolution) , tỉ lệ kích thước (aspect ratio) và tần số làm tươi (refresh rate) . Tỉ lệ kích thước là tỉ lệ giữa chiều ngang và chiều dọc . Tần số làm tươi là số lượng frame chiếu trong 1 giây . Ở trên là trường hợp tín hiệu video đơn sắc (monochromatic video signal) . Ta có thể mở rộng ra cho trường hợp tín hiệu video nhiều màu sắc . Theo Lý thuyết ba tác nhân của màu sắc (tri-stimulus theory of color) , mọi màu sắc đều có thể được tái tạo bằng cách kết hợp 3 màu nguyên tố : đỏ (red – R) , xanh dương (blue – B) và xanh lá cây (green – G) , theo một tỉ lệ thích hợp . Hình ảnh nhiều màu sắc sẽ được tạo bằng cách chồng 3 lớp tương ứng với 3 màu nguyên tố lên nhau . Hiện nay , có nhiều chuẩn video tương tự (analog video standards) đang được sử dụng , chúng khác nhau về các tham số hình ảnh (chẳng hạn như độ phân giải theo không gian và thời gian) và cách xử lý màu sắc . Các chuẩn này có thể được phân thành 3 nhóm : • Video tương tự đa thành phần (component analog video – CAV) • Video tổng hợp (composite video) • S-video Trong trường hợp video tương tự đa thành phần , các đơn vị cấu thành tín hiệu video được phân chia thành các tín hiệu video đơn sắc riêng biệt . Các đơn vị này có thể đơn giản là 3 màu nguyên tố : đỏ , xanh dương , xanh lá cây , hoặc được biến đổi thành dạng biểu diễn độ sáng – màu sắc (luminance – chrominance) . Thành phần luminance (kí hiệu là Y) thể hiện các mức xám (gray level) của video , và được tính từ 3 màu nguyên tố như sau : 25 Y = 0.30R + 0.59G + 0.11B Thành phần chrominance chứa đựng thông tin về màu sắc . Ứng với mỗi chuẩn , thành phần chrominance lại có cách biểu diễn khác nhau , chẳng hạn như : Thành phần chrominance được biểu diễn thành I , Q , với : I = 0.60R + 0.28G – 0.32B Q = 0.21R – 0.52G + 0.31B Hoặc thành phần chrominance được biểu diễn thành Cr , Cb , với : Cr = R – Y Cb = B – Y Trong thực tế , tín hiệu video với cách cấu tạo đa thành phần tạo ra chất lượng màu sắc tốt nhất . Tuy nhiên , điều này đòi hỏi quá trình truyền dẫn các thành phần phải được đồng bộ hóa chính xác , đồng thời băng thông cũng phải tăng lên gấp ba lần so với tín hiệu đơn sắc . Trong trường hợp video tổng hợp , tín hiệu video được định dạng theo hình thức : các thành phần chrominance được mã hóa vào đầu thành phần luminance , hợp thành một tín hiệu duy nhất . Điều này giúp tiết kiệm băng thông và đơn giản hóa quá trình truyền dẫn tín hiệu . Các định dạng video tổng hợp phổ biến hiện nay là NTSC (National Television System Committee hay Never Twice the Same Color) , PAL (Phase Alternating Line) , SECAM (Sequential Couleur Avec Memoire hay Sequential Chrominance Signal with Memory) . Chuẩn NTSC được sử dụng phổ biến ở khu vực Bắc Mĩ và Nhật Bản ; chuẩn SECAM được sử dụng ở Pháp , Đông Âu , Liên Xô và vùng Trung Đông ; chuẩn PAL được sử dụng ở khu vực hầu hết các khu vực còn lại , bao gồm Tây Âu , Anh , Nam Mĩ , Châu Á .v.v… 26 Một khuyết điểm của video tổng hợp là chất lượng màu sắc tạo ra không tốt . S–video là một giải pháp trung hòa giữa video tổng hợp và video đa thành phần .Tín hiệu trong S–video được phân thành 2 bộ phận , một cho thành phần luminance và một cho các thành phần chrominance đã được tổng hợp lại . Nhờ vậy , chất lượng màu sắc trong S–video tốt hơn trong video tổng hợp đồng thời băng thông để truyền tín hiệu S–video cũng tốn ít hơn băng thông dùng cho video đa thành phần . Chuẩn S–video hiện đang được sử dụng rộng rãi trong các máy ghi videocasette , máy quay phim .v.v… Việc thu nhận video tương tự chủ yếu dựa trên công nghệ băng từ , trừ trường hợp đĩa laser là sử dụng công nghệ quang học . Với video tương tự , các hình ảnh trong thế giới tự nhiên đã được thu nhận chính xác . Tuy nhiên , do bản chất của nó , video tương tự cung cấp cho người dùng rất ít khả năng tương tác và xử lý , chỉ có thể đơn giản như chuyển kênh TV hay quay tới quay lui , chiếu nhanh chiếu chậm một đoạn băng . Những năm gần đây , sự phát triển mạnh mẽ của công nghệ phần cứng , những tiến bộ trong công nghệ xử lý ảnh và nhất là những ưu điểm nổi bất của định dạng số đang hướng người sử dụng đến với video số . Trong thế giới số , tận dụng sức mạnh của máy tính , ta có thể dễ dàng thu nhận , lưu trữ , biên tập , xử lý và trao đổi hình ảnh video . 2.3.3 Video số Để có được tín hiệu video , tương tự (analog) hay số (digital) , cần phải thực hiện việc lấy mẫu ảnh sc( x1 , x2 , t) theo cả chiều không gian và thời gian . Đối với video tương tự , việc lấy mẫu được thực hiện theo chiều dọc 27 x2 (tung độ) và theo chiều thời gian t . Đối với video số , việc lấy mẫu được thực hiện trên cả 3 chiều : chiều ngang x1 (hoành độ) , chiều dọc x2 (tung độ) và chiều thời gian t . Thực chất , để thu được tín hiệu video số , ta cần phải thực hiện việc số hóa (digitization) , gồm 2 bước : lấy mẫu (sampling) và lượng tử hóa (quantization) . Lấy mẫu là tiến trình chuyển đổi tín hiệu từ dạng liên tục theo không gian và thời gian sang dạng rời rạc theo không gian và thời gian . Sau khi lấy mẫu , các tín hiệu thu được tuy đã ở dạng rời rạc nhưng chúng vẫn có giá trị ở dạng liên tục . Do đó ta cần phải thực hiện việc lượng tử hóa , tức là chuyển các giá trị từ dạng liên tục (cụ thể là dạng số thực) sang dạng rời rạc (số nguyên) . Hình 2.9 : Quá trình số hóa Các thông số kĩ thuật quan trọng của video số là độ phân giải theo chiều dọc (số pixel trên một cột) , độ phân giải theo chiều ngang (số pixel trên một dòng) , tỉ lệ kích thước (chiều ngang / chiều dọc) và tần số làm tươi . Băng thông của video được tính theo công thức : 28 FR = Tần số frame (tần số làm tươi) NL = Số dòng trên 1 frame HR = Độ phân giải theo chiều ngang ρ = thời gian chuyển tín hiệu từ giữa 2 dòng kế tiếp nhau Hầu hết các hệ thống video số đều biểu diễn màu sắc dưới dạng các thành phần riêng biệt (tương tự video analog đa thành phần) . Ngay cả khi đầu vào là tín hiệu video tương tự tổng hợp (composite video) thì đầu tiên nó cũng phải được chuyển sang dạng video tương tự đa thành phần (CAV) , sau đó từng thành phần sẽ được số hóa để cuối cùng thu được tín hiệu video số . Việc trao đổi video số giữa các ứng dụng cũng như giữa các hệ thống đòi hỏi việc chuẩn hóa . Ngành công nghiệp máy tính (computer industry) có các chuẩn về độ phân giải lúc hiển thị , ngành công nghiệp truyền hình (TV industry) có các chuẩn về thu phát , ngành công nghiệp truyền thông (communications industry) có các chuẩn về giao thức mạng . Do ta chỉ làm việc với video số nên từ đây về sau , khi đề cập đến video tức là đề cập đến video số . 2.4 Đối tượng video , chuyển động của đối tượng video , ước lượng chuyển động Trong phần này , luận văn sẽ trình bày những khái niệm và nội dung cơ bản của vấn đề theo vết đối tượng . 29 2.4.1 Đối tượng video (video object – VO) Xé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 đó . Thật ra , khái niệm đối tượng video rất linh động , nó có thể là bất kì thành phần trong khung cảnh , miễn sao đó là thành phần mà ta quan tâm . Phần còn lại của khung cảnh thường được gọi là nền (background) . Tập hợp tất cả các điểm ảnh thuộc đối tượng tạo thành mặt phẳng alpha (Alpha plane – AR) của đối tượng đó . 2.4.2 Chuyển động của đối tượng video 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 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 đó . Hình ảnh mà ta nhìn thấy trong video là hình chiếu của những khung cảnh 3 chiều lên mặt phẳng 2 chiều (mặt phẳng ảnh) . Do đó , chuyển động của các đối tượng video cũng chính là hình chiếu chuyển động của các đối tượng trong không gian 3 chiều lên mặt phẳng ảnh . Tuy nhiên , khi quan sát các hình ảnh video , không phải lúc nào ta cũng thấy được những chuyển động thật sự . Nguyên nhân chính là do mắt người nhận ra chuyển động (trong video) dựa trên sự thay đổi về cường độ của điểm ảnh . Do đó , có những trường hợp ta không nhận ra được chuyển động , ví dụ : quan sát hình ảnh một quả bóng đồng màu quay quanh trục qua tâm , mặc dù có chuyển động xảy ra nhưng do cường độ các điểm ảnh không đổi nên mắt ta không nhận ra được 30 Hình 2.10 : Quả bóng đồng màu quay quanh trục qua tâm Lại có những trường hợp ta ngộ nhận chuyển động , ví dụ : ánh sáng môi trường thay đổi , mặc dù thật sự vật đứng yên nhưng ta vẫn có cảm nhận vật đã di chuyển frame k frame k+1 Hình 2.11 : Ánh sáng môi trường thay đổi Để tách biệt rõ ràng giữa chuyển động thật sự và chuyển động do mắt người cảm nhận , người ta đưa ra khái niệm luồng thị giác (optical flow). Theo đó , chuyển động hai chiều (2-D motion) , tức chuyển động thật sự , là hình chiếu của chuyển động ba chiều lên mặt phẳng ảnh , còn luồng thị giác là những chuyển động mà mắt người nhận ra được dựa trên những thay đổi về cường độ của các điểm ảnh theo thời gian . Do thực tế ta chỉ có thể quan 31 sát được luồng thị giác nên từ đây về sau , khi đề cập đến chuyển động tức là ta đề cập đến luồng thị giác . Chuyển động của đối tượng video có thể phân thành 2 loại : chuyển động cục bộ (local motion) và chuyển động toàn cục (global motion) . Chuyển động cục bộ là chuyển động do bản thân đối tượng tạo ra , là những chuyển động giữa các bộ phận của đối tượng so với nhau . Còn chuyển động toàn cục là chuyển động của đối tượng , xét trên tổng thể , so với camera , hay có thể nói là chuyển động do camera tạo ra . Hình 2.12 : Chuyển động toàn cục và chuyển động cục bộ 2.4.3 Ước lượng chuyển động (motion estimation) Ước lượng chuyển động của một điểm ảnh là tìm ra vectơ dịch chuyển của điểm ảnh đó . Khái niệm về vectơ dịch chuyển d ur , được minh họa trong hình 2.12 . Mở rộng ra , ước lượng chuyển động của một đối tượng là ước lượng chuyển của tất cả các điểm ảnh thuộc đối tượng đó . Mục đích của 32 việc ước lượng chuyển động là để trả lời cho câu hỏi “chuyển động diễn ra như thế nào ?” . Như vậy , việc theo vết đối tượng có thể được xem là việc ước lượng chuyển động tại các frame liên tiếp nhau , kết quả ước lượng tại frame này là cơ sở cho việc ước lượng ở frame tiếp theo . Hìn 2.12 : Vectơ dịch chuyển d ur 2.5 Hiện tượng che phủ (occlusion) Trong thực tế , tiến trình theo vết đối tượng video thường gặp phải hiện tượng che phủ . “Che phủ” đề cập đến hiện tượng các bộ phận của đối tượng (hay của khung cảnh) bị che đi hay hiện ra do những chuyển động của 33 camera hay của chính đối tượng . Hiện tượng này được phân làm hai loại : tự che phủ (self-occlusion) và che phủ lẫn nhau (mutual occlusion) . Tự che phủ chỉ hiện tượng các bộ phận của đối tượng bị che mất đi hay được hiện ra do những chuyển động của bản thân đối tượng . Che phủ lẫn nhau chỉ hiện tượng các bộ phận của đối tượng bị che mất đi hay được hiện ra do những chuyển động của đối tượng khác . Hình 2.13 : Hiện tượng tự che phủ Hình 2.14 : Hiện tượng che phủ lẫn nhau 34 Chương 3 Mô hình theo vết đối tượng sử dụng lưới hai chiều Xét đoạn video quay một khung cảnh , đối tượng video là những thành phần có ý nghĩa đầy đủ trong khung cảnh đó . Mặt phẳng alpha (alpha plane – AR) của một đối tương video được định nghĩa là tập hợp tất cả các điểm thuộc đối tượng đó . Theo vết đối tượng bao gồm việc theo vết đường biên (boundary) , theo vết những chuyển động cục bộ (local motion) và những biến đổi về cường độ (độ sáng tối , độ tương phản) của đối tượng . Theo mô hình mà luận văn đề ra , đối tượng video được biểu diễn bằng một lưới tam giác hai chiều . Lưới được thiết kế dựa theo nội dung của đối tượng . Việc theo vết đường biên (chuyển động toàn cục) , chuyển động cục 35 bộ cũng như những biến đổi về cường độ giờ trở thành việc theo vết lưới hai chiều . Như đã trình bày trong chương 1 , mô hình mà luận văn đề ra là mô hình bán tự động . Theo đó , người dùng sẽ đảm nhận trách nhiệm chọn frame bắt đầu , gọi là frame tham chiếu (reference frame) , và trên frame này chọn ra đối tượng video được quan tâm (tức là xác định mặt phẳng alpha của đối tượng được quan tâm) . Sau đó , trong các frame tiếp theo , việc theo vết đối tượng sẽ được thực hiện hoàn toàn tự động . Tổng quát , tiến trình theo vết đối tượng bao gồm các bước sau : o Bước 1 : Chọn frame tham chiếu và chọn đối tượng video được quan tâm o Bước 2 : Tạo lưới tam giác cho đối tượng o Bước 3 : Ước lượng chuyển động tại các node của lưới o Bước 4 : Lan truyền lưới Bước 1 và 2 được thực hiện tại frame tham chiếu , bước 3 và 4 được thực hiện tại mỗi frame tiếp theo . Người dùng chọn ra đối tượng bằng cách xác định mặt phẳng alpha của đối tượng đó . Đường biên của mặt phẳng alpha được xấp xỉ bằng một đa giác , gọi là đa giác tham chiều (hình 3.1) . Đa giác này cần được xác định sao cho càng sát với đường biên càng tốt . Chuyển động của đa giác tham 36 chiếu (tức chuyển động toàn cục của đối tượng) được mô tả bằng các vectơ dịch chuyển tại các node ứng với các đỉnh của đa giác (corner node) , còn chuyển động cục bộ bên trong đa giác tham chiếu (bên trong đối tượng) được mô tả bằng các vectơ dịch chuyển tại các node nằm bên trong đa giác (inner node) . Vectơ chuyển động tại các node được xác định bằng thuật toán so khớp khối (block matching) kết hợp với các chiến lược tìm kiếm . Hình 3.1 : Xấp xỉ đường biên của mặt phẳng alpha Do mô hình đề ra chưa giải quyết vấn đề che phủ (occlusion) nên giả thiết là trong suốt quá trình theo vết , kể từ frame bắt đầu (frame tham chiếu) đến frame kết thúc , không có hiện tượng che phủ xảy ra . 37 Tiếp theo , trong phần 3.1 , luận văn sẽ trình bày chi tiết về việc tạo lưới . Trong phần 3.2 , luận văn sẽ trình bày về phương pháp xác định vectơ dịch chuyển của các node lưới . Cuối cùng trong phần 3.3 , luận văn sẽ trình bày phần lan truyền lưới . 3.1 Tạo lưới Lưới tam giác là lưới mà mỗi phần tử (mắt lưới) là một tam giác . Tạo lưới tam giác cho một đối tượng nghĩa là áp một lưới tam giác lên mặt phẳng alpha của đối tượng đó . Ta chỉ xét dạng lưới tuyến tính , là dạng lưới mà các cạnh thuộc các mắt lưới đều là đường thẳng , không phải là đường cong . Do đó , đường biên của đối tượng cần phải được xấp xỉ bằng một polyline khép kín (đa giác) . Theo [4] phép tạo lưới tam giác được coi là tối ưu nếu ứng với mỗi tam giác thành viên của lưới vừa tạo , ba đỉnh của tam giác là ba đỉnh gần nhất đối với các điểm thuộc miền tam giác đó (hình 3.2) . Có hai tiêu chuẩn thường được sử dụng để tối ưu hóa phép tạo lưới tam giác đó : 1. Tiêu chuẩn Max-Min : tam giác thành viên được tạo sao cho cực đại hóa góc nhỏ nhất (hình 3.3) 2. Tiêu chuẩn Vòng tròn : tam giác thành viên được tạo sao cho vòng tròn ngoại tiếp của nó không chứa đỉnh thuộc tam giác khác (hình 3.4) . 38 Hình 3.2 : Phép tạo lưới tam giác tối ưu và không tối ưu Hình 3.3 : Tiêu chuẩn Max-Min 39 Hình 3.4 : Tiêu chuẩn Vòng tròn Trong mô hình đề ra , luận văn sử dụng lưới tam giác tối ưu và được thiết kế dựa theo nội dung của đối tượng . Theo [6] , nguyên tắc cơ bản trong việc thiết kế lưới dựa theo nội dung là đặt các node của lưới lên các cạnh có cường độ lớn và định vị sao cho giá trị của hàm DFD (Displaced Frame Difference) tại các mắt lưới là xấp xỉ nhau . Hàm DFD tính tại vị trí (x ,y) được cho bởi công thức : DFD(x ,y) = ( IC(x ,y) – IR(x ,y) )P trong đó , IC(x ,y) và IR(x ,y) là cường độ điểm ảnh tại vị trí (x ,y) trên hai frame được xét , thường là frame k và frame k-1 hay frame hiện hành và frame tham chiếu ; còn p là một số nguyên dương , thông thường p=2 . 40 Thuật toán tạo lưới tổng quát bao gồm những bước sau : o Bước 0 : Khởi tạo tập node = ∅ , chọn các đỉnh của đa giác tham chiếu đưa vào tập node . Đa giác tham chiếu chính là đường biên bao ngoài của lưới . o Bước 1 : Gán nhãn “unmarked” cho tất cả các pixel thuộc đối tượng o Bước 2 : Tính giá trị DFD trung bình cho tất cả các pixel có nhãn “unmarked” ( , ) & ( , ) ( , ) p x y AR x y unmarked avg DFD x y DFD K ∈= ∑ AR là kí hiệu mặt phẳng alpha của đối tượng , K là số lượng pixel có nhãn “unmarked” , p=2 o Bước 3 : Với mỗi pixel được có nhãn “unmarked” , tính giá trị hàm lượng giá : 2( , ) | ( , ) |C x y I x y= ∇ |∇I(x,y)| là độ lớn của vectơ gradient cường độ điểm ảnh tại pixel (x,y) 41 o Bước 4 : Tìm pixel có nhãn “unmarked” và có giá trị C(x,y) cao nhất , chọn pixel đó làm node mới và đưa vào tập node của lưới . o Bước 5 : Lấy node vừa chọn được làm tâm , thực hiện lan rộng vùng ra các pixel “unmarked” xung quanh cho đến khi giá trị DFDavg của vùng lớn hơn giá trị DFDavg tính ở bước 2 , đánh dấu “marked” cho tất cả các pixel trong vùng vừa tạo được . o Bước 6 : Nếu tất cả các pixel đều đã được đánh dấu “marked” thì chuyển qua bước 7 , nếu không thì quay lại bước 2 . o Bước 7 : Thực hiện phép tạo lưới tam giác Delauney trên tập node vừa chọn được . Vectơ gradient cường độ điểm ảnh (spatial intensity gradient) Đạo hàm là một công cụ rất hữu hiệu để đo tốc độ thay đổi của sự vật . Xét hàm số một biến y = f(x) , đạo hàm theo biến x được cho bởi công thức : 0 0 ( ) ( )'( ) lim lim x h y f x h f xf x x h∆ −> −> ∆ + −= =∆ Như đã đề cập trong chương 2 , ảnh tĩnh là một phân bố cường độ theo không gian , ta có thể biểu diễn ảnh tĩnh như một hàm hai biến I(x, y) với x ứng với hoành độ , y ứng với tung độ và I(x, y) cho biết cường độ điểm ảnh tại điểm (x, y) . Đạo hàm của hàm I(x, y) theo biến x cho biết tốc độ thay đổi 42 của cường độ điểm ảnh theo hoành độ , tương tự , đạo hàm theo biến y cho biết tốc độ thay đổi của cường độ điểm ảnh theo tung độ . 0 ( , ) ( , )lim h f f x h y f x y x h−> ∂ + −=∂ 0 ( , ) ( , )lim h f f x y h f x y y h−> ∂ + −=∂ Khi đó , vectơ gradient cường độ điểm ảnh tại điểm ảnh (x, y) , kí hiệu ∇I(x, y) , được xác định bởi : ( , ) ( ( , ), ( , )) ( , )x y f fI x y I x y I x y x y ∂ ∂∇ = ∇ ∇ = ∂ ∂ Và độ lớn của vectơ gradient được xác định bởi : 2 2 2 2| ( , ) | | ( , ) | | ( , ) | ( ) ( )x y f fI x y I x y I x y x y ∂ ∂∇ = ∇ + ∇ = +∂ ∂ Đối với ảnh số , |∇Ix(x ,y)| và |∇Iy(x ,y)| được tính xấp xỉ như sau : | ( , ) | ( , ) ( 1, )xI x y I x y I x y∇ = − − hay 1| ( , ) | [ ( 1, ) ( 1, )] 2x I x y I x y I x y∇ = + − − 43 | ( , ) | ( , ) ( , 1)yI x y I x y I x y∇ = − − hay 1| ( , ) | [ ( , 1) ( , 1)] 2y I x y I x y I x y∇ = + − − Phép tạo lưới tam giác Delauney Phép tạo lưới Delauney là phép tạo lưới tối ưu dựa theo tiêu chuẩn “Vòng tròn” đã đề cập ở trên , nghĩa là tam giác thành viên được tạo sao cho vòng tròn ngoại tiếp của nó không chứa đỉnh của tam giác khác . Đã có nhiều thuật toán tạo lưới tam giác Delauney được đưa ra , tiêu biểu như : – Thuật toán Chèn tăng tiến (Incremental Insertion Algorithm) của tác giả Lawson (Mathematical Software III–1977) và cải tiến của thuật toán này do tác giả Watson đưa ra năm 1981 (Computer Journal 24) . – Thuật toán Chia để trị (Divide and Conquer Algorithm) của các tác giả D. T. Lee và B. J. Schachter (International Journal of Computer and Information Sciences–1980) và cải tiến của thuật toán này do tác giả Rex A. Dwyer đưa ra năm 1987 (Algorithmica 2) . – Thuật toán Đảo dòng (Sweepline Algorithm) do tác giả Steven Fortune đưa ra năm 1987 (Algorithmica 2) . Theo [13] , thuật toán Chia để trị và Đảo dòng được đánh giá là tốt hơn Chèn tăng tiến , rất tiếc là luận văn chưa tìm được những tài liệu mô tả rõ ràng hai thuật toán này nên không thể trình bày ở đây . 44 Thuật toàn Chèn tăng tiến (Incremental Insertion Algorithm) của tác giả Watson Thuật toán được trình bày một cách trực quan như sau : Cho một tập điểm ứng viên : Bước 0 : bao tập điểm bằng một lưới tam giác Delauney hợp lệ 45 Bước 1 : lấy ra một đỉnh tùy ý từ tập ứng viên , chèn vào lưới Bước 2 : Xóa những tam giác nào có vòng tròn ngoại tiếp chứa điểm vừa chèn vào 46 Bước 3 : Tạo lưới tam giác mới từ các đỉnh của đường bao lồi của điểm vừa chèn vào và bản thân điểm đó Bước 1, 2, 3 được lặp cho đến khi không còn điểm nào để chèn vào lưới , cụ thể là : 47 Kết quả cuối cùng : Các điểm Steiner Trong thực tế , với một tập điểm input bất kì , không phải lúc nào các thuật toán cũng có thể tạo được lưới tam giác tối ưu , ví dụ như tập điểm input là các đỉnh của chữ A : 48 Giải pháp cho những trường hợp này là trên các cạnh của lưới ta thêm vào các điểm mới , gọi là các điểm steiner , sao cho lưới tạo từ tập điểm mới thỏa được các điều kiện của lưới tối ưu . Việc thêm vào các điểm steiner còn giúp thiết lập được các ràng buộc về góc tối thiểu , chẳng hạn như ràng buộc không có tam giác thành viên nào có góc nhỏ hơn 30° . Có hai luật cơ bản trong quá trình thêm vào các điểm steiner : – Luật đường tròn xuyên tâm (diametral circle) : ứng với mỗi cạnh của lưới, dựng đường tròn nhận cạnh đó làm đường kính , nếu có đỉnh thứ ba lọt vào đường tròn thì thực hiện việc thêm điểm steiner vào trung điểm của cạnh đang xét . – Luật đường tròn ngoại tiếp (circumcircle) : nếu một tam giác thành viên có góc quá nhỏ , không thỏa ràng buộc về góc tối thiểu thì thực hiện việc thêm điểm steiner vào vị trí tâm đường tròn ngoại tiếp của tam giác đó . 49 3.2 Ước lượng chuyển động tại các node của lưới Ước lượng chuyển động tại các node của lưới tức là tìm ra vectơ dịch chuyển của các node đó . Khái niệm về vectơ dịch chuyển đã được trình bày trong chương 2 . Chuyển động toàn cục của đối tượng (tức chuyển động của đường biên của lưới) được mô tả bằng các vectơ dịch chuyển tại các node thuộc đường biên . Còn các chuyển động cục bộ bên trong đối tượng được mô tả bằng các vectơ dịch chuyển tại các node nằm bên trong đường biên . Để tìm ra các vectơ này , luận văn sử dụng phương pháp so sánh khối kết hợp với các chiến lược tìm kiếm . 50 Vectơ dịch chuyển tại một điểm ảnh trên frame k được xác định khi ta tìm ra vị trí tương ứng của điểm đó trong frame k+1 . Tuy nhiên , nếu chỉ dựa vào giá trị cường độ của một điểm ảnh thì không đủ để có thể tìm được chính xác vị trí của điểm ảnh đó trong frame mới . L ý do đơn giản là vì xung quanh một điểm ảnh thường có nhiều điểm có cùng giá trị cường độ với điểm ảnh đó . Vậy , nếu không thể chỉ dựa vào thông tin của bản thân điểm ảnh thì ta có thể kết hợp thêm thông tin từ các điểm láng giềng . Đây chính là tiền đề của phương pháp so khớp khối . Theo phương pháp này , để tìm ra vị trí mới của điểm ảnh (x ,y) trên frame k+1 , ta sẽ xét một khối kích thước N1×N2 có tâm là (x ,y) trên frame k và tìm khối tương ứng trên frame k+1 , khi đó vị trí mới của điểm ảnh (x ,y) trên frame k+1 sẽ là vị trí cho kết quả so sánh khối tốt nhất . Việc tìm kiếm khối tương ứng được giới hạn trong một vùng kích thước (N1+2M1)×(N2+2M2) , gọi là cửa sổ tìm kiếm (search window) , nhằm tiết kiệm chi phí tính toán . 51 Ý tưởng trên được áp dụng cho các node để tìm ra vectơ dịch chuyển tươnng ứng (hình) Các thuật toán block-matching khác nhau ở những điểm sau : – Tiêu chuẩn đánh giá việc so khớp – Chiến lược tìm kiếm – Cách xác định kích thước khối 3.2.1 Tiêu chuẩn đánh giá Các tiêu chuẩn thường được sử dụng là Trung bình bình phương sai số (Mean Square Error–MSE) , Trung bình trị tuyệt đối sai số (Mean Absolute Error–MAD) Mean Square Error (MSE) 2 1 2 1 1 2 ,1 2 1( , ) [ ( , ) ( , )]k k x y B MSE d d I x y I x d y d N N −∈ = − + +∑ 52 trong đó B là khối N1×N2 , Ik(x ,y) là cường độ điểm ảnh tại vị trí (x ,y) trên frame k , d ur =(d1 ,d2) là vectơ dịch chuyển ứng viên . Mean Absolute Difference (MAD) 1 2 1 1 2 ,1 2 1( , ) | ( , ) ( , ) |k k x y B MAE d d I x y I x d y d N N −∈ = − + +∑ 3.2.2 Các chiến lược tìm kiếm Chiến lược ba bước (Three Step Search – TSS) Chiến lược tìm kiếm này do Koga đề ra năm 1981 . Đây là một chiến lược rất phổ biến bởi nó đơn giản và hiệu quả . Ý tưởng như sau : – Bước 1 : Khởi tạo kích thước bước tìm kiếm (k) . Thực hiện việc so khớp tại chín vị trí : một vị trí tại tâm và tám vị trí tại các lân cận cách tâm một khoảng ứng với k . Di chuyển tâm đến vị trí có kết quả so khớp tốt nhất . – Bước 2 : Giảm k đi một nửa , nếu k≤1 thì qua bước 3 . Thực hiện việc so khớp tại tám vị trí xung quanh tâm tương ứng với k . Di chuyển tâm đến vị trí có kết quả so khớp tốt nhất . Quay lại bước 2 . – Bước 3 : Thực hiện việc so khớp tại tám vị trí xung quanh tâm tương ứng với k . Di chuyển tâm đến vị trí có kết quả so khớp tốt nhất . Đó chính là vị trí cần tìm . 53 Chiến lược tìm kiếm logarithm (Two Dimensional Logarithmic Search – TDL) Chiến lược này được Jain giới thiệu gần như cùng thời điểm với Three Step Search . Nó được đánh giá là tốt hơn TSS , đặc biệt trong những trường hợp có cửa sổ tìm kiếm lớn . Ý tưởng của chiến lược như sau : – Bước 0 : Khởi tạo kích thước bước tìm kiếm (k) . – Bước 1 : Thực hiện so khớp khối tại vị trí tâm và bốn vị trí : trên , dưới , trái , phải của tâm . – Bước 2 : Nếu vị trí có kết quả so khớp tốt nhất là tại tâm thì giảm k đi một nửa , nếu k≤1 thì qua bước 3 . Nếu vị trí tốt nhất không là tâm thì di chuyển tâm đến vị trí mới . Quay trở lại bước 1 . 54 – Bước 3 : Thực hiện việc so khớp tại tâm và tám vị trí lân cận tương ứng với k . Vị trí cho kết quả tốt nhất chính là vị trí cần tìm . Chiến lược bốn bước (Four Step Search – FSS) Chiến lược này do Lai-Man Po và Wing-Chung Ma đưa ra vào năm 1996. Ý tưởng của chiến lược như sau : – Bước 1 : Bắt đầu với bước tìm kiếm k = 2 . Thực hiện việc so khớp tại chín vị trí , một tại tâm và tám tại các vị trí lân cận cách tâm một khoảng k . Nếu vị trí cho kết quả tốt nhất là vị trí tâm thì qua bước 4 , ngược lại thì qua bước 2 . – Bước 2 : Di chuyển tâm đến vị trí có kết quả so khớp tốt nhất , k vẫn giữ nguyên , sau đó xét : ƒ Nếu vị trí tốt nhất là ở góc thì ta xét tiếp năm điểm như trong hình ƒ Nếu vị trí tốt nhất là tại vị trí giữa của cạnh ngang hay cạnh dọc thì ta xét ba điểm tiếp như trong hình 55 Di chuyển tâm đến vị trí tốt nhất . Nếu đó là vị trí tâm thì qua bước 4 , ngược lại thì qua bước 3 . – Bước 3 : Quay trở lại bước 2 – Bước 4 : k =1 , thực hiện so khớp tại chín vị trí , một tại tâm và tám tại các vị trí lân cận cách tâm một khoảng k . Vị trí cho kết quả tốt nhất chính là vị trí cần tìm . 56 3.2.3 Không gian tìm kiếm hợp lệ Trong quá trình ước lượng chuyển động tại các node của lưới , nếu ta không giới hạn cửa sổ tìm kiếm của các node trong một không gian tìm kiếm hợp lệ thì tính toàn vẹn về kết cấu của lưới có thể bị vi phạm , ví dụ : frame k frame k+1 Để có thể minh họa rõ ràng khái niệm không gian tìm kiếm hợp lệ , ta chia các node của lưới thành ba loại : node góc (corner node) ứng với các đỉnh của đa giác tham chiếu , node biên (boundary node) ứng với các điểm steiner được thêm vào đường biên và node trong (inner node) ứng với các node nằm trong đường biên . Corner node 57 Đối với corner node , không gian tìm kiếm hợp lệ là miền được gạch chéo trong hình Boundary node Đối với boundary node , không gian tìm kiếm hợp lệ là đoạn AB Inner node Đối với inner node , không gian tìm kiếm hợp lệ là miền đa giác được gạch chéo 58 3.3 Lan truyền lưới Dựa vào tập vectơ chuyển động tại các node đã tìm được ở bước trên , ta thực hiện việc lan truyền lưới , tức là xác định vectơ chuyển động của tất cả các điểm ảnh còn lại . Theo mô hình lưới hai chiều , 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 . Đối với lưới tam giác thì phép biến đổi không gian được chọn là phép biến đổi affine , bởi phép biến đổi này có sáu hệ số tự do và với ba tương ứng điểm ảnh tại ba đỉnh tam giác , ta có thể được suy ra các hệ số này . Biểu diễn tổng quát của phép biến đổi affine có dạng : 1 2 3 4 5 6 ' ' a a ax x a a ay y       = +             Từ ba đỉnh (x1 ,y1) , (x2 ,y2) , (x3 ,y3) tìm ra ba điểm ảnh tương ứng (x’1 ,y’1) , (x’2 ,y’2) , (x’3 ,y’3) . Từ ba cặp tương ứng này , ta có thể tính ra các hệ số tự do trong () bằng cách giải hệ phương trình tuyến tính : 59 ' ' 1 11 1 ' ' 2 11 1 ' ' 3 22 2 ' ' 4 22 2 ' ' 5 33 3 ' ' 6 33 3 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 a xx y a yx y a xx y a yx y a xx y a yx y                 =                         Sau khi đã xác định xong các hệ số , tất cả các điểm trong tam giác sẽ được dịch chuyển thông qua phép biến đổi affine vừa tìm được . 60 Chương 4 Cài đặt và thử nghiệm Toàn bộ mô hình theo vết đối tượng sử dụng lưới hai chiều mà luận văn đề ra bao gồm bốn nội dung chính : 1. Chọn frame tham chiếu và chọn đối tượng video được quan tâm 2. Tạo lưới tam giác cho đối tượng 3. Ước lượng chuyển động tại các node của lưới 4. Lan truyền lưới Luận văn đã cài đặt hoàn chỉnh phần chọn frame tham chiếu và xác định mặt phẳng alpha của đối tượng (nội dung thứ nhất) , cài đặt hoàn chỉnh phần tạo lưới tối ưu với thiết kế dựa theo nội dung của đối tượng (nội dung thứ hai) . Trong nội dung thứ ba , luận văn cài đặt xong phần ước lượng chuyển động tại các corner node , bao gồm phương pháp so khớp khối và các chiến lược tìm kiếm ; rất tiếc là đối với các inner node và boundary node , do chưa giải quyết được việc giới hạn không gian tìm kiếm nên không thể thực hiện 61 chính xác được việc ước lượng chuyển động và phần cài đặt đành phải dừng ở đây . 4.1 Chi tiết phần cài đặt Công cụ Chương trình demo được thực hiện trên môi trường Visual C++ 6.0 , các thư viện sử dụng gồm bộ thư viện Dali của trường đại học Cornell dùng để giải mã file MPEG và bộ thư viện BCGControlBarPro dùng để tạo giao diện cho chương trình . Nội dung chương trình Chương trình bao gồm các phần chính sau : 1. Lớp MPEGDecoder : giải mã file MPEG 2. Lớp MPEGViewer : hiện thị file MPEG 3. Lớp MPEG : lớp bao ngoài của hai lớp trên 4. Lớp FrameBuffer và Frame : quản lý các bộ đệm dùng trong quá trình giải mã và hiển thị file MPEG 5. Lớp VideoObject : lưu trữ và xử lý các nội dung liên quan đến đối tượng video 6. Dll TriMesh : chứa các hàm tạo lưới 7. Lớp TrackingAlgorithm : thực hiện các bước trong quá trình theo vết đối tượng 4.2 Kết quả thử nghiệm Mô hình được thử nghiệm trên hai đoạn video số theo chuẩn MPEG-1 , được đặt tên là “book1” và “clock1” , mỗi đoạn gồm có 20 frame . Ứng với 62 mỗi đoạn , ba thuật toán so khớp khối ứng với ba chiến lược tìm kiếm (Three Step Search , Logarithmic Search và Four Step Search) được chạy thử nghiệm . Tất cả các tính toán đều được thực hiện trên thành phần độ sáng (luminance – Y) . Do mô hình chưa cài đặt hoàn chỉnh nên hiệu ứng quan sát được không phải là toàn bộ đối tượng mà chỉ có đường viền của đối tượng được theo vết mà thôi . 4.2.1 “Book 1” Mặt phẳng alpha Lưới tam giác Frame tham chiếu 63 Logarithmic Search Frame 2 Frame 10 Frame 20 64 Three Step Search Frame 2 Frame 10 Frame 20 65 Four Step Search Frame 2 Frame 10 Frame 20 66 4.2.2 “Clock 1” Mặt phẳng alpha Lưới tam giác Frame tham chiếu Logarithmic Search Frame 2 Frame 10 67 Frame 20 Three Step Search Frame 2 Frame 10 68 Frame 20 Four Step Search Frame 2 Frame 10 69 Frame 20 Các kết quả cho thấy , chiến lược Four Step Search đạt được kết quả tốt nhất , kế đến là Three Step Search , cuối cùng là Logarithmic Search . Có thể giải thích việc Logarithmic Search cho kết quả kém nhất là do chiến thuật này xét ít điểm hơn , chỉ khởi đầu với 5 điểm : trên , dưới , trái , phải của tâm và bản thân vị trí tâm . Trong khi các chiến thuật FSS và TSS đều khởi đầu với 9 điểm kể cả tâm . 70 Chương 5 Tổng kết và hướng phát triển Theo vết đối tượng là một đề tài mới thuộc lĩnh vực xử lý video . Với nhiều ứng dụng hữu ích trong thực tế , đề tài đã và đang thu hút sự quan tâm của cộng đồng nghiên cứu . Trong phạm vi của mình , luận văn đã trình bày những nội dung cơ bản của vấn đề theo vết đối tượng , đồng thời đề ra một mô hình theo vết sử dụng lưới tam giác hai chiều có thiết kế dựa theo nội dung của đối tượng . Những kết quả cài đặt cụ thể đã phần nào thể hiện được tính đúng đắn của mô hình . Thực tế vẫn còn rất nhiều vấn đề cần phải giải quyết . Trước hết là hoàn chỉnh phần cài đặt của mô hình . Tiếp đó là thực hiện tối ưu hóa từng bước trong mô hình đề ra , nghiên cách tạo lưới tốt hơn , tìm ra những chiến lược tìm kiếm mạnh mẽ hơn . Ở bước đầu của mô hình , người sử dụng vẫn phải đảm nhận nhiều thao tác . Cần tìm ra cách làm giảm bớt trách nhiệm cho người dùng . Hiện tại , tất cả các tính toán đều được thực hiện trên thành phần độ sáng (luminance – Y) , những thử nghiệm trên các không gian màu khác hứa hẹn những kết quả khả quan hơn . Một phần quan trọng nữa cần phải thực hiện là giải quyết hiện tượng che phủ , điều này sẽ giúp cho mô hình có thể ứng dụng vào thực tế . 71 Tài liệu tham khảo [1] A.Murat Tekalp , Digital Video Processing , Prentice Hall , 1995 [2] Steven W. Smith , Digital Signal Processing , California Technical Publishing , 1997 [3] Nhiều tác giả , Handbook of Image & Video Processing , Academic Press , 2000 [4] Geogre Wolberg , Digital Image Warping , IEEE Computer Vision Press , 1990 [5] Cademir Toklu , “Object-Based Digital Video Processing Using 2-D Meshes” , 1998 [6] Yucel Altunbasak , A.Murat Tekalp , “Occlusion-Adaptive , Content- Based Mesh Design and Forward Tracking” , 1996 [7] Hoàng Kiếm , Dương Anh Đức , Lê Đình Duy , Cơ Sở Đồ Họa Máy Tính , Nhà xuất bản Giáo Dục , 2000 [8] Deepak Turaga , Mohamed Alkanhal , “Search Algorithms for Block- Matching in Motion Estimation” , 1998 [9] Peter van Beek , A.Murat Tekalp , Ning Zhuang , Isil Celasun và Minghui Xia , “Hierarchical 2D Mesh Representation , Tracking and Compression for Object-Based Video” , IEEE Transactions On CSVT , 1998 [10] Bilge Gunsel , A.Murat Tekalp và Peter J. L. van Beek , “Content- Based Access to Video Objects : Temporal Segmentation , Visual Summarization , and Feature Extraction” , 1997 72 [11] Isil Celasun , Minghui Xia , Peter J. L. van Beek và A.Murat Tekalp , “Hierarchical 2D Mesh Design and Compression for Video” , 1999 [12] Jonathan Richard Shewchuk , Triangle , 1996 [13] Jonathan Richard Shewchuk , “Triangle: Engineering a 2D Quality Mesh Generator and Delaunay Triangulator” , 1996 [14] David L. Marcum , “SIAM Short Course on Unstructured Mesh Generation” , SIAM Conference on Geometric Design and Computing , 4 November 2001 Sacramento , CA [15] Hoàng Kiếm , Trần Hạnh Nhi , Dương Anh Đức , Nhập Môn Cấu Trúc Dữ Liệu và Thuật Toán , ĐH Khoa Hoc Tự Nhiên , Khoa Công Nghệ Thông Tin , 2000. [16] Dave Marshall , “Introduce to Multimedia” , 2001 [17] Pekin Erhan Eren , “Object-Based Digital Video Analysis and Manipulation For Multimedia Applications” , University of Rochester , NewYork , 2002 [18] Yucel Altunbasak and A.Murat Tekalp , “Closed-Form Connectivity- Preserving Solutions for Motion Compensation Using 2-D Meshes” , IEEE Transactions on Image Processing , Vol 6 , No.9 , September 1997 [19] Isil Celasun , A.Murat Tekalp , “Optimal 2D Hierarchical Content- Based Mesh Design and Update for Object-Based Video” , 2000 [20] Ghassan Al-Regib , Yucel Altunbasak , Russell M. Mersereau , “Hierarchical Motion Estimation with Content-Based Meshes” , 2003 [21] Ghassan Al-Regib , Yucel Altunbasak , “2-D Motion Estimation with Hierarchical Content-Based Meshes” , 1999 [22] Y. Nakaya và H. Harashima , “Motion compensation based on spatial transformation” , IEEE Trans. Circuits and Syst. Video Tech., vol. 3 , pp. 339 - 357 , June 1994