Template matching is used in many practical applications for tracking the movement of clouds. To accommodate their non-rigid nature, additional constraints are often applied to produce cloud motion vectors that are more indicative of the underlying flow. One such approach is correlation-relaxation labelling, which uses a relaxation algorithm to refine sets of velocity vectors produced by template matching. The quality of the final result depends on the initial motion vectors and hence the choice of similarity metric at the template matching stage. Ordinal measures (OM) are a new class of matching functions that are sensitive to image noise. The use of OM for cloud tracking is evaluated both independently and as the first stage of a correlation-relaxation labelling scheme. Experimental results for noise-corrupted sequences show that the direct application of OM does not produce meaningful results. However, within a correlation-relaxation framework, OM produce a more consistent motion field than the widely used cross-correlation coefficient. The increase in accuracy was found to be greater for sequences corrupted by impulsive noise than for Gaussian noise.