检索结果-内蒙古大学图书馆

A RUN-BASED ONE-AND-A-HALF-SCAN CONNECTED-COMPONENT labeling algorithm

INTERNATIONAL JOURNAL OF PATTERN RECOGNITION AND ARTIFICIAL INTELLIGENCE 2010年第4期24卷 557-579页

作者： He, Lifeng Chao, Yuyan Suzuki, Kenji Shaanxi Univ Sci & Technol Taiyuan Shaanxi Peoples R China Aichi Prefectural Univ Nagakute Aichi 4801198 Japan Nagoya Sangyo Univ Grad Sch Environm Management Aichi 4888711 Japan Univ Chicago Dept Radiol Chicago IL 60637 USA

This paper presents a run-and label-equivalence-based one-and-a-half-scan algorithm for labeling connected components in a binary image. Major differences between our algorithm and conventional label-equivalence-based algorithms are: (1) all conventional label-equivalence-based algorithms scan all pixels in the given image at least twice, whereas our algorithm scans background pixels once and object pixels twice;(2) all conventional label-equivalence-based algorithms assign a provisional label to each object pixel in the first scan and relabel the pixel in the later scan(s), whereas our algorithm assigns a provisional label to each run in the first scan, and after resolving label equivalences between runs, by using the recorded run data, it assigns each object pixel a final label directly. That is, in our algorithm, relabeling of object pixels is not necessary any more. Experimental results demonstrated that our algorithm is highly efficient on images with many long runs and/or a small number of object pixels. Moreover, our algorithm is directly applicable to run-length-encoded images, and we can obtain contours of connected components efficiently.

关键词： labeling algorithm connected component label equivalence run-length encoding raster scan

来源：评论

学校读者我要写书评

暂无评论

A Bucket Graph-Based labeling algorithm with Application to Vehicle Routing

引用

TRANSPORTATION SCIENCE 2021年第1期55卷 4-28页

作者： Sadykov, Ruslan Uchoa, Eduardo Pessoa, Artur INRIA Bordeaux Sud Ouest F-33405 Talence France Univ Bordeaux Inst Math F-3340 Talence France Univ Fed Fluminense Engn Prod BR-24210240 Niteroi RJ Brazil

We consider the shortest path problem with resource constraints arising as a subproblem in state-of-the-art branch-cut-and-price algorithms for vehicle routing problems. We propose a variant of the bidirectional label-correcting algorithm in which the labels are stored and extended according to the so-called bucket graph. This organization of labels helps to significantly decrease the number of dominance checks and the running time of the algorithm. We also show how the forward/backward route symmetry can be exploited and how to eliminate arcs from the bucket graph using reduced costs. The proposed algorithm can be especially beneficial for vehicle routing instances with large vehicle capacity and/or with time window constraints. Computational experiments were performed on instances from the distance-constrained vehicle routing problem, including multidepot and site-dependent variants, on the vehicle routing problem with time windows, and on the "nightmare" instances of the heterogeneous fleet vehicle routing problem. Significant improvements over the best algorithms in the literature were achieved, and many instances could be solved for the first time.

关键词： labeling algorithm shortest path with resource constraints routing

来源：评论

学校读者我要写书评

暂无评论

A run-based two-scan labeling algorithm

引用

IEEE TRANSACTIONS ON IMAGE PROCESSING 2008年第5期17卷 749-756页

作者： He, Lifeng Chao, Yuyan Suzuki, Kenji Aichi Prefectural Univ Grad Sch Informat Sci & Technol Aichi 4801198 Japan Nagoya Sangyo Univ Grad Sch Environm Management Aichi 4888711 Japan Univ Chicago Dept Radiol Div Biol Sci Chicago IL 60637 USA

We present an efficient run-based two-scan algorithm for labeling connected components in a binary image. Unlike conventional label-equivalence-based algorithms, which resolve label equivalences between provisional labels, our algorithm resolves label equivalences between provisional label sets. At any time, all provisional labels that are assigned to a connected component are combined in a set, and the smallest label is used as the representative label. The corresponding relation of a provisional label and its representative label is recorded in a table. Whenever different connected components are found to be connected, all provisional label sets concerned with these connected components are merged together, and the smallest provisional label is taken as the representative label. When the first scan is finished, all provisional labels that were assigned to each connected component in the given image will have a unique representative label. During the second scan, we need only to replace each provisional label by its representative label. Experimental results on various types of images demonstrate that our algorithm outperforms all conventional labeling algorithms.

关键词： connected components labeling algorithm linear-time algorithm pattern recognition run-length encoding

来源：评论

学校读者我要写书评

暂无评论

