enblend algorithm

[cleanzero]

Hi,
I was trying to study and understand how Enblend algorithm works.
I'm looking at the example in http://enblend.sourceforge.net/details.htm,
where it says (just before the example) "The algorithm finds a line
which is as far away as possible from the edges of the area where two
images intersect".
Looking at the picture I wonder why the line starts at the upper left
corner of the intersection, shouldn't it be in the middle ??? For sure
I'm not understanding the purpose of Enblend. Wouldn't be that
blending line simply the line in the middle of the intersection ? If
someone could enlighten me...Thanks.

--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups "hugin and other free panoramic software" group.
A list of frequently asked questions is available at: http://wiki.panotools.org/Hugin_FAQ
To post to this group, send email to hugin-ptx@...
To unsubscribe from this group, send email to hugin-ptx-unsubscribe@...
For more options, visit this group at http://groups.google.com/group/hugin-ptx
-~----------~----~----~----~------~----~------~--~---

[cspiel]

Hi there!

On Jun 11, 10:25 am, tago <liquidt...@...> wrote:
> I was trying to study and understand how Enblend algorithm works.
> I'm looking at the example in http://enblend.sourceforge.net/details.htm,
> where it says (just before the example) "The algorithm finds a line
> which is as far away as possible from the edges of the area where two
> images intersect".

        This is the correct description of Enblend's initial seam line
generation, i.e. before seam line optimization.  Though I wouldd
prefer a more mathematical statement:
        "The algorithm finds a line whose minimum distance to any edge
        (of the overlap area) is maximal."                  [MAX-DIST]


> Looking at the picture I wonder why the line starts at the upper left
> corner of the intersection, shouldn't it be in the middle?

        Nope.  Think 2-dimensional. ;)  The overlap areas can be
irregular.  E.g., the overlap need not happen from "left-to-right", it
could be from "top-to-bottom" as well.  In the general case two images
can overlap in multiple areas even in the no 2-pi wraparound case.

OK, let us take a look at the example image.  If you place the initial
seam in the middle and I assume you mean horizontal center at the top,
you would get a distance to the left image's boundary (indicated by
the red line) of zero while still having a small distance to the right
image's boundary (indicated by the green line just above the red one).
Thus, this construction violates MAX-DIST because the distance to the
red line is not maximal.

Now, if you look _very_ closely at the example you will notice a tiny
"nose" at the top of the upper vertical segment of the seam line,
which violates MAX-DIST, too.  The overhang there actually is a bug.
See SourceForge bug id #2160427.  The nose can become pronounced with
irregularly shaped overlap areas.  See the attachments to the bug
report.  Regrettably, I have to deny you the pleasure of fixing it.
(Just kidding.)  It has been corrected in the "staging" branch
revision 331:
        http://bazaar.launchpad.net/~cspiel/enblend/staging/revision/331


> For sure I'm not understanding the purpose of Enblend.

        Neither do I. -- Now, will you buy me a beer?

However, I understand the purpose of the initial seam line generation
step.  Usually, the closer we get to an image border the more the
pixels suffer from distortion, aberration, etc.  As Enblend deals with
re-mapped images it is furthermore exposed to the errors introduced by
the projection, which also can increase towards the images' edges.
So, we want to stay away from _any_ edge as far as possible.  MAX-DIST
minimizes the combined "error" of both images participating in the
overlap.

And in the next semester we shall learn about seam line
optimization...


> If someone could enlighten me.

Isn't it better to be enlightened than it is to be enblended?


Cheers,
        Chris

--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups "hugin and other free panoramic software" group.
A list of frequently asked questions is available at: http://wiki.panotools.org/Hugin_FAQ
To post to this group, send email to hugin-ptx@...
To unsubscribe from this group, send email to hugin-ptx-unsubscribe@...
For more options, visit this group at http://groups.google.com/group/hugin-ptx
-~----------~----~----~----~------~----~------~--~---

[cleanzero]

Thanks for trying to help, but....I'm still confused.


> If you place the initial
> seam in the middle and I assume you mean horizontal center at the top,
> you would get a distance to the left image's boundary (indicated by
> the red line) of zero while still having a small distance to the right
> image's boundary (indicated by the green line just above the red one).

Why zero ? If I start the line in the middle of the overlap wouldn't
the horizontal distance between red and green borders exactly half of
the overlap width ?
I was trying to understand this with a friend of mine and apparently
we are both dummy :-)

