👩🏽‍✈️ 👩🏾‍🤝‍👨🏼 🚒 EvoJ का उपयोग आनुवंशिक एल्गोरिथ्म छवि अनुमोदन 🔈 🧑🏻 🤑

इस लेख में मैं आपको बताऊंगा कि कैसे आप बहुभुज के साथ अनुमानित छवियों के लिए आनुवंशिक एल्गोरिथ्म को लागू कर सकते हैं। मेरे पिछले लेखों की तरह, इस उद्देश्य के लिए मैं अपने स्वयं के EvoJ ढांचे का उपयोग करूंगा, जो मैंने पहले ही यहां और यहां के बारे में लिखा था।

समाधान विवरण विधि चुनना

EvoJ के साथ समस्याओं को हल करने के पारंपरिक तरीके के बाद, पहले हम यह चुनेंगे कि हम अपनी समस्या के समाधान का वर्णन कैसे करते हैं। एक सीधा समाधान बहुभुजों की एक सरल सूची के रूप में सन्निकटन का वर्णन करना है:

public interface PolyImage { List<Polygon> getCells(); }

इस दृष्टिकोण को जीवन का अधिकार है, हम जल्द या बाद में एक संतोषजनक तस्वीर का चयन करने में सक्षम होंगे। यह सबसे देर से होने की संभावना है, क्योंकि यह दृष्टिकोण अच्छे फैसलों को पार करने की दक्षता को कम करता है। और यहाँ क्यों है।

सादगी के लिए, निम्नलिखित चित्र की कल्पना करें।

मान लें कि हमारे पास जीन पूल में दो अच्छे समाधान हैं, जिनमें से प्रत्येक आदर्श एक से एक परीक्षण साइट से भिन्न होता है।

एक विशेषता पर ध्यान दें: दोनों मामलों में, बहुभुज संख्या 0 आदर्श रूप से एक छवि बहुभुज से मेल खाती है, जबकि दूसरा पक्ष पर कहीं निहित है। इन दो समाधानों को इस तरह से पार करना बहुत अच्छा होगा कि दोनों समाधानों में से पहले दो बहुभुज एक साथ दिखाई दें, हालांकि यह संभव नहीं है - ईवोजे सभी चर को बाइट सरणी में मैप करता है और किसी भी क्रम को बदले बिना, पार करते समय बाइट के साथ काम करता है।

क्रॉसओवर प्रक्रिया को निम्न आकृति में समझाया गया है।

इस प्रकार, एक ही सूचकांक वाले दो तत्व परिणामी समाधान में प्रकट नहीं हो सकते हैं।
क्रॉसिंग का परिणाम इस तरह से दिखाई देगा:

जो क्रोसब्रेडिंग की दक्षता को बहुत प्रभावित करेगा, विकासवाद को काफी धीमा कर देगा।

आप समस्या को "सही ढंग से" मूल आबादी को बोने के माध्यम से प्राप्त कर सकते हैं - समान रूप से छवि क्षेत्र में बहुभुज वितरित कर रहे हैं, ताकि सूची में बहुभुज का स्थान आकृति में इसकी ज्यामितीय स्थिति के अनुरूप हो। इस मामले में, म्यूटेशन को सीमित करना आवश्यक होगा ताकि पॉलीगॉन बहुत दूर "रेंगना" न कर सकें।

एक और अधिक उन्नत दृष्टिकोण शुरू में छवि को कोशिकाओं में विभाजित करना है, प्रत्येक कोशिका में पॉलीगॉन की अपनी सूची है। जावा इंटरफ़ेस के रूप में, इसे निम्नानुसार वर्णित किया गया है:

 public interface PolyImage { Colour getBkColor(); List<List<List<Polygon>>> getCells(); }

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

हम प्रत्येक बहुभुज का वर्णन इस प्रकार करते हैं:

 public interface Polygon { List<Point> getPoints(); Colour getColor(); int getOrder(); }

यहां, ऑर्डर प्रॉपर्टी वैश्विक बहुभुज रेंडरिंग ऑर्डर निर्धारित करती है। बहुभुज रंग के रूप में वर्णित किया जाएगा:

 public interface Colour { @MutationRange("0.2") @Range(min = "0", max = "1", strict = "true") float getRed(); @MutationRange("0.2") @Range(min = "0", max = "1", strict = "true") float getGreen(); @MutationRange("0.2") @Range(min = "0", max = "1", strict = "true") float getBlue(); void setRed(float red); void setGreen(float green); void setBlue(float blue); }

