Motion estimation for applications where appearance undergoes complex changes is challenging due to lack of an appropriate similarity function. In this paper, we propose to learn a discriminative similarity function based on an annotated database that exemplifies the appearance variations. We invoke the LogitBoost algorithm to selectively combine weak learners into one strong similarity function. The weak learners based on local rectangle features are constructed as nonparametric 2D piecewise constant functions, using the feature responses from both images, to strengthen the modeling power and accommodate fast evaluation. Because the negatives possess a location parameter measuring their closeness to the positives, we present a locationsensitive cascade training procedure, which bootstraps negatives for later stages of the cascade from the regions closer to the positives. This allows viewing a large number of negatives and steering the training process to yield lower training and test errors. In experiments of estimating the motion for the endocardial wall of the left ventricle in echocardiography, we compare the learned similarity function with conventional ones and obtain improved performances. We also contrast the proposed method with a learning-based detection algorithm to demonstrate the importance of temporal information in motion estimation. Finally, we insert the learned similarity function into a simple contour tracking algorithm and find that it reduces drifting.