advertisement

Image Compression using SVD

80 %
20 %
advertisement
Information about Image Compression using SVD
Technology

Published on January 27, 2014

Author: gmpapado

Source: slideshare.net

Description

Applied Computational Methods Project's Report - University of Patras - Electrical and Computer Engineering
advertisement

Πανεπιςτήμιο Πατρών Τμήμα Ηλεκτρολόγων Μηχανικών και Τεχνολογίασ Υπολογιςτών Τομζασ Συςτημάτων Αυτομάτου Ελζγχου Εφαρμοςμζνεσ Υπολογιςτικζσ Μζθοδοι Project ζην κάζεκα “Εθαρκοζκέλες Υποιογηζηηθές Μέζοδοη” κε ζέκα “Σσκπίεζε εηθόλας κε ηδηάδοσζες ηηκές” Σςμμεηέσονηερ:  Παπαδόπνπινο Γεώξγηνο – Μάξηνο, 7356 Έηορ: 2013 Εξάμηνο: 9o 1|Σελίδα

Πανεπιςτήμιο Πατρών Τμήμα Ηλεκτρολόγων Μηχανικών και Τεχνολογίασ Υπολογιςτών Τομζασ Συςτημάτων Αυτομάτου Ελζγχου Εφαρμοςμζνεσ Υπολογιςτικζσ Μζθοδοι Σκοπόρ Απηό ην project έρεη ζαλ ζθνπό λα εθαξκόζεη ηελ δηάζπαζε ηδηαδνπζώλ ηηκώλ ζηε ζπκπίεζε εηθόλσλ (Singular Value Decomposition-SVD to Image Compression). Οη ζπγθξίζεηο γίλνληαη κεηαμύ ησλ ζπκπηεζκέλσλ θαη ηεο αξρηθήο εηθόλαο ε νπνία είλαη ζηε κνξθή JPEG. Σθνπόο καο είλαη λα εμεηάζνπκε αλ ε SVD κπνξεί λα εθαξκνζζεί ζαλ κέζνδνο ζπκπίεζεο εηθόλαο ζε έγρξσκεο θσηνγξαθηθέο εηθόλεο. Παξόηη νη SVD θσηνγξαθίεο δελ ζπκπηέδνληαη ην ίδην θαιά κε ηηο JPEG, ηα απνηειέζκαηα είλαη ηθαλνπνηεηηθά. 2|Σελίδα

Πανεπιςτήμιο Πατρών Τμήμα Ηλεκτρολόγων Μηχανικών και Τεχνολογίασ Υπολογιςτών Τομζασ Συςτημάτων Αυτομάτου Ελζγχου Εφαρμοςμζνεσ Υπολογιςτικζσ Μζθοδοι Πεπιεσόμενα 1. Αναπαπάζηαζη εικόνων ζηον ςπολογιζηή 1.1 Απεικόνιζη εικόνων ζηον ςπολογιζηή 1.2 Αναπαπάζηαζη ενόρ pixel 1.3 Σςμπίεζη εικόναρ 2. SVD – Singular Value Decomposition 2.1 Ειζαγωγή 2.2 Θεώπημα:Διάζπαζη Ιδιαζοςζών Τιμών 2.3 Μείζη Διαζηάζεων 3. Υλοποίηζη SVD 3.1 O Αλγόπιθμορ 3.2 Παπάδειγμα SVD 3.3 Απαιηούμενη Μνήμη 4. Κώδικαρ MatLab 3|Σελίδα

Πανεπιςτήμιο Πατρών Τμήμα Ηλεκτρολόγων Μηχανικών και Τεχνολογίασ Υπολογιςτών Τομζασ Συςτημάτων Αυτομάτου Ελζγχου Εφαρμοςμζνεσ Υπολογιςτικζσ Μζθοδοι Ειζαγωγή Οη εηθόλεο είλαη έλα πνιύ ζεκαληηθό θνκκάηη ησλ ππνινγηζηώλ ηελ ζεκεξηλή επνρή. Τα πεξηζζόηεξα web-sites ζην δηαδίθηπν ρξεζηκνπνηνύλ πνιιέο εηθόλεο. Έλα κεγάιν πνζνζηό ηνπ εύξνπο κεηάδνζεο θαη απνζεθεπηηθέο επθνιίεο πεξηεξηδνληαη από ην κέγεζνο ησλ εηθόλσλ. Η κείσζε ηνπ κεγέζνπο ηεο εηθόλαο δηαηεξώληαο ηελ πνηόηεηα ηεο εηθόλαο είλαη πνιύ ζεκαληηθό, αιιηώο ηα ζπζηήκαηα ζα θσιύνληαη ηειείσο. Από ην 1990, ε έθδνζε JPEG πηνζεηήζεθε ζαλ standard γηα θσηνγξαθηθέο εηθόλεο ζην δηαδίθηπν. Απηό ην project πινπνηεί κηα άιιε κέζνδν γηα ζπκπίεζε εηθόλεο ρξεζηκνπνηώληαο ηε δηάζπαζε ηδηάδνπζσλ ηηκώλ (Singular Value Decomposition – SVD). 4|Σελίδα