Is the line generation based on something like the grassfire
transform ?

Are there details on how optimization works ? I guess one needs to
find a line that does not pass thru mismatches (i.e. parallax or
moving objects).

Thanks again.



On Jun 11, 7:04 pm, cspiel <csp...@...> wrote:

> Hi there!
>
> On Jun 11, 10:25 am, tago <liquidt...@...> wrote:
>
> > I was trying to study and understand how Enblend algorithm works.
> > I'm looking at the example inhttp://enblend.sourceforge.net/details.htm,
> > where it says (just before the example) "The algorithm finds a line
> > which is as far away as possible from the edges of the area where two
> > images intersect".
>
>         This is the correct description of Enblend's initial seam line
> generation, i.e. before seam line optimization.  Though I wouldd
> prefer a more mathematical statement:
>         "The algorithm finds a line whose minimum distance to any edge
>         (of the overlap area) is maximal."                  [MAX-DIST]
>
> > Looking at the picture I wonder why the line starts at the upper left
> > corner of the intersection, shouldn't it be in the middle?
>
>         Nope.  Think 2-dimensional. ;)  The overlap areas can be
> irregular.  E.g., the overlap need not happen from "left-to-right", it
> could be from "top-to-bottom" as well.  In the general case two images
> can overlap in multiple areas even in the no 2-pi wraparound case.
>
> OK, let us take a look at the example image.  If you place the initial
> seam in the middle and I assume you mean horizontal center at the top,
> you would get a distance to the left image's boundary (indicated by
> the red line) of zero while still having a small distance to the right
> image's boundary (indicated by the green line just above the red one).
> Thus, this construction violates MAX-DIST because the distance to the
> red line is not maximal.
>
> Now, if you look _very_ closely at the example you will notice a tiny
> "nose" at the top of the upper vertical segment of the seam line,
> which violates MAX-DIST, too.  The overhang there actually is a bug.
> See SourceForge bug id #2160427.  The nose can become pronounced with
> irregularly shaped overlap areas.  See the attachments to the bug
> report.  Regrettably, I have to deny you the pleasure of fixing it.
> (Just kidding.)  It has been corrected in the "staging" branch
> revision 331:
>        http://bazaar.launchpad.net/~cspiel/enblend/staging/revision/331
>
> > For sure I'm not understanding the purpose of Enblend.
>
>         Neither do I. -- Now, will you buy me a beer?
>
> However, I understand the purpose of the initial seam line generation
> step.  Usually, the closer we get to an image border the more the
> pixels suffer from distortion, aberration, etc.  As Enblend deals with
> re-mapped images it is furthermore exposed to the errors introduced by
> the projection, which also can increase towards the images' edges.
> So, we want to stay away from _any_ edge as far as possible.  MAX-DIST
> minimizes the combined "error" of both images participating in the
> overlap.
>
> And in the next semester we shall learn about seam line
> optimization...
>
> > If someone could enlighten me.
>
> Isn't it better to be enlightened than it is to be enblended?
>
> Cheers,
>         Chris

--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups "hugin and other free panoramic software" group.
A list of frequently asked questions is available at: http://wiki.panotools.org/Hugin_FAQ
To post to this group, send email to hugin-ptx@...
To unsubscribe from this group, send email to hugin-ptx-unsubscribe@...
For more options, visit this group at http://groups.google.com/group/hugin-ptx
-~----------~----~----~----~------~----~------~--~---

[cspiel]

Tago -

On Jun 12, 10:06 am, tago <liquidt...@...> wrote:
> Why zero?

        If you are on the border, i.e. at the
red or green lines then the distance to the
respective border is zero.


> If I start the line in the middle of the overlap wouldn't
> the horizontal distance between red and green borders exactly half of
> the overlap width ?

        What is the middle?  How would you
define it?  Does your definition also hold if
you turn the the example 90 degrees?

As I said before the problem is manifestly
two-dimensional.  Just looking at one border is
not enough.  We must look at _all_ borders at
the same time to find out what is the minimum
distance to any of them.


> Is the line generation based on something like the grassfire
> transform ?

        I'm sorry, but I cannot tell you what
Enblend's original algorithm is based upon,
because I never understood it.  8-|

The new algorithm employed in the "staging"
branch uses two nearest neighbor transforms
(NNT) of the differences between the mask files
A and B.  It constructs the seam mask by
assigning zeros to pixels closer to the borders
of A-B and ones to pixels closer to the borders
of B-A.  The boundary between the zeros and the
ones makes up the initial seam line.

