LuanVan.vnLuận Văn
Gửi thư

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ệuLuận án
Bậc họcTiến sĩ
NgànhCô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ăm2006
NguồnThư 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

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.