السَّمْت

الرؤية الحاسوبية2001مبتدئ9 دقيقة قراءة

كشف الأجسام السريع باستخدام سلسلة مُعزَّزة من السمات البسيطة

Rapid Object Detection Using a Boosted Cascade of Simple Features

Viola, P. · Jones, M. — CVPR

المشكلة

قبل عام 2001 كان محصوراً بين خيارين: إما دقة عالية مع بطء شديد (شبكات عصبية تمسح كل نافذة في الصورة)، أو سرعة مقبولة مع هشاشة واضحة (قواعد يدوية مضبوطة بالتجريب). صورة بأبعاد 384×288 فيها أكثر من 100,000 موقع محتمل لوجه بأحجام مختلفة، وتقييم مصنِّف معقد في كل موقع يستغرق دقائق لا أجزاء من الثانية. أما الفيديو اللحظي (15 إطاراً في الثانية) فيفرض معالجة الإطار كاملاً في أقل من 67 ميلّيثانية — وهو هدف لم يبلغه أيّ كاشف آنذاك.

الإسهام

ثلاث أفكار متكاملة تحقّق معاً كشف الوجوه في الزمن الحقيقي: (1) — بنية بيانات تحسب مجموع أي مستطيل بأربع عمليات قراءة فقط مهما كان حجمه، فتجعل حساب سمات هار سريعاً عند أي مقياس؛ (2) انتقاء السمات AdaBoost التي تختار أقوى السمات تمييزاً من بين أكثر من 160,000 سمة وتجمعها في مصنِّف قوي واحد؛ (3) سلسلة مصنِّفات متدرّجة من الأبسط إلى الأعقد، كل مرحلة تستبعد النوافذ التي لا تشبه الوجوه بسرعة، فلا يصل إلى المراحل المُكلفة إلا المرشّحون الجادّون.

الأثر

أول كاشف وجوه يعمل في الزمن الحقيقي على عتاد تجاري عادي. دُمج في الكاميرات الرقمية وكاميرات الويب، وظلّ الركيزة الأساسية لكشف الوجوه في مكتبة OpenCV لأكثر من عقد. فكرة الاستبعاد المتدرّج — ارفض مبكراً وبأقل تكلفة — تحوّلت إلى نمط تصميم سائد في كلها، وأثّرت في كل كاشف جاء بعدها من HOG إلى R-CNN.

تخيّل أنك تعمل في أمن المطار وعليك فحص آلاف الحقائب كل ساعة. لن تضع كل حقيبة في جهاز الأشعة خمس دقائق — الطوابير ستتوقف تماماً. الحل: نقاط تفتيش متدرّجة. الموظف الأول ينظر إلى بطاقة الوزن (ثانية واحدة) — خفيفة جداً؟ مرّرها. الحقائب القليلة التي تجتاز هذا الفحص تمرّ على كاشف المعادن (5 ثوانٍ). لا تزال مشبوهة؟ فحص بالأشعة الكاملة (30 ثانية).

99% من الحقائب تُنهي الفحص في أقل من ثانيتين. وحدها المشبوهة فعلاً تصل إلى الفحص المُكلف.

هذا ما تفعله فيولا-جونز تماماً: تفحص نوافذ الصورة واحدة تلو الأخرى، وكل فحص يعتمد على أنماط ضوء وظلّ بسيطة. معظم مساحة الصورة واضح أنها ليست وجهاً، فتُستبعد في أجزاء من الميلّيثانية، ويبقى تركيز الكاشف على النوافذ القليلة التي قد تحتوي وجهاً فعلاً.

المشكلة: مسح 100,000 نافذة في كل إطار

في جوهره مسألة نافذة منزلقة: نأخذ نافذة صغيرة — مثلاً 24×24 بكسل — ونُزلقها على كل موضع في الصورة وبكل حجم ممكن. صورة بأبعاد 384×288 تُولّد أكثر من 100,000 نافذة فرعية، وعند كل واحدة على الكاشف أن يُجيب: «هل هذا وجه أم لا؟»

قبل فيولا-جونز كانت أفضل الكواشف تعتمد على أو آلات متّجه الدعم. دقتها كانت جيدة، لكن تشغيلها على كل نافذة كان أبطأ بكثير مما يحتمله الفيديو. المشكلة واضحة: نحتاج دقيقاً وسريعاً بما يكفي للتقييم في أجزاء من الميكروثانية في الوقت نفسه.

افتح في المختبر
شاهد النافذة 24×24 وهي تنزلق عبر الصورة. كل موضع يحتاج قرار تصنيف مستقلاً.
تستيقظ التجربة عند وصولك…

سمات هار: أبسط كواشف أنماط ممكنة

