Make sure draw_ancientmap.anti_alias is actually correct before making it fast

[MM1nd]

Hi

I think we might have a problem, which took me way too long to hunt down, so let me back up a bit.

This is common.anti_alias as it was before I turned it into a convolution:

def anti_alias(map, steps): 
    """
    Execute the anti_alias operation steps times on the given map
    """
    height, width = map.shape

    def _anti_alias_step(original):
        anti_aliased = copy.deepcopy(original)
        for y in range(height):
            for x in range(width):
                anti_aliased[y, x] = anti_alias_point(original, x, y)
        return anti_aliased

    def anti_alias_point(original, x, y):
        n = 2
        tot = map[y, x] * 2
        for dy in range(-1, +2):
            py = (y + dy) % height
            for dx in range(-1, +2):
                px = (x + dx) % width
                n += 1
                tot += original[py, px]
        return tot / n

    current = map
    for i in range(steps):
        current = _anti_alias_step(current)
    return current

Notice a few things:

• In every step there is added a map[y,x]*2 part that does not depend on the previous step but keeps the result somewhat close to the original. Unfortunately the original parameter is very confusingly named in that respect.
• In every step a copy is made and only the copy is changed. The parts of the sum -- if they do not depend on the original map -- depend only on the previous step, never on changes made earlier in the same step.
• py and pxare mapped by the modulo operator to the half open interval from 0 to height or width respectively. range(0, width) in python notation. This makes for what we might call circular boundary conditions (i. e. this particular operation treats the map as if it were a torus)

I'm no expert in information theory, but all of this makes perfect sense, both sematically and mathematically. I think we can safely assume that this implementaion is correct. The current implementation shows exactly the same behaviour, only faster.

Compare that with draw_ancientmap.anti_alias as it is now:

    #...
    def anti_alias(steps):

        def _anti_alias_step():
            for y in range(resize_factor * world.height):
                for x in range(resize_factor * world.width):
                    _anti_alias_point(x, y)

        def _anti_alias_point(x, y):
            n = 2
            tot_r = target[y, x][0] * 2
            tot_g = target[y, x][1] * 2
            tot_b = target[y, x][2] * 2
            for dy in range(-1, +2):
                py = y + dy
                if py > 0 and py < resize_factor * world.height:
                    for dx in range(-1, +2):
                        px = x + dx
                        if px > 0 and px < resize_factor * world.width:
                            n += 1
                            tot_r += target[py, px][0]
                            tot_g += target[py, px][1]
                            tot_b += target[py, px][2]
            r = int(tot_r / n)
            g = int(tot_g / n)
            b = int(tot_b / n)
            target[y, x] = (r, g, b, 255)

        for i in range(steps):
            _anti_alias_step()

anti_alias(1)

Again notice a few points:

• This looks superficially similar to the version in common.py that I find it very likely that it was copied and then edited.
  • The main thing this seems to do differently is that it operates on individual channels of an image (r, g, b) and has different boundary conditions.
• Correct me if I am wrong, but this looks a lot like it was supposed to do mostly the same thing as common.anti_alias

Unfortunately it doesn't do the same thing at all. The points in the first list all fail here:

• target[y, x][0] * 2 refers to the result from the previous step, not the original state before any anti-aliasing. This might be intentional, but I kindof assume it's not, because there is no point in having seperate functions for the whole operation and individual steps, if not to take advantage of python scoping rules. Ironically this is far less of a problem, than one should assume, because the whole thing is only ever called with step=1 still I argue it would show incorrect behaviour it ever called with larger values for step.
• py and px are clipped by the if to the open intervall from 0 to height and width respectively. range(1,height) in python notation. Here I cannot even imagine circumstances where that would be intentional, I think it is simply a mistake (easily explainend because only very rarely the >= operator is what one wants). Again note that ironically this does not show because this close to the boundary our maps are water and there is nothing to anti-alias there, Still, incorrect code is incorrect.
• No copy is made. the operation is done in place and that means that the values in the current step are calculated on the basis of other values calculated in the same step, or more generally that the result of the operation depends on the order in which the values are iterated. This one actually does have an inpact on the result. Whether this is simply a bug or an intentional attempt to get rid of the copy at seemingly no cost or something else, I don't know. I do want to argue though, that to the degree to which common.anti_alias is correct, this is not, regardless the intentions.

Now for the hard part:

Long story short, I think this is not a correct implementation of the anti-alias operation and the aforestated points should be fixed. This would mean changing the "blessed" images so that the tests still pass. The test, IMO, is currently testing the wrong thing. Which is very unfortunate.

Full disclosure: Since the result is currently dependent on iteration order, it cannot be made fast. That's just a simple fact of life. So I see some risk that this comes across as "Alex wants to change the blessed image so that his fancy convolution works". I want to be very clear that that is not where I'm coming from. That is why I presented this in comparison with the naive but correct implementation, not the convolution. I'm genuinely convinced that this version is incorrect as it is implemented now.

Ideally, I think one of you should implement this correctly, i. e. after the pattern of the original common.anti_alias, and generate a new blessed image so that any risk of me tailoring the test to accept what I want to implement anyways, is mitigated. Should be an hour of work, tops. Maybe I'm too careful here.

Cheers

Alex

[MM1nd]

To further illustrate the point, here is the output as it is now: Note how the upper and left side of the small islands are darker.

This is what I think would be correct:

Notice how small islands are anti-aliased symetrically. One might argue that real islands aren't symmetrical. However they are also not predictably asymmetrically towards the north west. Anti-aliasing cannot magically conjure information from nothing.

[ftomassetti]

I think we can change the blessed images when it makes sense: the goal of having images is that we can manually check them and decide what it makes sense. I would not be stopped by a minor change in the final output when it is well thought and reasoned as in this case.

On 8 October 2017 at 17:46, MM1nd notifications@github.com wrote:

To further illustrate the point, here is the output as it is now: [image: am_incorrect] https://user-images.githubusercontent.com/1690444/31318282-e379a284-ac4f-11e7-8f65-cf185bc51d05.png Note how the upper and left side of the small islands are darker.

This is what I think would be correct: [image: am_correct] https://user-images.githubusercontent.com/1690444/31318283-e53c67e6-ac4f-11e7-97c4-4b45b900eaa2.png

Notice how small islands are anti aliased symetrically. One might argue that real islands aren't symmetrical. However they are also not predictably asymmetrically towards the north west. Anti-liasing cannot magically conjure information from nothing.

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/Mindwerks/worldengine/issues/250#issuecomment-335015509, or mute the thread https://github.com/notifications/unsubscribe-auth/AAazJlV7fo1t9cpUvVNWJs268TY5chbwks5sqO5xgaJpZM4PuILT .

-- Website at https://tomassetti.me GitHub https://github.com/ftomassetti

[MM1nd]

In that case I'll make a PR of what I have.

[MM1nd]

It seems I can only close this "red". Can you mark it as resolved?

[ftomassetti]

Issues can just be closes, while PR can be merged or closed, so closing it is the right thing to do here