martes, 31 de julio de 2012

Punteros en C++ - Parte II: Introducción

En el post anterior Punteros en C++ - Parte I: Introducción, expliqué lo más básico sobre punteros: su definición y su significado. Sin embargo, quedó pendiente explicar la pregunta más importante acerca de su existencia: Porqué querríamos almacenar direcciones de memoria en variables? La pregunta es totalmente válida, más aún con las complicaciones inherentes de usarlos. El objetivo de este post es responder la pregunta planteada anteriormente.

En el post anterior asumimos que la memoria era un conjunto de celdas en donde era posible almacenar información, lo cual es cierto, pero no del todo exacto. El sistema operativo segmenta la memoria cuando se inicia: una parte dedicada a los procesos del sistema operativo, otra para almacenar procesos de usuario, un segmento de memoria libre, etc. Nos vamos a enfocar en los dos últimos mencionados.
Cuando un programa se ejecuta, el sistema operativo le asigna una porción de memoria para que éste almacene su código máquina y los datos que usa. La parte de la memoria que un programa usa para los datos (es decir las celdas en donde se almacenan las variables) se llama Memoria Pila (o Stack). Se llama así porque es una estructura de tipo FIFO, en la que las asignaciones (y desasignaciones) de memoria se hacen siempre por el mismo extremo de la memoria.

La mala noticia es que el tamaño de la memoria pila de un programa no es tan grande como quisiéramos. Veamos el siguiente programa:

#include <iostream>
#include <cstdlib>

using namespace std;

int main(int argc, char* argv[]){
 
 //MB necesarios
 cout << (sizeof(double)*10000000)/(1024*1024) << endl;
 double A[10000000];
 return EXIT_SUCCESS;
}
En este programa, intentamos imprimir un mensaje con la cantidad de MB necesarios para almacenar un arreglo de 10 millones de double's. A continuación, creamos un arreglo A de double con 10 millones de elementos. Esto es aproximadamente 76MB de memoria necesaria (asumiendo que un double ocupa 8 bytes). Cuando ejecutamos el programa, el sistema operativo le asigna su memoria pila al proceso e intenta asignar una porción de memoria pila para A. El problema es que la memoria pila no puede crecer en tiempo de ejecución (y tampoco tiene 76MB disponibles!), por lo que nuestro programa termina intempestivamente con un stack overflow (o violación de segmento). Nota: el comportamiento de este programa puede cambiar, dependiendo del computador en el que se ejecuta. Yo lo ejecuté en un Core 2 Duo con 2GB de memoria.

Sin embargo, el comportamiento de nuestro programa está lejos de ser el que queremos. Tengo un computador con 2GB de memoria y no puedo ejecutar un programa que usa 76MB? Ok, no hay porqué desesperarnos, en realidad sí se puede, pero no así. La explicación para este fenómeno es que el sistema operativo limita la capacidad para cada proceso, porque sino entonces no podríamos ejecutar varios procesos a la vez compartiendo la memoria.

La buena noticia es que existe (gracias a Dios!) el segmento de memoria libre (Aleluya!). Más comúnmente conocido como Heap, éste segmento es una gran porción de memoria que el sistema operativo deja para el uso de quienes lo requieran. Además, así como esta porción de memoria es libre, entonces su comportamiento necesita ser dinámico para que los programas pidan más memoria cuando la necesiten y la liberen cuando ya no. Para mantener las cosas aún en regla, el sistema operativo administra el Heap, de manera que cuando un programa pide memoria libre, el sistema operativo busca si existe la cantidad de memoria que se requiere. Si existe, la reserva y le devuelve al programa la dirección de memoria en donde inicia la memoria reservada. Y Oh sorpresa!!! necesitamos almacenar esa dirección de memoria en algún lado, osea un puntero.

Dicho resumidamente, un puntero tiene que ser usado siempre que hacemos uso de la memoria libre, la cual nos permite usar mucha memoria a nuestro antojo (siempre bajo los límites de la memoria física, claro). Si no tuviéramos los punteros, no podríamos hacerlo y nuestros programas tendrían una capacidad limitada de memoria a usar.

Un inconveniente de usar la memoria libre, es que el programador es el responsable de solicitar memoria y de liberarla. En programas complejos, esto resulta en un verdadero dolor de cabeza para los principiantes, pero nada, que bastante práctica, no logre solucionar. Veamos el siguiente programa:

#include <iostream>
#include <cstdlib>

using namespace std;

int main(int argc, char* argv[]){
 
 //MB de memoria necesarios
 cout << (sizeof(double)*100000000)/(1024*1024) << endl;
 double* A = new double[100000000];
 /*Hacemos lo que tengamos que hacer con A*/
 delete[] A;
 return EXIT_SUCCESS;
}

En C++, el operador new se encarga de reservar memoria en la memoria libre. La cantidad de memoria solicitada está implícita en el tipo de dato que lo sucede. En el ejemplo,  solicitamos una cantidad de memoria para almacenar 100 millones de double's (ojo que solicitamos 10 veces más que en el programa anterior, equivalente a 762MB). La dirección de memoria en donde empieza la memoria reservada es retornada y se almacena en A, que es un puntero a double.  Finalmente, cuando nuestro programa va a terminar, liberamos la memoria reservada con delete.

Aunque el uso de la memoria dinámica y los punteros asociados es una alternativa que nos permite emplear mucha más memoria, su uso debe ser mesurado. Si tu programa, va a usar poca memoria, entonces dale prioridad al almacenamiento estático. El empleo de la memoria dinámica conlleva más procesamiento a nivel del sistema operativo (por el tema de mantener registro de la porciones de memoria ocupadas y libres ) y por lo tanto siempre añadirá cierto tiempo de procesamiento adicional. Por otro lado, si tu programa necesita memoria en tiempo de ejecución, la única alternativa es el empleo de memoria dinámica, por lo que en esos casos el uso de punteros puede ser la única alternativa.

Espero haber despejado algunas dudas acerca del uso de los punteros en C++, y si no, los siguientes posts pueden dar mejores luces acerca de su uso e importancia. En el siguiente post, hablaré de una útil aplicación de los punteros: estructuras de datos dinámicas.

Nota final: si deseas conocer más acerca del funcionamiento de la memoria en sistemas operativos modernos, recomiendo el estudio del Sistema Operativo Minix 3, cuyo código fuente (enteramente escrito en C y assembler) permite indagar a muy bajo nivel cómo se organiza todo dentro de nuestro computador. Además, el núcleo de Minix inspiró a Linus Torvalds a crear Linux :).

viernes, 20 de julio de 2012

Punteros en C++ - Parte I : Introducción

C++ es el lenguaje preferido de muchos programadores, debido a su versatilidad y potencia para expresar instrucciones a un computador. Sin embargo, uno de los principales problemas al aprender este lenguaje es la facilidad de incurrir en errores. Mas aún, si lo que queremos es usar de manera directa el modelo de memoria del lenguaje mediante el uso de punteros, vamos a tener muchísimos problemas.

En este post explicaré, de manera introductoria, cómo entender el manejo de memoria usando C++. La idea es lograr que hayan menos dolores de cabeza en el mundo :).

Voy a asumir en este post que conoces cómo compilar un código en C++, además de algunas características básicas como tipos de datos, funciones, etc. Empezaré la explicación con un código muy simple como se muestra a continuación:

#include <iostream>
#include <cstdlib>

using namespace std;

int main(int argc, char* argv[]){
 
 int var = 10;
 cout << var << endl;
 cout << &var << endl;
 
 return EXIT_SUCCESS;
}

En este código se presenta una función main clásica. En la línea 8 creamos una variable entera var que almacena un valor de 10.  Internamente lo que sucede es que cuando el programa se ejecute, el sistema operativo le va a asignar a nuestro programa un lugar en la memoria RAM para poder almacenar nuestra variable var. Imaginemos que la memoria RAM está compuesta por un conjunto de celdas en donde es posible almacenar información. Una posible configuración de la memoria después de crear la variable var se muestra en la siguiente figura:


El valor 10 se almacena en una celda que está en la dirección 0xbfc36158. Entonces, cada vez que usamos la variable var, internamente estamos usando esa celda de memoria asignada. Es por eso que la instrucción de la línea 9, toma el valor en la celda de memoria y lo imprime en pantalla. Un detalle importante es que en C++, uno puede saber cuál es la dirección de memoria en donde está almacenada una variable, para eso se emplea el operador &. Cuando uno aplica el operador & a una variable (como en la línea 10 del código de arriba), éste nos entrega la dirección de memoria en donde reside la variable. En el ejemplo, nuestro programa imprimirá en pantalla el valor de la variable y la dirección de memoria en donde está almacenada.

