Көпөлшемді дискретті конволюция - Википедия - Multidimensional discrete convolution

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

Анықтама

Проблемаларды бекіту және негіздері

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

Дискретті-бағалы сигналдар үшін бұл конволюцияны келесі арқылы тікелей есептеуге болады:

Дискретті көпөлшемді конволюцияны қолдаудың шығыс аймағы екі кіріс сигналының тірегі мен өлшемдері негізінде анықталады.

Екі қарапайым екі өлшемді сигнал арасындағы конволюцияны визуалдау

Екі өлшемді конволюция операторының бірнеше қасиеттері келтірілген. Бұл сигналдар үшін кеңейтілуі мүмкін екенін ескеріңіз -өлшемдер.

Коммутативті меншік:

Қауымдастырылған мүлік:

Тарату қасиеті:

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

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

Ассоциативті қасиетті қолдану арқылы оны келесідей жазуға болады:

яғни каскадталған жүйеге эквивалентті импульстік жауап келесі жолмен беріледі:

Екі фигура каскадталған жүйелерді білдіреді. Сүзгілердің реті шығысқа әсер етпейтінін ескеріңіз.

Осындай талдауды төменде көрсетілген параллель жүйелер жиынтығында жасауға болады.

Параллель сүзгілер жиынтығы бар жүйе.

Бұл жағдайда:

Дистрибьюторлық заңды қолдана отырып:

Бұл параллель жүйе жағдайында эквивалентті импульстік жауап келесі жолдармен қамтамасыз етіледі дегенді білдіреді.

Каскадталған жүйелердегі және параллель жүйелердегі эквивалентті импульстік реакцияларды жүйелермен жалпылауға болады - сүзгілердің саны.[1]

Мотивация және қолдану

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

Мысалы, электро-оптикалық шудың әсерінен кейбір сымсыз желі арқылы жіберілетін суретті қарастырыңыз. Ықтимал шу көздеріне арнаның берілуіндегі қателіктер, аналогтан цифрлық түрлендіргішке және кескін сенсорына жатады. Әдетте канал немесе сенсор туындайтын шу кеңістіктен тәуелсіз, жоғары жиілікті сигнал компоненттерін жасайды, бұл нақты кескіннің ашық және қара дақтарына айналады. Кескін деректерін жоғары жиіліктегі спектрлік мазмұннан тазарту үшін оны конволюция теоремасына негізделген төменгі жиіліктегі сүзгінің жиіліктік реакциясына көбейтуге болады, бұл сигналды уақыт / кеңістіктік доменде шоғырландыруға тең. төменгі жиіліктегі сүзгінің импульстік реакциясы. Мұны жасайтын бірнеше импульстік жауаптар төменде көрсетілген.[2]

Әдеттегі көп өлшемді төмен жылдамдықты сүзгілердің импульстік жауаптары

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

Жиектерді анықтауға арналған импульстің әдеттегі жауаптары
Түпнұсқа кескін (сол жақта) және шетін анықтайтын сүзгіден өткен сурет (оң жақта)

Кескінді өңдеуден басқа, әртүрлі өлшемді конволюцияны басқа да қосымшаларды іске қосуға мүмкіндік береді. Сүзгілер сандық байланыс жүйелерінде кеңінен таралғандықтан, көп өлшемді деректерді жіберуге тиісті кез-келген жүйеге сүзгілеу техникасы көмектеседі, ол нақты уақыт режимінде бейнені өңдеуде, жүйке желісін талдау, сандық геофизикалық деректерді талдау және т.б.[3]

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

Түпнұсқа кескін (сол жақта) және бұлыңғыр сурет (оң жақта) Гаусс конволюциясы көмегімен орындалады

Бөлінетін сигналдармен қатарлы-бағаналы ыдырау

Бөлінетін сигналдар

Сигнал деп аталады бөлінетін егер оны бірнеше өлшемді сигналдардың көбейтіндісі ретінде жазуға болатын болса.[1] Математикалық тұрғыдан бұл келесідей көрінеді:

