Juan Carlos Espinosa Ceniceros

jueves, 18 de abril de 2013

[Lab VC] Actividad 5: Detección de elipses

Para la actividad de laboratorio se debió programar el código para detección de círculos.

Los requisitos de la actividad son:

Identifica cada elipse/círculo individual
Rellénalo de un color aleatorio
Sigue marcando su centro con bolita & ID con etiqueta
Imprime un listado de los áreas de los círculos/elipses

En porcentaje de la imagen completa

Teoría

Para la detección de elipses se utilizó el método de cuerda-tangente, el procedimiento para aplicarlo se describe en la siguiente entrada:

http://juankenny.blogspot.mx/2013/04/vc-tarea-5-deteccion-de-elipses.html

Mejoras

Se mejoró el método para detectar ellipses, anteriormente hacía una búsqueda exhaustiva comparando todas las posibles combinaciones de pares de puntos para sacar los pixeles sujetos a votación y posteriormente ubicar el centro.

Ahora simplemente ordeno la lista de pixeles de los bordes por la coordenada Y, después hago una copia de la lista pero la ordeno al reves. Asi me quedan 2 listas con los pixeles ordenados en la coordenada Y pero una esta ordenada al reves.

Después, dado que tienen el mismo número de elementos, con un mismo ciclo recorro ambas listas tomando un punto de cada una, calculando las tangentes de los puntos y todo lo demás para obtener los votos.

Con éste cambio ahorro mucho tiempo de ejecución y además se mejoró un poco la precisión para hallar los centros, aunque todavía falta refinar más.

Ejemplo de detección con el nuevo método

Resultados de la actividad

Las imagenes utilizadas para las pruebas fueron las siguientes:

Original
Binarizada
Contornos

Los resultados de la detección y rellenado de pixeles fueron los siguientes:

Elipses con su área

Código

En el repositorio encuentran la implementación completa en código, la carpeta marcada como Tarea 6.

https://github.com/jcespinosa/vision_computacional

Dado que es el mismo código que antes, solo incluyo la nueva rutina para detectar elipses:

Fin de la actividad

martes, 16 de abril de 2013

[Lab RT] Actividad 7: Medidas de desempeño y métodos de generación de tráfico

La tarea de esta semana constitió en:

Investigar sobre los métodos de generación de tráfico en el simulador NS-2 o NS-3, cómo generarlo y cómo modificar sus propiedades.
Cómo se pueden monitorear las medidas de desempeño en la red simulada.

Seguimos utilizando NS-2, con algunas mejoras al generador de topologías de la entrada anterior.

Generación de tráfico

La generación de tráfico en NS-2 entra dentro de la clasificación Application Objects. Un Application Object puede ser de 2 tipos, una aplicación simulada o un generador de tráfico.

Lo que nos interesa son, justamente los generadores de tráfico.

Los objetos generadores de tráfico, generan tráfico de 4 tipos principales, y con una pequeña modificación, hasta 5 tipos diferentes, cada uno con sus propiedades y los cuales se describen a continuación.

Exponencial (Application/Traffic/Exponential)

Los objetos de tráfico exponencial, generan tráfico que puede "encenderse" o "apagarse" (comenzar y detenerse) por ciertos periodos de tiempo.

Durante los periodos de "encendido" los paquetes son generados en forma de ráfagas constantes. Durante los periodos de "apagado", pues ningún tipo de tráfico es generado.

Los periodos de encendido y apagado, y sus tiempos de duración, son tomados de acuerdo a una distribución exponencial.

Los parámetros de configuración de éste tipo de tráfico son:

PacketSize_ : El tamaño del paquete a generar, constante.
burst_time_ : Tiempo promedio para el estado "encendido" del tráfico.
idle_time_ : Tiempo promedio para el estado "apagado" del tráfico.
rate_ : Velocidad de transferencia durante los tiempos de "encendido".


set e [new Application/Traffic/Exponential]
$e set packetSize_ 210
$e set burst_time_ 500ms
$e set idle_time_ 500ms
$e set rate_ 100k

Poisson:

Configurando de forma especial el generador exponencial se puede obtener un generador que tome la forma de la distribución de Poisson.

Estableciendo la variable burst_time_ a cero y la variable rate_ a un valor demasiado alto se obtiene el resultado esperado.

Adicionalmente, el valor entre llegadas de paquetes es la suma de la tasa de transferencia (rate_) y el valor aleatorio correspondiente al parámetro idle_time_ . Para hacer el primero valor de la suma muy pequeño, el parámetro burst_time_ debe ser muy alto, de tal forma que el tiempo de transmisión sea despreciable comparado con los tiempos típicos de espera (idle_times).

Pareto (Application/Traffic/Pareto)

Genera tráfico con las mismas caracteristicas que el generador exponencial, la diferencia es que éste toma la forma de la distribución de Pareto.

Los parámetros de configuración son:

PacketSize_ : Tamaño constante de los paquetes generados.
burst_time_ : Tiempo promedio para el estado "encendido" del tráfico.
idle_time_ : Tiempo promedio para el estado "apagado" del tráfico.
rate_ : Velocidad de transferencia durante los tiempos de "encendido".
shape_ : Parámetro propio de la distribución.


set p [new Application/Traffic/Pareto]
$p set packetSize_ 210
$p set burst_time_ 500ms
$p set idle_time_ 500ms
$p set rate_ 200k
$p set shape_ 1.5

CBR (Application/Traffic/CBR)

El tipo de tráfico genera ráfagas constantes de paquetes a una velocidad constante, es útil para simular aplicaciones multimedia como stream de música o videos. Por lo general se utiliza bajo el protocolo UDP.

Los parámetros de configuración son:

PacketSize_ : El tamaño del paquete a enviar, constante.
rate_ : La tasa de transferencia.
interval_ : El intervalo de tiempo entre los paquetes.
random_ : Si se desea introducir ruido aleatorio en los tiempos de salida.
maxpkts_ : La cantidad máxima de paquetes a enviar, por ejemplo, en videostream, el tamaño del video a ver.

Los parámetros rate_ e interval_ son mutualmente excluyentes, es decir, en algunos scripts de puede configurar el intervalo en lugar de la tasa de transferencia o al revés para cualquier simulación algunos de los 2 parámetros debe ser especificado.


set cbr [new Application/Traffic/CBR]
$cbr set packetSize_ 48
$cbr set rate_ 64Kb
$cbr set random_ 1

Trace (Application/Traffic/Trace)

Los objetos de éste tipo son utilizados para generar tráfico a partir de un archivo de trazado.

