किसी भी कोण पर बिटमैप छवि का सटीक घुमाव

कोणों द्वारा एक रेखापुंज छवि को घूमना जो कि छवि के ज्यामितीय केंद्र के सापेक्ष 90 ° के गुणक हैं, एक तुच्छ कार्य है और प्रत्येक पिक्सेल के निर्देशांक को परिवर्तित करके गुणवत्ता की हानि के बिना हल किया जा सकता है।

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

नीचे हम न्यूनतम नुकसान के साथ एक मनमाना केंद्र के सापेक्ष एक मनमाना कोण द्वारा रास्टर छवि के सटीक रोटेशन के लिए एल्गोरिथ्म पर विचार करते हैं।

मैं प्रदान की गई सहायता के लिए खरचेंको व्लादिस्लाव व्लादिमीरोविच को धन्यवाद देता हूं।

एल्गोरिथ्म

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

मूल छवि के एक पिक्सेल मॉडल के रूप में, हम कोण = के लिए निम्नलिखित संकेतन के साथ, साइड = 1 के साथ एक वर्ग का उपयोग करेंगे:
i1 सबसे दाहिना कोना है;
i2 सबसे निचला कोना है;
i3 सबसे बाएं कोने में है;
i4 सबसे ऊपरी कोना है।

अंतिम छवि का मॉडल लाइनों = 1 के बीच की दूरी के साथ समानांतर क्षैतिज और ऊर्ध्वाधर लाइनों का एक ग्रिड होगा।

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

जब से आप रेखापुंज छवि को घुमाते हैं, प्रत्येक पिक्सेल का वर्ग एक ही कोण (इस पिक्सेल के केंद्र के सापेक्ष) से ​​घूमता है, हम एक पिक्सेल के लिए समस्या का समाधान करेंगे, और फिर मूल छवि के प्रत्येक पिक्सेल के लिए परिणामी समाधान लागू करेंगे।

एक रेखापुंज छवि के रोटेशन को दो भागों में विभाजित किया जा सकता है:
1. किसी दिए गए कोण द्वारा इस वर्ग के केंद्र के सापेक्ष मूल छवि के प्रत्येक पिक्सेल के वर्ग का रोटेशन।
2. छवि के रोटेशन के केंद्र के सापेक्ष छवि के रोटेशन के कोण के अनुसार पिक्सेल के वर्ग के केंद्र की ऑफसेट ताकि वर्ग अंतिम छवि के ग्रिड पर अपनी अंतिम स्थिति में हो।
इस स्थिति में, अंतिम छवि का ग्रिड मूल छवि के प्रत्येक पिक्सेल के वर्ग को 4, 5 या 6 टुकड़ों में "टुकड़ों" में काट देता है।

परिणामी विकल्पों की विविधता को व्यवस्थित करने के लिए, मुझे अंतिम छवि के ग्रिड के साथ स्रोत छवि के पिक्सेल के वर्ग के सभी प्रकार के चौराहों का एक वर्गीकरण करना था। केवल 23 अनिवार्य रूप से अलग-अलग विकल्प थे:


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

स्पष्टता के लिए, मैं विकल्प नंबर 3 के संभावित बदलावों में से एक दूंगा:

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

सूत्र १

इस सूत्र का उपयोग "टुकड़े" के अंतिम क्षेत्र की गणना करने के लिए नहीं किया गया है, लेकिन सहायक मध्यवर्ती क्षेत्रों की त्वरित गणना के लिए इसका उपयोग करना सुविधाजनक है, क्योंकि हम जानते हैं कि पूरे पिक्सेल का क्षेत्र = 1 है।
अंतिम छवि के ग्रिड पर वर्ग के कोनों से छोड़ी गई ऊंचाइयों का उपयोग सभी फ़ार्मुलों में इनपुट चर के रूप में किया जाता है, इस सरल कारण के लिए कि इन हाइट्स की गणना पिक्सेल के वर्ग के संबंधित कोने के समन्वय के संख्यात्मक मूल्य के तुरंत अंश को निकालने के लिए कम की जाती है।

