تكميم متجه الهرم

📅 آخر تحديث: ٢٢ يوليو ٢٠٢٦
✍️ نُشر في: ٢٢ يوليو ٢٠٢٦
📷 يحتوي على 22 صور
الموسوعة الحرة

تُعدّ تقنية التكميم المتجهي الهرمي ( PVQ ) طريقةً تُستخدم في برامج ترميز الصوت والفيديو لتكميم ونقل متجهات الوحدة ، أي المتجهات التي يعرف المُفكِّك مقدارها بينما لا يعرف اتجاهها. كما يُمكن استخدام PVQ كجزء من نظام تكميم الكسب/الشكل ، حيث يتم تكميم مقدار المتجه واتجاهه بشكل منفصل. وُصفت تقنية PVQ لأول مرة عام 1986 في ورقة بحثية بعنوان "مُكمِّم متجهي هرمي" للمؤلف توماس ر. فيشر. [ 1 ]

تحسين تجانس توزيع نقاط PVQ عن طريقw{\displaystyle w}أو1/w{\displaystyle 1/w}قوة الإحداثياتصأنا→علامة⁡(صأنا)(|صأنا|)w{\displaystyle p_{i}\to \operatorname {sgn}(p_{i})(|p_{i}|)^{w}}[ 2 ] يوضح الرسم التخطيطي مجموعات النجوم لـشمال=3{\displaystyle N=3}الأبعاد والمكتوبك=11،16،23،32{\displaystyle K=11,16,23,32}المعيار L1

من عيوب طريقة PVQ أنها تعمل وفقًا لمسافة سيارة الأجرة (معيار L1). يمكن التحويل من وإلى المسافة الإقليدية الأكثر شيوعًا (معيار L2) عبر إسقاط المتجهات ، إلا أن ذلك ينتج عنه توزيع أقل انتظامًا لنقاط التكميم (تصبح أقطاب الكرة الإقليدية ذات البعد n أكثر كثافة من المناطق غير القطبية). [ 3 ] حتى عام 2010، لم تكن هناك خوارزمية فعالة معروفة للتكميم المتجهي المثالي (أي المنتظم) للكرة الإقليدية ذات البعد n. [ 4 ] يمكن تقليل هذا التباين بتطبيق تشويه، مثل القوة على مستوى الإحداثيات، قبل الإسقاط، مما يقلل متوسط ​​مربع خطأ التكميم بنسبة 10% تقريبًا. [ 2 ]

يتم استخدام PVQ في برنامج ترميز الصوت CELT (الموروثة في Opus ) وبرنامج ترميز الفيديو Daala .

ملخص

كشكل من أشكال التكميم المتجهي ، يحدد PVQ دفتر رموز مكون من M نقطة تكميم، يتم تعيين كلمة رمزية عددية صحيحة لكل منها من 0 إلى M − 1. هدف المشفر هو إيجاد كلمة الرمز لأقرب متجه، والذي يجب على المفكك فك تشفيره مرة أخرى إلى متجه.

يتكون دليل رموز PVQ من جميع النقاط ذات الأبعاد Nص→{\displaystyle {\vec {p}}}بإحداثيات عددية صحيحة فقط، مجموع قيمها المطلقة يساوي ثابتًا K (أي أن معيارها L1 يساوي K ). في تدوين بناء المجموعة :

S(شمال،ك)={ص→∈Zشمال:‖ص→‖1=ك}{\displaystyle S(N,K)=\left\{{\vec {p}}\in \mathbb {Z} ^{N}:\left\|{\vec {p}}\right\|_{1}=K\right\}}

أين‖ص→‖1{\displaystyle \left\|{\vec {p}}\right\|_{1}}يشير إلى معيار L1 لـص→{\displaystyle {\vec {p}}}.

في الوضع الحالي، تُشكّل المجموعة S سطح هرم ذي N بُعد. وإذا رغبنا، يُمكننا إعادة تشكيله إلى كرة عن طريق "إسقاط" النقاط على الكرة، أي عن طريق تطبيعها .

Sجسم كروي(شمال،ك)={ص→‖ص→‖2:ص→∈S(شمال،ك)}{\displaystyle S_{\text{sphere}}(N,K)=\left\{{\frac {\vec {p}}{\left\|{\vec {p}}\right\|_{2}}}:{\vec {p}}\in S(N,K)\right\}}