दूसरे शब्दों में, तीन रंग घटकों की तरह, आप अभी भी एक अल्फा चैनल जोड़ सकते हैं, हालांकि, हम 50% पारदर्शिता के साथ सभी बहुभुज आकर्षित करेंगे, इससे उदासीन म्यूटेशन की संख्या कम हो जाएगी। यहाँ एनोटेशन का उद्देश्य, मुझे आशा है, स्पष्ट है। यदि नहीं, तो मेरे पिछले लेखों पर एक नज़र डालें, इस मुद्दे से निपटा गया है।

बहुभुज बिंदुओं का वर्णन इस प्रकार किया जाएगा:

 public interface Point { int getX(); int getY(); }

इस मामले में, निर्देशांक X और Y को सेल के केंद्र के सापेक्ष माना जाएगा, जिसमें बहुभुज होता है। कृपया ध्यान दें कि चर के अनुमेय मूल्यों को विनियमित करने वाले एनोटेशन केवल रंग विवरण में मौजूद हैं। यह इस तथ्य के कारण है कि अनुमेय समन्वय मूल्य छवि के आकार और कोशिकाओं के विन्यास पर निर्भर करते हैं, और रंग घटक के अनुमेय मूल्य पूर्वनिर्धारित चीजें हैं। इसके अलावा, PolyImage इंटरफ़ेस में दो आंतरिक सूचियों पर एनोटेशन को बिल्कुल भी लटका नहीं जा सकता है।

सभी आवश्यक पैरामीटर सेट करने के लिए, हम एक सिस्टम का उपयोग करेंगे जिसे डिटैच्ड एनोटेशन कहा जाता है।

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

अलग किए गए एनोटेशन के साथ EvoJ को कॉन्फ़िगर करना

  final HashMap<String, String> context = new HashMap<String, String>(); context.put("cells@Length", ROWS.toString()); context.put("cells.item@Length", COLUMNS.toString()); context.put("cells.item.item@Length", POLYGONS_PER_CELL.toString()); context.put("cells.item.item.item.points@Length", "6"); context.put("cells.item.item.item.points.item.x@StrictRange", "true"); context.put("cells.item.item.item.points.item.x@Min", String.valueOf(-widthRadius)); context.put("cells.item.item.item.points.item.x@Max", String.valueOf(widthRadius)); context.put("cells.item.item.item.points.item.x@MutationRange", "20"); context.put("cells.item.item.item.points.item.y@StrictRange", "true"); context.put("cells.item.item.item.points.item.y@Min", String.valueOf(-heightRadius)); context.put("cells.item.item.item.points.item.y@Max", String.valueOf(heightRadius)); context.put("cells.item.item.item.points.item.y@MutationRange", "20"); context.put("cells.item.item.item.order@Min", "0"); context.put("cells.item.item.item.order@Max", "1000");

