פורסם ב מאת עמרי

חלון מהיר

לפני כמה פוסטים שאלתי את השאלה הבאה:

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

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

אז הנה הפתרון שלי:
נחלק את התמונה למשבצות בגודל KxK, ונשמור רשימה של כל הנקודות בכל משבצת.
כאשר מבקשים מאיתנו לתת את רשימת הנקודות בחלון מסויים, נסתכל בארבעת החלונות שהחלון הזה חותך ונסנן את כל הנקודות בארבעת החלונות שלא נמצאות בתוך החלון המבוקש.
זה הכל בעצם.
הביצועים של הפתרון הזה מעולים, כדי להכין את הגריד (Grid) נעבור על כל הפיקסלים בתמונה, ולכל נקודה נמצא בזמן קבוע את המשבצת שאליה היא שייכת.
כשממש מחפשים את הנקודות בחלון מסויים, נבדוק במקרה הגרוע 2K*2K פיקסלים (אם כל הנקודות לבנות) אבל במקרה הרגיל נבדוק הרבה פחות (ואם החלון לא מכיל נקודות כלל נדע את זה מהר מאוד).
זה הקוד של העיבוד המקדים:
[code lang="java"]
private static int [][][] buildgrid(byte[][] image, int width, int height, int gridSize)
{
int grid[][][] = new int[width / gridSize][height / gridSize][];
// count the number of points in each grid cell
int numpoints[][] = new int[width / gridSize][height / gridSize];
for(int x=0;x Byte.MIN_VALUE)
{
numpoints[x/gridSize][y/gridSize]++;
}
}
}

for(int x=0;x Byte.MIN_VALUE)
{
int gy = y/gridSize;
int gx = x/gridSize;
int list[] = grid[gx][gy];
if (list == null)
{
int np = numpoints[gx][gy];
list = new int[np * 2];
grid[gx][gy] = list;
numpoints[gx][gy] = 0;
}

list[numpoints[gx][gy]++] = x;
list[numpoints[gx][gy]++] = y;
}
}
}
return grid;
}
[/code]

הקוד הבא סופר את המספר הנקודות בתוך החלון שמרכזו (x,y)' שימו לב שהלולאות עוברות על ארבעה ריבועים בגריד בלבד:
[code lang="java"]
// window boundaries:
int rx1 = x – grid_size/2;
int ry1 = y – grid_size/2;
int rx2 = rx1 + grid_size;
int ry2 = ry1 + grid_size;

// top left grid cell (out of 2×2 group to be checked)
int gx = rx1 / grid_size;
int gy = ry1 / grid_size;

for(int grid_x=gx;grid_x= 0 && grid_x < gwidth;grid_x++) { for(int grid_y=gy;grid_y= 0 && grid_y < gheight;grid_y++) { int list[] = grid[grid_x][grid_y]; if (list == null) continue; for(int i=0;i= rx1 && dx < rx2 && dy >= ry1 && dy < ry2) { c++; } } } } [/code] יתכן שאפשר לשפר את הביצועים אם נחלק את הגריד לריבועים יותר קטנים ונכלול ריבועים שלמים שנופלים בתוך החלון בלי לבדוק כל נקודה באופן פרטני, אבל לא ניסיתי. הביצועים של הפתרון הזה די מטורפים. על Q6600 במהירות 2.4GHZ, עם תמונה בגודל 500X500 פיקסלים וחלון של 20X20, בדיקה של כמה זמן לוקח לספור את הפיקסלים בכל 250,000 החלונות האפשריים לקחה כ160 מילישניות, מה שנותן מהירות בדיקה של מעל 1500 חלונות במילישניה (או יותר ממליון וחצי חלונות בשניה), בלי תלות בגודל התמונה שנבדקת (על תמונה של 1000X1000 המהירות היתה דומה). האפלט הבאה מדגימה את האלגוריתם. אפשר להוריד אותה מפה. הקוד כלול בתוך הJAR (אפשר לפתוח את הJAR עם תוכנה לפתיחת קבצי ZIP).
בנוסף, האפלט יכולה לרוץ כתוכנית רגילה : java -jar fast_window.jar
אפשר ללחוץ בתוך האפלט כדי לסמן את הנקודות בחלון.


הדפדפן שלך לא תומך בג'אווה, ככה האפלט ניראית (רק שהיא אינטראקטיבית) :


Facebook Comments

