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

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

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

איור 1	איור 2
איור 3	איור 4

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

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

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

מקור

רעש 0.2

רעש 0.3

רעש 0.4

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

ישנן שיטות מתוחכמות יותר להרעדה, המביאות את השגיאה קרוב ל-0, למשל אלגוריתם פלויד-שטיינברג [3,4] (ראו איור 4), וכן אלגוריתמים המכינים מראש "תבניות של רעש" הידועות כמוצלחות, במקום להגריל רעש אקראי [2]. כמו כן, ניתן כמובן גם להרעיד תמונות צבעוניות.

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

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

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

הערות והרחבות:

[1] Ken C. Pohlmann (2005). Principles of Digital Audio. McGraw-Hill Professional. ISBN 978-0-07-144156-8.

[2] הרעדה (ויקי באנגלית)

[3] R.W. Floyd, L. Steinberg, An adaptive algorithm for spatial grey scale. Proceedings of the Society of Information Display 17, 75–77 (1976)

[4] Floyd–Steinberg dithering

[5] R. M. Gray and T. G. Stockham, "Dithered quantizers," in IEEE Transactions on Information Theory, vol. 39, no. 3, pp. 805-812, May 1993, doi: 10.1109/18.256489.