GLSL 和 GPU 片段着色器执行中的总面积 table
Summed area table in GLSL and GPU fragment shader execution
我正在尝试计算我在 GPU 内存（相机捕获）中拥有的纹理的积分图像（又名总面积 table），目标是计算所述图像的自适应阈值。我正在使用 OpenGL ES 2.0，并且仍在学习 :)。
我用简单的高斯模糊着色器（vertical/horizontal 通过）进行了测试，效果很好，但我需要更大的可变平均面积才能得到满意的结果。
我之前确实在 CPU 上实现了该算法的一个版本，但我对如何在 GPU 上实现它有点困惑。
我试图对每个片段做一个（完全不正确的）测试，就像这样：
#version 100
#extension GL_OES_EGL_image_external : require
precision highp float;
uniform sampler2D u_Texture; // The input texture.
varying lowp vec2 v_TexCoordinate; // Interpolated texture coordinate per fragment.
uniform vec2 u_PixelDelta; // Pixel delta
void main()
{
// get neighboring pixels values
float center = texture2D(u_Texture, v_TexCoordinate).r;
float a = texture2D(u_Texture, v_TexCoordinate + vec2(u_PixelDelta.x * -1.0, 0.0)).r;
float b = texture2D(u_Texture, v_TexCoordinate + vec2(0.0, u_PixelDelta.y * 1.0)).r;
float c = texture2D(u_Texture, v_TexCoordinate + vec2(u_PixelDelta.x * -1.0, u_PixelDelta.y * 1.0)).r;
// compute value
float pixValue = center + a + b - c;
// Result stores value (R) and original gray value (G)
gl_FragColor = vec4(pixValue, center, center, 1.0);
}
然后另一个着色器得到我想要的区域然后得到平均值。这显然是错误的，因为有多个执行单元同时运行。
我知道在 GPU 上计算前缀和的常用方法是分两次进行（vertical/horizontal，如此处 on this thread or or here 所讨论），但是没有问题吗这里是因为前一个（顶部或左侧）的每个单元格都存在数据依赖性？
我似乎无法理解 GPU 上的多个执行单元处理不同片段的顺序，以及二次过滤器如何解决该问题。例如，如果我有这样的值：
2 1 5
0 3 2
4 4 7
两次通过应该给出（第一列然后行）：
2 1 5 2 3 8
2 4 7 -> 2 6 13
6 8 14 6 14 28
我如何确定，例如，值 [0;2] 将被计算为 6 (2 + 4) 而不是 4（0 + 4，如果尚未计算 0 ) ?
此外，据我所知，片段不是像素（如果我没记错的话），如果我使用确切的，我在第一遍中存储在我的一个纹理中的值在另一遍中是否相同从顶点着色器传递的相同坐标，还是会以某种方式进行插值？
您尝试做的事情无法在片段着色器中完成。 GPU 在本质上与 CPU 的非常不同，因为它们同时大量并行地执行指令。因此，OpenGL 不对执行顺序做出任何保证，因为硬件物理上不允许这样做。
因此，除了 "whatever the GPU thread block scheduler decides" 之外，实际上并没有任何定义的顺序。
片段是像素，有点像。它们是可能最终出现在屏幕上的像素。如果另一个三角形在另一个三角形前面结束，则先前计算的颜色值将被丢弃。无论先前颜色缓冲区中该像素存储的是什么颜色，都会发生这种情况。
至于在GPU上创建求和区域table，我想你可能首先想看看GLSL "Compute Shaders"，它是专门为这种事情制作的。
我认为您可以通过为 table 中的每一行像素创建一个线程来实现这一点，然后让每个线程 "lag behind" 与前一个相比增加 1 个像素排。
在伪代码中：
int row_id = thread_id()
for column_index in (image.cols + image.rows):
int my_current_column_id = column_index - row_id
if my_current_column_id >= 0 and my_current_column_id < image.width:
// calculate sums
这一方法的要点在于，应保证所有线程同时执行它们的指令，而不会先于另一个。这在 CUDA 中得到保证，但我不确定它是否在 OpenGL 计算着色器中。不过，这可能是您的起点。
根据上述内容，它在 GPU 上不会很出色。但假设在 GPU 和 CPU 之间分流数据的成本更麻烦，它可能仍然值得坚持。
最明显的初步解决方案是如前所述拆分 horizontal/vertical。使用加法混合模式，创建一个绘制整个源图像的四边形，然后例如对于宽度为 n 的位图上的水平步长，发出调用请求绘制四边形 n 次，第 0 次在 x = 0，第 m 次在 x = m。然后通过 FBO ping pong，将水平绘制缓冲区的目标切换为垂直绘制的源纹理。
内存访问可能是 O(n^2)（即您可能缓存得很好，但这很难完全缓解）所以这是一个相当糟糕的解决方案。你可以通过在乐队中做同样的事情来分而治之来改进它——例如对于垂直步骤，独立地对 8 行的各个行求和，之后最后一行下方的每一行的错误是未能包括该行上的任何总和。所以执行第二遍传播那些。
然而，在帧缓冲区中累积的一个问题是钳位以避免溢出 — 如果您期望积分图像中任何地方的值大于 255，那么您就不走运了，因为加法混合将钳位并且 GL_RG32I 等人在 3.0 之前没有达到 ES。
在不使用任何特定于供应商的扩展的情况下，我能想到的最佳解决方案是拆分源图像的位并在事后合并通道。假设您的源图像是 4 位并且您的图像在两个方向上都小于 256 像素，您将在 R、G、B 和 A 通道中各放置一位，执行正常的加法步骤，然后 运行 快速将着色器重新组合为 value = A + (B*2) + (G*4) + (R*8)。如果您的纹理在大小或位深度上更大或更小，则相应地放大或缩小。
（特定于平台的观察：如果您在 iOS 上，那么您希望循环中已经有一个 CVOpenGLESTextureCache，这意味着您有 CPU 和 GPU 访问权限相同的纹理存储，因此您可能更愿意将这一步踢到 GCD。iOS 是支持 EXT_shader_framebuffer_fetch 的平台之一；如果您可以访问它，那么您可以编写任何您喜欢的旧混合函数并至少放弃组合步骤。此外，您还可以保证在绘制之前已经完成了前面的几何图形，因此如果每个条带都将其总数写在它应该的位置并且也写入下面的行，那么您可以执行理想的双像素条带解决方案没有中间缓冲区或状态更改）
Tommy 和 Bartvbl 解决了您关于面积求和的问题 table，但您的自适应阈值核心问题可能不需要那个。
作为我使用 OpenGL ES 的开源 GPUImage framework, I've done some experimentation with optimizing blurs over large radii 的一部分。通常，增加模糊半径会导致每个像素的纹理采样和计算量显着增加，并伴随减速。
但是，我发现对于大多数模糊操作，您可以应用非常有效的优化来限制模糊样本的数量。如果在模糊之前对图像进行下采样，以较小的像素半径（半径/下采样因子）进行模糊，然后进行线性上采样，则可以得到一个模糊图像，该图像相当于在更大像素半径下模糊的图像。在我的测试中，这些降采样、模糊、然后升采样的图像看起来与基于原始图像分辨率模糊的图像几乎相同。事实上，精度限制会导致在原始分辨率下进行更大的半径模糊，图像质量会下降超过一定尺寸，而下采样的图像质量会保持适当的图像质量。
通过调整下采样因子以保持下采样模糊半径恒定，您可以在面对增加的模糊半径时实现接近恒定时间的模糊速度。对于自适应阈值，图像质量应该足以用于您的比较。
我在上述链接框架的最新版本中的高斯和框模糊中使用了这种方法，因此如果您在 Mac、iOS 上 运行，或者Linux，您可以通过试用其中一个示例应用程序来评估结果。我有一个基于使用此优化的框模糊的自适应阈值操作，因此您可以查看结果是否是您想要的。
对于初学者来说可能看起来很奇怪，但是前缀和或 SAT 计算适合并行化。作为 Hensley algorithm is the most intuitive to understand (also implemented in OpenGL), more work-efficient parallel methods are available, see CUDA scan. The paper from Sengupta discuss parallel method which seems state-of-the-art efficient method with reduce and down swap phases. These are valuable materials but they do not enter OpenGL shader implementations in detail. The closest document is the presentation you have found (it refers to Hensley 出版物），因为它有一些着色器片段。这是完全可以在带有 FBO Ping-Pong 的片段着色器中完成的工作。请注意，FBO 及其纹理需要将内部格式设置为高精度 - GL_RGB32F 最好，但我不确定 OpenGL ES 2.0 是否支持它。
我正在尝试计算我在 GPU 内存（相机捕获）中拥有的纹理的积分图像（又名总面积 table），目标是计算所述图像的自适应阈值。我正在使用 OpenGL ES 2.0，并且仍在学习 :)。
我用简单的高斯模糊着色器（vertical/horizontal 通过）进行了测试，效果很好，但我需要更大的可变平均面积才能得到满意的结果。
我之前确实在 CPU 上实现了该算法的一个版本，但我对如何在 GPU 上实现它有点困惑。 我试图对每个片段做一个（完全不正确的）测试，就像这样：
#version 100
#extension GL_OES_EGL_image_external : require
precision highp float;
uniform sampler2D u_Texture; // The input texture.
varying lowp vec2 v_TexCoordinate; // Interpolated texture coordinate per fragment.
uniform vec2 u_PixelDelta; // Pixel delta
void main()
{
// get neighboring pixels values
float center = texture2D(u_Texture, v_TexCoordinate).r;
float a = texture2D(u_Texture, v_TexCoordinate + vec2(u_PixelDelta.x * -1.0, 0.0)).r;
float b = texture2D(u_Texture, v_TexCoordinate + vec2(0.0, u_PixelDelta.y * 1.0)).r;
float c = texture2D(u_Texture, v_TexCoordinate + vec2(u_PixelDelta.x * -1.0, u_PixelDelta.y * 1.0)).r;
// compute value
float pixValue = center + a + b - c;
// Result stores value (R) and original gray value (G)
gl_FragColor = vec4(pixValue, center, center, 1.0);
}
然后另一个着色器得到我想要的区域然后得到平均值。这显然是错误的，因为有多个执行单元同时运行。
我知道在 GPU 上计算前缀和的常用方法是分两次进行（vertical/horizontal，如此处 on this thread or or here 所讨论），但是没有问题吗这里是因为前一个（顶部或左侧）的每个单元格都存在数据依赖性？
我似乎无法理解 GPU 上的多个执行单元处理不同片段的顺序，以及二次过滤器如何解决该问题。例如，如果我有这样的值：
2 1 5
0 3 2
4 4 7
两次通过应该给出（第一列然后行）：
2 1 5 2 3 8
2 4 7 -> 2 6 13
6 8 14 6 14 28
我如何确定，例如，值 [0;2] 将被计算为 6 (2 + 4) 而不是 4（0 + 4，如果尚未计算 0 ) ?
此外，据我所知，片段不是像素（如果我没记错的话），如果我使用确切的，我在第一遍中存储在我的一个纹理中的值在另一遍中是否相同从顶点着色器传递的相同坐标，还是会以某种方式进行插值？
您尝试做的事情无法在片段着色器中完成。 GPU 在本质上与 CPU 的非常不同，因为它们同时大量并行地执行指令。因此，OpenGL 不对执行顺序做出任何保证，因为硬件物理上不允许这样做。
因此，除了 "whatever the GPU thread block scheduler decides" 之外，实际上并没有任何定义的顺序。
片段是像素，有点像。它们是可能最终出现在屏幕上的像素。如果另一个三角形在另一个三角形前面结束，则先前计算的颜色值将被丢弃。无论先前颜色缓冲区中该像素存储的是什么颜色，都会发生这种情况。
至于在GPU上创建求和区域table，我想你可能首先想看看GLSL "Compute Shaders"，它是专门为这种事情制作的。
我认为您可以通过为 table 中的每一行像素创建一个线程来实现这一点，然后让每个线程 "lag behind" 与前一个相比增加 1 个像素排。
在伪代码中：
int row_id = thread_id()
for column_index in (image.cols + image.rows):
int my_current_column_id = column_index - row_id
if my_current_column_id >= 0 and my_current_column_id < image.width:
// calculate sums
这一方法的要点在于，应保证所有线程同时执行它们的指令，而不会先于另一个。这在 CUDA 中得到保证，但我不确定它是否在 OpenGL 计算着色器中。不过，这可能是您的起点。
根据上述内容，它在 GPU 上不会很出色。但假设在 GPU 和 CPU 之间分流数据的成本更麻烦，它可能仍然值得坚持。
最明显的初步解决方案是如前所述拆分 horizontal/vertical。使用加法混合模式，创建一个绘制整个源图像的四边形，然后例如对于宽度为 n 的位图上的水平步长，发出调用请求绘制四边形 n 次，第 0 次在 x = 0，第 m 次在 x = m。然后通过 FBO ping pong，将水平绘制缓冲区的目标切换为垂直绘制的源纹理。
内存访问可能是 O(n^2)（即您可能缓存得很好，但这很难完全缓解）所以这是一个相当糟糕的解决方案。你可以通过在乐队中做同样的事情来分而治之来改进它——例如对于垂直步骤，独立地对 8 行的各个行求和，之后最后一行下方的每一行的错误是未能包括该行上的任何总和。所以执行第二遍传播那些。
然而，在帧缓冲区中累积的一个问题是钳位以避免溢出 — 如果您期望积分图像中任何地方的值大于 255，那么您就不走运了，因为加法混合将钳位并且 GL_RG32I 等人在 3.0 之前没有达到 ES。
在不使用任何特定于供应商的扩展的情况下，我能想到的最佳解决方案是拆分源图像的位并在事后合并通道。假设您的源图像是 4 位并且您的图像在两个方向上都小于 256 像素，您将在 R、G、B 和 A 通道中各放置一位，执行正常的加法步骤，然后 运行 快速将着色器重新组合为 value = A + (B*2) + (G*4) + (R*8)。如果您的纹理在大小或位深度上更大或更小，则相应地放大或缩小。
（特定于平台的观察：如果您在 iOS 上，那么您希望循环中已经有一个 CVOpenGLESTextureCache，这意味着您有 CPU 和 GPU 访问权限相同的纹理存储，因此您可能更愿意将这一步踢到 GCD。iOS 是支持 EXT_shader_framebuffer_fetch 的平台之一；如果您可以访问它，那么您可以编写任何您喜欢的旧混合函数并至少放弃组合步骤。此外，您还可以保证在绘制之前已经完成了前面的几何图形，因此如果每个条带都将其总数写在它应该的位置并且也写入下面的行，那么您可以执行理想的双像素条带解决方案没有中间缓冲区或状态更改）
Tommy 和 Bartvbl 解决了您关于面积求和的问题 table，但您的自适应阈值核心问题可能不需要那个。
作为我使用 OpenGL ES 的开源 GPUImage framework, I've done some experimentation with optimizing blurs over large radii 的一部分。通常，增加模糊半径会导致每个像素的纹理采样和计算量显着增加，并伴随减速。
但是，我发现对于大多数模糊操作，您可以应用非常有效的优化来限制模糊样本的数量。如果在模糊之前对图像进行下采样，以较小的像素半径（半径/下采样因子）进行模糊，然后进行线性上采样，则可以得到一个模糊图像，该图像相当于在更大像素半径下模糊的图像。在我的测试中，这些降采样、模糊、然后升采样的图像看起来与基于原始图像分辨率模糊的图像几乎相同。事实上，精度限制会导致在原始分辨率下进行更大的半径模糊，图像质量会下降超过一定尺寸，而下采样的图像质量会保持适当的图像质量。
通过调整下采样因子以保持下采样模糊半径恒定，您可以在面对增加的模糊半径时实现接近恒定时间的模糊速度。对于自适应阈值，图像质量应该足以用于您的比较。
我在上述链接框架的最新版本中的高斯和框模糊中使用了这种方法，因此如果您在 Mac、iOS 上 运行，或者Linux，您可以通过试用其中一个示例应用程序来评估结果。我有一个基于使用此优化的框模糊的自适应阈值操作，因此您可以查看结果是否是您想要的。
对于初学者来说可能看起来很奇怪，但是前缀和或 SAT 计算适合并行化。作为 Hensley algorithm is the most intuitive to understand (also implemented in OpenGL), more work-efficient parallel methods are available, see CUDA scan. The paper from Sengupta discuss parallel method which seems state-of-the-art efficient method with reduce and down swap phases. These are valuable materials but they do not enter OpenGL shader implementations in detail. The closest document is the presentation you have found (it refers to Hensley 出版物），因为它有一些着色器片段。这是完全可以在带有 FBO Ping-Pong 的片段着色器中完成的工作。请注意，FBO 及其纹理需要将内部格式设置为高精度 - GL_RGB32F 最好，但我不确定 OpenGL ES 2.0 是否支持它。