Se debe adjuntar el archivo de trazado a este objeto, el cual especifica los datos del tráfico ya existentes.

Un archivo consiste en una serie de lineas con un formato y largo fijos. Cada línea o registro consiste en campos de 2*32 bit.

El primero indica el intervalo hasta el cual de podrá generar el siguiente paquete. El segundo indica el largo del siguiente paquete en bytes.

No hay parámetros de configuración para éste generador.

FTP over TCP (Application/FTP)

Como ya sabemos, se trata de tráfico que simula la transferencia de archivos bajo el modelo de cliente servidor.
Este tipo de tráfico es útil por ejemplo, para simular la descarga o subida de archivos, o para simular la transferencia de videos desde Youtube (desde que youtube utiliza TCP para la transferencia de videos.)

No hay parámetros de configuración para éste generador.

set ftp [new Application/FTP]
$ftp attachagent $tcp0

Telnet over TCP (Application/Telnet)
Con éste tipo de tráfico se pueden simular sesiones de línea de comandos, no generan paquetes de un tamaño muy grande pero son útiles para simular tráfico real.

No hay parámetros de configuración para éste generador.

set telnet [new Application/Telnet]
$telnet attach-agent $tcp0

Medidas de desempeño

Para analizar el rendimiento de nuestra red podemos analizar los archivos de salida de NS-2, estos archivos son los archivos de visualización en Network Animator (*.nam) y los archivos de trazas o trazado (*.tr)

Los archivos de trazas estan separados por espacios, y siguien el siguiente formato:

tipo de evento	tiempo	Nodo inicial	Nodo final	Tipo de tráfico	Tamaño del paquete
+,-,r,h,d	1.15	10	0	TCP,UDP	1000

Los archivos de nam tienen flags para separar los elementos utilizando el siguiente formato:

tipo de evento	tiempo	Nodo inicial	Nodo final	Tipo de tráfico	Tamaño del paquete
+,-,r,h,d	-t 1.15	-s 10	-d 0	-p TCP,UDP	-e 1000

Los tipos de eventos pueden ser:

+ : archivo en cola
- : paquete sacado de la cola
r : paquete recibido
h : paquete enrutado
d : paquete desechado (dropped)

Se pueden utilizar scripts de AWK que nos ayudan a leer dichos archivos y generar las estadísticas correspondientes de latencia, retraso, jitter y throughput.

Escribi un ejemplo de archivo para calcular el rendimiento de la red, los paquetes enviados y recibidos:

Prueba

Las mejoras al código de generación de topologías fue agregar redes un poco más reales, entonces ayudandome un poco con la libreria de python networkx pude generar redes en forma de grafos tipo small-world y scale-free

Solo se agregaron las siguientes lineas:

Después sigue la generación de tráfico, para ello implemente un módulo sencillo que lee un archivo que contiene el tráfico en la red con el siguiente formato:


n1,n2,1.0,4.0,tcp,ftp,0
n1,n2,1.0,4.0,tcp,tel,0
n1,n2,1.0,4.0,udp,cbr,700;1000
n1,n2,1.0,4.0,udp,exp,310;500;500;1000
n1,n2,1.0,4.0,udp,par,500;300;100;1000

Los elementos de cada línea del archivo son:

Nodo inicial
Nodo final
Tiempo de inicio del stream
Tiempo final del stream
Protocolo
Generador
Parámetros propios de cada generador (ver descripciones arriba)

Así, al leer el archivo se van generando las topologías y sus conexiones, después se genera el tráfico.
Es necesario conocer la topología para generar el tráfico, es decir, cuantos nodos son para introducir tráfico solo a conexiones existentes.

Cabe recordar que el script de python genera el script TCL de la simulación.

El método es un poco simple, pero cumple para generar el tráfico de distintos tipos, la función encargada de generar el tráfico es la siguiente:

En el siguiente video se puede ver como se programó el nodo 10 como "servidor" enviando tráfico UDP a los demás nodos, además se programo que el flujo de datos siguiera la distribución Exponencial y Pareto por lo que se puede ver como los nodos se conectan y desconectan repentinamente, siguiendo estas distribuciones. La topología es una malla que conecta 4 redes tipo scale-free.

Calculando el rendimiento:

Referencias

[VC] Tarea 5: Detección de elipses

Para esta actividad se debieron programar las rutinas para detectar elipses y círculos de diferentes tamaños en una imagen. Para ello se utilizó la Transformada de Hough y el método de la cuerda-tangente.

Teoría

Los pasos necesarios son:

Tomar la imagen original y aplicar detección de bordes, cuidar que los bordes sean lo suficientemente continuos.
Elegir las máscaras a aplicar, sigo trabajando con 2 máscaras de Sobel

$\begin{bmatrix}-1 & 0 & 1\\-2 & 0 & 2\\-1 & 0 & 1\end{bmatrix}$ $\begin{bmatrix} 1 & 2 & 1\\ 0 & 0 & 0\\ -1 & -2 & -1\end{bmatrix}$

Aplicar las máscaras utilizando convolución discreta (2D)

Aplicar por separado para obtener 2 gradientes Gx y Gy

Recorrer la lista de puntos de los bordes y elegir 2 puntos, aplicar alguna regla para evitar elegir dos puntos muy cercanos; así mismo, aplicar una regla para la selección de los puntos, puede ser al azar o recorrer la lista de pixeles de bordes en orden e ir armando los pares respetando la primer regla.
Elegir una gradiente para cada punto de acuerdo a sus coordenadas:

$$ gx = Gx \left [ y, x \right ] $$ $$ gy = Gy \left [ y, x \right ] $$

A partir de las matrices de gradientes obtenidas, calcular el ángulo para cada pixel de acuerdo a la formula:

$$ \theta = \arctan \left ( gy/gx \right ) $$ *Nota: Tuve que ajustar el ángulo obtenido, no sé si sea alguna causa local, pero si el dibujo de la recta tangente sale mal orientado primero asegurarse que el ángulo no sea mayor a 2$pi$ o menor a 0.
Después girar el ángulo con el siguiente ajuste:
$$ \theta = \left (\theta - \frac{pi}{2} \right )(-1) $$

Dibujar la recta tangente para cada punto, para mi caso particular utilicé una fórmula donde solo de necesita un punto y el ángulo, así como un largo arbitrario el cual lo definí con la longitud de la diagonal máxima de la imágen. La fórmula regresa los puntos donde comienza (xA,yA) y finaliza (xB, yB) la línea tangente (que es todo lo que necesitamos), tomando en cuenta que las coordenadas del pixel seleccionado son su coordenadas de origen. La fórmula es:

$$\left ( xA,yA \right ) = \left ( x + (L \cos \left ( \theta \right ) ), y + (L \sin \left ( \theta \right ) ) \right )$$ $$\left ( xB,yB \right ) = \left ( x + (L \cos \left ( \theta - \pi \right ) ), y + (L \sin \left ( \theta - \pi \right ) ) \right )$$

Identificar si las rectas tangentes se cruzan o no, si es así, detectar el punto de cruce.
Calcular el punto medio a partir de los puntos del borde que tocan las rectas tangentes.
Dibujar una linea entre el punto de cruce de las lineas tangentes y el punto medio.
Alargar dicha linea y someter a votación los pixeles que cruza dicha linea.
Agrupar los votos y definir el centro candidato.
Calcular los semidiametros del elipse a partir del centro candidato.
Aplicar la ecuación del elipse para dibujar el contorno del elipse.

Práctica

Las imagenes utilizadas para las pruebas fueron las siguientes:

Original
Binarizada
Contornos

Para la prueba realice una corrida exhaustiva, buscando casi todas las combinaciones de pares de puntos para comparar las tangentes, respetando los umbrales correspondientes.

Esta es una imágen que muestra un paso intermedio del proceso, las lineas azules son las tangentes, los puntos verdes son el origen de las tangentes, punto medio y punto de cruce de las tangentes, los puntos rojos son los pixeles sometidos a votacion:

La idea es repetir el paso mostrado en la imagen suficientes veces como para que el centro del elipse sea el mas votado.

Resultados

Los resultados de las pruebas fueron los siguientes

Como se puede ver en los resultados, algunas veces los centros de los elipses son detectados lejos del centro real, desplazados; esto afecta también el dibujo de los semidiámetros,
Pienso que falta un ajuste en el método de votación y de agrupación de votos.

Se imprimen en pantalla los ID de los elipses junto con el listado que incluye los tamaños de los semidiametros en pixeles y su porcentaje vs. el tamaño de la diagonal mayor de la imagen.

Código

En el repositorio encuentran la implementación completa en código, la carpeta marcada como Tarea 6.

https://github.com/jcespinosa/vision_computacional

Referencias:

domingo, 14 de abril de 2013

[Lab CU] Actividad 7: Métodos de localización en interiores

La actividad de esta semana consistió en realizar un pequeño reporte sobre algún documento buscado a través de Google Scholar donde se hable sobre métodos de localización en interiores.

El documento seleccionado fue:

...

RFID-ASSISTED INDOOR LOCALIZATION AND COMMUNICATION FOR
FIRST RESPONDERS*

J. R. Guerrieri(1), M. H. Francis(1), P. F. Wilson(1), T. Kos(1), L. E. Miller(2), N. P. Bryner(2), D. W. Stroup(2), L. Klein-Berndt

National Institute of Standards and Technology

guerieri@boulder.nist.gov

...

Introducción

El proyecto trata sobre un método de localización y comunicación para interiores que utiliza tags RFID (Radio frecuency identification) colocados de manera estratégica en los edificios, los tags funcionan como puntos de navegación.

Cuando los tags son colocados en personas u objetos, éstos pueden ser fácilmente rastreados utilizando lectores especiales en lugares fijos.

El proyecto explora éstas características, donde el usuario lleva consigo un lector especial para proveer una localización precisa rastreando a la persona u objeto. La información recolectada puede ser usada para comparar y corregir errores en cualquier sistema de rastreo inercial.

El proyecto también sirve para evaluar el concepto de un sistema de rastreo y localización de bajo costo que permita a diferentes instituciones de primeros auxilios tales como bomberos o paramédicos, ubicarse en un edificio donde los sistemas GPS no son fiables y donde incluso la señal del GPS puede verse afectada o bloqueada por algún otro siniestro.

También se considera la posibilidad de utilizar la información del edificio, que es almacenada en los tags. Esta información puede ayudar a los rescatistas en sus misiones, por ejemplo, describiendo el layout de un cuarto o lo que sea dependiendo del contexto en el que se encuentre. Esto ayuda a minimizar la necesidad de accesar a bases de datos mediante cualquier otro método de comunicación.

Motivación del estudio

Las tecnologías actuales no son fiables para la localización de objetivos dentro de los edificios.

Los sistemas de localización, rastreo y navegación en interiores no pueden depender de los sistemas GPS, es difícil utilizar éste sistema debido a que la señal de los mismos puede verse debilitada en espacios cerrados. Se considera entonces que los sistemas GPS no son fiables para éstos objetivos.

Sensores inerciales pueden rastrear la ubicación y el movimiento de objetivos, tales como acelerómetros, giroscopios, barómetros, etcétera.

Son un gran complemento al utilizarse con otros métodos de localización.

Los sitemas RFID pueden aumentar la precisión de los sistemas inerciales, agregando correcciónes a los mismos, como ya se menciono, aprovechando la capacidad de almacenamiento de los tags para proveer información adicional sobre la ubicación y posicionamiento dentro del edificio

Enfoque del estudio

El enfoque principal refiere a la propagación de las radiofrecuencias en el ambiente del edificio en situaciones de emergencia, así mismo se consideran otros enfoques tales como:

La estrategia de desarrollo
Métodos de rastreo
Las opciones de presentación de la información de la ubicación al usuario, y la manera de comunicarla a una estación de monitoreo.

El desarrollo de los RFID y los aspectos de localización en los escenarios estudiados incluyen:

Los beneficios obtenidos al elegir cierto tipo de dispositivos RFID, incluyendo costos, facilidad de programación, adecuación a los ambientes de emergencia, capacidad de datos.
Utilizar la mínima cantidad de puntos RFID de referencia para calibrar correctamente los demás sistemas de localización inercial y otros sistemas para mantener un buen nivel de precisión para las instituciones de primeros auxilios.
Utilizar múltiples puntos RFID de localización para facilitar la localización sin necesidad de otros sensores inerciales de localización.
Informar solamente al usuario su posición, asumiendo que los sistemas de comunicación interpersonales serán provistos por otro sistema.
Proporcionar a otros miembros del equipo de rescatistas y comandantes, las ubicaciones de los demás por medio de una red ad-hoc que combinen la lectura de los dispositivos RFID y radio comunicación.
Proveer instrucciones sobre las direcciones a los usuarios para ubicar salidas de emergencia.

Figura 1. Edificio con un layout simple de RFID

2. Parámetros de localización para bomberos.

