DT-Distance Transform

[johnny maxwell]

DT-Distance Transform

שלום לאנשי הפורום. אין לי יותר מידי תקוות אבל... אני מקווה שמישהו פה יוכל לסייע לי בעניין הבא: (אני מתייחס למקרה דו-מימדי) דיסטנס טרנספורם סטנדרטי,יכול לתת מפות של מרחקים מסוגים שונים. לגבי מרחק אוקלידי, הוא יכול לתת זאת רק בקירוב. במאמר מסויים שנתקלתי בו, נטען שבעזרת VDT (vector distance transform ), ניתן לקבל מפת מרחקים אוקלידים מדוייקת המושגת על ידי propagation של וקטור ההעתקה. (וזאת בניגוד לDT שעושה עדכון אינקרמנטלי של מפת המרחקים המושג באמצעות local propagations של המרחקים) הבעייה שלי: הבנתי איך עושים DT רגיל, אבל לא הבנתי איך מיישמים פרופוגיישן של וקטור ההעתקה. המאמר אליו המאמר המקורי הפנה בעניין הזה, לא התייחס בכלל לעניין... מישהו יודע? מישהו מכיר? תודה בכל מקרה.

 

[Calius]

תמיד החזק בתקווה!

מצאתי (אני חושב) את המאמר אליו אתה מתיחס, ואם אני מבין נכון אז הענין פשוט למדי: מה הבעיה עם המפה ה- "רגילה"? שמשבצת שנמצאת במרחק 2, זו שלידה לא ממש נמצאת במרחק 3, אלא רק בערך (אלכסונים וכו'). לכן, כדי למדוד מרחק אוקלידי, יחד עם האינפורמציה על המרחק עצמו (2, 3 וכו' בדוגמאות) פשוט עושים פרופוגציה גם לקואורדינטה ממנה מודדים את המרחק, וכך מחשבים את המרחק מחדש בכל פיקסל. זה לא אלגוריתם n^2 מכיוון שניתן לעצור פרופוגציה ברגע שכל השכנים שלך כבר יש להם מרחקים קטנים יותר מהמרחק שיחושב להם מהפיקסל שלפיו המרחק שלך מחושב. (הייתי ברור?...) חוצמיזה, דע לך שאם אתה לומד מורפולוגיה חישובית אז ישנן הרחבות של העניין הזה למישור רציף (לא רק פיקסלים). אם למדת גיאומטריה חישובית אתה אולי יודע על Skeleton -- זה בעצם זה. מניין השאלה? מה התחום?

 

[johnny maxwell]

אוף!!!! כתבתי תגובה והיא נמחקה...

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

 

[Calius]

לא כ"כ מתמצא. פעם למדתי גיאומטריה

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

 

[johnny maxwell]

אני לא בטוח שהבעיה היא רק מימושית.

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

 

[Calius]

אז ככה

קראתי קצת בלינק שצירפת. לא כתבת במפורש מה אתה עושה, כך שאני לא יכול להגיד איפה (אם בכלל) יש בעיה. הבנתי שרב האלג' המדוברים (ובכללם זה שאתה מממש) עושים Raster-Scan, שזה אמנם יעיל אבל רק מקרב מרחק אוקלידי אמיתי. אם תקרא את ההודעה המקורית שלי תראה שאני הנחתי אוטומטית אלג' Breadth First -- כזה שמתפשט. הוא פחות יעיל אבל *מדויק*, וגם מאוד אינטואיטיבי. לסיכום ביניים: 1) אני חושב שאני יכול לעזור לך עם האלג' "שלי" 2) ספר מה עשית בינתיים *בדיוק* 3) אשמח לעזור גם בולידציה של מה שעשית -- אחרי שאקרא מה זה אקרא את התזה הנ"ל מחדש בחלקים הרלוונטים. פה אני סתם עוד זוג עיניים.

 

[johnny maxwell]

אני שולח לך מסר

 

[johnny maxwell]

הללוליה

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

 

[avinamal]

כן! הידד לקליוס ולפורום מתמטיקה!../images/Emo13.gif

 

[johnny maxwell]

אז ככה

הוא מציע להשתמש במסכות הבאות, כמו שמופיע בקישור: http://www.tele.ucl.ac.be/PEOPLE/OC/these/node13.html#figanielsson_s__masks (אני מתייחס לזה של ה8 ולא לזה של 4) אם יש רק פרוטוטייפ אחד אז הכל טוב, והתוכנת מטלב שכתבתי עומדת במשימה בכבוד. הבעייה היא אם יש שני פרוטוטייפים (אני חושב שבאתר שצרפתי קוראים לזה אובייקט) או יותר: למשל במטריצה כזאת: [O*,*;*,*,O] אם הבנתי נכון סדר ההרצות הוא: המסכה השמאלית העליונה על השורה העליונה משמאל לימין. המסכה הימנית העליונה על השורה העליונה מימין לשמאל. אותו דבר על שורה שנייה. ואז BACK: המסכה השמאלית התחתונה על השורה השנייה משמאל לימין. המסכה הימנית התחתונה על השורה השניה מימין לשמאל. ואז אותו דבר על השורה הראשונה. זה נכון? הבעייה שלי שברגע שהוא מוצא את הפרוטוטייפ השני במהלך החזרה של המסכה הימנית העליונה, הערך של רכיב הY (בכל השורה השנייה)יהיה כבר אפס, למרות שהייתי שמח אם הוא היה נשאר 1 לפחות עבור האיבר הכי שמאלי בשורה השנייה...

 

[avinamal]

רוצים עוד פירוט!!

אם זה קצת חורג מגבולות הפורום... איזה תמונות אתה מעבד? מדוע להשתמש ב DT? מדוע שלא תשלח לי את הקוד שכתבת?

 

[johnny maxwell]

בשמחה...

אם זה חורג מגבולות הפורום אני מתנצל ואעבור למסרים. בנתיים אני נשאר... התמונות: MRI של מוח. למה? זה בתגובה השנייה. את הקוד אשלח לך במסר. ואל נא באפך במה שקשור ליעילות של הקוד- זה נכתב מהר רק כדי לראות שזה עובד. תודה רבה!

 

[avinamal]

מצטרף לשתי שאלות הסיכום ../images/Emo110.gif

איך הגעת למצב שאתה משתמש בהתמרה הזו?

 

[johnny maxwell]

כאמור:

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