Πανεπιςτήμιο Πατρών Τμήμα Ηλεκτρολόγων Μηχανικών και Τεχνολογίασ Υπολογιςτών Τομζασ Συςτημάτων Αυτομάτου Ελζγχου Εφαρμοςμζνεσ Υπολογιςτικζσ Μζθοδοι 1 Αναπαπάζηαζη εικόνων ζηον ςπολογιζηή 1.1 Απεικόνιζη εικόνων ζηον ςπολογιζηή Έλαο ππνινγηζηήο αλαπαξηζηά κηα εηθόλα ζε κηα ζπζθεπή απεηθόληζεο ζαλ έλα ζύλνιν από εμίζνπ ηζαπέρνληα ρξσκαηηζκέλεο ηειείεο νη νπνίεο απνθαινύληαη pixels (ζηνηρεία εηθόλσλ). Αλ απηά ηα pixels είλαη αξθεηά θνληά, πξνζεγγίδνπλ κηα ζπλερή εηθόλα. Σε απηό ην project όιεο νη εηθόλεο ζεσξνύληαη όηη είλαη νξζνγώληα. Μηα θιαζζηθή νζόλε ππνινγηζηή έρεη πεξηνρή εηθόλαο 768 x 1024 pixels. Όηαλ κηα εηθόλα ζαξώλεηαη ζε έλαλ ππνινγηζηή, έλα πιέγκα επηθαιύπηεηαη. Η εηθόλα δεηγκαηνιεπηείηαη ζε θάζε θπςέιε ηνπ πιέγκαηνο. Τν δείγκα δεκηνπξγεί έλα κέζν όξν ηεο πιεξνθνξίαο ρξώκαηνο πνπ πεξηέρεηαη ζε απηήλ ηελ θπςέιε. Απηή ε δηαδηθαζία νλνκάδεηαη ςεθηνπνίεζε. Έλα ζεκαληηθό ζεκείν ην νπνίν αμίδεη παξαηήξεζεο είλαη όηη ε αλαπαξάζηαζε ζηνλ ππνινγηζηή ηεο εηθόλαο είλαη κηα πξνζέγγηζε. 1.2 Αναπαπάζηαζη ενόρ Pixel Κάζε pixel αλαπαξηζηά έλα θνκκάηη ηεο εηθόλαο, αιιά πώο όιε απηή ε ζρεηηθή πιεξνθνξία ζπλδέεηαη; Σε κηα απιή πεξίπησζε αζπξόκαπξσλ εηθόλσλ θάζε pixel κπνξεί λα έρεη δύν θαηαζηάζεηο. Αλ ε εηθόλα ζε θιίκαθα ηνπ γθξη ηνηε θάζε pixel αλαπαξηζηά ηελ θσηεηλόηεηα ρξεζηκνπνηώληαο έλαλ πξαγκαηηθό αξηζκν από 0 (καύξν) εσο  . Ωζηόζν δελ είλαη δπλαηή ε απεηθόληζε pixels κε άπεηξε θσηεηλόηεηα, έηζη έλα άλσ όξην ππάξρεη γηα ηελ θσηεηλόηεηα θάζε pixel. Μηα βνιηθή αλαπαξάζηαζε ρξεζηκνπνηεί ρξεζηκνπνηεί πξαγκαηηθνύο αξηζκνύο ζην πεδίν [0...1]. Ωζηόζν ε ζπζθεπή απεηθόληζεο είλαη ηθαλή λα ρεηξηζηεί κόλν έλα πεπεξαζκέλν αξηζκό δηαθνξεηηθώλ θσηεηλνηήησλ, έηζη θβαληίδνπκε ηα pixels ζε δηαθξηηέο ζηάζκεο. Μηα θνηλή θβάληηζε ρξεζηκνπνηεί 256 ζηάζκεο θσηεηλόηεηαο 5|Σελίδα

