Census-Transformation

Die Census-Transformation (CT) (engl. Census Transform) wurde von Zabih und Woodfill vorgeschlagen^[1] und berechnet für jeden quadratischen Pixelbereich eines Bildes einen Bit-String als Signatur^[2].

Dadurch können insbesondere über die Hamming-Distanz der Bit-Strings schnell übereinstimmende Bereiche der Bilder ermittelt werden – beispielsweise zur Erzeugung einer disparity map als Vorstufe zur Bestimmung des optischen Flusses (optical flow) oder einer Stereo Disparität (stereo matching) von zeitlich folgenden bzw. gleichzeitig aufgenommenen Bildern.

Der Grauwert des zentralen Pixels wird einzeln mit seinen Nachbarn (Anzahl N) verglichen und das Ergebnis (N × 1 Bit) als Zahl abgespeichert (Bit-String) – wobei das Bit „0“ einen Wert größer und das Bit „1“ einen Wert kleiner oder gleich dem Grauwert des zentralen Pixels kennzeichnet. Meist wird eine 3×3-Umgebung betrachtet und der triviale Vergleich mit sich selbst ausgelassen (3 × 3 − 1 = 8 Bit = 1 Byte). Jedoch ist auch die Betrachtung einer 5×5-Umgebung gebräuchlich (5 × 5 − 1 = 24 Bit).

Die Reihenfolge der Ergebnisbits ist beliebig (aber fest) und kann beispielsweise im Uhrzeigersinn angeordnet sein.

F = [ 1 2 3 8 C 4 7 6 5 ] {\displaystyle \mathbf {F} ={\begin{bmatrix}1&2&3\\8&C&4\\7&6&5\end{bmatrix}}}

Dadurch entsteht ein Signatur-Vektor (z. B. „11001011“ bei einer 3x3 Umgebung) für den zentralen Pixel, welcher mit anderen Signatur-Vektoren verglichen werden kann.

Die von Zabih und Woodfill vorgeschlagene Census-Transformation wurde von Stein durch einen ϵ {\displaystyle \epsilon } -Parameter erweitert, wodurch ähnliche Pixel repräsentiert werden können (und damit eine gewisse Unschärfe bzw. Rauschen toleriert wird). Dadurch entsteht eine 3-wertige (three-moded) Census-Transformation, die hier in der von Stein gewählten Definition zusammen mit einem Beispiel gezeigt wird:

ξ ( P , P ′ ) = { 0 , wenn  P − P ′ > ϵ 1 , wenn  | P − P ′ | ≤ ϵ 2 , wenn  P ′ − P > ϵ 124 74 32 124 64 18 157 116 84 ⟶ 2 1 0 2 x 0 2 2 2 ⟶ 21002222 {\displaystyle \xi (P,P')={\begin{cases}0,&{\text{wenn }}P-P'>\epsilon \\1,&{\text{wenn }}|P-P'|\leq \epsilon \\2,&{\text{wenn }}P'-P>\epsilon \end{cases}}\qquad {\begin{array}{|c|c||c|}\hline 124&74&32\\\hline 124&64&18\\\hline 157&116&84\\\hline \end{array}}\longrightarrow {\begin{array}{|c|c|c|}\hline 2&1&0\\\hline 2&x&0\\\hline 2&2&2\\\hline \end{array}}\longrightarrow 21002222}

Bei der dreiwertigen Census-Transformation werden also zwei Bit benötigt, was die Länge des Vergleichsvektors verdoppelt.

Andererseits wird bei der erstmals von Fröba und Ernst vorgeschlagenen modifizierten Census-Transformation (modified CT, MCT) die Umgebung (Nachbarn und Zentralpixel) mit dem Mittelwert der 3×3-Umgebung verglichen. Dadurch hat die Filterantwort jedes Pixels ein Bit mehr (9 bzw. 25 Bit).

• kaum abhängig von Helligkeitsschwankungen (Belichtungszeit, regionale Schatten)
• unterscheidet Rotation und Spiegelung
• lokaler Filter
• Informationsverlust (d. h. das Bild ist aus der Filterantwort nicht rekonstruierbar)

Die Census-Transformation kann zur Berechnung des optischen Flusses (feature tracking), zur Bildsegmentierung oder bei der Gesichtserkennung verwendet werden. Sie ähnelt vom Konzept her den BRIEF-Features (ein Descriptor) und geht mehrfach in die Berechnung von Local Binary Patterns (LBP) ein.

1. ↑ ZABIH, Ramin; WOODFILL, John. Non-parametric local transforms for computing visual correspondence. In: European conference on computer vision. Springer, Berlin, Heidelberg, 1994, S. 151–158. doi:10.1007/BFb0028345
2. ↑ PEÑA, Dexmont; SUTHERLAND, Alistair. Non-parametric image transforms for sparse disparity maps. In: Machine Vision Applications (MVA), 14th IAPR International Conference on. IEEE, 2015, S. 291–294. doi:10.1109/MVA.2015.7153188

• Ramin Zabih, John Woodfill: Non-parametric local transforms for computing visual correspondence. In: Jan-Olof Eklundh (Hrsg.): Computer Vision — ECCV ’94 (= Lecture notes in computer science. Band 801). Springer-Verlag, Berlin/Heidelberg 1994, ISBN 3-540-57957-5, S. 151–158, doi:10.1007/BFb0028345. 
• Fridtjof Stein: Efficient Computation of Optical Flow Using the Census Transform. In: Pattern Recognition (= Lecture notes in computer science. Band 3175). Springer, Berlin/Heidelberg 2004, ISBN 3-540-22945-0, S. 79–86, doi:10.1007/978-3-540-28649-3_10. 
• Bernhard Fröba, Andreas Ernst: Face Detection with the Modified Census Transform. In: Proceedings of the Sixth IEEE International Conference on Automatic Face and Gesture Recognition (FGR’04). doi:10.1109/AFGR.2004.1301514. 
• Zucheul Lee, Jason Juang, Truong Q. Nguyen: Local Disparity Estimation With Three-Moded Cross Census and Advanced Support Weight. In: IEEE Transactions on Multimedia. Band 15, Nr. 8, 2013, S. 1855–1864, doi:10.1109/TMM.2013.2270456. 
• Bogusław Cyganek: Comparison of Nonparametric Transformations and Bit Vector Matching for Stereo Correlation. In: R. Klette, J. Žunić (Hrsg.): Combinatorial Image Analysis. IWCIA 2004 (= Lecture Notes in Computer Science (LNCS). Band 3322). 2004, S. 534–547, doi:10.1007/978-3-540-30503-3_39. 

• Michael Calonder, Vincent Lepetit, Christoph Strecha, Pascal Fua: BRIEF: Binary Robust Independent Elementary Features. In: Computer Vision – ECCV 2010 (= Lecture notes in computer science. Band 6314). Springer, Berlin/Heidelberg 2010, ISBN 978-3-642-15560-4, S. 778–792, doi:10.1007/978-3-642-15561-1_56 (online).