Development of the tree-based link labeling algorithm for optimal path-finding in urban transportation networks

引用

MATHEMATICAL AND COMPUTER MODELLING 1998年第9-11期27卷 51-65页

作者： Namkoong, S Rho, JH Choi, JU Korea Highway Corp Transportat Res Ctr Transportat Engn Div Sujeong Gu Kyeongki Do 461380 South Korea

The optimal path-finding algorithm which is an important module in developing route guidance systems and traffic control systems has to provide correct paths to consider U-turns, P-turns, and no-left-turns in urban transportation networks. Traditional methods which have been used to consider those regulations on urban transportation networks can be categorized into network representation and algorithmic methods like the vine-building algorithm. First, network representation methods use traditional optimal path-finding algorithms with modifications to the network structure: for example, just adding dummy nodes and links to the existing network allows constraint-search in the network. This method which creates large networks is hard to implement and introduces considerable difficulties in network coding. With the increased number of nodes and links, the memory requirement tremendously increases, which causes the processing speed to slow down. For these reasons, the method has not been widely accepted for incorporating turning regulations in optimal path-finding problems in transportation networks. Second, algorithmic methods, as they are mainly based on the vine-building algorithm, have been suggested for determining optimal path for networks with turn penalties and prohibitions. However, the algorithms, although they nicely reflect the characteristics of urban transportation networks, frequently provide infeasible or suboptimal solutions. The algorithm to be suggested in this research is a method which is basically based on Dijkstra's algorithm [1] and the tree-building algorithm used to construct optimal paths. Unlike the traditional node labeling algorithms which label each node with minimum estimated cost, this algorithm labels each link with minimum estimated cost. Comparison with the vine-building algorithm shows that the solution of the link-labeling algorithm is better than that of the vine-building algorithm which very frequently provides suboptimal solutions

关键词： shortest path finding turning regulation tree building vine building labeling algorithm

来源：评论

学校读者我要写书评

暂无评论

A labeling algorithm for the sensitivity ranges of the assignment problem

引用

APPLIED MATHEMATICAL MODELLING 2011年第10期35卷 4852-4864页

作者： Lin, Chi-Jen Ta Hwa Inst Technol Dept Ind Engn & Management Hsinchu Taiwan

In view of the simplex-type algorithm, the assignment problem is inherently highly degenerate. It may be the optimal basis has changed, but the optimal assignment is unchanged when parameter variation occurs. Degeneracy then makes sensitivity analysis difficult, as well as makes the classical Type I range, which identifies the range the optimal basis unchanged, impractical. In this paper, a labeling algorithm is proposed to identify two other sensitivity ranges - Type II range and Type III range. The algorithm uses the reduced cost matrix, provided in the final results of most solution algorithms for AP, to determine the Type II range which reflects the stability of the current optimal assignment. Thus, the algorithm generates a streamlined situation from searching the optimal solution until performing the sensitivity analysis of the assignment problem. The Type III range, reflecting the flexibility of optimal decision making, can be obtained immediately after the Type II range is determined. Numerical examples are presented to demonstrate the algorithm. (C) 2011 Elsevier Inc. All rights reserved.

关键词： Assignment problem Sensitivity analysis Degeneracy labeling algorithm

来源：评论

学校读者我要写书评

暂无评论

labeling algorithm and its fairness analysis for autonomous system

引用

Journal of Systems Engineering and Electronics 2005年第4期16卷 806-810页

作者： Han Guodong Wang Hui Wu Jiangxing National Digital Switching System Engineering & Technological Research Center Information Engineering Univ. Zhengzhou 450002 P. R. China Managment Coll. Tianjin Univ. Tianjin 300072 P. R. China

A kind of packet labeling algorithm for autonomous system is introduced. The fairness of the algorithm for each traffic stream in the integrated-services is analyzed. It is shown that the rate of each stream in the integrated-services would converge to a stable value if the transmittfing or forwarding rates converge to that of the receiving exponentially.

关键词： autonomous system labeling algorithm traffic stream fairness analysis.

来源：评论

学校读者我要写书评

暂无评论

A fast connected components labeling algorithm for binary images

引用

Journal of Harbin Institute of Technology(New Series) 2012年第3期19卷 81-87页

作者：付宜利韩现伟王树国 State Key Laboratory of Robotics and System Harbin Institute of Technology

