Цифрлық бейненің негізгі мінездемелері

- Сегменттің ұзын  бұрмаланған  үлгісі жасалады, тіректі траекториямен  барлық кластың  бірмәнді сәйкестікке келтіріледі;

- Тіректі траекториямен және  қалғандармен арасындағы  шығарылымы бірегей  сәйкестік емес орында   дискретті  косинусоидальды түрлендіруге ұшырайды (ДКТ), ДКТ коэффициенттері квантталады ;

- Компрестелген  файл сегмент бойынша  кванттардың ұқсас әрекетті траекториясы класына, сегментті орналастыру коэффициенттері, үйлесімділіктің траектория коэффициенттері,  тіректі траекториядан ауытқу траектория класының орны және өлшемі  тиісті болады;

- Артықты болдырмау үшін алынған файл  ақпаратты жоғалтпай сығуға ұшырайды.

Үйлесімділіктің оптимальды  коэффициентін есептеу процесі

Траектория  үйлесімділігінің  оптимальды  коэффициентін есептеу процесін,  кросс-кадрлы  интерполяция әдісінің  5  қадамы  орындалуы үшін  қажетті болатын  ауытқулар санының  бар  кезінде қарастырамыз.  Есептеудің алгоритмі келесідей болады :

- траекториясының шектеуімен траектория үшін үйлесімділіктің  үлкен және кіші жеткілікті коэффициент мәндерін есептеу;

- Үйлесімділік коэффициенттің төменгі және жоғарғы шек массивін сұрыптау; 

- Сапаның ағынды және оптимальды көрсеткіштерін нолмен инициализациялау. Төменгі шек массивінің және жоғарғы шек массивінің ағынды позициясының  көрсеткішетірін массивтің бірінші элементіне қою;

- Коэффициенттің жоғарғы және төменгі массивінің  ағынды мәнін  салыстыру. Егер жоғарғы шек массивінің ағынды мәні үлкен немесе төменгі шек массивінің ағынды мәніне тең болса, онда сапаның ағынды позициясын көбейтеміз және төменгі шек массивінің ағынды мәнін алға  жылжытамыз.Кері жағдайда  сапаның ағынды мәнін азайтамыз және жоғарғы шек массивінің ағынды позициясын алға жылжытамыз;

- Сапаның ағынды және оптимальды сапасының  көрсеткіштерін салыстыру.Егер сапаның ағынды көрсеткіші оптимальдыға қарағанда  жақсы болса, онда  сапаның омтимальды көрсеткішіне ағынды көрсеткішті меншіктеу, ал төменгі шек массивінің алдыңғы мәнін  және жоғарғы шек массивінің ағынды мәнін бөліктің үлкен санның қиылысу  шегі деп есте сақтаймыз; 

- Тексеру: егер  төменгі шек массивінің ағынды позициясының  көрсеткіші массивтің  шегінен тыс  позицияны көрсетсе, онда іздеу аяқталады. Кері жағдайда  төртінші қадамға өту жүргізіледі және іздеу жалғасады.

Бұл алгоритмде бірінші қадам  үйлесімділік  коэффициент мәнінің жиынына бағытталады,  ал қалғандары √  осындай бөліктердің  қиылысу санының үлкенін табуға бағытталады.  Алынған қиылысу  √ бұл  траектория үйлесімділік коэффициенттерінің жиыны , ол (3) формуланы қанағаттандырады, ал бұл  қиылысудан тұрмайтын, бөліктердің саны  екінші траекторияның лақтыру саны болып табылады, яғни  траекториялар арасындағы арақашықтық   дельтамен    ( бұл  √ сапаның оптимальды көрсеткішін есептеген мәнінің  сегменттегі қиылысудың толық санына дейінгі  сан болып табылады).

Үйлесімділік әрекеті бар бірінші класс траекториясының орындалуын M пикселді  биіктігі бар, ені N пикселді  және уақытты жалғастыруы T кадры бар сегмент  үшін классикалық әдіспен  ( "әрбірі  әрқайсысымен "  таңдау әдісі)  есептейміз. Ең жақсы  траекторияны  іздеу үшін  (M*N)2  коэффициенттерді іздеу  операциясы қажет болады. Сонымен қатар Хоар жылдам  сұрыптауын қолдану  қолдану кезінде  , коэффициенттерді іздеу  операциясының қиындығы  мынаған тең болады:

- Коэффициенттердің  төменгі және жоғарғы шегін  есептеу  үшін салыстырудың және  орналастырудың 4*T операциясы, көбейту және бөлудің  4*T операциясы қажет;

