viernes, 29 de octubre de 2010

El problema de los puntos más cercanos

Ahora que estoy con el proyecto todo el día, estoy redescubriendo problemas de cuando estaba en la carrera. El caso es que en uno de los pasos de la implementación, necesitaba obtener los dos puntos más cercanos.

El problema de los puntos más cercanos, es un problema geométrico, en el que dado n puntos (en mi caso en 2D, es decir en un plano), quiero encontrar un par de puntos cuya distancia entre ellos sea la menor.

Inicialmente pensé, uy que problema más fácil, con dos bucles anidados resuelvo el problema:


int p1, p2;
double dist, dist_min = 100000000;

for (int i = 0; i < num_puntos; i++){

    for (int i = 0; i < num_puntos; i++){

        if (i != j){
            dist = sqrt((puntos[i].X - puntos[j].X)^2 + (puntos[i].Y - puntos[j].Y)^2);

            if (dist < dist_min){

                p1 = i;
                p2 = j;
                dist = dist_min;
            }
        }
    }
}



Este caso serie por la fuerza bruta, sin pensar en ningún tipo de eficiencia ni nada por el estilo, Por lo que si tienes que repetir esta búsqueda muchas veces, el programa puede tirarse un ratillo en acabar ... Y ya que estamos os hablo de eficiencia. En el caso de la fuerza bruta, la eficiencia sería de O(n2), donde n es el número de puntos.

Hay varias formas de mejorar esta eficiencia, y resolver el problema en un tiempo menor:

  • Usar un algorimo divide y vencerás.Donde se consiguie una eficiencia de O(n log2n)
  • Usar programación dinámica y crear una serie de estructuras de datos para facilitar el problema. En este caso se podría llegar a alcanzar una eficiencia de O(log n)
En mi caso he implementado la primera opción. El algoritmo divide y vencerás realizará lo siguiente:
  1. Ordenamos los puntos según su componente X
  2. El caso base será cuando queden 2 ó 3 puntos, en ese caso calcular la distancia mínima.
  3. Si el número de puntos es mayor, calcular la distancia mínima como el mínimo entra la distancia en el lado derecho e izquierdo.
  4. Además, tenemos que tener en cuenta los puntos cerca de la zona de división, en este caso se calcularán los puntos que estén a menos de dist_min de la línea L. Esta nueva lista de puntos se ordena con respecto a la componente Y, y obtenemos la distancia mínima. Si esta es menor que la distancia mínimal actual se modifica el valor.
No sé si está muy claro el ejemplo pero de todas formas os dejo el trozo de código (en c++) que he implementado.


punto calcular_distancia_minima(int ini, int fin){
    punto p1, p2, p, paux;
    double dist1, dist2, dist3;

    if (fin - ini + 1 > 3){
        p1 = calcular_distancia_minima(ini, ini + (fin - ini + 1)/2 - 1);
        p2 = calcular_distancia_minima(ini + (fin - ini + 1)/2, fin);

        if (p1.get_peso() < p2.get_peso())

            p = p1;
        else
            p = p2;

        vector c1;

        for (int i = ini; i <= fin; i++){

            if (puntos[i].X > (puntos[ini + (fin - ini + 1)/2].X - p.distancia)){
                paux.X = puntos[i].X;
                paux.Y = puntos[i].Y;
                paux.posicion = i;
                c1.aniadir(paux);
            }

            else {

                if (puntos[i].X < (puntos[ini + (fin - ini + 1)/2].X + p.distancia)){

                    paux.X = puntos[i].X;
                    paux.Y = puntos[i].Y;
                    paux.posicion = i;
                    c1.aniadir(paux);
                }
            }
        }

        c1.mergesortY(0, c1.tamanio()-1);

        double dist;
        int j;

        for (int i = 0; i < c1.tamanio() - 1; i++){

            j = i + 1;

            while ((j < c1.tamanio()) && (c1[j].Y - c1[i].Y < p.distancia)){                 dist = sqrt((c1[i].X - c1[j].X)^2 + (c1[i].Y - c1[j].Y)^2);

                if (dist < p.distancia){

                    p.X = c1[i].posicion;
                    p.Y = c1[j].posicion;
                    p.distancia = dist;
                }

                j++;
            }
        }
    }

    else {

        if (fin - ini + 1 == 2){
            p.X = ini;
            p.Y = fin;
            p.distancia = sqrt((puntos[ini].X - puntos[fin].X)^2 + (puntos[ini].Y - puntos[fin].Y)^2);
        }

        else{
            dist1 = sqrt((puntos[ini].X - puntos[fin].X)^2 + (puntos[ini].Y - puntos[fin].Y)^2);
            dist2 = sqrt((puntos[ini].X - puntos[ini + 1].X)^2 + (puntos[ini].Y - puntos[ini + 1].Y)^2);
            dist3 = sqrt((puntos[ini + 1].X - puntos[fin].X)^2 + (puntos[ini + 1].Y - puntos[fin].Y)^2);

            if (dist1 <= dist2 && dist1 <= dist3){

                p.X = ini;
                p.Y = fin;
                p.distancia = dist1;
            }

            else{

                if (dist2 <= dist1 && dist2 <= dist3){

                    p.X = ini;
                    p.Y = ini + 1;
                    p.distancia = dist2;
                }

                else{
                    p.X = ini + 1;
                    p.Y = fin;
                    p.distancia = dist3;
                }
            }
        }
    }

    return p;
}