Y dónde están los punteros y cómo se relaciona a todo lo que hemos visto?
Pues, si podemos imprimir una dirección de memoria, entonces podemos almacenarla! Un puntero es "una variable que almacena una dirección de memoria". Así de simple! Veamos ahora el siguiente código:

#include <iostream>
#include <cstdlib>

using namespace std;

int main(int argc, char* argv[]){
 
 int var = 10;
 cout << var << endl;
 cout << &var << endl;
 
    int* p = &var;
 cout << p << endl;
 cout << &p << endl;
        
    return EXIT_SUCCESS;
}
Hemos añadido tres líneas de código al primer programa. En la línea 12, creamos el puntero p (usando la sintaxis <tipo-de-dato>*); osea una variable que va a almacenar una dirección de memoria. Hay que tener en cuenta que cuando se crea un puntero, hay que informar explícitamente acerca del tipo de dato que está almacenado en la dirección de memoria a almacenar. Por ejemplo, nuestro puntero p almacenará una dirección de memoria, en la cual se almacena un número entero (en este caso, el valor 10). El valor que le asignamos al puntero es la dirección de la variable var. La línea 13 imprime el valor almacenado en p (y por lo tanto, imprime lo mismo que la línea 10).

La pregunta es: Si un puntero es una variable, entonces está almacenada también en una celda de memoria, la cual a su vez también tiene una dirección? La respuesta es SI. Para graficar esto, veamos la siguiente figura:

Ahora la variable p (un puntero), posee una celda de memoria en donde está almacenando la dirección de la variable var, y por consiguiente tiene una dirección de memoria también. Para extraer la dirección de memoria de un puntero, usamos el operador &, como en la línea 14 del programa.

A estas alturas, resulta lógico pensar en la posibilidad de volver a almacenar la dirección del puntero p en otra variable. Una variable que almacena la dirección de memoria en donde se almacena un puntero, se le llama un puntero a un puntero (o mas comúnmente puntero doble). El siguiente código muestra cómo es posible hacer esto:

#include <iostream>
#include <cstdlib>

using namespace std;

int main(int argc, char* argv[]){
 
 int var = 10;
 cout << var << endl;
 cout << &var << endl;
 
    int* p = &var;
 cout << p << endl;
 cout << &p << endl;
        
    int** p2 = &p;
 cout << p2 << endl;
 cout << &p2 << endl;

    return EXIT_SUCCESS;
}
La línea 16 crea una variable en donde se va a almacenar la dirección de un puntero. La sintaxis usa ahora un doble asterisco para denotar que es un puntero doble. Y así uno podría crear cadenas de punteros las veces que queramos, aunque en la práctica no es realmente necesario el uso más allá de los punteros dobles (además de la complejidad que se añade a la comprensión del programa).

Algo interesante es que nuestra información también puede ser manipulada de manera indirecta usando los punteros. Veamos el siguiente código:
#include <iostream>
#include <cstdlib>

using namespace std;

int main(int argc, char* argv[]){
 
 int var = 10;
 cout << var << endl;
 cout << &var << endl;
 
    int* p = &var;
    *p = 12;
    cout << var << endl;

    return EXIT_SUCCESS;
}

En la línea 12, asignamos la dirección de la variable var a un puntero p. En la línea 13, usamos el puntero para cambiar el valor almacenado en la dirección de memoria que almacena el puntero (el operador * se usa para dereferenciar un puntero, osea tener acceso a la información de la dirección de memoria que mantiene el puntero). Finalmente, cuando volvemos a imprimir la variable var, vemos que su valor cambió, y lo hicimos indirectamente usando el puntero p.

Espero que este post haya sido de utilidad. En el siguiente post, explicaré las razones del uso de punteros y daré algunos consejos para su uso.

martes, 16 de agosto de 2011

Imágenes panorámicas

