detecting planes in 3D data

classic Classic list List threaded Threaded
9 messages Options
Reply | Threaded
Open this post in threaded view
|

detecting planes in 3D data

Ed Elston
My goal is detect planes in 3d data. At this time I haven't really
found a good approach to doing this and I am interested in suggestions
on how to start.

My range data is somewhat noisey so I expect that filtering to smooth
this will be required - that is given. Suppose I have very good data,
I still don't have an approach that allows me to segment the data into
regions and then fit an equation to that data which represents a plane.

Thanks, Ed



Reply | Threaded
Open this post in threaded view
|

RE: detecting planes in 3D data

Dave Grossman
There are probably established techniques for this, but I don't know them.
In the absence of such info, here is an approach: For each subset of 3
points, compute the unique plane. Each such plane can be characterized by 3
numbers: The altitude angle, the azimuth angle, and the distance from the
origin. Clustering could be done on these 3 properties. Then the averages
could be generated for each cluster.
 
 
 
  _____  

From: [hidden email] [mailto:[hidden email]] On Behalf Of Ed
Elston
Sent: Wednesday, January 07, 2009 6:48 AM
To: [hidden email]
Subject: [OpenCV] detecting planes in 3D data



My goal is detect planes in 3d data. At this time I haven't really
found a good approach to doing this and I am interested in suggestions
on how to start.

My range data is somewhat noisey so I expect that filtering to smooth
this will be required - that is given. Suppose I have very good data,
I still don't have an approach that allows me to segment the data into
regions and then fit an equation to that data which represents a plane.

Thanks, Ed



 


[Non-text portions of this message have been removed]

Reply | Threaded
Open this post in threaded view
|

Re: detecting planes in 3D data

get_imaginary
In reply to this post by Ed Elston
Hi Ed,

Not sure what you mean by 3d data...? Do you mean you have data from a
3d camera (i.e., a range camera), SICK Laser device, or similar?

If what you have is two images, the standard technique is to use
ransac on candidate point matches to find the homography with the most
support. Is that applicable to your problem and data?

Robin


--- In [hidden email], "Ed Elston" <ed.elston@...> wrote:

>
> My goal is detect planes in 3d data. At this time I haven't really
> found a good approach to doing this and I am interested in suggestions
> on how to start.
>
> My range data is somewhat noisey so I expect that filtering to smooth
> this will be required - that is given. Suppose I have very good data,
> I still don't have an approach that allows me to segment the data into
> regions and then fit an equation to that data which represents a plane.
>
> Thanks, Ed
>


Reply | Threaded
Open this post in threaded view
|

Re: detecting planes in 3D data

Ed Elston
I am evaluating a 3D IR time of flight camera which provides range
and intensity data in a pair of matching images.  It probably
appears the same as the output of a stereo pair after reconstruction
but I'm not that familiar with it.

I am reading about ransac but have no experience with it.  I'm not
clear on your suggestion about finding the homography with the most
support ???

Ed

--- In [hidden email], "Robin" <rhewitt@...> wrote:
>
> Hi Ed,
>
> Not sure what you mean by 3d data...? Do you mean you have data
from a
> 3d camera (i.e., a range camera), SICK Laser device, or similar?
>
> If what you have is two images, the standard technique is to use
> ransac on candidate point matches to find the homography with the
most
> support. Is that applicable to your problem and data?
>
> Robin
>
>
> --- In [hidden email], "Ed Elston" <ed.elston@> wrote:
> >
> > My goal is detect planes in 3d data. At this time I haven't
really
> > found a good approach to doing this and I am interested in
suggestions
> > on how to start.
> >
> > My range data is somewhat noisey so I expect that filtering to
smooth
> > this will be required - that is given. Suppose I have very good
data,
> > I still don't have an approach that allows me to segment the
data into
> > regions and then fit an equation to that data which represents a
plane.
> >
> > Thanks, Ed
> >
>


Reply | Threaded
Open this post in threaded view
|

Re: detecting planes in 3D data

get_imaginary
The description of your data helps :)

Planar homographies are a construct in 2D images, and I believe they
would not be directly applicable to your range data. However, ransac
is generic, and you can combine it with Dave Grossman's suggestion.

