Geekly articles weekly

在环境地图上识别光源

图片

本文介绍了该算法的Python实现，该算法使用等角矩形投影识别环境地图（LDR或HDR）上的光源。 但是，在进行较小的更改后，它也可以用于简单的背景图像或立方图。 该算法可能的应用示例：光线跟踪程序，在其中需要识别主要光源以便从它们发出光线； 在栅格化渲染器中，可以使用环境贴图来投射阴影； 此外，该算法还可以用于聚光消除程序中，例如AR。

该算法包括以下步骤：

  1. 将原始图像的分辨率降低到例如1024。
  2. 如有必要，将图像转换为亮度（亮度），并进行图像模糊处理。
  3. 准蒙特卡罗方法的应用。
  4. 从球坐标转换为等距坐标。
  5. 根据邻居的亮度过滤样本。
  6. 根据样本的亮度对其排序。
  7. 根据欧几里德度量标准过滤样本。
  8. 使用Bresenham算法合并样本。
  9. 根据其亮度计算照明集群的位置。

有许多降低图像分辨率的算法。 双线性滤波是最快或最容易实现的，此外，它最适合大多数情况。 要同时转换LDR和HDR图像的亮度，可以使用标准公式：

lum = img[:, :, 0] * 0.2126 + img[:, :, 1] * 0.7152 + img[:, :, 2] * 0.0722

此外，您可以对亮度图像进行轻微的模糊处理，例如，对于分辨率为1024的图像，可以使用1-2像素，以消除所有高频细节（特别是分辨率降低引起的）。

等距投影


环境地图中最常见的投影是等距投影3 。 我的算法可以与其他投影配合使用，例如与全景图和立方图配合使用，但是，在本文中，我们将仅考虑等距投影。 首先，您需要标准化图像坐标：

 pos[0] = x / width pos[1] = y / height

然后我们需要使用球面坐标将笛卡尔坐标转换为笛卡尔坐标，即 θ和φ，其中θ= x *2π，而φ= y *π。

 def sphereToEquirectangular(pos): invAngles = (0.1591, 0.3183) xy = (math.atan2(pos[1], pos[0]), math.asin(pos[2])) xy = (xy[0] * invAngles[0], xy[1] * invAngles[1]) return (xy[0] + 0.5, xy[1] + 0.5) def equirectangularToSphere(pos): angles = (1 / 0.1591, 1 / 0.3183) thetaPhi = (pos[0] - 0.5, pos[1] - 0.5) thetaPhi = (thetaPhi[0] * angles[0], thetaPhi[1] * angles[1]) length = math.cos(thetaPhi[1]) return (math.cos(thetaPhi[0]) * length, math.sin(thetaPhi[0]) * length, math.sin(thetaPhi[1]))

哈默斯利采样


下一步将应用准蒙特卡罗方法，例如Hammersley 2采样：


您可以使用其他采样方法，例如Holton 4 ，但是Hammersley速度更快，并且可以在整个球体上提供良好的样本分布。 如果使用简单的图像代替环境贴图，则Holton将是飞机样本的不错选择。 Hammersley采样的强制性要求是van der Corpute的根（行）倒置，有关更多详细信息，请参见链接2 。 这是它的快速实现：

 def vdcSequence(bits): bits = (bits << 16) | (bits >> 16) bits = ((bits & 0x55555555) << 1) | ((bits & 0xAAAAAAAA) >> 1) bits = ((bits & 0x33333333) << 2) | ((bits & 0xCCCCCCCC) >> 2) bits = ((bits & 0x0F0F0F0F) << 4) | ((bits & 0xF0F0F0F0) >> 4) bits = ((bits & 0x00FF00FF) << 8) | ((bits & 0xFF00FF00) >> 8) return float(bits) * 2.3283064365386963e-10 # / 0x100000000 def hammersleySequence(i, N): return (float(i) / float(N), vdcSequence(i))

然后，我们在球体上使用均匀覆盖：

 def sphereSample(u, v): PI = 3.14159265358979 phi = v * 2.0 * PI cosTheta = 2.0 * u - 1.0 # map to -1,1 sinTheta = math.sqrt(1.0 - cosTheta * cosTheta); return (math.cos(phi) * sinTheta, math.sin(phi) * sinTheta, cosTheta)

为了对Hammersley进行采样，我们使用固定数量的采样，具体取决于图像的分辨率，然后从球坐标转换为笛卡尔坐标，然后转换为等距：

  samplesMultiplier = 0.006 samples = int(samplesMultiplier * width * height) samplesList = [] # apply hammersley sampling for i in range(0, samples): xi = hammersleySequence(i, samples) xyz = sphereSample(xi[0], xi[1]) # to cartesian imagePos = sphereToEquirectangular(xyz) luminance = lum[imagePos[0] * width, imagePos[1] * height]

这将使我们能够很好地分布样本，将检查光源是否存在：


过滤光源


