We propose a method for line extraction in complex images. We consider a two-stage process. First, the initial measurements at each image point are given by combining the image convolution outputs obtained from directional filters. Second, a postprocessing stage, based on probabilistic relaxation, refines the initial labeling using contextual information. The major differences from other similar approaches are the explicit inclusion of the relative measurements between pixels and the careful modeling of the probability density functions of these measurements.