التعرف على مصادر الضوء على خرائط البيئة

تقدم هذه المقالة تطبيق Python للخوارزمية للتعرف على مصادر الضوء على خرائط البيئة (LDR أو HDR) باستخدام الإسقاط المتماثل. ومع ذلك ، بعد إجراء تغييرات طفيفة ، يمكن استخدامه أيضًا مع صور خلفية بسيطة أو خرائط مكعبة. أمثلة على التطبيق المحتمل للخوارزمية: برامج تتبع الشعاع التي من الضروري فيها التعرف على مصادر الضوء الأساسية من أجل إصدار أشعة منها ؛ في عارض البيانات المنقطة ، يمكن استخدامه لإلقاء الظلال باستخدام خريطة بيئة ؛ بالإضافة إلى ذلك ، يمكن أيضًا استخدام الخوارزمية في برامج إزالة الأضواء ، على سبيل المثال في AR.

تتكون الخوارزمية من الخطوات التالية:

1. إنقاص دقة الصورة الأصلية ، على سبيل المثال ، إلى 1024.
2. تحويل الصورة إلى سطوع (النصوع) ، إذا لزم الأمر ، مع طمس الصورة.
3. تطبيق طريقة شبه مونت كارلو.
4. التحول من الإحداثيات الكروية إلى الإحداثيات متساوية.
5. تصفية العينات بناءً على سطوع أحد الجيران.
6. فرز العينات بناء على سطوعها.
7. تصفية العينات على أساس متري الإقليدية.
8. دمج العينات باستخدام خوارزمية Bresenham.
9. حساب موقع مجموعة الإضاءة على أساس سطوعها.

هناك العديد من الخوارزميات لتقليل دقة الصور. تعد تصفية Bilinear هي الأسرع أو الأسهل في التنفيذ ، إلى جانب ذلك ، تكون الأنسب في معظم الحالات. لتحويل السطوع في كل من صور LDR و HDR ، يمكنك استخدام الصيغة القياسية:

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

بالإضافة إلى ذلك ، يمكنك تطبيق تمويه بسيط على صورة السطوع ، على سبيل المثال ، 1-2 بكسل لصورة بدقة 1024 ، لإزالة جميع تفاصيل التردد العالي (على وجه الخصوص ، بسبب انخفاض الدقة).

الإسقاط متساوية

الإسقاط الأكثر شيوعًا في خرائط البيئة هو الإسقاط المتساوي ³ . يمكن أن تعمل الخوارزمية الخاصة بي مع الإسقاطات الأخرى ، على سبيل المثال ، مع الخرائط البانورامية والمكعبات ، ومع ذلك ، في المقالة سننظر فقط في إسقاط متباعد متساوية. تحتاج أولاً إلى تطبيع إحداثيات الصورة:

 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 ² :


يمكنك استخدام طرق أخذ العينات الأخرى ، مثل Holton ⁴ ، ولكن هامرسلي أسرع ويوفر توزيعًا جيدًا للعينات عبر الكرة. سيكون Holton اختيارًا جيدًا لعينات المستوى إذا تم استخدام صورة بسيطة بدلاً من خريطة البيئة. من المتطلبات الإلزامية لأخذ عينات Hammersley هو قلب جذر van der Corpute (صف) ، لمزيد من التفاصيل ، انظر الروابط ² . هنا هو التنفيذ السريع:

 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 ، نستخدم عددًا ثابتًا من العينات ، استنادًا إلى دقة الصورة ، ونتحول من الإحداثيات الكروية إلى الديكارتية ، ومن ثم إلى equidistant:

  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) 

سيؤدي التمرير التالي إلى التصفية استنادًا إلى مقياس Euclidean والمسافة بين البيكسلات (اعتمادًا على دقة الصورة) - وهي بنية بيانات مكانية يمكن استخدامها للتخلص من التعقيد O (N ² ):

  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. الكشف عن مصادر الضوء في الصور الرقمية بواسطة ماسيج لاسكوفسكي
2. هامرسلي نقاط على نصف الكرة التي كتبها هولجر Dammertz
3. الإسقاط المتساوي بواسطة بول ريد
4. أخذ العينات مع هامرسلي وهالتون بوينتس من تيان تسين وونغ