An image processing apparatus includes an attribute information generation unit configured to generate attribute information about each pixel of input image data, a division unit configured to divide the input image data into a plurality of blocks of a predetermined size, a generation unit configured to generate a histogram of a color and a pixel existing in a focused block divided by the division unit, a color replacement unit configured to execute color replacement processing on each area defined by the histogram generated by the generation unit, a gradation presence determination unit configured to determine whether gradation exists, and a block integration unit configured, if it is determined that gradation exists, to integrate a focused area and an adjacent area to generate continuous gradation in the focused area and the adjacent area.