In this paper, we adopt constrained relaxation for distributed multi-view video coding (DMVC). The novel framework integrates the graph-based segmentation and matching to generate inter-view correlated side information without knowing the camera parameters. Moreover, graph-based representations of multi-view images are incorporated to form more distinctive feature constraints. The sparse data as a good hypothesis space aim for a best matching optimization of inter-view side information with compact syndromes, from inferred relaxed coset. The plausible filling-in from a priori feature constraints between neighboring views could reinforce a promising compensation to inter-view side information generation for joint multi-view decoding. In order to find distinctive feature matching with a more stable approximation, PCA-SIFT and TPS (thin plate spline) are adopted to reduce the dimension of SIFT descriptors and construct a more accurate inter-view motion model. The experimental results validate the high estimation precision and the rate-distortion improvements.