Retinal pigment epithelium (RPE) defects are indicated in many blinding diseases, but have been difficult to image. Recently, adaptive optics enhanced indocyanine green (AO-ICG) imaging has enabled direct visualization of the RPE mosaic in the living human eye. However, tracking the RPE across longitudinal images on the time scale of months presents with unique challenges, such as visit-to-visit distortion and changes in image quality. We introduce a coarse-to-fine search strategy that identifies paired patterns and measures their changes. First, longitudinal AO-ICG image displacements are estimated through graph matching of affine invariant maximal stable extremal regions in affine Gaussian scale-space. This initial step provides an automatic means to designate the search ranges for finding corresponding patterns. Next, AO-ICG images are decomposed into superpixels, simplified to a pictorial structure, and then matched across visits using tree-based belief propagation. Results from human subjects in comparison with a validation dataset revealed acceptable accuracy levels for the level of changes that are expected in clinical data. Application of the proposed framework to images from a diseased eye demonstrates the potential clinical utility of this method for longitudinal tracking of the heterogeneous RPE pattern.