convolution versus PDE

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
5 messages Options
Reply | Threaded
Open this post in threaded view
|

convolution versus PDE

Martin du Saire
Hi,

This may be off topic but hopefully you won't mind too much:  I
recently "discovered" that many convolution operations can be
performed using partial differential equations, quite often some form
of the heat equation.  Is there some advantage to this, and when
would this be an appropriate route to take?

Thanks.

Martin
Reply | Threaded
Open this post in threaded view
|

Re: convolution versus PDE

Duane and Julie
On Jul 27, 2006, at 9:31 AM, Martin du Saire wrote:

> Hi,
>
> This may be off topic but hopefully you won't mind too much:  I  
> recently "discovered" that many convolution operations can be  
> performed using partial differential equations, quite often some  
> form of the heat equation.  Is there some advantage to this, and  
> when would this be an appropriate route to take?
>
> Thanks.
>
> Martin

Convolutions are closed form.  PDEs are solved using an iterative  
process (in my experience), during which you have to decide when  
you've reached an answer that is good enough or has quit changing.

I can't imagine how solving a PDE could be quicker than doing a  
convolution.  I don't see a real difference in answers.  I'm trying  
to come up with a reason to use PDEs over convolution, but I'm having  
a hard time.

Perhaps if the convolution kernel is quite large, and you are willing  
to have an approximate answer to avoid having to worry about padding  
and/or edge effects?

    duane
Reply | Threaded
Open this post in threaded view
|

Antwort: Re: convolution versus PDE

Joachim Wesner
Hi

I´d mostly second this, for small kernels direct convolutions are surely
the quickest way (besides any edge/padding problems)

Convolutions (especially for large kernels) and PDEs can also both be
solved effectively by FFT methods, which however (might) have (depending on
your
problem) their own edge/padding/periodicity quirks. Those spectral methods
are often prefered because of their more "smoother", "global" solutions,
also because even multidimensional FFTs can be calculated pretty quickly on
today's computers.

See for ex.

http://www.pma.caltech.edu/~physlab/ph22_spring06/assgmt-4.pdf

It all depends....!?



                                                                                                                                       
                      Duane & Julie                                                                                                    
                      <vonschwartzwald         An:      [hidden email]                                                            
                      [hidden email]>              Kopie:                                                                                  
                      Gesendet von:            Thema:   Re: convolution versus PDE                                                    
                      ImageJ Interest                                                                                                  
                      Group                                                                                                            
                      <[hidden email]                                                                                                
                      .GOV>                                                                                                            
                                                                                                                                       
                                                                                                                                       
                      29.07.2006 19:07                                                                                                
                      Bitte antworten                                                                                                  
                      an ImageJ                                                                                                        
                      Interest Group                                                                                                  
                                                                                                                                       




On Jul 27, 2006, at 9:31 AM, Martin du Saire wrote:

> Hi,
>
> This may be off topic but hopefully you won't mind too much:  I
> recently "discovered" that many convolution operations can be
> performed using partial differential equations, quite often some
> form of the heat equation.  Is there some advantage to this, and
> when would this be an appropriate route to take?
>
> Thanks.
>
> Martin

Convolutions are closed form.  PDEs are solved using an iterative
process (in my experience), during which you have to decide when
you've reached an answer that is good enough or has quit changing.

I can't imagine how solving a PDE could be quicker than doing a
convolution.  I don't see a real difference in answers.  I'm trying
to come up with a reason to use PDEs over convolution, but I'm having
a hard time.

Perhaps if the convolution kernel is quite large, and you are willing
to have an approximate answer to avoid having to worry about padding
and/or edge effects?

    duane



______________________________________________________________________
This email has been scanned by the MessageLabs Email Security System.
For more information please visit http://www.messagelabs.com/email 
______________________________________________________________________
Reply | Threaded
Open this post in threaded view
|

Re: convolution versus PDE

Robert Dougherty
In reply to this post by Duane and Julie
My experience is that there are occasions when the image can be viewed as an
initial condition to a PDE, and you effectively want the solution as a
function of time.  You can either model the direct PDE solution process time
by time, or use a convolution expression to essentially apply the Green's
function to express the solution at each time in terms of the starting
image.  For small time steps, the evolution operator, which is approximated
as a local operator, can be a lot cheaper than the convolution.  An example
is modeling a range of Gaussian blurs.  To get from one degree of blur to
the next, the PDE approach is to solve the heat equation over a short time
interval using a finite difference formulation in time and space.  You need
to make the time step short enough for stability, of course.

Bob

Robert P. Dougherty, Ph.D.
President, OptiNav, Inc.
Phone (425) 467-1118
Fax (425) 467-1119
www.optinav.com
 

> -----Original Message-----
> From: ImageJ Interest Group [mailto:[hidden email]] On Behalf Of
> Duane & Julie
> Sent: Saturday, July 29, 2006 10:07 AM
> To: [hidden email]
> Subject: Re: convolution versus PDE
>
> On Jul 27, 2006, at 9:31 AM, Martin du Saire wrote:
>
> > Hi,
> >
> > This may be off topic but hopefully you won't mind too much:  I
> > recently "discovered" that many convolution operations can be
> > performed using partial differential equations, quite often some
> > form of the heat equation.  Is there some advantage to this, and
> > when would this be an appropriate route to take?
> >
> > Thanks.
> >
> > Martin
>
> Convolutions are closed form.  PDEs are solved using an iterative
> process (in my experience), during which you have to decide when
> you've reached an answer that is good enough or has quit changing.
>
> I can't imagine how solving a PDE could be quicker than doing a
> convolution.  I don't see a real difference in answers.  I'm trying
> to come up with a reason to use PDEs over convolution, but I'm having
> a hard time.
>
> Perhaps if the convolution kernel is quite large, and you are willing
> to have an approximate answer to avoid having to worry about padding
> and/or edge effects?
>
>     duane
Reply | Threaded
Open this post in threaded view
|

A Better Way to Threshold Vehicle Object?

Michael Ji
In reply to this post by Duane and Julie
hi there,

I tried tools in imageJ, such as auto-threshold,
background substract, etc. to threshold vehicle object
from image.

Since the vehicle object itself isn't cosnsistently
shaded, the result of threshold process is not
perfect---that the object is not with continuous
outline.

I wonder if there is other better way to extract such
object more efficiently and more accurately? or I need
to go further deeper to code particular Java algorithm
to deal with pixel directly?

http://transportation-michael.blogspot.com/

From the link, you could see the original image in the
bottom and result after thresholding at the top,

thanks your time,

Michael,


__________________________________________________
Do You Yahoo!?
Tired of spam?  Yahoo! Mail has the best spam protection around
http://mail.yahoo.com