Einige Fakten über kaskadierende Klassifikatoren, die in wissenschaftlichen Artikeln selten ernsthaft berücksichtigt werden.

Hallo Habr! Heute werden wir wieder über Anerkennung sprechen. Über ein so einfaches Erkennungsmodell wie einen kaskadierenden Klassifikator. Diese Kaskade wird in der populären Methode von Viola und Jones verwendet, über die sie bereits so oft über Habré geschrieben haben (zum Beispiel hier , hier und hier ). Das Traurige ist, dass trotz der Fülle an Artikeln niemand ernsthaft kaskadierende Klassifikatoren studierte. Und das nicht nur auf Habré, sondern auch in der wissenschaftlichen Gemeinschaft. Obwohl der kaskadierende Klassifikator einfach zu sein scheint, gibt es viele Fallstricke und interessante Funktionen. Daher haben wir es eilig, unser Wissen mit Ihnen zu teilen. Also, wenn Sie interessiert sind, willkommen bei cat.

Der kaskadierende Klassifikator ist ein sehr einfaches Modell. Es besteht aus mehreren aufeinanderfolgenden Ebenen, von denen jede als binärer Klassifikator dargestellt werden kann. Der untersuchte Präzedenzfall wird dem Eingang der ersten Ebene zugeführt und „wandert“ dann Ebene für Ebene. Wenn der Klassifizierer auf der nächsten Ebene den Präzedenzfall als negativ erkennt, wird er von den verbleibenden Klassifizierern der Kaskade nicht mehr analysiert. Ein solches einfaches Modell wurde nach der Veröffentlichung der Viola- und Jones-Methode [1] populär, bei der, wie bereits erwähnt, eine hohe Leistung erzielt wurde. Aber ist es nur dafür? Ist es nur ein kaskadierender Klassifikator? Lass es uns herausfinden!

Wir werden den heutigen Artikel über Habré in einem für uns neuen Format erstellen. Wir werden einige Aussagen auswählen, die wir im Detail enthüllen und sogar irgendwo widerlegen werden. Also lasst uns anfangen!

Der kaskadierende Klassifikator in der Viola- und Jones-Methode wird einfach verwendet, um den Betrieb des Objektdetektors zu beschleunigen

Im Originalartikel [1] auf der allerersten Seite steht ein solcher Satz:

Der dritte wichtige Beitrag dieser Arbeit ist eine Methode zur Kombination sukzessive komplexerer Klassifikatoren in einer Kaskadenstruktur, die die Geschwindigkeit des Detektors dramatisch erhöht, indem sie die Aufmerksamkeit auf vielversprechende Bildbereiche lenkt.

In der Tat ist die ursprüngliche Methode von Viola und Jones darauf ausgelegt, nach Objekten im Bild zu suchen. Darüber hinaus wird das Erkennungsproblem durch die Schiebefenstermethode unter Verwendung eines binären Klassifikators gelöst, der an jedem Punkt des untersuchten Bildes in verschiedenen Maßstäben angewendet wird. Das Ungleichgewicht der untersuchten Daten im Stadium der Erkennung („leere“ Regionen ohne das gewünschte Objekt in jedem untersuchten Bild, millionen- oder sogar milliardenfach mehr als Regionen mit Objekten) führte zur Verwendung einer Kaskade - ein Mechanismus, mit dem Sie „leere“ Regionen schnell abschneiden können.

Es ging aber darum, einen bereits ausgebildeten Klassifikator zu verwenden. Wenden wir uns nun dem Klassifikator-Trainingsverfahren zu. Es stellt sich heraus, dass es genau das gleiche Problem des Ungleichgewichts der Stichproben gibt: Die Anzahl der negativen Beispiele ist um ein Vielfaches größer (Millionen und sogar Milliarden Mal mehr) als die Anzahl der positiven Beispiele. Dank seiner Architektur wird jede neue Ebene der Kaskade mit der AdaBoost-Methode nicht für die gesamte negative Trainingsstichprobe trainiert, sondern nur für eine begrenzte Anzahl von Fehlern aus früheren Ebenen der Kaskade! Auf diese Weise können Sie die AdaBoost-Trainingsmaschine mit einer ausgewogenen und begrenzten Stichprobe betreiben!

Wie Sie sehen können, wird die Verwendung des Kaskadenklassifikators in der Viola- und Jones-Methode zweimal ausgeführt:

1. Sie können den Klassifikator einfach trainieren und so das Problem des "unendlichen" Trainingssatzes vermeiden.
2. Es ermöglicht ein schnelles Abschneiden von "leeren" Bereichen während der Objekterkennung, wodurch eine hohe durchschnittliche Produktivität erreicht wird.

Lassen Sie uns die klassische Kaskade weiter studieren und uns dem Thema Leistung zuwenden.

In diesem Sinne ist ein kaskadierender Klassifikator ein Beschleunigungswerkzeug.

Kehren wir noch einmal zur Frage des Zwecks der Kaskade zurück, aber jetzt auf der anderen Seite. Wenn Sie den Kaskadenklassifikator mathematisch betrachten, können Sie sehen, dass die Kaskade eine konjunktive Form starker Klassifikatoren ist (von denen jeder als lineare Zusammensetzung von Attributen dargestellt werden kann):

$$

$$Cascade\left(x\right)=\prod_{i=1}^{N}\left[S_i\left(x\right)>0\right], \\ S\left(x\right)=\left[\sum_{t=1}^{T}{\alpha_t\cdot h_t\left(x\right)}>0\right],$$

Wo $$$\left[\bullet\right]$- Anzeigefunktion.

Angesichts der begrenzten Anzahl verfügbarer Attribute (die sich in der Praxis bei der Verfolgung der Leistung als normal herausstellen) ist die konjunktive Form starker Klassifikatoren ausdrucksstärker als ein einzelner linearer Klassifikator. Dies ist leicht zu verstehen, wenn Sie sich ein einfaches Beispiel vorstellen, bei dem der Merkmalsraum aus zwei Elementen besteht und die positiven und negativen Objekte, die in den Koordinaten dieser Merkmale ausgedrückt werden, sich wie in der folgenden Abbildung gezeigt befinden (die grünen Objekte sind die positiven und die roten die negativen). Es ist klar, dass es keinen solchen einzelnen linearen Klassifikator gibt, der diese Stichprobe korrekt unterteilen kann. Eine Kaskade von vier Ebenen würde diese Aufgabe jedoch garantiert bewältigen.


Somit bietet die Verwendung eines Kaskadenklassifikators neben der Steigerung der Produktivität auch eine größere Ausdruckskraft als ein einzelner linearer Klassifikator unter Bedingungen einer begrenzten Anzahl von Merkmalen.

Der kaskadierende Klassifikator bietet eine konstant hohe Leistung und kann problemlos in Echtzeiterkennungssystemen verwendet werden

Wie oben erwähnt, können Sie mit dem Kaskadenschema aufgrund des schnellen Screenings "leerer" Regionen eine hohe Leistung erzielen, da ihre Anzahl um mehrere Größenordnungen größer ist als die Anzahl der Regionen, die das Objekt enthalten. Die Verarbeitungszeit eines „leeren“ Bereichs unterscheidet sich um ein Vielfaches von der Verarbeitungszeit eines Bereichs mit einem Objekt (proportional zur Länge der Kaskade - Anzahl der Kaskadenebenen).

Da sich die Anzahl der Bereiche, die das Objekt enthalten, von Bild zu Bild unterscheidet, ist auch die Verarbeitungszeit jedes Rahmens unterschiedlich. Aufgrund der Tatsache, dass sich auf dem Rahmen signifikant weniger Regionen mit einem Objekt befinden als Regionen ohne Objekt, wird der Unterschied in der Verarbeitungszeit nicht zehnmal, sondern zehnmal gemessen, was jedoch in industriellen Erkennungssystemen von Bedeutung ist.

Somit kann die Betriebszeit des Kaskadenklassifikators in verschiedenen Bildern erheblich variieren. Daher sollten bei ernsthaften Messungen der Leistung von Klassifikatoren Messungen der Betriebszeit im Durchschnitt und im schlimmsten Fall durchgeführt werden. Und seien Sie immer auf solche vorübergehenden „Inkonsistenzen“ vorbereitet, wenn Sie kaskadierende Klassifikatoren verwenden.

