enblend / black corners and fringes

[Wirz]

Hi,

I have a been looking at the enblend problem that is described here
(https://bugs.launchpad.net/enblend/+bug/721136) a bit more.

In all examples that I know of, the problem is that the seamline(s)
run(s) slightly outside of the overlap area. As a result, pixels are
included from one image which lie outside the image's area, or in a
transparent area (which apparently is not invalid but black). This
problem can occur for NFT and GC, becomes less frequent with fine and/or
optimise but can occur with any combination.

An obvious example is the result (1) with seamlines (2) which is
generated from the example files I have added to the above thread. This
particular example uses coarse/no-opt/gc.


If I understand the relevant algorithms correctly, this problem could
be/should be caught in three different places:
1) Neither GC nor NFT should return a seamline outside the overlap
2) the seamline optimisation should return only seams inside the
overlapping region
3) the blending should not assume out-of-bound or transparent pixels to
be black but either transparent or take a pixel from the other picture.


Which brings me to my question: Do you have any opinion on where this
problem should be fixed? I would assume fixing 3) is the easiest and
safest. On the other hand, seamlines outside the overlap area, produced
by 1) or 2) entirely refute the point of finding a good seamline to
begin with (leading to poor quality). So maybe one should treat this
problem in all three places (four actually, because GC, NFT, opt, blending)?

cheers, lukas


(1) http://78.46.190.157:8080/foo.tif
(2) http://78.46.190.157:8080/vis-1.tif

[Monkey]

I think all three should be fixed. #3 was one motivation for writing Multiblend, because it can cause problems even when seams don't stray (particularly when image edges make a corner). Multiblend assumes any out-of-bounds pixel (per image) is the same colour as its nearest in-bounds neighbour.

Of course even if you do that, if seam lines stray too close to the overlap then you will end up using the higher frequency components of those "fake" pixels to fill in that black hole, which is also not ideal, and if the seam lines stray outside the overlap region then you get those "fake" pixels directly visible (black in Enblend's case because it doesn't extend images in that way).

NFT seams should never go near the edges, so if it happens without optimisation I assume it's down to using a coarse mask. My knowledge may be a bit out of date, but my understanding of Enblend's seam generation is that the NFT is very precise (geometrically speaking) but very slow (hence the option for coarse masks), and the precision is unwarranted given that there are much faster methods and geometric precision isn't necessary. Multiblend's seams are different, but for practical purposes they are just as valid as Enblend's.

I've been doing a lot of work on image pyramids lately so a new version of MultiBlend may be a future project. I just did a test with a 70mp 11 image mosaic and MultiBlend is still 25x faster than the latest Enblend (with like-for-like settings) :D I know a lot more about multithreading and SSE now, so I'm hoping for at least double the speed.

[Wirz]

Hi!

On 26/09/2019 20:27, Monkey wrote:
> I think all three should be fixed. #3 was one motivation for writing
> Multiblend, because it can cause problems even when seams don't stray
> (particularly when image edges make a corner). Multiblend assumes any
> out-of-bounds pixel (per image) is the same colour as its nearest in-bounds
> neighbour.

That's a good points, I hadn't thought about the diffuser blending layers.

> Of course even if you do that, if seam lines stray too close to the overlap
> then you will end up using the higher frequency components

you mean lower frequency, right?

> of those "fake"
> pixels to fill in that black hole, which is also not ideal, and if the seam

> lines stray *outside* the overlap region then you get those "fake" pixels

> directly visible (black in Enblend's case because it doesn't extend images
> in that way).

Do you know how many pixels are maximally included to both sides (by
means of diffuser layers) in enblend and multiblend? I have never
noticed an artefact where there is a grey fringe without black which
should result from the seam being close to the edge but not beyond the edge.

> NFT seams should never go near the edges, so if it happens without
> optimisation I assume it's down to using a coarse mask. My knowledge may be
> a bit out of date, but my understanding of Enblend's seam generation is
> that the NFT is very precise (geometrically speaking) but very slow (hence
> the option for coarse masks), and the precision is unwarranted given that
> there are much faster methods and geometric precision isn't necessary.

