Combining convex hull and directed graph for fast and accurate ellipse detection

doi:10.1016/j.gmod.2021.101110

	Combining convex hull and directed graph for fast and accurate ellipse detection
	Shen, Zeyu 3,4,5; Zhao, Mingyang 2; Jia, Xiaohong 2; Liang, Yuan 1; Fan, Lubin 1; Yan, Dong-Ming 3,4,5
刊名	GRAPHICAL MODELS
	2021-07-01
卷号	116 页码:13
关键词	Ellipse detection Edge following Hough transform RANSAC
ISSN号	1524-0703
DOI	10.1016/j.gmod.2021.101110
英文摘要	Detecting ellipses from images is a fundamental task in many computer vision applications. However, due to the complexity of real-world scenarios, it is still a challenge to detect ellipses accurately and efficiently. In this paper, we propose a novel method to tackle this problem based on the fast computation of convex hull and directed graph, which achieves promising results on both accuracy and efficiency. We use Depth-First-Search to extract branchfree curves after adaptive edge detection. Line segments are used to represent the curvature characteristic of the curves, followed by splitting at sharp corners and inflection points to attain smooth arcs. Then the convex hull is constructed, together with the distance, length, and direction constraints, to find co-elliptic arc pairs. Arcs and their connectivity are encoded into a sparse directed graph, and then ellipses are generated via a fast access of the adjacency list. Finally, salient ellipses are selected subject to strict verification and weighted clustering. Extensive experiments are conducted on eight real-world datasets (six publicly available and two built by ourselves), as well as five synthetic datasets. Our method achieves the overall highest F-measure with competitive speed compared to representative state-of-the-art methods.
资助项目	National Natural Science Foundation of China[12022117] ; National Natural Science Foundation of China[61772523] ; National Natural Science Foundation of China[61802406] ; Beijing Natural Science Foundation[Z190004] ; Beijing Advanced Discipline Fund[115200S001] ; Open Research Fund Program of State key Laboratory of Hydroscience and Engineering, Tsinghua University[sklhse-2020-D-07] ; Alibaba Group through Alibaba Innovative Research Program
WOS研究方向	Computer Science
语种	英语
出版者	ACADEMIC PRESS INC ELSEVIER SCIENCE
WOS记录号	WOS:000672837300001
内容类型	期刊论文
源URL	[http://ir.amss.ac.cn/handle/2S8OKBNM/58914]
专题	中国科学院数学与系统科学研究院
通讯作者	Yan, Dong-Ming
作者单位	1.Alibaba Grp, Hangzhou 311121, Peoples R China 2.Chinese Acad Sci, Acad Math & Syst Sci, NCMIS, KLMM, Beijing 100190, Peoples R China 3.Tsinghua Univ, State Key Lab Hydrosci & Engn, Beijing 100084, Peoples R China 4.Univ Chinese Acad Sci, Sch Artificial Intelligence, Beijing 100149, Peoples R China 5.Chinese Acad Sci, Inst Automat, Natl Lab Pattern Recognit, Beijing 100190, Peoples R China
推荐引用方式 GB/T 7714	Shen, Zeyu,Zhao, Mingyang,Jia, Xiaohong,et al. Combining convex hull and directed graph for fast and accurate ellipse detection[J]. GRAPHICAL MODELS,2021,116:13.
APA	Shen, Zeyu,Zhao, Mingyang,Jia, Xiaohong,Liang, Yuan,Fan, Lubin,&Yan, Dong-Ming.(2021).Combining convex hull and directed graph for fast and accurate ellipse detection.GRAPHICAL MODELS,116,13.
MLA	Shen, Zeyu,et al."Combining convex hull and directed graph for fast and accurate ellipse detection".GRAPHICAL MODELS 116(2021):13.