- екі массивті сұрыптау үшін  салыстыру  2*T*l-g2(T) операциясы және  элементтерді орналастыру  T*l-g2(T) операциясы;

- интервалды және лақтыру сандарын іздеу үшін кем дегенде салыстырудың T операциясы қажет болады.

Сонымен нәтижесінде мынандай қиындық алынады: (M*N)2*(12*T+4*T*l-g2(T)+T) машиналық операциялар (элементтерді орналастыру операциялары екі машиналық операциялармен  орындалады ).

Осындай түрде, егер  512x384x30  өлшемді сегмент (фильмнің бір секундысы MPEG4 форматта)  үшін  үйлесімділік әрекеті бар  траекторияның бірінші класын  классикалық әдіспен  жасау қажет болса, бізге  ассемблер тілінде әдіспен орындалу кезінде және процессормен орындалу жиілігі 1ГГц болғанда  75 секунд уақыт қажет болады. Егер көптеген  дамыған процессорлер  кэш-жадпен жарты жиілікте  жұмыс істейтінін  ескеретін болсақ,  онда  салыстыру , ауыстыру және бөлу командаларынан басқа алгоритмнің орындалуы  үшін  75 секундқа тең болса,  онда алғашқы видеоны компрестеу жылдамдығы 4-8 есеге артады. Осымен байланысты үйлесімді әрекетті бірінші класты траекторияны жылдам жинау  қажеттілігі  туындайды.

Үйлесімді әрекетті класына  траекторияны жылдам жинаудың екі негізгі әдісін қарастырайық.

Кластарды блокт түрде  құру әдісі 

Әдіс траекторияның әрекетінің және уақыт бойынша бейне блоктардың  орналастыруының байланысына негізделген.  Егер  бірдей  қозғалатын  автокөлікті  қара  түсте  қарасақ, онда  көрші кванттардың қанықтық  функция траекториясы ұқсастау екендігін байқауға болады, олар бір- біріне қатысты  кейбір уақыт аралығына  ғана жылжытылған (сурет 10):

 

 

Сурет 10. Кластарды блокт түрде  құру әдісі 

 

Бұл уақыт аралығы объектінің қозғалыс жылдамдығына кері  пропорционалды болады. Осындай түрде, егер  қандайда бір  бейненің блогы бейненің тұрақты векторға жылжу жолымен  алдыңғы кадрдан  алынады, онда  блоктардың  траекториясы  тұрақты векторға жылжытылған блок  траекториясымен ұқсас екенін байқаймыз. Блок үшін мұндай жылжыту векторы болмауы мүмкін немесе бірнеше түрі болуы мүмкін. 

Жылжытудың  тұрақты векторының ерекше  мәні  -  бұл  √ (0,0)  мән бар болады. Алдыңғы кадрдан (0,0)  векторға жылжу жолымен алынған бейнелердің блогының  ерекшелігі  мынада, блоктың барлық ауданында қанықтықтың  жарқ етуі  берілген блоктың қанықтық пикселдерінің пропорциональды өзгеруіне әкеледі, блоктың ішіндегі  траектория үйлесімдігіне әсер етпейді.

 Берілген әдістің  артықшылығы, ол  шығарудың  шамалы  саны бар кезінде траекторияларға  жеңіл қатынауы   болып табылады.  

Жылжытудың артық  векторы  деп алдын ала қандайда бір себептер бойынша жылдыту векторын  таңдауды айтамыз.  Мысалы,  жылжытудың артық  векторы  ретінде біз  бейненің блогын алу үшін жиі қолданылатын жылжыту  векторды  таңдауға болады.

Мүмкін жылжыту векторлар арасында шығару орындарында жылжытудың артық векторы болмайды.

Мүмкін жылжыту векторларды іздеу үшін  әртүрлі жақсы танымал алгоритмдерді қолдануға болады.Олардан екеуі:

- фаза  корреляциялар әдісі;

- бейне блоктарын тікелей  салыстыру әдісі;

- фаза  корреляциялар әдісі

- әдіс Фурье түрлендіруін орналастыру теоемасына негізделген. Егер бір функция   (x0,y0) векторына орналастыру жолымен алынатын болса, онда келесі формуламен байланысты:

- 

 

 

-  F2*(x, y) сол және оң бөлігін көбейтеміз:

 

 

 

- Осыдан:

 

 

 