在第一遍过滤中，我们将忽略所有未超过亮度阈值的样本（对于HDR卡，可能会更高），然后按照亮度对所有样本进行排序：

  localSize = int(float(12) * (width / 1024.0)) + 1 samplesList = [] # apply hammersley sampling for i in range(0, samples): xi = hammersleySequence(i, samples) xyz = sphereSample(xi[0], xi[1]) # to cartesian imagePos = sphereToEquirectangular(xyz) luminance = lum[imagePos [0] * width, imagePos [1] * height] sample = Sample(luminance, imagePos , xyz) luminanceThreshold = 0.8 #do a neighbour search for the maximum luminance nLum = computeNeighborLuminance(lum, width, height, sample.imagePos, localSize) if nLum > luminanceThreshold: samplesList.append(sample) samplesList = sorted(samplesList, key=lambda obj: obj.luminance, reverse=True)

下一遍将基于欧几里德度量和像素之间的阈值距离（取决于图像的分辨率）进行过滤-这是一种空间数据结构，可用于消除复杂度O（N 2 ）：

  euclideanThreshold = int(float(euclideanThresholdPixel) * (width / 2048.0)) # filter based euclidian distance filteredCount = len(samplesList) localIndices = np.empty(filteredCount); localIndices.fill(-1) for i in range(0, filteredCount): cpos = samplesList[i].pos if localIndices[i] == -1: localIndices[i] = i for j in range(0, filteredCount): if i != j and localIndices[j] == -1 and distance2d(cpos, samplesList[j].pos) < euclideanThreshold: localIndices[j] = i

所得样本经过合并阶段以进一步减少光源数量：


合并光源


在最后阶段，合并属于同一照明集群的样本。 为此，我们可以使用Bresenham算法，并从亮度最高的样本开始，因为它们已经被订购。 当我们找到满足Bresenham测试要求的光源时，我们会根据其运行权重使用其位置更改光源的位置：

  # apply bresenham check and compute position of the light clusters lights = [] finalIndices = np.empty(filteredCount); finalIndices.fill(-1) for i in localIndices: sample = samplesList[i] startPos = sample.pos if finalIndices[i] == -1: finalIndices[i] = i light = Light() light.originalPos = np.array(sample.pos) # position of the local maxima light.worldPos = np.array(sample.worldPos) light.pos = np.array(sample.pos) light.luminance = sample.luminance for j in localIndices: if i != j and finalIndices[j] == -1: endPos = samplesList[j].pos if bresenhamCheck(lum, width, height, startPos[0], startPos[1], endPos[0], endPos[1]): finalIndices[j] = i # compute final position of the light source sampleWeight = samplesList[j].luminance / sample.luminance light.pos = light.pos + np.array(endPos) * sampleWeight light.pos = light.pos / (1.0 + sampleWeight) imagePos = light.pos * np.array([1.0 / width, 1.0 / height) light.worldPos = equirectangularToSphere(imagePos) lights.append(light)

Bresenham功能会检查亮度相同的连续线。 如果当前像素中的增量超过某个阈值，则检查失败：

 def bresenhamCheck(lum, imageSize, x0, y0, x1, y1): dX = int(x1 - x0) stepX = int((dX > 0) - (dX < 0)) dX = abs(dX) << 1 dY = int(y1 - y0) stepY = int((dY > 0) - (dY < 0)) dY = abs(dY) << 1 luminanceThreshold = 0.15 prevLum = lum[x0][y0] sumLum = 0.0 c = 0 if (dX >= dY): # delta may go below zero delta = int (dY - (dX >> 1)) while (x0 != x1): # reduce delta, while taking into account the corner case of delta == 0 if ((delta > 0) or (delta == 0 and (stepX > 0))): delta -= dX y0 += stepY delta += dY x0 += stepX sumLum = sumLum + min(lum[x0][y0], 1.25) c = c + 1 if(abs(sumLum / c - prevLum) > luminanceThreshold and (sumLum / c) < 1.0): return 0 else: # delta may go below zero delta = int(dX - (dY >> 1)) while (y0 != y1): # reduce delta, while taking into account the corner case of delta == 0 if ((delta > 0) or (delta == 0 and (stepY > 0))): delta -= dY x0 += stepX delta += dX y0 += stepY sumLum = sumLum + min(lum[x0][y0], 1.25) c = c + 1 if(abs(sumLum / c - prevLum) > luminanceThreshold and (sumLum / c) < 1.0): return 0 return 1

应当指出，如有必要，可以对Bresenham测试进行改进，这将导致更好地合并样本，例如，可以考虑位于图像边缘的光源的水平转移。 此外，可以轻松扩展功能，使其接近光源的面积。 另一个改进：您可以添加距离阈值，这样就不会合并距离太远的样本。 最终结果：


蓝色表示照明集群的局部最大值，蓝色表示光源的最终位置，红色表示属于同一照明集群的一部分并通过线连接的样本。

其他结果示例：



  1. Maciej Laskowski检测数码照片中的光源
  2. 哈默斯利（Hammersley）指出半球
  3. 保罗·里德的等角投影
  4. 黄天心（Tian-Tsin Wong）用Hammersley和Halton点进行采样

Source: https://habr.com/ru/post/zh-CN458598/

More articles:


All Articles