Anatomical structure labeling in echocardiogram images will assist cardiac disease diagnosis by providing a framework for doing geometrical statistics. General labeling algorithms often focus on stationary body structures and do not peiform well in echocardiography due to cardiac motion, low signal to noise ratio, and structural deformation caused by diseases. In this paper, we propose a new method for anatomical structure labeling in echocardiography that adopts the structure layout consistency, and works on mid-level primitives (segments). Specifically, the proposed method defines a constellation model, and based on which, a model score function is designed to measure the consistency between a testing candidate configuration and the constellation model. The parameters of the score function are learned through a discriminative training framework. Given a test image and its corresponding multi-level segmentation, we use an MCMC-based algorithm to infer the configuration which best fits the constellation model. We evaluate the proposed method on 50 images. The qualitative and quantitative results demonstrate the effectiveness of the proposed method.