Mientras que el número de tags RFID es flexible y se adapta a las necesidades, la información y requerimientos están identificados y se agrupan en términos de:

Tipo de edificio
Temperatura ambiental
Factores de atenuación de señales.

El tipo de edificio se refiere a los métodos y características en la construcción de un edificio para resistencia al fuego, se dividen en 5 tipos diferentes.

Resistentes al fuego, construídos de concreto reforzado y acero estructural.
No combustibles, construídos de metales recubiertos, exteriores metálicos.
Ordinarios, construídos con materiales mixtos, combustibles y no combustibles.
Madera pesada, construídos de materiales combustibes pero de manera limitada.
Estructura de madera, construídos de madera y son muy combustibles.

La temperatura ambiental durante los eventos de primeros auxilios es descrita en términos de las zonas y los grados de exposición al flujo de calor y el riesgo de sufrir daño.

Los factores de atenuación de señales que pueden afectar las señales de radio frecuencia incluyen:

Presencia de humedad en el aire debido a la combustión y encendido de alarmas, se espera un porcentaje del 100%
Partículas de humo en el aire.
Partículas cargadas en el aire.
Distribución de calor que pueden afectar el flujo de aire y las ondas de radio.
Materiales de construcción en los edificios tales como aislantes, metales, tratamiento de ventanas.

Estos factores pueden variar dependiendo del escenario de auxilio.

3. Técnicas de navegación y dispositivos

Se analizó principalmente una técnica llamada Dead Reckoning (navegación por estima). Si bien el sistema de navegación mas utilizado es el GPS, y se han mencionado las desventajas de utilizarlo en interiores y zonas muy urbanizadas. Una desventaja adicional es que cuando el dispositivo GPS pierde la señal, éste pierde una gran cantidad de tiempo adicional intentando reconectarse a los satélites.

El método de Navegación por estima (Dead Reckoning) es una técnica muy antigua que se basa en la estimación de la ubicación mediante la velocidad, tiempo y distancias recorridas y por recorrer durante un viaje. En buen método cuando las velocidades y el curso del viaje se mantienen constantes, sin embargo, la incertidumbre del método crece con el tiempo y es necesario introducir correcciones al sistema con regularidad. En este caso, los RFID proporcionan dichas correcciones.

Combinando el método con otros dispositivos como brújulas y giroscopios, su desempeño se puede llegar a comparar con el de un GPS.

Figura 2. Comparación del rastro de un GPS y un sistema DR

Aún existen ciertos problemas que solucionar, como la existencia de campos electromagnéticos y otro tipo de interferencias debido a corrientes de alta tensión, por ejemplo.

4. Ubicación y cantidad de tags

Determinar el número de tags y dispositivos RFID es hablar de la precisión requerida para el sistema. Los rangos de precisión deben ser formulados en términos de la cantidad de correcciones que deba hacerse al sistema y la densidad espacial de los puntos de acceso y rutas.

Sin embargo, el cálculo de la precisión final del sistema para interiores asistido por RFID puede resultar prematuro. Por ejemplo, un factor importante en la precisión del sistema de navegación por estima a ser probado en condiciones desconocidas a las esperadas en los escenarios de primeros auxilios es el caminar irregular de los rescatistas durante su labor, lo que puede afectar el algoritmo de conteo de pasos.

Además de que no existe un punto de referencia para los sistemas de localización en interiores, o por lo menos un método que proporcione un grado de precisión fiable.

La cantidad y ubicación de los tags depende principalmene de la tecnología RFID a utilizar, más que nada, los requerimientos y las distancias mínimas y máximas de operación.

Utilizar solo tags RFID puede ser una buena aproximación, sin embargo, solo se proporcionarias eventos de tipo "tu estas en ...", indicando solo una posición genérica, por ejemplo, de algún piso o cuarto.

Sería necesario tener un conocimiento previo de las instalaciones para correlacionar dicha información y la información proporcionada por los tags. Así se tendría una aproximación del área de trabajo.

Sin embargo, los resultados pueden ser ambiguos cuando se detecten dos o mas tags.

5. Opciones de tecnología RFID

Se intentan cubrir de forma exitosa los puntos de beneficios obtenidos, precio, disponibilidad, portabilidad y consumo energético, adicionalmente, los rangos de lectura y la capacidad de almacenamiento.

Los tags pasivos comerciales tienen rangos de lectura entre 10 y 15 cm, trabajando a 13.56MHz.

Para frecuencias mayores como 400MHz y 900MHz, las longitudes de onda crecen aproximadamente entre 300 y 800 cm.

Se ha comprobado que frecuencias de 600MHz a 2GHz son las más indicadas para la propagación en edificios.

6. Simulaciones

Utilizando un kit de desarrollo RFID que opera a una frecuencia de 900MHz, con lector, tags y software incluído.

La demostración consistió en un concepto de localización para primeros auxilios en un pasillo recto.

El programa incorpora una base de datos que contiene los números de identificación de los tags. El lector esta anclado a un carro para facilitar el viaje a través del pasillo.

Cuando el lector detecta un tag, su número de identificación es recolectado y se busca en la base de datos para obtener las coordenadas del tag.

La precisión y el desempeño se ven mejorados al permitir que solo se detecten los tags del tipo especificado. Asi mismo, los tags fueron modificados, colocando reflectores conductivos en frente de los mismos para mejorar la distancia de lectura, la cual se incremento de 2 a 3.3 m.

Fig 4. Ubicación gráfica del lector y los tags

7. Conclusiones

La sugerencia del paper sobre utilizar la tecnología RFID, junto con otros dispositivos de localización inerciales como giroscopios, brújulas y métodos como la navegación por estima se me hacen una buena aproximación a los métodos de localización en interiores, parece que el proyecto cumple en cuanto a los aspectos de precio y disponibilidad, sin embargo, pienso que aún existe un área muy grande para mejorar.

Así mismo, es interesante el enfoque del proyecto hacía crear un sistema para rescatistas, bomberos, policias; con el proyecto de busca mejorar su labor a la hora de prestar primeros auxilios además de contar con un sistema que les permita ubicar personas o miembros del equipo perdidos y asi salvar más vidas.

Referencias.

http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=4584714
NOTA: Todas las imágenes fueron tomadas del paper.

martes, 9 de abril de 2013

[Lab RT] Actividad 6: Métodos de ruteo y creación de topologías en NS2

La tarea de esta semana constitió en:

Investigar sobre los métodos de ruteo en el simulador NS-2 o NS-3, y cómo habilitarlos y/o cambiarlos para una simulación.
Crear un generador de topologías.