بدلاً من التعامل مع البكسلات الخام، تستخدم فيولا-جونز — وهي أنماط مستطيلة تقيس فرق السطوع بين مناطق متجاورة. الفكرة بسيطة: تخيّل قالباً نصفه أبيض ونصفه أسود، تضعه على الصورة وتحسب مجموع البكسلات تحت الجزء الأبيض ناقص مجموعها تحت الجزء الأسود.

لماذا ينجح هذا مع الوجوه؟ لأن للوجه بنية إضاءة ثابتة تقريباً: منطقة العينين أغمق من الوجنتين أسفلها، وجسر الأنف أفتح من العينين على جانبيه. ثنائية المستطيل تُوضع أفقياً فوق العينين تلتقط هذا النمط بالضبط — قيمتها ترتفع حين يتطابق القالب مع بنية تشبه الوجه، وتنخفض فيما عدا ذلك.

هناك ثلاثة أنواع أساسية: سمات الحافة (مستطيلان)، وسمات الخط (ثلاثة مستطيلات)، وسمات القُطر (أربعة مستطيلات). إذا حسبنا كل المواضع والأحجام والأنواع الممكنة داخل نافذة 24×24، نحصل على أكثر من 160,000 سمة محتملة — أكثر بكثير من عدد البكسلات نفسها.

افتح في المختبر
بدّل بين أنواع السمات واسحبها فوق الوجه. لاحظ كيف تعطي مناطق العينين والأنف استجابات أقوى بوضوح.
تستيقظ التجربة عند وصولك…

الصورة التكاملية: مجاميع مستطيلات في زمن ثابت

لو حسبنا أكثر من 160,000 مجموع مستطيلي بالطريقة العادية — حلقة على كل بكسل داخل المستطيل — لكان ذلك أبطأ بكثير مما نحتمل. الحل الذي قدّمه فيولا وجونز هو الصورة التكاملية (تُعرَف أيضاً بجدول المجاميع المساحية): جدول يُبنى مرة واحدة، وكل خلية فيه تخزّن مجموع كل البكسلات التي تقع أعلاها ويسارها.

بعد بناء هذا الجدول (تمريرة واحدة فقط على الصورة)، يمكنك حساب مجموع أي مستطيل بـأربع عمليات قراءة وثلاث عمليات جمع وطرح — مهما كان حجم المستطيل. مستطيل 2×2 ومستطيل 200×200 يُكلّفان القدر ذاته تماماً. هذه هي الحيلة التي تجعل حساب سمات هار عند كل الأحجام ممكناً في زمن ثابت.

ii(x,y)=∑x′≤x, y′≤yi(x′,y′)ii(x,y) = \sum_{x' \leq x,\, y' \leq y} i(x', y')
الصورة التكاملية — كل خلية هي المجموع التراكمي لما فوقها ويسارها — i(x,y) قيمة البكسل الأصلية، وii(x,y) قيمته في الصورة التكاملية. لحساب مجموع أي مستطيل ABCD نستخدم: ii(D) + ii(A) − ii(B) − ii(C) — أربع عمليات قراءة مهما كان الحجم.
افتح في المختبر
انقر على أي مستطيل في الصورة وشاهد كيف تحسب أربع عمليات قراءة عند الزوايا مجموع بكسلاته فوراً.
تستيقظ التجربة عند وصولك…

AdaBoost: انتقاء أفضل السمات

من بين أكثر من 160,000 سمة، الغالبية العظمى لا فائدة منها. كيف نعثر على القلّة التي تُحدث فرقاً؟ الجواب هو AdaBoost (). الفكرة أن الخوارزمية تعمل على جولات متتابعة:

  1. نبدأ بإعطاء كل صورة الوزن نفسه.
  2. نبحث عن سمة هار الواحدة الأفضل في الفصل بين الوجوه وغير الوجوه — وهذا ما يُسمّى ، ويكفي أن يكون أفضل بقليل من التخمين العشوائي.
  3. نرفع أوزان الصور التي أخطأ فيها، ونخفض أوزان التي أصاب فيها.
  4. نُكرّر: كل جولة جديدة تركّز على الحالات الصعبة التي فشلت فيها الجولات السابقة.

بعد T جولة نملك T مصنِّفاً ضعيفاً. المصنِّف القوي النهائي هو تصويتها الموزون — كلما كانت السمة أدقّ حصلت على صوت أعلى. والنتيجة مذهلة: مصنِّف قوي مبني من 200 سمة فقط (من أصل 160,000+) يحقق معدل كشف 95% مع نسبة مقبولة.

أول سمة تنتقيها الخوارزمية تلتقط الفرق بين منطقة العينين الداكنة ومنطقة الخدّ الفاتحة تحتها — سمة أفقية ثنائية المستطيل تُترجم ما يعرفه كل إنسان بالفطرة: العيون تقع في الظلّ.

