17 septiembre 2016

Ejemplo simple de Lista Ligads (Linked List)

El objetivo de este post es dar una explicación lo más simple que me sea posible de qué es una Lista Ligada o Linked List y cómo crear una. La explicación e implementación de la Lista Ligada va a ser en C y C++ explicando las diferencias entre la implementación en cada uno de los lenguajes.

Una Lista Ligada (o lista enlazada) es tipo de estructura de datos y se utiliza para almacenar información. Una Lista Ligada está compuesta por dos partes principales, los datos y un apuntador del mismo tipo de la estructura. Una representación visual se muestra a continuación y le vamos a llamar "Nodo":

En nuestro nodo tenemos que "Datos" contiene el tipo de dato que queremos almacenar en nuestra lista ligada, por ejemplo un entero, un doble, un caracter, etc. y "Siguiente" es un apuntador a otro "Nodo" del mismo tipo. La definición en C y C++ se puede hacer mediante una estructura (en C++ también se puede crear con una clase):

// En C
struct nodo
{
 int dato;
 struct nodo *siguiente;
};

// En C++
struct nodo
{
 int dato;
 nodo *siguiente;
};

Y podemos representar a una lista ligada de manera gráfica como se muestra a continuación:
Primero se crea un nodo y se inicializa apuntando a una dirección nula.

struct nodo* A = NULL; // En C

nodo* A = NULL; // En C++

Y después tenemos que alojar en memoria el nodo que hemos creado, esto lo hacemos mediante "malloc" en C y con "new" en C++:
A = (struct nodo*)malloc(sizeof(struct nodo)); // En C

A = new nodo; // En C++

De esta manera ya tenemos creado un nodo y de esta misma manera se pueden crear varios nodos y enlazarlos mediante sus apuntadores y direcciones. A continuación se explica mediante la implementación en C:

#include
#include

struct nodo
{
 int dato;
 struct nodo *siguiente;
};

// En este ejemplo vamos a crear una lista ligada de tres nodos
int main()
{
 struct nodo* A = NULL;
 struct nodo* B = NULL;
 struct nodo* C = NULL;
 // Alojamos los tres nodos en memoria
 A = (struct nodo*)malloc(sizeof(struct nodo));
 B = (struct nodo*)malloc(sizeof(struct nodo));
 C = (struct nodo*)malloc(sizeof(struct nodo));

 A->dato = 100; //le asignamos un valor a "dato" del primer nodo
 A->siguiente = B; // Ligamos el apuntador "siguiente" al nodo "B"

 B->dato = 200; //le asignamos un valor al "dato" del segundo nodo
 B->siguiente = C; // Ligamos el apuntador "siguiente" al nodo "C"
 C->dato = 300; //le asignamos un valor al "dato" del tercer nodo
 C->siguiente = NULL; // Asignamos el apuntador "siguiente" a Null
                     // para indicar que es el final de la lista    
 return 0;
}

En el ejemplo anterior podemos observar que solamente necesitamos la saber la información de "A" para acceder a los demás elementos de nuestra lista.

Para demostrar esto, podemos crear una función que recibe como parámetro el primer
nodo de nuestra lista ligada e imprime en la consola el "dato" guardado en cada uno de los elementos de la lista.
La implementación completa sería:

#include
#include

struct nodo
{
 int dato;
 struct nodo *siguiente;
};

// Funcion que imprime en pantalla todos los datos de la lista a partir
// del primer elemento de la lista
void imprimir_lista(struct nodo *n)
{
 while (n != NULL)
 {
    printf(" %d ", n->dato);
    n = n->siguiente;
 }
}

// En este ejemplo vamos a crear una lista ligada de tres nodos
int main()
{
 struct nodo* A = NULL;
 struct nodo* B = NULL;
 struct nodo* C = NULL;

 // Alojamos los tres nodos en memoria
 A = (struct nodo*)malloc(sizeof(struct nodo));
 B = (struct nodo*)malloc(sizeof(struct nodo));
 C = (struct nodo*)malloc(sizeof(struct nodo));

 A->dato = 100; //le asignamos un valor a "dato" del primer nodo
 A->siguiente = B; // Ligamos el apuntador "siguiente" al nodo "B"

 B->dato = 200; //le asignamos un valor al "dato" del segundo nodo
 B->siguiente = C; // Ligamos el apuntador "siguiente" al nodo "C"

 C->dato = 300; //le asignamos un valor al "dato" del tercer nodo
 C->siguiente = NULL; // Asignamos el apuntador "siguiente" a Null
                     // para indicar que es el final de la lista    
 imprimir_lista(A);

 return 0;
}

La implementación de la lista anterior en C++ sería como se muestra a continuación:

#include
struct nodo
{
 int dato;
 nodo *siguiente;
};


