A systematic and efficient curvilinear feature extraction algorithm using minimum spanning trees is developed. The algorithm is closely related to human perception through the Gestalt clustering properties of minimum spanning trees [1,2]. After curvilinear features are extracted, they are approximated, using KarhunenLoeve transform and then they are edited based on heuristics. The resulting line segments are the compact representation of the input image. Then this representation of the image can be directly applicable to the recognition of objects and scene matching. Results with real world images are presented to demonstrate the capabilities and applicabilities of the algorithm.