מלחמת המכווצים

התנצלות מסויימת: הפוסט הזה רצה להיות טכני יותר, ואז התחרט, ובאופן כללי לא ממש הצליח להיסגר על עצמו.

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

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

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

לפי הנתונים באתר של חברת hipix (שמפתחת אלגוריתם דחיסה חדש שכזה) 60% מנפח התעבורה בווב הוא תמונות. זה הרבה. הרבה מאוד. גם היום, כשמספרים לנו שהווב בגסיסה. עבור ynet, האפשרות לצמצם באופן משמעותי את נפח התמונות בלי לפגוע באיכות ההצגה שלהן היא רווח משמעותי, קיצוץ ניכר ברוחב הפס שמיתרגם מיידית לקיצוץ ניכר בהוצאות.

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

אנקדוטה קשורה למחצה:

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

“עזוב!” הפטיר אחד מהם באותו זלזול אופייני למרצים מבוגרים “זה סתם בזבוז!" מה כבר אנשים עושים עם המחשב בסוף? מקסימום קצת מעבד תמלילים, אולי איזה גליון באקסל”.

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

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

חזרה לעניין

וזה, בפועל, בדיוק מה שקורה היום.

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

paradox

בתמונה זו מסתתר פרדוקס משעשע

עוד אנקדוטה

לפני שבועות אחדים החליפו לי את הטלפון הסלולרי במקום העבודה. המכשיר החדש, חביב ככל שיהיה, לא פטר אותי מהגירוד הקל בקצות האצבעות לקנות לעצמי איזה סמארטפון ראוי, אבל לא זה העניין. איש ה-IT שטיפל בהחלפת הטלפונים הציג לי את המכשיר החדש בגאווה. “יש לו” אמר בסיפוק “אחלה מצלמה, 8 מגה-פיקסל”.

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

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

מקוריות, עצלנות, גאונות

ספק רב אם הייתי טורח לכתוב על כל זה אלמלא העובדה המפתיעה באמת בסיפור הזה. קריאה שטחית ומרפרפת של תיאור האלגוריתמים החדשים (זה הקנייני של hipix וה-WebP של גוגל שמופץ בקוד פתוח) הצליחה להדהים ואפילו לרגש אותי מעט.

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

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

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

9 תגובות ל“מלחמת המכווצים”

  1. לא מבין בדחיסה יותר מדי – אבל החלוקה למרצפות (tiling?!) נשמע לי כמו רעיון ישן גם בדחיסת תמונות. זה סוג של שרשרת מרקוב שהולכות אל כל הפיקסלים השכנים.
    דבר נוסף – זו דחיסה מקורבת (מאבדת/ lossy) וכמו בדחיסת מוזיקה ואולי בצורה קיצונית יותר – הסלולר פשוט גורם לנו להיות מאוד סבלניים לתמונות באיכות גרועה. גם כי המצלמות מעפנות (אך זמינות) וגם כי המסך קטן. קריאה מהירה בלינק לדחיסה של גוגל גם מגלה שהם מאפשרים טריי-אוף של האיכות. עם קרדיט גדול גם אני יכול לדחוס תמונה בצורה מרשימה (=כל הפקסלים שחורים).

    [להגיב לתגובה זו]

    שחר Reply:

    למיטב הבנתי, הרעיון של שימוש ב-I-frames, B-frames ו-P-frames (מונחים שהושאלו מדחיסת וידאו) עבור המרצפות האלה הוא חדש (עצם החלוקה למרצפות אכן לא נשמעת כחידוש בפני עצמו).
    נכון שבשני המקרים מדובר בדחיסה שהיא lossy, ושתיהן מוצגות כאלטרנטיבה ל-jpeg שגם היא כזו.
    בתחום של דחיסות lossless, כפי שציינתי בסוגריים, יש את הסיפור המרתק לא פחות של PNG מול GIF (שגיליתי רק תוך כדי קריאה בנושא בימים האחרונים).

    [להגיב לתגובה זו]

  2. הערה חשובה בעקבות התגובה של אורן: בהחלט יכול להיות שיצאתי אהבל גמור בהתלהבות שלי ממה שחשבתי שהוא חידוש גדול, או שלא ממש הבנתי את התיאורים הטכניים של שני האלגוריתמים נכון.
    אשמח לקבל תיקונים והערות ממי שמבין בנושא.

    [להגיב לתגובה זו]

    אורן Reply:

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

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

    [להגיב לתגובה זו]

    שחר Reply:

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

    [להגיב לתגובה זו]

  3. כמה הערות.
    קודם כל, איזה פוסט כיפי! אני תמיד מופתע שיש עוד אנשים שבכלל אכפת להם ממשהו כזה אפילו שהם לא מתעסקים בו ישירות, אז תודה. :-) אעיר כמה הערות, למרות שאני חוקר תחום שכן, ולאו דווקא דחיסת תמונות.

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

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

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

    אז זהו.
    תודה שוב,
    דניאל

    [להגיב לתגובה זו]

    שחר Reply:

    תודה רבה.
    יש לי כמה שאלות בהמשך ישיר. אנסה לנסח אותן מאוחר יותר.

    [להגיב לתגובה זו]

  4. יופי של פוסט, לא קלקלת לי אותו עם הספוילרים אתמול (אז טכנית הם לא ספוילרים?).

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

    מרצפות לא חופפות של 8×8 אותן דוחסים באופן בלתי תלוי

    כאן זה נעשה כן עם קשר בין מרצפת לשנייה.

    [להגיב לתגובה זו]

  5. המרצה צודק וטועה.

    אנשים שפונים אליי בתור "איש המחשבים" המשפחתי/שכונתי ושואלים איזה מחשב לקנות בד"כ מקבלים את השאלה: "מה את/ה הולכ/ת לעשות איתו? לגלוש , להוריד סרטים ולעבור ב-WORD? אז לקנות את המחשב כמעט-הכי זול שיש, 1000-1500 ש"ח ויספיק לך להכל".
    ואחרי זה הרצאה על כמה שהארדיסק מהיר ואמין יותר חשוב מעוד כמה מגהרצים במהירות שעון.
    מי היוצאי דופן? גיימרים, אנשים שעורכים וידאו, וגם (לקח שנלמד בדרך הקשה מזוגתי) מעצבים גרפיים וכו'. היא לא הקשיבה לי ולכן קנתה לפני 3 שנים מחשב שיותר מהיר מהמחשב שיש לי היום, ובצדק. כל הפוטושופ הזה.

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

    [להגיב לתגובה זו]

השארת תגובה

Subscribe without commenting