सूत्र २

इस सूत्र का उपयोग केवल विकल्प 1 और 2 में किया जाता है।

सूत्र ३

एक अक्सर उपयोग किया जाने वाला सूत्र बहुत अच्छा है कि यह जल्दी से गणना की जाती है। चूंकि घूर्णन कोण प्रत्येक पिक्सेल के लिए समान है, सभी पिक्सेल को संसाधित करने से पहले सभी त्रिकोणमितीय कार्यों को एक बार गिना जा सकता है, और फिर लूप में इन मानों को स्थिरांक के रूप में उपयोग करें।

सूत्र ४

इस सूत्र की गणना दो चरणों में की जाती है। सबसे पहले, कोष्ठकों में अभिव्यक्ति का मूल्यांकन किया जाता है। यदि यह एक सकारात्मक मूल्य लेता है, तो क्षेत्र की गणना की जाती है। यदि मान ऋणात्मक है, तो इसका मतलब है कि ग्रिड के कोण और वर्ग के किनारे से बना "स्प्लिन्टर" पिक्सेल को नहीं काटता है और आगे की गणना करने का कोई मतलब नहीं है।

उपरोक्त सभी को देखते हुए, सामान्य शब्दों में, एल्गोरिथ्म इस तरह दिखाई देगा:
1. मूल छवि को कंप्यूटर मेमोरी में लोड करें।
2. हम पिक्सेल में अंतिम छवि के आकार की गणना करते हैं।
3. एक मध्यवर्ती द्वि-आयामी सरणी बनाएं, जिसमें से प्रत्येक तत्व में एक फ्लोटिंग पॉइंट नंबर के प्रारूप में 3 RGB रंग घटक होते हैं। सरणी के आयाम अंतिम छवि के आकार के बराबर हैं।
4. मूल छवि के सभी पिक्सेल पर क्रमिक रूप से पुनरावृति; हम उनमें से प्रत्येक को एक दिए गए कोण से मोड़ते हैं और इसे अंतिम छवि के ग्रिड पर रखते हैं, पिक्सेल के वर्ग के कोनों के 4 निर्देशांक की गणना करते हैं; हम 23 विकल्पों के अनुसार एक पिक्सेल वर्गीकृत करते हैं और "टुकड़े" के क्षेत्र पर विचार करते हैं; इन "टुकड़ों" के क्षेत्र के अनुपात में मध्यवर्ती सरणी के संबंधित तत्वों के परिणामस्वरूप "टुकड़े" के रंगों को जोड़ें।
5. मूल छवि के सभी पिक्सल को संसाधित करने के बाद, प्रत्येक तत्व के लिए एक पूर्णांक मान के लिए मध्यवर्ती सरणी में RGB मानों को गोल करें और इन पूर्णांक मानों के आधार पर BMP प्रारूप में अंतिम छवि बनाएं।

कार्यक्रम

उपरोक्त एल्गोरिथ्म के आधार पर, विंडोज के लिए एक कार्यक्रम लिखा गया था। ऑब्जेक्ट पास्कल के लिए स्रोत कोड और संकलित निष्पादन योग्य डाउनलोड किया जा सकता है ।

कार्यक्रम इंटरफ़ेस।
"ओपन ..." बटन पर क्लिक करके, बीएमपी फ़ाइल चुनने का एक संवाद खुलता है। केवल 24-बिट पैलेट वाले बिटमैप का समर्थन किया जाता है। एक खिड़की में एक खुली छवि प्रदर्शित की जाती है। फ़ाइल और छवि आकार का पूरा शीर्षक विंडो शीर्षक में प्रदर्शित किया जाता है।

क्षेत्र में "एंगल" डिग्री में रोटेशन के कोण को सेट करता है - कोई भी सकारात्मक संख्या।
भिन्नात्मक संख्याओं को दर्ज करते समय, एक अवधि और अल्पविराम दोनों को दशमलव विभाजक के रूप में उपयोग किया जा सकता है।

