कुछ साल पहले मैंने छात्र के काम के लिए भग्न छवि संपीड़न का एक बहुत ही सरल कार्यान्वयन लिखा था और जीथब पर कोड पोस्ट किया था।

मेरे आश्चर्य के लिए, रिपॉजिटरी काफी लोकप्रिय हो गई, इसलिए मैंने कोड को अपडेट करने और इसे और सिद्धांत को समझाते हुए एक लेख लिखने का फैसला किया।

सिद्धांत

यह हिस्सा काफी सैद्धांतिक है, और यदि आप केवल कोड प्रलेखन में रुचि रखते हैं, तो आप इसे छोड़ सकते हैं।

संपीड़न मैपिंग

चलो $$$(ई, डी)$ पूर्ण मीट्रिक स्थान है , और $$$f: E \ rightarrow E$ - मैपिंग से $$$ई$ पर $$$ई$ ।

हम कहते हैं कि $$$च$ यदि मौजूद है तो एक कंप्रेसिव मैपिंग है $$$0 1 s <1$ ऐसा है कि:

$$

$$\ forall x, y \ E में, d (f (x), f (y)) \ leq sd (x, y)$$

इसके आधार पर, $$$च$ एक संपीड़न अनुपात के साथ एक संपीड़न मानचित्रण को निरूपित करेगा $$$एस$ ।

मैपिंग कॉन्ट्रैक्ट पर दो महत्वपूर्ण प्रमेय हैं: बानाच निश्चित बिंदु प्रमेय और कोलाज प्रमेय ।

निश्चित बिंदु प्रमेय : $$$च$ एक अद्वितीय निश्चित बिंदु है $$$x_0$ ।


इसके अलावा हम निरूपित करेंगे $$$x_0$ निश्चित बिंदु $$$च$ ।

कोलाज प्रमेय : यदि $$$d (x, f (x)) <\ epsilon$ तो $$$d (x, x_0) <\ frac {\ epsilon} {1 - s}$ ।


दूसरा प्रमेय हमें बताता है कि यदि हम एक संकुचन मानचित्र पाते हैं $$$च$ ऐसा है $$$च (x)$ के करीब है $$$x$ , तो हम निश्चित बिंदु पर निश्चित हो सकते हैं $$$च$ के करीब भी है $$$x$ ।

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

छवियों के लिए संपीड़न प्रदर्शित करता है

इस भाग में मैं दिखाऊंगा कि इस तरह के कंप्रेसिव डिस्प्ले कैसे बनाएं ताकि तय बिंदु छवि के करीब हो।

सबसे पहले, आइए इमेज सेट और दूरी सेट करें। हम चुन लेंगे $$$E = [0, 1] ^ {h \ टाइम्स w}$ । $$$ई$ के साथ काफी मैट्रिसेस है $$$ज$ पंक्तियों में $$$w$ स्तंभ और अंतराल में गुणांक के साथ $$$[0, 1]$ । फिर हम लेंगे $$$d (x, y) = \ left (\ sum_ {i = 1} ^ {h} {\ sum_ {j = 1} ^ {w} {(x_ {ij} -y_ {ij}) ^ 2}} \ right) ^ {0.5}$ । $$$ड$ फ्रोबेनियस मानदंड से प्राप्त की गई दूरी है ।

चलो $$ क्या वह छवि जिसे हम कंप्रेस करना चाहते हैं।

हम छवि को दो बार ब्लॉकों में विभाजित करेंगे:

• सबसे पहले, हम छवि को परिमित या अंतराल ब्लॉकों में विभाजित करते हैं $$$R_1, ..., R_L$ । ये ब्लॉक अलग हो गए हैं और पूरी छवि को कवर करते हैं।
• फिर हम छवि को स्रोतों या डोमेन के ब्लॉक में विभाजित करते हैं $$$D_1, ..., D_K$ । ये ब्लॉक आवश्यक रूप से अलग नहीं हैं और जरूरी नहीं कि यह पूरी छवि को कवर करे।