// Funcion que imprime en pantalla todos los datos de la lista a partir
// del primer elemento de la lista
void imprimir_lista(struct nodo *n)
{
 while (n != NULL)
 {
    cout << n->dato << endl;
    n = n->siguiente;
 }
}

// En este ejemplo vamos a crear una lista ligada de tres nodos
int main()
{
 nodo* A = NULL;
 nodo* B = NULL;
 nodo* C = NULL;

 // Alojamos los tres nodos en memoria
 A = new nodo;
 B = new nodo;
 C = new nodo;

 A->dato = 100; //le asignamos un valor a "dato" del primer nodo
 A->siguiente = B; // Ligamos el apuntador "siguiente" al nodo "B"
  
 B->dato = 200; //le asignamos un valor al "dato" del segundo nodo
 B->siguiente = C; // Ligamos el apuntador "siguiente" al nodo "C"

 C->dato = 300; //le asignamos un valor al "dato" del tercer nodo
 C->siguiente = NULL; // Asignamos el apuntador "siguiente" a Null
                     // para indicar que es el final de la lista    

 imprimir_lista(A);
 return 0;
}

Y gráficamente podemos representar la lista creada de la siguiente manera:

20 agosto 2016

Ya en serio, ¿Qué es el Internet de las cosas?

En el mundo del Internet de las Cosas (IoT de hoy en adelante) el objetivo es tener una red de dispositivos físicos y virtuales interconectados intercambiando información o como lo define el Internet of Things Global Standards Initiative (ITU), es la infraestructura global para la sociedad de la información.

Nos dice el IOTAP que hay tres olas: la primera el Internet de escritorio, la siguiente el Internet móvil (si los estoy viendo a ustedes smartphones y tablets) y la tercera el Internet de productos tecnológicos y de consumo por ejemplo refrigeradores, TVs, relojes, sistemas de riego automatizados, automóviles, etc.

Así es que en palabras simples, ¿Que es el Internet de las Cosas?.
Es la red de "cosas" (duh!), si cualquier cosa que se pueda imaginar que le puedan adaptar una "computadora" y que estén conectadas entre sí y que intercambian información. Pero para poder estar conectadas entre si, se necesitan protocolos y estándares de colaboración esto quiere decir ¿Cómo están conectados entre si?, un par de ejemplos pueden ser ZigBee, BLE o WiFi Direct sólo por mencionar algunos. Y se necesitan sensores en cada dispositivo o "cosa" para convertir el ambiente o lo que estén detectando o midiendo en datos y así transmitirlos a esa entidad tan misteriosa llamada "la nube".

Ahora bien algunas personas se preguntarán: ¿Por qué? y ¿Para qué? ...

La información, ergo los datos es el nuevo oro.

18 agosto 2016

Nuevo contenido del blog

Voy a comenzar a escribir nuevamente en este blog.
Inicialmente escribía sobre temas relacionados con el procesamiento digital de imágenes pero ahora además de esto empezaré a escribir sobre sistemas embebidos, sistemas operativos de tiempo real, programación desde varios enfoques (embebidos, programación en la nube, sistemas distribuidos, etc.), automóviles autónomos, sensores inteligentes y cualquier cosa que me parezca interesante.

Vaya vaya, parece que voy a escribir sobre el Internet de las cosas o Internet of Things (IoT).

Let's see how it goes.

28 julio 2011

Algoritmo de detección de iluminación defectuosa en indicadores de paneles de instrumentación – Parte I (Teoría)

 

El Presente proyecto fue realizado en Mayo del 2009 como proyecto final para una materia de Procesamiento Digital de Imágenes en la Maestría en Ciencias en Ingeniería Eléctrica en la Universidad Autónoma de Ciudad Juárez (UACJ).

 

Definición del Problema

En una empresa donde se manufacturan componentes electrónicos para la industria de la transportación se tiene un indicador analógico usado en camiones pesados y casas rodantes. Este indicador cuenta con iluminación de fondo, como es común en los vehículos automotrices para poder leer el indicador en condiciones de poca luz.

La iluminación esta dada por tres diodos emisores de luz (LED: Light Emisor Diode) ensamblados en la tablilla electrónica (PCB: Printed Circuit Board), la luz se distribuye por medio de un reflector plástico y se proyecta en la pantalla que contiene la graduación para la que esta diseñado. En la figura 1 se muestra un bosquejo de la posición de los LEDs en el objeto bajo prueba, aquí se muestra sin la pantalla para poder mostrar la localización de los emisores de luz. En la figura 2 se muestra una vista lateral para indicar de manera general la construcción del objeto bajo prueba en la parte de iluminación.

clip_image001

Figura 1. Vista superior del objeto bajo prueba

clip_image002

Figura 2. Vista lateral del objeto bajo prueba