Πανεπιςτήμιο Πατρών Τμήμα Ηλεκτρολόγων Μηχανικών και Τεχνολογίασ Υπολογιςτών Τομζασ Συςτημάτων Αυτομάτου Ελζγχου Εφαρμοςμζνεσ Υπολογιςτικζσ Μζθοδοι (256 = 28) ε νπνία είλαη κηα βνιηθή ηηκή γηα ππνινγηζηέο θαζώο θάζε pixel κπνξεί λα αλαπαξαζηαζεί ζαλ έλα 8-bit byte. Έγρξσκα ζήκαηα είλαη πην πεξίπινθα θαζώο ε πιεξνθνξία είλαη πνιπδηάζηαηε. Ο ρξσκαηηθόο ρώξνο πνπ ρξεζηκνπνηείηαη από ηνπο πεξηζζόηεξνπο ππνινγηζηέο είλαη έλαο ηξηζδηάζηαηνο Red Green Blue (RGB) ρώξνο. Κάζε pixel είλαη έλα ηξηζδηάζηαην δηάλπζκα κε θάζε ζηνηρείν λα αλαπαξηζηά ηε θσηεηλόηεηα ησλ βαζηθώλ ρξσκαηηθώλ ζπζηαηηθώλ θόθθηλν (red), πξάζηλν(green) θαη κπιε (blue). Τσλ πεξηζζόηεξσλ ππνινγηζηώλ νη νζόλεο ρξεζηκνπνηνύλ έλα RGB ρξσκαηηθό ρώξν. Οη εθηππσηέο σζηόζν ρξεζηκνπνηνύλ Cyan, Magenta, Yellow ρξσκαηηθό ρώξν (ηα βαζηθά ρξώκαηα γηα αλαθινύκελν θσηηζκό). Γελ κπνξεί όιε ε ρξσκαηηθή πιεξνθνξία λα θσδηθνπνηεζεί ζε ηξεηο δηαζηάζεηο. Μέζα ζηνλ RGB ρξσκαηηθό ρώξν, πνηθίιεο αλαπαξαζηάζεηο κπνξνύλ λα ρξεζηκνπνηεζνύλ γηα θάζε pixel. Η πην απιή πεξηέρεη ηε ζηάζκε θσηεηλόηεηαο γηα θάζε βαζηθό ρξώκα ζε έλα δηάλπζκα. Μηα άιιε αλαπαξάζηαζε είλαη ν Hue, Saturation, Value (HSV) ρώξνο. Σε απηήλ ην Value αλαπαξηζηά ηελ θσηεηλόηεηα ηεο ζπλδπαδόκελεο γθξίδαο θιίκαθνο εηθόλα, ην Hue ππνδεηθλύεη ηε γσλία ηνπ ρξσκαηηθνύ ηξνρνύ θαη ην Saturation ππνδεηθλύεη πόζν από απηό ην ρξώκα ρξεζηκνπνηείηαη. Τν RGB κπνξεί λα ρξεζηκνπνηεζεί κε θαλνληθέο θαξηεζηαλέο ζπληεηαγκέλεο ζε 3 ρώξνπο, ελσ HSV κπνξεί λα ζπγθξηζεί ζε έλα ηύπν πνιηθώλ ζπληεηαγκέλσλ. Μηα άιιε αλαπαξάζηαζε ρξεζηκνπνηείηαη από ην NTSC ζύζηεκα ηειεόξαζεο. Απνηειείηαη από έλα ζπζηαηηθό γάκκα (θσηεηλόηεηα θιίκαθαο ηνπ γθξη - greyscale) θαη δύν ζπζηαηηθά ρξσκαύγεηαο (chrominance). Αλαθέξεηαη ζαλ ρώξνο YIQ, όπνπ ην Υ αλαθέξεηαη ζην ζήκα ηεο θιίκαθαο ηνπ γθξη θαη ηα Ι θαη Q είλαη ηα ζήκαηα ρξσκαύγεηαο. Δλώ ην RGB είλαη ην απινύζηεξν ζηε ρξήζε, ππάξρνπλ πιενλεθηήκαηα ρξεζηκνπνηώληαο άιιεο αλαπαξαζηάζεηο. Τν πην ζνβαξό είλαη όηη κε ηελ θιηκάθσζε ηνπ saturation, κπνξνύκε λα 6|Σελίδα

Πανεπιςτήμιο Πατρών Τμήμα Ηλεκτρολόγων Μηχανικών και Τεχνολογίασ Υπολογιςτών Τομζασ Συςτημάτων Αυτομάτου Ελζγχου Εφαρμοςμζνεσ Υπολογιςτικζσ Μζθοδοι πξνζνκνηώζνπκε ην θαηλόκελν ηνπ ρξσκαηηθνύ ειέγρνπ ζε έλα ζεη ηειεόξαζεο. Απηό δελ ζρεηίδεηαη κε απηό ην project, σζηόζν ππάξρνπλ κεξηθά πιενλεθηήκαηα ζηε ρξήζε ελαιιαθηηθώλ αλαπαξαζηάζεσλ εμαηηίαο ηεο θύζεο ηνπ αλζξώπηλνπ καηηνύ. 1.3 Σςμπίεζη Εικόναρ Όηαλ έρνπκε πξνθαζνξίζεη ην ρξσκαηηθό ρώξν, θάζε pixel απνζεθεύεηαη ζαλ έλα δηάλπζκα ζην ρώξν. Αλ κηα εηθόλα απνηειείηαη από m x n pixels ζηνλ RGB ρξσκαηηθό ρώξν , ηόηε κηα εηθόλα ρξεηάδεηαη 3mn ζηνηρεία γηα λα αλαπαξαζηαζεί. Σε απηή ηελ εξγαζία θάζε pixel κπνξεί λα έρεη κηα απν ηηο 256 δηαθξηηέο ζηάζκεο θσηεηλόηεηαο. Μηα θιαζζηθή εηθόλα κεγέζνπο 480 x 640 κε κεζαία αλάιπζε ρξεηάδεηαη 921600 ζηνηρεία γηα λα απνζεθεπηεί (  0.9Μbytes). Αλ θαη νη ππνινγηζηέο κπνξνύλ λα ρεηξηζηνύλ αξρεία ηέηνηνπ κεγέζνπο (ή θαη πνιύ κεγαιύηεξσλ) γηα επεμεξγαζία, όηαλ πνιιέο εηθόλεο πξέπεη λα απνζεθεπηνύλ ή λα κεηαθεξζνύλ νη απαηηήζεηο γηα ρσξεηηθόηεηα θαη εύξνο δώλεο γίλνληαη ηεξάζηηεο. Η ζπκπίεζε εηθόλαο εθκεηαιιεύεηαη ην γεγνλόο όηη νη εηθόλεο δελ είλαη έλα ηπραίν ζύλνιν από ρξσκαηηζκέλεο ηειείεο αιιά έρνπλ κηα ζπγθεθξηκέλε δνκή. Απηή ηελ δνκή κπνξνύκε λα εθκεηαιιεηνύκε γηα λα αλαπαξαζηήζνπκε ηελ εηθόλα κε ιηγόηεξα ζηνηρεία. Υπάξρνπλ δύν είδε ζπκπίεζε εηθόλαο (παξνπζηάδνληαη παξαθάησ). Σςμπίεζη εικόναρ σωπίρ απώλειερ Με έλαλ αιγόξηζκν ζπκπίεζεο εηθόλαο ρσξίο απώιεηεο, κηα αλαθαζθεπαζκέλε εηθόλα (απνζπκπηεζκέλε) είλαη αθξηβώο ε ίδηα, pixel κε pixel, κε ηελ αξρηθή αζπκπίεζηε εηθόλα. Μηα ξνπηίλα ζπκπίεζεο ζα πξνζπαζήζεη λα δηαιέμεη πνηθίια ραξαθηεξηζηηθά ηεο εηθόλαο θαη λα ηα αλαπαξαζηήζεη κε ιηγόηεξα ζηνηρεία. Γηα παξάδεηγκα κηα εηθόλα ε νπνία πεξηέρεη έλα κεγάιν θόθθηλν ηεηξάγσλν, ε ξνπηίλα ζπκπίεζεο ζα εληνπίζεη απηό θαη αληί γηα λα απνζεθεύζεη θάζε θόθθηλν pixel, απιά ζα απνζεθεύζεη ην κέγεζνο, ηελ ζέο θαη ην ρξώκα ηνπ ηεηξαγώλνπ. Σςμπίεζη εικόναρ με απώλειερ 7|Σελίδα

