Hello Assume we want to implement an optimal photographic image interpolation algorithm. Using a recommended windowed sinc algorithm (e.g., Lanczos) would require evaluation of the sinc function (sin(x)/x) at variable arguments. Now I have an alternative algorithm which only requires evaluation of cosine values and multiplication, no variable division. Would this be advantageous on DSP architectures? I recall from prior DSP experiences that variable division is relatively expensive and better avoided in favor of multiplication. Can you confirm this opinion? Regards Guido
Question to DSP adepts
Started by ●January 7, 2004
Reply by ●January 7, 20042004-01-07
Guido Vollbeding <guido@jpegclub.org> wrote in news:3FFBF893.4AE2D0B4 @jpegclub.org:> Hello > > Assume we want to implement an optimal photographic image interpolation > algorithm. > Using a recommended windowed sinc algorithm (e.g., Lanczos) wouldrequire> evaluation of the sinc function (sin(x)/x) at variable arguments. > Now I have an alternative algorithm which only requires evaluation of > cosine values and multiplication, no variable division. Would this be > advantageous on DSP architectures? > I recall from prior DSP experiences that variable division isrelatively> expensive and better avoided in favor of multiplication. > Can you confirm this opinion? > > Regards > Guido >Yes, division is usually expensive on a DSP. I think it is about 8 cycles on a Sharc and about 1 cycle per bit on a 21xx. -- Al Clark Danville Signal Processing, Inc. -------------------------------------------------------------------- Purveyors of Fine DSP Hardware and other Cool Stuff Available at http://www.danvillesignal.com
Reply by ●January 7, 20042004-01-07
Al Clark wrote:> > Yes, division is usually expensive on a DSP. I think it is about 8 cycles > on a Sharc and about 1 cycle per bit on a 21xx.Thanks, I need some arguments for going the alternative path... Regards Guido
Reply by ●January 7, 20042004-01-07
"Guido Vollbeding" <guido@jpegclub.org> wrote in message news:3FFBF893.4AE2D0B4@jpegclub.org...> Hello > > Assume we want to implement an optimal photographic image interpolation > algorithm. > Using a recommended windowed sinc algorithm (e.g., Lanczos) would require > evaluation of the sinc function (sin(x)/x) at variable arguments. > Now I have an alternative algorithm which only requires evaluation of > cosine values and multiplication, no variable division. Would this be > advantageous on DSP architectures? > I recall from prior DSP experiences that variable division is relatively > expensive and better avoided in favor of multiplication. > Can you confirm this opinion?Guido, Google on "detect fundamental frequency", the first hit looks interesting: http://www2.cs.uregina.ca/~gerhard/publications/TRdbg-Pitch.pdf and there are many others that are particularly pertinent. Cepstral processing has been used in speech to separate the fundamental frequency of the exitation from other aspects of the vocal tract response. If you consider a neural net then you need to decide what goes into it. An array of samples? An array of delayed samples so they coincide in time? That is, delay the oldest sample so that it arrives at the input at the same time as the newest sample? I don't know .... not something I've done. Fred
Reply by ●January 7, 20042004-01-07
Hello Guido, Actually in many cases "optimal" image interpolation involves a nonlinear process. Yes I know this is unlike interpolating with sinc functions, but many papers have been written on this. Google on "demosaicing" and "Bayer" and "gradient" simultaneously and read there. What is mathematically correct from the WKS sampling theory needs to incorporate the nonlinearity of the visual process. Clay "Guido Vollbeding" <guido@jpegclub.org> wrote in message news:3FFBF893.4AE2D0B4@jpegclub.org...> Hello > > Assume we want to implement an optimal photographic image interpolation > algorithm. > Using a recommended windowed sinc algorithm (e.g., Lanczos) would require > evaluation of the sinc function (sin(x)/x) at variable arguments. > Now I have an alternative algorithm which only requires evaluation of > cosine values and multiplication, no variable division. Would this be > advantageous on DSP architectures? > I recall from prior DSP experiences that variable division is relatively > expensive and better avoided in favor of multiplication. > Can you confirm this opinion? > > Regards > Guido
Reply by ●January 7, 20042004-01-07
Hello Guido, Actually in many cases "optimal" image interpolation involves a nonlinear process. Yes I know this is unlike interpolating with sinc functions, but many papers have been written on this. Google on "demosaicing" and "Bayer" and "gradient" simultaneously and read there. What is mathematically correct from the WKS sampling theory needs to incorporate the nonlinearity of the visual process. Clay "Guido Vollbeding" <guido@jpegclub.org> wrote in message news:3FFBF893.4AE2D0B4@jpegclub.org...> Hello > > Assume we want to implement an optimal photographic image interpolation > algorithm. > Using a recommended windowed sinc algorithm (e.g., Lanczos) would require > evaluation of the sinc function (sin(x)/x) at variable arguments. > Now I have an alternative algorithm which only requires evaluation of > cosine values and multiplication, no variable division. Would this be > advantageous on DSP architectures? > I recall from prior DSP experiences that variable division is relatively > expensive and better avoided in favor of multiplication. > Can you confirm this opinion? > > Regards > Guido
Reply by ●January 7, 20042004-01-07
Fred Marshall wrote:> "Guido Vollbeding" <guido@jpegclub.org> wrote in message > news:3FFBF893.4AE2D0B4@jpegclub.org... > >>Hello >> >>Assume we want to implement an optimal photographic image interpolation >>algorithm. >>Using a recommended windowed sinc algorithm (e.g., Lanczos) would require >>evaluation of the sinc function (sin(x)/x) at variable arguments. >>Now I have an alternative algorithm which only requires evaluation of >>cosine values and multiplication, no variable division. Would this be >>advantageous on DSP architectures? >>I recall from prior DSP experiences that variable division is relatively >>expensive and better avoided in favor of multiplication. >>Can you confirm this opinion? > > > Guido, > > Google on "detect fundamental frequency", the first hit looks interesting: > > http://www2.cs.uregina.ca/~gerhard/publications/TRdbg-Pitch.pdf > > and there are many others that are particularly pertinent. > Cepstral processing has been used in speech to separate the fundamental > frequency of the exitation from other aspects of the vocal tract response. > > If you consider a neural net then you need to decide what goes into it. An > array of samples? An array of delayed samples so they coincide in time? > That is, delay the oldest sample so that it arrives at the input at the same > time as the newest sample? I don't know .... not something I've done. > > FredFred, Is this in the right thread? Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
Reply by ●January 7, 20042004-01-07
"Jerry Avins" <jya@ieee.org> wrote in message news:3ffc6409$0$6761$61fed72c@news.rcn.com...> Fred Marshall wrote: > > > "Guido Vollbeding" <guido@jpegclub.org> wrote in message > > news:3FFBF893.4AE2D0B4@jpegclub.org... > > > >>Hello > >> > >>Assume we want to implement an optimal photographic image interpolation > >>algorithm. > >>Using a recommended windowed sinc algorithm (e.g., Lanczos) wouldrequire> >>evaluation of the sinc function (sin(x)/x) at variable arguments. > >>Now I have an alternative algorithm which only requires evaluation of > >>cosine values and multiplication, no variable division. Would this be > >>advantageous on DSP architectures? > >>I recall from prior DSP experiences that variable division is relatively > >>expensive and better avoided in favor of multiplication. > >>Can you confirm this opinion? > > > > > > Guido, > > > > Google on "detect fundamental frequency", the first hit looksinteresting:> > > > http://www2.cs.uregina.ca/~gerhard/publications/TRdbg-Pitch.pdf > > > > and there are many others that are particularly pertinent. > > Cepstral processing has been used in speech to separate the fundamental > > frequency of the exitation from other aspects of the vocal tractresponse.> > > > If you consider a neural net then you need to decide what goes into it.An> > array of samples? An array of delayed samples so they coincide in time? > > That is, delay the oldest sample so that it arrives at the input at thesame> > time as the newest sample? I don't know .... not something I've done. > > > > Fred > > Fred, > > Is this in the right thread? > > JerryJerry, Nope! Thanks - I was afraid I'd done that.... Fred
Reply by ●January 8, 20042004-01-08
Hello Clay Thanks for your comment. Actually the sampling theory recommendation *does* give the best results in practice, though it is seldom used due to high computational effort. See for example http://www.path.unimelb.edu.au/~dersch/interpolator/interpolator.html But I have found another interpolation algorithm which is based on the Discrete Cosine Transformation as used in JPEG which seems to give similar good results and possibly computational advantages. Regards Guido
Reply by ●January 8, 20042004-01-08
Guido Vollbeding wrote:> Hello > > Assume we want to implement an optimal photographic image interpolation > algorithm. > Using a recommended windowed sinc algorithm (e.g., Lanczos) would require > evaluation of the sinc function (sin(x)/x) at variable arguments.I think you may be missing something. Depending on exactly how you are applying interpolation you should only need to calculate a finite set of coefficients once for a particular task. Applying these coefficients to your image is just a small number of integer multiply/adds per pixel. Of course I may have misunderstood the problem - maybe you want to dynamically interpolate by some varying amount across the image ? But even then, for pixel data you would still only need a relatively small table of interpolation coefficients which could be precomputed. Paul
