5.26. מציאת קווים וקטעים

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

הגלאי הנכון לקצוות בעלי כיוון הוא התמרת הקווים של Hough. מודול image חושף אותה בשני סוגים: find_lines() מחזירה קווים אינסופיים (כל קו משתרע על פני התמונה כולה); find_line_segments() מחזירה קטעים סופיים (לכל קו נקודות קצה בתוך הפריים). באיזה מהם היישום צריך תלוי בשאלה האם הקצוות המעניינים רציפים על פני כל הפריים או משתרעים רק על חלק ממנו.

5.26.1. כיצד התמרת Hough עובדת

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

קו מתואר במרחב Hough על ידי שני מספרים: theta, זווית הקו (0 – 179 מעלות), ו-rho, המרחק הניצב מראשית התמונה אל הקו (בעל סימן, בפיקסלים). כל קו שהתמונה מכילה הוא נקודה אחת במרחב (theta, rho). כל פיקסל קצה בקלט תורם קול אחד לכל צירוף (theta, rho) העקבי עם מיקומו – מבחינה רעיונית, עקומה דרך מרחב Hough. היכן שעקומות רבות כאלה מצטלבות, פיקסלי קצה רבים מסכימים על אותו קו, והצטלבות זו היא זיהוי.

הגלאי מחזיר את המקסימות המקומיות במרחב Hough שסך הקולות שלהן עולה על סף. כל Line מוחזר נושא את שני הייצוגים: x1, y1, x2, y2 עבור צורת נקודות הקצה (חתוכה לגבולות התמונה במקרה האינסופי), theta, rho עבור צורת Hough, ו-length ו-magnitude עבור גודל וספירת קולות בהתאמה.

5.26.2. קווים אינסופיים

find_lines() מריצה את התמרת Hough ומחזירה את הקווים החזקים ביותר, כשכל אחד מהם משתרע על פני התמונה כולה:

lines = img.find_lines(threshold=1500, theta_margin=25, rho_margin=25)

for l in lines:
    img.draw_line(l, color=(255, 0, 0))

ה-threshold הוא סך הקולות המינימלי כדי שקו יתקבל. סך הקולות מסכם את עוצמות קצה ה-Sobel של כל פיקסל תורם, כך שערכי threshold גדולים יותר דורשים קצוות ארוכים או חזקים יותר כדי לעבור – מה שגורם לערך הנכון להיות תלוי ברזולוציית התמונה (קו ארוך יותר ברזולוציה גבוהה יותר צובר יותר קולות) וגם בסצנה, ולכן יש לכוונן אותו עבור היישום המסוים. כנקודות התחלה גסות לכיוונון: 1000 עבור קו צנוע בתמונה ברורה, 500 או פחות עבור ניגודיות חלשה או קווים קצרים, 2000 או יותר עבור סצנות עמוסות שבהן קווים שגויים נוצרים מאשכולות של רעש קצה.

theta_margin ו-rho_margin שולטים במיזוג של מקסימות סמוכות. קצה פיזי יחיד מייצר אשכול קטן של תאים בעלי קולות גבוהים סביב ה-(theta, rho) האמיתי שלו, והגלאי מכווץ כל אשכול לשיא שלו לפני ההחזרה. theta_margin=25 (מעלות) ממזג כל שיא בטווח של 25 מעלות של כיוון; rho_margin=25 (פיקסלים) ממזג שיאים בטווח של 25 פיקסלים של מרחק. ברירות המחדל סבירות; העלאתן מחזירה פחות קווים, מובחנים יותר, והורדתן מחזירה יותר קווים, לעיתים כפולים.

x_stride ו-y_stride מתקדמים דרך פיקסלי הקצה במהלך ההצבעה, באותה דרך שהם מתקדמים דרך פיקסלים ב-find_blobs(). ברירות המחדל של 2 ו-1 עובדות עבור המקרה הנפוץ; העלאתן מאיצה את החיפוש במחיר הרזולוציה. roi מגביל את החיפוש לאזור בפריים, מה שגם מצמצם את הקווים המוחזרים וגם מפחית עבודה.

כל קו מוחזר ניתן לציור ישירות: אובייקט ה-Line עובר ישר אל draw_line(), שקוראת את שדות נקודות הקצה (x1, y1, x2, y2) מחזיתו. l.theta היא הזווית במעלות, המסווגת את הקו כאופקי, אנכי או אלכסוני בהשוואה אחת. l.magnitude הוא סך הקולות, הממיין את הקווים המוחזרים מהחזק ביותר לחלש ביותר.

5.26.3. קטעי קו

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

segments = img.find_line_segments(merge_distance=5, max_theta_difference=10)

for s in segments:
    img.draw_line(s, color=(0, 255, 0))

גלאי הקטעים עוקב לאורך פיקסלי קצה בעלי כיוון ישירות, במקום להצביע במרחב Hough, והתוצאה היא אוסף של ריצות ישרות קצרות. merge_distance מגדיר את מרווח הפיקסלים המרבי ששתי ריצות קצרות קולינאריות יכולות לפרוש ועדיין להתמזג לקטע מוחזר אחד; max_theta_difference מגדיר כמה מעלות של כיוון הממזג סובל בין ריצות סמוכות. מיזוג נדיב (merge_distance=10, max_theta_difference=15) מחזיר מספר קטן של קטעים ארוכים במחיר של גישור מדי פעם בין קצוות נפרדים באמת; מיזוג מחמיר (merge_distance=0, max_theta_difference=5) מחזיר קטעים קצרים רבים ומשאיר ליישום למיין אותם ב-Python.

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

5.26.4. מתי להשתמש בכל אחד

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

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

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

שני הגלאים חולקים מגבלה משותפת: הם זקוקים לניגודיות. מסנן קצה ה-Sobel שהם בנויים עליו מגיב למפלי בהירות; קצה צבעוני על רקע באותה בהירות בדיוק (קו אדום על קיר ירוק באותה לומיננסיות) אינו מייצר מפל ואינו מייצר זיהוי. כאשר מקרה זה צץ בפועל, התיקון הוא לחלץ ערוץ LAB יחיד כתמונת גווני אפור עם הניגודיות הנכונה לפני החיפוש – to_grayscale() כשערוץ b נבחר מבודד אדום מול ירוק היכן שערוץ הלומיננסיות לבדו שטוח – ולמסור תמונת ערוץ זו לגלאי הקווים.