New primary seam generator in Enblend

[Rosomack]

Hello all,

I'm happy to announce a new primary seam generator that was recently
integrated into the Enblend mainline. It was developed as part of the
Google Summer of Code 2011 program.

The algorithm is based on the idea of Graph-Cuts :
http://en.wikipedia.org/wiki/Graph_cuts_in_computer_vision
The implementation does not utilize max-flow algorithms, which are
relatively slow and memory-heavy.

The new seam generator takes into account feature frequency as well as
image dissimilarity, and therefore is less likely to cross elements
which would make the seam line more apparent, such as beams, fences,
railings etc.. This should produce better results than the old seam
generator in many cases.

The Graph Cut seam generator works best with a fine mask (--fine-mask
command line option). It requires more memory and time than the old
Nearest Feature Transform algorithm, so it is best to use NFT where
efficiency is essential. Graph-cut on the other hand should produce an
overall better seam in most cases.

For more information on usage and current limitations please refer to
the Enblend manual.

Special thanks to Thomas Modes and Christoph Spiel for great help and
guidance. Also a big thank you for everyone who sent me photos for
testing.

Regards,
Mikolaj

[Terry Duell]

Hullo Mikolaj

On Thu, 01 Sep 2011 21:17:44 +1000, Rosomack
<leszczyns...@gmail.com> wrote:

> Hello all,
>
> I'm happy to announce a new primary seam generator that was recently
> integrated into the Enblend mainline. It was developed as part of the
> Google Summer of Code 2011 program.

Thanks to everyone involved.
Is the new code available for building and testing?

Cheers,
--
Regards,
Terry Duell

[Terry Duell]

Hullo All,

On Fri, 02 Sep 2011 09:21:14 +1000, Terry Duell <tdu...@iinet.net.au>
wrote:

[snip]

> Thanks to everyone involved.
> Is the new code available for building and testing?

--
Regards,
Terry Duell

[Terry Duell]

Hullo All,

On Fri, 02 Sep 2011 09:21:14 +1000, Terry Duell <tdu...@iinet.net.au>
wrote:

[snip]

> Thanks to everyone involved.

> Is the new code available for building and testing?

Sorry, that question could have been better thought out.
I have now got the default from the hg repo and will attempt to build and
test a Fedora package.
I have found that 'cmake .' and 'make package_source' generates
'enblend-4.1.1-Source.tar.gz', which doesn't contain a 'configure' file.
This doesn't seem right.
Also, is the version number correct? At this stage it isn't a release, is
it? I would have expected something like 4.1-0.1 or somesuch, but this
version number business has always been a bit of a bewilderment to me :-)

[Terry Duell]

Hullo All,

On Fri, 02 Sep 2011 11:20:28 +1000, Terry Duell <tdu...@iinet.net.au>
wrote:

[snip]

> I have found that 'cmake .' and 'make package_source' generates

> 'enblend-4.1.1-Source.tar.gz', which doesn't contain a 'configure' file.
> This doesn't seem right.

Not having a good day. Finally figured a few things out. The Cmake option
doesn't appear to work as one would expect, but maybe it's me.
Using 'make --makefile=Makefile.scm' was the way to go...pays to read the
'Readme'.
I have managed to build a Fedora 15 x86_64 rpm without any errors, and it
installs and runs OK.
I ran a quick test on an old project that previously required masks to get
rid of people that appeared in multiple places. This version managed it
better. It does seem to be a bit slower.
A bit more testing needed to really sort out how best to use it.

[Matthew Petroff]

I just uploaded a test build of the Enblend/Enfuse trunk for 32-bit
Windows:
http://db.tt/o65MZB6

Matthew

[kfj]

On 1 Sep., 13:17, Rosomack <leszczynski.miko...@gmail.com> wrote:

> Hello all,
>
> I'm happy to announce a new primary seam generator that was recently
> integrated into the Enblend mainline. It was developed as part of the
> Google Summer of Code 2011 program.

I'm just doing a handheld panorama taken from the top of a reservoir
dam. The banister gave me grief as there were visible blending
artifacts. So I remembered having read of the new algorithm here and
got the latest code from the repo and built it, resulting in enblend
4.1-101796703d73.

When stitching my pano, first thing I noticed was that it was really
slow. When I looked at the output, there was a gaping black hole,
where enblend had simply forgotten one image. I couldn't quite believe
it and reran the stitch to the same effect. When I switched back to
the old algorithm using --primary-seam-generator=nearest-feature-
transform, it was still slow but at least it included all images. Am I
missing something - like, does the new algorithm need the images in a
particular sequence? Does anyone else have this problem?