NFT is of course very close to the edge at the two entry points and if
either the coarse mask or the optimisation mess up, it might end up on
the wrong side ...

> Multiblend's seams are different, but for practical purposes they are just
> as valid as Enblend's.

Is there an easy description of how they are constructed? Do you
explicitly penalise close proximity to the edges?

cheers, lukas

[Monkey]

On Sunday, 29 September 2019 22:58:09 UTC+1, lukas wrote:

you mean lower frequency, right?

No, higher (I said highEST but I meant highER). Lower frequencies would be expected to be used, because they will have spread from valid areas. You don't want to see the higher frequency components though (which will include the hard edge in Enblend's case, although I'm not 100% sure on how it works).

 

Do you know how many pixels are maximally included to both sides (by
means of diffuser layers) in enblend and multiblend?  I have never
noticed an artefact where there is a grey fringe without black which
should result from the seam being close to the edge but not beyond the edge.

That depends on the number of levels, which varies. In Enblend's case I think it's related to the size of overlap as each image is added (so some images may get blended more or less than others). In Multiblend, it depends on the size of the images (either input images or output image, depending if --wideblend is specified).

For the same number of levels, Multiblend blends about half as much as Enblend does, but it probably picks a higher number of levels. I think the total "spread" of a pixel's influence varies with the number of level cubed.

NFT is of course very close to the edge at the two entry points and if
either the coarse mask or the optimisation mess up, it might end up on
the wrong side ...

Is there an easy description of how they are constructed?  Do you
explicitly penalise close proximity to the edges?

To clarify, Multiblend's seams are still precise in a general sense, they just operate with a different metric. Enblend calculates the true Euclidean distances, which I think is one reason it is slow (it's optimised, but the algorithm is still complicated), whereas Multiblend uses a propagating algorithm, increasing distance by (if I remember rightly) 3 for every horizontal/vertical pixel and 4 for every diagonal pixel (only addition and comparison required). That results in a distance function which is more of a fat octagon than a circle, but for calculating seam lines it makes no practical difference to how "good" they are, unless you've somehow managed to take geometrically perfect photos, which never happens.

So there's no explicit penalty for being close the edges, but I'd say at worst Multiblend might stray about 5% closer (in a Euclidean sense) to the edges than Enblend.

[T. Modes]

Hi Lukas,

I got an answer from Chris Spiel, the main enblend developer, to your questions.

I hope this helps you further.

Am Mittwoch, 25. September 2019 23:14:41 UTC+2 schrieb lukas:

In all examples that I know of, the problem is that the seamline(s)
run(s) slightly outside of the overlap area.

        Furthermore, there are problems if the Simulated-Annealing
seamline optimizer plaits loops or sometimes even only cusps.

                                             As a result, pixels are
included from one image which lie outside the image's area, or in a
transparent area (which apparently is not invalid but black).  This
problem can occur for NFT and GC, becomes less frequent with fine and/or
optimise but can occur with any combination.

        I'd be surprised if *pure* NFT generates a seamline outside
the overlap area.  BTW, you can compare the Vigra implementation
(default; on host CPU) with the OpenCL implementation of the NFT
running on a GPGPU (only Manhattan and Euclidean metrics here).  Use
parameter "gpu-kernel-dt" to reroute the program flow.

Rosomack is the expert for GC; it's his code.

--- snip ---
If I understand the relevant algorithms correctly, this problem could
be/should be caught in three different places:
1) Neither GC nor NFT should return a seamline outside the overlap

Correct.

2) the seamline optimisation should return only seams inside the
overlapping region

Also correct.

3) the blending should not assume out-of-bound or transparent pixels to
be black but either transparent or take a pixel from the other picture.

        Indeed we ought to file this item under "never reached".  But
obviously these conditions *are* met and black or just weird areas can
show up in the blended image if the seamline took a detour to la-la
land.

