أوكتري

الشجرة الثمانية هي بنية بيانات شجرية، حيث تحتوي كل عقدة داخلية على ثمانية أبناء بالضبط . تُستخدم الأشجار الثمانية غالبًا لتقسيم الفضاء ثلاثي الأبعاد عن طريق تقسيمه بشكل متكرر إلى ثمانية أجزاء ثمانية . تُعد الأشجار الثمانية نظيرًا ثلاثي الأبعاد للأشجار الرباعية . الكلمة مشتقة من " oct" (جذر يوناني يعني "ثمانية") + " tree" (شجرة ). تُستخدم الأشجار الثمانية بكثرة في الرسومات ثلاثية الأبعاد ومحركات ألعاب ثلاثية الأبعاد .

يقسم كل عقدة في شجرة ثمانية الأجزاء الفضاء الذي تمثله إلى ثمانية أجزاء . في شجرة ثمانية الأجزاء النقطية (PR) (المماثلة لشجرة رباعية الأجزاء النقطية)، تخزن العقدة نقطة ثلاثية الأبعاد صريحة ، وهي "مركز" التقسيم لتلك العقدة؛ وتحدد هذه النقطة إحدى زوايا كل من الأجزاء الثمانية. أما في شجرة ثمانية الأجزاء المصفوفية (MX) (المماثلة لشجرة رباعية الأجزاء)، فإن نقطة التقسيم هي ضمنيًا مركز الفضاء الذي تمثله العقدة. يمكن أن تمثل العقدة الجذرية لشجرة ثمانية الأجزاء النقطية فضاءً لانهائيًا؛ بينما يجب أن تمثل العقدة الجذرية لشجرة ثمانية الأجزاء المصفوفية فضاءً محدودًا بحيث تكون المراكز الضمنية محددة جيدًا. تجدر الإشارة إلى أن أشجار ثمانية الأجزاء تختلف عن أشجار k -d : فأشجار k -d تنقسم على طول بُعد، بينما تنقسم أشجار ثمانية الأجزاء حول نقطة. كما أن أشجار k -d ثنائية دائمًا، وهو ما لا ينطبق على أشجار ثمانية الأجزاء. تقدم الأشجار متعددة الأبعاد ^{[ 1 ]} طريقة لتعميم كل من الأشجار k -d والأشجار الثمانية، من خلال السماح بتقسيم مجموعة فرعية من الأبعاد عند كل مستوى دقة.

استُخدم تقسيم مكاني مشابه لتقسيم الشجرة الثمانية في عام 1934، في نظرية ويتني للتغطية في الرياضيات. ^{[ 2 ]} وقد كان دونالد ميغر رائدًا في استخدام الأشجار الثمانية في رسومات الحاسوب ثلاثية الأبعاد ، كما وصف ذلك في تقرير صدر عام 1980 بعنوان "ترميز الشجرة الثمانية: تقنية جديدة لتمثيل ومعالجة وعرض الأجسام ثلاثية الأبعاد العشوائية بواسطة الحاسوب"، ^{[ 3 ]} والذي حصل بموجبه على براءة اختراع عام 1995 (بتاريخ أولوية 1984 ) بعنوان "توليد صور عالي السرعة للأجسام الصلبة المعقدة باستخدام ترميز الشجرة الثمانية". ^{[ 4 ]}

• مستوى عرض التفاصيل في رسومات الحاسوب ثلاثية الأبعاد ^{[ 5 ]}
• الفهرسة المكانية
• البحث عن أقرب جار ^{[ 6 ]}
• الكشف الفعال عن التصادم في ثلاثة أبعاد
• استبعاد المخروط الناقص
• طريقة متعددة الأقطاب السريعة
• شبكة غير منظمة
• تحليل العناصر المحدودة
• شجرة ثمانية فوكسل متفرقة ^{[ 7 ]}
• تقدير الحالة ^{[ 8 ]}
• تقدير المجموعة ^{[ 9 ]}