El problema se presenta cuando uno o más de los indicadores no encienden por alguna razón, esto es algo común en una ambiente de producción en serie, es por eso que se cuenta con un equipo de prueba funcional, el cual tiene la necesidad de detectar este tipo de defectos. Por ejemplo un objeto defectuoso es cuando uno de los Led mostrados en la figura 1 no prende o no esta presente. No es una tarea trivial detectarlos en con un sistema de visión, debido que el objeto bajo prueba tiene la pantalla que sirve para difuminar la luz junto con el reflector y no es fácil determinar cuales son las características necesarias para discriminar un objeto bueno de uno defectuoso.

Desarrollo.

Se cuenta actualmente en la línea de producción con un equipo de prueba funcional, con un sistema de visión, con el cual se ejercita el indicador tal y como si estuviera instalado en el vehiculo y se verifica que sea funcional. El objetivo del presente proyecto es para agregar la funcionalidad de que revise cuando uno de los emisores de luz esta faltante o no enciende.

El equipo consta de una computadora personal para adquirir la imagen, hacer el procesamiento y controlar los instrumentos del equipo. Cuenta con una cámara industrial de 1.3 megapíxeles con interfase USB. El objeto bajo prueba y la cámara se encuentran en un gabinete cerrado para minimizar el efecto de la iluminación a causa de la variación en la iluminación externa. A continuación se presenta en la figura 3 un dibujo básico de los componentes del sistema de visión. En este no se incluye todo lo relacionado con el control del mecanismo y la alimentación del objeto bajo prueba.

clip_image003

Figura 3. Diagrama básico del sistema de visión

En la figuras 4 y 5 se muestran ejemplos de objetos reales tomados con el sistema de visión descrito en el párrafo anterior. Se muestran ejemplos de dos tipos de indicadores, los cuales podemos separar en dos tipos, unos con fondo blanco y otros con fondo negro. Al ser diferentes los fondos el tipos de características en cada imagen es totalmente diferente, es uno de los objetivos de este trabajo el definir características en común para ser usadas como límites de pasa o falla.

En la figura 4 se muestran los indicadores con fondo blanco, la primera imagen muestra como se ve cuando una pieza esta correcta y los incisos restantes muestran los tipos de casos cuando faltan los emisores de luz del 1 al 3. En la figura 5 se muestran los mismos tipos de ejemplos pero en este caso para los indicadores con fondo negro.

Para realizar el procesamiento de las imágenes se usará el software MATLAB versión 7.0.0.19920 (R14) y el Toolkit de procesamiento digital de imágenes. El formato de la imagen a utilizar en este ejemplo es el formato PGM[1] (Portable GrayMap). Al leer la imagen con MATLAB se obtiene una matriz bidimensional de tipo uint8 y las dimensiones son definidas por el tamaño de la imagen, ya que cada píxel es representado por un byte de la matriz, con valores de 0 a 255 en escala de grises.

clip_image005

Figura 4.Ejemplo de indicadores con fondo blanco

a) LEDs correctos b) LED 1 Defectuoso c) LED 2 Defectuoso d) LED 3 Defectuoso

clip_image007

Figura 5. Ejemplo de indicadores con fondo negro

a) LEDs correctos b) LED 1 Defectuoso c) LED 2 Defectuoso d) LED 3 Defectuoso

Se utilizó la siguiente metodología para resolver el problema. Para poder resaltar las características de la imagen, se hicieron pruebas con varias técnicas de mejoramiento de imagen y también se le aplicaron diferentes técnicas de segmentación para resaltar dichas características que nos ayuden a determinar un parámetro confiable de segregación.

El método de extracción de bits se aplicó a las imágenes con el fin de segmentar la imagen y obtener una imagen binarizada como resultado. Anil K. Jain[2] explica la extracción de bits en una imagen y define al píxel u de la siguiente manera:

clip_image009

Y se requiere que nuestro píxel resultado v de la extracción de bit sea:

clip_image011

El autor define kn como se muestra a continuación:

clip_image013

En donde:

clip_image015

  • u, es el valor del píxel al que le vamos a extraer el bit
  • B, es el número de bits usado para representar un píxel
  • n, es el bit que queremos extraer de cada píxel, B es el menos significativo y 1 es el más significativo
  • L, es en nivel máximo que puede tener nuestra imagen

A continuación se muestra el código de MATLAB para implementar la extracción de bits:

function x = BitExtraction(myImagen, B, n ,L)

myImagenNueva = myImagen;

[rows cols] = size(myImagen);

for I = 1 : rows

for j = 1 : cols

u = double(myImagen(I,j));

iEne = floor(u/2^(B-n));

iEneMenosUno = floor(u/2^(B-(n-1)));

BitExtraido = iEne – (2*iEneMenosUno);

if BitExtraido == 1

