Image recognition device that combines first part candidates and second part candidates to generate a plurality of pairs; that calculates first estimate value for each of the plurality of pairs, this value indicating estimated possibility that these candidates are connected; that executes, for each of the plurality of pairs, correcting first estimate value by using second estimate value as a weight in a state in which a part candidate that is one among a pair of part candidates matching of which has already been performed and that differs from both first part candidate and second part candidate is connected to either first part candidate or second part candidate, second estimate value indicating estimated possibility that the pair of part candidates matching of which has already been performed are connected; and that performs matching of first part candidates and second part candidates using corrected first estimate values.