Πανεπιςτήμιο Πατρών Τμήμα Ηλεκτρολόγων Μηχανικών και Τεχνολογίασ Υπολογιςτών Τομζασ Συςτημάτων Αυτομάτου Ελζγχου Εφαρμοςμζνεσ Υπολογιςτικζσ Μζθοδοι Απηόο ν ηύπνο ηνπ αιγνξίζκνπ ζπκπίεζεο δε δηαηεξεί ηελ αθξηβή εηθόλα από pixel ζε pixel. Ωζηόζν ρξεζηκνπνεί ην πιενλέθηεκα ησλ πεξηνξηζκώλ ηνπ αλζξσπίλνπ καηηνύ λα κελ θαηαιαβαίλεη ηηο πξνζεγγίζεηο ηεο αξρηθήο εηθόλαο. Απηνί νη αιγόξηζκνη κπνξνύλ λα πεηύρνπλ πνιύ αλώηεξεο ηάμεηο ζπκπίεζεο από κεζόδνπο ρσξίο απώιεηεο, αιιά πξέπεη λα ρξεζηκνπνηνύληαη κε ζπλαίζζεζε. Αιγόξηζκνη ζπκπίεζεο κε απώιεηεο δνπιεύνπλ θαιά κε θσηνγξαθίεο ηεο θαζεκεξηλόηεηαο, ζπρλά δίλνπλ θαηαζηξνθηθα απνηειέζκαηα κε άιινπο ηύπνπο εηθόλσλ όπσο ηέρλεο ή θείκελν. Σπκπηέδνληαο ηεο εηθόλα αξθεηέο θνξέο ζα πξνθαιέζνπκε επηδείλσζε ηεο κε κε απνδεθηή εκθάληζε. Με απηό ηνλ ηόπν γίλεηαη θαηαλνεηό όηη ε ζπκπίεζε κε απώιεηεο κπνξεί λα ρξεζηκνπνηεζεί κόλν κεηά ηελ επεμεξγαζία ηεο εηθόλαο ελώ ζα έπξεπε λα απνθεπρζεί ζε ελδηάκεζα ζηάδηα. Δπηπξόζζεηα, ην γεγνλόο όηη ε ηειηθή εηθόλα κνηάδεη ζηελ αξρηθή νθείιεηαη απνθιεηζηηθά ζην αλζξώπηλν κάηη. 8|Σελίδα

