Find the outline of the difference between images

Question

I am trying to find outlines of one or more differences between two images.

Suppose you have two identical images. Then add an opaque square and a triangle to one of the images in random places. Forms may not overlap.

I want to get the coordinates of the outermost pixels of these shapes, and these coordinates should be “grouped” → I want to get two sets of coordinates, one for each shape.

I tried to compare each pixel and take the minimum and maximum values ​​of x and y, which give me the bounding box of the form. I have two problems: this gives me a bounding box, not the outline of a figure. And it works only if the image has no more than one shape.

I can’t think about how to do this for a lifetime.

I am pretty much attached to php, but I can go with either gd or imagick. I have a slight preference regarding gd, but imagick is faster and more powerful, so that is fine too.

Bonus points: the end result should be a simple (as simple as possible) polygon on the form. Some loss of accuracy is in order, and is actually encouraged. Polygon lines do not have to follow contours; some deviations are allowed in favor of fewer points.

Edit:
What I mean by contour is this: suppose I have an image with a rectangle drawn on it. The outline I would like to find is the four points that make up the rectangle. The image on which it is drawn can be any image. It can be a white canvas or a landscape or a portrait, you name it.
And now I understand that the order of the items is important. I should be able to re-draw the square, not in the shape of an hourglass.

Edit 2:
I'm one step closer using imagination.

convert img/modified.png img/original.png -compose ChangeMask -composite out.png 

This command uses the original as a mask for the modified version and gives me an image with only a shape in it. Perhaps with this image I can use the standard border detection algorithm.
One constant problem: it only works if there is only one shape in the image. But if this turns out to be a consequence, I think it will be normal.

Edit 3:
Now I can get the contours of not too complex shapes. But this leads to hundreds of points, which is too much. It should be compressed to about 20 points.

The process is as follows:

• I use the above imagemagick command which gives me an image with only a shape, the rest of the image is transparent
• In this image, I start at the top (0,0) and look down to find an opaque pixel. Then I look at (1,0), etc. When I reach the end, I start with (width, 0) and look left for an opaque pixel. So I walk around the image to “feel” the contours.

Answer 1

Here is a decent walkthrough of several contour tracing algorithms. Personally, I used the Moore environment tracking algorithm ( another link ) with good results. I believe that this is accurate and it keeps order, so you do not close the hourglass problem.

However, before I get to this point, I often have to do some preprocessing ( morphological filters or image subtraction (as you know)),

After these two steps you should have a set of points. You have two options:

1) Complex: collect them into vectors. If the vectors abruptly change the slope (or direction), you know that you have a point. Command line tools like potrace can do this. The potrace algorithm is here and very good. In the example of your simple rectangle, this will work, but it will also work in a more complex scenario such as a circle (you just have a lot of vectors for the circle).

2) Simple: move the pixels you found using Moore-Neigborhood and detect a change in direction. (otherwise, if three pixels form a line, and the next three are not “embedded” with some threshold x, then you have an angle). This algorithm will work for a square, but begins to fall apart for more complex images, such as octogons and circles, where the angular delta between the lines is more obtuse.

If all your shapes are simple enough (square circle ect), you can also consider pattern matching (a simple shape definition). A good link is here in the Aforge documentation.