A fast label-equivalence-based connected components labeling algorithm is proposed in this *** is a combination of two existing efficient methods,which are pivotal operations in two-pass connected components labeling *** is a fast pixel scan method,and the other is an array-based Union-Find data *** scan procedure assigns each foreground pixel a provisional label according to the location of the *** is to say,it labels the foreground pixels following background pixels and foreground pixels in different ways,which greatly reduces the number of neighbor pixel *** array-based Union-Find data structure resolves the label equivalences between provisional labels by using only a single array with path compression,and it improves the efficiency of the resolving procedure which is very time-consuming in general label-equivalence-based *** experiments on various types of images with different sizes show that the proposed algorithm is superior to other labeling approaches for huge images containing many big connected components.

关键词： binary image connected components labeling algorithm Union-Find label-equivalence

来源：评论

学校读者我要写书评

暂无评论

An Efficient Connected-Component labeling algorithm for 3-D Binary Images

IEEE OPEN JOURNAL OF THE COMPUTER SOCIETY

引用

IEEE OPEN JOURNAL OF THE COMPUTER SOCIETY 2023年第1期4卷 1-12页

作者： Zhao, Xiao Chao, Yuyan Zhang, Hui Yao, Bin He, Lifeng Shaanxi Univ Sci & Technol Artificial Intelligence Inst Sch Elect Informat & Artificial Intelligence Xian 710021 Peoples R China Nagoya Sangyo Univ Grad Sch Environm Management Owariasa Shi 4888711 Japan Aichi Prefectural Univ Grad Sch Informat Sci & Technol Nagakute 4801198 Japan

Conventional voxel-based algorithms for labeling connected components in 3D binary images use the same mask to process all object voxels. To reduce the number of times that neighboring voxels are checked when object voxels are processed, we propose an algorithm that uses two different masks for processing two different types of object voxels. One type of mask is used when the voxel preceding the object voxel being processed is an object voxel, and the other type is used otherwise. In either case, an optimal order is used for checking the voxels in the corresponding mask. Experimental results demonstrate that our proposed algorithm checked fewer voxels, and was more efficient than conventional algorithms.

关键词： Three-dimensional displays labeling Image resolution Medical services Medical diagnostic imaging Artificial intelligence Transforms Computer vision connected component labeling algorithm 3D binary image

来源：评论

学校读者我要写书评

暂无评论

Block-Based Connected-Component labeling algorithm Using Binary Decision Trees

引用

SENSORS 2015年第9期15卷 23763-23787页

作者： Chang, Wan-Yu Chiu, Chung-Cheng Yang, Jia-Horng Natl Def Univ Chung Cheng Inst Technol Dept Elect & Elect Engn Taoyuan 33551 Taoyuan County Taiwan

In this paper, we propose a fast labeling algorithm based on block-based concepts. Because the number of memory access points directly affects the time consumption of the labeling algorithms, the aim of the proposed algorithm is to minimize neighborhood operations. Our algorithm utilizes a block-based view and correlates a raster scan to select the necessary pixels generated by a block-based scan mask. We analyze the advantages of a sequential raster scan for the block-based scan mask, and integrate the block-connected relationships using two different procedures with binary decision trees to reduce unnecessary memory access. This greatly simplifies the pixel locations of the block-based scan mask. Furthermore, our algorithm significantly reduces the number of leaf nodes and depth levels required in the binary decision tree. We analyze the labeling performance of the proposed algorithm alongside that of other labeling algorithms using high-resolution images and foreground images. The experimental results from synthetic and real image datasets demonstrate that the proposed algorithm is faster than other methods.

关键词： connected components labeling algorithm decision tree scan mask

来源：评论

学校读者我要写书评

暂无评论

Efficient scan mask techniques for connected components labeling algorithm

引用

EURASIP JOURNAL ON IMAGE AND VIDEO PROCESSING 2011年第1期2011卷 1-20页

作者： Sutheebanjard, Phaisarn Premchaiswadi, Wichian Siam Univ Grad Sch Informat Technol Bangkok 10160 Thailand

Block-based connected components labeling is by far the fastest algorithm to label the connected components in 2D binary images, especially when the image size is quite large. This algorithm produces a decision tree that contains 211 leaf nodes with 14 levels for the depth of a tree and an average depth of 1.5923. This article attempts to provide a faster method for connected components labeling. We propose two new scan masks for connected components labeling, namely, the pixel-based scan mask and the block-based scan mask. In the final stage, the block-based scan mask is transformed to a near-optimal decision tree. We conducted comparative experiments using different sources of images for examining the performance of the proposed method against the existing methods. We also performed an average tree depth analysis and tree balance analysis to consolidate the performance improvement over the existing methods. Most significantly, the proposed method produces a decision tree containing 86 leaf nodes with 12 levels for the depth of a tree and an average depth of 1.4593, resulting in faster execution time, especially when the foreground density is equal to or greater than the background density of the images.

关键词： connected components image processing labeling algorithm linear time algorithm pattern recognition

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：