[Matemáticas] Resumir secuencia de números

Archivado
Suponeos que tenemos una secuencia de números:
3 2 4 5 6 7 1 8 9


Tenemos que resumir la secuencia en un solo número minimizando el error, por definición de "minimizar el error" se entiende como que los números se modifican lo menos posible. Por ejemplo si cogieramos el 9 y calcularamos el error absoluto acumulado:
9-9 = 0
9-8 = 1
9-7 = 2
9-6 = 3
9-5 = 4
9-4 = 5
9-3 = 6
9-2 = 7
9-1 = 8

Total: 36


La solución más eficiente a este problema en concreto sería el 5, puesto que su error es menor:

5-9 = 4
5-8 = 3
5-7 = 2
5-6 = 1
5-5 = 0
5-4 = 1
5-3 = 2
5-2 = 3
5-1 = 4

Total: 20


Si en vez de un solo número, tuvieramos que resumirla en dos números, probablemente cogeríamos el 3 y el 6. Y si fueran 5 números cogeríamos los números pares.

Si generalizamos el problema. Se busca que dada una secuencia de números, resumirla en X números de modo que se minimize el error. ¿Que pasos se deberían seguir para tener siempre la mejor solución? Busco un método que seguir paso a paso (da igual que sea laborioso, lo hará una computadora).

La idea de este problema es coger una imagen en 24 bits de color y pasarla a 256 colores sin perder mucha información, tengo mis dudas sobre como hacerlo y he planteado este problema que es equivalente
No sé si lo he entendido bien, pero creo q lo que pides es esto:

El maximo valor de la secuencia menos el minimo, todo ello partido por x+1, siendo x el cardinal de numeros que quieres. Tomas la parte entera (lo llamamos a) y los numeros que pides serian a*n con n=1,2,...x
Julian Sorel escribió:No sé si lo he entendido bien, pero creo q lo que pides es esto:

El maximo valor de la secuencia menos el minimo, todo ello partido por x que son los numero que quieres. Tomas la parte entera (lo llamamos a) y los numeros que pides serian a*n con n=1,2,...x

Eso solo funcionaría si la secuencia fuese continua y simétrica.

Te pongo un ejemplo que no funcionaría:
1 24 25 26

Buscar un número, según tu algoritmo sería el 13?
1-13 = 12
24-13 = 11
25-13 = 12
26-13 = 13

Total: 48


Pero a ojo yo veo valores más óptimos, como 25:
1-25 = 24
24-25 = 1
25-25 = 0
26-25 = 1

Total: 26


Es un problema complejo [fumando]
Puedes ordenarlos, y hacer la mediana del otal, luego las medianas de las partes etc... hasta el punto que tu consideres que la compresion es adecuada.

salu2

PD: Quiza mejor dividir por bloques y hacer la media de cada bloque. :-?
Ashdown está baneado por "faltas de respeto"
Hazte el histograma, divide los colores rangos de 256 masas iguales y para cada rango de colores busca el centro de masas para definir el color.
Ashdown escribió:Hazte el histograma, divide los colores rangos de 256 masas iguales y para cada rango de colores busca el centro de masas para definir el color.


Pero eso solo valdria cuando quieres un solo valor.
Para eso se utilizan algoritmos de clustering, que hay a patadas. La idea es representar los colores de la imagen en una matriz 3D (con las componentes RGB de los susodichos) y a partir de ahí aplicar un algoritmo de clustering que básicamente forma grupos (en tu caso 256).

http://en.wikipedia.org/wiki/Color_quantization

Seguramente puedas mirar el código de programas tipo imagemagick, aunque si quieres ir a lo fácil:
http://scikit-learn.org/stable/auto_exa ... ation.html

Y más fácil todavía:
http://stackoverflow.com/questions/1065 ... e-with-pil

Si lo quieres hacer por tu cuenta, generas la matriz, y luego aplicas por ejemplo KMeans:
http://es.wikipedia.org/wiki/K-means

Donde como distancia entre puntos puedes usar perfectamente la distancia euclídea, aunque hay otros métodos.
6 respuestas
Archivado
Volver a Miscelánea