Search code examples
pythonimage-processing

Method to replace pixel color with nearest pixel color that is not itself

For example, say this is the input:

enter image description here

For each pixel in the image, I want to replace that pixel with the color of its closest pixel (in terms of distance) that is not its color.

Here is an example of what I mean:

enter image description here

When thinking of possible ways to do this, I thought of BFS but soon realized that that process would probably take too long as the image size grows. Of course, I could be wrong since I don't have much experience with BFS.

So instead, I am looking to see if there is an alternative process to achieve the same result whether there's some image processing technique to accomplish this or another method.

Solution

  • yes, sure you have to go "BFS" there, but it actually means too little in this context. The problem here is that it is an expensive search, requiring you to visit a number of neighbors per pixel that grows quadratically to the "spot size". (remapping each pixel is already a quadratic problem proportional to the image area - so could end having a problem of 4th magnitude if your spots grow along with the image).

    This problem requires that you to think about it with no "ready made" standard algorithm, named after someone to be found in books - I would try locating the middle of each spot and spiral away from it - if space the spiral cycles, you will enclose regions that should have the same neighbors.

    Or you could trace pixels from selected vertical and horizontal lines, color up entire rectangular regions as long as they have the same color bordering lines, and just go bisecting the distance between these lines, skipping resolved regions.

    Also, there are different data you find for a given pixel distances to the spot borders that you could annotate, so that when traversing the image from other pixels, you can reuse that data - but it is not a trivial thing to do.

    You will have t think of an approach, and code it up. (no one here will write code from zero for you. If you happen to have an algorithm that you can't put into code, then you can put all the code you have - that code should be a minimal reproducible example: since it is "Python", include the import statments, file-reading calls to acquire the target image, and call to your function, so that people can tinker with your code and suggest fixes.