To do that, you'd pick a random set of points that are the minimum
needed to define a plane (3 3D points). Then take all the other points
(or use a large, randomly selected subset for this step) and count how
many points are "on" that plane. By "on" I mean they are within some
epsilon distance from the computed plane (epsilon is a parameter).
These are called "inliers". After N iterations (N is another
parameter) of random sampling and inlier counting, assume that the
plane with the most inliers is the structure you're looking for.

This works best if the structure you're seeking dominates your data.
In other words, there are a lot of points lying on the plane.

One thing to consider with ransac is numerical stability. You'll need
to select a representation for planes that doesn't have singularities,
that doesn't heavily favor distant points over nearby ones and so on.

HTH,
Robin


--- In [hidden email], "Ed Elston" <ed.elston@...> wrote:

>
> I am evaluating a 3D IR time of flight camera which provides range
> and intensity data in a pair of matching images.  It probably
> appears the same as the output of a stereo pair after reconstruction
> but I'm not that familiar with it.
>
> I am reading about ransac but have no experience with it.  I'm not
> clear on your suggestion about finding the homography with the most
> support ???
>
> Ed
>
> --- In [hidden email], "Robin" <rhewitt@> wrote:
> >
> > Hi Ed,
> >
> > Not sure what you mean by 3d data...? Do you mean you have data
> from a
> > 3d camera (i.e., a range camera), SICK Laser device, or similar?
> >
> > If what you have is two images, the standard technique is to use
> > ransac on candidate point matches to find the homography with the
> most
> > support. Is that applicable to your problem and data?
> >
> > Robin
> >
> >
> > --- In [hidden email], "Ed Elston" <ed.elston@> wrote:
> > >
> > > My goal is detect planes in 3d data. At this time I haven't
> really
> > > found a good approach to doing this and I am interested in
> suggestions
> > > on how to start.
> > >
> > > My range data is somewhat noisey so I expect that filtering to
> smooth
> > > this will be required - that is given. Suppose I have very good
> data,
> > > I still don't have an approach that allows me to segment the
> data into
> > > regions and then fit an equation to that data which represents a
> plane.
> > >
> > > Thanks, Ed
> > >
> >
>


Reply | Threaded
Open this post in threaded view
|

Re: detecting planes in 3D data

Ed Elston
Robin, thanks - that gives me something to go on.  Have you or
anyone heard of HK segmentation?  I'm reading a book
named "Introductory Techniques for 3-D Computer Vision" and in
chapter 4 they introduce this under 4.4 Surface Extraction from
Range Images.  Curious if this applies or any comments about it.  It
appears that the applications are reverse engineering and speed may
not be fast enough.

Another detail on my application, it will eventually be embedded and
our target is to run at 20 Hz or better (hard to do).  So is the
RANSAC a fast method?  In reading it seems that the parameters will
affect the speed greatly.

Ed

--- In [hidden email], "Robin" <rhewitt@...> wrote:
>
> The description of your data helps :)
>
> Planar homographies are a construct in 2D images, and I believe
they
> would not be directly applicable to your range data. However,
ransac
> is generic, and you can combine it with Dave Grossman's suggestion.
>
> To do that, you'd pick a random set of points that are the minimum
> needed to define a plane (3 3D points). Then take all the other
points
> (or use a large, randomly selected subset for this step) and count
how
> many points are "on" that plane. By "on" I mean they are within
some
> epsilon distance from the computed plane (epsilon is a parameter).
> These are called "inliers". After N iterations (N is another
> parameter) of random sampling and inlier counting, assume that the
> plane with the most inliers is the structure you're looking for.
>
> This works best if the structure you're seeking dominates your
data.
> In other words, there are a lot of points lying on the plane.
>
> One thing to consider with ransac is numerical stability. You'll
need
> to select a representation for planes that doesn't have
singularities,
> that doesn't heavily favor distant points over nearby ones and so
on.
>
> HTH,
> Robin
>
>
> --- In [hidden email], "Ed Elston" <ed.elston@> wrote:
> >
> > I am evaluating a 3D IR time of flight camera which provides
range
> > and intensity data in a pair of matching images.  It probably
> > appears the same as the output of a stereo pair after
reconstruction
> > but I'm not that familiar with it.
> >
> > I am reading about ransac but have no experience with it.  I'm
not
> > clear on your suggestion about finding the homography with the
most
> > support ???
> >
> > Ed
> >
> > --- In [hidden email], "Robin" <rhewitt@> wrote:
> > >
> > > Hi Ed,
> > >
> > > Not sure what you mean by 3d data...? Do you mean you have
data
> > from a
> > > 3d camera (i.e., a range camera), SICK Laser device, or
similar?
> > >
> > > If what you have is two images, the standard technique is to
use
> > > ransac on candidate point matches to find the homography with
the

