La detección de rostros de Viola-Jones afirma 180k características

He estado implementando una adaptación del algoritmo de detección de rostros de Viola-Jones . La técnica se basa en colocar un subcuadro de 24x24 píxeles dentro de una imagen y, posteriormente, colocar elementos rectangulares en su interior en todas las posiciones con todos los tamaños posibles.

Estas características pueden constar de dos, tres o cuatro rectángulos. Se presenta el siguiente ejemplo.

Afirman que el conjunto exhaustivo es más de 180k (sección 2):

Dado que la resolución base del detector es 24x24, el conjunto exhaustivo de características rectangulares es bastante grande, más de 180.000. Tenga en cuenta que, a diferencia de la base Haar, el conjunto de características rectangulares está demasiado completo.

Las siguientes declaraciones no se establecen explícitamente en el documento, por lo que son suposiciones de mi parte:

1. Solo hay 2 entidades de dos rectángulos, 2 entidades de tres rectángulos y 1 entidad de cuatro rectángulos. La lógica detrás de esto es que estamos observando la diferencia entre los rectángulos resaltados, no explícitamente el color o la luminancia ni nada por el estilo.
2. No podemos definir el tipo de característica A como un bloque de píxeles de 1x1; debe tener al menos 1x2 píxeles. Además, el tipo D debe tener al menos 2x2 píxeles, y esta regla se aplica de acuerdo con las otras características.
3. No podemos definir el tipo de característica A como un bloque de píxeles de 1x3 ya que el píxel del medio no se puede dividir y restarlo de sí mismo es idéntico a un bloque de píxeles de 1x2; este tipo de característica solo se define para anchos pares. Además, el ancho del tipo de característica C debe ser divisible por 3, y esta regla se aplica de acuerdo con las otras características.
4. No podemos definir una característica con una anchura y / o altura de 0. Por lo tanto, iterate X y Y a 24 menos el tamaño de la característica.

Según estas suposiciones, he contado el conjunto exhaustivo:

const int frameSize = 24;
const int features = 5;
// All five feature types:
const int feature[features][2] = {{2,1}, {1,2}, {3,1}, {1,3}, {2,2}};

int count = 0;
// Each feature:
for (int i = 0; i < features; i++) {
    int sizeX = feature[i][0];
    int sizeY = feature[i][1];
    // Each position:
    for (int x = 0; x <= frameSize-sizeX; x++) {
        for (int y = 0; y <= frameSize-sizeY; y++) {
            // Each size fitting within the frameSize:
            for (int width = sizeX; width <= frameSize-x; width+=sizeX) {
                for (int height = sizeY; height <= frameSize-y; height+=sizeY) {
                    count++;
                }
            }
        }
    }
}

El resultado es 162,336 .

La única forma que encontré para aproximarme a las "más de 180.000" de las que hablan Viola & Jones es descartando la suposición número 4 e introduciendo errores en el código. Esto implica cambiar cuatro líneas respectivamente a:

for (int width = 0; width < frameSize-x; width+=sizeX)
for (int height = 0; height < frameSize-y; height+=sizeY)

El resultado es entonces 180.625 . (Tenga en cuenta que esto evitará que las funciones toquen la parte derecha y / o la parte inferior de la subestructura).

Ahora, por supuesto, la pregunta: ¿se han equivocado en su implementación? ¿Tiene algún sentido considerar entidades con una superficie de cero? ¿O lo estoy viendo de forma incorrecta?

Al mirar más de cerca, su código me parece correcto; lo que hace que uno se pregunte si los autores originales tuvieron un error de uno en uno. ¡Supongo que alguien debería ver cómo lo implementa OpenCV!

No obstante, una sugerencia para facilitar la comprensión es cambiar el orden de los bucles for revisando primero todos los tamaños y luego recorriendo las ubicaciones posibles según el tamaño:

#include <stdio.h>
int main()
{
    int i, x, y, sizeX, sizeY, width, height, count, c;

    /* All five shape types */
    const int features = 5;
    const int feature[][2] = {{2,1}, {1,2}, {3,1}, {1,3}, {2,2}};
    const int frameSize = 24;

    count = 0;
    /* Each shape */
    for (i = 0; i < features; i++) {
        sizeX = feature[i][0];
        sizeY = feature[i][1];
        printf("%dx%d shapes:\n", sizeX, sizeY);

        /* each size (multiples of basic shapes) */
        for (width = sizeX; width <= frameSize; width+=sizeX) {
            for (height = sizeY; height <= frameSize; height+=sizeY) {
                printf("\tsize: %dx%d => ", width, height);
                c=count;

                /* each possible position given size */
                for (x = 0; x <= frameSize-width; x++) {
                    for (y = 0; y <= frameSize-height; y++) {
                        count++;
                    }
                }
                printf("count: %d\n", count-c);
            }
        }
    }
    printf("%d\n", count);

    return 0;
}

con los mismos resultados que el anterior 162336

Para verificarlo, probé el caso de una ventana 4x4 y verifiqué manualmente todos los casos (fácil de contar ya que las formas 1x2 / 2x1 y 1x3 / 3x1 son las mismas solo giradas 90 grados):

2x1 shapes:
        size: 2x1 => count: 12
        size: 2x2 => count: 9
        size: 2x3 => count: 6
        size: 2x4 => count: 3
        size: 4x1 => count: 4
        size: 4x2 => count: 3
        size: 4x3 => count: 2
        size: 4x4 => count: 1
1x2 shapes:
        size: 1x2 => count: 12             +-----------------------+
        size: 1x4 => count: 4              |     |     |     |     |
        size: 2x2 => count: 9              |     |     |     |     |
        size: 2x4 => count: 3              +-----+-----+-----+-----+
        size: 3x2 => count: 6              |     |     |     |     |
        size: 3x4 => count: 2              |     |     |     |     |
        size: 4x2 => count: 3              +-----+-----+-----+-----+
        size: 4x4 => count: 1              |     |     |     |     |