You see that neither the computationally
expensive Grassfire-, nor Watershed-
transformations are necessary.  The final
assignment step is a point-wise operation and
thus of linear complexity in the image size.  It
parallelizes trivially.

Latest revisions of "staging" do compute both
NNTs in parallel threads, too, given the project
has been configured with "--disable-image-cache
--enable-openmp" and the compiler supports
OpenMP.


> Are there details on how optimization works ?

        I guess there are lots of them!  It is
just that I have not looked at the seam-line
optimization close enough to tell you what is
going on there.  What about you inspecting it
and teaching me?


> I guess one needs to
> find a line that does not pass thru mismatches (i.e. parallax or
> moving objects).

        As far as I understand, this is the way
Enblend works.  It would explain why SmartBlend
sometimes produces superior output.

I have an idea of how to improve on the
optimization, though.  Hopefully, it will take
us on a par with SmartBlend.  (Kornel will love
to hear this;)


HTH,
        Chris

--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups "hugin and other free panoramic software" group.
A list of frequently asked questions is available at: http://wiki.panotools.org/Hugin_FAQ
To post to this group, send email to hugin-ptx@...
To unsubscribe from this group, send email to hugin-ptx-unsubscribe@...
For more options, visit this group at http://groups.google.com/group/hugin-ptx
-~----------~----~----~----~------~----~------~--~---

[Andrew Mihal-2]

Hi,
    The initial seam line generation I wrote is a nearest feature
transform based on voronoi transformation (Breu et al). There is a bug
in my implementation. I have a half-complete repair that is not
checked in yet, and Christoph has a repair in his staging branch. I
intend to replace the algorithm entirely with Danielsson's 4SED. I
also plan to write a version that computes the distance transform on
the surface of a sphere for full-360 images. Lack of time is the
primary factor holding back these projects.

The seam line optimization uses a two-step approach influenced by
research on active contours. The overlap region between an image pair
is treated as a cost function. Areas of disagreement and areas outside
the intersection region have high cost. First, the result of the
nearest feature transform is vectorized into a polyline, and a
generalized deterministic annealing algorithm is used to adjust the
vertex positions to optimize the cost of the line. The line is
penalized for crossing areas of high cost and vertices are penalized
for moving far from their initial positions in the center of the
overlap region. Second, Dijkstra's shortest path algorithm is used to
fill in the exact seam line between polyline vertices.

If you are interested in working on the seam line optimization, some
points to consider are:

- How to handle seams that are closed contours, e.g. the kind of
overlaps that are formed when patching the zenith or nadir of a
full-360 panorama.
- How to reduce the state space of the optimization to maintain
acceptable performance
- How to avoid geometrically uninteresting seam solutions, such as
seam lines that double back on themselves.
- How to encode the abstract notion of "seam invisibility" as the
optimization goal.
- How to identify image features that should or should not appear in
the final panorama.

I think these are all interesting problems and would be happy to
discuss ideas with you.

Andrew

On Sat, Jun 13, 2009 at 5:42 AM, cspiel <cspiel@...> wrote:

>
> Tago -
>
> On Jun 12, 10:06 am, tago <liquidt...@...> wrote:
>> Why zero?
>
>        If you are on the border, i.e. at the
> red or green lines then the distance to the
> respective border is zero.
>
>
>> If I start the line in the middle of the overlap wouldn't
>> the horizontal distance between red and green borders exactly half of
>> the overlap width ?
>
>        What is the middle?  How would you
> define it?  Does your definition also hold if
> you turn the the example 90 degrees?
>
> As I said before the problem is manifestly
> two-dimensional.  Just looking at one border is
> not enough.  We must look at _all_ borders at
> the same time to find out what is the minimum
> distance to any of them.
>
>
>> Is the line generation based on something like the grassfire
>> transform ?
>
>        I'm sorry, but I cannot tell you what
> Enblend's original algorithm is based upon,
> because I never understood it.  8-|
>
> The new algorithm employed in the "staging"
> branch uses two nearest neighbor transforms
> (NNT) of the differences between the mask files
> A and B.  It constructs the seam mask by
> assigning zeros to pixels closer to the borders
> of A-B and ones to pixels closer to the borders
> of B-A.  The boundary between the zeros and the
> ones makes up the initial seam line.
>
> You see that neither the computationally
> expensive Grassfire-, nor Watershed-
> transformations are necessary.  The final
> assignment step is a point-wise operation and
> thus of linear complexity in the image size.  It
> parallelizes trivially.
>
> Latest revisions of "staging" do compute both
> NNTs in parallel threads, too, given the project
> has been configured with "--disable-image-cache
> --enable-openmp" and the compiler supports
> OpenMP.
>
>
>> Are there details on how optimization works ?
>
>        I guess there are lots of them!  It is
> just that I have not looked at the seam-line
> optimization close enough to tell you what is
> going on there.  What about you inspecting it
> and teaching me?
>
>
>> I guess one needs to
>> find a line that does not pass thru mismatches (i.e. parallax or
>> moving objects).
>
>        As far as I understand, this is the way
> Enblend works.  It would explain why SmartBlend
> sometimes produces superior output.
>
> I have an idea of how to improve on the
> optimization, though.  Hopefully, it will take
> us on a par with SmartBlend.  (Kornel will love
> to hear this;)
>
>
> HTH,
>        Chris
>
> >
>

