Contour Generation

Contour Generation

Post by Kevin Roger » Tue, 11 Apr 2000 04:00:00



I'd appreciate some help with contour generation -- i.e. given a height map,
generate contour lines.

Seems like this should be a well-known algorithm (many apps, including
Photoshop, have some sort of contour generation capability), but I'm unable
to find any info.

Thanks a lot,

Kevin Rogers

 
 
 

Contour Generation

Post by Kenneth Sloa » Tue, 11 Apr 2000 04:00:00



> I'd appreciate some help with contour generation -- i.e. given a height map,
> generate contour lines.

> Seems like this should be a well-known algorithm (many apps, including
> Photoshop, have some sort of contour generation capability), but I'm unable
> to find any info.

There are several "well-known" algorithms.  One trap for the unwary is
that the algorithms often differ (and are considered "good" by different
people) because of the current technology (esp. memory size).

Suppose that your height map is relatively small, and is on a complete
rectangular grid.  You can start by considering every square cell (with
a height sample at each corner) and try to figure out how the contour(s)
pass through the cell.

Alas, some cells will be ambiguous.

In the alternative, you can find (by any means) a cell which contains a
part of the contour, and follow the contour wherever it leads you.

Alas, in some cells, you won't know (for sure) where to go next.

Resolving these ambiguities accounts for lots and lots of papers, and
algorithm design.

I prefer to examine EDGES joining sample points (instead of cells) and
build small pieces of contour separating height samples above and below
the contour height.

Alas, when these are stitched together, the contours may be ambiguous.

Alas, often the ambiguity is inherent in the data.  Then, no matter what
you do, you may end up being screwed.

In my opinion (warning - this opinion is not shared by many) it is
better to delay the resolution of any ambiguity as long as possible, so
that you may take maximum advantage of domain-specific knowledge.    So,
I prefer a method which refuses to make a choice...and allowe me to
represent an ambiguious answer.

If you'd rather have an unambiguous (but perhaps wrong) answer right
away, a convenient way to proceed is to triangulate (arbitrarily) your
square mesh into a triangular mesh.  Then you can either follow each
contour, or generate pieces of contour in all triangular cells in
parallel - and the answer will be unambiguous.

One way to think of this is to think of the triangulated height field as
a piecewise-planar surface in 3D.  Extracting a contour is equivalent to
finding the intersection of this surface with a plane (at constant z).

--

Computer and Information Sciences                       (205) 934-2213
University of Alabama at Birmingham                 FAX (205) 934-5473
Birmingham, AL 35294-1170   http://www.cis.uab.edu/info/faculty/sloan/

 
 
 

Contour Generation

Post by Kevin Roger » Tue, 11 Apr 2000 04:00:00


Hi,

Thanks for the info...however, I still don't quite understand how to do what
I need to do.

Quote:> There are several "well-known" algorithms.  One trap for the unwary is
> that the algorithms often differ (and are considered "good" by different
> people) because of the current technology (esp. memory size).

Is there someplace I can find these "well-known" algorithms documented?

Quote:

> Suppose that your height map is relatively small, and is on a complete
> rectangular grid.  You can start by considering every square cell (with
> a height sample at each corner) and try to figure out how the contour(s)
> pass through the cell.

> Alas, some cells will be ambiguous.

Are you saying that pieces of the contour won't necessarily match up?

Quote:

> In the alternative, you can find (by any means) a cell which contains a
> part of the contour, and follow the contour wherever it leads you.

> Alas, in some cells, you won't know (for sure) where to go next.

> Resolving these ambiguities accounts for lots and lots of papers, and
> algorithm design.

> I prefer to examine EDGES joining sample points (instead of cells) and
> build small pieces of contour separating height samples above and below
> the contour height.

> Alas, when these are stitched together, the contours may be ambiguous.

> Alas, often the ambiguity is inherent in the data.  Then, no matter what
> you do, you may end up being screwed.

Ouch. Suddenly this whole thing is looking quite ambiguous. ;-\