Programa main que llama a la función de calcular distancia:


// creamos un vector de puntos
vector puntos(2000);
puntos.inicializar();

int main(){
    puntos.mergesortX(0, puntos.tamanio() - 1);
    punto p_distancia = calcular_distancia_minima(0, puntos.tamanio() - 1);
}


Fuentes:
Closest Pair of Points Problem - Wikipedia
Closest Pair Problem - Subhash Suri
losest Pair of Points - Rahul Gokhale

domingo, 24 de octubre de 2010

De camino para el negro

Este sábado hubo en el gimnasio una especie de jornadas de puertas abiertas. Después de echar un rato por la mañana por allí, sobre las 12 empezaron los exámenes de karate. Se examinaron un par de blancos, un par de amarillos y Carlos, que ya es marrón :D.

Yo como me voy a examinar de cinturón negro pues hice una especie de prueba, es decir, lo enseñé para ver como iba la cosa, y parece que no muy mal.







En el vídeo se pueden ver varios fallos, las piernas están un poco reguleras, quizás porque no había calentado ni nada, y lo peor es que iba deprisa, y no dejo que se vean las técnicas bien. Todavía tengo 1 mes y medio para practicarlo pero hay que mejorar un poco más para que en Diciembre salga lo mejor posible ^^.

Y bueno también dejo el de Carlos, que le salió estupendamente :D




lunes, 18 de octubre de 2010

Binarización de imágenes

La primera fase de mi proyecto, es binarizar las imágenes para facilitar el procesamiento posterior. Esto lo tengo implementado desde hace bastante, pero en su momento cuando busqué me costó encontrar la mejor opción.

Binarizar una imagen es cambiar todos sus colores en sólo dos, dependiendo de un umbral dado. Por ejemplo si tenemos una imagen en escala de grises y queremos que sea blanco y negro, lo que hacemos es escoger un valor de gris que será el umbral. Dentro de la imagen todos los valores menores que el umbral serán negro y los mayores blanco.


Como se puede observar el algoritmo es bastante sencillo, el problema aquí sería escoger el valor del umbral, de tal manera que la imagen no sea totalmente blanco o totalmente negra, sino que se distingan las formas.
La mejor opción sería que este umbral se escogiera según los valores de la imagen, de tal manera que el valor elegido no dependa del usuario sino de la propia imagen. Esto es lo que os voy a explicar.


El algoritmo para la selección del umbral lo que hace es iterativamente calcular un nuevo umbral, de tal manera que el bucle acabe cuando el nuevo umbral sea igual al calculado en la iteración anterior.


El valor inicial escogido como umbral será la media de todos los valores de la imagen.

A partir de aquí calculamos los nuevos valores del umbral, calculando la media de los valores de la imagen que están por encima y por debajo del umbral anterior.

Bueno creo que así es un poquito difícil entenderlo así que dejo el código que es más sencillo. En este caso se trabaja con imágenes en escala de grises:


//se calcula el valor inicial del umbral
double umbral0 = 0;

for (int i = 0; i < filas; i++){

    for (int j = 0; j < columnas; j++){
        umbral0 += imagen[i][j];
    }
}

umbral0 = umbral0 / (filas*columnas);

//vamos a calcular el valor real

double umbral1 = 0;
double umbral_der = 0;
double umbral_izq = 0;
int cont_izq = 0;
int cont_der = 0;

