قبل عامين ، كتبت تنفيذًا بسيطًا للغاية لضغط الصورة النمطي للركاب لعمل الطلاب ونشرت الكود على جيثب .

لدهشتي ، تبين أن المستودع كان شائعًا للغاية ، لذلك قررت تحديث الكود وكتابة مقالة تشرح ذلك والنظرية.

نظرية

هذا الجزء نظري تمامًا ، وإذا كنت مهتمًا فقط بمستندات الشفرة ، فيمكنك تخطيها.

تعيينات ضغط

سمح $$$(E ، د)$ هو الفضاء المتري الكامل ، و $$$f: E \ rightarrow E$ - رسم الخرائط من $$$E$ في $$$E$ .

نحن نقول ذلك $$$و$ هو تعيين الضغط إذا كان موجودا $$$0 <s <1$ بحيث:

$$

$$\ forall x، y \ in E، d (f (x)، f (y)) \ leq sd (x، y)$$

بناء على هذا ، $$$و$ ستشير إلى تعيين ضغط مع نسبة ضغط $$$s$ .

هناك نظريان مهمان حول تعيينات التعاقد: نظرية Banach للنقطة الثابتة ونظرية الكولاج .

نظرية النقطة الثابتة : $$$و$ لديه نقطة ثابتة فريدة من نوعها $$$x_0 دولا$ .


كذلك سوف نشير إلى $$$x_0 دولا$ نقطة ثابتة $$$و$ .

نظرية الكولاج : if $$$d (x، f (x)) <\ epsilon$ ثم $$$d (x، x_0) <\ frac {\ epsilon} {1 - s}$ .


تخبرنا النظرية الثانية أننا إذا وجدنا خريطة انكماش $$$و$ مثل هذا $$$f (x)$ قريب من $$$x$ ، ثم يمكننا أن نكون متأكدين من أن النقطة الثابتة $$$و$ أيضا قريبة من $$$x$ .

هذه النتيجة ستكون الأساس لعملنا في المستقبل. في الواقع ، بدلاً من حفظ الصورة ، يكفي أن نحفظ شاشة الضغط ، التي تكون النقطة الثابتة قريبة من الصورة.

يعرض ضغط للصور

سأوضح في هذا الجزء كيفية إنشاء عروض الضغط هذه بحيث تكون النقطة الثابتة قريبة من الصورة.

أولاً ، دعنا نضبط مجموعة الصور والمسافة. سوف نختار $$$E = [0، 1] ^ {h \ times w}$ . $$$E$ هو الكثير من المصفوفات مع $$$ح$ في الصفوف $$$w$ الأعمدة ومع المعاملات في الفاصل الزمني $$$[0، 1]$ . ثم سنتخذ $$$d (x، y) = \ left (\ sum_ {i = 1} ^ {h} {\ sum_ {j = 1} ^ {w} {(x_ {ij} -y_ {ij}) ^ 2}} \ right) ^ {0.5}$ . $$$د$ هي المسافة التي تم الحصول عليها من القاعدة Frobenius .

سمح $$$x \ في E$ هي الصورة التي نريد ضغطها.

سنقوم بتقسيم الصورة إلى كتل مرتين:

• أولاً ، نقسم الصورة إلى كتل محدودة أو فاصلة $$$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) \ in R_l$$

موافقة : إذا $$$f_l$ يتم التعاقد تعيينات ، ثم و $$$و$ أيضا رسم الخرائط الضغط.


لا يزال هناك سؤال واحد يحتاج إلى إجابة: كيفية الاختيار $$$D_ {k_l}$ و $$$f_l$ ؟

توفر نظرية الكولاج طريقة لاختيارها: if $$$x_ {R_l}$ قريب من $$$f (x_ {D_ {k_l}})$ للجميع $$$ل$ ثم $$$x$ قريب من $$$f (x)$ ومن خلال نظرية الكولاج $$$x$ و $$$x_0 دولا$ هي أيضا قريبة.

لذلك نحن مستقلون للجميع $$$ل$ يمكننا بناء مجموعة من تعيينات الضغط من كل منهما $$$D_ {k}$ في $$$R_l$ واختيار الأفضل. في القسم التالي ، نعرض جميع تفاصيل هذه العملية.

تطبيق