रेडियो बटन "CW" और "CCW" रोटेशन की दिशा निर्दिष्ट करते हैं: क्रमशः "दक्षिणावर्त" और "वामावर्त"।

"बैकग्राउंड कलर" ब्लॉक में, आप बैकग्राउंड कलर सेट कर सकते हैं, जिसके साथ इमेज की बाउंड्री पिक्सल मिक्स हो जाएगी। डिफ़ॉल्ट पृष्ठभूमि का रंग काला है।

"सेंटर एक्स" और "सेंटर वाई" फ़ील्ड में रोटेशन के केंद्र के निर्देशांक सेट किए जाते हैं। यह ध्यान में रखा जाना चाहिए कि मूल छवि के ऊपरी बाएं कोने में है और वाई नीचे की ओर बढ़ता है। डिफ़ॉल्ट रूप से, रोटेशन का केंद्र लोड छवि के ज्यामितीय केंद्र में सेट किया गया है।

"घुमाएँ" बटन दबाकर या Enter कुंजी दबाकर, छवि को किसी दिए गए रोटेशन केंद्र के सापेक्ष पूर्व निर्धारित कोण से घुमाया जाता है और खिड़की में प्रदर्शित किया जाता है। कोणों द्वारा छवि को घुमाना जो कि 90 ° से अधिक है, को मूल योजना के पिक्सल के निर्देशांक में परिवर्तित करके एक सरलीकृत योजना के अनुसार कार्यान्वित किया जाता है, जबकि "केंद्र X" और "केंद्र Y" के मूल्यों को अनदेखा किया जाता है।
एल्गोरिथ्म के सेकंड में चलने का समय "घुमाएँ" बटन के नीचे प्रदर्शित होता है।

"सहेजें ..." बटन का उपयोग करके, घुमाई गई छवि को BMP फ़ाइल में सहेजा जा सकता है।

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

चार-कोर 2.67 गीगाहर्ट्ज प्रोसेसर वाली मशीन पर 1024 x 768 के आयामों वाली एक छवि को इस कार्यक्रम द्वारा औसतन कोण पर, लगभग 0.5 सेकंड में घुमाया जाता है। 4000 x 4000 के आयाम वाली एक छवि - लगभग 10 सेकंड में। अलग-अलग कोणों के लिए एल्गोरिथ्म का चलने का समय इस तथ्य के कारण भिन्न हो सकता है कि अलग-अलग कोणों पर छवि को अलग-अलग "खंडों" में विभाजित किया जाता है, क्रमशः, अलग-अलग समय बिताए गए क्षेत्रों की गणना के लिए।

एक अस्थायी बिंदु संख्या के प्रारूप में अंतिम छवि के पिक्सेल की रंग जानकारी युक्त मध्यवर्ती सरणी को विस्तारित (10 बाइट्स) के रूप में लागू किया जाता है, इसलिए बड़ी छवियों (लगभग 5000 x 5000 पिक्सेल से अधिक) को संसाधित करने से मेमोरी अतिप्रवाह त्रुटि हो सकती है। कम सटीक डेटा प्रकार को लागू करने और अंतिम बिटमैप में तुरंत संख्या के पूर्णांक भाग को संग्रहीत करके स्थिति में सुधार करना संभव है, सहायक सरणी में केवल भिन्नात्मक भाग को छोड़कर।

परिणाम

आइए हम फ़ोटोशॉप में लागू सटीक एल्गोरिदम और छवि रोटेशन एल्गोरिथ्म के संचालन का तुलनात्मक विश्लेषण करें।

परीक्षण 1

पहले परीक्षण के लिए, मैंने एक बहुत ही सरल छवि ली - 1 पिक्सेल की मोटाई के साथ काले रंग की एक क्षैतिज रेखा और 10 पिक्सेल की लंबाई, 100 x 100 पिक्सेल के आयाम के साथ एक सफेद वर्ग के केंद्र से ऑफसेट:


जिसके बाद मैंने इस चित्र को निर्देशांक (0, 0) 3 ° दक्षिणावर्त के साथ घुमाया। बिंदु (0, 0) को इसलिए चुना गया, क्योंकि मेरे प्रयोगों को देखते हुए, फ़ोटोशॉप इस विशेष बिंदु के सापेक्ष छवि को घुमाता है। यहां तुलनात्मक परिणाम (24 गुना बढ़ा):


परिशुद्धता एल्गोरिदम





फोटोशॉप 7.0.1





फ़ोटोशॉप CS6 (64 बिट)
फ़ोटोशॉप एल्गोरिथ्म एक अधिक विपरीत तस्वीर देता है, सटीक एल्गोरिदम कुछ हद तक छवि को "धुंधला" करता है। लेकिन सामान्य तौर पर, एक दृश्य मूल्यांकन के साथ, परिणाम लगभग समान है। जिस तरह से, हम ध्यान दें कि फ़ोटोशॉप में लागू रोटेशन एल्गोरिथ्म ने 10 वर्षों में महत्वपूर्ण बदलाव नहीं किए हैं।

परीक्षण २

दूसरे परीक्षण के लिए, मैंने मानक Win7 वितरण से एक ट्यूलिप चुना:



इस छवि को ज्यामितीय केंद्र के सापेक्ष 5 ° दक्षिणावर्त मोड़ने के बाद, मैंने आरजीबी चैनलों के संदर्भ में सभी पिक्सल के रंग को अभिव्यक्त किया। यहाँ सटीक एल्गोरिदम और फ़ोटोशॉप एल्गोरिथ्म का परिणाम है:

मूल	सटीक मोड़ (गोलाई से पहले)	सटीक मोड़ (गोलाई के बाद)	फोटोशॉप CS6
आर = 33381406 जी = 27933900 B = 11239213	R = 33381406.0000004 (~ 0) G = 27933899.9999997 (~ 0) B = 11239212,9999999 (~ 0)	आर = 33382786 (1380) G = 27933920 (20) B = 11238086 (-1127)	आर = 33387726 (6320) G = 27950823 (16923) B = 11245937 (6724)

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

दो एल्गोरिदम की एक दृश्य तुलना के लिए, मैं छवि का एक बड़ा टुकड़ा दूंगा,


क्रमशः 5 ° दक्षिणावर्त घुमाया गया, Photoshop'om:


और सटीक एल्गोरिथ्म:


एक तुलनात्मक विश्लेषण से पता चलता है कि फ़ोटोशॉप छवि के विपरीत तत्वों को बेहतर ढंग से संरक्षित करता है, लेकिन एक ही समय में विकृत रंग का "halos" बनाता है। सटीक एल्गोरिथ्म रंग को विकृत नहीं करता है, लेकिन एक ही समय में कुछ हद तक छवि को धुंधला करता है।

निष्कर्ष

1. सटीक और एक ही समय में एक मनमाना कोण पर बिटमैप छवि का अपेक्षाकृत त्वरित रोटेशन संभव है। मेरे लिए, यह सवाल बना हुआ है कि पेशेवर ग्राफिक संपादकों में ऐसा कोई विकल्प क्यों नहीं है जो उपयोगकर्ता को थोड़े समय में छवि को बहुत सटीक रूप से घुमाने की अनुमति देता है।

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

3. विपरीत विवरण के दृश्य धारणा के दृष्टिकोण से, फ़ोटोशॉप इष्टतम एल्गोरिथ्म द्वारा सबसे अच्छा परिणाम प्रदान किया जाता है। सटीक एल्गोरिदम उन मामलों में लागू करने के लिए समझ में आता है जहां छवि के रंग के बारे में अधिकतम जानकारी बनाए रखना महत्वपूर्ण है।

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