Para las simulaciones utilizaré NS-2 ya que, aunque ya es antiguo considero que tiene mejor documentación y sirve muy bien para las actividades requeridas.

Para su instalación y configuración pueden seguir la guía que escribí en la entrada anterior:

http://juankenny.blogspot.mx/2013/03/lab-rt-actividad-5-practica-con-ns-2-y.html

Métodos de ruteo

En NS-2 es posible activar 3 métodos diferentes de ruteo, cada uno con sus tipos más específicos, los métodos son:

Unicast: Se utiliza cuando la información (paquetes) viajan desde un solo emisor a un solo receptor. Es decir, de nodo a nodo.
Multicast: Se utiliza cuando la información (paquetes) viajan desde un emisor a varios destinatarios. De un nodo a una lista específica de nodos.
Adhoc: Se utiliza en las transmisiones inalámbricas, donde no existe un nodo central sino que todos están listos para enviar y recibir información.

Unicast:

Es el método de ruteo por default en NS-2 y por lo general no es necesario especificarlo, sin embargo, se pueden activar diferentes protocolos y algoritmos que entran en ésta clasificación:

Static: Es la estrategia de ruteo por default, y utiliza el algoritmo de Dijkstra para el calculo de las rutas, el cual corre una vez justo después del inicio de la simulación
Session: Se utiliza para realizar cambios en el ruteo de los nodos de la topología, lo que permite redes dinámicas. Sin embargo, no es muy realista ya que no hay interrupciones transitorias como en el caso del ruteo estático.
DV: Implementación del algoritmo Bellman-Ford para hallar las mejores rutas entre los nodo. Las rutas se actualizan periódicamente según un intervalo de tiempo establecido.
Cost: Establece costos a cada una de las conexiones entre los nodos, los costos pueden ser diferentes en cada dirección.
Multi-path

Para activar cualquiera de los protocolos o algoritmos de ruteo unicast se debe hacer una llamada al procedimiento rtproto y después especificar el tipo de ruteo a aplicar, por ejemplo:


$ns rtproto Static;
$ns rtproto Session;
$ns rtproto DV $n1 $n2 $n3;

Multicast:

CtrMcast: Similar al PIM-SM (Protocol Independent Multicast Sparse Mode), es un protocolo para ruteo eficiente a grupos de multicast, construye un esquema tipo árbol de cada emisor a receptor en el grupo de multicast.
DM: Similar al PIM-DM (Protocol Independent Multicast Sparse Mode), es un protocolo adecuado donde muchos nodos se suscriben para recibir paquetes multicast
ST: Shared Tree Model
BST: Bi-directional Shared Tree Model

Para activar cualquiera de los protocolos de ruteo basados en multicast se deben hacer llamadas a 2 procedimientos multicast y mrtproto:


$ns multicast (justo despues de set $ns [new Scheduler])
$ns mrtproto BST
$ns mrtproto ST
$ns mrtproto CtrMcast

Adhoc:

Los protocolos adhoc se utilizan en redes inálambricas, y solo es posible utilizarlo y el nodo se configura especifícamente para ser nodo inalámbrico (que en NS-2 se conoce como nodo móvil [mobile node]). Para configurar un nodo de forma inalámbrica, se deben de tomar en cuenta las siguientes opciones y elegir de los parámetros los que apliquen en nuestro modelo:

Opciones	Parametros	Notas
addressType	flat, hierarchichal
MPLS	ON,OFF	Multi protocol Label Switching
wiredRouting	ON, OFF
llType	LL, LL/Sat	Link Layer
macType	Mac/802_11, Mac/Csma/Ca, Mac/Sat, Mac/Sat/UnslottedAloha, Mac/Tdma	Medium Access Control
ifqType	Queue/DropTail, Queue/DropTail/PriQueue	Interface Queue type
phyType	Phy/wirelessPhy, Phy/Sat	Physical Layer Type
adhocRouting	DIFFUSION/RATE, DIFFUSION/PROB, DSDV, DSR, FLOODING, OMNIMCAST,AODV,TORA,PUMA	adhoc routing protocol
propType	Propagation/TwoRayGround, Propagation/Shadowing	Propagation Type
antType	Antenna/OmniAntenna,	Antenna type
Channel	Channel/WirelessChannel, Channel/Sat	Channel to be used
mobileIP	ON,OFF	to set the IP for Mobile or not
energyModel	EnergyModel	energy model to be enabled or not
initialEnergy	<joule>	in terms of joules (Ex: 3.24)
txPower		Power in terms of Watts (0.32)
rxPower		Power in terms of Watts (0.1)
idlePower		Power in terms of Watts (0.02)
agentTrace	ON, OFF	Tracing to be on or off
routerTrace	ON, OFF	Tracing to be on or off
macTrace	ON, OFF	Tracing to be on or off
movementTrace	ON, OFF	Tracing to be on or off
errProc	UniformErrorProc
toraDebug	ON, OFF

En la opción adhocRouting se pueden elegir los diferentes modos de ruteo.

Un ejemplo de configuración de un nodo inalámbrico con protocolo de enrutamiento adhoc sería:


$ns node-config -addressType hierarchical \
                -adhocRouting AODV \
                -llType LL \
                -macType Mac/802_11 \
                -ifqType Queue/DropTail/PriQueue \
                -ifqLen 50 \
                -antType Antenna/OmniAntenna \
                -propType Propagation/TwoRayGround \
                -phyType Phy/WirelessPhy \
                -topologyInstance \$topo \
                -channel Channel/WirelessChannel \
                -agentTrace ON \
                -routerTrace ON \
                -macTrace OFF \
                -movementTrace OFF

Manual:

Si se decide por un método de ruteo manual, se tendrán que escribir las tablas de ruteo una por una, las cuales no son más que un conjunto de reglas que especifican hacia donde viajan los paquetes, cuál nodo es el inicial, cuál nodo es el destino, etcétera. Un ejemplo con 2 nodos:


$ns rtproto Manual
set n1 [$ns node]
set n2 [$ns node]
$ns duplex-link $n1 $n2 10Mb 100ms DropTail
[$n1 get-module "Manual"] add-route-to-adj-node -default $n2
[$n1 get-module "Manual"] add-route-to-adj-node $n2
[$n2 get-module "Manual"] add-route-to-adj-node -default $n1

Por default, en la mayoría de los protocolos de ruteo el algoritmo utilizado para hallar los caminos entre los nodos es el algoritmo de Dijkstra.