यहां हम एक संदर्भ बनाते हैं - properties फ़ाइल के समान Map , जहां properties का नाम BeanUtils में स्वीकार किए गए नोटेशन के समान ऑब्जेक्ट की संपत्ति के पथ से मेल खाता है, सिवाय इसके कि सूची आइटम कीवर्ड item द्वारा इंगित किए गए हैं।
इस प्रकार, नाम cells हमारे मूल PolyImage इंटरफ़ेस की cells संपत्ति का वर्णन करती हैं। और लाइन cells.item इस सूची के तत्व हैं, जो बदले में लाइन cells.item.item द्वारा वर्णित सूची हैं। cells.item.item , आदि।
संपत्ति का नाम और @ चिह्न के बाद अलग किए गए एनोटेशन का नाम है, जो एक नियमित एनोटेशन के नाम के समान है। सूची की लंबाई निर्दिष्ट करना अनिवार्य है ताकि EvoJ को बाइट सरणी में आरक्षित करने के लिए कितना स्थान पता हो।
एनोटेशन cells.item.item.item.points@Length बहुभुज में बिंदुओं की संख्या निर्धारित करती है (पथ का पता लगाती है - cells संपत्ति, तीन नेस्टेड सूचियां, नेस्टेड सूची के तत्वों के points गुण।
बिंदुओं के निर्देशांक, उनके उत्परिवर्तन की त्रिज्या के मूल्यों की सीमाओं, और आदेश संपत्ति के मूल्यों की सीमाएं एक समान तरीके से निर्धारित की जाती हैं।

अगला, हम जीन पूल बनाते समय भरे हुए संदर्भ का उपयोग करते हैं।

फिटनेस सुविधाएँ बनाना

एक फिटनेस फ़ंक्शन के रूप में, हम मूल से चयनित छवि के विचलन के वर्गों का योग चुनते हैं, एक ऋण चिह्न के साथ - चूंकि सबसे छोटी राशि सबसे अच्छे समाधानों से मेल खाती है। फिटनेस फ़ंक्शन ImageRating क्लास में लागू किया गया है, इसके प्रमुख बिंदुओं पर ध्यान दें।

पिछले लेखों के उदाहरणों के अनुसार, कक्षा AbstractSimpleRating सहायक वर्ग से विरासत में मिली है:

 public class ImageRating extends AbstractSimpleRating<PolyImage>

और अमूर्त doCalcRating विधि को निम्नानुसार लागू करता है:

  @Override protected Comparable doCalcRating(PolyImage solution) { BufferedImage tmp = drawImage(solution); return compareImages(originalImage, tmp); }

यहाँ drawImage फंक्शन अपने सेल, ऑर्डर, कलर आदि के अनुसार सभी बहुभुजों को तुच्छ रूप से drawImage । हम इस पर विस्तार से ध्यान नहीं देंगे - आनुवंशिक एल्गोरिथम से संबंधित कुछ भी इसमें निहित नहीं है।

compareImages फ़ंक्शन पिक्सेल-बाय-पिक्सेल छवि तुलना करता है। आइए बारीकी से देखें

  private Comparable compareImages(BufferedImage originalImage, BufferedImage tmp) { long result = 0; int[] originalPixels = originalImage.getRaster().getPixels(0, 0, originalImage.getWidth(), originalImage.getHeight(), (int[]) null); int[] tmpPixels = tmp.getRaster().getPixels(0, 0, tmp.getWidth(), tmp.getHeight(), (int[]) null); for (int i = 0; i < originalPixels.length; i++) { long d = originalPixels[i] - tmpPixels[i]; result -= d * d; } return result; }

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

पुनरावृत्तियों का कार्यान्वयन

परिणाम को तेज़ी से प्राप्त करने के लिए, इष्टतम म्यूटेशन मापदंडों को चुनना आवश्यक है:

संभावना है कि निर्णय एक उत्परिवर्तन से गुजरना होगा
समाधान के भीतर प्रत्येक चर के उत्परिवर्तन की संभावना
परिवर्तन की त्रिज्या - एक म्यूटेशन के दौरान एक बिंदु को स्थानांतरित करने वाली अधिकतम दूरी
समाधान जीवनकाल (पूरी तरह से उत्परिवर्तन से संबंधित नहीं है, लेकिन अभिसरण की दर को भी प्रभावित करता है)

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

उपरोक्त सभी को देखते हुए, मुख्य कार्यक्रम लूप का आयोजन निम्नानुसार किया गया है:

आनुवंशिक एल्गोरिथ्म के 10 पुनरावृत्तियों प्रदर्शन करते हैं
सबसे अच्छा समाधान से फिटनेस फ़ंक्शन मान लें
यह निर्धारित करें कि क्या रणनीति बदलने का समय आ गया है
यदि आवश्यक हो तो रणनीति बदलें
अस्थायी फ़ाइल में छवि सहेजें
यूआई को अपडेट करें

कार्यक्रम को लॉन्च करने के बाद, लगभग 15 मिनट (आपकी मशीन की शक्ति के आधार पर) में आप पाएंगे कि चयनित छवि पहले से ही मूल रूप से मिलती-जुलती है, और एक या दो घंटे के बाद आप लेख की शुरुआत में दिए गए परिणाम के करीब पहुंच जाएंगे।

एल्गोरिथ्म का और सुधार

निम्नलिखित अनुकूलन लागू करने से प्रगति में काफी तेजी आ सकती है:

सन्निकटन को आरजीबी के बजाय लैब स्पेस में किया जाता है, यह इस तथ्य की विशेषता है कि रंग अंतरिक्ष में बिंदुओं के बीच कार्टेशियन की दूरी आंख के अनुसार अंतर के अनुरूप है। यह प्रति सेकंड पुनरावृत्तियों की संख्या को नहीं जोड़ेगा, लेकिन यह सही दिशा में विकास को निर्देशित करेगा।
छवि क्षेत्रों के महत्व का एक मुखौटा बनाएं - रुचि के हाइलाइट किए गए क्षेत्रों के साथ एक श्वेत-श्याम छवि, जो तब फिटनेस फ़ंक्शन की गणना में उपयोग की जाएगी, इससे विकास पर ध्यान केंद्रित करने की अनुमति मिलेगी कि वास्तव में ब्याज क्या है।
छवियों के लिए VolatileImage का उपयोग करें। मेरी मशीन पर, ब्यूटेरिएमेज पर ड्राइंग, बफ़रेडआईमैज पर ड्राइंग की तुलना में 10 गुना तेज है। सच है, तो परिणाम को पिक्सल के रंगों को प्राप्त करने के लिए वैसे भी बफ़रडैमेज में बदलना पड़ता है, इससे प्रदर्शन में एक महत्वपूर्ण गिरावट आती है, लेकिन फिर भी अंतिम परिणाम बफ़रडाइमैज पर सिर्फ बहुभुज खींचने की तुलना में 3 गुना बेहतर है।
विभिन्न चरणों में इष्टतम म्यूटेशन पैरामीटर चुनें। यह एक आसान काम नहीं है, लेकिन यहां तक कि एक आनुवंशिक एल्गोरिथ्म भी मदद कर सकता है। मैंने उन प्रयोगों का आयोजन किया जहां उत्परिवर्तन पैरामीटर चर थे, और फिटनेस फ़ंक्शन प्रति 100 पुनरावृत्तियों में त्रुटि में कमी की औसत दर थी। परिणाम उत्साहजनक हैं, लेकिन इस समस्या को हल करने के लिए महत्वपूर्ण कम्प्यूटेशनल शक्ति की आवश्यकता है। शायद निम्नलिखित लेखों में से एक में मैं इस समस्या का करीब से विश्लेषण करूंगा।
कई स्वतंत्र जीन पूल शुरू करते हैं और अलग-अलग जीन पूल से अलग-अलग व्यक्तियों के लिए निश्चित अंतराल पर स्वतंत्र रूप से उनमें विकास करते हैं। इस दृष्टिकोण को जीए द्वीप मॉडल कहा जाता है, अर्थात्, विकास की प्रक्रियाएं क्योंकि यह एक-दूसरे से अलग-अलग द्वीपों पर थीं, विभिन्न द्वीपों के व्यक्तियों के बीच पार बहुत दुर्लभ हैं।
पॉलीगोन के साथ छवि को धीरे-धीरे बोएं: प्रत्येक सेल में 1-2 पॉलीगोन पहले रखें, उन्हें "रेंगना" की अनुमति दें, फिर उन जगहों पर एक और 1-2 पॉलीगोन जोड़ें जहां छवि मूल से सबसे अधिक विचलन करती है और केवल नए जोड़े गए पॉलीगोन विकसित होते हैं, इसलिए दोहराएं जब तक सेल में बहुभुजों की संख्या की सीमा नहीं हो जाती है, और तब पूरी छवि का विकास शुरू होता है, जैसा कि ऊपर लेख में वर्णित है। यह दृष्टिकोण सबसे सटीक करीब सन्निकटन की ओर जाता है।

अंतभाषण

इसलिए, हमने एक उदाहरण देखा कि छवि सन्निकटन समस्या को हल करने के लिए ईवोजे का उपयोग कैसे करें। यह ध्यान देने योग्य है कि एक आनुवंशिक एल्गोरिथम द्वारा छवियों का सन्निकटन एक व्यावहारिक की तुलना में अधिक अकादमिक या सौंदर्यवादी रुचि है, क्योंकि इसी तरह का परिणाम अन्य विशेष रूप से तेज छवि वेक्टराइजेशन एल्गोरिदम के साथ प्राप्त किया जा सकता है।

अगली बार मैं डिजाइन विचारों को उत्पन्न करने के लिए एक आनुवंशिक एल्गोरिथ्म का उपयोग करने के बारे में बात करूंगा।

UPD1: चूंकि लेख के पाठ में दिए गए स्रोतों का लिंक हड़ताली नहीं है, इसलिए मैं इसे यहाँ http://evoj.sourceforge.net/static/demos/img-demo.rar

UPD2: श्रमिकों के अनुरोध पर, मैं अपने पहले लेख से स्लाइड का उद्धरण करता हूं

स्रोत छवि	मिलान की गई छवि