--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups "hugin and other free panoramic software" group.
A list of frequently asked questions is available at: http://wiki.panotools.org/Hugin_FAQ
To post to this group, send email to hugin-ptx@...
To unsubscribe from this group, send email to hugin-ptx-unsubscribe@...
For more options, visit this group at http://groups.google.com/group/hugin-ptx
-~----------~----~----~----~------~----~------~--~---

[Klaus Foehl]

Hi,

On 14 June, 08:12, Andrew Mihal <andrewcmi...@...> wrote:

> - How to handle seams that are closed contours, e.g. the kind of
> overlaps that are formed when patching the zenith or nadir of a
> full-360 panorama.

It is not only the the closed contour (where there is a bug as shown)
http://wiki.panotools.org/Enblend_Testcase_2008-05-02
but one should think about overlap areas where the bordering
is not just images A-B but maybe A-B-A-B or even A-B-A-B-A-B
when one loops around the bounding line. One needs two
or even three seam lines, and there is a choice of topology.

Computing a nearest neighbour mask based on raster representation
does not run into such kind of problem, of course.

> - How to avoid geometrically uninteresting seam solutions, such as
> seam lines that double back on themselves.

If one crops the stitching output, then topologically
the blend area may be bordered by image A or image B, but third
possibility is that the crop line is a border as well. No problem for
a bitmap-based nearest neighbour algorithm (again), but in principle
one has the freedom to start the seam line, anywhere along the border.
Of course one wants to slightly prefer a mid-point start.

http://wiki.panotools.org/Enblend_Testcase_2008-05-18
shows where a different seam line start would be beneficial.


One more thing. For debugging, for development I would like
--save-masks  --load-masks  --visualises commands
that save all masks and seam line visualisations.
At the moment files only from the last blend step
are surviving (the previous versions are overwritten),
and a standard stitch usually uses more than 2 images.

Regards
Klaus
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups "hugin and other free panoramic software" group.
A list of frequently asked questions is available at: http://wiki.panotools.org/Hugin_FAQ
To post to this group, send email to hugin-ptx@...
To unsubscribe from this group, send email to hugin-ptx-unsubscribe@...
For more options, visit this group at http://groups.google.com/group/hugin-ptx
-~----------~----~----~----~------~----~------~--~---

[Seb Perez-D-2]

On Mon, Jun 15, 2009 at 10:18, Klaus Foehl<kf@...> wrote:
> One more thing. For debugging, for development I would like
> --save-masks  --load-masks  --visualises commands
> that save all masks and seam line visualisations.
> At the moment files only from the last blend step
> are surviving (the previous versions are overwritten),
> and a standard stitch usually uses more than 2 images.