أين‖ص→‖2{\displaystyle \left\|{\vec {p}}\right\|_{2}}يشير إلى معيار L2 لـص→{\displaystyle {\vec {p}}}.

تؤدي زيادة قيمة المعامل K إلى المزيد من نقاط التكميم، وبالتالي عادةً ما ينتج عنها تقريب "أكثر دقة" لمتجه الوحدة الأصليv→{\displaystyle {\vec {v}}}على حساب استخدام كلمات ترميزية عددية أكبر تتطلب المزيد من البتات للإرسال.

مثال

لنفترض أننا نرغب في تكميم متجهات الوحدة ثلاثية الأبعاد باستخدام المعامل K = 2. يصبح دليل الترميز الخاص بنا كالتالي:

كلمة السرنقطةنقطة معيارية
0< − 2, 0, 0>< − 1.000, 0.000, 0.000>
1< − 1, − 1, 0>< − 0.707, − 0.707, 0.000>
2< − 1, 0, − 1>< − 0.707, 0.000, − 0.707>
3< − 1, 0, 1>< − 0.707, 0.000, 0.707>
4< − 1, 1, 0>< − 0.707, 0.707, 0.000>
5<0, − 2, 0><0.000, − 1.000, 0.000>
6<0, − 1, − 1><0.000, − 0.707, − 0.707>
7<0, − 1, 1><0.000, − 0.707, 0.707>
8<0, 0, − 2><0.000, 0.000, − 1.000>
كلمة السرنقطةنقطة معيارية
9<0, 0, 2><0.000, 0.000, 1.000>
10<0, 1, − 1><0.000, 0.707, − 0.707>
11<0, 1, 1><0.000, 0.707, 0.707>
12<0, 2, 0><0.000, 1.000, 0.000>
13<1, − 1, 0><0.707, − 0.707, 0.000>
14<1, 0, − 1><0.707, 0.000, − 0.707>
15<1, 0, 1><0.707, 0.000, 0.707>
16<1, 1, 0><0.707, 0.707, 0.000>
17<2, 0, 0><1.000, 0.000, 0.000>