BitExtraido = L;

else

BitExtraido = 0;

end

myImagenNueva(I,j) = BitExtraido;

end

end

x = myImagenNueva;

Código 1. Función en MATLAB para realizar extracción de bits a una imagen PGM

En las siguientes figuras se observan ejemplos de extracción del bit más significativo aplicados a un indicador no defectuoso y los casos de indicadores defectuosos.

clip_image017clip_image019

Figura 6. Ejemplo de extracción del bit más significativo del inciso a) y b) de la figura 4

clip_image021clip_image023

Figura 7. Ejemplo de extracción del bit más significativo del inciso c) y d) de la figura 4

clip_image025clip_image027

Figura 8. Ejemplo de extracción del bit más significativo del inciso a) y b) de la figura 5

clip_image029clip_image031

Figura 9. Ejemplo de extracción del bit más significativo del inciso c) y d) de la figura 5

Las figuras 6 y 7 nos muestran las imágenes con el bit más significativo extraído de la figura 4, éstas son para el caso con los indicadores con fondo blanco. Las figuras 8 y 9 son los equivalentes de la figura 5 y son para el caso con indicadores con fondo negro.

Como se puede observar en las imágenes anteriores al aplicarles el método de extracción de bits, la falta de luz debido al componente emisor de luz faltante se acentúa resaltando dicha característica en las imágenes. También se puede apreciar que la diferencia se ve marcada en una circunferencia hacia la orilla del perímetro del indicador. Para obtener una imagen con que resalte de una manera mas eficiente las características se puede enmascarar la imagen y extraer solamente la región de interés para ser analizada posteriormente y en base a eso decidir si el objeto bajo prueba es defectuoso o no.

El siguiente código en MATLAB muestra la función usada para extraer la región de interés en este caso.

Function imMasked = maskDonnutRegion(myImage, CentX, CentY, Rinf, Rsup)

h=CentX; k=CentY;

N=1024; t=(0:N)*2*pi/N;

x = Rsup*cos(t)+h;

y = Rsup*sin(t)+k;

BW = roipoly(myImage,x,y);

mask1 = uint8(BW); t=(0:N)*2*pi/N;

x = Rinf*cos(t)+h; y = Rinf*sin(t)+k;

BW = roipoly(myImage,x,y);

mask2 = uint8(~BW);

imMasked = uint8(myImage).*mask1.*mask2;

Código 2. Función en MATLAB para realizar la selección de la región de interés

En el código anterior se usa la función roipoly[3] incluida en MATLAB y se usa para seleccionar una región poligonal de interés. Para este ejemplo el polígono se define de manera de círculo, y se usan dos círculos para definir el perímetro superior y el perímetro inferior en el cual se va a enmascarar la imagen.

A continuación se muestra los ejemplos de las imágenes resultado de la extracción del bit más significativo.

clip_image033clip_image035

Figura 10. Ejemplo de selección de región de interés del ejemplo de la figura 6

clip_image037clip_image039

Figura 11. Ejemplo de selección de región de interés del ejemplo de la figura 7

clip_image041clip_image043

Figura 12. Ejemplo de selección de región de interés del ejemplo de la figura 8

clip_image045clip_image047

Figura 13. Ejemplo de selección de región de interés del ejemplo de la figura 9

Como se puede apreciar en las imágenes anteriores se observa que la imagen resultante muestra cambios significativos entre las imágenes que no presentan defectos (primera imagen de las figuras 10 y 12) y las imágenes defectuosas.

A las imágenes resultantes se les aplicaron dos técnicas de medición estadísticas para analizar los resultados y ver si se pueden definir los límites para determinar si la imagen es buena o mala.

Una de las mediciones usadas es la media, la cual calcula el promedio de los valores de la imagen. La función usada es mean, se representa de la siguiente manera.

clip_image048

También se calculó la desviación estándar de las imágenes procesadas. La desviación estándar se representa de la siguiente manera. La función usada es std[4].

clip_image049

Una tercera técnica usada es la entropía, la función usada es wentropy[5], ésta función es usada para criterios de selección debido a que describe propiedades relacionadas con la información de una señal dada, en este caso una imagen en escala de grises. La definición de la función usada esta dada por:

clip_image050

clip_image051

clip_image052


[1] http://netpbm.sourceforge.net/doc/pgm.html

[2] Jain, Anil K. Fundamentals of Digital Image Processing, Prentice Hall, 1989, USA

[3] Ver ayuda de MATLAB: help roipoly

[4] Ver ayuda de MATLAB: mean y std.

[5] Ver ayuda de MATLAB: doc wentropy. Esta función esta incluida en el toolbox de wavelets.

This is I

Blog dedicado a escribir sobre Sistemas Embebidos y el Internet de las Cosas o IoT que le llaman.