In unserer Praxis hatten wir bereits ernsthafte Probleme aufgrund einer erheblichen Diskrepanz in der Kaskadenbetriebszeit im Durchschnitt und im schlimmsten Fall. Im Rahmen des Projekts zur mautpflichtigen Straßenautomatisierung haben wir das Problem der Erkennung des Fahrzeugtyps gelöst, wobei eine der Hauptunteraufgaben das Problem der Zählung von Radsätzen war. Natürlich haben wir die Viola- und Jones-Methode verwendet, um Räder an einzelnen Rahmen zu erkennen. Aufgrund der großen Variabilität der Räder (siehe Abbildung unten) war die trainierte Kaskade ziemlich lang (20 Stufen). Wir haben unangenehme Live-Probleme beobachtet, die mit unterschiedlichen Verarbeitungszeiten für jeden Frame verbunden waren, was uns ernsthaft daran hinderte, ein Erkennungssystem in Echtzeit aufzubauen.


Dann entwickelten wir die Idee eines klassischen kaskadierenden Klassifikators zu einem vollwertigen Entscheidungsbaum und entwickelten eine einzigartige Lerntechnologie für einen solchen Entscheidungsbaum (denken Sie daran, dass ein Algorithmus vorgeschlagen werden musste, mit dem wir die mit dem „endlosen“ Trainingssatz verbundenen Probleme vermeiden können). Details zu diesem Algorithmus finden Sie in unserer wissenschaftlichen Arbeit [3]. Hier berichten wir nur einige Fakten:

1. Der längste Pfad in einem trainierten Baum besteht aus 6 starken Klassifikatoren (das Schema eines trainierten Baumklassifikators ist in der folgenden Abbildung dargestellt).
2. Ein ausgebildeter Baumklassifikator bot eine bessere Arbeitsqualität als eine zuvor trainierte Kaskade. Dies ist logisch und folgt aus der Tatsache, dass die Ausdruckskraft der baumartigen Kaskade (die eine konjunktiv-disjunktive Form ist) höher ist als die Ausdruckskraft der Kaskade (konjunktive Form).
3. Ein ausgebildeter Baumklassifikator hat die Kaskade im schlimmsten Fall ernsthaft umgangen, fast ohne im Durchschnitt zu verlieren.

Die folgende Tabelle enthält numerische Vergleiche von Kaskaden- und Baumklassifikatoren.


Wenn Sie also wirklich kaskadierende Klassifikatoren in Echtzeit in Erkennungssystemen verwenden möchten, denken Sie immer an die Funktionen, die mit der Arbeitsgeschwindigkeit im Durchschnitt und im schlimmsten Fall verbunden sind.

Die kaskadierenden Klassifikator-Trainingstechnologien sind so offensichtlich, dass es nichts gibt, mit dem man sich ernsthaft beschäftigen könnte.

Oh, dies ist wahrscheinlich eines der schwierigsten Themen im Zusammenhang mit kaskadierenden Klassifikatoren. Das Fazit ist, dass in allen Artikeln, die wir getroffen haben, der Kaskadenlernprozess so schlecht, oberflächlich und ohne angemessene Begründung der Wirksamkeit des Kaskadenlernalgorithmus beschrieben wird. Normalerweise sieht der Kaskadenlernalgorithmus ungefähr so ​​aus:

1. Entscheiden Sie sich für die Werte des Anteils der falschen Anerkennung ($$$F$) für die gesamte Kaskade.
2. Entscheiden Sie sich für die Werte des Anteils der tatsächlichen Anerkennung ($$$d$) und Bruchteile falscher Erkennung ($$$f \lt F$) für jede Erkennungsstufe.
3. Entscheiden Sie sich für ein Validierungsmuster, um die Qualitätsindikatoren des endgültigen Klassifikators ehrlich zu bewerten.
4. Trainieren Sie jede neue Ebene der Kaskade (die, wie wir uns erinnern, an allen verfügbaren positiven Beispielen sowie an falsch positiven Fehlern der aktuellen Kaskade trainiert wird), damit ihre Leistung erreicht wird $$$d_i$und $$$f_i$waren nicht schlimmer als gegeben, das heißt $$$d_i>d$und $$$f_i \lt f$. Übrigens ist auch der Prozess der Sicherstellung dieser Indikatoren an sich von großem Interesse.
5. Fügen Sie der Kaskade das neu trainierte Level hinzu und bewerten Sie die Qualitätsindikatoren in der Validierungsstichprobe. Wenn die Falscherkennungsrate geringer als das Ziel ist$$$F$, dann beende das Training. Fahren Sie andernfalls mit Schritt 4 fort, um eine neue Kaskadenstufe zu erlernen.