while( abs(umbral0 - umbral1) > 0){
    umbral1 = umbral0;
    umbral_der = 0;
    umbral_izq = 0;
    cont_izq = 0;
    cont_der = 0;

    for (int i = 0; i < filas; i ++){

        for (int j = 0; j < columnas; j++){ 

            if (imagen[i][j] < umbral1){
                umbral_izq += imagen[i][j];
                cont_izq ++;
            }

            else{
                umbral_fer += imagen[i][j];
                cont_der ++;
            }
        
    }

    umbral0 = (umbral_izq/cont_izq + umbral_der/cont_der)/2;
}


A continuación os muestro unos ejemplillos del resultado :D



viernes, 15 de octubre de 2010

Paseo por la nieve

El fin de semana habíamos planeado subir en el día del Pilar a la sierra, ya que era fiesta y no había ni trabajo ni clases ni nada de nada :D.

El plan en principio era subir al Veleta y al Mulhacen, y luego volver a casa por la noche. Pero la cosa se complicó porque este fin de semana nevó en la sierra, y hacer la paliza de los dos picos con la nieve no parecía muy sensato, así que lo acortamos a intentar subir al Veleta y jugar con la nieve :P.

El grupo de aventureros estaba formado por Carlos, mi hermano Juanga, René, Ali y yo :). Llegamos tempranito arriba, sobre las 10 y algo, y la verdad es que la principio nos cundió bastante, o eso me pareció a mi.


Visitamos el observatorio antiguo, para que lo viera mi hermano, y de allí a la Virgen de las Nieves. Por esa zona todavía no había nieve. Pero fue subir el primer repecho y encontrarnos manchas grandes de nieve.






Seguimos campo a través durante un rato, hasta que empezó a haber nieve abundante. Y nos separamos mi hermano que quería subir hasta arriba, fue solo acortando por los repechillos. El resto seguimos por la carretera, que la pendiente era mucho menor y se podía ir mucho más a gusto, sin ahogarnos ni nada (porque allí arriba hay menos concentración de oxígeno :P).





La verdad es que nos cundió porque llegamos hasta la zona donde sólo había nieve y no se veía ni la carretera ni nada.

Por el camino hicimos el tonto, y me refiero a jugar con la nieve, pararnos n veces para ver cosas. Jugar con los chuzos, ver las plantas heladas, hacer ángeles en la nieve y cosas así xD.








El caso es que para lo que nos paramos y to eso, llegamos bastante lejos, al menos Carlos y yo, y más que ninguno mi hermano que coronó el pico :P.

La cosa fue así, subimos con René y Ali hasta que ya no podíamos más, es decir, hasta que ya no pude casi levantar la pierna para andar, porque me lesioné en un entrenamiento de karate, y hasta que Ali dijo que tenía ya mucho frío. Como quedamos con mi hermano en que íbamos a encontrarnos arriba, fuimos Carlos y yo a buscarlo, pero yo me quedé en mitad ... Carlos empezó a subir lo que quedaba, mientras que mi hermano bajaba ... así que a grito pelao conseguimos que Carlos nos oyera y bajó. Lo malo del asunto que empezaron a atravesarnos nubes, y no se veía nada de nada .... De hecho, al principio pensaba que mi hermano era un poste xD.






Nos reunimos todos y empezamos a bajar. Esta vez campo a través y pasando de la carretera, que hacía muchísimo frío y todos queríamos llegar al coche. Paramos sobre las 3 a comer, pero para las 4 o así ya estábamos en el coche.

La verdad la aventura estubo chula, pero fue una pena no poder llegar arriba, aunque la verdad tampoco habríamos visto nada por culpa de las nubes ... Parecía que éramos la comunidad del anillo e íbamos por las montañas esas que salían en la película xD.

En el coche, se durmieron todos, menos yo que era la que conducía y a las 5 llegamos a Granada para poder descansar de la paliza ^^.

Esta excursión fue muy diferente a la del año pasado, que casualmente hicimos en las mismas fechas. La diferencia principal fue la nieve, que hizo que todo fuera diferente ...

sábado, 2 de octubre de 2010

Cambio de look

Pues como veis el cambio de look no me lo he hecho yo, sino que es para el blog :D. Estaba cansada de tanto azul, y no es que este no tenga, pero el fondo blanco y las letras negras se agradecen la verdad ^^.

Espero que os guste a vosotros también :).

Dejo una imagen del antiguo para recordar como era xD