También se pueden realizar tareas más avanzadas como modificar la tabla de ruteo en cada nodo, o escribir nuestro propio algoritmo de ruteo.

Errores de red

Un concepto adicional y que aporta más realismo a una simulación es la programación de errores en la red. La forma más simple es insertar un error para la pérdida de paquetes en una conexión entre dos nodos. La manera de hacerlo es la siguiente:


set loss_module [new ErrorModel]
$loss_module set rate_ 0.01
$loss_module unit pkt
$loss_module ranvar [new RandomVariable/Uniform]
$loss_module drop-target [new Agent/Null]
$ns lossmodel $loss_module $n0 $n1

Generación de topologías

Para la generación de topologías, me centré solamente en un los tipos de ruteo unicast y multicast. El script para la generación de topologías es escalable, por lo que no sería complejo implementar otros métodos de ruteo, como el adhoc, exceptuando el manual el cual tendría que aplicarse editando directamente el archivo *.tcl que da como salida el script

El lenguaje que utilicé para la generación de topologías fue Python, y mediante este script genero un archivo *.tcl.

Primeramente, el script recibe como entrada un archivo separado por comas donde viene especificada la configuración de la red, el archivo tiene el siguiente formato:


sim,3.0,unicast,DV
red,r1,30,5,50,duplex-link,null,m;1.0
subred,s1,10,1,75,duplex-link,udp,e
subred,s2,10,1,80,duplex-link,tcp,e
subred,s3,10,1,50,duplex-link,udp,a

El primer elemento es una etiqueta, ahora solo se soportan 3 etiquetas, cada una con un formato especifico, en este orden deben escribirse en el archivo:

sim: Refiere a los parámetros generales de la simulación en orden, los parámetros especificados en esta linea son tiempo de la simulación, tipo de ruteo, subtipo de ruteo.
red: Aquí se especifican los parámetros de la red a crear, en orden, los parámetros especificados son: un id para identificar el objeto, el numero de nodos de toda la red, ancho de banda, latencia, tipo de conexiones, tipo de trafico, tipo de topología, parámetros específicos de la topología.
subred: Una vez que se ha creado la red, la red se divide en subredes. Los parámetros son los mismos que para toda la red. Se tiene que ajustar manualmente el número de nodos de cada subred y al final la suma debe coincidir con la cantidad de nodos de toda la red.

Las topologías soportadas son 3 (las más comunes):

Estrella: Un nodo central y todos los demás nodos conectados a él.
Anillo: Un nodo central, conectados en forma de lista enlazada, el último nodo se conecta con el primero.
Malla: Conecta todos los nodos entre sí, pero recibe un parámetro adicional que es un valor entre 0.0 y 1.0, este parámetro es la probabilidad de conexión lo que permite crear topologías con forma de grafo. Se crea una matriz de adyacencia para crear las conexiones pero aun falta ajustar un poco pues pueden salir nodos huerfanos.

Para el caso de las redes con forma de grafo, no es necesario especificar la etiqueta subred, solo en la etiqueta red especifican la cantidad de nodos y el script arma la red completamente.

Los tipos de ruteo soportados son los que entran en la clasificación de unicast y multicast.

El tráfico soportado por el script es de dos tipos:

TCP: De tipo FTP
UDP: De tipo CBR

El tráfico se genera de manera automática también, pero es diferente para cada subred. Se toman los nodos de una subred y se configuran para ser generadores de tráfico y receptores a la vez.

Sin embargo, el script decide cuales de las posibles conexiones estará activa.

Los tipos de conexión soportados son:

Simplex-link
Duplex-link

Evaluando las posibilidades, pienso que se pueden simular una buena cantidad de redes con estas características ya que, por si sola, la topología de malla puede tomar muchas formas y soportar una gran cantidad de nodos.

Capturas de ejemplo:

Ejemplo de 2 estrellas y 2 anillos, conectados por una malla

Ejemplo de una red con forma de grafo

Videos

El primer video es básico, una topología de grafo simple con un método de ruteo Unicast tipo Session.

El segundo video es un poco más complejo, 4 topologías, 2 estrellas y 2 anillos conectadas por una malla, utilizando ruteo Unicast tipo DV.
Se puede ver en los primeros segundos como la red envía mensajes broadcast a todos los nodos para calcular las tablas de ruteo.
Hay ciertos segundos donde lo vuelve a hacer pero por la calidad del video no se alcanzan a apreciar claramente.

Código

Implementar la lógica del programa fue todo un desafío, sobre todo tomando en cuenta que el script debe aceptar redes escalables, conectar los nodos, asignar los agentes correctamente y que el trafico se genere y termine donde debe ser, sin embargo, pienso que el resultado final fue muy bueno.
Aún faltan detalles por afinar y cosas que implementar, acepto recomendaciones.

Referencias:

domingo, 7 de abril de 2013

[Lab CU] Actividad 6: Sugerencias de mejora

Habiendo escuchado la clase de los compañeros sobre el diseño de sus prototipos, el hardware y software a utilizar, redactaremos la retroalimentación de los proyectos junto con algunas sugerencias sobre cómo mejorar los mismos en cuanto a requerimientos.

...

Casa segura (Rene, Raúl, Iván)

El proyecto esta interesante, pero quedo muy simple la presentación, no se explica gran cosa sobre el hardware que necesitan y se enfocan solo en lo más simple.
Por ejemplo, para el circuito para abrir y cerrar puertas y ventanas no explican qué hardware de la lista utilizarán.
De acuerdo a la lista que proporcionan, hay muchas oportunidades de mejora, por ejemplo:

Un sistema individual para abrir puertas utilizando RFID.
Un sistema individual para abrir puertas utilizando bluetooth.

Para ambos casos pueden armar un prototipo, algún tipo de cerradura electrónica que involucra un Arduino dedicado, o identifiquen bien cuál tecnología les favorece más en cuanto a costo y tiempo de desarrollo.

Recomiendo RFID para las puertas y bluetooth para comunicación local con los demás dispositivos.

Para la apertura de ventanas, dudo que el servomotor les sirva, recomiendo que busquen un motor de pasos que tiene más potencia, en el catálogo de Newark se ofrecen algunos a buen precio.

El circuito para la detección de presencia también necesita otro Arduino dedicado.

Después necesitan encontrar la forma de interconectar todo. Recomiendo considerar el uso de una computadora, ya sea una Raspberry o laptop que sirva de servidor y les proporcione algo más poderoso y preciso para tomar decisiones que un Arduino, además un servidor es bastante recomendado para aplicaciones de domótica, así también pueden generar un servicio de monitoreo en línea, enviar alarmas o notificaciones al usuario, etcétera.