> > most
> > > support. Is that applicable to your problem and data?
> > >
> > > Robin
> > >
> > >
> > > --- In [hidden email], "Ed Elston" <ed.elston@> wrote:
> > > >
> > > > My goal is detect planes in 3d data. At this time I haven't
> > really
> > > > found a good approach to doing this and I am interested in
> > suggestions
> > > > on how to start.
> > > >
> > > > My range data is somewhat noisey so I expect that filtering
to
> > smooth
> > > > this will be required - that is given. Suppose I have very
good
> > data,
> > > > I still don't have an approach that allows me to segment the
> > data into
> > > > regions and then fit an equation to that data which
represents a
> > plane.
> > > >
> > > > Thanks, Ed
> > > >
> > >
> >
>


Reply | Threaded
Open this post in threaded view
|

Re: detecting planes in 3D data

get_imaginary
Hi Ed,

About the HK method, no, I have zero experience with range images. I
imagine there are many specialized techniques, and probably also a
better forum (somewhere) than this one for finding out about them. The
OpenCV libraries are more for 2D images.

Ransac speed and other behaviors are highly data dependent, so I can't
answer about performance in the abstract. If your plane is highly
dominant, it should find it prety fast. If not, I'd suggest you
calculate the number of iterations required based on typical scenarios
for the number of inliers and outliers in your data. My approach in
general is to first find something that works (since that alone can be
very hard), and worry later about making it fast. You can always make
naive ransac faster (and more accurate) by adding domain-specific or
task-specific constraints....

Best of luck with this,
Robin


--- In [hidden email], "Ed Elston" <ed.elston@...> wrote:

>
> Robin, thanks - that gives me something to go on.  Have you or
> anyone heard of HK segmentation?  I'm reading a book
> named "Introductory Techniques for 3-D Computer Vision" and in
> chapter 4 they introduce this under 4.4 Surface Extraction from
> Range Images.  Curious if this applies or any comments about it.  It
> appears that the applications are reverse engineering and speed may
> not be fast enough.
>
> Another detail on my application, it will eventually be embedded and
> our target is to run at 20 Hz or better (hard to do).  So is the
> RANSAC a fast method?  In reading it seems that the parameters will
> affect the speed greatly.
>
> Ed
>
> --- In [hidden email], "Robin" <rhewitt@> wrote:
> >
> > The description of your data helps :)
> >
> > Planar homographies are a construct in 2D images, and I believe
> they
> > would not be directly applicable to your range data. However,
> ransac
> > is generic, and you can combine it with Dave Grossman's suggestion.
> >
> > To do that, you'd pick a random set of points that are the minimum
> > needed to define a plane (3 3D points). Then take all the other
> points
> > (or use a large, randomly selected subset for this step) and count
> how
> > many points are "on" that plane. By "on" I mean they are within
> some
> > epsilon distance from the computed plane (epsilon is a parameter).
> > These are called "inliers". After N iterations (N is another
> > parameter) of random sampling and inlier counting, assume that the
> > plane with the most inliers is the structure you're looking for.
> >
> > This works best if the structure you're seeking dominates your
> data.
> > In other words, there are a lot of points lying on the plane.
> >
> > One thing to consider with ransac is numerical stability. You'll
> need
> > to select a representation for planes that doesn't have
> singularities,
> > that doesn't heavily favor distant points over nearby ones and so
> on.
> >
> > HTH,
> > Robin
> >
> >
> > --- In [hidden email], "Ed Elston" <ed.elston@> wrote:
> > >
> > > I am evaluating a 3D IR time of flight camera which provides
> range
> > > and intensity data in a pair of matching images.  It probably
> > > appears the same as the output of a stereo pair after
> reconstruction
> > > but I'm not that familiar with it.
> > >
> > > I am reading about ransac but have no experience with it.  I'm
> not
> > > clear on your suggestion about finding the homography with the
> most
> > > support ???
> > >
> > > Ed
> > >
> > > --- In [hidden email], "Robin" <rhewitt@> wrote:
> > > >
> > > > Hi Ed,
> > > >
> > > > Not sure what you mean by 3d data...? Do you mean you have
> data
> > > from a
> > > > 3d camera (i.e., a range camera), SICK Laser device, or
> similar?
> > > >
> > > > If what you have is two images, the standard technique is to
> use
> > > > ransac on candidate point matches to find the homography with
> the
> > > most
> > > > support. Is that applicable to your problem and data?
> > > >
> > > > Robin
> > > >
> > > >
> > > > --- In [hidden email], "Ed Elston" <ed.elston@> wrote:
> > > > >
> > > > > My goal is detect planes in 3d data. At this time I haven't
> > > really
> > > > > found a good approach to doing this and I am interested in
> > > suggestions
> > > > > on how to start.
> > > > >
> > > > > My range data is somewhat noisey so I expect that filtering
> to
> > > smooth
> > > > > this will be required - that is given. Suppose I have very
> good
> > > data,
> > > > > I still don't have an approach that allows me to segment the
> > > data into
> > > > > regions and then fit an equation to that data which
> represents a
> > > plane.
> > > > >
> > > > > Thanks, Ed
> > > > >
> > > >
> > >
> >
>