Wenn als Ergebnis des oben genannten Algorithmus trainiert $$$K$Ebenen der Kaskade, dann können Sie die durchschnittliche Komplexität des Anteils der korrekten Erkennung der Kaskade wie folgt schätzen:

$$

$$N=n_1+\sum_{i=2}^{K}\left(n_i\prod_{j=2}^{i}p_j\right),\\ D=\prod_{i=1}^{K}d_i,$$

Wo $$$n_i$- Komplexität $$$i$Kaskadenebene $$$p_i$- Wahrscheinlichkeit der Berechnung $$$i$Level-Kaskade und $$$d_i$- Anteil der korrekten Anerkennungen $$$i$Level-Kaskade.

Wie Sie sehen können, ist die Komplexität der Kaskade nicht an dem vorgestellten Trainingsalgorithmus beteiligt, daher kann sie natürlich nicht als leistungswirksam bezeichnet werden. Gleichzeitig wissen wir mit Sicherheit, dass Wissenschaftler auf der ganzen Welt fest von der Bedeutung von Lernalgorithmen für effektive Kaskaden überzeugt sind. Zur Bestätigung hier ein Zitat aus einem Artikel von Paul Viola und Michael Jones [4]:

The overall training process involves two types of tradeoffs. In most cases classifiers with more features will achieve higher detection rates and lower false positive rates. At the same time classifiers with more features require more time to compute. In principle one could define an optimization framework in which
– the number of classifier stages,
– the number of features, $$$n_i$, of each stage,
– the threshold of each stage
are traded off in order to minimize the expected number of features $$$N$given a target for $$$F$and $$$D$. Unfortunately finding this optimum is a tremendously difficult problem.

Es ist interessant, dass unsere 2016 durchgeführte Überprüfung der einschlägigen Literatur ergab, dass es zu diesem Zeitpunkt keine effektiven Trainingsalgorithmen für kaskadierende Klassifikatoren gab. Übrigens haben wir bei Smart Engines dieses Problem gelöst. Wir haben die folgende Funktion untersucht, die von Erkennungsfehlern der ersten Art abhängt ($$$E_1$), Erkennungsfehler der zweiten Art ($$$E_2$) und mittlerer Schwierigkeitsgrad ($$$N$):

$$

$$F\left(E_1,\ {\ E}_2,\ N\right)=\ {\ \beta_1\cdot\ E}_1+\ \beta_2\cdot E_2+\ \ \beta_3\cdot N.$$

Auswahl der Parameter $$$\beta_1$, $$$\beta_2$und $$$\beta_3$Stellen Sie die relativen Kosten für Fehler der ersten und zweiten Art sowie die Komplexität des resultierenden Detektors ein. Während des Trainings des Kaskadenklassifikators haben wir den Greedy-Algorithmus zum Aufzählen von Parametern auf jeder Ebene verwendet, um Kaskaden zu erhalten, die die ausgewählte Funktion maximieren. Eine detaillierte Beschreibung des entwickelten Algorithmus würde den Rahmen dieses Artikels sprengen, aber wir sind immer bereit, sie mit Ihnen, unserem Leser, zu teilen, indem wir einen bibliografischen Link bereitstellen [5].

Fazit

Um alles, was unsererseits gesagt wurde, am Beispiel des kaskadierenden Klassifikatormodells zusammenzufassen, möchten wir die folgenden Schlussfolgerungen ziehen:

1. Es ist selten möglich, eine wissenschaftliche Arbeit zu treffen, in der alle notwendigen Details ausführlich beschrieben werden.
2. Es ist sehr nützlich, wissenschaftliche Artikel erneut zu lesen und ernsthaft über die Eigenschaften und Einschränkungen der darin vorgestellten Modelle nachzudenken, auch wenn es auf den ersten Blick so aussieht, als ob im Artikel alles „gekaut“ ist.
3. Es wird immer einen Platz für wertvolle wissenschaftliche Forschung geben, auch wenn das untersuchte Modell vor 20 Jahren vorgeschlagen wurde.

Wir freuen uns sehr, wenn das in diesem Artikel vorgestellte Material nützlich ist und natürlich immer für eine fruchtbare Diskussion in den Kommentaren bereit ist.

Danke.