Сол жақ  бөлігі  - бұл  екі сигналдың нормалданған  бірігей спектральды  тығыздығы: f1 функциясы және  f2 функциясы.Енді сол жақтан  бастап  Фурьенің кері байланысы қызықтырады. Ол өздігінен  f1 және  f2  корреляционды  функцияны көрсетеді және  (x0, y0) нүктеде максимумға ие болады (сурет 11):

 

 

Сурет 11. Фурьенің кері байланысы

 

- Енді  егер  f1  орнына  кейбір кадрдың  блогында    пикселдер қанықтығының  функциясын  қою ,  f2  орнына  өлшем бойынша алдыңғы кадрдың  блогындағы пикселдер қанықтығының  функциясын  қою ,  (x0,y0)  екіншіге қатысты  бірінші блоктың жылжыту векторы болып табылады;

- Әдістің артықшылығы: әдіс алгоритмді  жағынан қарапайым,  Фурьенің жылдам түрлендіруін бейненің функциясын және корреляциялық функцияны есептеу үшін қолдану  арқылы  жоғары өнімділікке жетуге болады, әдіс  видеотізбекті  сегменттерге тиімді бөлуге мүмкіндік береді, ол әдісті иерархиялық  үйлесу әдісін бірігіп қолдану арқылы үлкен объектілердің жылдамдығын және бағытын табуға болады; 

- Сонымен қатар, әдістің көптеген кемшіліктері бар. Олардың  ішіндегі үлкені, бейненің екі блогы үшін корреляциялық функцияны есептеу  кезінде әдістің математикалық    табиғаты кванттардың қанықтық функциясын  толықтырады.  Осымен байланысты әдіс бейненің  үлкен аудандарының  бір біріне қатысты  кішігірім  жылжытуды табу үшін  қолданылады.Бейненің кіші  аудандардың  үлкен  жылжытуын табу үшін    фрагмент  векторын іздеу   облысын   алуға  қажет.  Мысалы,  8х8 пиксельді  квадраты  формалы бейненің ауданын  [-6, 6]х[-6, 6] пикселді  облыс  жылжытуын іздеу үшін,  кішігірім  жабылғылы облысты іздеу векторын  кішігірім  жабылған облысты іздеу  8х8 төрт квадтарттан тұрады (сурет 12):

 

 

- Мүмкін, жабық түрі:

 

Сурет 12. 8х8 пиксельді  квадраты 

 

- аса тиімді болып  көрсетіле береді, бірақ  ол олай емес,ол  жылжыту векторын іздеу  одблысын жабатын  блоктар шекарасындағы координаттардың белгісіздігіне рұқсат береді; 

- Алдыңғы мысалда  минимальды жабыны бар төсем келтірілген, блоктар шекара маңында корреляциялық функцияның бұрмалануына байланысты аса мықты жабынды қолдануға  болады.   Осының салдарынан ,  фазаларды корреляциялау әдісін қолдану үшін  жадтың  үлкен көлемі және үлкен есептегіш қуаттар талап етіледі;

Бейне блоктарын тікелей  салыстыру әдісі:

- Әдіс  берілген  блокпен және  оның  басқа кадрда жылжу векторын іздеу облысынан әрбір  векторға  жылжу арасындағы  ерекшелік  нормасын есептеуге  негізделген;

- Әдістің артықшылығына келесілер жатады: оның   қарапайымдылығы,  кіші облыстардың  үлкен  жылжуын  іздеу  кезінде  немесе бейненің  бірдей қозғалатын үлкен облыстарының   жоғарғы өнімділігі, жадқа аз талап қойылады. Бейненің үлкен облысы кезінде әдісті норманың жарты аддитивтіліктің қасиетін : бүтін блоктар үшін ғана емес,  тек  кейбір блоктың нүктелердің көпмүшесі  норманың айырмашылығын бірден есептеуді жүргізу, қолдану жолымен жылдамдатуға болады . Көптеген жағдайларда  мұндай тәсіл  жылжытудың  мүмкін  векторларының аз көпмүшесі бойынша іздеуді жылдамдатуға  әсер етеді;

- Әдістің кемшіліктері мыналар болып табылады: бейненің  үлкен облысының аз жылжуын іздеу кезінде төмен тиімділік, орындалуының қиындығы және әдістің  бір-біріне эквивалентті болмайтын блоктарды іздеуге бейімделуі.  Бұл жағдайда  норма болып табылмайтын және  жарты аддитивтіліктің қасиеті жоқ айырмашылықты қолдануға тура келеді.Траекториялар арасындағы арақашықтық  деп мұнда  (3) формула мағынасында түсіндірілмейді, сондықтан жинақтаудан кейін траекторияны сұрыптау бойынша қосымша жұмыс  талап етіледі және  жинақтау кезінде оған жатпай қалғандары  траектория класына қосылады; 