3x1 shapes:                                |     |     |     |     |
        size: 3x1 => count: 8              +-----+-----+-----+-----+
        size: 3x2 => count: 6              |     |     |     |     |
        size: 3x3 => count: 4              |     |     |     |     |
        size: 3x4 => count: 2              +-----------------------+
1x3 shapes:
        size: 1x3 => count: 8                  Total Count = 136
        size: 2x3 => count: 6
        size: 3x3 => count: 4
        size: 4x3 => count: 2
2x2 shapes:
        size: 2x2 => count: 9
        size: 2x4 => count: 3
        size: 4x2 => count: 3
        size: 4x4 => count: 1

todas. Todavía hay cierta confusión en los artículos de Viola y Jones.

En su documento CVPR'01 se indica claramente que

"Más específicamente, utilizamos tres tipos de características. El valor de una característica de dos rectángulos es la diferencia entre la suma de los píxeles dentro de dos regiones rectangulares. Las regiones tienen el mismo tamaño y forma y son adyacentes horizontal o verticalmente (consulte la Figura 1). Una característica de tres rectángulos calcula la suma dentro de dos rectángulos exteriores restada de la suma en un rectángulo central. Finalmente, una característica de cuatro rectángulos ".

En el artículo IJCV'04 se dice exactamente lo mismo. En total, 4 características . Pero, curiosamente, esta vez afirmaron que el conjunto de funciones exhaustivo es 45396. Esa no parece ser la versión final. Aquí supongo que se introdujeron algunas restricciones adicionales, como min_width, min_height, relación ancho / alto e incluso posición.

Tenga en cuenta que ambos documentos se pueden descargar en su página web .

Al no haber leído todo el documento, la redacción de su cita me llama la atención.

Dado que la resolución base del detector es 24x24, el conjunto exhaustivo de características rectangulares es bastante grande, más de 180.000. Tenga en cuenta que, a diferencia de la base Haar, el conjunto de características rectangulares está demasiado completo.

"El conjunto de características del rectángulo está demasiado completo" "Conjunto exhaustivo"

Me suena como una trampa, donde espero que el escritor del artículo continúe con una explicación de cómo reducen el espacio de búsqueda a un conjunto más efectivo, por ejemplo, eliminando casos triviales como rectángulos con cero. área de superficie.

editar: o usar algún tipo de algoritmo de aprendizaje automático, como sugiere el resumen. Un conjunto exhaustivo implica todas las posibilidades, no solo las "razonables".

No hay garantía de que cualquier autor de un artículo sea correcto en todas sus suposiciones y hallazgos. Si cree que el supuesto n. ° 4 es válido, mantenga ese supuesto y pruebe su teoría. Puede tener más éxito que los autores originales.

Muy buena observación, pero implícitamente podrían poner cero en el marco de 24x24, o "desbordar" y comenzar a usar los primeros píxeles cuando se sale de los límites, como en los cambios de rotación, o como Breton dijo que podrían considerar algunas características como "características triviales". y luego deséchelos con AdaBoost.

Además, escribí versiones de Python y Matlab de su código para poder probar el código yo mismo (más fácil de depurar y seguir para mí) y así los publico aquí si alguien los encuentra útiles en algún momento.

Pitón:

frameSize = 24;
features = 5;
# All five feature types:
feature = [[2,1], [1,2], [3,1], [1,3], [2,2]]

count = 0;
# Each feature:
for i in range(features):
    sizeX = feature[i][0]
    sizeY = feature[i][1]
    # Each position:
    for x in range(frameSize-sizeX+1):
        for y in range(frameSize-sizeY+1):
            # Each size fitting within the frameSize:
            for width in range(sizeX,frameSize-x+1,sizeX):
                for height in range(sizeY,frameSize-y+1,sizeY):
                    count=count+1
print (count)

Matlab:

frameSize = 24;
features = 5;
% All five feature types:
feature = [[2,1]; [1,2]; [3,1]; [1,3]; [2,2]];

count = 0;
% Each feature:
for ii = 1:features
    sizeX = feature(ii,1);
    sizeY = feature(ii,2);
    % Each position:
    for x = 0:frameSize-sizeX
        for y = 0:frameSize-sizeY
            % Each size fitting within the frameSize:
            for width = sizeX:sizeX:frameSize-x
                for height = sizeY:sizeY:frameSize-y
                    count=count+1;
                end
            end
        end
    end
end

display(count)

En su artículo original de 2001, solo afirman que se utilizan tres tipos de características:

utilizamos tres tipos de funciones

también

Las regiones tienen el mismo tamaño y forma.

Dado que cada tipo tiene dos orientaciones, es razonable suponer que utilizan 6 características en total (al menos para el cálculo del número total de características): 2 características de dos rectángulos, 2 características de tres rectángulos y 2 características de cuatro rectángulos. Con esta suposición, hay más de 180.000 funciones:

feature_types = [(1,2), (2,1), (1,3), (3,1), (2,2), (2,2)]
window_size = (24,24)

total_features = 0
for f_type in feature_types:
    for f_height in range(f_type[0], window_size[0] + 1, f_type[0]):
        for f_width in range(f_type[1], window_size[1] + 1, f_type[1]):
            total_features += (window_size[0] - f_height + 1) * (window_size[1] - f_width + 1)
            
print(total_features)
# 183072

Si descarta un tipo de características de cuatro rectángulos (que parece ser el caso en su publicación posterior), entonces el número total de características es 162,336.