How to optimize a palette-based image recoloring algorithm

Question

I've a scenario, where I generate a color palette against a specific image. Then I want to click on any of the palette colors n and select a new color to be put on all the pixels with the previous color code. I'm done, and it's working, but I need your help on optimizing its results and time. The code to generate the palette using color thief is:

function make_pallete(){
    var images = document.getElementById('default_img');
    colors = colorThief.getPalette(images, 8);
    for (var i = 0 ; i < colors.length; i++) {
        $('#swatches').append("<div class='swatch' style='background-color:rgb("+       colors[i][0]+ ","+ colors[i][1] + "," + colors[i][2] +")'></div>");
    }
}

And the Django view, where I'm performing recoloring is:

def recolor_image(request):
    if request.method == "POST":
        pic = request.POST.get("image")
        old_rgb = request.POST.getlist("old_rgb[]")
        new_rgb = request.POST.getlist("new_rgb[]")
        path = "D:/pysofts/flagcarpets" + pic
        pic  = path
        picture = Image.open(pic)
        # Get the size of the image
        width,height = picture.size
        print old_rgb
        for x in range(0, width):
            for y in  range(0, height):
                current_color = picture.getpixel((x,y))
                r,g,b = current_color
                if r in range(int(old_rgb[0]) - 50, int(old_rgb[0]) + 50) and g in     range(int(old_rgb[1]) - 50, int(old_rgb[1]) + 50) and b in range(int(old_rgb[2]) - 50, int(old_rgb[2]) + 50):
                    r = int(new_rgb[0])
                    g = int(new_rgb[1])
                    b = int(new_rgb[2])
               new_color = (r,g,b)
               picture.putpixel((x,y), new_color)
        picture.save(path)
        return HttpResponse(pic)

As I said, it's recoloring the image, but the efficiency is poor (it doesn't put new color to every previous pixel) n it takes about 30 seconds to recolor the image. What would a more precise algorithm be?

Answer 1

What is the image resolution and colors?

Pixel based recoloring of images around 1024x768 should take just few [ms].
If you have low color count like up to 256 you can use palette based images like GIF,BMP,PCX to change only the palette instead pixels for speed.
If you want real speed, use C/C++

The problem:

The first thing I see is GDI getpixel access, which is SLOW. (see bitmap ScanLine property). So, create array of pointers to lines of your image and use that (call ScanLine only once per line then use the array) This will avoid GDI checking slow downs.

Each getpixel/ScanLine call invokes around 100 sub calls to check the type, format, resolution whatever.
If you access own array of pointers then you just access memory without any additional slowdowns (usually around 1000x faster then getpixel).
Find a ScanLine[] equivalent in your platform and rewrite. Here is an example in VCL/C++ so you know what to look for and how to use it.
It should be almost the same as this is GDI interface.

If you want to use indexed colors (Palette)

You can visualize with OpenGL and Indexed colors. This way you change only the palette and opengl recolors the rest on its own.
This process is good for speed while editing, it recolors only while saving.

Another option is to use 256 color palette image fileformats (GIF,BMP,PCX).
For that you have to limit the colors to 256.
You can use any method. Here's mine: Effective gif/image color quantization, but this will change the color dynamic range see the images there.

Recoloring

If you have your color palette sorted then you can use binary search to speed up the process.
With too many colors a good idea is to use dictionaries.
For example, create lists: List<DWORD> r0[256],g0[256],b0[256];. Each holding all colors starting with r,g,or b value.
For example, r0[55] will hold all used colors with red=55.
This way you can search in O(n^2) instead of O(n^3) not counting binary search.
See the above GIF link how I recolor for additional ideas.