I think the version of enblend by cspiel does that (I haven't tested it yet)

https://code.launchpad.net/~cspiel/enblend/staging

Best,

Seb

--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups "hugin and other free panoramic software" group.
A list of frequently asked questions is available at: http://wiki.panotools.org/Hugin_FAQ
To post to this group, send email to hugin-ptx@...
To unsubscribe from this group, send email to hugin-ptx-unsubscribe@...
For more options, visit this group at http://groups.google.com/group/hugin-ptx
-~----------~----~----~----~------~----~------~--~---

[rewolff]

On Jun 14, 8:12 am, Andrew Mihal <andrewcmi...@...> wrote:

> The seam line optimization uses a two-step approach influenced by
> research on active contours. The overlap region between an image pair
> is treated as a cost function. Areas of disagreement and areas outside
> the intersection region have high cost. First, the result of the
> nearest feature transform is vectorized into a polyline, and a
> generalized deterministic annealing algorithm is used to adjust the
> vertex positions to optimize the cost of the line. The line is
> penalized for crossing areas of high cost and vertices are penalized
> for moving far from their initial positions in the center of the
> overlap region. Second, Dijkstra's shortest path algorithm is used to
> fill in the exact seam line between polyline vertices.

Hmm. I worked on "real time minimimum cost contour detection" in
'92-'95. Why the annealing, there is an algorithm that will give you
the
exact minimum cost.

I would take the initial seam line. take lines perpendicular to this
line
and along this line I'd sample the cost function. A parabolic function
for "distance from the original seam", and some function for the
difference
between the two images. Preferably the number of points on those
perpendicular lines are always the same. This gives a rectangular
matrix
of cost points. Now, for every point in the matrix, you have three
options of getting there from the line above. diagonal from the left
diagonal from the right, or straight down. If you move down the matrix
this way, you'll find the minimum cost from top to bottom through the
matrix, which transforms to a line more or less parallel to the
initial
seam.
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups "hugin and other free panoramic software" group.
A list of frequently asked questions is available at: http://wiki.panotools.org/Hugin_FAQ
To post to this group, send email to hugin-ptx@...
To unsubscribe from this group, send email to hugin-ptx-unsubscribe@...
For more options, visit this group at http://groups.google.com/group/hugin-ptx
-~----------~----~----~----~------~----~------~--~---

[Andrew Mihal-2]

Hi,
    The vertex state space is already restricted to the perpendicular
lines as you suggest. When the initial seam line bends, these state
space lines tend to intersect, which leads to geometrically
uninteresting solutions where the seam line doubles back on itself.
Addressing this issue would be a good start. One of the motivations
for choosing annealing was the ability to encode more complex
optimization criteria into the costfunction, like a penalty for seams
that have self-intersections, or are too straight, or too curvy, or
reduce the enclosed area of a closed contour by too much, etc. The
current implementation is very rudimentary, both in the costfunction
implementation and the annealer itself. I would put more time into it
if I had any to spare.

Andrew

On Thu, Jun 18, 2009 at 1:06 AM,
r.e.wolff<r.e.wolff@...> wrote:

>
> On Jun 14, 8:12 am, Andrew Mihal <andrewcmi...@...> wrote:
>> The seam line optimization uses a two-step approach influenced by
>> research on active contours. The overlap region between an image pair
>> is treated as a cost function. Areas of disagreement and areas outside
>> the intersection region have high cost. First, the result of the
>> nearest feature transform is vectorized into a polyline, and a
>> generalized deterministic annealing algorithm is used to adjust the
>> vertex positions to optimize the cost of the line. The line is
>> penalized for crossing areas of high cost and vertices are penalized
>> for moving far from their initial positions in the center of the
>> overlap region. Second, Dijkstra's shortest path algorithm is used to
>> fill in the exact seam line between polyline vertices.
>
> Hmm. I worked on "real time minimimum cost contour detection" in
> '92-'95. Why the annealing, there is an algorithm that will give you
> the
> exact minimum cost.
>
> I would take the initial seam line. take lines perpendicular to this
> line
> and along this line I'd sample the cost function. A parabolic function
> for "distance from the original seam", and some function for the
> difference
> between the two images. Preferably the number of points on those
> perpendicular lines are always the same. This gives a rectangular
> matrix
> of cost points. Now, for every point in the matrix, you have three
> options of getting there from the line above. diagonal from the left
> diagonal from the right, or straight down. If you move down the matrix
> this way, you'll find the minimum cost from top to bottom through the
> matrix, which transforms to a line more or less parallel to the
> initial
> seam.
> >
>

--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups "hugin and other free panoramic software" group.
A list of frequently asked questions is available at: http://wiki.panotools.org/Hugin_FAQ
To post to this group, send email to hugin-ptx@...
To unsubscribe from this group, send email to hugin-ptx-unsubscribe@...
For more options, visit this group at http://groups.google.com/group/hugin-ptx
-~----------~----~----~----~------~----~------~--~---