#85 Minor issues in Resize resulting in lost performance

None
closed
Hervé Drolon
None
5
2015-02-01
2013-10-15
Anonymous
No

I was digging into the Resize code (the weight generation, more specifically) and I noticed two issues.

-First the zero trimming, at the end of the weight generation, is incorrectly placed
behind the (dTotalWeight > 0) && (dTotalWeight != 1) test, which leads that zeros are not trimmed if the combined weight is 1.

-Second issue is more severe. I noticed there are always some zeros in the table! One leading and one trailing. For every filter.

After spending a day comparing the original ('89) code with the current impl. it turned out there are some subtle differences in how the samples are created and accessed. I took the time and ported the 89 code to the curr. impl. and suddenly - the zeros were gone!

Needles to say eliminating the two zeros automatically boosted the performance for every filter to some degree. The simpler the filter - the greater the performance gain, because they use fewer samples.

In general the problem was that the range of samples was too wide (the iLeft to iRight range), not only it was too wide on its own, but it was sampled including the iRight (the last) where the original states explicitly that the range is last-1.

Below is copy-paste ready fixed version of the weight generation function.

One important note for a full implementation:
The rest of the code in Resize must be ported to sample until i < iRight, where before it sampled until i <= iRight, when applying the weights to the source pixels! Otherwise there will be a crash, obviously.

CWeightsTable::CWeightsTable(CGenericFilter *pFilter, unsigned uDstSize, unsigned uSrcSize) {
  unsigned u;
  double dWidth;
  double dFScale = 1.0;
  const double dFilterWidth = pFilter->GetWidth();

  // scale factor
  const double dScale = double(uDstSize) / double(uSrcSize);

  if(dScale < 1.0) {
    // minification
    dWidth = dFilterWidth / dScale;
    dFScale = dScale;
  } else {
    // magnification
    dWidth= dFilterWidth;
  }

  // allocate a new line contributions structure
  //
  // window size is the number of sampled pixels
  m_WindowSize = 2 * (int)ceil(dWidth);
  m_LineLength = uDstSize;
   // allocate list of contributions
  m_WeightTable = (Contribution*)malloc(m_LineLength * sizeof(Contribution));
  for(u = 0 ; u < m_LineLength ; u++) {
    // allocate contributions for every pixel
    m_WeightTable[u].Weights = (double*)malloc(m_WindowSize * sizeof(double));
  }

  // offset for discrete to continuous coordinate conversion
  const double dOffset = (0.5 / dScale);

  for(u = 0; u < m_LineLength; u++) {
    // scan through line of contributions
    const double dCenter = (double)u / dScale + dOffset;   // inverse mapping (discrte dst 'u' to continous src 'dCenter')
    // find the significant edge points that affect the pixel
    int iLeft = MAX (0, (int) (dCenter - dWidth + .5));
    int iRight = MIN ((int) (dCenter + dWidth + .5), int(uSrcSize));

    // cut edge points to fit in filter window in case of spill-off (not needed any more)
//      if((iRight - iLeft + 1) > int(m_WindowSize)) {
//          if(iLeft < (int(uSrcSize) - 1 / 2)) {
//              iLeft++;
//          } else {
//              iRight--;
//          }
//      }

    m_WeightTable[u].Left = iLeft;
    m_WeightTable[u].Right = iRight;

    int iSrc = 0;
    double dTotalWeight = 0;  // zero sum of weights
    for(iSrc = iLeft; iSrc < iRight; iSrc++) {
      // calculate weights
      const double weight = dFScale * pFilter->Filter(dFScale * ((double)iSrc +.5 - dCenter));
      m_WeightTable[u].Weights[iSrc-iLeft] = weight;
      dTotalWeight += weight;
    }

    if((dTotalWeight > 0) && (dTotalWeight != 1)) {
      // normalize weight of neighbouring points
      for(iSrc = iLeft; iSrc < iRight; iSrc++) {
        // normalize point
        m_WeightTable[u].Weights[iSrc-iLeft] /= dTotalWeight;
      }
    }

      // simplify the filter, discarding null weights at the right
      iSrc = iRight - iLeft - 1;
      while(m_WeightTable[u].Weights[iSrc] == 0){
        m_WeightTable[u].Right--;
        iSrc--;
        if(m_WeightTable[u].Right == m_WeightTable[u].Left){
          break;
        }
      }

   }
}

Discussion

  • Hervé Drolon
    Hervé Drolon
    2013-11-19

    Hi Mihail,

    Thanks for this patch, it is now commited to the CVS.
    I also noticed that this patch improves the spatial accuracy of the filters.

    Hervé

     


Anonymous


Cancel   Add attachments