The invention relates to a labeling apparatus (1) for labeling structures of an object shown in an object image. A probability map providing unit (3) provides a probability map, the probability map indicating for different labels, which are indicative of different structures of the object, and for different positions in the probability map the probability that the respective structure, which is indicated by the respective label, is present at the respective position, wherein the probability depends on the position in the probability map. The probability map is mapped to the object image by a mapping unit (4), wherein a label assigning unit (5) assigns to a provided contour, which represents a structure in the object image, a label based on the mapped probability map. This allows automatically labeling structures of the object, which are indicated by provided contours in the object image, with relatively low computational efforts.