Find-replace on canvas

I have an image with flags on it like the one with a pie chart here .

How can I find a particular flag on it and replace with another flag using canvas?

Edit: I cannot control the source image, but the region to find is always known and the image to replace is always the same size as the one to find. I jus开发者_如何学Got need to replace one particular flag with another particular flag.

Edit 2: The flag may appear in the image several times.

You won't see spectacular performance, but one way to approach this is by just iterating over the pixels in your pie chart image.

Call getImageData() on your pie chart image to acquire all the pixel data for the image (ie. request the maximum dimensions). Similarly, call getImageData() on the flag you want to search for. Setup a loop that iterates over all the pixels acquired from the pie chart. For each pixel, assume it is the top left (or another corner based on your iteration order) of the flag you are searching for. Compare it to the first pixel in your flag pixel data, and if they agree, continue iterating within a window size equal to the width and height of your flag. If you get to the end of the window iteration and each pixel pair matches, you've found the flag you're looking for. If they don't, move on to the next pixel in the pie chart data and iterate over the window again.

Note that in the worst case you're looking at O([N * W * H] - [W * H]) or just O(N * W * H) with N = pie chart pixels and W x H = flag dimensions. You could probably improve this by not iterating over windows where you know there will be no flags, and by shifting the window more intelligently. Once you do find a match, you have the coordinates of the corner where you want to call drawImage() to paste your new flag on top.

Of course this approach assumes that the flag you're searching for is represented exactly in the pie chart image. If you are comparing a non-compressed flag to a compressed pie chart image, or vice versa, you won't find a match. Likewise, any size or orientation variations will completely defeat this approach. If you need that kind of flexibility, you're delving into something like SIFT territory. While I'm sure that could be implemented using canvas elements, I wouldn't want to be the one to do it.

In this situation, you'll want to make sure that you don't traverse the DOM unnecessarily while performing iterations. In particular, you will want to store local references to the pixel data as explained here: http://www.onaluf.org/en/entry/13

Given you already know the coordinates and have an image to map, you'll likely want to use drawImage.