Reply | Threaded
Open this post in threaded view
|

Re: detecting planes in 3D data

Ed Elston
Thanks, one last question - where do I find an implementation of
this in OpenCV?  So far, I can't locate it.

Ed

--- In [hidden email], "Robin" <rhewitt@...> wrote:
>
> Hi Ed,
>
> About the HK method, no, I have zero experience with range images.
I
> imagine there are many specialized techniques, and probably also a
> better forum (somewhere) than this one for finding out about them.
The
> OpenCV libraries are more for 2D images.
>
> Ransac speed and other behaviors are highly data dependent, so I
can't
> answer about performance in the abstract. If your plane is highly
> dominant, it should find it prety fast. If not, I'd suggest you
> calculate the number of iterations required based on typical
scenarios
> for the number of inliers and outliers in your data. My approach in
> general is to first find something that works (since that alone
can be
> very hard), and worry later about making it fast. You can always
make
> naive ransac faster (and more accurate) by adding domain-specific
or

> task-specific constraints....
>
> Best of luck with this,
> Robin
>
>
> --- In [hidden email], "Ed Elston" <ed.elston@> wrote:
> >
> > Robin, thanks - that gives me something to go on.  Have you or
> > anyone heard of HK segmentation?  I'm reading a book
> > named "Introductory Techniques for 3-D Computer Vision" and in
> > chapter 4 they introduce this under 4.4 Surface Extraction from
> > Range Images.  Curious if this applies or any comments about
it.  It
> > appears that the applications are reverse engineering and speed
may
> > not be fast enough.
> >
> > Another detail on my application, it will eventually be embedded
and
> > our target is to run at 20 Hz or better (hard to do).  So is the
> > RANSAC a fast method?  In reading it seems that the parameters
will
> > affect the speed greatly.
> >
> > Ed
> >
> > --- In [hidden email], "Robin" <rhewitt@> wrote:
> > >
> > > The description of your data helps :)
> > >
> > > Planar homographies are a construct in 2D images, and I
believe
> > they
> > > would not be directly applicable to your range data. However,
> > ransac
> > > is generic, and you can combine it with Dave Grossman's
suggestion.
> > >
> > > To do that, you'd pick a random set of points that are the
minimum
> > > needed to define a plane (3 3D points). Then take all the
other
> > points
> > > (or use a large, randomly selected subset for this step) and
count
> > how
> > > many points are "on" that plane. By "on" I mean they are
within
> > some
> > > epsilon distance from the computed plane (epsilon is a
parameter).
> > > These are called "inliers". After N iterations (N is another
> > > parameter) of random sampling and inlier counting, assume that
the
> > > plane with the most inliers is the structure you're looking
for.
> > >
> > > This works best if the structure you're seeking dominates your
> > data.
> > > In other words, there are a lot of points lying on the plane.
> > >
> > > One thing to consider with ransac is numerical stability.
You'll
> > need
> > > to select a representation for planes that doesn't have
> > singularities,
> > > that doesn't heavily favor distant points over nearby ones and
so

