Active Shape Models (ASMs), a knowledge-based segmentation algorithm developed by Cootes and Taylor, have become a standard and popular method for detecting structures in medical images. In ASMs - and various comparable approaches - the model of the object's shape and of its gray-level variations is based the assumption of linear distributions. In this work, we explore a new way to model the gray-level appearance of the objects, using a k-nearest-neighbors (kNN) classifier and a set of selected features for each location and resolution of the Active Shape Model. The construction of the kNN classifier and the se-lection of features from training images is fully automatic. We compare our approach with the standard ASMs on synthetic data and in four medical segmentation tasks. In all cases, the new method produces significantly better results (p < 0.001).