La fotografía digital está presente en el quehacer de la gente desde hace ya buen tiempo. La cámara digital ha facilitado la generación de cantidades gigantescas de imágenes almacenadas en repositorios, redes sociales, etc. Tanto ha sido el impacto de estos dispositivos en la vida cotidiana, que ahora se ha empezado a introducir muchas herramientas al vuelo para procesamiento de fotografías digitales (detección de rostros, eliminación de ojos rojos, maquetación, eliminación del efecto de movimiento, etc). Recientemente, una aplicación interesante permite tomar fotografías panorámicas, algo que no estaba disponible hasta hace un par de años. En esta entrada les muestro una aplicación que desarrollé para un curso de Visión Computacional que permite reconstruir una fotografía panorámica partiendo de un conjunto de imágenes.

La idea es que uno tome varias fotografías y el programa reconstruya la vista que componen todas las imágenes. En este caso, el método que detallo más adelante, sirve para imágenes en escala de grises con la condición de que las imágenes deben contener cierto nivel de superposición de la vista original. La solución está basada en el uso de características locales extraídas desde las imágenes.

Para empezar, tenemos un conjunto de imágenes (para el ejemplo, el pan de azúcar, Rio de Janeiro - Brasil):

Para hacer el método lo más general posible, nosotros asumimos que las imágenes no están en orden. Por lo que el primer paso es determinar cómo las imágenes estarán dispuestas en la reconstrucción final. 

Nosotros calculamos los puntos de interés y los descriptores SIFT de cada imagen. Luego, para cada par de imágenes, hallamos el número de puntos de interés que se corresponden entre sí. Este paso se realiza en varios procesos:
  • Para cada punto de interés de la primera imagen, hallamos su vecino más cercano en la colección de puntos de interés de la segunda imagen. En realidad, se analiza la proporción entre la distancia al primer vecino y al segundo vecino más cercano. Si la proporción entre estas distancias es mayor a 0.8, no se considera dicha correspondencia.
  • Escogemos aleatoriamente un conjunto de correspondencias. Luego, empleando el método de mínimos cuadrados, calculamos la matriz de transformación homogénea que minimice el error de localización entre los puntos de las correspondencias. Esta transformación es validada empleando el conjunto entero de correspondencias. Se considera un "inlier", los puntos cuya versión transformada no difiere en 3 píxeles de sus correspondientes.  Este proceso de realiza muchas veces para garantizar una convergencia adecuada. Comúnmente se le conoce a esta método como RANSAC.
  • Finalmente, nos quedamos con el conjunto de inliers de mayor número.
Con la información sobre las correspondencias, es posible determinar cómo deberían ir las imágenes. Por ejemplo, la imagen de más a la izquierda, sólo tendrá correspondencias hacia la derecha. De la misma forma, para la imagen de más a la derecha. Además, la relación de correspondencia puede representarse como un grafo dirigido, sobre el que es posible encontrar una ordenación topológica a partir del nodo más a la izquierda. Esta ordenación define el orden  de las imágenes en la composición final. 


Para la composición final, empleamos el conjunto de correspondencias previamente calculado. Dadas dos imágenes, sus correspondencias, y la transformación entre puntos correspondientes, creamos una imagen que sea capaz de albergar todos los píxeles de ambas imágenes. A continuación, la primera imagen es copiada en alguna posición fija de la imagen destino y la segunda imagen es transformada de acuerdo a la transformación hallada. Para componer adecuadamente ambas imágenes y evitar la generación de artefactos, nosotros creamos dos máscaras rectangulares de pesos lineales (del mismo tamaño que las imágenes), de manera que al centro de la máscara haya un 1 y a los extremos de la máscara hayan 0's. De esta forma, la composición se realiza haciendo un promedio ponderado de los valores de los píxeles conforme sus pesos en las máscaras.

El resultado final fue:




lunes, 11 de abril de 2011

Elecciones, democracia y el país del nunca jamás...

Parece increíble el shock que vienen causando los resultados de las elecciones presidenciales en el Perú. Medios de comunicación, usuarios de redes sociales, analistas políticos, políticos extranjeros y hasta un premio nobel opinan, en diferentes grados, las consecuencias de tener que elegir, en una ya casi segura segunda vuelta, entre Ollanta Humala y Keiko Fujimori.

Las disputas van y vienen y los agravios entre nosotros mismos, los peruanos, no se han hecho esperar. Los candidatos presidenciales que no pasarán a segunda vuelta empiezan a tirarse la pelota de porqué no renunciaron los otros perdedores cuando supieron que se venía la vorágine Humala-Fujimori. Y supongo que la respuesta más obvia y criolla sería: "Por la misma razón, por la que el que pedía las renuncias, tampoco quería renunciar". Particularmente, creo que es normal que los políticos se peleen, pues tienen intereses de por medio. Sin embargo, me ha parecido completamente inaudito que los peruanos de a pie, como tú o como yo, tengamos que insultarnos y agredirnos, cuando no somos capaces de reconocer que el pueblo ha "hablado". Y eso es democracia: el poder es del pueblo. 