(0.707 =2/2{\displaystyle {\sqrt {2}}/2}(مقربة إلى 3 منازل عشرية.)

لنفترض الآن أننا نرغب في إرسال متجه الوحدة <0.592, −0.720 , 0.362> (مقربًا هنا إلى 3 منازل عشرية، للتوضيح). وفقًا لدليل الشفرات الخاص بنا، فإن أقرب نقطة يمكننا اختيارها هي الكلمة المشفرة 13 (<0.707, −0.707 , 0.000>)، والتي تقع على بُعد 0.381 وحدة تقريبًا من نقطتنا الأصلية.

تؤدي زيادة قيمة المعامل K إلى زيادة حجم دفتر الرموز، مما يزيد عادةً من دقة إعادة البناء. على سبيل المثال، بناءً على كود بايثون الموضح أدناه، ينتج عن K = 5 (حجم دفتر الرموز: 102) خطأً قدره 0.097 وحدة فقط، بينما ينتج عن K = 20 (حجم دفتر الرموز: 1602) خطأً قدره 0.042 وحدة فقط.

كود بايثون

استيراد itertools و math من typing استيراد NamedTupleclass PVQEntry ( NamedTuple ): codeword : int point : tuple [ int , ... ] normalizedPoint : tuple [ float , ... ]دالة إنشاء دفتر رموز PVQ ( n : عدد صحيح ، k : عدد صحيح ) -> قائمة [ PVQEntry ]: """  خوارزمية بسيطة لإنشاء دفتر رموز PVQ ذي n بُعدًا مع k  نبضة.  تعقيد وقت التشغيل: O(k**n) "  "" ret = [] for p in itertools.product ( range ( -k , k + 1 ) , repeat = n ) : if sum ( abs ( x ) for x in p ) == k : norm = math.sqrt ( sum ( x ** 2 for x in p )) q = tuple ( x / norm for x in p ) ret.append ( PVQEntry ( len ( ret ) , p , q ) )إرجاع retدالة ` search_pvq_codebook ( codebook : list [ PVQEntry ] , p : tuple [ float , ... ] ) -> tuple [ PVQEntry , float ] ` :  خوارزمية بسيطة للبحث في دفتر رموز PVQ. تُرجع هذه الدالة النقطة  الأقرب إلى p في دفتر الرموز، وفقًا للمسافة الإقليدية.  ` ret = None min_dist = None for entry in codebook : q = entry.normalizedPoint dist = math.sqrt ( sum (( q [ j ] - p [ j ]) ** 2 for j in range ( len ( p ) ) ) ) if min_dist is None or dist < min_dist : ret = entry min_dist = dist`إرجاع القيمة ret ، min_distدالة مثال ( p : tuple [ float , ... ], k : int ) -> None : n = len ( p ) codebook = create_pvq_codebook ( n , k ) print ( "عدد إدخالات دفتر الرموز: " + str ( len ( codebook ))) entry , dist = search_pvq_codebook ( codebook , p ) print ( "أفضل إدخال: " + str ( entry )) print ( "المسافة: " + str ( dist ))φ = 1.2 θ = 5.4 x = math.sin ( φ ) * math.cos ( θ ) y = math.sin ( φ ) * math.sin ( θ ) z = math.cos ( φ ) p = ( x , y , z ) مثال ( p , 2 ) مثال ( p , 5 ) مثال ( p , 20 )​​​​​​​​​​

تعقيد

يمكن البحث في دليل رموز PVQ فييا(كشمال){\displaystyle O(KN)}[ 4 ] يمكن أيضًا إجراء التشفير وفك التشفير فييا(كشمال){\displaystyle O(KN)}استخداميا(ك+شمال){\displaystyle O(K+N)}الذاكرة. [ 5 ]

حجم دفتر الرموز يخضع للتكرار [ 4 ]

V(شمال،ك)=V(شمال-1،ك)+V(شمال،ك-1)+V(شمال-1،ك-1){\displaystyle V(N,K)=V(N-1,K)+V(N,K-1)+V(N-1,K-1)}

معV(شمال،0)=1{\displaystyle V(N,0)=1}للجميعشمال≥0{\displaystyle N\geq 0}وV(0،ك)=0{\displaystyle V(0,K)=0}للجميعك≠0{\displaystyle K\neq 0}.

يُعطى الحل المغلق بواسطة [ 6 ]

V(شمال،ك)=2شمال⋅2F1(1-ك،1-شمال;2;2).{\displaystyle V(N,K)=2N\cdot {}_{2}F_{1}(1-K,1-N;2;2).}

أين2F1{\displaystyle {}_{2}F_{1}}هي الدالة الهندسية الفائقة .

انظر أيضاً

مراجع

  1. ↑ فيشر، توماس ر. (يوليو 1986). "مُكمِّم متجه هرمي". معاملات IEEE في نظرية المعلومات . 32 (4): 568-583 . doi : 10.1109/TIT.1986.1057198 .
  2. 1 2 دودا، جاريك (2017). "تحسين مُكمِّم المتجهات الهرمي باستخدام إسقاط القوة". arXiv : 1705.05285 [ math.OC ].
  3. ↑ فالين، جان مارك (سبتمبر 2013). "التكميم المتجهي الهرمي لترميز الفيديو" (ملف PDF) . مؤسسة Xiph.Org . تم الاطلاع عليه في 4 أبريل 2021 .
  4. 1 2 3 فالين، جان مارك؛ تيريبري، تيموثي ب.؛ مونتغمري، كريستوفر؛ ماكسويل، غريغوري (يناير 2010). "برنامج ترميز عالي الجودة للكلام والصوت بتأخير أقل من 10 مللي ثانية". معاملات IEEE في معالجة الصوت والكلام واللغة . 18 (1): 58-67 . arXiv : 1602.05526 . doi : 10.1109/TASL.2009.2023186 . S2CID 11516136 . 
  5. ↑ تيريبري، تيموثي ب. (2009). "cwrs.c" . أوبوس . مؤسسة Xiph.Org . تم الاطلاع عليه في 6 أبريل 2021 .
  6. ↑ تيريبري، تيموثي ب. (ديسمبر 2007). "ترميز متجه النبض" . مؤسسة Xiph.Org . مؤرشف من الأصل في 30 سبتمبر 2019. تم الاطلاع عليه في 4 أبريل 2021 .