A threshold matrix generation method of generating a threshold matrix that is compared with a multi-tone original image when halftoning said original image, the method comprising the steps of: a) obtaining an evaluation value element for a given undetermined matrix element in a matrix area based on a positional relationship between each determined matrix element and said undetermined matrix element while taking into consideration repetitive application of a threshold matrix when halftoning an original image, said undetermined matrix element being a matrix element whose position in a turn-on order has not been determined, said turn-on order indicating an order in which dots are added with increasing tone level, said matrix area being an area where said threshold matrix is generated and in which a plurality of matrix elements are arranged in a row direction and a column direction, said determined matrix element being a matrix element whose position in said turn-on order has been determined; b) adding up an evaluation value element regarding said each determined matrix element so as to obtain an evaluation value for said undetermined matrix element; c) performing said steps a) and b) for all undetermined matrix elements; d) determining, in said turn-on order, a position of an undetermined matrix element that is most highly evaluated based on the evaluation value among said all undetermined matrix elements; e) repeating said steps a) through d) until positions of said all undetermined matrix elements in said turn-on order are determined; and f) determining a threshold value of each matrix element in said matrix area in accordance with said turn-on order, wherein, at least in a case where a ratio of the number of determined matrix elements to the number of said plurality of matrix elements is within a predetermined range, said step a) includes the steps of: a1) obtaining said evaluation value element based on a distance in said row direction between said undetermined matrix element and said each determined matrix element and a distance in said column direction between said undetermined matrix element and said each determined matrix element; and a2) if said positional relationship between said each determined matrix element and said undetermined matrix element is a predetermined specific positional relationship, correcting said evaluation value element regarding said each determined matrix element such that said undetermined matrix element is less evaluated based on said evaluation value, and if said positional relationship is not said specific positional relationship, correcting said evaluation value element regarding said each determined matrix element such that said undetermined matrix element is more highly evaluated based on said evaluation value, said specific positional relationship being a relationship in which said each determined matrix element is located in the same position as said undetermined matrix element with respect to said row direction or said column direction, characterized in that said specific positional relationship further includes a condition that a distance between said each determined matrix element and said undetermined matrix element is two times a pitch of said matrix elements. a) obtaining an evaluation value element for a given undetermined matrix element in a matrix area based on a positional relationship between each determined matrix element and said undetermined matrix element while taking into consideration repetitive application of a threshold matrix when halftoning an original image, said undetermined matrix element being a matrix element whose position in a turn-on order has not been determined, said turn-on order indicating an order in which dots are added with increasing tone level, said matrix area being an area where said threshold matrix is generated and in which a plurality of matrix elements are arranged in a row direction and a column direction, said determined matrix element being a matrix element whose position in said turn-on order has been determined; b) adding up an evaluation value element regarding said each determined matrix element so as to obtain an evaluation value for said undetermined matrix element; c) performing said steps a) and b) for all undetermined matrix elements; d) determining, in said turn-on order, a position of an undetermined matrix element that is most highly evaluated based on the evaluation value among said all undetermined matrix elements; e) repeating said steps a) through d) until positions of said all undetermined matrix elements in said turn-on order are determined; and f) determining a threshold value of each matrix element in said matrix area in accordance with said turn-on order, a1) obtaining said evaluation value element based on a distance in said row direction between said undetermined matrix element and said each determined matrix element and a distance in said column direction between said undetermined matrix element and said each determined matrix element; and a2) if said positional relationship between said each determined matrix element and said undetermined matrix element is a predetermined specific positional relationship, correcting said evaluation value element regarding said each determined matrix element such that said undetermined matrix element is less evaluated based on said evaluation value, and if said positional relationship is not said specific positional relationship, correcting said evaluation value element regarding said each determined matrix element such that said undetermined matrix element is more highly evaluated based on said evaluation value,