It very much depends upon which image format, and which of the various subformats the image is in. Many images are stored in a "palettized format", meaning that there is a lookup table (palette) in the image file that maps the numbers stored in the data portion of the file to the actual colors used when the image is displayed. With this type of image, changing an individual colour is as simple as replacing it's entry in the palette with the new colour.

If the image is stored as "true colour"--ie. 24-bits per perl format--then there is very little option but to scan the entire data portion of the image file and replace the old colour with the new.

However, depending upon the image format you wish to process, this needn't be a particularly slow process. With knowledge of the format of the file and a little care, it is possible to do this a regex-style search and replace process, treating the appropriate portion of the image as a big string, thereby avoiding the overhead of (multiple) function/method calls per pixel.

Which image format(s) do you need to process?