تقوم خوارزمية تكميم الألوان باستخدام شجرة الأوكتري ، التي ابتكرها جيرفوتز وبورغاتوفر عام 1988، بتشفير بيانات ألوان الصورة على شكل شجرة أوكتري يصل عمقها إلى تسعة مستويات. تُستخدم أشجار الأوكتري لأن${\displaystyle 2^{3}=8}$يحتوي نظام RGB على ثلاثة مكونات لونية . يُحدد فهرس العقدة التي تتفرع منها الشجرة في المستوى الأعلى بصيغة تستخدم البتات الأكثر أهمية من مكونات اللون الأحمر والأخضر والأزرق، على سبيل المثال: 4r + 2g + b. يستخدم المستوى الأدنى التالي أهمية البت التالي، وهكذا. تُهمل البتات الأقل أهمية أحيانًا لتقليل حجم الشجرة.

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

يُقسّم مخطط الخوارزمية التكرارية الموضح أدناه ( بصيغة MATLAB ) مصفوفة من النقاط ثلاثية الأبعاد إلى مربعات على نمط شجرة ثمانية. يبدأ التنفيذ بمربع واحد يُحيط بجميع النقاط المُعطاة، ثم يُقسّم هذا المربع بشكل تكراري إلى مناطقه الثمانية في الشجرة الثمانية. يتوقف التكرار عند تحقق شرط خروج مُحدد. ومن أمثلة شروط الخروج هذه (الموضحة في الكود أدناه):

• عندما تحتوي الخانة على عدد أقل من عدد معين من النقاط
• عندما يصل الصندوق إلى الحد الأدنى من الحجم أو السعة بناءً على طول حوافه
• عندما يصل التكرار إلى الحد الأقصى لعدد التقسيمات الفرعية

دالة [أعماق_الصناديق، آباء_الصناديق، زوايا_الصناديق، صناديق_النقاط] = OcTree ( النقاط )binDepths = [ 0 ] % تهيئة مصفوفة لأعماق الخانات باستخدام هذه الخانة الأساسية binParents = [ 0 ] % هذه الخانة الأساسية ليست فرعًا من خانات أخرى binCorners = [ min ( points ) max ( points )] % تُحيط بجميع النقاط في فضاء XYZ pointBins (:) = 1 % في البداية، يتم تعيين جميع النقاط لهذه الخانة الأولى divide ( 1 ) % بدء تقسيم هذه الخانة الأولىدالة القسمة ( رقم الصندوق )إذا استوفى هذا المربع أيًا من شروط الخروج، فلا تقم بتقسيمه أكثر. binPointCount = nnz ( pointBins == binNo ) binEdgeLengths = binCorners ( binNo , 1 : 3 ) - binCorners ( binNo , 4 : 6 ) binDepth = binDepths ( binNo ) exitConditionsMet = binPointCount < value || min ( binEdgeLengths ) < value || binDepth > value if exitConditionsMet return ; % إنهاء الدالة التكرارية endوإلا، قسّم هذا الصندوق إلى 8 صناديق فرعية جديدة بنقطة تقسيم جديدة. newDiv = ( binCorners ( binNo , 1 : 3 ) + binCorners ( binNo , 4 : 6 )) / 2 for i = 1 : 8 newBinNo = length ( binDepths ) + 1 binDepths ( newBinNo ) = binDepths ( binNo ) + 1 binParents ( newBinNo ) = binNo binCorners ( newBinNo ) = [ أحد أزواج newDiv الثمانية مع minCorner أو maxCorner ] oldBinMask = pointBins == binNo % احسب أي النقاط في pointBins == binNo تنتمي الآن إلى newBinNo pointBins ( newBinMask ) = newBinNo % قسّم هذا الصندوق الذي تم إنشاؤه حديثًا بشكل متكرر divide ( newBinNo ) end

باستخدام قائمة الألوان الكاملة لصورة RGB ذات 24 بت كمدخل نقطي لتطبيق تحليل النقاط باستخدام شجرة الأوكتري الموضح أعلاه، يُظهر المثال التالي نتائج تكميم الألوان باستخدام شجرة الأوكتري. الصورة الأولى هي الأصلية (532818 لونًا مميزًا)، بينما الثانية هي الصورة المُكمّمة (184 لونًا مميزًا) باستخدام تحليل شجرة الأوكتري، حيث يُخصص لكل بكسل اللون الموجود في مركز خانة شجرة الأوكتري التي يقع فيها. بدلاً من ذلك، يمكن اختيار الألوان النهائية عند مركز جميع الألوان في كل خانة من خانات شجرة الأوكتري، إلا أن هذه العملية الحسابية الإضافية لا تُؤثر بشكل كبير على النتيجة المرئية. ^{[ 10 ]}

