Cet article présente une implémentation Python de l'algorithme de reconnaissance des sources lumineuses sur les cartes d'environnement (LDR ou HDR) à l'aide d'une projection équirectangulaire. Cependant, après avoir apporté des modifications mineures, il peut également être utilisé avec de simples images d'arrière-plan ou des cartes cubiques. Exemples d'application possible de l'algorithme: programmes de traçage de rayons dans lesquels il est nécessaire de reconnaître des sources lumineuses primaires pour en émettre des rayons; dans les rendus pixellisés, il peut être utilisé pour projeter des ombres à l'aide d'une carte d'environnement; en outre, l'algorithme peut également être utilisé dans des programmes d'élimination des projecteurs, par exemple en RA.
L'algorithme comprend les étapes suivantes:
- Diminution de la résolution de l'image d'origine, par exemple, à 1024.
- Convertissez l'image en luminosité (luminance), si nécessaire, avec un flou de l'image.
- Application de la méthode quasi-Monte Carlo.
- Transformation de coordonnées sphériques en coordonnées équidistantes.
- Filtrer les échantillons en fonction de la luminosité d'un voisin.
- Triez les échantillons en fonction de leur luminosité.
- Filtrage des échantillons basés sur la métrique euclidienne.
- Fusion d'échantillons à l'aide de l'algorithme de Bresenham.
- Calcul de la position du groupe d'éclairage en fonction de sa luminosité.
Il existe de nombreux algorithmes pour réduire la résolution des images. Le filtrage bilinéaire est le plus rapide ou le plus facile à mettre en œuvre, et en plus, il est le mieux adapté dans la plupart des cas. Pour convertir la luminosité des images LDR et HDR, vous pouvez utiliser la formule standard:
lum = img[:, :, 0] * 0.2126 + img[:, :, 1] * 0.7152 + img[:, :, 2] * 0.0722
De plus, vous pouvez appliquer un léger flou à l'image de luminosité, par exemple, 1 à 2 pixels pour une image avec une résolution de 1024, pour éliminer tous les détails haute fréquence (en particulier, causés par une diminution de la résolution).
Projection équidistante
La projection la plus courante dans les cartes d'environnement est la projection équidistante
3 . Mon algorithme peut fonctionner avec d'autres projections, par exemple, avec des cartes panoramiques et cubiques, cependant, dans l'article, nous ne considérerons qu'une projection également espacée. Vous devez d'abord normaliser les coordonnées de l'image:
pos[0] = x / width pos[1] = y / height
Ensuite, nous devons convertir des coordonnées cartésiennes à partir de coordonnées sphériques, c'est-à-dire θ et φ, où θ = x * 2π, et φ = 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]))
Échantillonnage de Hammersley
La prochaine étape consistera à appliquer la méthode quasi-Monte Carlo, par exemple l'échantillonnage Hammersley
2 :
Vous pouvez utiliser d'autres méthodes d'échantillonnage, comme Holton
4 , mais Hammersley est plus rapide et fournit une bonne répartition des échantillons à travers la sphère. Holton serait un bon choix pour les échantillons d'avion si une simple image est utilisée à la place de la carte de l'environnement. Une exigence obligatoire pour l'échantillonnage de Hammersley est l'inversion des racines (rangée) de van der Corpute, pour plus de détails, voir les liens
2 . Voici sa mise en œuvre rapide:
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
Ensuite, nous utilisons une superposition uniforme sur la sphère:
def sphereSample(u, v): PI = 3.14159265358979 phi = v * 2.0 * PI cosTheta = 2.0 * u - 1.0
Pour échantillonner Hammersley, nous utilisons un nombre fixe d'échantillons, en fonction de la résolution de l'image, et convertissons des coordonnées sphériques en cartésiennes, puis en équidistantes:
samplesMultiplier = 0.006 samples = int(samplesMultiplier * width * height) samplesList = []
Cela nous donnera une bonne répartition des échantillons qui seront vérifiés pour la présence de sources lumineuses:
Filtrage des sources lumineuses
Lors de la première passe de filtrage, nous ignorons tous les échantillons qui ne dépassent pas le seuil de luminosité (pour les cartes HDR, il peut être supérieur), puis trions tous les échantillons selon leur luminosité:
localSize = int(float(12) * (width / 1024.0)) + 1 samplesList = []
Le prochain passage filtrera en fonction de la métrique euclidienne et de la distance de seuil entre les pixels (en fonction de la résolution de l'image) - il s'agit d'une structure de données spatiales qui peut être utilisée pour se débarrasser de la complexité O (N
2 ):
euclideanThreshold = int(float(euclideanThresholdPixel) * (width / 2048.0))
Les échantillons résultants passent par l'étape de fusion pour réduire davantage le nombre de sources lumineuses:
Fusion de sources lumineuses
À la dernière étape, la fusion d'échantillons appartenant au même groupe d'éclairage est effectuée. Pour ce faire, nous pouvons utiliser l'algorithme de Bresenham et commencer par les échantillons avec la luminosité la plus élevée, car ils sont déjà commandés. Lorsque nous trouvons une source de lumière qui satisfait au test de Bresenham, nous utilisons sa position pour changer la position de la source en fonction du poids de la course:
La fonction Bresenham recherche une ligne continue qui a la même luminosité. Si le delta du pixel actuel dépasse un certain seuil, la vérification échoue:
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):
Il convient de noter que, si nécessaire, des améliorations peuvent être apportées au test de Bresenham, ce qui conduira à une meilleure fusion des échantillons, par exemple, il peut prendre en compte le transfert horizontal des sources de lumière situées sur les bords de l'image. De plus, la fonction peut être facilement étendue afin qu'elle se rapproche de la zone des sources lumineuses. Autre amélioration: vous pouvez ajouter un seuil de distance pour ne pas combiner des échantillons trop éloignés. Résultats finaux:
Le bleu indique les maxima locaux des groupes d'éclairage, le bleu représente les positions finales des sources lumineuses et le rouge désigne les échantillons qui font partie du même groupe d'éclairage et sont reliés par des lignes.
Autres exemples de résultats:
- Détection de sources lumineuses dans les photographies numériques par Maciej Laskowski
- Points Hammersley sur l'hémisphère par Holger Dammertz
- Projection équirectangulaire de Paul Reed
- Échantillonnage avec Hammersley et Halton Points par Tien-Tsin Wong