उदाहरण के लिए, हम छवि को इस प्रकार खंडित कर सकते हैं:


फिर प्रत्येक अंतराल ब्लॉक के लिए $$$R_l$ हम एक डोमेन ब्लॉक चुनते हैं $$$D_ {k_l}$ और मानचित्रण $$$f_l: [0, 1] ^ {D_ {k_l}} \ rightarrow [0, 1] ^ {R_ {l}}$ ।

आगे हम एक फंक्शन को परिभाषित कर सकते हैं $$$च$ के रूप में:

$$

$$f (x) _ {ij} = f_l (x_ {D_ {k_l}}) _ _ ij} \ text {if} (i, j) \ _ R_l $ मे$$

अनुमोदन : यदि $$$f_l$ और फिर, मैपिंग अनुबंध कर रहे हैं $$$च$ कम्प्रेसिव मैपिंग भी।


एक प्रश्न शेष है जिसका उत्तर दिया जाना है: कैसे चुनें $$$D_ {k_l}$ और $$$f_l$ ?

कोलाज प्रमेय उन्हें चुनने का एक तरीका प्रदान करता है: यदि $$$x_ {R_l}$ के करीब है $$$f (x_ {D_ {k_l}})$ सभी के लिए $$$ल$ तो $$$x$ के करीब है $$$च (x)$ और महाविद्यालय प्रमेय द्वारा $$$x$ और $$$x_0$ पास भी हैं।

इसलिए हम सभी के लिए स्वतंत्र हैं $$$ल$ हम प्रत्येक से निचोड़ मैपिंग के एक सेट का निर्माण कर सकते हैं $$$D_ {k}$ पर $$$R_l$ और सबसे अच्छा चुनें। अगले भाग में, हम इस ऑपरेशन के सभी विवरण दिखाते हैं।

कार्यान्वयन

प्रत्येक अनुभाग में मैं दिलचस्प कोड अंशों की नकल करूंगा, और पूरी स्क्रिप्ट यहां मिल सकती है ।

विभाजन

मैंने बहुत ही सरल तरीका चुना। स्रोत ब्लॉक और लीफ ब्लॉक एक ग्रिड पर छवि को विभाजित करते हैं, जैसा कि ऊपर की छवि में दिखाया गया है।

ब्लॉकों का आकार दो की शक्तियों के बराबर है और यह काम को बहुत सरल करता है। सोर्स ब्लॉक 8 बाय 8 और एंड ब्लॉक 4 बाय 4 हैं।

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

रूपांतरण

इस खंड में, मैं दिखाऊंगा कि कैसे से संपीड़न मैपिंग बनाएं $$$D_ {k}$ पर $$$R_l$ ।

याद रखें कि हम इस तरह की मैपिंग उत्पन्न करना चाहते हैं $$$f_l$ को $$$f (x_ {D_k})$ के करीब था $$$x_ {R_l}$ । यही है, जितने अधिक मैपिंग हम उत्पन्न करते हैं, उतना ही अच्छा एक खोजने की संभावना है।

हालांकि, संपीड़न की गुणवत्ता स्टोर करने के लिए आवश्यक बिट्स की संख्या पर निर्भर करती है $$$f_l$ । यही है, यदि कई कार्य बहुत बड़े हैं, तो संपीड़न खराब होगा। यहां एक समझौते की जरूरत है।

मैंने तय किया कि $$$f_l$ इस तरह दिखेगा:

$$

$$f_l (x_ {D_k}) = s \ टाइम्स घुमाएँ _ {\ theta} (flip_d (कम करें (x_ {D_k}))) + b$$

जहाँ $$$घट$ - यह ब्लॉक 8 से 8 तक ब्लॉक 4 से 4 तक जाने के लिए एक फ़ंक्शन है, $$$फ्लिप$ और $$$$ घूमती ह$ - परिशोधन परिवर्तन, $$$एस$ इसके विपरीत बदल जाता है, और $$$ब$ - चमक।

