Registration and segmentation of anatomical structures are two well studied problems in medical imaging. Optimizing segmentation and registration jointly has been proven to improve results for both challenges. In this work, we propose a joint optimization scheme for registration and segmentation using dictionary learning based descriptors. Our joint registration and segmentation aims to solve an optimization function, which enables better performance for both of these ill-posed processes. We build two dictionaries for background and myocardium for square patches extracted from training images. Based on dictionary learning residuals and sparse representations defined on these pre-trained dictionaries, a Markov Random Field (MRF) based joint optimization scheme is built. The algorithm proceeds iteratively updating the dictionaries in an online fashion. The accuracy of the proposed method is illustrated on Cardiac Phase-resolved Blood Oxygen-Level-Dependent (CP-BOLD) MRI and standard cine Cardiac MRI data from MICCAI 2013 SATA Segmentation Challenge. The proposed joint segmentation and registration method achieves higher dice accuracy for myocardium segmentation compared to its variants.