In the parts where the new algorithm did place seams (so, between the
images it used rather than ignored, it's a 6+1+2), the seam placement
was a great deal better than that of the old algorithm. This makes me
want to have the new one working very much, never mind it's slow! If
needed, I can try and reduce the problem to a simple test case,
compress the images and file a bug report.

Kay

[Rosomack]

Hi Kay,

this sure sounds like a bug.

On 13 Wrz, 21:34, kfj <_...@yahoo.com> wrote:
> In the parts where the new algorithm did place seams (so, between the
> images it used rather than ignored, it's a 6+1+2), the seam placement
> was a great deal better than that of the old algorithm. This makes me
> want to have the new one working very much, never mind it's slow! If
> needed, I can try and reduce the problem to a simple test case,
> compress the images and file a bug report.
>

That would be much appreciated! The algorithm is new, so we have to
iron out the bugs that didn't appear in early tests.

As for the "slow" part, please make sure that you are building without
debug symbols. From my experience it had a significant impact on
performance. The algorithm _is_ slower, but it shouldn't be too bad
even for big pictures.

[kfj]

On 14 Sep., 20:47, Rosomack <leszczynski.miko...@gmail.com> wrote:
> Hi Kay,
>
> this sure sounds like a bug.
>
> On 13 Wrz, 21:34, kfj <_...@yahoo.com> wrote:
>
> > I can try and reduce the problem to a simple test case,
> > compress the images and file a bug report.
>
> That would be much appreciated! The algorithm is new, so we have to
> iron out the bugs that didn't appear in early tests.

this bug seems to be tricky. I tried to replace the images with
dummies by running ptodummy on the pto, but this kept the bug from
happening. I finally managed to boil it down to two images, and I
noticed the first one had a part masked out. When I removed the mask,
the bug would not occur. I've placed the two images in my Ubuntu One
account:

http://ubuntuone.com/5agaYGJD7U8c28IjaXTuTd
http://ubuntuone.com/5wacFTG5X4xbAEIT9Ev34z

Here I can produce the erroneous output by simply doing

enblend -o xx.tif enb*.tif

What happens is that the masked part comes out black and most of the
second image is missing. Still want me to file a bug report with the
tracker?

> As for the "slow" part, please make sure that you are building without
> debug symbols. From my experience it had a significant impact on
> performance. The algorithm _is_ slower, but it shouldn't be too bad
> even for big pictures.

Ooops... thanks for pointing it out. I had just taken the whole cmake
command line from the wiki, and there it's with Debug. The speed seems
more reasonable now I've recompiled with Release.

Kay

[kfj]

On 14 Sep., 20:47, Rosomack <leszczynski.miko...@gmail.com> wrote:

> Hi Kay,
>
> this sure sounds like a bug.

P.S. it seems to have to do with masking. I threw out all masks from
the original project I first saw the problem with, and it stitches
fine now (with my feet and all in it, of course ;)

Kay

[David Benes]

Dne čtvrtek, 15. září 2011, kfj <_k...@yahoo.com> napsal(a):

Hi Kay,

I also received images with black rectangles after blending and I am not using masks in this case. Every time (but not all images are affected) I ran enblend I received black rectangle but with different size.

For me rebuilding enblend without image cache solved my problem.

[kfj]

On 15 Sep., 16:01, David Benes <dben...@gmail.com> wrote:

> I also received images with black rectangles after blending and I am not
> using masks in this case. Every time (but not all images are affected) I ran
> enblend I received black rectangle but with different size.
> For me rebuilding enblend without image cache solved my problem.

Thanks for sharing your solution. But I suppose in my case it's a
different problem, since (as per wiki) I am compiling with image cache
off (or at least I think I do). This is the cmake command line I used
for my last build:

cmake ../enblend.hg -DENABLE_GPU:BOOL=ON -DENABLE_IMAGECACHE:BOOL=OFF -
DENABLE_OPENMP:BOOL=ON -DCPACK_BINARY_DEB:BOOL=ON -
DCPACK_BINARY_NSIS:BOOL=OFF -DCPACK_BINARY_RPM:BOOL=OFF -
DCPACK_BINARY_STGZ:BOOL=OFF -DCPACK_BINARY_TBZ2:BOOL=OFF -
DCPACK_BINARY_TGZ:BOOL=OFF -DCPACK_BINARY_TZ:BOOL=OFF -
DCMAKE_BUILD_TYPE=Release -DCMAKE_INSTALL_PREFIX:PATH=/usr/local

and the -DENABLE_IMAGECACHE:BOOL=OFF should switch the image cache
off. Is that the flag you meant?

Kay

[Felix Hagemann]

Hi Kay,

this pretty much sounds like a known bug in enblend:
bugs.launchpad.net/enblend/+bug/785803
bugs.launchpad.net/enblend/+bug/766501

On 15 September 2011 14:41, kfj wrote:
>
> P.S. it seems to have to do with masking. I threw out all masks from
> the original project I first saw the problem with, and it stitches
> fine now (with my feet and all in it, of course ;)

It's often seen with masks, but seems to be caused by the blending
geometry in general. You can try to change the image order, the size
of the remapped images (scale up or down) or change yaw. All of those
sometimes seem to help.

Felix

[David Benes]

Dne čtvrtek, 15. září 2011, kfj <_k...@yahoo.com> napsal(a):

Thanks for sharing your solution. But I suppose in my case it's a
different problem, since (as per wiki) I am compiling with image cache
off (or at least I think I do). This is the cmake command line I used
for my last build:

cmake ../enblend.hg -DENABLE_GPU:BOOL=ON -DENABLE_IMAGECACHE:BOOL=OFF -
DENABLE_OPENMP:BOOL=ON   -DCPACK_BINARY_DEB:BOOL=ON -
DCPACK_BINARY_NSIS:BOOL=OFF -DCPACK_BINARY_RPM:BOOL=OFF   -
DCPACK_BINARY_STGZ:BOOL=OFF -DCPACK_BINARY_TBZ2:BOOL=OFF -
DCPACK_BINARY_TGZ:BOOL=OFF   -DCPACK_BINARY_TZ:BOOL=OFF -
DCMAKE_BUILD_TYPE=Release -DCMAKE_INSTALL_PREFIX:PATH=/usr/local

and the -DENABLE_IMAGECACHE:BOOL=OFF should switch the image cache
off. Is that the flag you meant?

Kay

I'm sorry Kay, I didn't test enblend on images you provided earlier before sending my solution.

On your images I can confirm the problem. Using --no-optimize parameter for enblend returns little bit better result, but still very far from desired outcome.

Regarding image cache, you are right, -DENABLE_IMAGECACHE:BOOL=OFF is the flag I was talking about.

[kfj]

On 15 Sep., 23:19, Felix Hagemann <felix.hagem...@gmail.com> wrote:
> Hi Kay,
>
> this pretty much sounds like a known bug in enblend:
> bugs.launchpad.net/enblend/+bug/785803
> bugs.launchpad.net/enblend/+bug/766501

You're right. Should have checked...
And while using the latest version to see the effect of the graph cut
algorithm, I noticed the same brightly coloured one-pixel artifacts
which bothered me last time I went bleeding edge with enblend - see

https://bugs.launchpad.net/enblend/+bug/787387

so it looks like I can't use the latest version anyway. I just wish
these bugs were fixed - it gives me a bad gut feeling to see these
bugs just lingering in a piece of software I use pretty much daily...
I know there's a tendency in software development to go for the glory
of new features, but not fixing bugs finally ruins the whole thing for
everyone and the sparkling new features just sink with the flawed
ship.

> On 15 September 2011 14:41, kfj wrote:
>
> > P.S. it seems to have to do with masking. I threw out all masks from
> > the original project I first saw the problem with, and it stitches
> > fine now (with my feet and all in it, of course ;)
>
> It's often seen with masks, but seems to be caused by the blending
> geometry in general. You can try to change the image order, the size
> of the remapped images (scale up or down) or change yaw. All of those
> sometimes seem to help.

Browsing through the bug reports, I also noticed that it seems to
sometimes go away with --fine-mask - no joy here, the problem was
worse with it. What did help (I only tried with my two images from the
reduced set) was to change the order, thanks for the tip - I put the
masked one first and the problem disappeared. Altogether I think I'll
switch back to some previous version, though, because the coloured
dots are very annoying and most of my shots are pure landscapes where
the NFT works just fine.

Kay

[cri]

If can be of any help, I can confirm that I have the same problem with
black area using enblend from the repo and a fresh pano shooted today.
I can also confirm that the problem comes out when I add masks. I will
test the proposed workarounds (change image order or size).

[Rosomack]

Hi all,

the new seam finder works wonders with [--fine-mask].

For those with problems - could you try if it makes a difference? The
new seam generator and the old optimizers sometimes don't get along
very well. There are some minor bugs in the old optimizers that pop up
with the new seam generator more often than with the old one.

Regards,
Mikolaj

[kfj]

On 17 Sep., 12:03, Rosomack <leszczynski.miko...@gmail.com> wrote:
> Hi all,
>
> the new seam finder works wonders with [--fine-mask].

as I've written two mails previously, --fine-mask makes the problem
worse for me.

Kay

[kfj]

On 14 Sep., 20:47, Rosomack <leszczynski.miko...@gmail.com> wrote:

> Hi Kay,
>
> this sure sounds like a bug.

> ...

> As for the "slow" part, please make sure that you are building without
> debug symbols. From my experience it had a significant impact on
> performance. The algorithm _is_ slower, but it shouldn't be too bad
> even for big pictures.

My latest build of enblend is MUCH slower than previous versions, no
matter what seam generator I use. Look at this: first, an older
version of enblend built from a tar ball I had on my system:

kfj@Anja:~/Panorama/Piemont 8-9 2011$ enblend --
version
enblend 4.0-753b534c819d
...

kfj@Anja:~/Panorama/Piemont 8-9 2011$ time enblend -o IMG_1723-
IMG_1731.tif IMG_1723-IMG_1731000?.tif
enblend: info: loading next image: IMG_1723-IMG_17310000.tif 1/1
enblend: info: loading next image: IMG_1723-IMG_17310001.tif 1/1
enblend: info: loading next image: IMG_1723-IMG_17310002.tif 1/1
enblend: info: loading next image: IMG_1723-IMG_17310003.tif 1/1
enblend: info: loading next image: IMG_1723-IMG_17310004.tif 1/1
enblend: info: loading next image: IMG_1723-IMG_17310005.tif 1/1
enblend: info: loading next image: IMG_1723-IMG_17310006.tif 1/1
enblend: info: loading next image: IMG_1723-IMG_17310007.tif 1/1
enblend: info: loading next image: IMG_1723-IMG_17310008.tif 1/1
enblend: warning: some images are redundant and will not be blended
enblend: info: writing final output

real 1m44.463s
user 1m20.729s
sys 0m5.076s

that's what I am used to. Now the same with the latest build (and it's
built as Relase build):

kfj@Anja:~/Panorama/Piemont 8-9 2011$ _enblend --version
enblend 4.1-48edb6264ad8
...

kfj@Anja:~/Panorama/Piemont 8-9 2011$ time _enblend --primary-seam-
generator=nearest-feature-transform -o IMG_1723-IMG_1731.tif IMG_1723-
IMG_1731000?.tif
enblend: info: loading next image: IMG_1723-IMG_17310000.tif 1/1
enblend: info: loading next image: IMG_1723-IMG_17310001.tif 1/1
enblend: info: loading next image: IMG_1723-IMG_17310002.tif 1/1
enblend: info: loading next image: IMG_1723-IMG_17310003.tif 1/1
enblend: info: loading next image: IMG_1723-IMG_17310004.tif
1/1
enblend: info: loading next image: IMG_1723-IMG_17310005.tif
1/1
enblend: info: loading next image: IMG_1723-IMG_17310006.tif
1/1
enblend: info: loading next image: IMG_1723-IMG_17310007.tif
1/1
enblend: info: loading next image: IMG_1723-IMG_17310008.tif
1/1
enblend: warning: some images are redundant and will not be
blended
enblend: info: writing final
output

real
11m33.315s
user
20m29.457s
sys
0m6.664s

I suppose something must be wrong. It's taking about 6.66 (ha!
paranoid? 6.66 as long, and 6.66 sec system time) as long as before.
What other causes apart from compiling with Debug (which I didn't) and
the new algorithm (which I didn't use) could cause this slowdown?

Kay

[Rosomack]

Hi Kay,

OpenMP or GPU support during compilation? Perhaps other developers
could give a better insight (I'm small fish compared to them :) ).

Honestly I don't think it's the new algorithm, just as you said.

Mikolaj

[Jeffrey Martin]

How big do you mean? Can it blend an arbitrarily large image? I mean, does the time scale linearly?

Jeffrey

[Rosomack]

Hi Jeffrey,

the algorithm uses Dijkstra's algorithm with a priority queue, so the
maximum time complexity involved in finding the cut itself should be
somewhere around O(n log(n) + e), n being the number of pixels in the
overlap region and e being the number of edges in the graph used
(since pixels are 4-connected nodes in the graph, worst case here
would be O(n log(n) + 4n)). That said, it usually completes
calculations in a reasonable time even with a fine mask. You can
always test and compare with the old algorithm if in doubt.

Best regards,
Mikolaj