في كل قسم ، سأقوم بنسخ أجزاء التعليمات البرمجية المثيرة للاهتمام ، ويمكن العثور على البرنامج النصي بأكمله هنا .

الأقسام

اخترت نهجا بسيطا جدا. تقوم كتل المصادر وكتل الأوراق بتقسيم الصورة على الشبكة ، كما هو موضح في الصورة أعلاه.

حجم الكتل يساوي صلاحيات اثنين وهذا يبسط العمل إلى حد كبير. كتل المصدر هي 8 في 8 وكتل النهاية هي 4 في 4.

هناك خطط التقسيم أكثر تعقيدا. على سبيل المثال ، يمكننا استخدام شجرة quadtree لتفريق المساحات مع الكثير من التفاصيل بقوة.

التحولات

في هذا القسم ، سأعرض كيفية إنشاء تعيينات ضغط من $$$D_ {k}$ في $$$R_l$ .

تذكر أننا نريد إنشاء مثل هذا التعيين $$$f_l$ إلى $$$f (x_ {D_k})$ كان قريبا من $$$x_ {R_l}$ . أي أنه كلما زادت التعيينات التي ننشئها ، زاد احتمال العثور على تعيينات جيدة.

ومع ذلك ، تعتمد جودة الضغط على عدد البتات المطلوبة للتخزين $$$f_l$ . أي إذا كانت العديد من الوظائف كبيرة جدًا ، فسيكون الضغط سيئًا. هناك حاجة إلى حل وسط هنا.

قررت ذلك $$$f_l$ سوف تبدو مثل هذا:

$$

$$f_l (x_ {D_k}) = s \ times تدوير _ {\ theta} (flip_d (اختزل (x_ {D_k}))) + ب$$

حيث $$ - هذه وظيفة للانتقال من الكتل 8 إلى 8 إلى الكتل 4 إلى 4 ، $$ و $$ - التحولات أفيني ، $$$s$ يغير التباين و $$$ب$ - السطوع.

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) 

للحفاظ على شكل زاوية الصورة $$$\ theta$ يمكن أن تأخذ فقط القيم $$$\ {0 ^ {\ circ} ، 90 ^ {\ circ} ، 180 ^ {\ circ} ، 270 ^ {\ circ} \}$ .

تعكس وظيفة الانعكاس الصورة إذا كان 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 

نحتاج إلى 1 بت لتتذكر ما إذا كان النسخ المتطابق مطلوبًا و 2 بت لزاوية الدوران. علاوة على ذلك ، إذا أنقذنا $$$s$ و $$$ب$ باستخدام 8 بتات لكل قيمة ، سنحتاج إلى 11 بت فقط لحفظ التحويل.

بالإضافة إلى ذلك ، يجب علينا التحقق مما إذا كانت هذه الوظائف عبارة عن تعيينات انكماش. والدليل على ذلك ممل قليلاً ، وليس ما نحتاجه حقًا. ربما في وقت لاحق سوف أضيفه كملحق لهذه المادة.

ضغط

خوارزمية الضغط بسيطة. أولاً ، نقوم بإنشاء جميع التحويلات الممكنة لكل مجموعات المصادر باستخدام دالة 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 ، وإذا كان التحويل الذي تم اختباره هو الأفضل للجميع ، تم حفظه:

 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] 

تفريغ

خوارزمية تخفيف الضغط أكثر بساطة. نبدأ مع صورة عشوائية تمامًا ، ثم نطبق صورة مضغوطة عدة مرات $$$و$ :

 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 بتحميل الصورة وضغطها test_greyscale كل تكرار لضغط الضغط:


ليس سيئا على الإطلاق لمثل هذا التنفيذ البسيط!

صور RGB

تتمثل الطريقة الساذجة للغاية لضغط صور 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 :


ظهرت القطع الأثرية. ربما تكون هذه الطريقة ساذجة جدًا لتحقيق نتائج جيدة.

إلى أين أذهب بعد ذلك

إذا كنت تريد معرفة المزيد عن ضغط الصورة النمطي هندسيًا ، يمكنني أن أنصحك بقراءة مقالة Fractal and Wavelet Image Compression Techniques by Stephen Welsted. إنه سهل القراءة ويشرح تقنيات أكثر تطوراً.