هل يجب أن تكتب قيمة كل بكسل إذا كانت مساحة كبيرة من الصورة بلون واحد؟ سنصنع صورة صغيرة، ونحتفظ بوصف مناطقها ثم نعيد رسم الخانات منها. وبعد أن يبدو الوصف مختصرًا، سنضع أمامه صورة شطرنجية تكشف كلفته. المطلوب مقارنة تمثيلين محددين، لا إعلان طريقة رابحة لكل الصور.
الخلاصة السريعة
- صورتنا ثنائية من 64 خانة؛ الأسود قيمته 1 والأبيض 0.
- تتحول إلى شجرة فيها عقدتان داخليتان وسبع أوراق، أي تسع عقد.
- نثبت ترتيب الأرباع: شمال غرب، شمال شرق، جنوب غرب، جنوب شرق.
- في صيغة اخترعناها للتمرين، تحتاج الصورة 21 بتًا قبل الحشو، وتُخزن في 3 بايتات.
- الصورة الشطرنجية بالحجم نفسه تحتاج 22 بايتًا بهذه الصيغة، مقابل 9 في تمثيلنا المباشر.
ما الذي يمثله فرع الشجرة؟
تصف OpenDSA الشجرة الرباعية للمناطق بوصفها تقسيمًا منتظمًا للصورة إلى أرباع؛ يستمر تقسيم المنطقة التي تضم أكثر من لون أو قيمة. لذلك يختلف قرار التقسيم هنا عن شجرة توزع نقاطًا منفردة في المكان. [1]
يمثل الجذر الصورة كلها، وتمثل الورقة منطقة متجانسة. يعرض Samet و Rosenfeld هذا البناء للصورة الثنائية، مع ترتيب الأبناء شمال غرب ثم شمال شرق ثم جنوب غرب ثم جنوب شرق. نلتزم بهذا الترتيب في تمريننا. [2]
ارسم مربعًا من ثمانية صفوف وثمانية أعمدة. لوّن الربع العلوي الأيسر أسود، واترك العلوي الأيمن أبيض. لوّن السفلي الأيمن أسود أيضًا. بقي الربع السفلي الأيسر: قسمه إلى أربعة مربعات من صفين وعمودين، ولوّن الأول والأخير وفق ترتيبنا أسود، واترك الاثنين الآخرين أبيض.
تحقق من آخر أربعة صفوف بدل الاكتفاء بشكل قريب. الصفان 4 و 5 يحتويان من اليسار 1 1 0 0 1 1 1 1. الصفان 6 و 7 يحتويان 0 0 1 1 1 1 1 1. أما الصفوف من 0 إلى 3 فتتكرر فيها 1 1 1 1 0 0 0 0. هذه الأسطر هي مرجعنا عند إعادة البناء.
احسب العقد قبل الحديث عن الحجم
الصورة الكاملة ليست متجانسة، فتحتاج عقدة تقسيم واحدة. ثلاثة من أرباعها لا تحتاج أبناء: مربع أسود علوي أيسر، وأبيض علوي أيمن، وأسود سفلي أيمن. الربع السفلي الأيسر مختلف داخله، فنضيف له عقدة تقسيم ثانية وأربع أوراق جديدة.
إجمالي الأوراق ثلاث كبيرة وأربع صغيرة، أي سبع. ومع عقدتي التقسيم يصبح العدد تسعًا. راجع مساحة الأوراق مستقلة عن شكل الشجرة: ثلاث مناطق مساحة كل منها 16 تعطي 48 ، وأربع مناطق مساحة كل منها 4 تعطي 16 ؛ المجموع 64. لا تتداخل المناطق، وتغطي صفوف الصورة وأعمدتها جميعًا.
اختر صيغة يمكنك عدّها
لن نفترض أن العقدة تأخذ بايتًا أو أن اسمها النصي مجاني. نخترع صيغة تعليمية محددة: 00 لورقة بيضاء، و01 لورقة سوداء، و10 لعقدة تقسيم، ونحجز 11 دون استعمال. هذه ليست صيغة ملف شائعة ولا مواصفة من المصدرين؛ إنها اتفاق صنعناه كي تصبح المقارنة قابلة للحساب.
نكتب ثلاثة بتات في البداية تخبرنا بأسّ طول الضلع: القيمة 3 تعني طولًا يساوي ثمانية، لأن 2³ = 8. تمثلها البتات 011. تقبل هذه الترويسة في تمريننا أسسًا من 0 إلى 7 ، ولا تسجل اسم ملف أو زمن تصوير أو ألوانًا أخرى. كل من يقرأ البيانات يعرف اتفاق الرموز مسبقًا.
بعد الترويسة نكتب رمز الجذر، ثم نزور أبناءه بالترتيب المحدد، وننهي جميع أبناء أي عقدة قبل الانتقال إلى أخيها التالي. لهذه الصورة يصبح سطر الرموز: 10 01 00 10 01 00 00 01 01. الرمز الرابع هو عقدة الربع السفلي الأيسر، والأربعة التي تليه أوراقه؛ الرمز الأخير يعود إلى الربع السفلي الأيمن الكبير.
تسعة رموز، في كل منها بتان، تعطي 18 بتًا. أضف الترويسة لتحصل على 21 بتًا. نخزن بايتات كاملة، فنضيف ثلاثة أصفار للحشو حتى 24 بتًا، أي 3 بايتات. إذا جمعت البتات وفق هذا الاتفاق، فإن كتابتها الست عشرية هي 72 48 28. الصفر في الحشو ليس ورقة بيضاء إضافية.
أعد الصورة من الوصف وحده
أخف الرسم والصفوف المكتوبة، واترك سطر الرموز والترويسة. يبدأ القارئ بمساحة 8×8 ، ويقرأ 10 فيفتح أربع مساحات 4×4. الرمز 01 يملأ الأولى بالأسود، و00 يترك الثانية بيضاء. عند الرمز الرابع يفتح داخل المساحة الثالثة أربع مساحات 2×2.
املأ هذه المربعات الصغيرة بالأسود والأبيض والأبيض والأسود، ثم عد إلى المستوى السابق. بقي الربع الكبير الرابع، ورمزه الأسود الأخير. بهذا استهلكنا الشجرة كلها؛ لا نواصل تفسير أصفار الحشو. قارن الصفوف الثمانية بالمرجع، وخاصة الحد بين الصفين 5 و 6 في الجزء الأيسر.
لو بدّلت ترتيب الربعين السفليين أثناء الاستعادة، فقد تنتهي بصورة لها عدد الخانات السوداء نفسه ولكن ترتيبًا مختلفًا. لذلك اختبر المطابقة خانة بخانة، لا مجموع الأسود فقط. في نموذجنا نراجع أيضًا أن كل خانة كُتبت مرة واحدة، كي لا يخفي تداخل المناطق فراغًا في موضع آخر.
قارنه بتمثيل مباشر واضح
البديل الذي نقارنه به يضع الترويسة الثلاثية نفسها ثم 64 بتًا، واحدًا لكل خانة بالترتيب صفًا بعد صف. مجموعه 67 بتًا، ويحتاج 9 بايتات مع الحشو. إذن 3 مقابل 9 نتيجة صحيحة لاتفاقينا ولهذه الصورة؛ لا نقارنها بحجم ملف PNG أو صورة هاتف تحتوي معلومات لم تدخل تجربتنا.
| الصورة | العقد | البتات مع الترويسة | البايتات بعد الحشو |
|---|---|---|---|
| تمريننا | 9 | 21 | 3 |
| لون واحد | 1 | 5 | 1 |
| شطرنجية | 85 | 173 | 22 |
| تغيير خانة واحدة | 17 | 37 | 5 |
في الصورة ذات اللون الواحد لا نحتاج تقسيمًا: رمز ورقة واحد مع الترويسة يساوي 5 بتات، فنخزن بايتًا. أما الشطرنجية، حيث تتناوب القيمتان أفقيًا ورأسيًا، فلا يوجد مربع 2×2 متجانس. تصبح العقد الداخلية واحدة في القمة وأربعًا تحتها وست عشرة بعدها؛ مجموعها 21 ، وتحتها 64 ورقة منفردة.
إذن لدينا 85 عقدة، أي 170 بتًا للرموز، ثم ثلاثة للترويسة:173 بتًا. نملأ حتى 176 بتًا فنحصل على 22 بايتًا. في هذه الحالة يتفوق التمثيل المباشر ذو التسعة بايتات. بقاء عدد البكسلات 64 في الصورتين لا يجعل عدد العقد متساويًا.
تغيير صغير يكشف حساسية البنية
عد إلى صورتنا الأصلية، وغيّر الخانة عند الصف 0 والعمود 0 من الأسود إلى الأبيض. الربع العلوي الأيسر لم يعد موحدًا؛ ينقسم إلى أربعة. وطفله العلوي الأيسر يحتاج تقسيمًا آخر كي يعزل الخانة المعدلة. نستبدل ورقة واحدة ببنية ذات تسع عقد، فتزداد الشجرة ثماني عقد، من 9 إلى 17.
تصبح الكلفة 34 بتًا للرموز، و 37 مع الترويسة، وخمسة بايتات بعد الحشو. هذه نتيجة تغيير اخترناه وموقعه معلوم؛ لا نزعم أن كل تغيير لبكسل واحد يضيف المقدار نفسه. راجعنا الحالات الأربع بالترميز والاستعادة، وفحصنا رفض رمز محجوز أو تقسيم خانة منفردة. التحقق يخص صورة ثنائية وصيغتنا المحددة، دون قياس سرعة أو تجربة على مكتبة صور.