Yo no he votado en esta oportunidad, pues me encuentro en el extranjero. Y si hubiera votado, definitivamente no hubiera votado por Humala ni por Keiko. Sin embargo, me sentí ofendido, como peruano, apreciar cómo se les llamaba imbéciles, idiotas, inconscientes a la gente que votó por Humala y Keiko. La razón por la que escribo este artículo es porque deseo establecer mi punto de vista sobre mi pena y mi sensación de ofensa.

Primero, la intolerancia que demuestran los que no están de acuerdo con los resultados y las broncas sin fin generadas a partir de ello, pone de manifiesto la gran zanja que divide a nuestra sociedad. Esa sociedad que busca siempre echarle la culpa a otro de los males del país (y los de uno mismo) y qué mejor que echarle la culpa al que está al otro lado de la zanja. Esa misma intolerancia que nos vuelve ciegos y que no nos permite ver que el país acaba de reclamar en la única forma en la que puede hacerlo. Esa intolerancia que no nos deja ver que los que están al otro lado de la zanja, pueden ser más que los de tu lado y que aquellas personas que, en alguna otra circunstancia, no tiene cabida en los intereses del país, acaban de decirnos: Nosotros también somos peruanos. 

Para los intolerantes que juzgan a quienes están decidiendo el futuro del país, les digo:

  • Hay un peruano en la sierra o en la selva que no siente el progreso, que no tiene acceso a una buena educación, que su único porvenir está en trabajar diariamente la tierra que le heredaron sus padres. Un peruano al que históricamente, le han ofrecido el oro y el moro, y que hasta el momento sólo le han dado indiferencia.
  • Hay un peruano durmiendo en los cerros, bajo esteras. Porque al no ver progreso en la sierra o la selva, emigra buscando el lugar en donde se sienta parte de esto que se llama país.
  • Hay un peruano trabajando en las calles, muriéndose de frío, que de lo único de lo cual se puede jactar al terminar su jornada es de la gran cantidad de indiferencia que le damos.
  • Hay un peruano, no necesariamente en la extrema pobreza, que ha asociado las palabras: modelo económico liberal, estabilidad económica, inversiones, con corrupción, sinvergüencería, disgregación social.
Los resultados de estas elecciones son una cachetada a nuestro fingido progreso. Aquel progreso que la gente que todos los días tiene que arréglarselas para comer, no siente. 

Pero es que los verdaderos imbéciles están en nuestra clase política. Los candidatos perdedores tenían planes de gobierno parecidos, todos iban a subir el sueldo mínimo: uno a 700, otro a 750, y el más demagogo a 850. Pero era la misma idea!!!! Sino que cada uno de ellos quería ser presidente. Cómo no puede la gente darse cuenta de la clase de candidatos "buenos" que teníamos. Si les importaba realmente el Perú, porque no co-gobernar? A verdad! Estamos en Perú: todos quieren su tajada. Menudos candidatos.

Por otro lado,  las propuestas que se debaten la presidencia han ido con un mensaje diferente, cuestionando las políticas de integración social y ahí es en donde han logrado obtener sus votos.  Los peruanos que describo arriba, se han visto seducidos una vez más por el mensaje esperanzador, por aquellos que les prometen igualdad. Y de paso por el que le promete facilismos. Pero es indudable, imagínense a quien lleva décadas olvidado, lo mínimo que va a querer es un reconocimiento a lo que hace. Una bolsa de arroz, un vaso de leche, 100 soles mensuales y tienes su democracia empeñada.

Mucha gente teme que el país retroceda, el problema es que para mucha gente, el país nunca avanzó. Ojalá nuestros 2 pasados gobiernos se hubieran puesto las pilas en ese sentido. Ahora, no nos estaríamos llamando imbéciles.

"Cuando miramos al otro lado de la zanja, hay poquitos! Deben estar escondidos, porque ahora sí sabemos que son muchos más que nosotros y acaban de decirnos que están pensando en poner un puente".