reduce कार्य परिवेश के औसत से छवि के आकार को reduce करता है:

 def reduce(img, factor): result = np.zeros((img.shape[0] // factor, img.shape[1] // factor)) for i in range(result.shape[0]): for j in range(result.shape[1]): result[i,j] = np.mean(img[i*factor:(i+1)*factor,j*factor:(j+1)*factor]) return result 

rotate फ़ंक्शन किसी दिए गए कोण द्वारा छवि को घुमाता है:

 def rotate(img, angle): return ndimage.rotate(img, angle, reshape=False) 

छवि कोण के आकार को बनाए रखने के लिए $$$$ थीटा$ केवल मूल्य ले सकते हैं $$$\ {0 ^ {\ circ}, 90 ^ {\ circ}, 180 ^ {\ circ}, 270 ^ {\ circ} \ $ ।

flip फ़ंक्शन छवि को प्रतिबिंबित करता है यदि direction -1 है और मान 1 होने पर प्रतिबिंबित नहीं करता है:

 def flip(img, direction): return img[::direction,:] 

पूर्ण रूपांतरण apply_transformation फ़ंक्शन द्वारा किया जाता है:

 def apply_transformation(img, direction, angle, contrast=1.0, brightness=0.0): return contrast*rotate(flip(img, direction), angle) + brightness 

मिररिंग की आवश्यकता है, और रोटेशन के कोण के लिए 2 बिट्स को याद रखने के लिए हमें 1 बिट की आवश्यकता है। इसके अलावा, अगर हम बचाते हैं $$$एस$ और $$$ब$ प्रत्येक मान के लिए 8 बिट्स का उपयोग करना, रूपांतरण को बचाने के लिए हमें केवल 11 बिट्स की आवश्यकता होगी।

इसके अलावा, हमें जांचना चाहिए कि क्या ये कार्य संकुचन मैपिंग हैं। इसका प्रमाण थोड़ा उबाऊ है, और वास्तव में हमें क्या चाहिए। शायद बाद में मैं इसे लेख में एक परिशिष्ट के रूप में जोड़ दूंगा।

दबाव

संपीड़न एल्गोरिदम सरल है। सबसे पहले, हम Gener_all_transformed_blocks फ़ंक्शन का उपयोग करते हुए सभी स्रोत ब्लॉकों के सभी संभावित affine परिवर्तनों को generate_all_transformed_blocks करते हैं:

 def generate_all_transformed_blocks(img, source_size, destination_size, step): factor = source_size // destination_size transformed_blocks = [] for k in range((img.shape[0] - source_size) // step + 1): for l in range((img.shape[1] - source_size) // step + 1): # Extract the source block and reduce it to the shape of a destination block S = reduce(img[k*step:k*step+source_size,l*step:l*step+source_size], factor) # Generate all possible transformed blocks for direction, angle in candidates: transformed_blocks.append((k, l, direction, angle, apply_transform(S, direction, angle))) return transformed_blocks 

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

 def compress(img, source_size, destination_size, step): transformations = [] transformed_blocks = generate_all_transformed_blocks(img, source_size, destination_size, step) for i in range(img.shape[0] // destination_size): transformations.append([]) for j in range(img.shape[1] // destination_size): print(i, j) transformations[i].append(None) min_d = float('inf') # Extract the destination block D = img[i*destination_size:(i+1)*destination_size,j*destination_size:(j+1)*destination_size] # Test all possible transformations and take the best one for k, l, direction, angle, S in transformed_blocks: contrast, brightness = find_contrast_and_brightness2(D, S) S = contrast*S + brightness d = np.sum(np.square(D - S)) if d < min_d: min_d = d transformations[i][j] = (k, l, direction, angle, contrast, brightness) return transformations 

सबसे अच्छा कंट्रास्ट और ब्राइटनेस खोजने के लिए, find_contrast_and_brightness2 मेथड से कम से कम वर्ग समस्या हल होती है:

 def find_contrast_and_brightness2(D, S): # Fit the contrast and the brightness A = np.concatenate((np.ones((S.size, 1)), np.reshape(S, (S.size, 1))), axis=1) b = np.reshape(D, (D.size,)) x, _, _, _ = np.linalg.lstsq(A, b) return x[1], x[0] 

unpacking

विघटन एल्गोरिथ्म भी सरल है। हम पूरी तरह से यादृच्छिक छवि के साथ शुरू करते हैं, और फिर कई बार निचोड़ छवि लागू करते हैं $$$च$ :

 def decompress(transformations, source_size, destination_size, step, nb_iter=8): factor = source_size // destination_size height = len(transformations) * destination_size width = len(transformations[0]) * destination_size iterations = [np.random.randint(0, 256, (height, width))] cur_img = np.zeros((height, width)) for i_iter in range(nb_iter): print(i_iter) for i in range(len(transformations)): for j in range(len(transformations[i])): # Apply transform k, l, flip, angle, contrast, brightness = transformations[i][j] S = reduce(iterations[-1][k*step:k*step+source_size,l*step:l*step+source_size], factor) D = apply_transformation(S, flip, angle, contrast, brightness) cur_img[i*destination_size:(i+1)*destination_size,j*destination_size:(j+1)*destination_size] = D iterations.append(cur_img) cur_img = np.zeros((height, width)) return iterations 

यह एल्गोरिथ्म काम करता है क्योंकि संपीड़न मानचित्र में एक विशिष्ट निश्चित बिंदु है, और कोई फर्क नहीं पड़ता कि हम किस स्रोत की छवि चुनते हैं, हम इसके लिए प्रयास करेंगे।

मुझे लगता है कि समय एक छोटे से उदाहरण के लिए आ गया है। मैं बंदर छवि को संपीड़ित और खोलना चाहूंगा:


test_greyscale फ़ंक्शन छवि को लोड करता है, इसे संपीड़ित करता है, इसे विघटित करता है, और विघटन के प्रत्येक पुनरावृत्ति को दिखाता है:


इस तरह के एक सरल कार्यान्वयन के लिए बिल्कुल भी बुरा नहीं है!

आरजीबी चित्र

RGB छवियों को संपीड़ित करने के लिए एक बहुत ही भोली दृष्टिकोण सभी तीन चैनलों को व्यक्तिगत रूप से संपीड़ित करने के लिए है:

 def compress_rgb(img, source_size, destination_size, step): img_r, img_g, img_b = extract_rgb(img) return [compress(img_r, source_size, destination_size, step), \ compress(img_g, source_size, destination_size, step), \ compress(img_b, source_size, destination_size, step)] 

और अनपैकिंग के लिए, हम केवल तीन चैनलों के डेटा को अलग से अनपैक करते हैं और उन्हें तीन इमेज चैनलों में इकट्ठा करते हैं:

 def decompress_rgb(transformations, source_size, destination_size, step, nb_iter=8): img_r = decompress(transformations[0], source_size, destination_size, step, nb_iter)[-1] img_g = decompress(transformations[1], source_size, destination_size, step, nb_iter)[-1] img_b = decompress(transformations[2], source_size, destination_size, step, nb_iter)[-1] return assemble_rbg(img_r, img_g, img_b) 

एक और बहुत ही सरल उपाय तीनों चैनलों के लिए एक ही संपीड़न डिस्प्ले का उपयोग करना है, क्योंकि वे अक्सर बहुत समान होते हैं।

यदि आप यह जांचना चाहते हैं कि यह कैसे काम करता है, तो test_rgb फ़ंक्शन test_rgb :


कलाकृतियाँ दिखाई दीं। यह विधि शायद अच्छे परिणाम उत्पन्न करने के लिए बहुत भोली है।

आगे कहाँ जाना है

यदि आप फ्रैक्टल इमेज कम्प्रेशन के बारे में अधिक जानना चाहते हैं, तो मैं आपको स्टीफन वेलस्टेड द्वारा आर्टिकल फ्रैक्टल और वेवलेट इमेज कंप्रैशन तकनीक पढ़ने की सलाह दे सकता हूं। अधिक परिष्कृत तकनीकों को पढ़ना और व्याख्या करना आसान है।