...

Garage Inteligente (Emmanuel, Max, Carmen, Victor)

Buen proyecto.

La recomendación que les doy es, por un lado, aprovechar mucho mejor el poder computacional que tendrán con las librerías que utilizarán.
La idea con código se me hace buena, sobre todo porque están de moda, pero me parece más interesante ya que utilizarán algo de visión computacional, abrir el garage identificando directamente la o las matrículas del vehículo. Sobre todo porque Emmanuel ya estuvo trabajando en eso, sería un buen módulo adicional a las opciones que ya tienen.

Por otro lado, el hardware, para un prototipo esta bien que utilicen un módulo bluetooth, ahora, si utilizarán servicio web sería viable agregar algún módulo WIFI en lugar de bluetooth para cuando el celular entre en el rango se conecte automáticamente a la red local y se comunique con el arduino mediante LAN.

Para la apertura de la puerta, hay un hack sencillo que se puede hacer a los motores que abren las puertas de garage, creo los que son marca Craftman (y creo son los más comunes). Pueden poner 2 módulos diferentes, uno donde ustedes provean su propio sistema para abrir y cerrar puertas y otro donde ofrezcan modificar dichos motores para abrir y cerrrar la puerta.
Si no se quieren meter con el motor, algo facil también es modificar el control para abrir y cerrar las puertas. Lo modifican para que envíe una señal al motor utilizando un Arduino dependiendo de lo que quieran hacer, en ésta liga viene un poco mejor explicado esté último ejemplo:

http://blog.silverhawk.net/2013/01/arduino-garage-door-opener-no-rolling.html

Muy bien el proyecto, y también se puede lograr mucho si lo comienzan a ver desde diversas perspectivas.

...

Bloqueo mágico de computadora (Obed, Ave, Pedro, Jona)

Es uno de los proyectos más simples y eso me parece excelente, una webcam es todo lo que se necesita.

Una opción de mejora puede ser que analizarán la manera en que pueden convertir su aplicación en un servicio, tanto de Ubuntu como de Windows, o cualquier sistema operativo que estén considerando.
Posiblemente ahí necesiten además leer la documentación de los mismos y agregar algunos otros lenguajes a su lista, tales como Bash o Batch para Windows.
Pienso que si convierten su proyecto en un servicio estaría mucho mejor ya que se convertiría en algo interesante.

En ésta liga encontré como configurar un servicio para Ubuntu:

http://conscs.wordpress.com/2012/05/06/creating-a-service-in-ubuntu-12-04/

Y en éstas ligas cómo hacer un servicio para Windows, aunque involucra utilizar C#

http://carmencitasanchez.wordpress.com/2007/08/22/crear-e-instalar-un-servicio-windows-paso-a-paso/

http://blog.controlzeta.net/?p=450

También recomiendo leer sobre el celular Samsung Galaxy S4 y los nuevos controles por gestos que incluye, tiene uno llamado Smart Pause que hace algo parecido a lo suyo.

Sería bueno ir más allá y desarrollar una suite de control de gestos para la computadora, es una muy buena oportunidad de mejora.

...

Galeria Inteligente (Blanca, Vanessa, Adriana, Rodolfo)

Muy interesante el proyecto, que bueno que orientaron bien su proyecto

Tengo una recomendación muy buena, pienso que utilizar un sensor de proximidad solamente no es muy fiable, ya que los sensores de proximidad no diferencian entre objetos o personas.
Una oportunidad de mejora es complementar su proyecto con una cámara web que les ayude a identificar cuando una o más personas se acerquen a la obra.
El sensor de proximidad calcularía si una persona esta suficientemente cerca para ver la obra y escuchar la descripción o si solo es un individuo que pasaba por el pasillo.
La cámara identificaría los objetos y solo reproduciría la descripción de la obra si el objeto identificado es una persona.

Entonces aquí su lista de hardware se complementa con la cámara, y la lista de software se complementa con utilizar OpenCV y alguna red neuronal para identificar personas.

Si utilizarán MySQL entonces queda ambigua la lista, pues para utilizar MySQL necesitan un servidor, entonces especificar que se utilizará una computadora como servidor para guardar la base de datos de las descripciones de los mensajes, además de ser requisito pues se necesita algo más poderoso para correr paralelamente la identificación de personas.

El proyecto va bien, solo identificar bien las tecnologías para lograr el resultado deseado en su proyecto.

...

Alarma de automóvil (Alex, Ricardo, Sergio, Roberto)

El proyecto ya tiene mejor forma.

Pienso que el diseño que le dan esta muy limitado y tiene algunos agujeros de seguridad, por ejemplo, pienso que el auto debería de tener una computadora autónoma que no sea posible de configurar a menos que el auto esté cerca de la estación.
En el dock pueden configurar todo, desde las notificaciones, activar o desactivar alarmas, etcétera.
En el auto no pueden configurar nada, el auto automáticamente al encenderse aprovecha la proximidad con la estación/dock para sincronizar todas las configuraciones, conectarse a internet vía GSM/3G (GSM es mas barato y más viable pues la cantidad de datos que enviarán no es muy grande) y conectarse a los satélites GPS (recomiendo analizar la opción de GPS asistido para mayor fiabilidad y rapidez).
Una opción de batería autónoma también sería buena opción para determinadas situaciones.

En ese punto el dock se convertiría en un servidor, conectado permanentemente al auto, recibiendo los datos y lanzando las alarmas en caso de emergencia, así en caso de robo, el criminal no se daría cuenta que esta siendo vigilado, sino que la estación se encarga de todo y el auto sería una trampa de dos filos para el criminal.
Pueden crear un servicio en línea que pueda ser visualizado desde un smartphone y llevar un control de la estación en todo momento.
Así desde el auto todo sería transparente y el usuario no se preocuparía de nada, todo se sincronizaría automáticamente.

...

Localizador Bluetooth (Omar, Saúl Isaías)

La nueva idea es buena, pero pues porqué cambiar, ahora la idea queda ambigua porque no han presentado todo el background de la misma.

Localizar objetos parece buena idea, pero no queda claro qué tipo de objetos, pienso que el tamaño del módulo bluetooth a utilizar limitaría mucho el tipo de objetos que pueden ser localizados.
El costo de los componentes también es importante, cuánto costará el módulo bluetooth para cada tag además de los demás componentes del circuito que involucra.
La batería es otro concepto, no me queda claro la forma en la que lidiarán con eso, hacer pruebas con un celular parece la salida fácil, pero, al momento de crear el prototipo real ¿cómo gestionarán el uso de energía?. Una aproximación puede ser utilizar una batería recargable, pero no sería muy "inteligente" tener que estar cargando todos los tags de todos los objetos que no quieres perder y mucho menos utilizar baterias desechables de corta duración.
Una oportunidad de mejora para hacer los tags más inteligentes es utilizar pequeñas celdas solares más una batería recargable.

