In this paper, we build on the RANSAC method to detect multiple instances of objects in an image, where the objects are modeled as curvilinear segments with distinct endpoints. Our approach differs from previously presented work in that it incorporates soft constraints, based on a dense image representation, that guide the estimation process in every step. This enables (1) better correspondence with image content, (2) explicit endpoint detection and (3) a reduction in the number of iterations required for accurate estimation. In the case of curvilinear objects examined in this paper, these constraints are formulated as binary image labels, where the estimation proved to be robust to mislabeling, e.g. in case of intersections. Results for both synthetic and real data from medical X-ray images show the improvement from incorporating soft image-based constraints.