% قراءة الصورة الأصلية RGB Img = imread ( 'IMG_9980.CR2' ); % استخراج البكسلات كثلاثيات نقاط RGB pts = reshape ( Img , [], 3 ); % إنشاء كائن تجزئة OcTree باستخدام سعة خانة مستهدفة OT = OcTree ( pts , 'BinCapacity' , ceil (( size ( pts , 1 ) / 256 ) * 7 )); % إيجاد الخانات التي تمثل "عقدًا طرفية" في كائن الشجرة الثمانية leafs = find ( ~ ismember ( 1 : OT.BinCount , OT.BinParents ) & ... ismember ( 1 : OT.BinCount , OT.PointBins ) ); % إيجاد الموقع المركزي RGB لكل خانة طرفية binCents = mean ( reshape ( OT.BinBoundaries ( leafs , :) , [ ] , 3 , 2 ) , 3 ) ; % إنشاء صورة "مفهرسة" جديدة مع خريطة ألوان ImgIdx = zeros ( size ( Img , 1 ), size ( Img , 2 )); for i = 1 : length ( leafs ) pxNos = find ( OT . PointBins == leafs ( i )); ImgIdx ( pxNos ) = i ; end ImgMap = binCents / 255 ; % تحويل لون 8 بت إلى قيم RGB في MATLAB % عرض الصورة الأصلية ذات 532818 لونًا والصورة الناتجة ذات 184 لونًا figure subplot ( 1 , 2 , 1 ), imshow ( Img ) title ( sprintf ( 'Original %d color image' ,size ( unique ( pts , 'rows' ), 1 ))) subplot ( 1 , 2 , 2 ), imshow ( ImgIdx , ImgMap ) title ( sprintf ( 'Octree-quantized %d color image' , size ( ImgMap , 1 )))

• تقسيم الفضاء الثنائي
• التسلسل الهرمي للفترات المحددة
• كيوب 2: ساوربراتن ، محرك ألعاب ثلاثي الأبعاد تعتمد فيه الهندسة بشكل شبه كامل على الأشجار الثمانية.
• محرك الألعاب id Tech 6 هو محرك ألعاب ثلاثي الأبعاد يستخدم وحدات البكسل ثلاثية الأبعاد المخزنة في أشجار ثمانية.
• محرك Irrlicht يدعم عقد المشهد الثمانية
• مشكلة قياس كلي
• شجرة ثمانية خطية
• يحتوي OGRE على تطبيق لإدارة المشاهد باستخدام شجرة ثمانية
• رصف الطبقات الفرعية
• فوكسل
• كوادري

• مجلة أنظمة مايكروسوفت - التكميم الثماني
• تحديد كمية الألوان باستخدام الأشجار الثمانية في مجلة دكتور دوبز
• نظرة عامة على تحديد كمية الألوان في شجرة الأوكتري
• سوجان لال، ب.؛ أونيكريشنان، أ.؛ بولوز جاكوب، ك. (1998). "التنفيذ المتوازي لخوارزمية توليد شجرة ثمانية". وقائع المؤتمر الدولي لمعالجة الصور لعام 1998. ICIP98 (رقم التصنيف 98CB36269) . المجلد  3. الصفحات 1005-1009 . doi : 10.1109/ICIP.1998.727419 . ISBN  0-8186-8821-1. S2CID 195863788 . 
• توليد أشجار ثمانية من مسح نقطي مع تقليل فقدان المعلومات، بقلم: ب. سوجان لال، أ. أونيكريشنان، ك. بولوز جاكوب، المؤتمر الدولي السابع لـ IASTED 2001
• الأشجار الثمانية المتوازية لتطبيقات العناصر المحدودة (مؤرشفة بتاريخ 3 مارس 2016 على موقع Wayback Machine)
• فيديو: استخدام شجرة ثمانية في تقدير الحالة
• الأشجار الرباعية، والأشجار الثمانية، والأشجار المتعامدة ، فصل في مكتبة الخوارزميات الحسابية CGAL