Pavia Center

Report
‫פרוייקט בתמונות‬
‫היפרספקטרליות‬
‫מגישים‪ :‬עוז גבריאלוב‬
‫טלאור אברמוביץ‬
‫מנחה‪ :‬אמיר אדלר‬
‫סמסטר אביב ‪2014‬‬
‫רקע‬
‫• תמונה היפרספקטרלית‬
‫– מורכבת מתחום רחב של תדרים‪ ,‬החל מאור נראה ועד‬
‫תת אדום‬
‫• מולטיספקטרלי מול היפרספקטרלי‬
‫– מספר בדיד של תחום צרים מול תחום אחד רחב‬
‫• שימושים‬
‫– ריגול‪ ,‬חקלאות‪ ,‬גיאולוגיה ועוד‬
‫• יתרונות וחסרונות‬
‫– מידע רב בתמונה המאפשר להבחין בין עצמים שונים‬
‫– סיבוכיות גבוהה יותר ועלות‬
‫הגדרת הבעייה‬
‫• אוסף הדגימות – חלוקה לאימון ובדיקה‬
‫– חלוקה סטטית של הדגימות לשתי קבוצות‪ :‬אימון ובדיקה‬
‫– חלוקה דינמית באמצעות אלגוריתם ‪K-Fold Cross Validation‬‬
‫• סוגי המחלקות‬
‫– מחלקות (‪ )classes‬לדוגמא‪ :‬מים‪ ,‬אספלט וצמחייה‬
‫• סיווג וקטור בדיקה למחלקה המתאימה‬
‫– שימוש בוקטורי האימון ע"י אחד מהאלגוריתמים הבאים לשם‬
‫קביעת סוג המחלקה של וקטור חדש‪ ,‬מקבוצת הבדיקה‬
‫הצגת‬
‫האלגוריתמים‬
‫אלגוריתמי סיווג‬
‫• מרחב מדגם ‬
‫– במקרה שלנו ‪ , ⊂ ℝ‬כאשר  הוא מספר הקווים‬
‫הספקטרליים בתמונה‬
‫• קבוצת תיוגים ‬
‫– במקרה שלנו‪ ,‬קבוצת התיוגים הכילה בין ‪ 9‬ל‪16-‬‬
‫מחלקות שונות‬
‫• קבוצת אימון של מספר סופי של דוגמאות‬
‫מתויגות‬
‫– } ∈  ‪ = { 1 ,1 , … ,  , ∶  ∈ ,‬‬
‫תהליך הלמידה‬
‫אימון על קבוצה סופית‪ ,S ,‬של‬
‫דוגמאות מסווגות‬
‫קבלת מסווג‪/‬כלל סיווג‬
‫סיווג של דוגמאות חדשות מתוך‬
‫המרחב באמצעות המסווג‬
K Nearest Neighbors (kNN)
‫• האלגוריתם מתבסס על הקרבה בין‬
‫וקטור שאותו יש לסווג  ∈  לבין‬
‫הוקטורים שבקבוצת האימון‬
‫– מדד הקרבה שבו השתמשנו הוא‬
L2 ‫נורמת‬
K Nearest Neighbors
Input: a training sample  = { 1 , 1 , … ,  ,  :  ∈ ,  ∈ }
Parameter: k – number of neighbors
Train: Memorize 
Classify: for every vector  ∈ , return the majority label among its k closest (by
L2 norm means) neighbors in the training sample 
‫)‪Principal Components Analysis (PCA‬‬
‫• אלגוריתם הסיווג של ‪ PCA‬מתבסס על‬
‫הטרנספורמציה הלינארית המוגדרת‬
‫ע"י אלגוריתם הורדת הממד של ‪PCA‬‬
‫‪PCA demo‬‬
‫‪12‬‬
‫‪Samples on y=x with noise‬‬
‫)‪First principal component (98% of energy‬‬
‫‪y=x‬‬
‫‪10‬‬
‫– טרנספורמציה זו מתקבלת מפירוק ‪SVD‬‬
‫של המטריצה  שעמודותיה הן ‬
‫הוקטורים של קבוצת האימון‬
‫‪8‬‬
‫‪4‬‬
‫|‬
‫|‬
‫–  … ‪ = 1‬‬
‫|‬
‫|‬
‫– פירוק ‪ SVD‬של  מחזיר מטריצות ‪,,‬‬
‫כך ש‪:‬‬
‫‬
‫ = ‬
‫ הינה מטריצה אלכסונית‪ ,‬שנניח כי‬
‫אברי אלכסונה מופיעים בסדר יורד‬
‫ונסמנם ב‪ -‬‬
‫‪10‬‬
‫‪2‬‬
‫‪9‬‬
‫‪8‬‬
‫‪7‬‬
‫‪5‬‬
‫‪6‬‬
‫‪x‬‬
‫‪4‬‬
‫‪3‬‬
‫‪2‬‬
‫‪1‬‬
‫‪0‬‬
‫‪y‬‬
‫‪6‬‬
Principal Components Analysis (PCA)
PCA
Input: a training sample  = { 1 , 1 , … ,  ,  :  ∈ ,  ∈ }
Parameter: E – energy limit
Train:
• Foreach class  ∈ :
• Get the matrix   as defined.
•   , ,  = (  ).
• Define

to be the lowest  such that
•  = max  

=1 
 
≥ .
∈
• Foreach class  ∈  define   to be the matrix that contains the first 
columns of   , and save it.
Classify: for every vector  ∈ , return arg min  − 
∈





2
‫‪K-SVD‬‬
‫• ראשית נגדיר את ‪ ,‬מטריצת הוקטורים המנורמלים‬
‫–‬
‫‬
‫‪ 2‬‬
‫|‬
‫– ‬
‫|‬
‫= ‬
‫…‬
‫|‬
‫‪ = 1‬‬
‫|‬
‫• לכל מחלקה נפעיל את פונקציית ‪KSVD‬‬
‫– ] ‪  = [,1‬‬
‫–   היא המילון על פיו יתבצע הסיווג באחת משתי דרכים‪,‬‬
‫סיווג לפי שגיאה או סיווג לפי דלילות‪ ,‬ו‪ 1 -‬היא שגיאת‬
‫האימון‬
K-SVD
K-SVD
Input: a training sample  =
1 , 1 , … ,  ,  :  ∈ ,  ∈ 
Parameters:  -Learning Error, T – Max. atoms,  - Classify Error
Train:
• Get  as described
• Foreach class  ∈ :
•   = [, 1 ]
Classify:
• OMP –
• Foreach vector  ∈ :

• Foreach  ∈ :  = [  , , ]

• return arg min  −   ∗  2
∈
• OMP2 –
• Foreach vector  ∈ :

• Foreach  ∈ :  = 2   , , 2

• return arg min 
∈
0
‫‪K Fold Cross Validation‬‬
‫• אלגוריתם שנועד לבדוק את הביצועים של כל אחד מאלגוריתמי הלמידה‪,‬‬
‫ועל מנת לקבוע את הפרמטרים האופטימליים של כל אלגוריתם‬
‫‪Testing set‬‬
‫‪Testing set‬‬
‫‪Testing set‬‬
‫‪Testing set‬‬
K Fold Cross Validation
,‫• אלגוריתם שנועד לבדוק את הביצועים של כל אחד מאלגוריתמי הלמידה‬
‫ועל מנת לקבוע את הפרמטרים האופטימליים של כל אלגוריתם‬
K Fold Cross Validation
Input:
• Training set  = 1 , 1 , … ,  ,  :  ∈ ,  ∈ 
• Set of parameters values Θ
• Learning algorithm 
• Integer 
Algorithm:
• Randomly partition  into  equally disjoint sets 1 , 2 , … , 
• Foreach  ∈ Θ
• For  = 1, … , 
• ℎ, = (\ ; )
1
•  () =  =1 ,  ∈  ∶ ℎ,  ≠ 
1
•    =  =1 ,  ∈ \ ∶ ℎ,  ≠ 
• Plot  ,   as function of  (Model Selection Curve)
• Output  ∗ = arg min   
θ
‫תוצאות‬
‫כיצד ביצענו את הבדיקות?‬
‫• לכל אלגוריתם קיימים פרמטרים המשפיעים על אחוז‬
‫השגיאה המתקבל‬
‫– ‪ :kNN‬מספר השכנים – ‪1,2,3,5,10,20,30‬‬
‫– ‪ :PCA‬סף האנרגיה – ‪0.7-0.9‬‬
‫– ‪ :KSVD‬שגיאת האימון – ‪0.025-0.01‬‬
‫• סיווג לפי שגיאה‪ :‬שגיאת הסיווג ‪0.01-0.1 -‬‬
‫• סיווג לפי דלילות‪ :‬מספר האטומים המקסימלי – ‪5-13‬‬
‫• לכל תמונה מצאנו את הפרמטרים האופטימליים לכל‬
‫אחד מהאלגוריתמים‬
‫• כל אחד מ‪ 3-‬אלגוריתמי הסיווג נבדק ע"י אלגוריתם‬
‫‪ K-Fold Cross Validation‬כאשר ‪K=10‬‬
Pavia University
Pavia University - Ground Truth
Pavia University - kNN
• 610 X 340 pixels
• 103 spectral bands
• 9 classes
Pavia University - PCA
Pavia University
Pavia University - Ground Truth
• 610 X 340 pixels
• 103 spectral bands
• 9 classes
Pavia University - K-SVD (by error)
Pavia University - K-SVD (by sparcity)
• 1096 X 715 pixels
• 102 spectral bands
• 9 classes
Pavia Center
Pavia Center - Ground Truth
Pavia Center - kNN
Pavia Center - PCA
• 1096 X 715 pixels
• 102 spectral bands
• 9 classes
Pavia Center
Pavia Center - Ground Truth
Pavia Center - K-SVD (by error)
Pavia Center - K-SVD (by sparcity)
• 145 X 145 pixels
• 200 spectral bands
• 16 classes
Indian Pines
Indian Pines - Ground Truth
Indian Pines - kNN
Indian Pines - PCA
Indian Pines - K-SVD (by error)
Indian Pines - K-SVD (by sparcity)
• 512 X 217 pixels
• 204 spectral bands
• 16 classes
Salinas
Salinas - Ground Truth
Salinas - kNN
Salinas - PCA
Salinas - K-SVD (by error)
Salinas - K-SVD (by sparcity)
‫טבלה מסכמת של התוצאות‬
KNN
(num. neighbours)
PCA
(energy limit [%])
KSVD – by error
(omp2)
(test error, train error)
KSVD – by sparcity (omp)
(sparcity, train error)
Pavia University
90.988%
(5)
66.85%
(72.22)
70.54%
(0.0325, 0.025)
74.39%
(5,0.1)
Pavia Center
98.799%
(5)
92.916%
(70)
92.546%
(0.01,0.075)
94.328%
(5,0.1)
Indian Pines
77.22%
(5)
67.2%
(90)
28.76%
(0.0325,0.025)
61.01%
(11, 0.025)
Salinas
93.97%
(1)
84.48%
(87.78)
85.1%
(0.01,0.075)
88.66%
(11, 0.025)
‫סיכום ומסקנות‬
‫• תמונה גדולה יותר ‪ ‬סיווג טוב יותר‬
‫– ככל שהתמונה גדולה יותר‪ ,‬כך יש יותר מידע והסיווג מוצלח יותר‬
‫בכל האלגוריתמים‬
‫• ‪ – kNN‬האלגוריתם שנתן את תוצאות הסיווג הטובות ביותר‬
‫– כלומר‪ ,‬הוקטורים ששייכים לאותה מחלקה קרובים אחד לשני‬
‫– למרות זאת‪ kNN ,‬בעל סיבוכיות זמן ריצה וסיבוכיות מקום גבוהות‬
‫• ‪ – PCA‬סיבוכיות זמן ריצה ומקום נמוכים‪ ,‬אבל סיווג כלל אינו‬
‫מושלם‬
‫– התוצאות ש‪ PCA-‬נותן בסיווג אינן עקביות כמו ב‪kNN-‬‬
‫– השונות של שגיאת השחזור של וקטורי הבדיקה למרחב המתאים‬
‫למחלקה שלהם גבוהה‬
‫• ‪ – KSVD‬סיווג טוב יותר ועקבי יותר מ‪ PCA-‬עם אותה סיבוכיות‬
‫מקום‪ ,‬אך סיבוכיות זמן ריצה גבוהה‬
‫– סיווג לפי דלילות (‪ )omp‬נותן תוצאה טובה יותר מאשר סיווג לפי‬
‫שגיאה (‪)omp2‬‬
‫הצעות לשיפור‬
‫• שילוב של אלגוריתם להורדת ממד‪ ,‬ולאחר מכן‬
‫הפעלת ‪ kNN‬על הבעיה בממד החדש‬
‫– למשל‪ ,‬ע"י הפעלת ‪ PCA‬או ‪ KSVD‬על וקטורי האימון‬
‫– בכך נוכל לחסוך בסיבוכיות זמן ומקום של ‪kNN‬‬
‫• הרחבת קבוצת אלגוריתמי הסיווג‬
‫• עיבוד מקדים של התמונה לפני הסיווג‪ ,‬למשל‬
‫באמצעות כלים של עיבוד תמונה או כלים‬
‫מיוחדים לשימוש בתמונות היפרספקטרליות‬
‫• הרחבת מאגר התמונות לבדיקה‬
‫– יאפשר אימון על קבוצת תמונות וסיווג יתר התמונות‬
‫ביבליוגרפיה‬
• Hyperspectral Imaging. Retrieved from Wikipedia:
http://en.wikipedia.org/wiki/Hyperspectral_imaging
• Hyperspectral Remote Sensing Scenes. Retrieved from
University of the Basque Country:
http://www.ehu.es/ccwintco/index.php?title=Hyperspectr
al_Remote_Sensing_Scenes
• Rubinstein, R. Matlab Tools. Retrieved from Ron
Rubinstein's Homepage:
http://www.cs.technion.ac.il/~ronrubin/software.html
• Shalev-Shwartz, S., & Ben-David, S. Understanding
Machine Learning.
QUESTIONS?

similar documents