GPUImage框架中的样条插值算法

Question

我最近使用GPUImage框架（[=24=]GPUImageToneCurveFilter）读取Adobe acv文件并生成着色器纹理的LUT。在成功使用此实用程序在我的图像中呈现自定义色调后，我很好奇使用了哪种样条插值算法来实现这一点。在示例代码中，我可以发现有一些二阶导数计算。但是我不明白数学参数是从哪里来的。能否告诉我一些进一步插值研究的理论参考？谢谢。

[编辑]

正如Spektre在下面提到的，我将样条计算的代码粘贴在GPUImageToneCurveFilter.m中。这是 Objective-C 版本。

从ACV文件中获取控制点并将它们从(0, 1)转换为(0, 255)后，将这些点发送到splineCurve函数进行插值，如下所示：

NSMutableArray *splinePoints = [self splineCurve:convertedPoints];

两个插值函数为：

- (NSMutableArray *)splineCurve:(NSArray *)points
{
    NSMutableArray *sdA = [self secondDerivative:points];

    // [points count] is equal to [sdA count]
    NSInteger n = [sdA count];
    if (n < 1)
    {
        return nil;
    }
    double sd[n];

    // From NSMutableArray to sd[n];
    for (int i=0; i<n; i++) 
    {
        sd[i] = [[sdA objectAtIndex:i] doubleValue];
    }


    NSMutableArray *output = [NSMutableArray arrayWithCapacity:(n+1)];

    for(int i=0; i<n-1 ; i++) 
    {
#if TARGET_IPHONE_SIMULATOR || TARGET_OS_IPHONE
        CGPoint cur = [[points objectAtIndex:i] CGPointValue];
        CGPoint next = [[points objectAtIndex:(i+1)] CGPointValue];
#else
        NSPoint cur = [[points objectAtIndex:i] pointValue];
        NSPoint next = [[points objectAtIndex:(i+1)] pointValue];
#endif

        for(int x=cur.x;x<(int)next.x;x++) 
        {
            double t = (double)(x-cur.x)/(next.x-cur.x);

            double a = 1-t;
            double b = t;
            double h = next.x-cur.x;

            double y= a*cur.y + b*next.y + (h*h/6)*( (a*a*a-a)*sd[i]+ (b*b*b-b)*sd[i+1] );

            if (y > 255.0)
            {
                y = 255.0;   
            }
            else if (y < 0.0)
            {
                y = 0.0;   
            }
#if TARGET_IPHONE_SIMULATOR || TARGET_OS_IPHONE
            [output addObject:[NSValue valueWithCGPoint:CGPointMake(x, y)]];
#else
            [output addObject:[NSValue valueWithPoint:NSMakePoint(x, y)]];
#endif
        }
    }

    // The above always misses the last point because the last point is the last next, so we approach but don't equal it.
    [output addObject:[points lastObject]];
    return output;
}

- (NSMutableArray *)secondDerivative:(NSArray *)points
{
    const NSInteger n = [points count];
    if ((n <= 0) || (n == 1))
    {
        return nil;
    }

    double matrix[n][3];
    double result[n];
    matrix[0][1]=1;
    // What about matrix[0][1] and matrix[0][0]? Assuming 0 for now (Brad L.)
    matrix[0][0]=0;    
    matrix[0][2]=0;    

    for(int i=1;i<n-1;i++) 
    {
#if TARGET_IPHONE_SIMULATOR || TARGET_OS_IPHONE
        CGPoint P1 = [[points objectAtIndex:(i-1)] CGPointValue];
        CGPoint P2 = [[points objectAtIndex:i] CGPointValue];
        CGPoint P3 = [[points objectAtIndex:(i+1)] CGPointValue];
#else
        NSPoint P1 = [[points objectAtIndex:(i-1)] pointValue];
        NSPoint P2 = [[points objectAtIndex:i] pointValue];
        NSPoint P3 = [[points objectAtIndex:(i+1)] pointValue];
#endif

        matrix[i][0]=(double)(P2.x-P1.x)/6;
        matrix[i][1]=(double)(P3.x-P1.x)/3;
        matrix[i][2]=(double)(P3.x-P2.x)/6;
        result[i]=(double)(P3.y-P2.y)/(P3.x-P2.x) - (double)(P2.y-P1.y)/(P2.x-P1.x);
    }

    // What about result[0] and result[n-1]? Assuming 0 for now (Brad L.)
    result[0] = 0;
    result[n-1] = 0;

    matrix[n-1][1]=1;
    // What about matrix[n-1][0] and matrix[n-1][2]? For now, assuming they are 0 (Brad L.)
    matrix[n-1][0]=0;
    matrix[n-1][2]=0;

    // solving pass1 (up->down)
    for(int i=1;i<n;i++) 
    {
        double k = matrix[i][0]/matrix[i-1][1];
        matrix[i][1] -= k*matrix[i-1][2];
        matrix[i][0] = 0;
        result[i] -= k*result[i-1];
    }
    // solving pass2 (down->up)
    for(NSInteger i=n-2;i>=0;i--)
    {
        double k = matrix[i][2]/matrix[i+1][1];
        matrix[i][1] -= k*matrix[i+1][0];
        matrix[i][2] = 0;
        result[i] -= k*result[i+1];
    }

    double y2[n];
    for(int i=0;i<n;i++) y2[i]=result[i]/matrix[i][1];

    NSMutableArray *output = [NSMutableArray arrayWithCapacity:n];
    for (int i=0;i<n;i++) 
    {
        [output addObject:[NSNumber numberWithDouble:y2[i]]];
    }

    return output;
}

希望这些解释可以帮助您了解 Brad L. 使用何种算法对曲线进行插值，从而产生与 Photoshop 相同的结果。

Answer 1

我不认识这种语言（除了 C++ 之类的东西）所以很难读懂它（对我来说）但我认为这个

double y= a*cur.y + b*next.y + (h*h/6)*( (a*a*a-a)*sd[i]+ (b*b*b-b)*sd[i+1] );

是你问的。术语：

a*cur.y + b*next.y

是基本的线性插值，所以当 t=0.0 结果是当前点，如果 t=1.0 结果是下一个点。其余的是某种具有特定参数的叠加曲线，可能会为按点距离缩放的梯度产生某种凹凸图案（这就是为什么使用增量）。要扭转它会很难（而且我太懒了）但是热量让我想起 Bernstein 多项式（用于 BEZIER 和 样条曲线)。 a^3 和 b^3 表示三次曲线。您应该从绘制它生成的图形开始，然后尝试创建具有相似属性的多项式插值。如果结果与您找到的词匹配，您就回答。有关详细信息，请参阅：

以及那里的所有链接（尤其是 How to construct own interpolation 链接）。

GPUImage框架中的样条插值算法

Spline Interpolation Algorithm in GPUImage framework

algorithm

interpolation

gpuimage

spline

derivative