> > on.
> > >
> > > HTH,
> > > Robin
> > >
> > >
> > > --- In [hidden email], "Ed Elston" <ed.elston@> wrote:
> > > >
> > > > I am evaluating a 3D IR time of flight camera which provides
> > range
> > > > and intensity data in a pair of matching images.  It
probably
> > > > appears the same as the output of a stereo pair after
> > reconstruction
> > > > but I'm not that familiar with it.
> > > >
> > > > I am reading about ransac but have no experience with it.  
I'm
> > not
> > > > clear on your suggestion about finding the homography with
the

> > most
> > > > support ???
> > > >
> > > > Ed
> > > >
> > > > --- In [hidden email], "Robin" <rhewitt@> wrote:
> > > > >
> > > > > Hi Ed,
> > > > >
> > > > > Not sure what you mean by 3d data...? Do you mean you have
> > data
> > > > from a
> > > > > 3d camera (i.e., a range camera), SICK Laser device, or
> > similar?
> > > > >
> > > > > If what you have is two images, the standard technique is
to
> > use
> > > > > ransac on candidate point matches to find the homography
with
> > the
> > > > most
> > > > > support. Is that applicable to your problem and data?
> > > > >
> > > > > Robin
> > > > >
> > > > >
> > > > > --- In [hidden email], "Ed Elston" <ed.elston@>
wrote:
> > > > > >
> > > > > > My goal is detect planes in 3d data. At this time I
haven't
> > > > really
> > > > > > found a good approach to doing this and I am interested
in
> > > > suggestions
> > > > > > on how to start.
> > > > > >
> > > > > > My range data is somewhat noisey so I expect that
filtering
> > to
> > > > smooth
> > > > > > this will be required - that is given. Suppose I have
very
> > good
> > > > data,
> > > > > > I still don't have an approach that allows me to segment
the

> > > > data into
> > > > > > regions and then fit an equation to that data which
> > represents a
> > > > plane.
> > > > > >
> > > > > > Thanks, Ed
> > > > > >
> > > > >
> > > >
> > >
> >
>


Reply | Threaded
Open this post in threaded view
|

Re: detecting planes in 3D data

get_imaginary
Oh, there may not be a generic implementation. Since the algorithm is
so simple, and nearly all the work is structure- and context-specific,
it's usually just inlined. (For example, ransac for computing
homographies will have homography calcs and degeneracy checks embedded
in it.) Sorry! But maybe someone else knows otherwise...?

Best,
Robin


--- In [hidden email], "Ed Elston" <ed.elston@...> wrote:

