低时空复杂度下高效无重复随机遍历图像像素的实现方案

当处理大尺寸图像时，预存所有像素坐标再打乱会占用大量内存，我们可以通过伪随机遍历函数直接生成唯一且分布均匀的像素坐标，无需预存任何坐标列表，时空复杂度极低。

方案1：线性同余生成器(LCG) + 坐标映射 #

线性同余生成器(LCG)是一种轻量的伪随机数生成器，只要参数选择得当，就能生成覆盖0到n²-1的所有整数（即所有像素的一维索引），再将索引转换为二维坐标即可。这种方法空间复杂度为O(1)，仅需存储几个状态变量，每个坐标生成都是O(1)操作。

JavaScript实现 #

function* pixelRandomTraversal(n) {
    const totalPixels = n * n;
    // LCG参数，满足全周期条件：a与totalPixels互质，c与totalPixels互质
    const a = 1664525;
    const c = 1013904223;
    let current = Math.floor(Math.random() * totalPixels); // 随机起始点

    for (let i = 0; i < totalPixels; i++) {
        const x = current % n;
        const y = Math.floor(current / n);
        yield { x, y };
        current = (a * current + c) % totalPixels;
    }
}

// 使用示例：遍历1000×1000图像
const n = 1000;
for (const { x, y } of pixelRandomTraversal(n)) {
    // 处理像素逻辑，例如：
    // const pixel = imageData.data[(y * n + x) * 4];
}

说明 #

• 示例中的LCG参数是经过验证的通用值，能适配绝大多数图像尺寸（包括2的幂和非2的幂的情况），保证生成的序列覆盖所有像素无重复。
• 随机起始点可以让每次遍历的顺序都不同，避免固定模式。

方案2：Halton低差异序列 #

如果更注重点的均匀分布而非严格随机，Halton序列是更好的选择。它能生成均匀分散的点，不会出现局部聚集，适合需要均匀采样的场景。

JavaScript实现 #

function halton(index, base) {
    let result = 0;
    let fraction = 1 / base;
    let i = index;
    while (i > 0) {
        result += fraction * (i % base);
        i = Math.floor(i / base);
        fraction /= base;
    }
    return result;
}

function* pixelHaltonTraversal(n) {
    for (let i = 1; i <= n * n; i++) {
        const x = Math.floor(halton(i, 2) * n);
        const y = Math.floor(halton(i, 3) * n);
        yield { x, y };
    }
}

// 使用示例
const n = 1000;
for (const { x, y } of pixelHaltonTraversal(n)) {
    // 处理像素逻辑
}

说明 #

• Halton序列通过不同基数生成x、y方向的分量，保证点的均匀性。
• 如果图像尺寸n是基数的幂（比如n=2^k），可以调整起始索引（比如从随机数开始）避免重复点。

内容的提问来源于stack exchange，提问作者yuta y