पुनरावृत्त फ़ंक्शन सिस्टम: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
Line 1: Line 1:
[[File:Sierpinski1.png|thumb|right|250px|[[सीरपिंस्की त्रिकोण]] आईएफएस का उपयोग करके बनाया गया (स्वयं-समान संरचना को चित्रित करने के लिए रंगीन)]]
[[File:Sierpinski1.png|thumb|right|250px|[[सीरपिंस्की त्रिकोण]] आईएफएस का उपयोग करके बनाया गया है।]]
[[File:Chris Ursitti fractal 0000.png|thumb|right|200px|रंगीन आईएफएस को [[एपोफिसिस (सॉफ्टवेयर)]] सॉफ्टवेयर का उपयोग करके डिजाइन किया गया है और [[ इलेक्ट्रिक भेड़ |इलेक्ट्रिक भेड़]] द्वारा प्रस्तुत किया गया है।]]गणित में, '''पुनरावृत्त फलन प्रणाली''' (आईएफएस) आंशिक के निर्माण की एक विधि है; परिणामी [[भग्न|आंशिक]] अक्सर [[स्व-समान]] होते हैं। आईएफएस आंशिक, आंशिक ज्यामिति की तुलना में समुच्चय सिद्धांत से अधिक संबंधित हैं।<ref name="picg">{{cite book |title=Progress in Computer Graphics: Volume 1 |last=Zobrist |first= George Winston |author2=Chaman Sabharwal |year=1992 |publisher=Intellect Books |isbn=9780893916510 |page=135 |url=https://play.google.com/store/books/details?id=Ai6Qo0qoE9EC |access-date=7 May 2017}}</ref> इन्हें 1981 में पेश किया गया था।
[[File:Chris Ursitti fractal 0000.png|thumb|right|200px|रंगीन आईएफएस को [[एपोफिसिस (सॉफ्टवेयर)|एपोफिसिस]] सॉफ्टवेयर का उपयोग करके डिजाइन किया गया है और [[ इलेक्ट्रिक भेड़ |इलेक्ट्रिक मेष]] द्वारा प्रस्तुत किया गया है।]]'''पुनरावृत्त फ़ंक्शन सिस्टम''' (आईएफएस) फ्रेक्टल संपीड़न के निर्माण की एक विधि है जिसके परिणामस्वरूप फ्रेक्टल संपीड़न प्रायः समान होते हैं। फ्रेक्टल संपीड़न, ज्यामिति फ़ंक्शन की तुलना में समूह सिद्धांत से अधिक संबंधित होते हैं।<ref name="picg">{{cite book |title=Progress in Computer Graphics: Volume 1 |last=Zobrist |first= George Winston |author2=Chaman Sabharwal |year=1992 |publisher=Intellect Books |isbn=9780893916510 |page=135 |url=https://play.google.com/store/books/details?id=Ai6Qo0qoE9EC |access-date=7 May 2017}}</ref> जिन्हें 1981 में प्रस्तुत किया गया था।


आईएफएस आंशिक, जैसा कि इन्हें सामान्यतः कहा जाता है, किसी भी संख्या में आयाम के हो सकते हैं, लेकिन सामान्यतः इनकी गणना और 2डी में तैयार की जाती है। आंशिक स्वयं की कई प्रतियों के मिलन से बना है, प्रत्येक प्रतिलिपि एक फलन (इसलिए "फलन प्रणाली") द्वारा रूपांतरित होती है। विहित उदाहरण सीरपिंस्की त्रिकोण है। फलन सामान्यतः [[संकुचन मानचित्रण]] होते हैं, जिसका अर्थ है कि वे बिंदुओं को एक साथ लाते हैं और आकृतियों को छोटा बनाते हैं। इसलिए, एक आईएफएस आंशिक का आकार स्वयं की कई संभवतः-अतिव्यापी छोटी प्रतियों से बना होता है, जिनमें से प्रत्येक भी स्वयं की प्रतियों से बना होता है, विज्ञापन अनंत तक। यह इसकी स्व-समान आंशिक प्रकृति का स्रोत है।
सामान्यतः इन्हें फ्रेक्टल संपीड़न कहा जाता है ये फ़ंक्शन किसी भी संख्या में आयाम के हो सकते हैं, लेकिन सामान्यतः इनकी गणना और 2डी में की जाती है। फ्रेक्टल संपीड़न स्वयं के कई प्ररूपों के युग्म से बने होते है। प्रत्येक प्रारूप एक फ़ंक्शन ("फ़ंक्शन सिस्टम") द्वारा रूपांतरित होते है। उदाहरण के लिए सीरपिंस्की त्रिकोण है। फ्रेक्टल संपीड़न सामान्यतः [[संकुचन मानचित्रण]] के होते हैं, जिसका अर्थ है कि वे कई बिंदुओं मे एक साथ प्रयुक्त होते हैं और आकृतियों को छोटा बनाते हैं। इसलिए एक फ्रेक्टल संपीड़न का आकार स्वयं की कई संभवतः अतिव्यापी छोटी प्रतियों से बना होता है, जिनमें से प्रत्येक फ़ंक्शन स्वयं की प्रतियों से बना होता है। यह इसकी स्व-समान फ्रेक्टल संपीड़न संरचना का स्रोत है।


==परिभाषा==
==परिभाषा==
औपचारिक रूप से, एक [[पुनरावृत्त फ़ंक्शन|पुनरावृत्त फलन]] प्रणाली [[पूर्ण मीट्रिक स्थान|पूर्ण आव्यूह समष्टि]] पर संकुचन मैपिंग का एक सीमित समुच्चय है।<ref>Michael Barnsley (1988). ''Fractals Everywhere'', p.82. Academic Press, Inc. {{ISBN|9780120790623}}.</ref> प्रतीकात्मक रूप से,
औपचारिक रूप से एक [[पुनरावृत्त फ़ंक्शन]] सिस्टम [[पूर्ण मीट्रिक स्थान|पूर्ण संरचना]] पर संकुचन चित्रण का एक सीमित समूह है:<ref>Michael Barnsley (1988). ''Fractals Everywhere'', p.82. Academic Press, Inc. {{ISBN|9780120790623}}.</ref>
:<math>\{f_i:X\to X\mid i=1,2,\dots,N\},\ N\in\mathbb{N}</math>
:<math>\{f_i:X\to X\mid i=1,2,\dots,N\},\ N\in\mathbb{N}</math>
एक पुनरावृत्त फलन प्रणाली है यदि प्रत्येक <math>f_i</math> संपूर्ण आव्यूह समष्टि <math>X</math> पर एक संकुचन है।
यह एक पुनरावृत्त फ़ंक्शन सिस्टम है यदि प्रत्येक <math>f_i</math> संपूर्ण फ़ंक्शन <math>X</math> पर एक संकुचन है।


==गुण==
==विशेषताएँ==
[[File:Chaosgame.gif|thumb|right|250px|अराजकता के खेल द्वारा एक आईएफएस का निर्माण (एनिमेटेड)]]
[[File:Chaosgame.gif|thumb|right|250px|"चॉस खेल" द्वारा एक आईएफएस का निर्माण (एनिमेटेड)]]
[[File:Ifs-construction.png|thumb|आईएफएस दो फलनों के साथ बनाया जा रहा है।]]हचिंसन ने दिखाया कि, आव्यूह स्पेस <math>\mathbb{R}^n</math> या अधिक सामान्यतः पूर्ण आव्यूह स्पेस <math>X</math> के लिए फलनों की ऐसी प्रणाली में एक अद्वितीय गैर-रिक्त [[सघन स्थान|सघन समष्टि]](कॉम्पैक्ट) (बंद और घिरा हुआ) निश्चित समुच्चय S होता है।<ref name="hutchinson">{{cite journal |last=Hutchinson |first=John E. |title=भग्न और स्व समानता|journal=Indiana Univ. Math. J. |volume=30 |year=1981 |pages=713–747 |doi=10.1512/iumj.1981.30.30055 |url=https://maths-people.anu.edu.au/~john/Assets/Research%20Papers/fractals_self-similarity.pdf |issue=5|doi-access=free }}</ref> एक निश्चित समुच्चय के निर्माण का एक तरीका प्रारंभिक गैर-रिक्त बंद और बंधे हुए समुच्चय S0 से शुरू करना और Fi की क्रियाओं को दोहराना है, Sn+1 को Fi के अंतर्गत <math>\lim_{n \rightarrow \infty} S_n</math><nowiki> की छवियों का संघ माना जाता है; तब S को सीमा S_{n}} का </nowiki>[[ समापन (टोपोलॉजी) |समापन (टोपोलॉजी)]] मान लिया जाता है। प्रतीकात्मक रूप से, अद्वितीय निश्चित (गैर-रिक्त कॉम्पैक्ट) समुच्चय <math>S\subseteq X</math> में संपत्ति है
[[File:Ifs-construction.png|thumb|आईएफएस को दो फ़ंक्शनों के साथ बनाया जा रहा है।]]हचिंसन ने दिखाया कि पूर्ण फ़ंक्शन <math>\mathbb{R}^n</math> या अधिक सामान्यतः पूर्ण फ़ंक्शन <math>X</math> के लिए फ़ंक्शनों के सिस्टम में एक अद्वितीय गैर-रिक्त संक्षिप्त निश्चित समूह S होता है।<ref name="hutchinson">{{cite journal |last=Hutchinson |first=John E. |title=भग्न और स्व समानता|journal=Indiana Univ. Math. J. |volume=30 |year=1981 |pages=713–747 |doi=10.1512/iumj.1981.30.30055 |url=https://maths-people.anu.edu.au/~john/Assets/Research%20Papers/fractals_self-similarity.pdf |issue=5|doi-access=free }}</ref> एक संक्षिप्त निश्चित समूह के निर्माण का एक प्रकार प्रारंभिक गैर-रिक्त समूह S<sub>0</sub> से प्रारम्भ करना और F<sub>i</sub> की क्रियाओं को दोहराना S<sub>n+1</sub> को F<sub>i</sub> के अंतर्गत <math>\lim_{n \rightarrow \infty} S_n</math> की छवियों का संघ माना जाता है तब S को <math>S\subseteq X</math> की एक टोपोलॉजी मान लिया जाता है। प्रतीकात्मक रूप से अद्वितीय निश्चित गैर-रिक्त समूह <math>S\subseteq X</math> में गुण है:
:<math>S = \overline{\bigcup_{i=1}^N f_i(S)}.</math>
:<math>S = \overline{\bigcup_{i=1}^N f_i(S)}.</math>
इस प्रकार समुच्चय S, <math>A\subseteq X</math> के माध्यम से परिभाषित [[हचिंसन ऑपरेटर|हचिंसन संक्रियक]] <math>F: 2^X\to 2^X</math> का निश्चित समुच्चय है
इस प्रकार <math>A\subseteq X</math> के माध्यम से परिभाषित [[हचिंसन ऑपरेटर]] <math>F: 2^X\to 2^X</math> का निश्चित समूह है:
:<math>F(A)=\overline{\bigcup_{i=1}^N f_i(A)}.</math>
:<math>F(A)=\overline{\bigcup_{i=1}^N f_i(A)}.</math>
एस का अस्तित्व और विशिष्टता [[संकुचन मानचित्रण सिद्धांत]] का परिणाम है, जैसा कि तथ्य है
S का अस्तित्व और विशिष्टता [[संकुचन मानचित्रण सिद्धांत]] का परिणाम है, जैसा कि निम्न है:
:<math>\lim_{n\to\infty}F^{n}(A)=S</math>
:<math>\lim_{n\to\infty}F^{n}(A)=S</math>
<math>X</math> में किसी भी गैर-रिक्त कॉम्पैक्ट समुच्चय <math>A</math> के लिए। (संविदात्मक आईएफएस के लिए यह अभिसरण किसी भी गैर-रिक्त बंद सीमा वाले समुच्चय <math>A</math> के लिए भी होता है)। मनमाने ढंग से एस के करीब यादृच्छिक तत्व नीचे वर्णित "अराजकता खेल" द्वारा प्राप्त किए जा सकते हैं।
<math>X</math> में किसी भी गैर-रिक्त समूह <math>A</math> के लिए (संविदात्मक आईएफएस के लिए यह अभिसरण किसी भी गैर-रिक्त सीमा वाले समूह <math>A</math> के लिए भी होता है) अपेक्षाकृत रूप से S के निकट यादृच्छिक तत्व नीचे वर्णित "चॉस खेल" द्वारा प्राप्त किए जा सकते हैं।


हाल ही में यह दिखाया गया था कि गैर-संकुचित प्रकार के आईएफएस (अर्थात उन मानचित्रों से बने होते हैं जो एक्स में किसी भी टोपोलॉजिकली समतुल्य आव्यूह के संबंध में संकुचन नहीं हैं) आकर्षित करने वाले परिणाम दे सकते हैं। ये प्रक्षेप्य समष्टिों में स्वाभाविक रूप से उत्पन्न होते हैं, हालाँकि वृत्त पर शास्त्रीय अपरिमेय घुमाव को भी अनुकूलित किया जा सकता है।<ref>M. Barnsley, A. Vince, The Chaos Game on a General Iterated Function System</ref>
हाल ही में यह दिखाया गया था कि गैर-संकुचित प्रकार के आईएफएस (अर्थात उन मानचित्रों से बने होते हैं जो <math>X</math> में किसी भी [[ समापन (टोपोलॉजी) |टोपोलॉजिकल]] समतुल्य समूह के संबंध में संकुचित नहीं हैं) आकर्षित करने वाले परिणाम दे सकते हैं। ये प्रक्षेप्य संरचना में स्वाभाविक रूप से उत्पन्न होते हैं। हालाँकि वृत्त पर प्राथमिक अपरिमेय संख्या को भी परिवर्तित कर सकते हैं।<ref>M. Barnsley, A. Vince, The Chaos Game on a General Iterated Function System</ref>


फ़ंक्शंस <math>f_i</math> का संग्रह संरचना के अंतर्गत एक [[मोनोइड]] उत्पन्न करता है। यदि ऐसे केवल दो फलन हैं, तो मोनॉइड को एक बाइनरी ट्री के रूप में देखा जा सकता है, जहां पेड़ के प्रत्येक नोड पर, एक या दूसरे फलन के साथ रचना की जा सकती है (यानी बाईं या दाईं शाखा लें)। सामान्यतः, यदि k फलन हैं, तो कोई मोनॉइड को पूर्ण k-ary वृक्ष के रूप में देख सकता है, जिसे केली वृक्ष के रूप में भी जाना जाता है।
फ़ंक्शन <math>f_i</math> समूह संरचना के अंतर्गत एक [[मोनोइड]] उत्पन्न करता है। यदि ऐसे केवल दो फ़ंक्शन हैं, तो मोनॉइड को एक बाइनरी ट्री के रूप में देखा जा सकता है, जहां बाइनरी ट्री के प्रत्येक नोड पर एक या दूसरे फ़ंक्शन के साथ रचना की जा सकती है अर्थात बाईं या दाईं शाखा मे सामान्यतः यदि k फ़ंक्शन हैं, तो कोई मोनॉइड को पूर्ण k ट्री के रूप में देख सकता है, जिसे "केली बाइनरी ट्री" के रूप में भी जाना जाता है।


==निर्माण==
==निर्माण==
[[File:Fractal fern explained.png|thumb|upright|बार्न्सले फ़र्न, एक प्रारंभिक आईएफएस]]
[[File:Fractal fern explained.png|thumb|upright|बार्न्सले फ़र्न प्रारंभिक आईएफएस]]
[[File:Menger sponge (IFS).jpg|thumb|200px|मेन्जर स्पंज, और 3-आयामी आईएफएस।]]
[[File:Menger sponge (IFS).jpg|thumb|200px|मेन्जर स्पंज और 3-आयामी आईएफएस।]]
[[File:Coupe d'arbre.png|thumb|आईएफएस वृक्ष का निर्माण गैर-रेखीय फलन जूलिया के साथ किया गया]]
[[File:Coupe d'arbre.png|thumb|आईएफएस ट्री का निर्माण गैर-रेखीय फ़ंक्शन जूलिया के साथ किया गया था।]]
[[File:HERBO avecTige.png|thumb|]]कभी-कभी प्रत्येक फलन <math>f_i</math> को एक रैखिक, या अधिक सामान्यतः एक [[एफ़िन परिवर्तन]], और इसलिए एक आव्यूह द्वारा दर्शाया जाना आवश्यक होता है। हालाँकि, आईएफएस को गैर-रेखीय फलनों से भी बनाया जा सकता है, जिसमें [[प्रक्षेप्य परिवर्तन]] और [[रैखिक परिवर्तन]] सम्मिलित हैं। आंशिक लौ गैर-रेखीय फलनों वाले आईएफएस का एक उदाहरण है।
[[File:HERBO avecTige.png|thumb|]]कभी-कभी प्रत्येक फ़ंक्शन <math>f_i</math> को सामान्यतः [[एफ़िन परिवर्तन|एफ़िन फ़ंक्शन]] या एक रैखिक फ़ंक्शन द्वारा दर्शाया जाना आवश्यक होता है। हालाँकि आईएफएस को गैर-रेखीय फ़ंक्शनों से भी बनाया जा सकता है, जिसमें [[प्रक्षेप्य परिवर्तन]] और [[रैखिक परिवर्तन]] सम्मिलित हैं। फ्रेक्टल संपीड़न लौ गैर-रेखीय फ़ंक्शनों वाले आईएफएस फ़ंक्शन का एक उदाहरण हैं।


आईएफएस आंशिक की गणना करने के लिए सबसे आम एल्गोरिदम को "कैओस गेम" कहा जाता है। इसमें विमान में एक यादृच्छिक बिंदु को चुनना, फिर अगले बिंदु को प्राप्त करने के लिए बिंदु को बदलने के लिए फलन प्रणाली से यादृच्छिक रूप से चुने गए फलनों में से एक को पुनरावृत्त करना सम्मिलित है। एक वैकल्पिक एल्गोरिदम किसी दिए गए अधिकतम लंबाई तक फलनों के प्रत्येक संभावित अनुक्रम को उत्पन्न करना है, और फिर फलनों के इन अनुक्रमों में से प्रत्येक को प्रारंभिक बिंदु या आकार पर प्रयुक्त करने के परिणामों को प्लॉट करना है।
फ्रेक्टल संपीड़न की गणना करने के लिए सबसे सामान्य एल्गोरिथम को "चॉस खेल" कहा जाता है। इसमें समतल में एक यादृच्छिक बिंदु को चुनना, फिर अगले बिंदु को प्राप्त करने के लिए बिंदु को परिवर्तित करना फ़ंक्शन सिस्टम से यादृच्छिक रूप से चुने गए फ़ंक्शनों में से एक को पुनरावृत्त करना सम्मिलित है। एक वैकल्पिक एल्गोरिथम किसी दी गई अधिकतम लंबाई तक फ़ंक्शनों के प्रत्येक संभावित अनुक्रम को उत्पन्न करता है और फिर फ़ंक्शनों के इन अनुक्रमों में से प्रत्येक को प्रारंभिक बिंदु या आकार पर प्रयुक्त करने के परिणामों को निश्चित करता है। इनमें से प्रत्येक एल्गोरिथम एक वैश्विक निर्माण प्रदान करता है जो पूरे फ्रेक्टल संपीड़न में वितरित अंक उत्पन्न करता है। यदि फ्रेक्टल संपीड़न का एक छोटा क्षेत्र खींचा जा रहा है, तो इनमें से कई बिंदु स्क्रीन की सीमाओं से बाहर हो जाएंगे। इससे इस प्रकार से तैयार किए गए आईएफएस निर्माण में ज़ूम करना अस्पष्ट हो जाता है। आईएफएस को प्रयुक्त करने वाले सॉफ़्टवेयर के लिए केवल यह आवश्यक है कि संपूर्ण सिस्टम औसतन प्रयोगिक हो।<ref>{{cite web |last=Draves |first=Scott |author-link=Scott Draves |author2=Erik Reckase |date=July 2007 |url=http://flam3.com/flame.pdf |title=फ्रैक्टल फ्लेम एल्गोरिथम|access-date=2008-07-17 |archive-url=https://web.archive.org/web/20080509073421/http://flam3.com/flame.pdf |archive-date=2008-05-09 |url-status=dead }}</ref> हालाँकि आईएफएस के सिद्धांत के अनुसार प्रत्येक फ़ंक्शन को प्रयोगिक होना आवश्यक होता है।
==विभाजित पुनरावृत्त फ़ंक्शन सिस्टम==


इनमें से प्रत्येक एल्गोरिदम एक वैश्विक निर्माण प्रदान करता है जो पूरे आंशिक में वितरित अंक उत्पन्न करता है। यदि आंशिक का एक छोटा सा क्षेत्र खींचा जा रहा है, तो इनमें से कई बिंदु स्क्रीन की सीमाओं से बाहर हो जाएंगे। इससे इस तरीके से तैयार किए गए आईएफएस निर्माण में ज़ूम करना अव्यावहारिक हो जाता है।
पीआईएफएस (विभाजित पुनरावृत्त फ़ंक्शन सिस्टम), जिसे स्थानीय पुनरावृत्त फ़ंक्शन सिस्टम भी कहा जाता है।<ref name="lacroix"/> सामान्यतः यह अच्छी छवि संपीड़न देता है, यहां तक ​​​​कि उन छवियों के लिए भी जिनमें सरल फ्रेक्टल संपीड़न द्वारा दिखाए गए स्व-समान संरचना के प्रकार प्रदर्शित नहीं होते हैं।<ref name="SIGGRAPH'92">{{cite conference
 
हालाँकि आईएफएस के सिद्धांत के अनुसार प्रत्येक फलन को संविदात्मक होना आवश्यक है, व्यवहार में आईएफएस को प्रयुक्त करने वाले सॉफ़्टवेयर को केवल यह आवश्यक है कि संपूर्ण प्रणाली औसतन संविदात्मक हो।<ref>{{cite web |last=Draves |first=Scott |author-link=Scott Draves |author2=Erik Reckase |date=July 2007 |url=http://flam3.com/flame.pdf |title=फ्रैक्टल फ्लेम एल्गोरिथम|access-date=2008-07-17 |archive-url=https://web.archive.org/web/20080509073421/http://flam3.com/flame.pdf |archive-date=2008-05-09 |url-status=dead }}</ref>
==विभाजित पुनरावृत्त फलन प्रणाली==
 
पीआईएफएस (विभाजित पुनरावृत्त फलन प्रणाली), जिसे स्थानीय पुनरावृत्त फलन प्रणाली भी कहा जाता है,<ref name="lacroix"/> आश्चर्यजनक रूप से अच्छी छवि संपीड़न देता है, यहां तक ​​​​कि उन तस्वीरों के लिए भी जिनमें सरल आईएफएस आंशिक द्वारा दिखाए गए स्व-समान संरचना के प्रकार प्रतीत नहीं होते हैं।<ref name="SIGGRAPH'92">{{cite conference
|url= https://karczmarczuk.users.greyc.fr/matrs/Dess/RADI/Refs/fractal_paper.pdf
|url= https://karczmarczuk.users.greyc.fr/matrs/Dess/RADI/Refs/fractal_paper.pdf
|last= Fischer
|last= Fischer
Line 52: Line 48:
|url-status= dead
|url-status= dead
}}</ref>
}}</ref>
==उलटा समस्या==
==व्युत्क्रम समस्या==
{{Main|आंशिक संपीड़न
{{Main|आंशिक संपीड़न
}}
}}


आईएफएस या Pआईएफएस मापदंडों के एक समुच्चय से एक छवि उत्पन्न करने के लिए बहुत तेज़ एल्गोरिदम सम्मिलित हैं। यह तेज़ है और इसे कैसे बनाया गया इसका विवरण संग्रहीत करने, उस विवरण को गंतव्य डिवाइस पर प्रसारित करने और छवि में प्रत्येक पिक्सेल के रंग को संग्रहीत करने और प्रसारित करने की तुलना में उस छवि को गंतव्य डिवाइस पर नए सिरे से पुन: उत्पन्न करने के लिए बहुत कम संग्रहण समष्टि की आवश्यकता होती है।<ref name="lacroix">Bruno Lacroix. [http://www.collectionscanada.gc.ca/obj/s4/f2/dsk2/ftp01/MQ36939.pdf "Fractal Image Compression"]. 1998.</ref>
आईएफएस या पीआईएफएस मापदंडों के समूह से एक छवि उत्पन्न करने के लिए कई तीव्र एल्गोरिथम सम्मिलित हैं। इसे कैसे बनाया गया है इसका विवरण संग्रहीत करने, उस विवरण को गंतव्य डिवाइस पर प्रसारित करने और छवि में प्रत्येक पिक्सेल के रंग को संग्रहीत करने और प्रसारित करने की तुलना में उस छवि को गंतव्य डिवाइस पर नए रूप मे पुन: उत्पन्न करने के लिए बहुत कम संग्रहण भंडारण की आवश्यकता होती है।<ref name="lacroix">Bruno Lacroix. [http://www.collectionscanada.gc.ca/obj/s4/f2/dsk2/ftp01/MQ36939.pdf "Fractal Image Compression"]. 1998.</ref>


उलटा समस्या अधिक कठिन है: कुछ मूल मनमानी डिजिटल छवि जैसे डिजिटल फोटोग्राफ को देखते हुए, आईएफएस पैरामीटर का एक समुच्चय ढूंढने का प्रयास करें, जो पुनरावृत्ति द्वारा मूल्यांकन किए जाने पर, मूल के समान एक और छवि उत्पन्न करता है। 1989 में, अरनॉड जैक्विन ने केवल पीआईएफएस का उपयोग करके व्युत्क्रम समस्या के एक प्रतिबंधित रूप का समाधान प्रस्तुत किया; व्युत्क्रम समस्या का सामान्य रूप अनसुलझा है।<ref>
व्युत्क्रम समस्या अधिक कठिन है कुछ मूल डिजिटल छवियों जैसे डिजिटल फोटोग्राफ को देखते हुए, आईएफएस पैरामीटर के समूह को खोजने का प्रयास करें, जो पुनरावृत्ति द्वारा मूल्यांकन किए जाने पर, मूल छवियों के समान एक और छवि उत्पन्न करता है। 1989 में अरनॉड जैक्विन ने केवल पीआईएफएस का उपयोग करके व्युत्क्रम समस्या के एक प्रतिबंधित रूप का समाधान प्रस्तुत किया था जो व्युत्क्रम समस्या का सामान्य रूप अस्पष्ट उदाहरण है।<ref>
Dietmar Saupe, Raouf Hamzaoui.
Dietmar Saupe, Raouf Hamzaoui.
[https://www.uni-konstanz.de/mmsp/pubsys/publishedFiles/SaHa94.pdf "A Review of the Fractal Image Compression Literature"].
[https://www.uni-konstanz.de/mmsp/pubsys/publishedFiles/SaHa94.pdf "A Review of the Fractal Image Compression Literature"].
Line 65: Line 61:
[https://web.archive.org/web/20181123231446/https://pdfs.semanticscholar.org/d77b/ffac2560c92771d3756c0e29863a44919d6f.pdf "Algorithm for Fast Fractal Image Compression"].
[https://web.archive.org/web/20181123231446/https://pdfs.semanticscholar.org/d77b/ffac2560c92771d3756c0e29863a44919d6f.pdf "Algorithm for Fast Fractal Image Compression"].
{{doi|10.1117/12.206368}}.
{{doi|10.1117/12.206368}}.
</ref><ref name="lacroix" />
</ref><ref name="lacroix" /> 1995 तक सभी [[ भग्न संपीड़न |फ्रेक्टल संपीड़न]] सॉफ़्टवेयर जैक्विन के दृष्टिकोण पर आधारित थे।<ref name="kominek" />
 
1995 तक, सभी [[ भग्न संपीड़न |आंशिक संपीड़न]] सॉफ़्टवेयर जैक्विन के दृष्टिकोण पर आधारित हैं।<ref name="kominek" />
==उदाहरण==
==उदाहरण==
आरेख दो एफ़िन फ़ंक्शंस से आईएफएस पर निर्माण दिखाता है। फलन को द्वि-इकाई वर्ग पर उनके प्रभाव द्वारा दर्शाया जाता है (फलन उल्लिखित वर्ग को छायांकित वर्ग में बदल देता है)। दो फलनों का संयोजन हचिंसन संक्रियक बनाता है। संक्रियक के तीन पुनरावृत्तियों को दिखाया गया है, और फिर अंतिम छवि निश्चित बिंदु, अंतिम आंशिक की है।
आरेख दो एफ़िन फंक्शन से आईएफएस पर निर्माण दिखाता है। आरेख को द्वि-इकाई वर्ग पर उनके प्रभाव द्वारा दर्शाया जाता है आरेख उल्लिखित वर्ग को छायांकित वर्ग में परिवर्तित कर देता है। दो आरेखों का संयोजन हचिंसन ऑपरेटर बनाता है। ऑपरेटर के तीन पुनरावृत्तियों को दिखाया गया है और फिर अंतिम छवि निश्चित बिंदु, अंतिम [[ भग्न संपीड़न |फ्रेक्टल संपीड़न]] है।


आंशिक के शुरुआती उदाहरण जो आईएफएस द्वारा उत्पन्न किए जा सकते हैं उनमें कैंटर समुच्चय सम्मिलित है, जिसे पहली बार 1884 में वर्णित किया गया था और डी राम कर्व्स, एक प्रकार का स्व-समान वक्र जिसे 1957 में [[गेर्जेस डी. रहम]] रैम द्वारा वर्णित किया गया था।
फ्रेक्टल संपीड़न के प्रारम्भिक उदाहरण जो आईएफएस द्वारा उत्पन्न किए जा सकते हैं उनमें कैंटर समूह सम्मिलित है, जिसे पहली बार 1884 में वर्णित किया गया था। डी राम वक्र एक प्रकार का स्व-समान वक्र है, जिसे 1957 में [[गेर्जेस डी. रहम]] रैम द्वारा वर्णित किया गया था।


==इतिहास==
==इतिहास==
आईएफएस की वर्तमान स्वरूप में कल्पना 1981 में जॉन ई. हचिंसन द्वारा की गई थी<ref name="hutchinson" />और [[माइकल बार्न्सले]] की पुस्तक आंशिक एवरीव्हेयर द्वारा लोकप्रिय हुआ। <!-- In 1992 [[Scott Draves]] developed the [[Fractal flame]] algorithm.-->
आईएफएस की वर्तमान स्वरूप में कल्पना 1981 में जॉन ई. हचिंसन द्वारा की गई थी और [[माइकल बार्न्सले]] की पुस्तक फ्रेक्टल संपीड़न एवरीव्हेयर द्वारा प्रस्तुत की गई थी।<ref name="hutchinson" />  


{{Quote|आईएफएस कुछ पौधों, पत्तियों और फ़र्न के लिए मॉडल प्रदान करते हैं, आत्म-समानता के आधार पर जो अक्सर प्रकृति में शाखाओं वाली संरचनाओं में होती है।|माइकल बार्न्सले<ref name=V-variable>[[माइकल बार्न्सले]]''{{cite web |url= http://www.maths.anu.edu.au/~barnsley/pdfs/V-var_super_fractals.pdf |title=V-variable fractals and superfractals}}&nbsp;{{small|(2.22&nbsp;MB)}}</ref>}}
{{Quote|आईएफएस कुछ पौधों, पत्तियों और फ़र्न के लिए मॉडल प्रदान करते हैं, आत्म-समानता के आधार पर जो प्रायः प्रकृति में शाखाओं वाली संरचनाओं में होती है।|माइकल बार्न्सले<ref name=V-variable>[[माइकल बार्न्सले]]''{{cite web |url= http://www.maths.anu.edu.au/~barnsley/pdfs/V-var_super_fractals.pdf |title=V-variable fractals and superfractals}}&nbsp;{{small|(2.22&nbsp;MB)}}</ref>}}<!-- In 1992 [[Scott Draves]] developed the [[Fractal flame]] algorithm.-->


==यह भी देखें==
==यह भी देखें==
{{Portal|Mathematics}}
{{Portal|Mathematics}}
*[[एल प्रणाली|जटिल-आधार प्रणाली]]
*[[एल प्रणाली|समिश्र आधार सिस्टम]]
*[[कोलाज प्रमेय]]
*[[कोलाज प्रमेय]]
*[[विश्लेषणात्मक कार्यों की अनंत रचनाएँ|विश्लेषणात्मक फलनों की अनंत रचनाएँ]]
*[[विश्लेषणात्मक कार्यों की अनंत रचनाएँ|विश्लेषणात्मक फ़ंक्शनों की अनंत रचनाएँ]]
*एल-प्रणाली
*एल-सिस्टम
*आंशिक संपीड़न
*फ्रेक्टल संपीड़न


==टिप्पणियाँ==
==टिप्पणियाँ==

Revision as of 12:50, 17 July 2023

सीरपिंस्की त्रिकोण आईएफएस का उपयोग करके बनाया गया है।
रंगीन आईएफएस को एपोफिसिस सॉफ्टवेयर का उपयोग करके डिजाइन किया गया है और इलेक्ट्रिक मेष द्वारा प्रस्तुत किया गया है।

पुनरावृत्त फ़ंक्शन सिस्टम (आईएफएस) फ्रेक्टल संपीड़न के निर्माण की एक विधि है जिसके परिणामस्वरूप फ्रेक्टल संपीड़न प्रायः समान होते हैं। फ्रेक्टल संपीड़न, ज्यामिति फ़ंक्शन की तुलना में समूह सिद्धांत से अधिक संबंधित होते हैं।[1] जिन्हें 1981 में प्रस्तुत किया गया था।

सामान्यतः इन्हें फ्रेक्टल संपीड़न कहा जाता है ये फ़ंक्शन किसी भी संख्या में आयाम के हो सकते हैं, लेकिन सामान्यतः इनकी गणना और 2डी में की जाती है। फ्रेक्टल संपीड़न स्वयं के कई प्ररूपों के युग्म से बने होते है। प्रत्येक प्रारूप एक फ़ंक्शन ("फ़ंक्शन सिस्टम") द्वारा रूपांतरित होते है। उदाहरण के लिए सीरपिंस्की त्रिकोण है। फ्रेक्टल संपीड़न सामान्यतः संकुचन मानचित्रण के होते हैं, जिसका अर्थ है कि वे कई बिंदुओं मे एक साथ प्रयुक्त होते हैं और आकृतियों को छोटा बनाते हैं। इसलिए एक फ्रेक्टल संपीड़न का आकार स्वयं की कई संभवतः अतिव्यापी छोटी प्रतियों से बना होता है, जिनमें से प्रत्येक फ़ंक्शन स्वयं की प्रतियों से बना होता है। यह इसकी स्व-समान फ्रेक्टल संपीड़न संरचना का स्रोत है।

परिभाषा

औपचारिक रूप से एक पुनरावृत्त फ़ंक्शन सिस्टम पूर्ण संरचना पर संकुचन चित्रण का एक सीमित समूह है:[2]

यह एक पुनरावृत्त फ़ंक्शन सिस्टम है यदि प्रत्येक संपूर्ण फ़ंक्शन पर एक संकुचन है।

विशेषताएँ

"चॉस खेल" द्वारा एक आईएफएस का निर्माण (एनिमेटेड)
आईएफएस को दो फ़ंक्शनों के साथ बनाया जा रहा है।

हचिंसन ने दिखाया कि पूर्ण फ़ंक्शन या अधिक सामान्यतः पूर्ण फ़ंक्शन के लिए फ़ंक्शनों के सिस्टम में एक अद्वितीय गैर-रिक्त संक्षिप्त निश्चित समूह S होता है।[3] एक संक्षिप्त निश्चित समूह के निर्माण का एक प्रकार प्रारंभिक गैर-रिक्त समूह S0 से प्रारम्भ करना और Fi की क्रियाओं को दोहराना Sn+1 को Fi के अंतर्गत की छवियों का संघ माना जाता है तब S को की एक टोपोलॉजी मान लिया जाता है। प्रतीकात्मक रूप से अद्वितीय निश्चित गैर-रिक्त समूह में गुण है:

इस प्रकार के माध्यम से परिभाषित हचिंसन ऑपरेटर का निश्चित समूह है:

S का अस्तित्व और विशिष्टता संकुचन मानचित्रण सिद्धांत का परिणाम है, जैसा कि निम्न है:

में किसी भी गैर-रिक्त समूह के लिए (संविदात्मक आईएफएस के लिए यह अभिसरण किसी भी गैर-रिक्त सीमा वाले समूह के लिए भी होता है) अपेक्षाकृत रूप से S के निकट यादृच्छिक तत्व नीचे वर्णित "चॉस खेल" द्वारा प्राप्त किए जा सकते हैं।

हाल ही में यह दिखाया गया था कि गैर-संकुचित प्रकार के आईएफएस (अर्थात उन मानचित्रों से बने होते हैं जो में किसी भी टोपोलॉजिकल समतुल्य समूह के संबंध में संकुचित नहीं हैं) आकर्षित करने वाले परिणाम दे सकते हैं। ये प्रक्षेप्य संरचना में स्वाभाविक रूप से उत्पन्न होते हैं। हालाँकि वृत्त पर प्राथमिक अपरिमेय संख्या को भी परिवर्तित कर सकते हैं।[4]

फ़ंक्शन समूह संरचना के अंतर्गत एक मोनोइड उत्पन्न करता है। यदि ऐसे केवल दो फ़ंक्शन हैं, तो मोनॉइड को एक बाइनरी ट्री के रूप में देखा जा सकता है, जहां बाइनरी ट्री के प्रत्येक नोड पर एक या दूसरे फ़ंक्शन के साथ रचना की जा सकती है अर्थात बाईं या दाईं शाखा मे सामान्यतः यदि k फ़ंक्शन हैं, तो कोई मोनॉइड को पूर्ण k ट्री के रूप में देख सकता है, जिसे "केली बाइनरी ट्री" के रूप में भी जाना जाता है।

निर्माण

बार्न्सले फ़र्न प्रारंभिक आईएफएस
मेन्जर स्पंज और 3-आयामी आईएफएस।
आईएफएस ट्री का निर्माण गैर-रेखीय फ़ंक्शन जूलिया के साथ किया गया था।
HERBO avecTige.png

कभी-कभी प्रत्येक फ़ंक्शन को सामान्यतः एफ़िन फ़ंक्शन या एक रैखिक फ़ंक्शन द्वारा दर्शाया जाना आवश्यक होता है। हालाँकि आईएफएस को गैर-रेखीय फ़ंक्शनों से भी बनाया जा सकता है, जिसमें प्रक्षेप्य परिवर्तन और रैखिक परिवर्तन सम्मिलित हैं। फ्रेक्टल संपीड़न लौ गैर-रेखीय फ़ंक्शनों वाले आईएफएस फ़ंक्शन का एक उदाहरण हैं।

फ्रेक्टल संपीड़न की गणना करने के लिए सबसे सामान्य एल्गोरिथम को "चॉस खेल" कहा जाता है। इसमें समतल में एक यादृच्छिक बिंदु को चुनना, फिर अगले बिंदु को प्राप्त करने के लिए बिंदु को परिवर्तित करना फ़ंक्शन सिस्टम से यादृच्छिक रूप से चुने गए फ़ंक्शनों में से एक को पुनरावृत्त करना सम्मिलित है। एक वैकल्पिक एल्गोरिथम किसी दी गई अधिकतम लंबाई तक फ़ंक्शनों के प्रत्येक संभावित अनुक्रम को उत्पन्न करता है और फिर फ़ंक्शनों के इन अनुक्रमों में से प्रत्येक को प्रारंभिक बिंदु या आकार पर प्रयुक्त करने के परिणामों को निश्चित करता है। इनमें से प्रत्येक एल्गोरिथम एक वैश्विक निर्माण प्रदान करता है जो पूरे फ्रेक्टल संपीड़न में वितरित अंक उत्पन्न करता है। यदि फ्रेक्टल संपीड़न का एक छोटा क्षेत्र खींचा जा रहा है, तो इनमें से कई बिंदु स्क्रीन की सीमाओं से बाहर हो जाएंगे। इससे इस प्रकार से तैयार किए गए आईएफएस निर्माण में ज़ूम करना अस्पष्ट हो जाता है। आईएफएस को प्रयुक्त करने वाले सॉफ़्टवेयर के लिए केवल यह आवश्यक है कि संपूर्ण सिस्टम औसतन प्रयोगिक हो।[5] हालाँकि आईएफएस के सिद्धांत के अनुसार प्रत्येक फ़ंक्शन को प्रयोगिक होना आवश्यक होता है।

विभाजित पुनरावृत्त फ़ंक्शन सिस्टम

पीआईएफएस (विभाजित पुनरावृत्त फ़ंक्शन सिस्टम), जिसे स्थानीय पुनरावृत्त फ़ंक्शन सिस्टम भी कहा जाता है।[6] सामान्यतः यह अच्छी छवि संपीड़न देता है, यहां तक ​​​​कि उन छवियों के लिए भी जिनमें सरल फ्रेक्टल संपीड़न द्वारा दिखाए गए स्व-समान संरचना के प्रकार प्रदर्शित नहीं होते हैं।[7]

व्युत्क्रम समस्या

आईएफएस या पीआईएफएस मापदंडों के समूह से एक छवि उत्पन्न करने के लिए कई तीव्र एल्गोरिथम सम्मिलित हैं। इसे कैसे बनाया गया है इसका विवरण संग्रहीत करने, उस विवरण को गंतव्य डिवाइस पर प्रसारित करने और छवि में प्रत्येक पिक्सेल के रंग को संग्रहीत करने और प्रसारित करने की तुलना में उस छवि को गंतव्य डिवाइस पर नए रूप मे पुन: उत्पन्न करने के लिए बहुत कम संग्रहण भंडारण की आवश्यकता होती है।[6]

व्युत्क्रम समस्या अधिक कठिन है कुछ मूल डिजिटल छवियों जैसे डिजिटल फोटोग्राफ को देखते हुए, आईएफएस पैरामीटर के समूह को खोजने का प्रयास करें, जो पुनरावृत्ति द्वारा मूल्यांकन किए जाने पर, मूल छवियों के समान एक और छवि उत्पन्न करता है। 1989 में अरनॉड जैक्विन ने केवल पीआईएफएस का उपयोग करके व्युत्क्रम समस्या के एक प्रतिबंधित रूप का समाधान प्रस्तुत किया था जो व्युत्क्रम समस्या का सामान्य रूप अस्पष्ट उदाहरण है।[8][9][6] 1995 तक सभी फ्रेक्टल संपीड़न सॉफ़्टवेयर जैक्विन के दृष्टिकोण पर आधारित थे।[9]

उदाहरण

आरेख दो एफ़िन फंक्शन से आईएफएस पर निर्माण दिखाता है। आरेख को द्वि-इकाई वर्ग पर उनके प्रभाव द्वारा दर्शाया जाता है आरेख उल्लिखित वर्ग को छायांकित वर्ग में परिवर्तित कर देता है। दो आरेखों का संयोजन हचिंसन ऑपरेटर बनाता है। ऑपरेटर के तीन पुनरावृत्तियों को दिखाया गया है और फिर अंतिम छवि निश्चित बिंदु, अंतिम फ्रेक्टल संपीड़न है।

फ्रेक्टल संपीड़न के प्रारम्भिक उदाहरण जो आईएफएस द्वारा उत्पन्न किए जा सकते हैं उनमें कैंटर समूह सम्मिलित है, जिसे पहली बार 1884 में वर्णित किया गया था। डी राम वक्र एक प्रकार का स्व-समान वक्र है, जिसे 1957 में गेर्जेस डी. रहम रैम द्वारा वर्णित किया गया था।

इतिहास

आईएफएस की वर्तमान स्वरूप में कल्पना 1981 में जॉन ई. हचिंसन द्वारा की गई थी और माइकल बार्न्सले की पुस्तक फ्रेक्टल संपीड़न एवरीव्हेयर द्वारा प्रस्तुत की गई थी।[3]

आईएफएस कुछ पौधों, पत्तियों और फ़र्न के लिए मॉडल प्रदान करते हैं, आत्म-समानता के आधार पर जो प्रायः प्रकृति में शाखाओं वाली संरचनाओं में होती है।

— माइकल बार्न्सले[10]

यह भी देखें

टिप्पणियाँ

  1. Zobrist, George Winston; Chaman Sabharwal (1992). Progress in Computer Graphics: Volume 1. Intellect Books. p. 135. ISBN 9780893916510. Retrieved 7 May 2017.
  2. Michael Barnsley (1988). Fractals Everywhere, p.82. Academic Press, Inc. ISBN 9780120790623.
  3. 3.0 3.1 Hutchinson, John E. (1981). "भग्न और स्व समानता" (PDF). Indiana Univ. Math. J. 30 (5): 713–747. doi:10.1512/iumj.1981.30.30055.
  4. M. Barnsley, A. Vince, The Chaos Game on a General Iterated Function System
  5. Draves, Scott; Erik Reckase (July 2007). "फ्रैक्टल फ्लेम एल्गोरिथम" (PDF). Archived from the original (PDF) on 2008-05-09. Retrieved 2008-07-17.
  6. 6.0 6.1 6.2 Bruno Lacroix. "Fractal Image Compression". 1998.
  7. Fischer, Yuval (1992-08-12). Przemyslaw Prusinkiewicz (ed.). SIGGRAPH'92 course notes - Fractal Image Compression (PDF). SIGGRAPH. Vol. Fractals - From Folk Art to Hyperreality. ACM SIGGRAPH. Archived from the original (PDF) on 2017-09-12. Retrieved 2017-06-30.
  8. Dietmar Saupe, Raouf Hamzaoui. "A Review of the Fractal Image Compression Literature".
  9. 9.0 9.1 John Kominek. "Algorithm for Fast Fractal Image Compression". doi:10.1117/12.206368.
  10. माइकल बार्न्सले"V-variable fractals and superfractals" (PDF). (2.22 MB)


संदर्भ


बाहरी संबंध