Кейбір оңай ажыратылатын сигналдарға блоктың қадамдық функциясы және дельта-дирак импульсі функциясы жатады.

(бірлік қадам функциясы)

(дельта-дирак импульсінің функциясы)

Конволюция - бұл сызықтық операция. Бұдан шығатыны, бөлінетін сигналдардың көп өлшемді конволюциясы көптеген бір өлшемді конволюциялардың көбейтіндісі ретінде көрсетілуі мүмкін. Мысалы, жағдайды қарастырайық х және сағ екеуі де бөлінетін функциялар.

Бөліну қасиеттерін қолдану арқылы оны келесідей етіп жазуға болады:

Сонда бұл бір өлшемді конволюциялардың көбейтіндісіне дейін азаяды:

Содан кейін бұл тұжырым екі ажыратылатынға дейін созылуы мүмкін М-өлшемдік сигналдар келесідей:

Сонымен, екі сигналды бөлуге болатын кезде, көп өлшемді конволюцияны есептеу арқылы есептеуге болады бір өлшемді конволюциялар.

Жол бағанының ыдырауы

Жол-баған әдісін конволюциядағы сигналдардың бірі бөлінетін кезде қолдануға болады. Әдіс әр үлгінің тікелей есептелуіне қарағанда (сигналдардың бірі бөлінетіндігін ескере отырып) есептеу тиімділігі жоғары екі көпөлшемді сигналдардың конволюциясын есептеу әдісіне жету үшін бөлінгіштік қасиеттерін пайдаланады.[4] Төменде жолдарды бағанмен ыдыратуға негізделген математикалық пайымдаулар көрсетілген (әдетте бұл бөлінетін сигнал):

Мәні енді басқаларын бағалау кезінде қайта қолдануға болады ортақ мәні бар мәндер :

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

Процессор берілген операцияға қажетті сигналдық деректерді жүктейді. Қазіргі заманғы процессорлар үшін деректер жадтан процессорлардың кэшіне жүктеледі, оның жадыға қарағанда қол жеткізу уақыты тезірек болады. Кэштің өзі жолдарға бөлінген. Кэш жолы жадтан жүктелген кезде, бірден бірнеше мәліметтер операндтары жүктеледі. Сигнал деректерінің қатары толығымен процессордың кэшіне сыйып кететін оңтайландырылған жағдайды қарастырайық. Бұл нақты процессор деректер қатарына тиімді қол жеткізе алады, бірақ бағандар бойынша емес, өйткені бір бағандағы әр түрлі операндтар әртүрлі кэш жолдарында орналасады.[5] Жадқа қол жеткізу тәсілін пайдалану үшін деректер жиынын ауыстырып, оны бағандар бойынша қол жеткізуге тырысқаннан гөрі, оны қатарлы етіп осьтеу тиімдірек. Алгоритм келесідей болады:

  1. Бөлінетін екі өлшемді сигналды бөліңіз екі өлшемді сигналға және
  2. Сигналдың көлденең компоненттері бойынша қатарлы конволюцияны орындаңыз қолдану алу
  3. Сигналдың тік компоненттерін ауыстырыңыз 2-қадамнан туындайды.
  4. Орналастырылған тік компоненттері бойынша қатарлы конволюцияны орындаңыз қажетті өнімді алу үшін

Бағаналы ыдырау кезіндегі есептеу жылдамдығы

Өлшемнің кескіні болған жағдайды қарастырыңыз көлемінің бөлінетін сүзгісі арқылы өтіп жатыр . Кескіннің өзі бөлінбейді. Егер нәтиже фильтрдің бөлінгіштігін пайдаланбай, тікелей конволюция тәсілін қолдана отырып есептелсе, бұл шамамен қажет болады көбейту және қосу. Егер сүзгінің бөлінгіштігі ескерілсе, сүзуді екі сатыда орындауға болады. Бірінші қадам болады көбейту мен толықтырулар және екінші қадам болады , нәтижесінде барлығы немесе көбейту және қосу.[6] Тікелей және бөлінетін конволюция арасындағы есептеу күрделілігін салыстыру келесі суретте келтірілген:

Есептеу саны a 10 x 10 Өлшем сүзгісі арқылы кескін J x K қайда J = K өлшемі бойынша өзгереді 1 дейін 10

Дискретті мәнді көпөлшемді сигналдардың шеңберлік айналуы

Көпөлшемді сигналдардағы дөңгелек конволюция тәсілінің алғышарты - арасындағы байланысты дамыту болып табылады Конволюция теоремасы және Дискретті Фурье түрлендіруі (DFT), бұл екі ақырлы, дискретті мәнді сигналдар арасындағы конволюцияны есептеу үшін қолданыла алады.[7]

Көп өлшемдегі конволюция теоремасы

Бір өлшемді сигналдар үшін Конволюция теоремасы деп мәлімдейді Фурье түрлендіруі екі сигнал арасындағы конволюция осы екі сигналдың Фурье түрлендірулерінің көбейтіндісіне тең. Сонымен, уақыт доменіндегі конволюция жиілік аймағындағы көбейтуге тең. Математикалық тұрғыдан бұл принцип келесі арқылы көрінеді:

Бұл принцип бірнеше өлшемді сигналдармен жұмыс істеуге тікелей қолданылады.
Бұл сипат тез пайдалануға кеңейтіледі Дискретті Фурье түрлендіруі (DFT) келесідей (сызықтық конволюция дөңгелек конволюциямен ауыстырылатынын ескеріңіз, мұндағы мөлшерінің дөңгелек конволюциясы жұмысын белгілеу үшін қолданылады ):

Бірнеше өлшемді сигналдармен жұмыс жасағанда:

Мұндағы дөңгелек конволюциялар өлшемі болады .

Конволюцияны дөңгелектеу тәсілі

Дөңгелек конволюция тәсілін қолданудың мотиві оның DFT-ге негізделгендігінде. Дөңгелек конволюцияның алғышарты - кіріс сигналдарының DFT қабылдап, оларды көбейтіп, содан кейін кері DFT қабылдайды. Мұқият болу керек, егер жеткілікті үлкен DFT қолданылса, онда лақап ат пайда болмайды. DFT ақырғы дәрежедегі сигналдармен жұмыс жасағанда сандық түрде есептелінеді. Бұл тәсілдің бір артықшылығы мынада: DFT және кері DFT алуды қажет ететіндіктен, тиімді алгоритмдерді қолдануға болады Жылдам Фурье түрлендіруі (FFT). Дөңгелек конволюцияны тек жиіліктік облыста ғана емес, уақыттық / кеңістіктік облыста да есептеуге болады.

2-ге тең дөңгелек конволюцияның блок-схемасы М- өлшемді сигналдар

Бүркендірмеу үшін DFT өлшемін таңдау

Екі ақырлы дәрежедегі сигналдарды қарастырайық х және сағ алынады. Екі сигнал үшін де сәйкесінше DFT бар:

және

Қолдау аймағы болып табылады және және қолдау аймағы болып табылады және .

Осы екі сигналдың сызықтық конволюциясы келесідей болады:

Қолдау аймақтарын ескере отырып және , қолдау аймағы содан кейін келесідей беріледі:

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

үшін

Нәтиже солай болады сызықтық конволюция нәтижесінің кеңістіктегі бүркеншік нұсқасы болады . Мұны келесі түрде білдіруге болады:

Содан кейін, кеңістіктегі бүркеншік репликалар арасында лақап ат қоймас үшін және келесі шарттарды қанағаттандыру үшін таңдалуы керек:

Егер бұл шарттар орындалса, онда айналмалы конволюцияның нәтижелері сызықтық конволюциямен тең болады (шеңбер конволюциясының негізгі кезеңін тірек аймағы ретінде қабылдайды). Бұл:

үшін

DFT-ді қолданудың қысқаша мазмұны

