To detect curvilinear structures in natural images, we propose a novel rankinglearning system and an abstract curvilinear shape inference algorithm based on graph theory. Weanalyze the curvilinear structures as a set of small line segments. In this work, the rankings ofthe line segments are exploited to systematize the topological feature of the curvilinear structures.Structured Support Vector Machine is employed to learn the ranking function that predicts thecorrespondence of the given line segments and the latent curvilinear structures. We first extractcurvilinear features using morphological profiles and steerable filtering responses. Also, we proposean orientation-aware feature descriptor and a feature grouping operator to improve the structuralintegrity during the learning process. To infer the curvilinear structure, we build a graph based onthe output rankings of the line segments. We progressively reconstruct the curvilinear structureby looking for paths between remote vertices in the graph. Experimental results show that theproposed algorithm faithfully detects the curvilinear structures within various datasets.