1
\$\begingroup\$

I have the following code that does the resizing of a 1D vector with nearest neighbor interpolation in a similar fashion you'd also resize an image, only in 1D rather than 2D. Another term would be resampling, but there seems to be a lot of confusion around these terms (resampling is also a technique in statistics), so I prefer to be more descriptive.

Currently the code looks like this and I need to optimize it:

inline void resizeNearestNeighbor(const int16_t* current, uint32_t currentSize, int16_t* out, uint32_t newSize, uint32_t offset = 0u)
{
    if(currentSize == newSize)
    {
        return;
    }

    const float scaleFactor = static_cast<float>(currentSize) / static_cast<float>(newSize);
    for(uint32_t outIdx = 0; outIdx<newSize; ++outIdx)
    {
        const int currentIdx = static_cast<uint32_t>(outIdx * scaleFactor);
        out[outIdx] = current[(currentIdx + offset)%currentSize];
    }
}

You can ignore the offset in the function above - it's there because the item being resized is a ring buffer which can vary its length (by shortening head or tail).

I saw there's a group of functions designated for linear interpolation in CMSIS DSP library by Keil and perhaps there's also something that would fulfill this example as well and speed it up in the library. Unfortunately I'm unable to understand the provided example with the sine...

Do you know what would be the most efficient way of realizing the above function on this platform (can also use any form of interpolation and not just nearest neighbor)?

\$\endgroup\$
1
  • \$\begingroup\$ Much of the runtime is probably the modulus operator since that will require division, while everything else is pretty simple. Before you try other libraries, remove that and see if it's fast enough. \$\endgroup\$ May 16 at 11:33

1 Answer 1

2
\$\begingroup\$

This really belongs on Code Review.

But if it's the floating-point math that's slowing you down, you might consider a variation of Bresenham's Algorithm:

inline void resizeNearestNeighbor (
  const int16_t* current,
  uint32_t currentSize,
  int16_t* out,
  uint32_t newSize,
  uint32_t offset = 0u)
{
  /* Pre-load fraction with half the limit to get correct rounding */
  uint32_t fraction = newSize;
  const uint32_t incr = currentSize * 2;
  const uint32_t limit = newSize * 2;
  uint32_t currentIdx = 0;
  for (uint32_t outIdx = 0; outIdx < newSize; ++outIdx) {
    out[outIdx] = current[(currentIdx + offset)%currentSize];
    fraction += incr;
#if 1
    /* Use this if integer div and mod are fast */
    currentIdx += fraction / limit;
    fraction = faction % limit;
#else
    /* Otherwise, use this */
    while (fraction >= limit) {
      fraction -= limit;
      ++currentIdx;
    }
#endif
  }
}
\$\endgroup\$
5
  • \$\begingroup\$ This is a really brilliant solution! How could this not come to my mind before despite me knowing the algorithm! Thank you so much! The other improvement might be to get rid of the modulo and do this in two batches. Thanks again! \$\endgroup\$ May 16 at 11:44
  • 1
    \$\begingroup\$ Yes, well, I spent a few months of my life figuring out how to do this kind of image resampling in real time at HD resolution in an FPGA. So it's a topic near and dear to my heart! \$\endgroup\$
    – Dave Tweed
    May 16 at 11:47
  • \$\begingroup\$ The beauty of this solution is that it avoids a lot of expensive divisions - I love it! Even with FPU, the integer solution is much faster actually, at least on most platforms I know of! \$\endgroup\$ May 16 at 11:50
  • \$\begingroup\$ Note: I fixed a typo in the #else section. \$\endgroup\$
    – Dave Tweed
    May 16 at 11:59
  • 1
    \$\begingroup\$ Thanks. I am still not closing it, because perhaps someone knowledgable in Cortex M7 or CMSIS comes with a solution that can make use of vectorization, perhaps combining it into your suggestion. \$\endgroup\$ May 16 at 12:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.