1

我正在尝试在 Halide 中实现标准化互相关。

下面的代码构建，Halide JIT 编译不会抛出任何错误。但是，在 JIT 编译后，Halide 似乎挂起。无论trace_*我在不同的 Funcs 上进行了多少次调用，都只会打印一条迹线（在 上Func output）：

Begin realization normxcorr.0(0, 2028, 0, 2028)
Produce normxcorr.0(0, 2028, 0, 2028)

任何建议都会有所帮助。

该算法等同于 OpenCV中的CV_TM_CCOEFF_NORMED 和 MATLAB 中的 normxcorr2 ：

void normxcorr( Halide::ImageParam input,
                Halide::ImageParam kernel,
                Halide::Param<pixel_t> kernel_mean,
                Halide::Param<pixel_t> kernel_var,
                Halide::Func& output )
{
    Halide::Var x, y;
    Halide::RDom rk( kernel );

    // reduction domain for cumulative sums
    Halide::RDom ri( 1, input.width() - kernel.width() - 1, 
                     1, input.height() - kernel.height() - 1 );

    Halide::Func input_32( "input32" ),
             bounded_input( "bounded_input"),
             kernel_32( "kernel32" ),
             knorm( "knorm" ),
             conv( "conv" ),
             normxcorr( "normxcorr_internal" ),
             sq_sum_x( "sq_sum_x" ),
             sq_sum_x_local( "sq_sum_x_local" ),
             sq_sum_y( "sq_sum_y" ),
             sq_sum_y_local( "sq_sum_y_local" ),
             sum_x( "sum_x" ),
             sum_x_local( "sum_x_local" ),
             sum_y( "sum_y" ),
             sum_y_local( "sum_y_local" ),
             win_var( "win_var" ),
             win_mean( "win_mean" );

    Halide::Expr ksize = kernel.width() * kernel.height();

    // accessing outside the input image always returns 0
    bounded_input( x, y ) = Halide::BoundaryConditions::constant_exterior( input, 0 )( x, y );

    // cast to 32-bit to make room for multiplication
    input_32( x, y ) = Halide::cast<int32_t>( bounded_input( x, y ) );
    kernel_32( x, y ) = Halide::cast<int32_t>( kernel( x, y ) );

    // cumulative sum along each row
    sum_x( x, y ) = input_32( x, y );
    sum_x( ri.x, ri.y ) += sum_x( ri.x - 1, ri.y );

    // sum of 1 x W strips
    // (W is the width of the kernel)
    sum_x_local( x, y ) = sum_x( x + kernel.width() - 1, y );
    sum_x_local( x, y ) -= sum_x( x - 1, y );

    // cumulative sums of the 1 x W strips along each column
    sum_y( x, y ) = sum_x_local( x, y );
    sum_y( ri.x, ri.y ) += sum_y( ri.x, ri.y - 1);

    // sums up H strips (as above) to get the sum of an H x W rectangle
    // (H is the height of the kernel)
    sum_y_local( x, y ) = sum_y( x, y + kernel.height() - 1 );
    sum_y_local( x, y ) -= sum_y( x, y - 1 );

    // same as above, just with squared image values
    sq_sum_x( x, y ) = input_32( x, y ) * input_32( x, y );
    sq_sum_x( ri.x, ri.y ) += sq_sum_x( ri.x - 1, ri.y );

    sq_sum_x_local( x, y ) = sq_sum_x( x + kernel.width() - 1, y );
    sq_sum_x_local( x, y ) -= sq_sum_x( x - 1, y );

    sq_sum_y( x, y ) = sq_sum_x_local( x, y );
    sq_sum_y( ri.x, ri.y ) += sq_sum_y( ri.x, ri.y - 1);

    sq_sum_y_local( x, y ) = sq_sum_y( x, y + kernel.height() - 1 );
    sq_sum_y_local( x, y ) -= sq_sum_y( x, y - 1 );

    // the mean value of each window
    win_mean( x, y ) = sum_y_local( x, y ) / ksize;

    // the variance of each window
    win_var( x, y ) =  sq_sum_y_local( x, y ) / ksize;
    win_var( x, y) -= win_mean( x, y ) * win_mean( x, y );

    // partially normalize the kernel
    // (we'll divide by std. dev. at the end)
    knorm( x, y ) = kernel_32( x, y ) - kernel_mean;

    // convolve kernel and the input
    conv( x, y ) = Halide::sum( knorm( rk.x, rk.y ) * input_32( x + rk.x, y + rk.y ) );

    // calculate normxcorr, except scaled to 0 to 254 (for an 8-bit image)
    normxcorr( x, y ) = conv( x, y ) * 127 / Halide::sqrt( kernel_var * win_var( x, y ) ) + 127;

    // after scaling pixel values, it's safe to cast down to 8-bit
    output( x, y ) = Halide::cast<pixel_t>( normxcorr( x, y ) );
}
4

1 回答 1

2

我相信这里的问题只是你没有为你的任何函数指定任何时间表，所以一切都被内联，导致中间值的大量冗余计算。所以实际上这在技术上并不是挂起的，而是简单地为每个像素做大量的工作，因此未能在合理的时间内完成。

首先，尝试说每个函数都应该compute_root（例如，sum_x.compute_root();），最容易在函数末尾的块中。这应该以更合理的速度进行，应该一个接一个地打印每个函数（从输入开始），而不是仅仅normxcore.0, 并且应该完成。

实际上，您的许多函数实际上只是其输入的逐点转换，因此这些输入可以保留为内联（不是compute_root），这应该会进一步加快速度（尤其是当您开始并行化和向量化某些阶段时）。乍一看，[sq_]sum_{x,y}可能不应该内联，但其他所有内容都可能内联。knorm并且input_32是一个折腾，取决于你的目标和你的日程安排。

我添加了这个简单的时间表和其他一些小的清理，在这里进行了快速可运行的修订：

https://gist.github.com/d64823d754a732106a60

在我的测试中，它在一秒钟内以 2K^2 的输入运行，没有什么花哨的。

顺便说一句，一个小提示：使用调试符号 ( -g) 编译生成器代码应该可以让您免于在所有Func声明中提供名称字符串。这在早期的实现中是一个不幸的缺陷，但我们现在可以直接从 C++ 源符号名称中设置这些名称，只要您在启用调试符号的情况下进行编译。

于 2015-07-02T01:56:04.943 回答