- Әдіс траекториялардың басты массивтерін анықтау үшін   және класқа дәл тиісті болған  ұқсас әрекетті тракторияларды анықтауға мүмкіндік беретін қосымша болып табылады. Қалған  траекторияларды ұқсас әрекетті басқа әдістер бойынша класқа жатқызу қажет;

- Әдістің алгоритмдік қиындығын есептеу қиындау болады, кездеспелі  блоктардың иерархия құрылымы  әртүрлі  видео тізбектер үшін ерекшеленеді. Кадрдың 8x8 өлшемді блоктарға  бөліну кезінде ең "нашар" жағдайдың қиындығын есептеу, бір- біріне қатысты траекторияның жылжу мүмкіндігін қарастырмаймыз;

- Қиындық = [көрші кадрлардың блоктарының пропорционалдылық коэффициентін есептеу қиындығы]+[блоктарды біріктіру қиындығы ]+[жасалған класқа  қалған траекторияларды жатқызу қиындығы]+[кластың траекториясын сүзгілеу қиындығы].

- (M*N/64) блоктар берілген. Әрбір блок √8*8*T√  үшін  пропорциональдылық коэффициенті  бөлу операциясы, салыстыру операциясы  8*8*T тең болады. Біріктіру  ұқсастық коэффициентін іздеу операциясынан қиындығы (M*N)2/4096 аспайтын,  ұқсас траекториясы бар блоктарға ғана жүргізіледі. Қалған траекторияларды жатқызу  және траектория класын сүзгілеу  қиындығы  - (M*N) ұқсастық коэффициентін іздеу операциясына тең болады. 

Әдістің соңғы алгоритмдік қиындығы :

- 3*M*N+M*N*(1+(M*N)/4096)*(12*T+4*T*l-g2(T)+T), бұл дегеніміз классикалық әдіске қарағанда төмен екендігін  көрсетеді.

Ұқсас әрекетті траектория кластарын каскадты жинау әдісі:

- Әдіс  траектория әрекетінің айырмашылығын  визуальды қабылдау тәсіліне  негізделген: бір біріне  кванттар жақын орналасса, соғұрлым траектория әрекетінің айырмашылығы білінеді . Әдістің идеясы кадрдың бүкіл аумағын  жеке бөліктерге бөлуден және осы бөліктердің ішінде  класқа траекторияны жинаудан  тұрады. Сосын, кадрдың осы бөліктерін  үлкен бөліктерге біріктіру, алдыңғы кезеңдерде алынған ұқсас әрекетті траектория класына тіректі траекторияларды жинау жүргізіледі. Процесс кадр бойынша толығымен  жүргізілмейінше тоқтамайды;

- Әдіс  кадрды облыстарға бөлу бойынша және әрбір кезеңде жиналған кластар өлшемі бойынша бірнеше модификациядан тұрады; 

- Кадрды облыстарға бөлудің  бірінші  және  қарапайым тәсілі жинаудың  әрбір  кезеңі үшін  кадрды  алдын ала белгілі облыстарға  априорлы бөлуге қатысты болады.Екінші тәсіл күрделі, әрбір келесі кезеңде кадрды бөлу  алдыңғы жинау кезеңінде алынған тіректі траектория  санына тәуелді болады.  Мысалы, жинау үшін траектория санын шектерге немесе облыстағы тіректі  траекторияларды  азайту қажет;

- Жиналатын  кластың  өлшемдерін  берудің  әдісінде екі тәсілді  көрсетуге болады. Бірінші тәсіл "класқа тиісті болатын траекторияларды жинау " принципіне негізделген. Мысалы, класқа жинаудың үш  кезең үшін 15 дельтамен және сегменттің ұзындығынан   30%   радиусы қажет, ал ұқсас әрекетті траектория кластары үшін  өлшемдер ретінде әрбір  кезеңде  5 тең болатын  дельтаны және сегмент ұзындығынан класс радиусы  10%  таңдауға болады. Осылай, жинаудан кейін  үшінші қорытынды кезеңде  біз   15-тен кем емес дельтаны және сегмент ұзындығынан класс радиусы  30%  класты  аламыз. Мұндай жинақтаудан кейін ұқсас әрекетті  траектория кластарының саны  артық болып кетеді, олардың артықтығын төмендету үшін кейбір кластардың бірігуін талап етеді: