کانولوشن
این مقاله نیازمند ویکیسازی است. لطفاً با توجه به راهنمای ویرایش و شیوهنامه، محتوای آن را بهبود بخشید. |
کانوُلوشِن (به انگلیسی: Convolution) در ریاضیات یا بهطور دقیقتر آنالیز تابعی، یک عملگر ریاضی است که بر روی دو تابع f و g عمل میکند. کانولوشن مشابه تابع همبستگی است. کاربردهای این عملگر شامل آمار، بینایی رایانهای، پردازش تصویر، پردازش سیگنال، مهندسی برق و معادلات دیفرانسیل میشود.
کانولوشن را میتوان برای توابعی از گروههای غیر از فضای اقلیدسی تعریف کرد. در حالت خاص، کانولوشنِ دورهای (Cyclic Convolution) را میتوان برای توابع متناوب تعریف کرد، و کانولوشن گسسته را میتوان برای توابع صحیح تعریف کرد. چنین تعمیمهایی از کانولوشن دارای کاربردهایی در زمینه تحلیل عددی، جبر خطی عددی، و پردازش سیگنال های گسسته دارند.
تاریخچه[ویرایش]
عمل
- ،
به ازای
،
حالت خاص ضرب ترکیبی است که ریاضیدان ایتالیایی ویتو ولترا آن را مطرح کردهاست.[۱]
کانولوشن اصولاً به نام "Faltung" (که همان Folding انگلیسی به معنی تا کردن است)، توسط یک ریاضیدان آلمانی به نام گوستاو دوچ معرفی شد.[۲]
تعریف[ویرایش]
کانولوشن دو تابع ƒ و g به صورت ƒ*g نوشته میشود. این تعریف به صورت انتگرال حاصلضرب دو تابع که یکی از آنها نسبت به محور عمودی مختصات برعکس شده و روی آن یکی میلغزد تعریف میشود. با این تعریف، کانولوشن یک نوع خاص از تبدیل انتگرالی است.
کانولوشن را میتوان به عنوان میانگین وزنی تابع (ƒ(τ با مومنتوم t در نظر بگیریم که وزنها توسط (g(−τ به اندازه t جابجا میشوند (لغزش میکنند). با تغییر t، تابع وزنی قسمت های مختلف تابع ورودی را برجسته میکند. بهطور کلی، اگر f و g بر روی Rd توابع با مقدار مختلط باشند، آنگاه کانولوشن را میتوان به صورت انتگرال زیر تعریف کرد:
شرح تصویری کانولوشن | |
---|---|
۱. بیان هر تابع بر حسب متغیر زائد .
شکل موج بدست آمده (که در اینجا نمایش داده نشدهاست) کانولوشن تابع f و g است. اگر (f(t تابع ضربه باشد، نتیجه این عمل همان (g(t خواهد بود، که پاسخ ضربه نامیده میشود. |
کانولوشن دورهای (Cyclic Convolution)[ویرایش]
وقتی یک تابع gT متناوب باشد (که T دوره تناوب آن است)، آنگاه برای تابع ƒ (بهطوریکه ƒ∗gT وجود داشته باشد)، کانولوشن نیز متناوب و یکتا خواهد بود:
که to یک مقدار انتخاب است. جمع، یک بسط متناوب از تابع ƒ خوانده میشود.
اگر gT بسط متناوب یک تابع دیگر (مثلاً g) باشد، آنگاه رابطه ƒ∗gT را کانولوشنِ دورهای ƒ و g مینامند.
کانولوشن گسسته[ویرایش]
کانولوشن برای دو تابع گسسته ƒ، g که بر روی مجموعه اعداد صحیح Z تعریف شدهاست، انتگرال گسسته ƒ و g با رابطه زیر بدست میآید:
زمانی که دو چندجملهای را ضرب میکنیم، ضرایب حاصلضرب توسط کانولوشن توالی ضرایب اصلی بدست میآید، که برای جلوگیری از ایجاد جملههای تعریف نشده با عدد صفر بسط داده میشوند؛ این عمل تحت عنوان حاصلضرب کوشی ضرایب دو چند جملهای شناخته میشود.
کانولوشن گسستهٔ دورهای[ویرایش]
وقتی تابع gN متناوب است (با تناوب N)، آنگاه برای تابعی مانند ƒ، بهطوریکه ƒ∗gN وجود داشته باشد، کانولوشن متناوب و یکتا خواهد بود:
حاصل این مجموع بر روی k را بسط دورهای تابع ƒ مینامند.
اگر gN بسط دورهای یک تابع دیگر باشد، g، آنگاه عبارت ƒ∗gN را کانولوشن دورهای ƒ و g مینامند.
زمانی که طول زمانی غیرصفر هر دو تابع ƒ و g به محدوده [0, N-۱] مقید شود، آنگاه ƒ∗gN به صورت زیر کاهش خواهد یافت:
-
(
)
نماد برای کانولوشن دورهای یادآور کانولوشن بر روی گروه دورهای یک integers modulo N است.
الگوریتمهای کانولوشن سریع[ویرایش]
در برخی حالات، کانولوشن گسسته میتواند به کانولوشن دورهای تبدیل شود تا بتوان از خواص کانولوشن برای اجرای تبدیل سریع توسط کامپیوتر بهره برد. برای مثال، کانولوشن توالی رقمی[۳] یک عمل بسیار مهم ضرب اعداد چند رقمی است، که در نتیجه میتواند به صورت بهینهای با تکنیکهای تبدیل پیادهسازی شود(Knuth 1997, §4.3.3.C; von zur Gathen & Gerhard 2003, §۸٫۲).
Eq.1 به ازای هر مقدار خروجی به N عمل محاسباتی نیاز دارد و در نتیجه N2 عمل برای N خروجی؛ که این مقدار محاسبات با استفاده از هر کدام از الگوریتمهای سریع بهطور چشمگیری میتواند کاهش یابد. پردازش سیگنال دیجیتال و دیگر کاربردهای مهندسی معمولاً از الگوریتمهای کانولوشن سریع برای کاهش هزینه محاسبات کانولوشن با پیچیدگی از درجه O(N log N) استفاده میکنند.
مرسومترین الگوریتم کانولوشن سریع، از الگوریتمهای تبدیل فوریه سریع (FFT) قضیه کانولوشن دورهای استفاده میکنند. در حالت خاص، کانولوشن دورهای دو توالی با طول محدود را میتوان با اعمال FFT هر کدام، ضرب نقطه به نقطه، و سپس اعمال FFT معکوس بدست آورد. در نتیجه انواع کانولوشن تعریف شده در بالا را به صورت بهینه میتوان با استفاده از تکنیکهایی همراه با افزودن و/یا کاهش صفر خروجی پیادهسازی کرد. الگوریتمهای کانولوشن سریع دیگر، مثل الگوریتم شون هاگه- اشتراسِن، نیز از تبدیل فوریه سریع در حلقه دیگر استفاده میکنند.
دامنه تعریف[ویرایش]
کانولوشن دو تابع با مقدار مختلط بر روی Rd
خوش تعریف است، تنها اگر ƒ و g به اندازه کافی در بینهایت افت سریع خواهد داشت که انتگرال آن وجود داشته باشد. شرایط وجود کانولوشن تا حدودی ما را به اشتباه میاندازد، زیرا یک انفجار (blow up) در تابع g در بینهایت به راحتی با افت سریع تابع ƒ در بینهایت جبران میشود. در نتیجه مسئله وجود کانولوشن شامل شرایط دیگری بر روی ƒ و g میشود.
توابع کاملاً پشتیبان شده[ویرایش]
اگر ƒ و g توابع ریاضی کاملاً پشتیبان شده باشند، آنگاه کانولوشن آنها وجود دارد، و همچنین تابع بدست آمده کاملاً پشتیبانی شده و پیوسته میباشد (Hörmander). اصولاً اگر یکی از توابع (مثلاً ƒ) کاملاً پشتیبانی شده و دیگری انتگرالپذیر بومی باشد، آنگاه ƒ∗g خوش تعریف و پیوسته خواهد بود.
توابع انتگرالپذیر[ویرایش]
کانولوشن ƒ و g وجود دارد اگر ƒ و g هر دو توابع انتگرالپذیر لِبِسگ (در L1(Rd)) باشند؛ در این حالت ƒ∗g نیز انتگرالپذیر است (Stein & Weiss 1971, Theorem 1.3). این بیان، یک نتیجهگیری از قضیه تونلی است. به همین صورت، اگر ƒ ∈ L1(Rd) و g ∈ Lp(Rd) که ۱ ≤ p ≤ ∞، آنگاه ƒ∗g ∈ Lp(Rd) و
در حالت خاص p= ۱، این رابطه نشا میدهد که L1 یک جبر باناخ تحت کانولوشن است (و تساوی دو طرف برقرار است اگر f و g در تمام نقاط غیر منفی باشند).
بهطور کلی تر، نامساوی یونگ بیان میکند که کانولوشن یک نگاشت دوطرفه پیوسته بین فضاهای Lp مناسب است. بهطور خاص، اگر ۱ ≤ p,q،r ≤ ∞ رابطه زیر را ارضا کنند
آنگاه
در نتیجه، کانولوشن نگاشت دوطرفه پیوسته از Lp×Lq به Lr است.
توابع با نزول سریع[ویرایش]
علاوه بر توابع با پشتیبانی کامل و توابع انتگرالپذیر، توابعی که دارای سرعت نزول سریع در بینهایت هستند نیز میتوانند تحت کانولوشن قرار بگیرند. یکی از ویژگیهای مهم کانولوشن آن است که اگر ƒ و g هر دو سریعاً نزولی باشند، آنگاه ƒ∗g نیز به سرعت نزول میکند. با در نظر گرفتن این واقعیت که کانولوشن معمولاً با دیفرانسیلگیری همراه است (به خصوصیات مراجعه کنید)، باعث میشود که کلاس توابع شوارتز تحت کانولوشن بسته باشند.
توزیعها[ویرایش]
تحت برخی شرایط، میتوان کانولوشن یک تابع با یک توزیع، یا دو توزیع را تعریف کرد. اگر ƒ یک تابع کاملاً پشتیبانی شده باشد و g یک توزیع باشد، آنگاه ƒ∗g یک تابع نرم است که توسط فرمول توزیعی زیر تعریف میشود
در حالت کلی تر، میتوان تعریف کانولوشن را بسط داد که بهطور یکتا، قانون زیر حتی در حالتی که ƒ یک توزیع باشد، و g یک توزیع کاملاً پشتیبانی شده در نظر بگیریم، بر قرار باشد (Hörmander 1983, §۴٫۲):
اندازهها[ویرایش]
کانولوشن هر دو اندازه بورل μ و ν از تغییر محدود، اندازه λ است که با رابطه زیر تعریف میشود:
این رابطه زمانی که μ و ν را توزیع در نظر بگیریم با کانولوشنهای تعریف شده در بالا مطابقت دارد؛ همچنین برای کانولوشن توابع L1 وقتی که μ و ν نسبت به اندازه لِبِسگ مطلقاً پیوسته باشند.
همچنین، کانولوشن اندازهها نسخه دیگری از نامعادله یونگ که در زیر آمدهاست را ارضا میکنند
که نُرم، تعریف کلی اندازه است. از آنجا که فضای اندازه تغییر محدود یک فضای باناخ است، با کانولوشن اندازه میتوان مشابه روشهای استاندارد تحلیل تابعی که قابل اعمال به توزیعها نیست برخورد کرد.
خواص[ویرایش]
خواص جبری[ویرایش]
کانولوشن یک ضرب را بر روی فضای برداری توابع انتگرالپذیر است. این حاصلضرب خواص ریاضی زیر را ارضا میکند، که به معنی آن است که فضای توابع انتگرالپذیر با حاصل کانولوشن یک جبر جابجا پذیر است بدون عنصر خنثی (Strichartz 1994, §۳٫۳). دیگر فضاهای برداری توابع، مثل فضای توابع پیوسته کاملاً پشتیبانی شده، تحت کانولوشن بسته هستند، و در نتیجه جزء جبرهای جابهجاپذیر هستند.
؛ خاصیت انجمنی با یک عدد اسکالر
به ازای هر عدد حقیقی (مختلط)
هیچ عمل جبری توابع، یک عامل خنثی در ضرب را برای کانولوشن ایجاد نمیکنند. کمبود عامل خنثی در ضرب عملاً مشکل بزرگی به حساب نمیآید، زیرا زیرا اکثر توابعی که کانولوشن روی آنها انجام میشود را میتوان با یک توزیع دیراک مورد کانولوشن قرار داد، یا حداقل (مثلاً برای حالت L1) میتوان تقریبی از عامل خنثی را برای آن در نظر گرفت [نیازمند ابهامزدایی]. ولی فضای برداری توزیعهای کاملاً پشتیبانی شده، اجازه حضور عامل خنثی در ضرب را تحت کانولوشن به ما میدهند. به خصوص اینکه
که δ توزیع دلتا است.
؛ عنصر معکوس
برخی توزیعها برای کانولوشن یک عنصر معکوس دارند، S−1، که با رابطه زیر تعریف میشوند
مجموعهای از توزیعهای معکوس پذیر یک گروه آبلی را تحت کانولوشن تشکیل میدهند.
مزدوج مختلط؛
انتگرالگیری[ویرایش]
اگر ƒ و g توابع انتگرالپذیر باشند، آنگاه انتگرال کانولوشن آنها در تمام فضا، از حاصلضرب انتگرال آنها بدست میآید:
این رابطه از قضیه فوبینی بر گرفته شدهاست. نتیجه مشابهی نیز برقرار است در صورتی که ƒ و g فقط توابع قابل اندازهگیری غیر منفی باشند توسط قضیه تونلی بیان میشود.
دیفرانسیلگیری[ویرایش]
در حالت یک متغیری داریم
که d/dx همان مشتق است. بهطور کلی، در حالتی که توابعی از متغیرهای مختلف داشته باشیم، فرمول مشابهی با استفاده از مشتق پارهای برقرار است.
یک نتیجه خاص این رابطه ان است که کانولوشن را میتوان به شکل یک عمل «هموار کنندگی» نگاه کرد: کانولوشن ƒ و g به تعداد مرتبهای که ƒ و g قابل دیفرانسیلگیری هستند، قابل دیفرانسیلگیری است.
این خاصیت تحت شرایطی برقرار است که ƒ و g مطلقاً انتگرالپذیر باشند و به عنوان یکی از نتایج نامعادله یونگ حداقل یکی از آنها دارای (L1) . برای مثال، زمانی که ƒ مشتق پذیر پیوسته با پشتیبانی کامل باشد، و g یک تابع دلخواه و انتگرالپذیر محدود باشد،
قضیه کانولوشن[ویرایش]
قضیه کانولوشن بیان میدارد که:
که بیانکننده تبدیل فوریه تابع است، و یک عدد ثابت است که وابسته به نرمالیزه تبدیل فوریه است (به «خصوصیات تبدیل فوریه» مراجعه کنید). برخی نسخههای دیگر این قضیه برای تبدیل لاپلاس، تبدیل لاپلاس دوسویه، تبدیل z و تبدیل ملین برقرار است.
[[همچنین میتوانید به قضیه کانولوشن تیچ مارش که اهمیت کمتری دارد مراجعه کنید.]]
کاربردها[ویرایش]
کانولوشن در بسیاری از کاربردهای مهندسی و ریاضی دیده میشود؛
- در مهندسی برق، کانولوشن یک تابع (سیگنال ورودی) با تابعی دیگر (پاسخ ضربه)، خروجی یک سیستم خطی تغییرناپذیر با زمان (LTI) را به دست میدهد. خروجی سیستم در هر لحظه برابر با اثر جمعی تمام مقادیر پیشین تابع ورودی است، که آخرین مقادیر معمولاً بیشترین تأثیر را دارند.
- در کاربردهای پردازش سیگنال رقمی و پردازش تصویر، تابع ورودی بهطور کامل در دسترس است و لذا میتوان هر قسمت از خروجی را بدست آورد. در این نوع، میتوان از مزیت این که خروجی تنها به چند ورودی اخیر بستگی دارد بهره برد.
- کانولوشن هر مؤلفه فرکانسی را بهطور مستقل بدون وابستگی به دیگر فرکانسها تقویت و با تضعیف میکند.
- در آمار، کانولوشن در واقع یک میانگین متحرک وزن دار است.
- در تئوری احتمال، توزیع احتمال مجموع دو متغیر تصادفی مستقل برابر است با کانولوشن توزیعهای مستقل.
- در نورشناخت، بسیاری از انواعِ تارشدگی (Blur) را با کانولوشن بیان میکنند. یک سایه (مثلاً سایه دست روی یک میز، زمانی که دست بین میز و نور قرار میگیرد) را میتوان کانولوشن شکل منبع نور (که قالب سایه را تشکیل میدهد) و یک جسم (که سایه آن تشکیل میشود) دانست. یک عکس خارج از فوکوس، کانولوشن شکل جسم (لبههای جسم) با شکل عدسی است (Bokeh).
- بهطور مشابه، در پردازش سیگنال رقمی، فیلتر کانولوشنی نقش مهمی را در الگوریتمهای تشخیص لبه و کاربردهای مشابه بازی میکند.
- در صداشناسی، یک پژواک، کانولوشن صدا با تابعی است که عناصر منعکس کنندهٔ صدا را توصیف میکند.
- در همهمه مصنوعی (پردازش سیگنال رقمی، صدای پس زمینه)، کانولوشن برای نگاشت پاسخ ضربه یک اتاق واقعی بر روی سیگنال صوتی رقمی استفاده میشود.
- In time-resolved fluorescence spectroscopy, the excitation signal can be treated as a chain of delta pulses, and the measured fluorescence is a sum of exponential decays from each delta pulse.
- در سیستمهای برنامهریز درمان رادیویی، قسمت اعظم محاسبات کدها از الگوریتمهای برهمنهی کانولوشن استفاده میکنند.
- در فیزیک، هر جا که سیستم خطی با "اصل برهمنهی" همراه میشود، کانولوشن را نیز خواهیم دید.
- در سامانه اطلاعات مکانی، پاسخ تقریب هستهایِ تابعِ شدتِ یک الگوی نقطهای، کانولوشن ایزوتروپیک هسته گوسی یک انحراف استاندارد با وزنهای نقطهای (برای هر نقطه داده) است.(Diggle 1995) میتوانید به documentation of the "Kernel Smoothed Intensity of Point Pattern" of the SDA4PP QGIS plugin مراجعه کنید.
جستارهای وابسته[ویرایش]
- ماتریس توپلیتس
- نظریه سیستم خطی تغییرناپذیر با زمان
- ماتریس توپلیتس
- Cross-correlation
- دکانولوشن
- ضرب دیریکله
- Titchmarsh convolution theorem
- Convolution power
- پردازش سیگنال پیوسته
- Convolution for optical broad-beam responses in scattering media
- List of convolutions of probability distributions
- Jan Mikusinski
پانویس[ویرایش]
- ↑ According to [Lothar von Wolfersdorf (2000), "Einige Klassen quadratischer Integralgleichungen", Sitzungsberichte der Sächsischen Akademie der Wissenschaften zu Leipzig, Mathematisch-naturwissenschaftliche Klasse, Band 128, Heft 2, 6-7], the source is Volterra, Vito (1913), "Leçons sur les fonctions de linges". Gauthier-Villars, Paris 1913.
- ↑ Gustav Doetsch, "Die Integrodifferentialgleichungen vom Faltungstypus". Mathematische Annalen 89 (1923), 192-207
- ↑ Digital
منابع[ویرایش]
- Bracewell, R. (1986), The Fourier Transform and Its Applications (2nd ed.), McGraw–Hill, ISBN 0-07-116043-4.
- Hewitt, Edwin; Ross, Kenneth A. (1979), Abstract harmonic analysis. Vol. I, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], 115 (2nd ed.), Berlin, New York: Springer Science+Business Media, ISBN 978-3-540-09434-0, MR551496.
- Hewitt, Edwin; Ross, Kenneth A. (1970), Abstract harmonic analysis. Vol. II: Structure and analysis for compact groups. Analysis on locally compact Abelian groups, Die Grundlehren der mathematischen Wissenschaften, Band 152, Berlin, New York: Springer Science+Business Media, MR0262773.
- Hörmander, L. (1983), The analysis of linear partial differential operators I, Grundl. Math. Wissenschaft., 256, Springer, ISBN 3-540-12104-8, MR0717035.
- Kassel, Christian (1995), Quantum groups, Graduate Texts in Mathematics, 155, Berlin, New York: Springer Science+Business Media, ISBN 978-0-387-94370-1, MR1321145.
- Knuth, Donald (1997), Seminumerical Algorithms (3rd. ed.), Reading, Massachusetts: Addison–Wesley, ISBN 0-201-89684-2.
- Rudin, Walter (1962), Fourier analysis on groups, Interscience Tracts in Pure and Applied Mathematics, No. 12, Interscience Publishers (a division of John Wiley and Sons), New York–London, ISBN 0-471-52364-X, MR0152834.
- Sobolev, V.I. (2001), "Convolution of functions", in Hazewinkel, Michiel, Encyclopaedia of Mathematics, Springer, ISBN 978-1556080104.
- Stein, Elias; Weiss, Guido (1971), Introduction to Fourier Analysis on Euclidean Spaces, Princeton University Press, ISBN 0-691-08078-X.
- Strichartz, R. (1994), A Guide to Distribution Theory and Fourier Transforms, CRC Press, ISBN 0-8493-8273-4.
- Titchmarsh, E (1948), Introduction to the theory of Fourier integrals (2nd ed.), New York, N.Y.: Chelsea Pub. Co. (published 1986), ISBN 978-0-8284-0324-5.
- Uludag, A. M. (1998), "On possible deterioration of smoothness under the operation of convolution", J. Math. Anal. Appl. 227 no. 2, 335--358
- Treves, François (1967), Topological Vector Spaces, Distributions and Kernels, Academic Press, ISBN 0-486-45352-9.
- von zur Gathen, J.; Gerhard, J. (2003), Modern Computer Algebra, Cambridge University Press, ISBN 0-521-82646-2.
- Diggle, P. J. (1995), "A kernel method for smoothing point process data", Journal of the Royal Statistical Society, Series C) 34 (1985) 138–147
پیوند به بیرون[ویرایش]
![]() |
معنای convolution را در ویکیواژه، واژهنامهٔ آزاد، ببینید. |
![]() |
در ویکیانبار پروندههایی دربارهٔ کانولوشن موجود است. |
- Earliest Uses: The entry on Convolution has some historical information.
- https://web.archive.org/web/20090319210410/http://www.nitte.ac.in/downloads/Conv-LTI.pdf
- Convolution, on The Data Analysis BriefBook
- http://www.jhu.edu/~signals/convolve/index.html Visual convolution Java Applet.
- http://www.jhu.edu/~signals/discreteconv2/index.html Visual convolution Java Applet for Discrete Time functions.
- Lectures on Image Processing: A collection of 18 lectures in pdf format from Vanderbilt University. Lecture 7 is on 2-D convolution., by Alan Peters.
- A collection of 2D convolution kernels
- Convolution Kernel Mask Operation Interactive tutorial
- Convolution at مثورلد
- Freeverb3 Impulse Response Processor: Opensource zero latency impulse response processor with VST plugins
عملیات دوتایی | ||||
---|---|---|---|---|
عددی | تابعی | مجموعهای | ساختاری | |
مقدماتی
+ جمع حسابی
div خارج قسمت اقلیدسی ترکیباتی
() ضریب دوجملهای |
∘ ترکیب ∗ کانولوشن |
جبر مجموعهها
∪ اجتماع ترتیب کلی
توریها
|
مجموعهها
× ضرب دکارتی گروهها
⊕ حاصلجمع مستقیم مدولها
⊗ ضرب تانسوری |
درختها
واریتههای متصل
# جمع متصل فضاهای نقطهدار
∨ bouquet |
بُرداری | ||||
(.) ضرب اسکالر ∧ ضرب برداری | ||||
جبری | ||||
[,] کروشه لی {,} کروشه پواسون ∧ ضرب خارجی | ||||
هومولوژی | ||||
∪ cup-produit • حاصلضرب اشتراک |
ترتیبی | |||
+ الحاق | ||||
منطق بولی | ||||
∧ عطف منطقی | ∨ فصل منطقی | ⊕ یای انحصاری | ⇒ استلزام منطقی | ⇔ اگر و فقط اگر |