MultiBooks - Tổng hợp IT - PC part 18

Tham khảo tài liệu multibooks - tổng hợp it - pc part 18, công nghệ thông tin, kỹ thuật lập trình phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả
Nội dung trích xuất từ tài liệu:
MultiBooks - Tổng hợp IT - PC part 18endrectangle = record XLB, XUB, YLB, YUB: interger; objlist:objnode; day, mth, yr:integer; camera_type: string; other_info: data_record; (* Lưu trữ thông tin về chữ nhật*) place: stringendobjnode = record objid: string; imageid: string; data: infotype (* Lưu trữ thông tin tuỳ ý về đối tượng*) nxt: objnodeendinfotype = record objname: string; objdata: objdata_record; Lp, Up: real; (* Biên trên, dưới của xác suất *) Next: infotypeendTrong định nghĩa của objnode trên đây, Lp và Up ký hiệu biên trên và biên dướicủa xác suất mà sự nhận diện này là đúng.Hãy xem xét CSDL ảnh đơn giản đã mô tả ở đầu chương, chỉ bao gồm các ảnhpic1.gif, pic2.gif và pic3.gif trong hình 3.1. Giả sử các ảnh này chứa đối tượng o1,o2, o3 và o4 với khoảng xác suất chỉ ra trên đây trong phiên bản xác suất khoảngcủa quan hệ name. Hình 3.12 cho thấy cây R được sử dụng để biểu diễn ba ảnh nàyvà bốn đối tượng trên đó. Cây R trên hình 3.12 được xây dựng theo các bước sau:1. Error!Lấy chữ nhật: Trước hết ta xây dựng bảng con mô tả các chữ nhật và ảnh. Hình3.13 chỉ ra bốn chữ nhật o1, o2, o3 và o4. Chú ý rằng mặc dù các chữ nhật này cóđược từ các ảnh khác nhau, chúng ta có thể chồng chúng lên trong cùng một ảnh.2. Tạo cây R: Tạo cây R biểu diễn các chữ nhật trên (hình 3.12). Tại bước nàycác nút đối tượng trong cây R vẫn chưa được làm đầy. ObjId ImageId XLB XUB YLB YUB o1 pic1.gif 10 60 5 50 o2 pic1.gif 80 120 20 55 o3 pic2.gif 20 65 20 75 o4 pic3.gif 25 75 10 603. Error!Bổ sung đối tượng: Chúng ta bổ sung đối tượng và làm đầy các trường tương ứngcủa các đối tượng khác nhau lưu trong cây R. Hình 3.14 chỉ ra nội dung của cácnút khác nhau khi đối tượng mới o được bổ sung vào hệ thống, và đối tượng mớinày có cùng các trường XLB, XUB, YLB và YUB như đối tượng o1. Chỉ có một sựkhác biệt giữa đối tượng o1 và đối tượng mới o là ở chỗ đối tượng mới o xuất hiệntrong ảnh khác.3.7.1 Biểu diễn CSDL ảnh bằng cây R tổng quátBiểu diễn dữ liệu ảnh bằng cây R mô tả trên đây không cho khả năng tìm kiếmláng giềng gần nhất. Lý do là mỗi đối tượng o có chữ nhật liên kết, Ro. Tuy nhiên,chữ nhật này là chữ nhật 2-d như chỉ ra trên hình 3.14. Cách biểu diễn này lưu trữcác thuộc tính của mỗi đối tượng trong trường “Data” của nó. Vì trường “Data”không được sử dụng để tạo ra chỉ số R-tree, có nghĩa rằng truy vấn trên cơ sở cáctrường này là không hiệu quả, việc tìm kiếm láng giềng gần nhất trở nên nặng nề.Có hai mở rộng không phức tạp về cây R có thể sử dụng để giải quyết vấn đề này.Thứ nhất dựa trên cơ sở khái niệm của cây R khái quát hóa (gR-tree) mô tả dướiđây. Thứ hai dựa trên cơ sở cây véctơ lồng nhau (telescoping vector tree) sẽ đượcmô tả sau.Nhớ lại rằng đối tượng o có thể được biểu diễn bởi vùng trong không gian n+2chiều, nơi mà mỗi đối tượng có n đặc trưng và không gian hai chiều khác biểu diễnchữ nhật bao đối tượng. Chữ nhật tổng quát hóa cho không gian có số chiều g (cóthể coi g=n+2) được xác định bởi tập các ràng buộc sau:l1 £ x1 £ u1l2 £ x2 £ u2...lg £ xg £ ugChú ý rằng khi g=2, chúng ta có n=0, khi đó chữ nhật 2-d là trường hợp đặc biệtcủa định nghĩa này.Nếu bây giờ ta có tập đối tượng Obj, chúng ta có thể biểu diễn tập đối tượng nàybởi tập ràng buộc (n+2)-d. Cây R khái quát hoá (gR-tree) bậc K hoàn toàn giốngcây R trừ các hệ số sau đây.· Khi nút N biểu diễn chữ nhật bao khái quát hóa GBR(N) của số chiều (n+2),nó được biểu diễn bởi 2x(n+2) trường số thực, cho cận dưới và cận trên của mỗichiều.· Khi nút N bị bẻ gẫy, hợp nhất của các chữ nhật bao khái quát hóa với con củachúng chữ nhật bao khái quát hóa kết hợp với N.· Mỗi nút (không phải là gốc và lá) chứa nhiều nhất k chữ nhật bao khái quáthóa và ít nhất [K/2] chữ nhật khái quát hóa.· Thông thường, mọi chữ nhật (n+2)-d được lưu trữ tại lá.Do đó, cây gR được định nghĩa đúng như cây R, trừ khi các nút chứa tập các chữnhật bao khái quát hóa thay cho tập các chữ nhật bao 2-d. Rõ ràng, cấu trúc của nútđược mở rộng để mô tả cận trên và cận dưới của (n+2)-d. Tìm kiếm láng giềng gầnnhất có thể được thực hiện hiệu quả như sau đây.Giả sử Rq là chữ nhật truy vấn (nó có thể biểu diễn đối tượng ảnh). Ta muốn tìmmọi chữ nhật trong cây gR có tên T mà nó gần Rq nhất (mức gần được xác định bởithước đo d trên các điểm). Ta mở rộng thước đo d để áp dụng vào chữ nhật nhưsau: d(R, R’) = min{d(p, p’) | pÎ R, p’ Î R’}Tiến trình tìm kiếm được thể hiện trong giải thuật sau:Giải thuật 3.5 NN_Search_GR(T, RQ) SOL=NIL; (* cho đến bây giờ chưa có giải pháp *); Todo = List containing T only; Bestdist = ¥; (* khoảng cách của giải ...