Got any example code?

Thanks again,

Kevin

 
 
 

Contour Generation

Post by Earl F. Glyn » Wed, 12 Apr 2000 04:00:00



Quote:> I'd appreciate some help with contour generation -- i.e. given a height
map,
> generate contour lines.

Try the "Contours, Contour Maps" links in Section B, Algorithms, of
http://www.efg2.com/Lab/Library/Graphics.htm

--
efg


Overland Park, KS  USA

efg's Computer Lab:  http://www.efg2.com/Lab

 
 
 

Contour Generation

Post by Kevin Roger » Wed, 12 Apr 2000 04:00:00


Thanks! That's more like it!





> > I'd appreciate some help with contour generation -- i.e. given a height
> map,
> > generate contour lines.

> Try the "Contours, Contour Maps" links in Section B, Algorithms, of
> http://www.efg2.com/Lab/Library/Graphics.htm

> --
> efg


> Overland Park, KS  USA

> efg's Computer Lab:  http://www.efg2.com/Lab

 
 
 

Contour Generation

Post by Kenneth Sloa » Mon, 17 Apr 2000 04:00:00



> I must disagree with the opinion that "contours generated by folowing a
> contour around an image produce ambiguities".

> These ambiguities can be simply resolved by 'recursion' (i use an explicit
> stack instead).  That is, by following contours in a clockwise manner the
> ambiguities are resolved

> So if the edge is detected when traversing left to right.  for the current
> cell you would proceed down, then right then up.  if the edge was detected
> going down, you proceed left, then down then right.

> I use this technique in extracting contours from medical images.  It
> produces correct results 100% of the time.

You are resolving the ambiguity arbitrarily.  This "works" - but does
not necessarily  produce "correct results".  While it is true that your
program is never confused - it is not at all clear to me that your
program is always right!

Tell me - what does your method produce for the contours at level 2 for
the following input set of samples:

    1 1 1 3 3 3 1 1 1 3 3 3 1 1 1 3 3 3
    1 1 1 3 3 3 1 1 1 3 3 3 1 1 1 3 3 3
    1 1 1 3 3 3 1 1 1 3 3 3 1 1 1 3 3 3
    3 3 3 1 1 1 3 3 3 1 1 1 3 3 3 1 1 1
    3 3 3 1 1 1 3 3 3 1 1 1 3 3 3 1 1 1
    3 3 3 1 1 1 3 3 3 1 1 1 3 3 3 1 1 1
    1 1 1 3 3 3 1 1 1 3 3 3 1 1 1 3 3 3
    1 1 1 3 3 3 1 1 1 3 3 3 1 1 1 3 3 3
    1 1 1 3 3 3 1 1 1 3 3 3 1 1 1 3 3 3
    3 3 3 1 1 1 3 3 3 1 1 1 3 3 3 1 1 1
    3 3 3 1 1 1 3 3 3 1 1 1 3 3 3 1 1 1
    3 3 3 1 1 1 3 3 3 1 1 1 3 3 3 1 1 1
    1 1 1 3 3 3 1 1 1 3 3 3 1 1 1 3 3 3
    1 1 1 3 3 3 1 1 1 3 3 3 1 1 1 3 3 3
    1 1 1 3 3 3 1 1 1 3 3 3 1 1 1 3 3 3
    3 3 3 1 1 1 3 3 3 1 1 1 3 3 3 1 1 1
    3 3 3 1 1 1 3 3 3 1 1 1 3 3 3 1 1 1
    3 3 3 1 1 1 3 3 3 1 1 1 3 3 3 1 1 1

And, please explain why the contours generated are the "correct result".

(actually, there *is* a correct answer - but most people won't like it.
They may tolerate it in 2D, but almost no one is happy with the
analogous result in 3D.  Nevertheless, it *is* correct.)

I'm most eager to see if your program generates the "correct" answer.  
Most of the programs in the literature which match your high-level
description do *not* get it right.  (at least, I haven't seen very many
in over 30 years of working on this kind of problem...)