Конволюция теоремасы мен дөңгелек конволюцияны сызықтық конволюцияны орындауға тең нәтижеге жету үшін келесі тәсілмен пайдалануға болады:[8]

  1. Таңдау және қанағаттандыру және
  2. Сигналдарды нөлге қойыңыз және екеуі де солай өлшемі бойынша
  3. Екеуінің де DFT-ін есептеңіз және
  4. Алу үшін DFT нәтижелерін көбейтіңіз
  5. IDFT нәтижесі содан кейін екі сигнал бойынша сызықтық конволюцияны орындау нәтижесіне тең болады

Қабаттасу және қосу

Көп өлшемді конволюцияны жүзеге асырудың тағы бір әдісі - бұл қабаттасып қосыңыз тәсіл. Бұл әдіс қазіргі кездегі сандық жүйелерге тән деректердің үлкен көлеміне байланысты көп өлшемді консоляциялармен байланысты есептеу қиындығын азайтуға көмектеседі.[9] Қысқаша болу үшін мысал ретінде екі өлшемді жағдай қолданылады, бірақ бірдей ұғымдарды бірнеше өлшемге дейін кеңейтуге болады.

Тікелей есептеуді пайдаланып екі өлшемді конволюцияны қарастырыңыз:

Шығу сигналы деп есептейік нөлдік емес коэффициенттері бар, ал импульстік реакциялар нөлдік емес үлгілерден тұрады, бұл тікелей есептеу үшін MN көбейтілуі керек және есептеу үшін MN - 1 қосымшалары қажет болады. Оның орнына FFT қолдану арқылы фильтрдің жиілік реакциясы және кірістің Фурье түрлендіруі жадта сақталуы керек еді.[10] Есептеудің үлкен көлемдері және жадты сақтау кеңістігін шамадан тыс пайдалану проблемалық мәселені тудырады, өйткені қосымша өлшемдер қосылады. Мұнда қабаттасу және қосу конволюциясы әдісі келеді.

Шағын конволюциялық блоктарға ыдырау

Ақпаратты толығымен блоктаудың орнына ақпаратты өлшемдердің кіші блоктарына бөлуге болады х нәтижесінде FFT кішірейеді, есептеу қиындығы аз болады және сақтау орны аз болады. Мұны математикалық түрде келесі түрде көрсетуге болады:

қайда білдіреді х қосындысы болып табылатын кіріс сигналы блок сегменттері, және .

Шығу сигналын шығару үшін екі өлшемді конволюция орындалады:

Орнына ауыстыру нәтижесі:

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

Процедураның бұзылуы

Келіңіздер өлшемі болуы :

  1. Кірісті үзу қабаттаспайтын өлшем блоктарына .
  2. Нөл жастықшасы оның өлшемдері болатындай () ().
  3. Алу үшін DFT пайдаланыңыз .
  4. Әрбір кіріс блогы үшін:
    1. Нөл жастықшасы өлшемдер болуы керек () ().
    2. Беру үшін әр блоктың дискретті Фурье түрлендіруін алыңыз .
    3. Алу үшін көбейтіңіз .
    4. -Ның кері дискретті Фурье түрлендіруін алыңыз алу .
  5. Табыңыз қабаттасып және соңғысын қосу арқылы үлгілері біріншісімен үлгілері нәтиже алу үшін.[11]

Операцияның кескіндік әдісі

Қабаттастыру әдісін айқынырақ көру үшін келесі иллюстрациялар әдісті графикалық түрде қарастырады. Кіріс деп есептейік Төмендегі суретте көрсетілгендей тік және көлденең бағытта N ұзындығының квадраттық тірегі бар. Содан кейін ол төрт кішкене квадраттардан тұратын етіп төрт кішігірім сегменттерге бөлінеді. Жиынтық сигналдың әр блогының өлшемдері болады .

Шіріген кіріс сигналы

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

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

Импульстік жауаппен компоненттің жеке шешімі
Әр компоненттің бөлектелген қабаттасу бөліктерімен шешімі

Дәл осындай процесс қалған екі кіріс үшін де жасалады және олар конволюцияны қалыптастыру үшін жинақталады. Бұл сол жақта бейнеленген.

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

=

екі бағытта. Ашық көк бөлік көршілес екі конволюцияның қабаттасуымен корреляциялайды, ал көгілдір көгілдір бөлік төрт конволюцияның қабаттасуымен корреляцияланады. Барлық осы қабаттасқан бөліктер біріктірілген конволюцияны қалыптастыру үшін конволюцияларға қосымша қосылады .[12]

Қабаттасу және сақтау

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

Қабаттасу және қосу салыстыру

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

Бір өлшемде екі әдіс арасындағы өнімділік пен сақтаудың метрикалық айырмашылықтары минималды. Алайда көпөлшемді конволюция жағдайында жылдамдық пен сақтау қабілеті бойынша қабаттасуды қосу әдісінен гөрі қабаттасуды үнемдеу әдісі басым болады.[13] Қабаттасу және қосу жағдайындағы сияқты, процедура екі өлшемді жағдайға жүгінеді, бірақ барлық көпөлшемді процедураларға оңай таралуы мүмкін.

Процедураның бұзылуы

Келіңіздер өлшемі болуы :

  1. Кірістіру бағандар және кіріс сигналының басындағы нөлдер қатарлары екі өлшемде де.
  2. Сәйкес сигналды өлшемдердің қабаттасқан сегменттеріне бөлу ()() онда әрбір екі өлшемді блок қабаттасады .
  3. Нөл жастықшасы оның өлшемдері болатындай ()().
  4. Алу үшін DFT пайдаланыңыз .
  5. Әрбір кіріс блогы үшін:
    1. Беру үшін әр блоктың дискретті Фурье түрлендіруін алыңыз .
    2. Алу үшін көбейтіңіз .
    3. -Ның кері дискретті Фурье түрлендіруін алыңыз алу .
    4. Біріншісінен құтылыңыз әрбір шығыс блогы үшін .
  6. Табыңыз соңғысын қосу арқылы әрбір шығыс блогы үшін үлгілер .[11]

Спираль трансформациясы

Бағаналы ыдырауға ұқсас, спираль түрлендіру көпөлшемді конволюцияны бірөлшемді конволюциялық қасиеттер мен операторларды қосу арқылы есептейді. Сигналдардың бөлінгіштігін пайдаланудың орнына, ол декарттық координаттар кеңістігін көп өлшемді кеңістіктен бір өлшемді кеңістікке дейін бейнелеуге мүмкіндік беретін бұрандалы координаттар кеңістігіне түсіреді.

Бір өлшемді конволюция әдістерімен көп өлшемді конволюция

Спираль түрленуін түсіну үшін алдымен көп өлшемді конволюцияны бір өлшемді конволюцияға қалай бөлуге болатынын түсіну пайдалы. Шешілетін екі сигнал деп есептейік және нәтиже шығарады . Бұл келесідей көрінеді:

Әрі қарай екі матрицалар құрылады, олар екі өлшемдегі әрбір кірісті нөлге теңестіреді, сондықтан әрбір кіріс эквивалентті өлшемдерге ие болады, яғни.

және

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

+

+

Осы екі вектордың айналу ұзындығы, , шығарылуы және көрсетілуі мүмкін:

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

Спиральды сүзу

Екі өлшемді декарттық торда жұмыс істегенде, Фурьенің екі осі бойымен өзгеруі екі бағаналы жазықтық цилиндрге айналады, өйткені әрбір бағанның немесе жолдың соңы цилиндрді құрайтын тиісті шыңына бекітіледі. Спиральда сүзу ұқсас жағдайда жүреді, егер бұл жағдай болмаса, әр бағанның төменгі жағы келесі бағанның жоғарғы жағына бекітіледі, нәтижесінде бұрандалы тор пайда болады. Бұл төменде көрсетілген. Қараңғыланған плиткалар сүзгі коэффициенттерін білдіреді.

2D декартиялық сүзу жазығынан спиральді сүзгіге айналу.

Егер бұл спираль құрылымды кесіп алып, бір өлшемді жолаққа айналдырса, 2-д-декарттық жазықтықтағы бірдей сүзгі коэффициенттері бірдей кіріс деректерімен сәйкес келеді, нәтижесінде эквивалентті сүзу схемасы шығады. Бұл екі өлшемді конволюцияны бір өлшемді конволюция операторы орындай алатындығына кепілдік береді, өйткені 2D сүзгісі 1D сүзгісінде фильтр коэффициенттерін бөлетін нөлдік саңылаулармен ашылды.

Жарақатсыз болғаннан кейін бір өлшемді сүзу жолағы.

Кейбір төмен жылдамдықты екі өлшемді сүзгі қолданылған деп болжансақ, мысалы:

0-10
-14-1
0-10

Содан кейін, екі өлшемді кеңістікті спиральға айналдырғаннан кейін, бір өлшемді сүзгі келесідей болады:

Бір өлшемді сүзгіде бір өлшемді сүзгілеу жолағында көрсетілгеннен кейін алдыңғы нөлдер жоқ екеніне назар аударыңыз. Барлық бір өлшемді жолақты ширатуға болатын еді; дегенмен, жетекші нөлдерді елемеу есептеу үшін арзанға түседі. Сонымен қатар, бұл артқы нөлдік мәндердің ешқайсысы жадыда құнды жад ресурстарын сақтай отырып сақталмауы керек.[15]

Қолданбалар

Helix transformations to implement recursive filters via convolution are used in various areas of signal processing. Although frequency domain Fourier analysis is effective when systems are stationary, with constant coefficients and periodically-sampled data, it becomes more difficult in unstable systems. The helix transform enables three-dimensional post-stack migration processes that can process data for three-dimensional variations in velocity.[15] In addition, it can be applied to assist with the problem of implicit three-dimensional wavefield extrapolation.[16] Other applications include helpful algorithms in seismic data regularization, prediction error filters, and noise attenuation in geophysical digital systems.[14]

Gaussian Convolution

One application of multidimensional convolution that is used within signal and image processing is Gaussian convolution. This refers to convolving an input signal with the Gaussian distribution function.

2D Gaussian Visualization where және

The Gaussian distribution sampled at discrete values in one dimension is given by the following (assuming ):

This is readily extended to a signal of М dimensions (assuming stays constant for all dimensions and ):
One important property to recognize is that the М dimensional signal is separable such that:
Then, Gaussian convolution with discrete-valued signals can be expressed as the following:

Approximation by FIR Filter

Gaussian convolution can be effectively approximated via implementation of a Finite impulse response (FIR) filter. The filter will be designed with truncated versions of the Gaussian. For a two-dimensional filter, the transfer function of such a filter would be defined as the following:[17]

қайда

Choosing lower values for және will result in performing less computations, but will yield a less accurate approximation while choosing higher values will yield a more accurate approximation, but will require a greater number of computations.

Approximation by Box Filter

Another method for approximating Gaussian convolution is via recursive passes through a box filter. For approximating one-dimensional convolution, this filter is defined as the following:[17]

Typically, recursive passes 3, 4, or 5 times are performed in order to obtain an accurate approximation.[17] A suggested method for computing р is then given as the following:[18]

қайда Қ is the number of recursive passes through the filter.

Then, since the Gaussian distribution is separable across different dimensions, it follows that recursive passes through one-dimensional filters (isolating each dimension separately) will thus yield an approximation of the multidimensional Gaussian convolution. Бұл, M-dimensional Gaussian convolution could be approximated via recursive passes through the following one-dimensional filters:

Қолданбалар

Gaussian convolutions are used extensively in signal and image processing. For example, image-blurring can be accomplished with Gaussian convolution where the parameter will control the strength of the blurring. Higher values would thus correspond to a more blurry end result.[19] Ол сондай-ақ әдетте қолданылады Компьютерлік көру сияқты қосымшалар Масштаб-инвариантты түрлендіру (SIFT) feature detection.[20]

