In this paper, feature point matching is formulated as an optimization problem in which the uniqueness condition is constrained. We propose a novel score function based on homography-induced pairwise constraints, and a novel optimization algorithm based on relaxation labeling. Homography-induced pairwise constraints are effective for image pairs with viewpoint or scale changes, unlike previous pairwise constraints. The proposed optimization algorithm searches for a uniqueness-constrained solution, while the original relaxation-labeling algorithm is appropriate for finding many-to-one correspondences. The effectiveness of the proposed method is shown by experiments involving image pairs with viewpoint or scale changes in addition to repeated textures and nonrigid deformation. The proposed method is also applied to object recognition, giving some promising results.