--

Computer and Information Sciences                       (205) 934-2213
University of Alabama at Birmingham                 FAX (205) 934-5473
Birmingham, AL 35294-1170   http://www.cis.uab.edu/info/faculty/sloan/

 
 
 

Contour Generation

Post by tecel00 » Tue, 18 Apr 2000 04:00:00


I must disagree with the opinion that "contours generated by folowing a
contour around an image produce ambiguities".

These ambiguities can be simply resolved by 'recursion' (i use an explicit
stack instead).  That is, by following contours in a clockwise manner the
ambiguities are resolved

So if the edge is detected when traversing left to right.  for the current
cell you would proceed down, then right then up.  if the edge was detected
going down, you proceed left, then down then right.

I use this technique in extracting contours from medical images.  It
produces correct results 100% of the time.

aaron



> > I'd appreciate some help with contour generation -- i.e. given a height
map,
> > generate contour lines.

> > Seems like this should be a well-known algorithm (many apps, including
> > Photoshop, have some sort of contour generation capability), but I'm
unable
> > to find any info.

> There are several "well-known" algorithms.  One trap for the unwary is
> that the algorithms often differ (and are considered "good" by different
> people) because of the current technology (esp. memory size).

> Suppose that your height map is relatively small, and is on a complete
> rectangular grid.  You can start by considering every square cell (with
> a height sample at each corner) and try to figure out how the contour(s)
> pass through the cell.

> Alas, some cells will be ambiguous.

> In the alternative, you can find (by any means) a cell which contains a
> part of the contour, and follow the contour wherever it leads you.

> Alas, in some cells, you won't know (for sure) where to go next.

> Resolving these ambiguities accounts for lots and lots of papers, and
> algorithm design.

> I prefer to examine EDGES joining sample points (instead of cells) and
> build small pieces of contour separating height samples above and below
> the contour height.

> Alas, when these are stitched together, the contours may be ambiguous.

> Alas, often the ambiguity is inherent in the data.  Then, no matter what
> you do, you may end up being screwed.

> In my opinion (warning - this opinion is not shared by many) it is
> better to delay the resolution of any ambiguity as long as possible, so
> that you may take maximum advantage of domain-specific knowledge.    So,
> I prefer a method which refuses to make a choice...and allowe me to
> represent an ambiguious answer.

> If you'd rather have an unambiguous (but perhaps wrong) answer right
> away, a convenient way to proceed is to triangulate (arbitrarily) your
> square mesh into a triangular mesh.  Then you can either follow each
> contour, or generate pieces of contour in all triangular cells in
> parallel - and the answer will be unambiguous.

> One way to think of this is to think of the triangulated height field as
> a piecewise-planar surface in 3D.  Extracting a contour is equivalent to
> finding the intersection of this surface with a plane (at constant z).

> --

> Computer and Information Sciences                       (205) 934-2213
> University of Alabama at Birmingham                 FAX (205) 934-5473
> Birmingham, AL 35294-1170   http://www.cis.uab.edu/info/faculty/sloan/

 
 
 

Contour Generation

Post by Dave Eberl » Tue, 18 Apr 2000 04:00:00



<snip>

Quote:> (actually, there *is* a correct answer - but most people won't like it.
> They may tolerate it in 2D, but almost no one is happy with the
> analogous result in 3D.  Nevertheless, it *is* correct.)

Ken, you've been doing this stuff long enough to know that
the term "correct answer" only makes sense if you specify
what continuous formulation you have in mind to represent
the discrete image data.  Two different continuous
formulations can lead to two topologically different sets of
contours.

Once you choose your continuous formulation, then the
real problem is to correctly extract the level curves or
level surfaces.  While I am sure you know this, but for
the benefit of others, using trilinear interpolation in 3D
as the continuous formulation, Marching Cubes fails to
correctly extract the level surfaces.  The algorithms
benefit is its speed at the expense of topological
correctness.

--
Dave Eberly

http://www.magic-software.com