Pienso que deberían poner más atención al prototipo físico, ya que se puede ver que en el aspecto de software están bien informados, pero por lo visto no han abordado los detalles más simples en el aspecto del hardware.

Hay dos proyectos parecidos al suyo, sirven de lectura para analizar la competencia y ver la manera en la que ellos solucionaron los detalles encontrados al realizar sus proyectos:

Cobra: http://bitelia.com/2012/01/ces-2012-cobra-encuentra-tus-objetos-perdidos-con-una-aplicacion
StickNFind (el más parecido): http://www.xatakamovil.com/conectividad/sticknfind-etiquetas-bluetooth-4-0-para-localizar-objetos

Y se hardware, éste parece ser un tag NCF Bluetooth, puede servirles: http://www.identivenfc.com/en/bluetooth-nfc-tag-42mm-dia.htm

...

Oficina Inteligente (Lupe, Osvaldo, Triana, Esteban)

Esta vez se quedaron muy cortos respecto al alcance del hardware.
El acceso a la oficina esta cubierto parcialmente, falta especificar la relación entre los componentes de hardware, por ejemplo, dicen que el servidor será el lector RFID ¿?. Sería montarlo en un arduino y conectarlo a una PC vía usb o ethernet para mayor velocidad.

En cuanto a los sensores, además del sensor de presencia pueden auxiliarse con un sensor de iluminación para el control de las luces, así atacarían también el lado de ahorro de energía.
Los sensores de temperatura pueden mejorarse utilizando termostatos, que son mas fiables en un entorno de oficina, además, si la oficina ya tiene instalado un sistema de aire acondicionado por lo general ya viene incluido también el termostato.

Se necesita mas hardware para el lado de desconexión de equipos sin usar, aquí recomiendo checar algún tipo de relevador que les permita controlar la corriente alterna de una forma segura y cortar la misma para apagar los dispositivos.

Para la alarma recomiendo algún tipo de bocina o algo más analógico como un timbre o campana, además de luces de advertencia.
El bloque de puertas se puede implementar con una cerradura eléctrica, las venden en cualquier distribuidor de equipos de seguridad, o si la empresa ya cuenta con cerraduras eléctricas pueden verificar la manera de controlarlas mediante electrónica que ustedes diseñen, ya sea con un arduino o un Raspberry Pi. De manera alterna pueden implementar un servomotor o un motor de paso para emular la cerradura.

...

Despertador inteligente (Ramón, Cecy, Roberto)

Es un proyecto que tiene bastante potencial y que tiene muchas opciones de mejora, solo basta con aplicar mucha creatividad para lograr muchas cosas.

El software que utilizarán me parece más que suficiente, ya que solo involucra un poco de programación en los arduino.
En cuanto al hardware, me parece que están siendo un tanto limitados, por ejemplo, pueden implementar diferentes métodos de comunicación con diferentes tipos de hardware en lugar de crear el propio:

Comunicación bluetooth
Comunicación Xbee
Comunicación infraroja (para objetivos fijos)

Y de acuerdo a lo que elijan sería bueno ampliar la lista de hardware a utilizar, ahora, pueden implementar diferentes tipos de alarmas, por ejemplo:

Montar una alarma en una pared y que no se apague hasta que el usuario presione un botón en ella.
Montar el sensor de presión en una alfombra fuera del cuarto.
Montar el buzzer en un pequeño auto autónomo que corra por toda la habitación y obligue al usuario a perseguirlo para apagarlo.
Un micrófono y que la alarma no se apague hasta que el usuario cante la canción que se escucha ahí.

En fin, cada diseño involucra hardware adicional pero no necesariamente un gasto adicional y serían buenas ideas para prototipos que pueden utilizar para convertir su proyecto en toda una gama de opciones de alarmas más intuitivas.

Si tienen algo de tiempo extra pueden ejecutar cualquier otra opción.

...

Esas fueron mis observaciones y recomendaciones para los demás proyectos.

[IT] Card game extra points

Label: "Label all edges heading to the right with a zero and those heading to the left with ones."
Column: "Initialize the first column of M all zero if the first character of the text is not equal to the first character of the pattern."
Binary: "For binary text and a binary pattern"
Rule: "Special rules to save more time by shifting more positions: Bad character rule, Good suffix rule"
Efficient: "Knutt-Morris-Pratt, usually less efficient, but much easier to explain and prove."
Pattern: "
When a substring of the pattern aligns and then there is a mismatch
at position i, move the pattern i - sp’ i positions to the right.
Fuzzy: "
Example: binary input, fuzzy or stuttering output
Lossless: "
If all bits of L can be recovered from S, the compression is lossless.
Dictionary: "
The dictionary is included in the beginning of the compressed
file, unless it is implicitly constructed in a standard way
Code word: "
Each word is replaced by a (shorter) code word.
The code words usually cannot share prefixes
Obtain: "
Concatenate the edge labels for the path from the root to a leaf to
obtain the code word for the symbol at that leaf.
Preprocessing: "
The use of shortcut rules generally requires preprocessing.
Average: "
Average information content:
Logarithm: "
The base of the logarithm is not that crucial; interpret it as units,
base two being the bit (binary digit)
Root: "For any leaf i, the labels on the path from the root to that leaf concatenate to exactly the suffix S[i..m]."
Symbol: "
An implicit suffix tree for S is obtained from a suffix tree by
removing the terminal symbol $ from all edge labels, removing
any unlabelled edge, and removing subsequently all nodes that
do not complete at least two children.
Equal: "
If the two are equal for a given r and P is of length n, then there is
a match to P starting at r in T."
Worst case: "
How does this differ from the worst case complexity?
Rate: "
The rate of information flow; the maximum value of...
Compute: "To compute M( j ), we perform a binary AND on Bit-Shift( j -1) and U ( T ( j ) )."
Correct: "
The probability of correct transmission is denoted as p
Optimal: "
Optimal input frequencies
Buffer: "
Online compression = the string arrives bit by bit,
possibly with a limited-capacity buffer
Apply: "
We must apply mod p during the computations of the H values
for this to save us anything at all.
Complexity: "
Install and experimentally determine the “typical-case”
complexity.