Extracting geometric data of landmarks from fluoroscopic images plays an important role in camera calibration process of a fluoroscopic-image-based surgical navigation system. Connected components labeling is the essential technique for the extraction. A new fast connected components labeling algorithm was presented. The definition of upward concave set was introduced to explain the algorithm. Feasibility and efficiency of the algorithm were verified with experiments. This algorithm performs well in labeling non-upward concave set connected components and applies to landmarks labeling well. Moreover, the proposed algorithm possesses a desirable characteristic that will facilitate the subsequent processing of fluoroscopic images.