Comparación de formas irregulares

Question

Estoy tratando de llegar a un sistema de puntuación para algunas investigaciones de psicología del comportamiento.

Pido a las personas que dibujen una letra, luego tracen sobre ella, ambas en una tableta gráfica. Quiero evaluar la precisión de este rastro. Entonces, dibujas cualquier letra ('a'), luego lo haces de nuevo, luego la puntúo en función de lo similar que fue a la primera vez que la dibujaste. Los dibujos se almacenan como ubicaciones de píxeles.

La precisión se evalúa como la proximidad a la letra original. El método no necesita permitir cambios de escala, rotación o posición. Conceptualmente es como el área entre las dos líneas, solo las líneas son muy irregulares, por lo que las integrales (que yo sepa) no funcionarán.

Escribo en MATLAB, pero cualquier ayuda conceptual sería apreciada. Intenté sumar la distancia mínima entre todos los píxeles dibujados, pero esto da puntajes buenos (bajos) a puntos individuales bien ubicados.

Esto debe haberse hecho antes, pero no estoy teniendo suerte con mis búsquedas. Cualquier ayuda muy apreciada!

--- Solución parcial utilizando el método sugerido por @Bill a continuación. No funciona, ya que el gradiente de bwdist es demasiado empinado. En lugar de la bonita segunda imagen que Bill muestra, se parece más a la original.

%% Letter to image 
im = zeros(1080,1920,3); % The screen (possible pixel locations) 
% A small square a bit like the letter 'a', a couple of pixels wide. 
pixthick = 5; 
im(450:450+pixthick,[900:1100],:) = 1; 
im(550:550+pixthick,[900:1100],:) = 1; 
im([450:550],900:900+pixthick,:) = 1; 
im([450:570],1100:1100+pixthick,:) = 1; 
subplot(2,1,1); imagesc(im); %% atransbw = bwdist(im(:,:,1)<0.5); subplot(2,1,2); 
imagesc(atransbw); 

Answer 1

Lo que podría ayudarle es una distance transform, implementado en MATLAB como bwdist. Estas líneas de recompensas están cerca, incluso si no coinciden.

a_img_1 = imread('a.jpg'); 
imagesc(a_img_1); 

a_img_1_dist_transform = bwdist(a(:, :, 1) < 250); 
imagesc(a_img_1_dist_transform); 

Puede hacer lo mismo con la segunda imagen, y resumir la diferencia en los valores de píxeles en las imágenes distancia transformado, algo así como:

score = sum(abs(a_img_1_dist_transform(:) - a_img_2_dist_transform(:))) 

(Tenga en cuenta que esto le dará puntajes más altos a menos imágenes similares y v.v.)

Para evitar problemas que mencione de "puntajes buenos (bajos) en puntos individuales bien ubicados", puede experimentar con otras medidas de distancia, como la distancia cuadrática entre valores de píxeles.

Answer 2

Es posible que desee encontrar una transformación afín que coincida con algún criterio de error, por ejemplo, error cuadrático medio. De esta manera, usted será invariante para la traducción y la escala. O si desea penalizar la traducción, también puede agregar el costo de la traducción. (Nos ayudaría a ayudarlo si proporciona más información sobre qué tipo de características se consideran similares o no)

Ahora, una implementación eficiente es otra cuestión. Tal vez deberías mirar en el registro de imágenes. Estoy seguro de que esto se ha hecho muchas veces.

Answer 3

En realidad, sugeriría una solución mucho más de alto nivel. Encuentre un algoritmo de aprendizaje automático OCR que devuelva algún tipo de confianza. O bien, si no tiene confianza, pruebe la distancia entre el texto de salida y el real.
Esto es como un ser humano que observa la escritura e intenta comprenderla. Cuanto mayor sea la confianza, mejor será el resultado.

Answer 4

Los contextos de forma son un poderoso descriptor de características basado en "histogramas polares" de las formas. El Wikipedia page es en profundidad, pero here es otra página con información adicional (y una buena explicación visual de la técnica), así como MATLAB demo code. Las letras coincidentes fueron una de las aplicaciones originales del método, y el código de demostración al que me conecto no requiere que convierta sus vectores de rastreo en imágenes.

Un método más simplista podría ser una "diferencia de imagen" definida como exclusiva o de dos letras. Esto requeriría convertir sus vectores de traza a imágenes binarias. Algo así como:

x = xor(im1,im2); 
d = sum(x(:))/sum(im1(:)); %# normalize to the first image 

Por último, si sus vectores traza tienen el mismo número de puntos, o se puede hacer que por muestreo, análisis procrusteano podría ser útil. La idea del análisis de Procrustes es encontrar una transformación lineal óptima de mínimos cuadrados (rotación, traslación y escalado) entre dos conjuntos de puntos. La bondad de ajuste entre los dos conjuntos de puntos viene dada por la "estadística de Procrustes" u otras medidas como la desviación de la raíz media cuadrática de los puntos.

%# Whatever makes sense; 
%# procrustes needs N x 2 matrices with (x,y) coords for N points. 
coords1 = [x1 y1]; 
coords2 = [x2 y2]; 

%# This sampling may be too naive. 
n = max(size(coords1,1), size(coords2,1)); 
coords1 = coords1(1:n,:); 
coords2 = coords2(1:n,:); 

%# d is sum-of-squares error 
%# z is transformed coords2 
%# tr is the linear transformation 
[ d, z, tr ] = procrustes(coords1, coords2); 

%# RMS deviation of points may be better than SSE. 
n = size(coords1,1); 
rmsd = sqrt((sum((coords1(:) - z(:)).^2)/n)); 

Answer 5

Esta es mi solución definitiva y complicada, que básicamente utiliza el método de Bill Cheatham. ¡Gracias por toda la ayuda!

% pixLet is the 2D vector contain locations where drawing occurred. First convert it to an image. 

im = zeros(1000,1000); % This is the image 
for pix = 2:size(pixLet,1) 
    y1 = pixLet(pix-1,2); x1 = pixLet(pix-1,1); 
    y2 = pixLet(pix,2); x2 = pixLet(pix,1); 
    xyd = round(pdist([x1 y1; x2 y2])*2); 
    xs = round(linspace(x1,x2,xyd)); 
    ys = round(linspace(y1,y2,xyd)); 
    for linepix = 1:length(xs) 
     im(ys(linepix),xs(linepix)) = 1; 
    end 
end 

% Blur the image 
blur = fspecial('gaussian',[sz sz],reach); 
gausIm = conv2(im,blur,'same'); 

% I made a function of the above to do this for both the template and the trace. 
score = sum(sum(abs(gausIm1-gausIm2)));