>
> Thanks, one last question - where do I find an implementation of
> this in OpenCV?  So far, I can't locate it.
>
> Ed
>
> --- In [hidden email], "Robin" <rhewitt@> wrote:
> >
> > Hi Ed,
> >
> > About the HK method, no, I have zero experience with range images.
> I
> > imagine there are many specialized techniques, and probably also a
> > better forum (somewhere) than this one for finding out about them.
> The
> > OpenCV libraries are more for 2D images.
> >
> > Ransac speed and other behaviors are highly data dependent, so I
> can't
> > answer about performance in the abstract. If your plane is highly
> > dominant, it should find it prety fast. If not, I'd suggest you
> > calculate the number of iterations required based on typical
> scenarios
> > for the number of inliers and outliers in your data. My approach in
> > general is to first find something that works (since that alone
> can be
> > very hard), and worry later about making it fast. You can always
> make
> > naive ransac faster (and more accurate) by adding domain-specific
> or
> > task-specific constraints....
> >
> > Best of luck with this,
> > Robin
> >
> >
> > --- In [hidden email], "Ed Elston" <ed.elston@> wrote:
> > >
> > > Robin, thanks - that gives me something to go on.  Have you or
> > > anyone heard of HK segmentation?  I'm reading a book
> > > named "Introductory Techniques for 3-D Computer Vision" and in
> > > chapter 4 they introduce this under 4.4 Surface Extraction from
> > > Range Images.  Curious if this applies or any comments about
> it.  It
> > > appears that the applications are reverse engineering and speed
> may
> > > not be fast enough.
> > >
> > > Another detail on my application, it will eventually be embedded
> and
> > > our target is to run at 20 Hz or better (hard to do).  So is the
> > > RANSAC a fast method?  In reading it seems that the parameters
> will
> > > affect the speed greatly.
> > >
> > > Ed
> > >
> > > --- In [hidden email], "Robin" <rhewitt@> wrote:
> > > >
> > > > The description of your data helps :)
> > > >
> > > > Planar homographies are a construct in 2D images, and I
> believe
> > > they
> > > > would not be directly applicable to your range data. However,
> > > ransac
> > > > is generic, and you can combine it with Dave Grossman's
> suggestion.
> > > >
> > > > To do that, you'd pick a random set of points that are the
> minimum
> > > > needed to define a plane (3 3D points). Then take all the
> other
> > > points
> > > > (or use a large, randomly selected subset for this step) and
> count
> > > how
> > > > many points are "on" that plane. By "on" I mean they are
> within
> > > some
> > > > epsilon distance from the computed plane (epsilon is a
> parameter).
> > > > These are called "inliers". After N iterations (N is another
> > > > parameter) of random sampling and inlier counting, assume that
> the
> > > > plane with the most inliers is the structure you're looking
> for.
> > > >
> > > > This works best if the structure you're seeking dominates your
> > > data.
> > > > In other words, there are a lot of points lying on the plane.
> > > >
> > > > One thing to consider with ransac is numerical stability.
> You'll
> > > need
> > > > to select a representation for planes that doesn't have
> > > singularities,
> > > > that doesn't heavily favor distant points over nearby ones and
> so
> > > on.
> > > >
> > > > HTH,
> > > > Robin
> > > >
> > > >
> > > > --- In [hidden email], "Ed Elston" <ed.elston@> wrote:
> > > > >
> > > > > I am evaluating a 3D IR time of flight camera which provides
> > > range
> > > > > and intensity data in a pair of matching images.  It
> probably
> > > > > appears the same as the output of a stereo pair after
> > > reconstruction
> > > > > but I'm not that familiar with it.
> > > > >
> > > > > I am reading about ransac but have no experience with it.  
> I'm
> > > not
> > > > > clear on your suggestion about finding the homography with
> the
> > > most
> > > > > support ???
> > > > >
> > > > > Ed
> > > > >
> > > > > --- In [hidden email], "Robin" <rhewitt@> wrote:
> > > > > >
> > > > > > Hi Ed,
> > > > > >
> > > > > > Not sure what you mean by 3d data...? Do you mean you have
> > > data
> > > > > from a
> > > > > > 3d camera (i.e., a range camera), SICK Laser device, or
> > > similar?
> > > > > >
> > > > > > If what you have is two images, the standard technique is
> to
> > > use
> > > > > > ransac on candidate point matches to find the homography
> with
> > > the
> > > > > most
> > > > > > support. Is that applicable to your problem and data?
> > > > > >
> > > > > > Robin
> > > > > >
> > > > > >
> > > > > > --- In [hidden email], "Ed Elston" <ed.elston@>
> wrote:
> > > > > > >
> > > > > > > My goal is detect planes in 3d data. At this time I
> haven't
> > > > > really
> > > > > > > found a good approach to doing this and I am interested
> in
> > > > > suggestions
> > > > > > > on how to start.
> > > > > > >
> > > > > > > My range data is somewhat noisey so I expect that
> filtering
> > > to
> > > > > smooth
> > > > > > > this will be required - that is given. Suppose I have
> very
> > > good
> > > > > data,
> > > > > > > I still don't have an approach that allows me to segment
> the
> > > > > data into
> > > > > > > regions and then fit an equation to that data which
> > > represents a
> > > > > plane.
> > > > > > >
> > > > > > > Thanks, Ed
> > > > > > >
> > > > > >
> > > > >
> > > >
> > >
> >
>