ht(x)={1if ptft(x)<ptθt0otherwiseh_t(x) = \begin{cases} 1 & \text{if } p_t f_t(x) < p_t \theta_t \\ 0 & \text{otherwise}\end{cases}
المصنِّف الضعيف — سمة واحدة، عتبة واحدة، قطبية واحدة — f_t(x) قيمة السمة، وθ_t العتبة، وp_t القطبية (1±). كل مصنِّف ضعيف يُصدر حكماً بسيطاً: «وجه» أو «ليس وجهاً» بناءً على ما إذا تجاوزت سمة هار واحدة عتبة محددة.
H(x)={1∑t=1Tαtht(x)≥12∑t=1Tαt0otherwiseH(x) = \begin{cases} 1 & \sum_{t=1}^{T} \alpha_t h_t(x) \geq \tfrac{1}{2}\sum_{t=1}^{T} \alpha_t \\ 0 & \text{otherwise}\end{cases}
المصنِّف القوي — التصويت الموزون لكل المصنِّفات الضعيفة — α_t وزن المصنِّف الضعيف t — كلما كان أدقّ ارتفع وزنه. القرار النهائي هو تصويت أغلبية موزون بين كل المصنِّفات الضعيفة. هذا جوهر AdaBoost.
افتح في المختبر
تنقّل بين جولات AdaBoost خطوة بخطوة. لاحظ كيف تختار كل جولة سمة جديدة تعالج أخطاء ما قبلها.
تستيقظ التجربة عند وصولك…

سلسلة الانتباه المتدرّجة: ارفض مبكراً وبتكلفة زهيدة

حتى مصنِّف من 200 سمة مُكلف جداً إذا شغّلناه على كل نافذة. لكن هنا تأتي الملاحظة الجوهرية: معظم النوافذ ليست وجوهاً أصلاً. لماذا نُنفق 200 سمة على رقعة سماء صافية؟

السلسلة المتدرّجة تُرتّب المصنِّفات في مراحل، من الأرخص إلى الأغلى:

  • المرحلة 1: تستخدم سمتين فقط. تلتقط ~100% من الوجوه لكنها تسمح بمرور 40% من غير الوجوه. التكلفة: أجزاء من الميكروثانية. الأثر: نصف العمل يُزاح فوراً.
  • المرحلة 2: تستخدم 10 سمات، وتُطبَّق فقط على ما اجتاز المرحلة الأولى.
  • المراحل 3–38: تستخدم 25 ثم 50 ثم مئات السمات تدريجياً. كل مرحلة تُنقص عدد الباقين أكثر.

القيد الأساسي: كل مرحلة يجب أن تحافظ على معدل كشف شبه مثالي (~99.9%) مع استبعاد أكبر قدر ممكن من غير الوجوه. معدل الإنذار الكاذب الكلي يساوي حاصل ضرب معدلات الإنذار الكاذب في كل المراحل. مع 38 مرحلة، حتى الاستبعاد المتواضع في كل مرحلة يتراكم ليصل إلى معدل إنذار كاذب متناهي الصغر.

المحصلة: في المتوسط لا تُقيَّم سوى 10 سمات (من أصل 6,000+) لكل نافذة. الأغلبية الساحقة تُرفَض عند المرحلة الأولى أو الثانية دون أن تصل إلى المراحل المُكلفة — وهذا ما يمنح إمكانيته.

F=∏i=1Kfi,D=∏i=1KdiF = \prod_{i=1}^{K} f_i, \qquad D = \prod_{i=1}^{K} d_i
رياضيات السلسلة — معدلات الإنذار الكاذب والكشف تتراكم بالضرب — F = معدل الإنذار الكاذب الكلي، D = معدل الكشف الكلي، K = عدد المراحل. المعدلات تتضاعف بالضرب من مرحلة لأخرى. مثلاً مع f_i ≈ 0.3 عبر 10 مراحل: F = 0.3¹⁰ ≈ 0.000006. هكذا تحقّق السلسلة انتقائية فائقة من تراكم استبعاد متواضع في كل مرحلة.
افتح في المختبر
شاهد 1,000 نافذة فرعية تدخل السلسلة وراقب كم منها ينجو بعد كل مرحلة — ستلاحظ أن معظمها يسقط في المرحلتين الأولى والثانية.
تستيقظ التجربة عند وصولك…

كيف تعمل القطع معاً

خط المعالجة يسير هكذا: (1) نحوّل الصورة إلى تدرّج رمادي ونبني الصورة التكاملية في تمريرة واحدة. (2) نُزلق نافذة 24×24 على أحجام متعددة. (3) عند كل موضع نُشغّل السلسلة المتدرّجة — معظم النوافذ تخرج من المرحلة الأولى مباشرة. (4) النوافذ القليلة التي تجتاز المراحل الـ38 كلها تُعلَن كوجوه. (5) ندمج الكشوف المتداخلة.

النظام عالج صورة بأبعاد 384×288 في نحو 0.067 ثانية (15 إطاراً في الثانية) على معالج Pentium III بسرعة 700 ميغاهرتز — معالج تجاري عادي من عام 2001. على مجموعة اختبار MIT+CMU حقّق معدل كشف 91.4% مع 50 إنذاراً كاذباً فقط على 130 صورة اختبار.

افتح في المختبر
اضغط «كشف» لتشغيل خط المعالجة كاملاً. شاهد كيف تُبنى الصورة التكاملية، ثم تعمل التصفية المتدرّجة، ثم تظهر الوجوه المكتشفة.
تستيقظ التجربة عند وصولك…

الأفكار الأساسية في شيفرة برمجية

الصورة التكاملية وحساب سمات هارpython

مبسَّط لإظهار الفكرة — ليس التنفيذ الحقيقي.

import numpy as np

def integral_image(img):
    """بناء الصورة التكاملية: ii[y,x] = مجموع كل البكسلات أعلاها ويسارها."""
    return img.cumsum(axis=0).cumsum(axis=1)

def rect_sum(ii, x1, y1, x2, y2):
    """مجموع البكسلات في المستطيل (x1,y1)→(x2,y2) بأربع عمليات قراءة."""
    A = ii[y1-1, x1-1] if y1 > 0 and x1 > 0 else 0
    B = ii[y1-1, x2]   if y1 > 0 else 0
    C = ii[y2, x1-1]   if x1 > 0 else 0
    D = ii[y2, x2]
    return D + A - B - C   # زمن ثابت، لأي حجم مستطيل

def haar_two_rect(ii, x, y, w, h):
    """سمة ثنائية المستطيل: النصف العلوي ناقص النصف السفلي."""
    top  = rect_sum(ii, x, y, x+w-1, y+h//2-1)
    bot  = rect_sum(ii, x, y+h//2, x+w-1, y+h-1)
    return top - bot       # عالية حين يكون الأعلى أسطع من الأسفل

# مثال: أول سمة ينتقيها AdaBoost
# حافة أفقية عبر منطقة العين: داكن أعلاه وفاتح أسفله
# هذه السمة الواحدة ترفض ~50% من غير الوجوه.

لماذا غيّرت كل شيء

  1. 2001

    فيولا-جونز — كشف الوجوه اللحظي

    أول كاشف وجوه يعمل بمعدل 15 إطاراً في الثانية على عتاد تجاري عادي. الصورة التكاملية وانتقاء السمات بـAdaBoost والسلسلة المتدرّجة — ثلاث أفكار رسمت ملامح عقد كامل في الرؤية الحاسوبية.

  2. 2003

    توسيع سمات هار (ليينهارت ومايدت)

    أُضيفت سمات هار مائلة بزاوية 45° فتحسّن أداء الكشف. أصبحت هذه المجموعة الموسّعة هي الخيار الافتراضي لتدريب السلاسل المتدرّجة في OpenCV.

  3. 2005

    HOG + SVM (دالال وتريغز)

    استُبدلت سمات هار بواصفات تدرُّج أغنى تعتمد على توزيع اتجاهات الحوافّ، وأعطت نتائج ممتازة في كشف المشاة. النموذج لا يزال يقوم على النافذة المنزلقة.

  4. 2012

    AlexNet — بداية عصر التعلُّم العميق

    الشبكات الالتفافية العميقة صارت تتعلّم السمات تلقائياً وتفوّقت على السمات المصمَّمة يدوياً كهار وHOG. لكن مبدأ الاستبعاد المتدرّج لم يمت — عاد بأشكال جديدة.

  5. 2014

    R-CNN (غيرشيك وآخرون)

    شبكة CNN قائمة على المناطق: اقترح مناطق مرشّحة أولاً ثم صنّف كلاً منها بشبكة عميقة. الفلسفة هي فلسفة السلسلة المتدرّجة نفسها: لا تُصنّف كل شيء، بل رشّح أولاً.

  6. 2016

    YOLO و SSD — كشف بتمريرة واحدة

    تمريرة واحدة عبر شبكة عصبية واحدة تحلّ محلّ خط المعالجة بأكمله — نافذة منزلقة وسلسلة متدرّجة معاً. كشف لحظي من جديد لكن بسمات عميقة هذه المرة. الشعلة انتقلت من فيولا-جونز.

المرجعViola, Jones. Rapid Object Detection Using a Boosted Cascade of Simple Features. CVPR, 2001.

مصطلحات هذه الورقة