Which brings me to my question:  Do you have any opinion on where this
problem should be fixed?  I would assume fixing 3) is the easiest and
safest.  On the other hand, seamlines outside the overlap area, produced
by 1) or 2) entirely refute the point of finding a good seamline to
begin with (leading to poor quality).  So maybe one should treat this
problem in all three places (four actually, because GC, NFT, opt, blending)?

        After more than a decade of maintaining Enblend/Enfuse I can
tell you that the difficulties really start when you dive into the
code.

The first step I'd take is to add a set of precise diagnostics that
help spotting the problem.  For example:
  * issue a warning for any deviant seamline in the terminal window,
  * improve the output of `--visualize',
  * paint incorrect black areas with #ff00ff, or enclose them with
    #00ffff-colored diamonds (at a minimum size to emphasize
    single-pixel errors)
There is no reason to restrict these diagnostics to the final image as
any stage could be buggy and equally deserves a check.  For
flexibility and reducing the number of recompilations `--parameter'
always comes in handy; see file "parameter.h".

IMO, the second step could be to work through the image-processing
pipeline front-to-back, i.e. start with the NFT, make it rock solid.
Then proceed to GC, harden it, and so on.


HTH,
        cls

[Wirz]

Hi Thomas and Chris,

Thank you for your suggestions! I'm not sure when I'll have time for
that, but starting with improved error detection should certainly be
doable for some time soon.

It's not important but I actually have an example where NFT+coarse+nopt
leads to small but well visible black triangles next to the entry points
of the seam. Even with NFT+fine+nopt I can spot a single black pixel.

cheers, lukas

On 30/10/2019 19:09, T. Modes wrote:
> Hi Lukas,
>
> I got an answer from Chris Spiel, the main enblend developer, to your
> questions.
> I hope this helps you further.
>
> Am Mittwoch, 25. September 2019 23:14:41 UTC+2 schrieb lukas:
>
> In all examples that I know of, the problem is that the seamline(s)
> run(s) slightly outside of the overlap area.
>
> Furthermore, there are problems if the Simulated-Annealing
> seamline optimizer plaits loops or sometimes even only cusps.
>
>
> As a result, pixels are
> included from one image which lie outside the image's area, or in a
> transparent area (which apparently is not invalid but black). This
> problem can occur for NFT and GC, becomes less frequent with fine and/or
> optimise but can occur with any combination.
>

> I'd be surprised if **pure** NFT generates a seamline outside

> the overlap area. BTW, you can compare the Vigra implementation
> (default; on host CPU) with the OpenCL implementation of the NFT
> running on a GPGPU (only Manhattan and Euclidean metrics here). Use
> parameter "gpu-kernel-dt" to reroute the program flow.
>
> Rosomack is the expert for GC; it's his code.
>
>
>
> --- snip ---
> If I understand the relevant algorithms correctly, this problem could
> be/should be caught in three different places:
> 1) Neither GC nor NFT should return a seamline outside the overlap
>
> Correct.
>
>
>
> 2) the seamline optimisation should return only seams inside the
> overlapping region
>
> Also correct.
>
>
>
> 3) the blending should not assume out-of-bound or transparent pixels to
> be black but either transparent or take a pixel from the other picture.
>
> Indeed we ought to file this item under "never reached". But

> obviously these conditions **are** met and black or just weird areas can

[Gunter Königsmann]

A possibility that often is overlooked is the reason for many glitches in modern computer games: What if all algorithms work out as expected - but even the small numeric error double floats make add up to one pixel? Wilkinson's polynomial shows us that truly catastrophic add-up can occur in simple mathematical problems of the like hugin solves even without trigonometric functions that can convert small errors on the input to large errors on the output => leaving one pixel of error margin might do wonders even where the equation is flawless math. If Wilkinson's polynomial isn't impressive enough feel free to search for Siegfried Rump's polynomials. Both have been indicated to me by Richard Fateman from the maxima Project that is about an open-source program that is willing willing to do nearly all maths (including playing with equations) you'll ever need.

Kind regards,

Gunter.

--
Diese Nachricht wurde von meinem Android-Gerät mit K-9 Mail gesendet.