Πανεπιςτήμιο Πατρών Τμήμα Ηλεκτρολόγων Μηχανικών και Τεχνολογίασ Υπολογιςτών Τομζασ Συςτημάτων Αυτομάτου Ελζγχου Εφαρμοςμζνεσ Υπολογιςτικζσ Μζθοδοι 2 SVD – Singular Value Decomposition 2.1 Ειζαγωγή Η δηάζπαζε ηδηνδνπζώλ ηηκώλ δέρεηαη έλαλ πίλαθα A δηαζηάζεσλ m x n θαη ππνινγίδεη ηξεηο πίλαθεο ηνπο U, S, θαη V. O S είλαη έλα δηαγώληνο m x n πίλαθαο (ίδηεο δηαζηάζεηο κε ηνλ Α). Ο U θαη ν V είλαη πίλαθεο κεγέζνπο m x m θαη n x n αληίζηνηρα. Οη πίλαθεο ζρεηίδνληαη κε ηελ εμίζσζε: A  USV T (1) Ο ππνινγηζκόο ηνπ SVD έγγπηαη ζην λα βξνύκε ηα ηδηνδηαλύζκαηα θαη ηηο ηδηνηηκέο ησλ ΑΑΤ θαη ΑΤΑ. Τα ηδηνδηαλύζκαηα ηνπ ΑΤΑ δεκηνπξγνύλ ηηο ζηήιεο ηνπ V θαη ηα ηδηνδηαλύζκαηα ηνπ ΑΑΤ δεκηνπξγνύλ ηηο ζηήιεο ηνπ U. Οη ηδηνηηκέο ηνπ ΑΤΑ ή ηνπ ΑΑΤ είλαη ηα ηεηξάγσλα ησλ ηδηνδνπζώλ ηηκώλ ηνπ Α. Οη ηδηάδνπζεο ηηκέο είλαη ηα δηαγώληα ζηνηρεία ηνπ πίλαθα S θαη δηαηάζζνληαη ζε θζίλνπζα ζεηξά. Δπίζεο είλαη πάληα πξαγκαηηθνί αξηζκνί. Αλ ν πίλαθαο Α είλαη πξαγκαηηθόο, ηόηε νη U θαη V είλαη επίζεο πξαγκαηηθνί. Η εμίζσζε (1) κπνξεί λα εθθξαζηεί σο: A minm , n  i 1 u i s i vT i (2) όπνπ ui θαη vi είλαη ην η-νζηό δηάλπζκα ζηήιε ησλ U θαη V αληίζηνηρα, θαη si είλαη νη ηδηάδνπζεο ηηκέο. Ο πίλαθαο Α κπνξεί λα πξνζεγγηζηεί από ηνλ πίλαθα (rank) k από ηελ ζρέζε: k A   u i s i vT i  κε ηάμε (3) i 1 Η 2εξε-λόξκα ηνπ πίλαθα κπνξεί λα ππνινγηζηεί από ηηο ηδηάδνπζεο ηηκέο. Με απηό ηνλ ηξόπν ν πίλαθαο ζθάικαηνο      είλαη 9|Σελίδα

