Geekly articles weekly

Reconhecimento de fontes de luz em mapas ambientais

imagem

Este artigo apresenta uma implementação em Python do algoritmo para reconhecer fontes de luz em mapas do ambiente (LDR ou HDR) usando uma projeção equiretangular. No entanto, depois de fazer pequenas alterações, ele também pode ser usado com imagens de fundo simples ou mapas cúbicos. Exemplos da possível aplicação do algoritmo: programas de rastreamento de raios nos quais é necessário reconhecer fontes de luz primárias para emitir raios a partir delas; em renderizadores rasterizados, pode ser usado para projetar sombras usando um mapa do ambiente; além disso, o algoritmo também pode ser usado em programas de eliminação de destaque, por exemplo, em RA.

O algoritmo consiste nas seguintes etapas:

  1. Diminua a resolução da imagem original, por exemplo, para 1024.
  2. Converta a imagem em brilho (luminância), se necessário, com desfoque de imagem.
  3. Aplicação do método quase-Monte Carlo.
  4. Transformação de coordenadas esféricas em coordenadas equidistantes.
  5. Filtrando amostras com base no brilho de um vizinho.
  6. Classifique as amostras com base no brilho.
  7. Filtrando amostras com base na métrica euclidiana.
  8. Mesclando amostras usando o algoritmo de Bresenham.
  9. Cálculo da posição do cluster de iluminação com base em seu brilho.

Existem muitos algoritmos para reduzir a resolução das imagens. A filtragem bilinear é a mais rápida ou fácil de implementar e, além disso, é mais adequada na maioria dos casos. Para converter o brilho nas imagens LDR e HDR, você pode usar a fórmula padrão:

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

Além disso, você pode aplicar um leve desfoque na imagem do brilho, por exemplo, 1-2 pixels para uma imagem com uma resolução de 1024, para eliminar todos os detalhes de alta frequência (em particular, causados ​​por uma diminuição na resolução).

Projeção Equidistante


A projeção mais comum em mapas ambientais é a projeção equidistante 3 . Meu algoritmo pode trabalhar com outras projeções, por exemplo, com mapas panorâmicos e cúbicos, no entanto, no artigo, consideraremos apenas uma projeção igualmente espaçada. Primeiro você precisa normalizar as coordenadas da imagem:

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

Precisamos converter de e para coordenadas cartesianas usando coordenadas esféricas, ou seja, θ e φ, onde θ = x * 2π e φ = 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 Sampling


O próximo passo será aplicar o método quase-Monte Carlo, por exemplo, a amostragem de Hammersley 2 :


Você pode usar outros métodos de amostragem, como Holton 4 , mas Hammersley é mais rápido e fornece uma boa distribuição de amostras pela esfera. Holton seria uma boa escolha para amostras de avião se uma imagem simples for usada em vez do mapa do ambiente. Um requisito obrigatório para a amostragem de Hammersley é a inversão das raízes (linha) de van der Corpute, para obter mais detalhes, consulte os links 2 . Aqui está sua rápida implementação:

 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))

Em seguida, usamos sobreposição uniforme na esfera:

 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)

Para amostrar Hammersley, usamos um número fixo de amostras, dependendo da resolução da imagem, e convertemos de coordenadas esféricas em cartesiana e depois em equidistante:

  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]

Isso nos dará uma boa distribuição de amostras que serão verificadas quanto à presença de fontes de luz:


Filtrando fontes de luz


Na primeira etapa da filtragem, ignoramos todas as amostras que não excedem o limite de brilho (para cartões HDR, pode ser maior) e, em seguida, classificamos todas as amostras pelo brilho:

  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)

A próxima passagem realizará a filtragem com base na métrica euclidiana e na distância limite entre os pixels (dependendo da resolução da imagem) - essa é uma estrutura de dados espaciais que pode ser usada para se livrar da complexidade 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

As amostras resultantes passam pelo estágio de fusão para reduzir ainda mais o número de fontes de luz:


Mesclando fontes de luz


No último estágio, é realizada a mesclagem de amostras pertencentes ao mesmo cluster de iluminação. Para fazer isso, podemos usar o algoritmo de Bresenham e começar com as amostras com o brilho mais alto, porque elas já estão ordenadas. Quando encontramos uma fonte de luz que satisfaz o teste de Bresenham, usamos sua posição para alterar a posição da fonte com base no peso da corrida:

  # 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)

A função Bresenham verifica se há uma linha contínua com o mesmo brilho. Se o delta no pixel atual exceder um determinado limite, a verificação falhará:

 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

Deve-se notar que, se necessário, melhorias podem ser feitas no teste de Bresenham, o que levará a uma melhor fusão das amostras, por exemplo, pode levar em consideração a transferência horizontal de fontes de luz localizadas nas bordas da imagem. Além disso, a função pode ser facilmente expandida para aproximar a área das fontes de luz. Outra melhoria: você pode adicionar um limite de distância para não combinar amostras muito distantes. Resultados Finais:


Azul indica o máximo local dos clusters de iluminação, azul indica as posições finais das fontes de luz e vermelho indica amostras que fazem parte do mesmo cluster de iluminação e são conectadas por linhas.

Outros exemplos de resultados:



  1. Detecção de fontes de luz em fotografias digitais por Maciej Laskowski
  2. Pontos de Hammersley no Hemisfério por Holger Dammertz
  3. Projeção Equiretangular por Paul Reed
  4. Amostragem com Hammersley e Halton Points por Tien-Tsin Wong

Source: https://habr.com/ru/post/pt458598/

More articles:


All Articles