שאלה על אלגוריתם

[omni4]

שאלה על אלגוריתם

שאלתי כבר, אבל לא ניסחתי טוב. התמונה הנתונה הוא מטריצה כאשר הלבן מיוצג כערך "1" והשחור מיוצג כ-"0". אני רוצה לתחום כל "כתם" במלבן (לא נורא שיכנס קצת לבן מסביב לשחור בתוך המלבן), איזה דרך טובה כדאי לעשות כדי למצוא את מיקומי המלבנים? מצורפת תמונת דוגמא. תודה

 

[vinney]

הייתי מציע לך לבדוק כיוון של אלגוריתמים

לחישוב הקמור (יש בקורמן לקראת סוף הספר), ולעשות להם אופטימיזציה אם אתה רוצה מלבנים דווקא.

 

[omni4]

של האו"פ?

 

[johnny d]

לבעיה קוראים clustering

והיא בעיה קשה, NP-Hard למען הדיוק... באופן כללי לחלק מרחב (דיסקרטי או לא) לקבוצות של נקודות זה לא בדיוק בעיה פתירה בהינתן מספר פונצקיות מטרה ביחס לפרמטרים של התחומים... ברגע שיש לך קבוצות לעומת זאת למצוא מלבן זה לא בעיה . . .

 

[1ca1]

אבל עדיין יש הרבה שיטות טובות מאוד

באופן כללי הבעיה היא Image segementation שהיא שונה במקצת מclustering כללי בML אבל עדיין כנראה שקול מבחינה חישובית (פתירת image segementation אפשרית ע"י clustering, ואפשר לייצג את בעיית הקיבוץ הדו-מימדית! בעזרת תמונה כמו שהראו למעלה ולפתור עם image segementation). עוד על הנושאים כמובן יש בויקי http://en.wikipedia.org/wiki/Segmentation_%28image_processing%29 http://en.wikipedia.org/wiki/Data_clustering נראה לי הדרך הכי טובה כאן היא לבצע "גילוי שפות", ואח"כ לעשות קמור של השפות (כי בד"כ מקבלים שפות לא רציפות מרוב האלגוריתמים) ותקבל משהו סביר בזמן ריצה יחסית טוב. מצד שני אפשר גם לנקוט בגישות יותר מתחום הML, ולבצע k-means וכאלה, אבל כאן ההפרדה שנראית היא הפרדה חזקה מאוד (אולי גם אפשר לתחום "איזורים גדולים" בתמונה ע"י פרספטרונים חוזרים לכל קבוצה שרוצים לתחום בכל פעם (משהו בסגנון "corss validation"), אבל יכול להיות שזה קשה (ואפילו בלי אפשרי בלי לדעת מראש את מספר התחומים).

 

[omni4]

נתון שיש 3 אזורים.

"גילוי שפות", הכוונה למסננים?

 

[1ca1]

תלוי

אם תסתכל על זה מכיוון אחד, זה בעצם נגזרות דיסקרטיות לסוגיהן, מצד אחר, יכול להיות שאתה קורא לזה מסננים (זה קשור גם לnoise reduction וכו'), בקיצור גגל ווויק (מלשון להסתכל בויקי), http://en.wikipedia.org/wiki/Edge_detection

 

[johnny d]

אז הבעיה היא אחרת

הבעיה שאתה מתאר עכשיו היא מציאת שלושת המקבצים הרציפים הגדולים ביותר, זה לא בעיה וניתן לפתירון בזמן ליניארי. כבר ציינו מעלי את שם הבעיה אתה רק צריך לחפש את האלגוריתם רמז דק: google)

 

[omni4]

אני אנסה להבהיר את עצמי

אני לא יודע את מיקומי הכתמים, איך הכי טוב למצוא אותם?