Algorithms for two-dimensional shape analysis using concavity trees
Luận án · Tiến sĩ · năm 2006 · đề tài tham khảo
| Loại tài liệu | Luận án |
|---|---|
| Bậc học | Tiến sĩ |
| Ngành | Công nghệ thông tin |
| Tác giả | Ossama El Badawy |
| Cơ sở đào tạo | Đại học Quốc gia TP. Hồ Chí Minh |
| Năm | 2006 |
| Nguồn | Thư viện số Đại học Quốc gia TP. Hồ Chí Minh · trang gốc |
Tóm tắt
This thesis presents data structures and algorithms for the analysis of the 2-D shape of patterns. In this work, a pattern is typically an object in a bi-level image and analyzing it involves two main ingredients: representing it in computer memory; and determining its degree of similarity to other patterns. The core idea around which this work is based is that of the convex hull of a set of points in the plane; after all, an object is a set of pixels in the plane of the image. From the simple concept of the convex hull stems the more involved concept of a concavity tree, a data structure that has remained largely unstudied, especially in connection to shape analysis. We present an efficient contour-based algorithm for concavity tree extraction, detailing its use in the decomposition of 2-D shapes into, and their reconstruction from, convex polygons. We compare the performance of the proposed algorithm with that of other existing algorithms and we report smaller reconstruction errors and faster execution speeds. We then introduce modifications to the contour-based algorithm that allow the resulting trees to better capture shape information for similarity matching purposes. We also propose a concavity tree matching algorithm that takes as input two labelled trees and returns the distance between them as a measure of the dissimilarity between the corresponding shapes. We then propose an efficient method for nearest-neighbour shape-based image retrieval based on concavity trees that allow for a query to be matched to a database without the need to fully compare the query against all the database entries. The shape matching abilities of concavity trees are evaluated and results and comparisons are reported. We show that concavity trees are able to boost the performance of global shape features by as much as 20% when those features are used to label the nodes of the trees. We also show how any shape matching metric that returns a "normalizable" distance between two silhouettes can be plugged in the proposed concavity tree matching algorithm, consistently resulting in a measurable improvement in the former's matching ability at a small performance cost. While their overall matching precision is not as good as the current state-of-the-art in shape matching when applied to data sets like MPEG7, concavity trees do provide a performance edge (in terms of computational complexity and retrieval time), allowing them to be used for first-stage matching, for example. Representing a shape using its concavity tree can be made a reversible process. That is, by storing appropriate information in the tree nodes, it is possible to reconstruct the original image from its tree representation. We take this idea further and show how, with some modifications to the core algorithm, a very compact and reversible representation of a shape can be computed during concavity-tree extraction. This new representation can be exact, or approximate to a pre-set degree, making it equivalent to a lossless or lossy compression of the image containing the shape. We report near-lossless compression ratios that are 40% better than the JBIG standard on the MPEG7 dataset. This technique allows for shape information to be extracted, possibly for shape retrieval and matching purposes, without the need to fully decompress the image (i.e., in the compressed domain). We also show how to extend the technique to images containing multiple shapes, with or without holes. In making the above technique applicable to arbitrary bi-level images while maintaining its low computational complexity, an on-line linear-time algorithm for computing the convex hull of a class of complex polygons was devised. Based on Melkman's simple-polyline algorithm, the proposed algorithm makes it possible to extract both, the contour of an object, as well as its convex hull, in one sequential pass, even when those contours form complex polygons. When an image contains multiple objects, each will have its
Bản toàn văn lưu tại thư viện Đại học Quốc gia TP. Hồ Chí Minh
Thông tin và tóm tắt ở trên lấy từ kho số mở của thư viện trường. Bản toàn văn do thư viện trường quản lý — có nơi cho đọc trực tuyến, có nơi cần tài khoản bạn đọc của trường.
Mở tại thư viện trường ↗
Dùng tài liệu tham khảo cho đúng
- Đọc để hiểu cách người trước đặt câu hỏi, chọn phương pháp, trình bày số liệu — rồi tự làm với dữ liệu và bối cảnh của bạn.
- Ý, số liệu, bảng biểu lấy từ tài liệu này phải trích dẫn (tác giả, năm, tên đề tài, cơ sở đào tạo).
- Đề tài trùng tên vẫn làm được nếu khác đơn vị khảo sát, thời gian hoặc cách tiếp cận — nêu rõ điểm khác trong phần mở đầu.
Hướng dẫn chọn đề tài, cấu trúc và số liệu cho ngành này: Luận văn công nghệ thông tin · Hỏi đáp từng chương với người hướng dẫn số: Học Giả Số · Công cụ số: Luận Văn Số.
Đề tài cùng ngành
- Hệ thống EDR thông minh tích hợp học tăng cường và mô hình ngôn ngữ lớn cho phát hiện APT
- Hệ thống kiểm thử xâm nhập tự trị có kiểm soát dựa trên kiến trúc điều khiển nhận thức và phối hợp đa tác tử
- Hệ thống phân tích bảo mật tự động tích hợp vào quy trình CI/CD
- FusionNet: Mô hình lai nhẹ hiệu quả với cơ chế hoán đổi kênh và tự chú ý tách biệt để phát hiện bệnh cây trồng trên thiết bị biên.
- Building a smart document scanner application on mobile
- Phát hiện các bất thường về nhịp tim dựa trên điện tâm đồ.
- Phương pháp local search cho một bài toán giao hàng trong thực tế
- Hệ thống phát hiện xâm nhập dựa trên học tiệm tiến với mô hình học sâu kết hợp giám sát và không giám sát
Tác giả muốn gỡ, sửa thông tin hoặc bổ sung bản toàn văn: gửi yêu cầu qua trang Liên hệ, kèm đường dẫn trang này.