A threshold matrix generation method of generating a threshold matrix to be compared with an original image of multi-gradation in performing halftoning of said original image in an image recording apparatus which is capable of recording an image at single speed and at N-fold speed where N is an integer not less than 2, comprising the step of: a) preparing a matrix space which is a set of matrix elements arranged both in a column direction which corresponds to a recording direction in said image recording apparatus and in a row direction perpendicular to said column direction, and characterized by the steps of: b) setting writing elements which are matrix elements corresponding to writing positions on a recording object so that one writing element is positioned at intervals of (N-1) matrix elements in said column direction and one writing element is positioned at intervals of (N-1) matrix elements or two writing elements are positioned at intervals of (2N-2) matrix elements in said row direction and setting the other matrix elements as non-writing elements in said operation a) or after said operation a); c) giving the first turn-on number to one writing element, being thereafter changed to a determined element, and then repeating a process of specifying a writing element which is farthest away from all determined elements and giving a next turn-on number to said writing element, being thereafter changed to a determined element, in consideration of repetitive application of said threshold matrix in performing halftoning of an original image, to thereby allocate turn-on numbers to all writing elements (S33 to S35); d) obtaining a threshold matrix for N-fold speed by determining a threshold value of each writing element in accordance with said turn-on number; and e) shrinking said threshold matrix for N-fold speed in said row direction by omitting said non-writing elements. a) preparing a matrix space which is a set of matrix elements arranged both in a column direction which corresponds to a recording direction in said image recording apparatus and in a row direction perpendicular to said column direction, and characterized by the steps of: b) setting writing elements which are matrix elements corresponding to writing positions on a recording object so that one writing element is positioned at intervals of (N-1) matrix elements in said column direction and one writing element is positioned at intervals of (N-1) matrix elements or two writing elements are positioned at intervals of (2N-2) matrix elements in said row direction and setting the other matrix elements as non-writing elements in said operation a) or after said operation a); c) giving the first turn-on number to one writing element, being thereafter changed to a determined element, and then repeating a process of specifying a writing element which is farthest away from all determined elements and giving a next turn-on number to said writing element, being thereafter changed to a determined element, in consideration of repetitive application of said threshold matrix in performing halftoning of an original image, to thereby allocate turn-on numbers to all writing elements (S33 to S35); d) obtaining a threshold matrix for N-fold speed by determining a threshold value of each writing element in accordance with said turn-on number; and e) shrinking said threshold matrix for N-fold speed in said row direction by omitting said non-writing elements.