עמוד הבית -> דחיסת תמונה - תקן לתמונה בודדת - JPEG

התקן המשמש כיום לדחיסת תמונות וידאו בודדות הוא JPEG - על שם ראשי התיבות של שם הקבוצה שיצרה את התקן (Joint Photographic Expert Group). תקן זה הוא למעשה קובץ של כמה אלגוריתמים מוסכמים למטרות שונות של דחיסה. בתקן מוגדרים ארבעה סוגי קידוד אפשריים. השוני ביניהם נוגע גם בצורת הדחיסה עצמה, וגם בצורת האחסון וההעברה של המידע הדחוס. ארבעת הסוגים לקידוד הם:

• קידוד סדרתי - זהו הקידוד הרגיל והשימושי ביותר, המהווה את החלק העיקרי של התקן. בקידוד זה התמונה נדחסת ונפרסת פיקסל אחר פיקסל, שורה אחר שורה, כלומר לפי סדר תירה מקובל. קידוד זה מתבסס מאד על דחיסת התמרה, והוא מיועד בעיקר לתמונות "רגילות". בקידוד זה מדובר בדחיסה עם הפסדים, ולכן ניתן לדחוס תמונה צבעונית ביחסי דחיסה בין 7:1 ל-30:1, תוך קבלת איכות סבירה. ניתן גם להגיע ליחס דחיסה של 100:1, אך כפי שכבר צוין, ביחס דחיסה כזה התמונה המתקבלת לאחר הפריסה הנה באיכות ירודה למדי. הקידוד הסדרתי כולל שני אלגוריתמים עיקריים: אלגוריתם הבסיס - המשמש לתמונות רמות אפור, ואלגוריתם מרובה הרכיבים - המשמש לתמונות צבע ומהווה הרחבה לאלגוריתם הבסיס.
• קידוד חסר הפסדים - ישנם שימושים, כמו למשל שימושים רפואיים, שבהם הדחיסה חייבת להיות חסרת הפסדים. למטרה זו קיים ב-JPEG אלגוריתם נוסף. יחס הדחיסה המתקבל באמצעותו הוא אמנם נמוך יחסית (עד 2:1 בד"כ), אך מובטח שהדחיסה הנה חסרת הפסדים, כלומר ניתן שלחזר את התמונה המקורית במלואה. הדחיסה כאן אינה מבוססת על התמרה, אלא על שיערוך מדויק של כל פיקסל מערכי שכניו.
• קידוד מתחדד - במקרים בהם קצב השידור והפריסה של התמונה הדחוסה הוא איטי (ביחס לגודלה של התמונה), שימוש בקידוד הסדרתי הרגיל יעכב מאד את הצופה בניסיונו להבין את תכולת התמונה. במקרים כאלו יש עניין לאפשר לצופה לקבל תמונה כללית גסה, אשר הולכת ומתחדדת. ניתן לבצע זאת ע"י סידור המידע הדחוס בכמה תמונות אחת על גבי השניה, וכך לבנות את תמונה כולה. בדרך זו ניתן לקבל במהירות יחסית תמונה גסה, שהולכת ומתחדדת במהלך בנייתה. שימוש בשיטה זו נעשה, לדוגמה, ברשתות מחשבים (למשל ברשת האינטרנט).
• קידוד מדרגי - לעיתים קרובות, לפני פתיחת קובץ תמונה במחשב, תהליך העלול להמשך כמה עשרות שניות, מעונינים להתבונן בתמונה במבט כללי מהיר. לשם כך דרושה גישה מהירה לגרסה גסה של התמונה, שכמובן כוללת כמות מועטה יחסית של מידע. כדי לבצע זאת, התמונה מאורגנת במדרג תמונות ברמות שונות של הפרדה, שכל אחת מהן נגישה בעת הפריסה. מהירות הגישה לכל תמונה מאלה נקבעת ע"י ההפרדה שלה. בשיטה זו משתמשים בעיקר ברשתות מחשבים ובתוכנות עיבוד תמונה שונות.

אלגוריתם הבסיס של JPEG

התמרה

אלגוריתם הבסיס של JPEG מבוסס על דחיסת ההתמרה DCT. התמונה מחולקת לתת תמונות של 8 * 8 נקודות. לאחר מכן מבוצעת הזזת רמות ע"י חיסור של 128 מכל נקודה, ותחום הערכים משתנה מ-[0,255] ל-[128,-127]. התמרת הקוסינוס הדו ממדית מבוצעת על תת התמונה כדי שיתקבל מערך מקדמי ההתמרה (F(u,v, שגם הוא בגודל של 8 * 8. על מערך המקדמים מתבצע הכימוי.

כימוי

הכימוי בתקן JPEG (מסומל באיור ע"י Q) הוא כימוי סף, אלא שבמקרה זה לא משתמשים בסף אחיד לכל איברי מערך המקדמים. במקומו, משתמשים במערך כימוי (Q(u,v בגודל של 8 * 8. כל איבר במערך הכימוי מציין את גודלו של צעד הכימוי עבור המקדם המתאים לו במערך מקדמי ההתמרה (F(u,v. מקדם ההתמרה (F(u,v עובר כימוי לערך שלם k, אם:

הערך k עצמו מתקבל אם כן מתוך:
כלומר, מקדם ההתמרה מחולק בערך שמתאים לו ממערך הכימוי, והערך השלם (round) הקרוב ביותר לתוצאה, הוא מקדם ההתמרה שלאחר הכימוי. לכן, אם

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

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


מערך כימוי אופייני (Q(u,v לתקן JPEG

קידוד

אחרי הכימוי עוברים מקדמי ההתמרה קידוד. מקדם ה-DC (המקדם הראשון בשורה הראשונה) עובר קידוד בנפרד מן המקדמים האחרים, n^2 -1 מקדמי ה-AC. מקדם ה-DC יחסי לממוצע n^2 הערכים בתת תמונה בגודל n*n. מאחר שקיים מתאם גבוה בין ערכי ה-DC של תת תמונות סמוכות, עובר מקדם ה-DC קידוד הפרש ביחס למקדם ה-DC של תת התמונה הקודמת העובר קידוד. כדאי לטפל במיוחד במקדם ה-DC, וזאת מפני שלעיתים קרובות מקדם זה מכיל חלק ניכר מהאנרגיה הכוללת של התמונה.
שאר מקדמי ה-AC מסודרים בסדרה עוקבת בצורת זיג זג. כידוע, אחרי איבר ה-DC מופיעים בסדרה המקדם השני בשורה הראשונה, המקדם השני בעמודה הראשונה, המקדם השלישי בעמודה הראשונה וכך הלאה, עד למקום השמיני בשורה השמינית. סידור זה עוזר בקידוד, מפני שמקדמי התדר המרחבי הנמוך (שסביר יותר שיהיו בעלי ערך משמעותי) מוצבים לפני מקדמי התדר המרחבי הגבוה, שחלקם הגדול עובר כימוי לאפס. כפי שיוסבר, המקדמים שערכם אפס אינם עוברים קידוד נפרד, אלא משפיעים על קידוד המקדם המשמעותי הראשון שאחריהם.
מקדמי ההתמרה שלאחר כימוי וסידור עוברים קידוד הופמן. תקן JPEG אינו מחייב קוד הופמן מסוים, אך הוא מציע טבלאות קידוד אפשריות הן לערכי ה-DC העוברים קידוד הפרש בנפרד, והן למקדמי ה-AC. טבלאות אלו נבנו על סמך בדיקה סטטיסטית של תכולת מספר גדול מאד של תמונות אופייניות. המטרה היא להפיק קידוד יעיל ככל האפשר ע"י הקצאת מילות הקוד הקצרות לערכים השכיחים ביותר של המקדמים המקודדים.

נתבונן בטבלה שלהלן, המתארת את קידוד (הפרש) מקדמי ה-DC.

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


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

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

פריסת תמונה

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