An image processing apparatus configured to generate a halftone image of an input image by performing quantization using a threshold value matrix, comprising: a holding unit configured to hold a threshold value matrix in which different threshold values are arranged; an allocation means configured to allocate the threshold values of the threshold value matrix to pixels of the input image; a candidate/provider pixel determination unit configured to determine, for each pixel included in the input image, whether that pixel is a candidate pixel having a threshold value allocated thereto which is to be replaced with a new threshold value, or whether that pixel is a provider pixel that can provide the new threshold value to be allocated to the candidate pixel, wherein the candidate/provider pixel determination unit determines that said pixel is a candidate pixel if it has a pixel value greater than a predetermined pixel value, and that said pixel is a provider pixel if it has a pixel value which is equal to or less than the predetermined pixel value; a threshold value determination unit configured to determine, for a determined candidate pixel in a processing area, using a threshold value in the threshold value matrix allocated to one of said provider pixels in the processing area other than the candidate pixel, the new threshold value to be allocated to the candidate pixel, wherein the processing area is an area in the input image that has a predetermined size smaller than a size of the threshold value matrix, wherein the threshold value determination unit is further configured to replace the threshold value in the threshold value matrix allocated to the candidate pixel with the determined new threshold value and to repeat the determination for each of a plurality of further processing areas being areas of the input image having the predetermined size; and a dither processing unit configured to perform the quantization using the threshold value matrix with the new threshold values. a holding unit configured to hold a threshold value matrix in which different threshold values are arranged; an allocation means configured to allocate the threshold values of the threshold value matrix to pixels of the input image; a candidate/provider pixel determination unit configured to determine, for each pixel included in the input image, whether that pixel is a candidate pixel having a threshold value allocated thereto which is to be replaced with a new threshold value, or whether that pixel is a provider pixel that can provide the new threshold value to be allocated to the candidate pixel, wherein the candidate/provider pixel determination unit determines that said pixel is a candidate pixel if it has a pixel value greater than a predetermined pixel value, and that said pixel is a provider pixel if it has a pixel value which is equal to or less than the predetermined pixel value; a threshold value determination unit configured to determine, for a determined candidate pixel in a processing area, using a threshold value in the threshold value matrix allocated to one of said provider pixels in the processing area other than the candidate pixel, the new threshold value to be allocated to the candidate pixel, wherein the processing area is an area in the input image that has a predetermined size smaller than a size of the threshold value matrix, wherein the threshold value determination unit is further configured to replace the threshold value in the threshold value matrix allocated to the candidate pixel with the determined new threshold value and to repeat the determination for each of a plurality of further processing areas being areas of the input image having the predetermined size; and a dither processing unit configured to perform the quantization using the threshold value matrix with the new threshold values.