20 תגובות בנושא “חלון מהיר”

  1. למה לעשות ככה:

    נתונה לך נקודה x,y שהיא מרכז המשבצת
    k גודל המשבצת

    לרוץ מ(x-k/2) עד (x+k/2) ואותו דבר על הy
    ולבדוק עבור כל נקודה אם היא לבנה

  2. אתה מוזמן לשנות את הקוד באפלט ולבדוק מה הביצועים שזה נותן.
    להערכתי פי 10 יותר לאט.

  3. הפיתרון שאנון הציע הוא הפתרון המובן מאליו, שזמן הריצה שלו הוא או של N (תקן אותי אם אני טועה).

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

    אבל אולי כדאי לך לרשום מהו זמן הריצה של הפיתרון שלך *ללא* הסריקה הראשונית (שינתנת "חינם")?

    שים לב, אני מציע את זה בלי שקראתי את הפתרון אז אם זה מסובך לחשב אז אין צורך.

  4. תיקון: ואני מעדיף לא לקרוא –> ואני מעדיף לא לקרוא עכשיו.

  5. זמן הריצה של הפתרון של אנין הוא ריבוע גודל החלון (K^2).
    זמן הריצה של הפתרון שלי הוא לינארי למספר הנקודות בארבע חלונות. אם נסתכל על זמני ריצה, הפתרונות דומים (ארבע זה קבוע, ובבעיה יש כעשרה אחוז של נקודות, שזה עוד קבוע).
    אבל בפועל אנון עובר תמיד על K^2 פיקסלים, ואני עובר בממוצע על
    2k*2k*0.1=4k^2*0.1 = 0.4k^2

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

    עוד נקודה חשובה:
    הגדרתי את השאלה כך שיש 10% נקודות שמפוזרות באופן אקראי. זה לא מדוייק ובבעיות "אמיתיות" הפיזור הוא לא אקראי. במקרה כזה יש יתרון משמעותי לפתרון שלי כי הוא מסוגל לומר כמעט מיד שאין שום נקודות בחלון מסויים (בלי לעבור על K^2 פיקסלים).

  6. רק עכשיו קראתי והפנמתי את הפתרון שלך, נראה מעניין מאוד.

    יש לי מחשבה. לא חשבתי על זה עד הסוף אז רק אזרוק את זה:

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

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

    שוב, רק מחשבה.

  7. תיקון: אני חושב שזה N^2 פעולות –> אני חושב שזה N^4 פעולות

  8. יונתן,
    למרבה הצער לא ניתן ליצור רשימה חד מימדית ממוינת בגודל N^2 איברים כך שהיא תכיל רצפים שמכילים ריבועים שלמים.
    תנסה לחשוב על זה עד הסוף ותווכח בעצמך.

  9. צודק לחלוטין, אני מבין למה.

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

  11. אווףף שכחתי לגמרי מזה.,

    עמרי אני כבר לא זוכר במדויק מה היה הפיתרון שלי אבל אני זוכר שהוא היה פחות יעיל משלך (כאשר חשבתי עליו שוב).

    בקיצור עבודה יפה 🙂

  12. סליחה שאני מצטרף לחגיגה באיחור, רק עכשיו גיליתי את החידה הזו!

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

    1. אני יוצר Y רשימות מקושרות (דו-כיווניות) של ערכי X של הפיקסלים הלבנים (כל שורה בנפרד).
    2. כשאני מקבל X ו-Y עבור הריבוע, אני מחשב את ה-Y ההתחלתי והסופי לבדיקה ע"י Y +/- חצי K ועובר רק על הרשימות הרלוונטיות:
    2.1. בכל רשימה, מבצע חיפוש בינארי כדי לאתר פיקסל שנמצא בטווחי X של הריבוע.
    2.1.1 אם יש כזה, הולך קדימה ואחורה ברשימה ומסמן את הפיקסלים עד שאני יוצא מגבולות X של הריבוע או מגיע לקצה הרשימה.

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

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

  14. אכן מערכים ולא רשימות, ואני מאשים בזה את השעה בה כתבתי 🙂
    אני אכתוב משהו ואראה מה יוצא. אם זה יהיה פייט מעניין, יש לך התנגדות שאכתוב על כך בטור שלי בנענע10 תוך אזכור הפוסט שלך?

  15. הנה רעיון חדש בלי בעיית הביצועים של החיפוש הבינארי.

    שוב, ניצור מערך (A) של מיקומי הפיקסלים הלבנים עבור כל שורה.

    כעת, ניצור מערך נוסף (B) של "קווים אנכיים" במרווחים של K פיקסלים, שכל אחד מהם בעצמו הוא מערך של מיקומי Y, שכל אחד מהם מכיל הפניה לפיקסל הלבן הקרוב ביותר מימין ומשמאל ב-(A) עבור אותו Y. זה דורש יותר זמן וחישובים בעיבוד הראשוני, אבל להערכתי לא משהו מוגזם.

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

    לא נשמע ממש ברור, אני יודע, מצד שני זה נראה מאד מבטיח. אנסה לתכנת את זה בקרוב ולהביא תוצאות.

  16. רעיון מעניין עם ביצועים דומים אינטואיטיבית לפתרון שלי.
    תממש ונראה מה עדיף :).

    וכמובן שאין לי שום התנגדות שתכתוב על זה בטור שלך, אני אשמח.

  17. אם כבר, אז יש פתרון עם זמן ריצה קבוע אבל עם מעבר ראשוני יותר ארוך.
    מה שאתה עושה זה עבור כל פיקסל בתמונה אתה מחשב מראש את כמות הפיקסלים הלבנים במלבן שבין הפיקסל ל 0,0
    כלומר אתה מקבל עבור כל פיקסל את כמות הפיקסלים הלבנים שנמצאים משמאלו ומעליו.

    אחר כך, בזמן ריצת התוכנית מה שאתה מחפש זה פשוט את הערך של הפינה הימנית התחתונה פחות הפינה הימנית העליונה פחות הפינה השמאלית התחתונה ועוד הפינה השמאלית העליונה
    כלומר זמן ריצה קבוע.

    מבחינת זמן ריצה של ההכנה: כמו בתכנות דינאמי אפשר לרוץ בזמן ריבוע ברקורסיה. על כך שאתה מבצע חישוב של התא 0,0 ואז כל תא משמאלו ומתחתיו אם הוא לבן אתה מוסיף 1.

  18. אה, כן. נראה לי אפילו שהמעבר הראשוני שלי מהיר יותר משלך… כי אני מקבל זמן ריבועי על ידי ריצה רקורסיבית פעם אחת על המערך.
    והפתרון בזמן אמת הוא
    O(1)

  19. הכוונה שלי היא לספור את כמות הפיקסלים הלבנים. או שהכוונה היא למצוא את כל המיקומים שלהם?

  20. הפתרון שהצעת ידוע בשם Integral image, והוא אכן מאפשר לסכום שטחים בקלות.
    http://en.wikipedia.org/wiki/Summed_Area_Table
    הוא מאוד שימושי, ומשתמשים בו גם באלגוריתם למציאת פנים Viola jones.

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

סגור לתגובות.