Πανεπιςτήμιο Πατρών Τμήμα Ηλεκτρολόγων Μηχανικών και Τεχνολογίασ Υπολογιςτών Τομζασ Συςτημάτων Αυτομάτου Ελζγχου Εφαρμοςμζνεσ Υπολογιςτικζσ Μζθοδοι ίζνο κε ηελ επόκελε ηδηάδνπζα ηηκή πνπ δελ ρξεζηκνπνηείηαη ζηνλ  . Καζώο νη ηδηάδνπζεο ηηκέο είλαη ζε θζίλνπζα ζεηξά, παξαηεξνύκε όηη ην ζθάικα κεηώλεηαη πξνο ην κεδέλ. 2.2 Θεώπημα: Διάζπαζη Ιδιαζοςζών Τιμών Έζησ Α έλαο m x n πίλαθαο κε ηάμε r. Τόηε ππάξρεη έλαο m x n πίλαθαο Σ όπνπ  D 0 S ,  0 0 κε (m-r) ζεηξέο νη νπνίεο έρνπλ όιεο κεδεληθά ζηνηρεία, (n-r) ζηήιεο νη νπνίεο έρνπλ όιεο κεδεληθά ζηνηρεία θαη D είλαη έλαο r x r δηαγώληνο πίλαθαο (γηα θάπνηα r δελ μεπεξλά ην κηθξόηεξν m θαη n. Τα δηαγώληα ζηνηρεία ηνπ D είλαη νη πξώηεο r ηδηάδνπζεο ηηκέο ηνπ Α: s1  s2  ...  sr 0 θαη ππαξρεη έλαο νξζνγώληνο πίλαθαο m x n U θαη έλαο νξζνγώληνο πίλαθαο n x n V ηέηνηνο ώζηε λα ηζρύεη ε (1). 2.3 Μείωζη Διαζηάζεων Πνηόο ν ιόγνο όκσο λα κεηαζρεκαηίζνπκε ηνλ πίλαθα Α ζε USV T . Θέινπκε λα πξνζεγγίζνπκε ηνλ m x n πίλαθα Α ρξεζηκνπνηώληαο πνιύ ιηγόηεξα ζηνηρεία από ηνλ αξρηθό πίλαθα. Φξεζηκνπνηώληαο ηελ ηάμε ηνπ πίλαθα, δηώρλνπκε ηελ πιεξνθνξία πνπ δελ καο ρξεηάδεηαη όηαλ r  m ή r  n. T T T T   s1u1v1  s2u2v2  ...  sr ur vr  sr 1ur 1vr 1  ... Αθνύ νη ηδηάδνπζεο ηηκεο είλαη κεγαιύηεξεο από ην κεδέλ. Πξνζζέηνληαο ηνπο εμαξηώκελνπο όξνπο όπνπ νη ηδηάδνπζεο ηηκέο είλαη ίζεο κε ην κεδέλ, δελ επεξεάδνπκε ηελ εηθόλα. Γηώρλνληαο ηνπο κεδεληθνύο όξνπο ζην ηέινο ηεο εμίζσζεο, έρνπκε: T T T   s1u1v1  s2u2v2  ...  sr ur vr (4) Έλαο ηξόπνο λα ζπκπηέζνπκε ηελ εηθόλα είλαη λα πξνζεγγίζνπκε ηνλ Α κε έλαλ πίλαθα κηθξόηεξεο ηάμεο. Αλ k<r ηόηε ε πιεζηέζηεξε πξνζέγγηζε ηνπ Α, (rankA = r) – από έλαλ πίλαθα ηάμεο k ν νπνίνο είλαη ζηελ νπζία απόθνπή ηεο (4) γηα ηνπο k πξώηνπο όξνπο – είλαη: 10 | Σ ε λ ί δ α

Πανεπιςτήμιο Πατρών Τμήμα Ηλεκτρολόγων Μηχανικών και Τεχνολογίασ Υπολογιςτών Τομζασ Συςτημάτων Αυτομάτου Ελζγχου Εφαρμοςμζνεσ Υπολογιςτικζσ Μζθοδοι T T T   Ak  s1u1v1  s2u2v2  ...  sk uk vk 11 | Σ ε λ ί δ α (5)

Πανεπιςτήμιο Πατρών Τμήμα Ηλεκτρολόγων Μηχανικών και Τεχνολογίασ Υπολογιςτών Τομζασ Συςτημάτων Αυτομάτου Ελζγχου Εφαρμοςμζνεσ Υπολογιςτικζσ Μζθοδοι 3 Υλοποίηζη SVD 3.1 Ο Αλγόπιθμορ Σην ζεκείν απηό πεξηγξάθνπκε ηνλ αιγόξηζκν πνπ αθνινπζνύκε ζηνλ θώδηθα πνπ γξάθηεθε ζην MatLab. Τα βήκαηα πνπ αθνινπζήζεθαλ είλαη ηα εμήο: I. II. III. IV. V. Υπνινγηζκόο ησλ ΑΑΤ θαη ΑΤΑ Υπνινγηζκόο ηδηνηηκώλ θαη ηνπ πίλαθα S Βξίζθνπκε ηνλ U Βξίζθνπκε ηνλ V Υπνινγίδνπκε ηνλ SVD Οη πίλαθεο U, S θαη V έρνπλ ηελ αθόινπζε κνξθή ν θαζέλαο: U  u1  s1 ... un  , S   0  0  0 0 0 0  sn   θαη  v1  V      vn    T 3.2 Παπάδειγμα SVD Έλαο πίλαθαο 2 x 2 ηάμεο δπν είλαη κηα θπζηθή επηινγή γηα παξάδεηγκα ηεο SVD πξνζέγγηζεο θαζώο νη πεξηζζόηεξεο εηθόλεο αδηακθεζβήηεηα ζα έρνπλ πιήξε ηάμε. Έζησ έλαο πίλαθαο Α:  2 2 A   1 1  ηόηε ν αλάζηξνθνο ηνπ ζα είλαη:  2 1 AT    2 1  Τν πξώην βήκα (Ι) ηνπ SVD είλαη ν ππνινγηζκόο ησλ ΑΑΤ θαη ΑΤΑ: 12 | Σ ε λ ί δ α

Πανεπιςτήμιο Πατρών Τμήμα Ηλεκτρολόγων Μηχανικών και Τεχνολογίασ Υπολογιςτών Τομζασ Συςτημάτων Αυτομάτου Ελζγχου Εφαρμοςμζνεσ Υπολογιςτικζσ Μζθοδοι  2 2   2 1 8 0         1 1   2 1   2 0   2 1  2 2  5 3         2 1   1 1  3 5 Τν δεύηεξν βήκα (ΙΙ) ηεο δηαδηθαζίαο είλαη λα βξόπκε ηηο ηδηνηηκέο ησλ ΑΤΑ θαη ΑΑΤ. Όηαλ ηηο βξόπκε κπνξνύκε εύθνια λα ππνινγίζνπκε ηηο ηδηάδνπζεο ηηκέο παίξλνληαο ηηο ηεηξαγσληθέο ξίδεο ησλ ηδηνηηκώλ ι1 θαη ι2. Έρνληαο ηηο s1 θαη s2 κπνξνύκε λα ζρεκαηίζνπκε ηνλ S, AAT   I  0 (6) AT A   I  0 (7) Λύλνληαο ηελ (6) δεκηνπξγεί ηα ι1 θαη ι2: AAT   I  0 8 0  1 0  0 2    0 1   0     8 0 0 2 0 8    2     0 1  8 2  2 Τώξα πνπ έρνπκε ηα ι1 θαη ι2 κπνξνύκε λα ππνινγίζνπκε ηηο ηδηάδνπζεο ηηκέο ηνπ ΑΑΤ. s1  1  8 s2  2  2 Έρνληαο ηα s1 θαη s2 κπνξνύκε λα ζρεκαηίζνπκε ηνλ πίλαθα S: 13 | Σ ε λ ί δ α

Πανεπιςτήμιο Πατρών Τμήμα Ηλεκτρολόγων Μηχανικών και Τεχνολογίασ Υπολογιςτών Τομζασ Συςτημάτων Αυτομάτου Ελζγχου Εφαρμοςμζνεσ Υπολογιςτικζσ Μζθοδοι  8 S 0  0   2  Τν ηξίην βήκα (III) ηνπ αιγνξίζκνπ είλαη λα βξνύκε ηνλ πίλαθα U. Οη ζηήιεο ηνπ είλαη ηα κνλαδηαία ηδηνδηαλύζκαηα ηνπ ΑΑΤ. Δκείο ζα ρξεηαζηεί λα ιύζνπκε ηελ εμίζσζε (8) ρξεζηκνπνηώληαο ηηο ηδηνηηκέο γηα λα βξνύκε ηα δύν ηδηνδηαλύζκαηα πνπ κπνξνύκε λα ρξεζηκνπνηήζνπκε γηα ζηήιεο ηνπ U.  AA T  I  x  0 (8)  A A   I  x  0 (9) T Λύλνπκε γηα ην πξώην ηδηνδηάλπζκα ηνπ ΑΑΤ. Οη παξαθάησ πξάμεηο βνεζνύλ ζην λα βξνύκε ηελ πξώηε ζηήιε ηνπ U.  AA T  I  x  0  8 0  1 0    1      x1  0 0 1    0 2  8  1  0  0  x 0 2  1  1  0  8  8 x1  0  0 2  8   0 0  0 6  x1  0    1 x1    0 Λύλνπκε γηα ην δεύηεξν ηδηνδηάλπζκα ηνπ ΑΑΤ. Οη παξαθάησ πξάμεηο βνεζνύλ ζην λα βξνύκε ηε δεύηεξε ζηήιε ηνπ U.  AA T 14 | Σ ε λ ί δ α  I  x  0

Πανεπιςτήμιο Πατρών Τμήμα Ηλεκτρολόγων Μηχανικών και Τεχνολογίασ Υπολογιςτών Τομζασ Συςτημάτων Αυτομάτου Ελζγχου Εφαρμοςμζνεσ Υπολογιςτικζσ Μζθοδοι  8 0  1 0      2 0 1   x 2  0    0 2 8  2  0  0  x 0 2  2  2  0  8  8 x2  0  0 2  8   0 0  0 6  x 2  0   0  x2    1  Παξάγνπκε ηηο ζηήιεο ηνπ U κεηαζρεκαηίδνληαο ηα x1 θαη x2 ζε κνλαδηαία δηαλύζκαηα (νη U θαη V πξέπεη λα είλαη νξζνθαλνληθνί). u1  x1 x1  1 u1    0 u2  x2 x2 0  u2    1  Τώξα πνπ έρνπκε ηα κνλαδηαία ηδηνδηαλύκζηα u1 θαη u2 κπνξνύκε λα ζρεκαηίζνπκε ηνλ U.  1 0  U    0 1 Τν ηέηαξην βήκα απνηειεί κε παξόκνηα δηαδηθαζία κε ηελ αλσηέξσ ρξεζηκνπνηώληαο ηελ εμίζσζε (9) λα βξνύκε ηα κνλαδηαία ηδηνδηαλύζκαηα ηνπ V … 1/ 2  v1    1/ 2     1/ 2  v2     1/ 2    Τώξα πνπ έρνπκε ηα κνλαδηαία ηδηνδηαλύζκαηα v1 θαη v2 κπνξνύκε λα ζρεκαηίζνπκε ηνλ V. 15 | Σ ε λ ί δ α

Πανεπιςτήμιο Πατρών Τμήμα Ηλεκτρολόγων Μηχανικών και Τεχνολογίασ Υπολογιςτών Τομζασ Συςτημάτων Αυτομάτου Ελζγχου Εφαρμοςμζνεσ Υπολογιςτικζσ Μζθοδοι 1/ 2 V  1/ 2  1/ 2   1/ 2   Έρνληαο ηνπο U, S θαη V ε εμαγσγή ηνπ Α πξαγκαηνπνηείηαη θαη έρνπκε έηνηκν ηνλ SVD. A  USV T  2 2  1 0  8  1 1    0 1       0  0   1/ 2 1/ 2    2   1/ 2 1/ 2    3.3 Απαιηούμενη Μνήμη Η κλήκε πνπ απαηηείηαη γηα λα απνζεθεπηεί κηα αζπκπίεζε εηθόλα κεγέζνπο m x n είλαη: Im=mn Αμηδεη λα ζεκεησζεί όηη ην κέγεζνο ηεο κλήκεο πνπ απαηηείηαη απμάλεη εθζεηηθά θαζώο νη δηαζηάζεηο απμάλνπλ. Η κλήκε πνπ απαηηείηαη από κηα πξνζέγγηζε κε ρξήζε ηνπ SVD ηάμεο k είλαη: AM  k (m  n  1) Τν κέγεζνο ηεο κλήκεο πνπ απαηηείηαη απμάλεη γρακκηθά θαζώο νη δηαζηάζεηο κεγάισλνπλ εθζεηηθά. Έηζη θαζώο ε εηθόλα κεγαιώλεη, πεξηζζόηεξε κλήκε απνζεθεύεηαη ρξεζηκνπνηώληαο ην SVD. Έλα πξόβιεκα πνπ πξνθύπηεη είλαη όηη αλ ν SVD ρξεζηκνπνηείηαη γηα λα αλαπαξάγεη κηα εηθόλα αθρηβώς, ε ζπκπηεζκέλε εηθόλα εθιακβάλεη πεξηζζόηεξν ρώξν από ηελ αζπκπίεζηε. Απηό ζεκαίλεη όηη ππάξρνπλ ζεκαληηθά όξηα ζην k γηα ην νπνίν ΑΜ < ΙΜ : k(m  n  1)  mn k 16 | Σ ε λ ί δ α mn m  n 1

Πανεπιςτήμιο Πατρών Τμήμα Ηλεκτρολόγων Μηχανικών και Τεχνολογίασ Υπολογιςτών Τομζασ Συςτημάτων Αυτομάτου Ελζγχου Εφαρμοςμζνεσ Υπολογιςτικζσ Μζθοδοι 4 Κώδικαρ MatLab Παξαθάησ δίλεηαη ην πξόγξακκα πνπ πινπνηήζεθε ζην MatLab βαζηζκέλν ζηελ αλσηέξσ ινγηθή. clc; clear all; image = 'image2.png'; % read in the image img = imread(image); ImageOrg = im2double(img); ImageSize = size(ImageOrg); figure; subplot(1,5,1); imshow(ImageOrg); title (sprintf('Original Image: %s, Size: %i x %i', image, ImageSize(1), ImageSize(2))); k=int64((ImageSize(1)*ImageSize(2))/(ImageSize(1)+ImageSize(2)+1)-1) for j = 1:4 for i = 1:3 [U,S,V] = svd(ImageOrg(:,:,i)); NewImage(:,:,i) = U(:,1:k)*S(1:k,1:k)*V(:,1:k)'; end NewImage(NewImage>1)=1; NewImage(NewImage<0)=0; NewImageSize = size(NewImage); subplot(1,5,j+1); imshow(NewImage); Newimg = 'newimage2.jpg'; imwrite(NewImage,Newimg) title (sprintf('Compressed Image: %i', j)); k = k-195; end axis off Σηηο θάησζη εηθόλεο βιέπνπκε ηα πεηξάκαηα πνπ έγηλαλ κεηώλνληαο θάζε θνξά ηελ ηάμε ηνπ πίλαθα (k) – δειαδή αθαηξώληαο πεξηζζόηεξνπο όξνπο – έρνληαο ζαλ πξώηε εηθόλα ην πξσηόηππν. Σηελ ηειεπηαία εηθόλα θάζε πεηξάκαηνο είλαη αηζζεηή ε δηαθνξά αλάιπζεο (εηδηθά ζε απηήλ κε ην θηεξό ηνπ αεξνπιάλνπ, ην νπνίν δελ δηαθξίλεηαη). Οπόηε πξέπεη λα ζπκπεξάλνπκε όηη κεηά ην αξρηθό k (ην νπνίν είλαη ην όξην κεηά ην νπνίν ε αλάιπζε ραιάεη), πξέπεη λα είκαζηε πξνζεθηηθνί κε ηελ επηινγή ηνπ αθνύ αξρηθά δελ θαίλνληαη κεγάιεο 17 | Σ ε λ ί δ α

Πανεπιςτήμιο Πατρών Τμήμα Ηλεκτρολόγων Μηχανικών και Τεχνολογίασ Υπολογιςτών Τομζασ Συςτημάτων Αυτομάτου Ελζγχου Εφαρμοςμζνεσ Υπολογιςτικζσ Μζθοδοι δηαθνξέο ζηελ αλάιπζε ηεο εηθόλαο (νθείιεηαη θαζαξά ζηελ πξνζέγγηζε ηνπ αλζξσπίλνπ καηηνύ) αιιά ζηαδηαθά είλαη αηζζεηέο. 18 | Σ ε λ ί δ α

Add a comment

Related presentations

Presentación que realice en el Evento Nacional de Gobierno Abierto, realizado los ...

In this presentation we will describe our experience developing with a highly dyna...

Presentation to the LITA Forum 7th November 2014 Albuquerque, NM

Un recorrido por los cambios que nos generará el wearabletech en el futuro

Um paralelo entre as novidades & mercado em Wearable Computing e Tecnologias Assis...

Microsoft finally joins the smartwatch and fitness tracker game by introducing the...

Related pages

Applications of SVD: image compression

Applications of SVD: image compression. SVD > Applications > Image compression | Next. Images as matrices. ... Using the low-rank approximation via SVD ...
Read more

Image Compression with SVD - Harvey Mudd College

Image Compression with SVD James Chen ... An major drawback of using SVD for image compression is that fact that the U and V will have to stored together ...
Read more

Image Compression with the SVD in R - John Myles White

... Home / 2009 / December / 17 / Image Compression with the SVD ... is a 212 by 201 image. Using the SVD, ... hack for image compression struck me as ...
Read more

Image Compression using SVD and DCT - University of Utah

Image Compression using SVD and DCT Math 2270-003 Spring 2012 Yizhou Ye
Read more

Using SVD to compress an image in MATLAB - Stack Overflow

I am brand new to MATLAB but am trying to do some image compression code for grayscale images. Questions How can I use SVD to trim off low-valued ...
Read more

Image compression using singular value decomposition ...

Welcome back! Last time we have introduced the SVD-decomposition and discussed the rank-(k) approximation of a matrix (A). We have also seen a small ...
Read more

Image Compression using Singular Value Decomposition

Image Compression using Singular Value Decomposition Miss Samruddhi Kahu ... presents one such image compression technique called as SVD.
Read more

A Variation on SVD Based Image Compression

A Variation on SVD Based Image Compression ... decomposed using SVD. Suppose X r= U0 0 V0T denotes the approximation obtained for X. We experimentally find
Read more

SVD Compression - www.math.uci.edu

SVD Compression Let f be a given image represented as a m r by m c matrix. By applying the singular value decomposition (SVD) to f, we can write f = UΣVT ...
Read more

Image Compression - Wolfram Demonstrations Project

Explore thousands of free applications across science, mathematics, engineering, technology, business, art, finance, social sciences, and more.
Read more