Please use this identifier to cite or link to this item:
http://hdl.handle.net/10397/231
| Title: | An efficient recursive shortest spanning tree algorithm using linking properties | Authors: | Kwok, SH Constantinides, AG Siu, WC |
Issue Date: | Jun-2004 | Source: | IEEE transactions on circuits and systems for video technology, June 2004, v. 14, no. 6, p. 852-863 | Abstract: | Speed is a great concern in the recursive shortest spanning tree (RSST) algorithm as its applications are focused on image segmentation and video coding, in which a large amount of data is processed. Several efficient RSST algorithms have been proposed in the literature, but the linking properties are not properly addressed and used in these algorithms and they are intended to produce a truncated RSST. This paper categorizes the linking process into three classes based on link weights. These linking processes are defined as the linking process for link weight equal to zero (LPLW-Z), the linking process for link weight equal to one (LPLW-O), and the linking process for link weight equal to real number (LPLW-R). We study these linking properties and apply them to an efficient RSST algorithm. The proposed efficient RSST algorithm is novel, as it makes use of linking properties, and its resulting shortest spanning tree is truly identical to that produced by the conventional algorithm. Our experimental results show that the percentages of links for the three classes are 17%, 27%, and 58%, respectively. This paper proposes a prediction method for LPLW-O, as a result of which the vertex weight of the next region can be determined by comparing sizes of the merging regions. It is also demonstrated that the proposed LPLW-O with prediction approach is applicable to the multiple-stage merging. Our experimental results show that the proposed algorithm has a substantial improvement over the conventional RSST algorithm. | Keywords: | Edge detection Graph theory Image segmentation Linking property Recursive shortest spanning tree (RSST) |
Publisher: | Institute of Electrical and Electronics Engineers | Journal: | IEEE transactions on circuits and systems for video technology | ISSN: | 1051-8215 | EISSN: | 1558-2205 | DOI: | 10.1109/TCSVT.2004.828334 | Rights: | © 2004 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE. This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder. |
| Appears in Collections: | Journal/Magazine Article |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| algorithm_04.pdf | 688.29 kB | Adobe PDF | View/Open |
Access
View full-text via PolyU eLinks 
Page views
104
Last Week
1
1
Last month
Citations as of May 28, 2023
Downloads
143
Citations as of May 28, 2023
SCOPUSTM
Citations
13
Last Week
0
0
Last month
0
0
Citations as of Jun 2, 2023
WEB OF SCIENCETM
Citations
6
Last Week
0
0
Last month
0
0
Citations as of Jun 1, 2023
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.