VQ: Vector Quantization
چندی سازی برداریVQ: Vector Quantization
چندی سازی برداریالگوریتم (LBG Linda-Buzo-Gray)
الگوریتم LBG در واقع یک الگوریتم رقمی سازی برداری(vector quantization) می باشد که به کمک آن می توان یک codebook مناسب تهیه کرد. Codebook به دست آمده در حقیقت مجموعه مراکز بازه های رقمی سازی می باشد. این روش شبیه روش k-means در خوشه بندی (data clustering) می باشد.
الگوریتم LBG در حقیقت یک الگوریتم پیمایشی می باشد و به منظور رفع مشکل خوشه بندی پیشنهاد گردید که به آن الگوریتم لوید تعمیم یافته نیز گفته می شود. این الگوریتم توسط لیند و همکارانش در سال 1982 مطرح گردید که قادر است به طور قابل قبولی بر مشکل k-mean غلبه کند. مراحل این الگوریتم به صورت زیر می باشد.
1. تعداد خوشه ها مشخص می گردد و در ابتدا M= 1 قرار می دهیم
2. برای تمام داده ها بردار مرکز محاسبه می گردد.
3. تا زمانی که تعداد خوشه ها برابر تعداد تعین شده نشده باشد هر یک از M بردار مرکز به 2 بردار جدید شکسته می شود تا 2M بردار مرکز تولید گردد. هر بردار جدید بایستی درون همان خوشه قرار داشته باشد و به اندازه کافی از هم دور باشند.
4. شرط خاتمه : زمانی که M برابر تعداد خوشه مورد نظر الگوریتم LBG باشد الگوریتم خاتمه می یابد و در غیر این صورت به مرحله 2 می رود و الگوریتم را تکرار می کند.
با یک مثال الگوریتم توضیح می دهیم در این مثال به جای تعیین تعداد خوشه به عنوان شرط خاتمه از شرط عدم تغییر در اطلاعات استفاده می کنیم
کتاب کد
|
weight |
height |
|
|
50 |
45 |
1 |
|
180 |
80 |
2 |
|
117 |
45 |
3 |
|
weight |
height |
|
|
41 |
44 |
a |
|
117 |
59 |
b |
|
110 |
60 |
c |
|
180 |
72 |
d |
|
180 |
64 |
e |
|
182 |
80 |
f |
برای هر نقطه فاصله آن تا هر یک از نقاط کتاب کد را محاسبه می کنیم و نقطه ای را انتخاب می کنیم که کمترین فاصله را داشته باشد.
For a (44,41):
Point 1: (45-44)2 +(50-41)2 = 1+81=82
Point 2: (80-44)2 +(180-41)2 = 1296+19321=20617
Point 3: (45-44)2 +(117-41)2 =1+5776=5777
For b (59,117)
Point 1: (45-59)2 + (50-117)2 =196+4489 = 4698
Point 2: (80-59)2 +(180-117)2 =440
Point 3: (45-59)2 +(117-117)2 = 196
For c (60,110)
Point 1: (45-60)2 + (50-110)2 =225+3600=3825
Point 2: (80-60)2 +(180-110)2 =400+4900=5300
Point 3: (45-60)2 +(117-110)2 =225+49=274
For d (72,180)
Point 1: (45-72)2 +(50-180)2 =729+16900=17629
Point 2: (80-72)2 +(180-180)2 =64
Point 3: (45-72)2 +(117-180)2 =729+3969=4698
For e (64,180)
Point 1: (45-64)2 +(50-180)2 = 361+16900=17261
Point 2: (80-64)2 +(180-180)2 = 256
Point 3: (45-64)2 + (117-180)2 = 361 + 3969 = 4330
For f (80,182)
Point 1: (45-80)2 + (50-182)2 = 1225 + 17424 = 18649
Point 2: (80-80)2 +(180-182)2 = 4
Point 3: (45-80)2 + (117-182)2 = 1225 + 33124 = 34349
Regine 1 => (44,41)
Regine 2 => (72,180), (64,180), (80,182)
Regine 3 => (59,117), (60,110)
حال نقاط جدید کتاب کد را محاسبه می کنیم
Regine 1 = (44,41)
Regine 2 = (72,180)
(72,180), (64,180), (80,182)
Regine 3 = (72,180)
(59,117), (60,110)
کتاب کد
|
weight |
height |
|
|
41 |
44 |
1 |
|
180 |
72 |
2 |
|
113 |
59 |
3 |
|
Regine |
weight |
height |
|
|
1 |
41 |
44 |
a |
|
3 |
117 |
59 |
b |
|
3 |
110 |
60 |
c |
|
2 |
180 |
72 |
d |
|
2 |
180 |
64 |
e |
|
2 |
182 |
80 |
f |
عملیات فوق را تکرار می کنیم
For a (44,41)
Point 1: (44-44)2 + (41-41)2 = 0
Point 2: (72-44)2 + (180-41)2 = 784 + 19321 = 20105
Point 3: (59-44)2 + (113-41)2 = 225 + 5184 = 5409
For b (59,117)
Point 1: (44-59)2 + (41-117)2 = 225 + 5776 = 6001
Point 2: (72-59)2 + (180-117)2 = 169 + 3969 = 4138
Point 3: (59-59)2 + (113-117)2 = 16
For c (60,110)
Point 1: (44-60)2 + (41-110)2 = 256 + 7461 = 5017
Point 2: (72-60)2 + (180-110)2 = 144 + 4900 = 5044
Point 3: (59-60)2 + (113-110)2 = 1 + 9 =10
For d (72,180)
Point 1: (44-72)2 + (41-180)2 = 784 + 19321 = 20105
Point 2: (72-72)2 + (180-180)2 = 0
Point 3: (59-60)2 + (113-180)2 = 1 + 4489 = 4490
For e (64,180)
Point 1: (44-64)2 + (41-180)2 = 400 + 19321 = 19721
Point 2: (72-64)2 + (180-180)2 = 64
Point 3: (59-64)2 + (113-180)2 = 25 + 4489 = 4514
For f (80,180)
Point 1: (44-80)2 + (41-180)2 = 1296 + 19321 = 20617
Point 2: (72-80)2 + (180-180)2 = 68
Point 3: (59-64)2 + (113-180)2 = 25 + 4489 =4514
Regine 1 => (44,41)
Regine 2 => (72,180), (64,180), (80,182)
Regine 3 => (59,117), (60,119)
حال نقاط جدید کتاب کد را محاسبه می کنیم
Regine 1 = (44,41)
Regine 2 = (72,180)
(72,180), (64,180), (80,182)
Regine 3 = (72,180)
(59,117), (60,119)
کتاب کد
|
weight |
height |
|
|
41 |
44 |
1 |
|
180 |
72 |
2 |
|
113 |
59 |
3 |
کتاب کد های به دست آمده در این مرحله با مرحله قبل برابر می باشد بنابراین این کتاب کد نهایی می باشد.
الگوریتم LBG
منابع
1- Compression for Multimedia
CAMBRIDGE UNIVERSITY PRESS Cambridge, New York, Melbourne, Madrid, Cape Town, Singapore, São Paulo, Delhi, Dubai, Tokyo Cambridge University Press The Edinburgh Building, Cambridge CB2 8RU, UK
2 - https://www.youtube.com/watch?v=_S-5M8Zf6hc
