[INVESTIGATION] ImageBuffer iterators based on Space Filling Curves

Đang mở
  • Có gì không ổn?
#4,554 8 bình luận 0 reaction 0 người được giao Xem trên GitHub

Maintainer thường phản hồi trong vòng 1 ngày

Chưa có ai nhận issue này.

Đánh giá

Độ khó
5/5
Thời gian dự kiến
Hơn một tuần
Mức phù hợp với người mới
25/100
Loại issue
Tính năng
Độ rõ ràng
Cần làm rõ
Mức độ hoạt động
Đình trệ
Công nghệ
cpp
Lĩnh vực
computer-graphics, performance

Hướng nghiên cứu

Bắt đầu bằng cách biên dịch và chạy nghiên cứu C++ độc lập, so sánh process_ref với process_morton trên các kích thước ảnh và tích chập đã nêu. Đọc cách sử dụng ImageBuf::Iterator và ImageBuf::ConstIterator được thể hiện trong ví dụ, sau đó xác định liệu việc duyệt Morton hoặc Hilbert có mang lại lợi ích đo được hay không. Issue không định nghĩa thế nào là hoàn tất; kết quả cần xác lập bằng chứng về hiệu năng và một hướng triển khai cụ thể.

Do mô hình lập chỉ mục viết ra từ nội dung của issue.

Mô tả

Recently I've been looking into space filling curves, in particular the Morton curve (see https://en.wikipedia.org/wiki/Z-order_curve) and the Hilbert curve (see https://en.wikipedia.org/wiki/Hilbert_curve). I've read that these curves can be used to iterate through the pixels of an image in a "cache-friendly" way as they preserve spatial locality fairly well, and thus could improve the performances of some image processing algorithms.

I've started doing some investigation work, however the results I got so far do not suggest any performance improvements when using the Morton curve to iterate: I'm applying a simple convolution with a Gaussian kernel on a 4096x4096 image (on a single thread), and iterating with ImageBuffer::Iterator vs with my custom Morton curve implementation both take on average the exact same time.

If someone has some knowledge around space filling curves, performance engineering, or simply wants to continue the investigation on their side and provide more insight on this, your help is definitely welcome!

Here is the code I wrote for this initial investigation:

#include <OpenImageIO/imageio.h>
#include <OpenImageIO/imagebuf.h>
#include <OpenImageIO/imagebufalgo.h>

#include <iostream>
#include <string>
#include <cmath>
#include <chrono>


using namespace OIIO;


void process_ref(ImageBuf & dst, const ImageBuf & src, const ImageBuf & kernel)
{
    ROI roi    = src.roi();
    ROI kroi   = kernel.roi();

    ImageBuf::Iterator<float> dstit(dst);
    ImageBuf::ConstIterator<float> srcit(src);

    for (; !dstit.done(); ++dstit) {
        float sum = 0.f;

        const float* k = (const float*)kernel.localpixels();
        srcit.rerange(dstit.x() + kroi.xbegin, dstit.x() + kroi.xend,
                      dstit.y() + kroi.ybegin, dstit.y() + kroi.yend,
                      0                      , 1                    ,
                      ImageBuf::WrapClamp);
        for (; !srcit.done(); ++srcit, k += 1) {
            sum += k[0] * srcit[0];
        }

        dstit[0] = sum;
    }
}


void process_morton(ImageBuf & dst, const ImageBuf & src, const ImageBuf & kernel, int nbits)
{
    float* pixels = static_cast<float*>(dst.localpixels());

    const ImageSpec & spec = dst.spec();
    const uint64_t nmax    = (1 << (2 * nbits));

    ROI roi    = src.roi();
    ROI kroi   = kernel.roi();

    ImageBuf::ConstIterator<float> srcit(src);

    for (uint64_t i = 0; i < nmax; ++i) {
        uint32_t xmorton = 0;
        uint32_t ymorton = 0;
        for (int j = 0; j < nbits; ++j) {
            xmorton |= (i & (1 << (2 * j))) >> j;
            ymorton |= (i & (1 << (2 * j + 1))) >> (j + 1);
        }

        float sum = 0.f;

        const float* k = (const float*)kernel.localpixels();
        srcit.rerange(xmorton + kroi.xbegin, xmorton + kroi.xend,
                      ymorton + kroi.ybegin, ymorton + kroi.yend,
                      0                    , 1                  ,
                      ImageBuf::WrapClamp);
        for (; !srcit.done(); ++srcit, k += 1) {
            sum += k[0] * srcit[0];
        }

        pixels[ymorton * spec.width + xmorton] = sum;
    }
}


int main(int argc, char *argv[])
{
    // Command-line arguments
    const std::string mode = argv[1];
    const int nbits = std::stoi(argv[2]);
    const float kernel_size = std::stof(argv[3]);
    const std::string filename = argv[4];

    // Specs for image buffer
    // We only use dimensions that are powers of 2,
    // with an exponent specified by the user
    const int xres = (1 << nbits);
    const int yres = (1 << nbits);
    const int nchannels = 1;
    ImageSpec spec(xres, yres, nchannels, TypeDesc::FLOAT);

    // Destination buffer
    ImageBuf dst(spec);

    // Source buffer
    // Use a simple checker
    ImageBuf src(spec);
    float dark[3]  = { 0.1, 0.1, 0.1 };
    float light[3] = { 0.4, 0.4, 0.4 };
    ImageBufAlgo::checker(src, 64, 64, 1, cspan<float>(dark), cspan<float>(light));

    // Kernel buffer
    // Use a normalized Gaussian kernel
    ImageBuf kernel = ImageBufAlgo::make_kernel("gaussian", kernel_size, kernel_size);

    // Apply convolution to compute the final image
    // Measure elapsed time to compare iterator-based approach
    // and Morton-curve-based approach
    auto t_start = std::chrono::high_resolution_clock::now();
    if (mode == "ref") process_ref(dst, src, kernel);
    else if (mode == "morton") process_morton(dst, src, kernel, nbits);
    auto t_end = std::chrono::high_resolution_clock::now();
    std::cout << "Elapsed time: "
              << std::chrono::duration_cast<std::chrono::microseconds>(t_end - t_start).count()
              << " microseconds" << std::endl;

    // Store final image on disk
    auto out = ImageOutput::create(filename);
    out->open(filename, spec);
    dst.write(out.get());
    out->close();

    return EXIT_SUCCESS;
}
Ngôn ngữ chính
C++
Star
2.4k
Fork
718
Merge trung bình
2 ngày 10 giờ
Pull request đã merge (30 ngày)
87

Chuẩn bị môi trường

Bắt đầu từ đâu

  1. Đọc hết issue, rồi đọc hướng dẫn đóng góp của dự án.
  2. Bình luận trên issue rằng bạn sẽ nhận — tránh hai người làm cùng một việc.
  3. Fork repository và làm thay đổi trên một nhánh.
  4. Mở pull request có tham chiếu số hiệu của issue.

Issue khác của AcademySoftwareFoundation/OpenImageIO

Tất cả issue của AcademySoftwareFoundation/OpenImageIO

Issue tương tự

Thêm issue về C++

Nhận issue mới trong hộp thư của bạn

Bản tóm tắt ngắn những issue GitHub phù hợp với người mới.