Estoy intentando escribir un programa que va a realizar el OCR en un teléfono móvil, y hace poco me encontré con este artículo :
Puede alguien explicar esto a mí ?
Respuesta
¿Demasiados anuncios?
Andrew
Puntos
140
Es lamentable que se utiliza "valores propios" de la descripción que aquí (aunque es correcto); es mejor mirar el análisis de componentes principales desde el punto de vista de la descomposición de valor singular (SVD).
Recordar que cualquier $m\times n$ matriz $\mathbf$ posee la descomposición de valor singular de $\mathbf A=\mathbf U\mathbf \Sigma\mathbf V^\$, donde $\mathbf U$ y $\mathbf V$ son matrices ortogonales, y $\mathbf \Sigma$ es una matriz diagonal cuyas entradas $\sigma_k$ son llamados valores singulares. Cosas que normalmente están configurados de tal manera que los valores propios son dispuestos en nonincreasing orden: $\sigma_1 \geq \sigma_2 \geq \cdots \geq \sigma_{\min(m,n)}$.
Por analogía con el eigendecomposition (autovalores y autovectores), el $k$-ésima columna de $\mathbf U$, $\mathbf u_k$, correspondiente a la $k$-ésimo valor singular que se llama la izquierda singular vector, y el $k$-ésima columna de $\mathbf V$, $\mathbf v_k$, es el derecho singular vector. Con esto en mente, usted puede tratar $\mathbf$ como una suma de exterior, productos de vectores, con los valores singulares como "pesos":
$$\mathbf A=\sum_{k=1}^{\min(m,n)} \sigma_k \mathbf u_k\mathbf v_k^\$$
Bien, en este punto, algunas personas podrían ser murmuración "blablabla, álgebra lineal tonterías". La clave aquí es que si el tratamiento de imágenes como matrices (niveles de gris, o valores de color RGB a veces), y, finalmente, los de las matrices de enfermedad vesicular porcina, que a su vez que algunos de los valores singulares de $\sigma_k$ son pequeñas. La clave de la "aproximación" de estas imágenes, entonces, es tratar a esos pequeños $\sigma_k de$ cero, resultando en lo que se llama un "bajo-rango aproximación":
$$\mathbf Un\approx\sum_{k=1}^\ell \sigma_k \mathbf u_k\mathbf v_k^\la parte superior,\qquad \ell \ll \min(m,n)$$
Las matrices correspondientes a las imágenes puede ser grande, por lo que ayuda si usted no tiene que mantener a todos los valores propios y vectores singulares de todo. (El "dos", "diez", y "treinta" significan lo que dicen: $n=256$, y han escogido $\ell$ $2$, $10$, y $30$, respectivamente). El criterio de cuando a cero a cabo un singular valor depende de la aplicación, por supuesto.
Supongo que fue un poco largo. Tal vez debería haber vinculado a Cleve Moler el libro en lugar de esto (ver la página 21 en adelante, en particular).
Editar 12/21/2011:
Me he decidido a escribir un breve Mathematica notebook demostrando de bajo rango de aproximaciones a las imágenes, utilizando el famoso Lenna imagen de prueba. El notebook puede ser obtenido de mí, bajo petición.
En breve, el $512\times 512$ imagen de ejemplo puede ser obtenida a través de ImageData[ColorConvert[ExampleData[{"TestImage", "Lena"}], "Grayscale"]]. Una parcela de $\log_{10} \sigma_k$ se parece a esto:
Aquí está una comparación de la original imagen de Lenna con un par de bajo rango de aproximaciones:
Al menos para mis ojos, toma $120$ de $512$ valores singulares (sólo un poco más de $\frac15$ de los valores singulares) lo convierte en una muy buena aproximación.
Probablemente la única salvedad de la SVD es que es bastante lento algoritmo. Para las imágenes que son bastante grandes, teniendo la enfermedad vesicular porcina podría tomar un largo tiempo. Al menos uno se ocupa únicamente de una sola matriz para la escala de grises de las imágenes; de color RGB, fotos, uno debe tomar el SVD de tres matrices, una para cada componente de color.