Сондай-ақ қараңыз

Әдебиеттер тізімі

  1. ^ а б Dudgeon, Dan; Mersereau, Russell (1983), Multidimensional Digital Signal Processing, Prentice-Hall, pp. 21–22
  2. ^ "MARBLE: Interactive Vision". homepages.inf.ed.ac.uk. Алынған 2015-11-12.
  3. ^ "Digital Geophysical Analysis Redesign". www-rohan.sdsu.edu. Алынған 2015-11-12.
  4. ^ Sihvo, Tero; Niittylahti, Jarkko (5 June 2005). "Row-Column Decomposition Based 2D Transform Optimization on Subword Parallel Processors". International Symposium on Signals, Circuits and Systems, 2005. ISSCS 2005. 1. 99–102 бет. дои:10.1109/ISSCS.2005.1509860. ISBN  978-0-7803-9029-4.
  5. ^ "Introduction to Caches". Computer Science University of Maryland. Алынған 10 қараша 2015.
  6. ^ Eddins, Steve. "Separable Convolution". Mathwords. Алынған 10 қараша 2015.
  7. ^ Dudgeon, Dan; Mersereau, Russell (1983), Multidimensional Digital Signal Processing, Prentice-Hall, б. 70
  8. ^ Dudgeon, Dan; Mersereau, Russell (1983), Multidimensional Digital Signal Processing, Prentice-Hall, б. 72
  9. ^ Fernandez, Joseph; Kumar, Vijaya (2013). Multidimensional Overlap-Add and Overlap-Save for Correlation and Convolution. 509-513 бб. дои:10.1109/ICIP.2013.6738105. ISBN  978-1-4799-2341-0.
  10. ^ "2D Signal Processing" (PDF). EE502: Digital Signal Processing. Дублин қаласы университеті. б. 24. Алынған 11 қараша, 2015.
  11. ^ а б Kundur, Deepa. "Overlap-Save and Overlap-Add" (PDF). Торонто университеті. Алынған 12 қараша, 2015.
  12. ^ "2D Signal Processing" (PDF). EE502: Digital Signal Processing. Дублин қаласы университеті. б. 26. Алынған 11 қараша, 2015.
  13. ^ Kim, Chang; Strintzis, Michael (May 1980). "High-Speed Multidimensional Convolution". Үлгіні талдау және машиналық интеллект бойынша IEEE транзакциялары. PAMI-2 (3): 269–273. дои:10.1109/tpami.1980.4767017.
  14. ^ а б Naghizadeh, Mostafa; Sacchi, Mauricio (November 2009). "Multidimensional convolution via a 1D convolution algorithm". Жетекші шеті.
  15. ^ а б Claerbout, Jon (September 1998). "Multidimensional recursive filters via a helix". Геофизика. 63 (5): 9. Бибкод:1998Geop...63.1532C. CiteSeerX  10.1.1.76.1193. дои:10.1190/1.1444449.
  16. ^ Fomel, Sergey; Claerbout, Jon (1997). "Exploring three-dimensional implicit wavefield extrapolation with the helix transform" (PDF). SEP Report: 43–60.
  17. ^ а б в Getreuer, Pascal (2013). "A Survey of Gaussian Convolution Algorithms". Image Processing on Line. 3: 286–310. дои:10.5201/ipol.2013.87.
  18. ^ Wells, W.M. (1986). "Efficient synthesis of Gaussian filters by cascaded uniform filters". Үлгіні талдау және машиналық интеллект бойынша IEEE транзакциялары. PAMI-8 (2): 234–239. дои:10.1109/TPAMI.1986.4767776.
  19. ^ "Gaussian Blur - Image processing for scientists and engineers, Part 4". patrick-fuller.com. Алынған 2015-11-12.
  20. ^ Lowe, D.G. (1999). "Object recognition from local scale-invariant features" (PDF). Proceedings of the International Conference on Computer Vision. 2: 1150–1157.