Compression image

For this entry in the class of Information theory and coding methods, the compression was commissioned an image or an audio file, in this case is going to make an image compression with wavelets.

First make a little introduction to know what we are doing.

Image Compression

The objective of image compression is to reduce the redundant and irrelevant data of the image with the lowest possible loss, suitable for storage or transmission efficiently.

Classifying compression methods:

• Lossless compression (Lossles).
• Lossy compression (lossy).

In the lossless coding can transmit an image using lossless compression on a lossy transmission protocol like UDP. By contrast in lossy compression can transmit a lossy compressed image information on a lossless protocol such as TCP.

Methods lossy encoding:

• Lossy predictive coding.
• Transform Coding.

Methods of lossless compression coding:

• Variable logitud coding (Huffman Coding and others).
• Encoding bit planes: decomposition and RLE.
• LZW and CCYTT Basics.
• Lossless predictive coding.

Decomposition of Images

There are different ways to decompose an image, but in this case applies DWT, this wavelet transform has recently become a very popular tool when it comes to analysis, denoising and signal and image compression, this transform obtained of a image four types of ratios:

• cA: Coefficient of approximation. (LL, which corresponds to the upper left corner)
• cH: horizontal detail coefficient. (LH, which corresponds to the upper right corner)
• cV: vertical detail coefficient. (HL, which corresponds to the lower left corner)
• cD: diagonal detail coefficient. (HH, which corresponds to the lower right corner)

What are wavelets?

The wavelets are families of functions found in space and used as features for analysis, examine the signal of interest for its features and address space size.

Wavelets

Until now, the major outstanding application of wavelets has been digital image compression. They are the backbone of the new standard JPEG-2000 digital imaging and method WSQ (Wavelet Scalar Quantization English, wavelet scalar quantization) using the FBI to compress its database of fingerprints. In this context, one can think of wavelets as basic components of the images. An image of a forest may consist wider wavelets: a large swath of green for the forest and a patch of blue for the sky. Wavelets greater detail and sharpness can be used to distinguish one another tree. You can add branches and needles wavelet image even finer. As a brushstroke of a painting, each wavelet is not an image itself, but many wavelets together can recreate anything. Unlike a stroke of a painting, a wavelet can be made arbitrarily small: one wavelet has no physical limitations of size because it is just a series of zeros and ones stored in the memory of http://www7.nationalacademies.org/ spanishbeyonddiscovery/mat_008276-04.htmluna computer.

A fascinating property of wavelets is to automatically choose the same features as our eyes. The wavelet coefficients after quantization are still correspond to pixels that are very different from their neighbors, on the edge of objects in an image. Thus, wavelets recreate an image by tracing edges mainly, that is exactly what humans do when they paint a picture. In fact, some researchers have suggested that the analogy between wavelet transformation and human vision is not accidental, and that our visual cues filtered neurons similarly to wavelets.

Some types of wavelets for compression

- Haar wavelets
The first DWT was invented by the Hungarian mathematician Alfréd Haar. For an input represented by a list of numbers, the Haar wavelet transform may be considered to simply pair up input values, storing the difference and passing the sum. This process is repeated recursively, pairing up the sums to provide the next scale: finally resulting in differences and one final sum.

- Daubechies wavelets
The most commonly used set of discrete wavelet transforms was formulated by the Belgian mathematician Ingrid Daubechies in 1988. This formulation is based on the use of recurrence relations to generate progressively finer discrete samplings of an implicit mother wavelet function; each resolution is twice that of the previous scale. In her seminal paper, Daubechies derives a family of wavelets, the first of which is the Haar wavelet. Interest in this field has exploded since then, and many variations of Daubechies' original wavelets were developed.

- The Dual-Tree Complex Wavelet Transform (ℂWT) The Dual-Tree Complex Wavelet Transform (ℂWT) is relatively recent enhancement to the discrete wavelet transform (DWT), with important additional properties: It is nearly shift invariant and directionally selective in two and higher dimensions. It achieves this with a redundancy factor of only  for d-dimensional signals, which is substantially lower than the undecimated DWT. The multidimensional (M-D) dual-tree ℂWT is nonseparable but is based on a computationally efficient, separable filter bank (FB).

Now let´s start with the homework for this entry.

What was used?

To perform this homework was used

• Wavelets.
• A type of Fourier transform (DWT as mentioned above).
• Python as programming language.
• PyWavelets library to call the transformed and so compress the image.
• Libreria numpy to make a matrix with the pixels of the image and so is easier to implement the wavelet.
• PIL library for image loading.
• Library for execution sys from commands in terminal.
• Library time, to know execution times.

Sequence

The sequence following the code is simple thanks to the libraries used

• Image is loaded.
• We make the image smaller, to make the process faster.
• Then we put a grayscale filter to the image.
• Then we take the pixels as an array with numpy.
• We use the discrete transform for compression.
• We save image.

Code

Results

Original image

Compress image

Comparison of weights

Times

______________________________________________________________________

Original image

Compress image

Comparison of weights

Times

_______________________________________________________________________________

Original image

Compress image

Comparison weight

Times

Conclusion

The discrete transform works great for compressing images and we can notice in the above results, this is very good because as mentioned above have files lighter help us to store more information. Unfortunately the images come out very blurry

The image size affects the time that is done the compression process as it has to do more tours of the image.




References

[*] wavelets: ver el bosque y los arboles, Beyond discovery, http://www7.nationalacademies.org/spanishbeyonddiscovery/mat_008276-04.html

[*]Compresión de imagen, Wikipedia la enciclopedia libre http://es.wikipedia.org/wiki/Compresi%C3%B3n_de_imagen

[*]nullege  http://nullege.com/codes/show/src@p@y@PyWavelets-0.2.2@demo@wp_2d.py/10/pywt.WaveletPacket2D

[*] http://hci.iwr.uni-heidelberg.de/MIP/Teaching/ip/ex04/ia_ex04.pdf

[*] Documentation pywavelets http://www.pybytes.com/pywavelets/ref/wavelets.html

[*] DWT. http://www.pybytes.com/pywavelets/ref/dwt-discrete-wavelet-transform.html

Bioinformatics

Data Compression Concepts and Algorithms and Their Applications to Bioinformatics

by Ozkan U. Nalbanto ̃ lu, David J. Russell and Khalid Sayood 

Introduction:

Compressing data, involves understanding the way information is structured and, if possible, the mechanism by which the information was generated or is destined to be used. Thus, in order to compress speech it helps to know that the speech production process can be modeled by an autoregressive moving average filter excited by a signal with a periodic and a noise-like component.

Life is strongly associated with organization and structure. Living organisms can be viewed as agents communicating with their environment and storing information necessary for adaptation to the environment. This information storage, both in content and form, is shaped by the process of evolution and transmitted from one generation to the next via the DNA molecule.

In this work we look at how the tools and theoretical constructs, which have been so useful in the development of data compression algorithms, can be used to understand biologically important molecules which can be represented as sequences, such as DNA, RNA, and proteins. 

We briefly review compression algorithms developed for compressing biological sequences, however, the attention of this document main focus is on how conceptual tools in the data compression repertoire have been used in the field of bioinformatics.

This document observed at how the concepts of Shannon Entropy, average mutual information, Kolmogorov complexity and grammar-based modeling have been used in bioinformatics. There is an excellent review of compression algorithms for biological sequences in. Therefore, we provide only a brief survey of compression algorithms for biological sequences and focus more on their use as a measure of distance between biological sequences. We conclude with a section on grammar based techniques and their application in bioinformatics.

A bit of Biology

The major focus of bioinformatics is on three kinds of molecules, DNA, RNA, and proteins, all of which can be represented as sequences. The DNA molecule is made up of a concatenation of four different kinds of nucleotides, Thymine, Adenine, Cytosine, and Guanine.

The DNA molecule can be represented as a sequence by representing each nucleotide by the first letter of the corresponding nucleobase (T, A, C, and G). DNA is a double stranded molecule with neighboring strands connected through hydrogen bonding between the nucleobases. This double stranded nature of the DNA molecule makes it more robust to errors than the single stranded RNA molecule and provides a mechanism for accurate reproduction of the information.

The regions of the DNA molecule that act as blueprints for proteins are called genes. An entire gene is transcribed by the RNA polymerase enzyme into an RNA molecule. The ribose sugar in the RNA molecule differs from the deoxyribose sugar in the DNA molecule in that a hydroxyl (OH) group. Furthermore, the nucleobases that are part of the ribose nucleotides that make up the RNA molecule are Uracil (U), Adenine (A), Cytosine (C), and Guanine (G), with Uracil replacing Thymine.

The transcription from DNA to RNA is through base pairing every C is transcribed as a G, a G is transcribed as a C, a T is transcribed as an A and an A is transcribed as a U. The RNA molecule created through the action of RNA polymerase is processed and portions excised resulting in a messenger RNA (mRNA). Each gene can be transcribed multiple times and the transcript can be translated multiple times before it is subjected to degradation. The level of transcription and translation is controlled through a complex set of regulation mechanisms which involve, among other things, the binding of regulatory proteins to sites on the DNA close to the gene.

Entropy and Biology

Given that DNA is a means of transmitting information between generations it was natural that the concepts of entropy and information be applied to understanding DNA. One of the first contributions to the use of the concept of information in bioinformatics was the work of Lila Gatlin in the 1960’s. Gatlin proposed a definition for the information content of DNA which was essentially a measure of the divergence of the DNA sequence from an iid sequence. Given an alphabet of size N , where N is four for DNA sequences and 20 for amino acid sequences, Gatlin defined two quantities D1 and D2 which measured divergence from the equiprobable state and divergence from independence, respectively.

 Gatlin connects this definition of information to redundancy by noting that defining redundancy as

result in

Based on the limited data available at that time, Gatlin showed empirically that DNA from vertebrates, bacteria, and phage (viruses that prey on bacteria) can be distinguished by looking at their information content and that there is increasing redundancy in the DNA of organisms as we move from lower complexity organisms like bacteria to higher complexity organisms such as vertebrates. Plotting the data available to her as shown in the next figure it is easy to see why she would come to that conclusion.

The logo as created by Schneider and Stephens is widely used in various bioinformatic applications as they provide information useful to biologists. A tall stack of letters at a particular location implies that the corresponding site is important for some reason. Schneider and colleagues in other work have used logos for studying DNA protein interaction, to investigate variants and look for novel genes. The utility of the entropy concept in such a wide range of application suggests that perhaps these concepts are natural to biological sequences and a more wide-ranging and deeper analysis would be a fruitful endeavor.

Application of Average Mutual Information

What entropy is to lossless compression, the rate distortion function is to lossy compression. Both provide a bound on the efficacy of compression. The rate distortion function depends on two things, the distortion measure and average mutual information between the source coder input and the source coder output. The average mutual information between random variables X and Y is given by

The ability of the average mutual information to expose relatedness has been used in a number of ways in bioinformatics. Then the average mutual information can be used to identify bases in DNA sequences, or residues in amino acid sequences that in some way depend upon each other. This dependence can help understand something about the two and three dimensional structure of the virus, or protein.

Korber et al. in a groundbreaking study identified correlated mutations in the envelope protein of the HIV-1 virus. By mutating the envelope protein the virus tries to keep the host’s defense off-balance. This effect is clearly seen in AMI charts developed by Sayood et al. when studying the differences between infected infants who succumbed to HIV and those who did not. The AMI chart is simply a representation of the average mutual information values in the form of a matrix where the (i, j)th pixel in the chart represents the average mutual information between the ith residue and the jth residue of the envelope protein. 

The difference in the charts shows the differing characteristics of the populations with substantial levels of mutation continuing in those patients who remained asymptomatic an indication perhaps of continuing efforts of the viral population to overcome the host defenses.

The DNA of organisms contains regions which code for proteins and regions which do not. In eukaryotes these regions are interspersed in genes. Because the protein coding regions are interpreted in terms of triplets, one would expect a periodicity of three in the dependence between bases in coding regions, and no such periodicity in non-coding regions. This is indeed the case and the existence or non-existence of such periodicity in the average mutual information can be used to distinguish between coding and non-coding regions.

The concept of average mutual information has also been used to understand relationships between expression patterns of genes. A popular method for observing a cell in action is through the use of microarrays. By measuring the amount of messenger RNA present under different conditions these arrays indicate which genes are active in each condition and the level of activity. A gene seldom acts alone and in order to understand the causal relationships between genes it is important to find which genes behave similarly. A number of studies use average mutual information to obtain this clustering

Compression and Phylogeny

General purpose compression algorithms do not perform well with biological sequences, resulting

quite often in expansion rather than compression. This document main focus, however, is on the relationship of compression concepts with evolutionary distance metrics.

One of the most well-known DNA compressors is Gencompress. Gencompress uses the fact that DNA sequences contain tandem repeats, multiple copies of genes and palindromic sequences. It involves a modified Lempel-Ziv (LZ) algorithm which searches for reverse complements and approximate repeats. Approximate repeats are subsequences which can be transformed into a copy of the original subsequences using a small number of edit operations (substitution, insertion, deletion). Copying an approximate repeat and modifying it with edit operations is shown to be cheaper in terms of bits than describing the sequence under construction in some other manner.

The following video shows as working the Lempel Ziv:

Note: if you do not understand the video, in references is the link which explains how it is that works in conjunction with this gif.

The phylogeny is the evolutionary history of the development of a group of organisms. And is the study of the evolutionary relationships between different groups of organisms, using information matrices and DNA molecules morfología.2 With this information established phylogenetic trees, based on phylogenetic classification. This classification is part of the systematic, further comprising also phenetic classification systems and classical Linnean.

Benedetto et al. use this measure of similarity to determine authorship, and for determining the phylogeny of languages. This latter application is what interests us as there is a great deal of literature which suggests that languages evolved through a process of natural selection similar to biological evolution. Therefore, a measure of distance which seems to reflect evolutionary distance between languages would also be useful in understanding phylogenetic relationships between organisms.

That the basic principle behind the Lempel-Ziv compression algorithms have been so successful in identifying evolutionary relationships may mean that the differences uncovered through the use of compression are somehow natural to the evolutionary process. This speculation is further supported by the exploitation of distance metrics based on compression for protein classification and genome segmentation [61]. Kocsor et al. showed that using compression based approaches can be more accurate for protein classification than the commonly used Smith-Waterman alignment algorithm or Hidden Markov Models. Pelta showed that the compression of protein contact maps can be used for protein classification and showed that the UNIX compress algorithm can be used for protein domain identification.

Grammar and Biology

The Lempel-Ziv algorithms, though usually not thought of that way, are examples of the use of

a grammar for compression. The original concept behind abstract grammars is that a grammar G is

meant to completely describe the underlying structure of a corpus of sequences. Because most naturally

occurring sequences contain repetition and redundancy, grammars are often able to describe sequences

efficiently. Hence, the usage of grammars can be thought of as a means to provide compression.

The next figure show how works this type of compression.

Identification of function and/or meaning of segments of biological sequences remains an ongoing and active area of research. This means studying primary structure, or the sequential ordering, of sequences and the secondary structure, or the three-dimensional shapes that form due to attractions that occur among separated segments within the sequences. A somewhat uncommon method for predicting RNA secondary structure focuses only on the information contained within the sequences.

Conclusion
The concepts behind data compression have been very useful in understanding how information is organized in a number of signals used in multimedia communications. It is a natural step to go from analyzing signals such as speech, audio and video to analyzing biological “signals” such as DNA, RNA, and proteins. The results have been somewhat counterintuitive. Instead of these techniques being useful in the development of compression algorithms for biological signals, these concepts have been most useful in illuminating various biological relationships. These range from providing a species signature to providing tools for analyzing the behavior of gene regulation networks. Reviewing the wide variety of places where these concepts have been useful it is difficult to escape the feeling that information theory, in particular those aspects of it that relate to data compression, are somehow organic to the area of bioinformatics. Is believe this will be a fascinating field of study for many years to come and a productive area in which people with an understanding of these concepts can make valuable contributions.

References:
[*] Ozkan U. Nalbanto ̃ lu, David J. Russell and Khalid Sayood. "Data Compression Concepts and Algorithms and Their Applications to Bioinformatics". Entropy 2010, 12.  http://www.mdpi.com/1099-4300/12/1/34

[*] Pablo Morales. "Que es la Filogenia". 9 de julio de 2010. http://biologia.laguia2000.com/biologia/que-es-la-filogenia

[*] "Animation of Lempel-Ziv Encoding Algorithm" http://www.data-compression.com/lempelziv.html. gif lempel ziv.

Images taken from the pdf

Clase redes: Resumen

A Biometric-Based User Authentication for Wireless  Sensor Networks

por YUAN Jianjun, JIANG Changjun,  JIANG Zuowen

Introducción

En los últimos años, las redes de sensores inalámbricos (WSN) han encontrado una amplia gama de aplicaciones, tales como en tiempo real la supervisión del tráfico, la medición de la actividad sísmica, la supervisión de vida silvestre, etc.

La autenticación de usuarios debe ofrecer a la protección de los datos importantes y para evitar que los usuarios no autorizadas obtengan provecho de los datos. La seguridad de la autenticación de usuario tradicional se basa en contraseñas. Sin embargo, las contraseñas simples son fáciles de romper por los ataques de diccionario. Las claves secretas criptográficas, que son largas y al azar, son caros de mantener debido a que son difíciles de memorizar y deben almacenarse en algún lugar. Por lo tanto, se proponen las llaves biométricas, que se basan en las características fisiológicas o de comportamiento de las personas, tales como huellas dactilares, iris, cara, etc.

Las ventajas de las llaves biométricas se resumen de la siguiente manera.

• Las llaves biométricas son extremadamente difíciles de adivinar.
• Las teclas biométricas no son fáciles de abandonar ni olvidar.
• Las llaves biométricas son muy difíciles de copiar con o acción.
• Las llaves biométricas no pueden ser falsificados o distribuidos fácilmente.

Hasta el momento, la autenticación de usuario basada en claves biométricos no se ha aplicado a las aplicaciones WSN. En este trabajo se propone un protocolo de autenticación biométrica de usuario basada en redes de sensores inalámbricos (WSN).

Trabajos relacionadas
La autenticación de usuario en la capa de aplicación WSN no se ha abordado de manera efectiva en comparación con el enlace y protocolos de capa de red para WSN.

- Idea Watro
Watro propone un método de autenticación de usuario basada en la algoritmos Diffie-Hellman y RSA. Hay un fallo de seguridad en el protocolo de Watro, como se explica a continuación.

Cuando un intruso obtiene la clave pública del usuario, él o ella puede cifrar una clave de sesión junto con otros parámetros y enviar la cadena cifrada para el usuario. Al recibir la cadena cifrada, el usuario cree que se trata desde el nodo sensor. Por lo tanto, el usuario descifra la cadena recibida con su clave privada y utiliza la clave de sesión para las operaciones posteriores al intruso tiene la intención de realizar.

- Idea Wong
Wong presentaron un protocolo de autenticación de usuario para WSN, que se basa en la contraseña del usuario y emplea solamente la función hash. El protocolo soporta muchos usuarios registrados con la misma amenaza login-id, es decir, que tiene la contraseña de un usuario válido puede iniciar sesión en la red. El protocolo también es vulnerable a los ataques de robo-verificador ya que el GW-nodo y conexión nodos deben mantener la tabla de la contraseña y la identidad de los usuarios registrados.

- Idea Lee
Por otra parte, la autenticación basada en claves biométricos es más fiable que la autenticación tradicional basada en contraseñas. Lee propuso un método de autenticación de usuario basada en huellas digitales mediante tarjetas inteligentes. Sin embargo, su método no puede resistir el ataque de suplantación y no se aplica a WSN.

Biometria usada en autenticación de usuario 

 Nota: Para el entendimiento de las fases siguientes es necesario estar revisando esta tabla ya que se utilizan abreviaturas o asignaciones a ciertas palabras.

- Fase de registro

• Paso 1: El usuario, Ui, ingresa su biometría, BI, en el dispositivo específico y ofrece su identidad, la IDI y la contraseña, PWI, el GW-nodo de forma segura.
• Paso 2: Al recibir la solicitud de registro, la calcula Ri GW-nodo = h (IDI | | PWI | | Ei) ⊕ h (S), donde Ei = h (Bi). La información secreta S solo se sabe en el nodo-GW.
• Paso 3: El nodo-GW genera una tarjeta inteligente conparámetros IDi, Ri, h (PWI), h (·), Ei, y X, donde X es un parámetro secreto generado por el GW-nodo y almacenado en algunos nodos de sensores designados antes de los nodos en el campo están desplegados. Estos nodos de sensores son responsables para el intercambio de datos con los usuarios y saber X. Entonces, el GW-nodo envía la tarjeta inteligente del usuario para el usuario, Ui, a través de un canal seguro.

- Fase de Logeo

• Paso 1: Ui inserta su tarjeta inteligente en el lector de tarjetas y las entradas biométricas personales, Bi, en el dispositivo específico para verificar sus datos biométricos.
• Paso 2: Calcular Ei * = h (Bi) y leer Ei de la tarjeta inteligente. Si Ei * ≠ Ei, que significa que la IU no pasa la verificación biométrica, y el esquema de autenticación del usuario se termina. Por el contrario, si Ei * = Ei, Ui pasa la verificación biométrica, y luego Ui entradas IDI y PWI. La tarjeta inteligente verifica la IDI y PWI con los almacenados en el mismo. Si el IFI entrado y PWI son correctas, la tarjeta inteligente realiza las siguientes operaciones.
• Paso 3: Calcular Di = h (IDI | | PWI | | Ei) ⊕ h (X | | T), donde T es la fecha y hora actual del sistema de interfaz de usuario.
• Paso 4: Calcular Mi = h (Ri | | X | | T) y enviar (Di, Mi, T) con el nodo de GW

- Fase de autenticación

• Paso 1 Verifique T. Si (T * - T) ∨ DT, se interrumpe la fase de autenticación, donde DT es el intervalo de tiempo esperado para el retardo de transmisión de la WSN. Por el contrario, si (T-T) ≤ Delta T, se llevará a cabo el siguiente paso.
• Paso 2 Calcular Li Di ⊕ = h (X | | T) y Mi * = h ((Li ⊕ h (S)) | | X | | T).
• Paso 3 Si Mi * = Mi, el nodo GW acepta la solicitud de inicio de sesión, de lo contrario, se rechaza.
• Paso 4 Calcular Yi = h (Di | | A | | X | | Tg), donde A es el nodo sensor que responde a la pregunta de Ui, y Tg es la fecha y hora actual del nodo GW. Los envíos GW-nodo (Di, Yi, Tg) a En medio de un canal público. En emplea Yi para asegurar que el mensaje (Di, Yi, Tg) viene rom la legítima GW-nodo Yi porque se genera con X que se sabe que en este lugar y los nodos GW.
• Paso 5 A In, la verificación de Tg es similar a la verificación de T. Entonces En calcula h (Di | | A | | X | | Tg) y comprueba si es igual a Yi. Si los dos anteriores verificación.

- Fasede cambio

De acuerdo con el esquema propuesto en el presente trabajo, el usuario Ui puede cambiar su contraseña libremente. En primer lugar, se inserta Ui su tarjeta inteligente y entradas de su plantilla biométrica, Bi, en el dispositivo específico para verificar sus datos biométricos. Si el usuario pasa la verificación biométrica, es decir, Ei = h (Bi), él o ella puede introducir la antigua contraseña, PWI, y la nueva contraseña, PWI *. La tarjeta inteligente realiza las siguientes operaciones.
a1 = h (IDI | | PWI | | Ei) a2 = a1 ⊕ Ri = h (S) * Ri = h (IDI | | PWI * | | Ei) ⊕ a2 último, sustituir Ri, h (PWI) con Ri * , h (PWI *) en la tarjeta inteligente.

Análisis de la seguridad y rendimiento del sistema propuesto

- Análisis de Seguridad.
Si un usuario legal perdió su tarjeta inteligente, es extremadamente difícil para un adversario obtener la contraseña del usuario o información biométrica ya que la extracción de los parámetros de la tarjeta inteligente es bastante difícil. Por otra parte, el adversario no puede cambiar la contraseña, ya que él o ella no pueden  pasar la verificación biométrica.


Ataque al robo de verificación: El sistema puede resistir ataques de robo del verificador porque el esquema está libre de la tabla verificador/contraseña. En el protocolo, los nodos GW-nodo y el sensor no mantienen tablas de contraseñas. Por lo tanto, un atacante no puede robar contraseñas de los usuarios de los nodos GW-nodo o sensor.

Ataque por adivinanza: El protocolo puede resistir el ataque de adivinanzas, que es una preocupación fundamental en los sistemas basados ​​en contraseñas, ya que la contraseña en el protocolo se transmite como un resumen de alguna otra información secreta. El atacante no puede adivinar la contraseña del usuario de Di debido a la manera de una sola característica de la función de hash, incluso si el

atacante puede obtener Di que contiene la contraseña.

Ataque por repetición: Reproducción de un mensaje interceptado se puede prevenir en el protocolo propuesto. Si un atacante intercepta (Di, Mi, T) e intenta iniciar sesión en el nodo de GW a través de la reproducción de la misma mensaje, él / ella no puede pasar la verificación de la solicitud de inicio de sesión debido a (T * - T) ∨ Delta T, donde T * es la hora del sistema cuando el GW-nodo recibe el mensaje repetido.

Ataque por suplantación: El esquema propuesto puede resistir el ataque de suplantación ya que un atacante puede obtener Di al interceptar una solicitud de inicio de sesión (Di, Mi, T). Sin embargo, con el fin de iniciar de nuevo, Di necesita ser recalculado usando una nueva marca de tiempo, Tnew, para evitar el ataque de reproducción.

- Rendimiento

Coste de computacion: El coste de computación para la fase de registro es un trabajo de una sola vez por un período. Así se calcula el coste de computación para la fase de registro por separado. En la Tabla 2, el protocolo de Watro y otros requiere algunas operaciones exponenciales debido a que su sistema se basa en la resolución de problemas de logaritmos discretos lo que los hace computacionalmente mas costosos que los tres mencionados. Un objetivo del protocolo realizado en este paper es reducir al mínimo el coste de computación de los nodos de sensores, ya que su energía es limitada.

Coste de Comunicación: El sistema requiere 3 intercambios de mensajes, mientras que el esquema de Watro y otros, y el esquema de Wong 2 y 4 requieren intercambios, respectivamente. El esquema de Watro es computacionalmente costosa, aunque su esquema requiere un menor número de intercambios de mensajes. Por otra parte, el número de sub-mensajes en el esquema del paper es la más pequeña entre los tres esquemas. Teniendo en cuenta el coste computacional y el costo de la comunicación, el sistema del paper es eficiente y ahorra costes de energía nodos sensores.


Conclusión

En este trabajo se presenta un esquema de autenticación biométrica de usuario basada en WSN. El método utiliza accesos biométricos y se resiste a las amenazas de robo del verificador, de los cuales muchos son los usuarios conectados con la misma identidad de inicio de sesión, adivinado, reproducido, y suplantado. El programa utiliza, una única función de hash y es eficiente en comparación con la de otros protocolos relacionados. Además, la contraseña del usuario se puede cambiar libremente mediante el esquema propuesto. En el futuro, vamos a diseñar nuevos protocolos para resistir el ataque de denegación de servicio y ataques compromiso nodo.

Cada vez es mas fácil romper la seguridad y conseguir contraseñas de usuarios o ya en los extremos poder entrar a las bases de datos de la nasa, es por eso que es importante la realización de nuevos métodos para la autenticación para la entrada al sistema, este paper nos da la novodesa idea de utilizar redes sensoras para realizar esto y que seria bueno implementar.


Referencias:
[*] YUAN Jianjun, JIANG Changjun,  JIANG Zuowen. A Biometric-Based User Authentication for Wireless Sensor Networks. 2010, Vol.15 No.3, 272-276. http://link.springer.com/content/pdf/10.1007%2Fs11859-010-0318-2.pdf

Imagenes sacadas del pdf 

Proyecto final: Traduccion braille

Presentación

 

Reporte:

Traducción de braille.

Propósito.

Es la creación de un programa para la detección de puntos braille y posterior traducción de su lenguaje al lenguaje ascii utilizando técnicas de visión computacional.

Justificación.

Este trabajo se realizo para la ayuda de los profesores que cuentan con alumnos con problemas de visión o son ciegos y que utilizan este sistema para entregar trabajos o comunicarse por escrito.

Para darle la sencillez a los maestros de poder revisar esos trabajos sin temor a equivocarse o perjudicar al alumno que tienen estos problemas.

Además el sistema puede ser utilizado en otras áreas que no sean las educativas, también puede servir para la gente que busca entender mejor este tipo de lenguaje ya que cuenta con un amigo o familiar con problemas en la vista y así a ayudarlo a seguir adelante

Librerías utilizadas.

Las librerías necesarias para que este programa realice su funcionamiento son:

• Python: Como lenguaje de desarllo.
• Numpy: Para la manipulación de los arreglos de las imágenes.
• PIL: Para la carga de las imágenes a utilizar ya sea jpg, png, etc.
• Image: 
• ImageDraw: Para dibujar puntos de referencia que marquen los puntos braille (como cuadros indicando el punto detectado).
• sys: argv: Para leer parámetros desde terminal.
• time: time: Para cronometrar el rendimiento del sistema.

Como trabaja (secuencia).

El programa trabaja de manera sencilla, primero toma la imagen y la transforma a escala de grises dándole un formato como de blanco y negro, después binariza para reforzar el formato anterior y detectar mejor los puntos, lo que sigue es detectar los puntos y marcarlos con un cuadro de color amarillo, después se realiza un tipo grid en la imagen para poder revisar cada parte por separado como la imagen siguiente:

Despues se revisa cada espacio y se manda un 1 o un 0 dependiendo de donde haya un punto marcado esto se toma de la siguiente manera:

Ahora el programa nos mandara la cadena de la letra braille segun los puntos marcados por ejemplo en la anterior imagen seria así:

1011100

El programa mandaría un 1 en posición 1, 0 en posición 2, 1 en posición 3, así hasta completar la cadena, ya al final lo único que se hace es compara con la "base de datos" y encontrar la letra que es
 
Evaluación de desempeño.

Para las pruebas se utilizo un equipo Dell Inspiron mini 1012, las especificaciones de esta computadora son:

• Procesador: Intel Atom N450 (1667 MHz)
• RAM: 2 GB DDR2 (667 MHz)
• Tarjeta de video: Intel GMA 3150
• Sistema operativo: Ubuntu 12.04

Para analizar el desempeño lo que se realizo fue ver cuanto es lo que se tardaba el programa en identificar la letra braille, lo que se encontró fue lo siguiente:

Las imágenes que se utilizaron para encontrar esto fueron las siguiente:

letra 3

letra 2

Como podemos ver en la imagen de la corrida nos muestra que la que se tardo mas en realizar el proceso fue en la letra 3, pero porque sucede esto si son el mismo tamaño y la misma resolución.

Bueno esto se debe a que en el programa revisa cada espacio del grid que se realiza, como se menciono anteriormente, y tiene que revisar si hay algo en esa posición entonces tiene que pasar por todas las condiciones para poder mandar que si hay algo en dicha posición, con esto llegamos a la conclusión que mientras mas puntos se encuentren pegados mas se va a tardar el programa en realizar este proceso. Como lo es en el caso de la letra 3 donde en la posición 4, 5, 6 tienen un punto.
 
Pruebas.

Imagen original	Puntos encontrados	Resultado corrida

Como se puede apreciar toma mas tiempo en realizar si los puntos se encuentran mas pegados esto es por que esta checando si esta o no.

Aquí dejo esta imagen para que vean en conjunto con las imágenes anteriores si es que la letra que se dio es la correcta.

Trabajo a futuro.

• Mejorar la forma de detección de los puntos para poder leer un texto completo.
• Estaría bien implementarlo a un sistema android o IOS, para que con la cámara puede realizar este proceso.

Liga git:
https://github.com/nightkrowl/Visionfinal

Referencias.
[*] Reconocimiento Automático de Texto Braille, Héctor Ferraro,  http://revista.info.unlp.edu.ar/tesinas/tesis20.pdf

[*] Capítulo 3: O.C.R. para Texto Braille, J. L. Cantón Blanco, X. Fernández Hermida, F. Martín Rodríguez, http://webs.uvigo.es/gpi-rv/ficheros/pub/reports/braille.pdf

Laboratorio 12: Resumen

Ad Hoc Relay Wireless Networks over Moving Vehicles on Highways 

por Zong Da Chen, HT Kung, Dario Vlah

INTRODUCCIÓN

La conectividad inalámbrica en los vehículos se está convirtiendo en un importante modo de comunicación, ya, los grandes fabricantes de automóviles están lanzando servicios inalámbricos de bajo ancho de banda basados ​​en infraestructura en apoyo de las aplicaciones denominadas telemática del automóvil.

Las redes ad hoc formados por gran ancho de banda, los dispositivos inalámbricos de corto alcance, como el basado en el estándar de LAN inalámbrica 802.11, son muy adecuadas para los vehículos de transporte. Su despliegue en vehículos individuales no requiere ninguna infraestructura, también, enrutamiento ad hoc se adapta a la movilidad del nodo. Una serie de interesantes aplicaciones son posibles en este tipo de redes, que clasifican en tres grupos.

• Las aplicaciones tradicionales: incluyen todos los servicios populares de Internet como navegación, correo electrónico, streaming de vídeo web, etc. Estos pueden activarse de manera general al equipar vehículos con puntos de acceso para los dispositivos portátiles existentes, como cuadernos o PDA. Conectividad a Internet en su conjunto se puede lograr a través de nodos colocadas a lo largo de la carretera.
• Aplicaciones de localización las que proporcionan información sobre la ubicación geográfica de los puntos de interés para los usuarios.
• Aplicaciones localizadas se realizan en colaboración entre grupos de nodos cercanos, por lo que coincide con el modelo ad hoc.

En este trabajo se pone a prueba la hipótesis de que el movimiento de vehículos acoplados compuestos por una carretera puede contribuir significativamente a la entrega de mensajes con éxito, siempre que los mensajes pueden ser transmitidos almacenan temporalmente en mover nodos en espera de oportunidades que se envíen más. se tomo a prueba esta hipótesis mediante la simulación de la circulación de vehículos en una carretera, simulando una red ad hoc sobre los vehículos, y la medición del rendimiento de la red a medida que disminuye la densidad del tráfico.

Entorno de simulación

El entorno de simulación consta de dos componentes.

• El primero es un microsimulator de tráfico que produce trazas de movimiento precisos de los vehículos que viajan en una carretera. 
• El segundo es un simulador de red que modela el transporte de mensajes entre los vehículos.

Microsimulator de Trafico

CORSIM (simulador de pasillo) que se utilizo en este trabajo es un simulador de traffico microscópico desarrollado por la Administración Federal de Carreteras. CORSIM modela el comportamiento de los conductores humanos mediante la aproximación de un conjunto de decisiones comunes de un conductor, tales como la ralentización o cambiando de carril en las proximidades de vehículos más lentos por delante. Estas decisiones causan la aceleración y la orientación de los vehículos para cambiar, lo que resulta en patrones de movimiento realistas.

Hay tres entradas al simulador:

• Una geometría de la carretera: En la simulaciones es muy basica representada en la siguiente Figura, que es un segmento de carretera recta con dos direcciones, cada una compuesta de uno o más carriles.
• La velocidad de flujo libre: Es la velocidad media que los viajeros alcanzan cuando se mueven sin restricciones por otros vehículos u obstáculos. El parámetro de velocidad de flujo libre que se  utiliza en la simulaciones fue 50 mph.
• Una tasa de entrada: Controla el periodo en el que el simulador genera nuevos vehículos. Al final de cada período, un nuevo vehículo se coloca en uno de los puntos de entrada, pero sólo si se dispone de suficiente espacio en caso de congestión, no se generan nuevos vehículos.

Carretera Simulacion

La salida de cada simulación es un rastro de posiciones del vehículo tomadas a intervalos de un segundo. Todas las simulaciones duraron 300 segundos simulados. Se realizó un total de 170 simulaciones, de autopistas con uno a cinco carriles en cada lado, y las tasas totales de insumos que varían entre 5 y 800 vehículos por hora. Las densidades promedio de los vehículos observados en las carreras de simulación 170 se resumen en la siguiente tabla.

Simulador de red

Los mensajes se propagan con avidez cada paso de tiempo, saltando al vecino más cercano al destino. Esta cantidad de estado es suficiente para el propósito de encontrar el retardo debido a la movilidad.

Se describen dos tipos de patrones de transmisión de la red inalámbrica a la que llamaron el reenvío pesimista y optimista, que se distinguen por el tiempo que se permiten los mensajes a permanecer en los nodos intermedios.

• En reenvio pesimista, un mensaje cada vez que se cae no existe siguiente salto para su destino. Así es como funciona el reenvío en la mayoría de las implementaciones de red ad hoc.
• En el reenvío optimista, los mensajes sin saltos siguientes pueden permanecer en los nodos intermedios durante algún tiempo, con la esperanza de que el movimiento físico de los nodos de red con el tiempo crea una oportunidad de reenvío.

Configuración experimental

Para el experimento de esta sección, se utiliza el siguiente escenario de tráfico. Un solo paquete es enviado por cada vehículo entrando en la carretera. El destino del paquete es elegida para los 10 kilómetros de distancia, en la dirección del coche a entrar, sin embargo, si tal vehículo pasa a estar dentro de r de 10 km de distancia, y luego se envía ningún paquete. Se lleva a cabo las medidas de retardo en las huellas de carretera que hemos resumido en la Tabla 1, para el rango de radio r = 200m.


Comparando el optimista y el pesimista

La siguiente figura muestra el comportamiento de medida del retraso optimista y pesimista como la densidad de vehículos en las carreteras aumenta. A altas densidades, ambos retardos están cerca de cero, ya que la probabilidad de que un destino es inalcanzable es muy bajo. Sin embargo, el retraso pesimista se eleva más bruscamente que la demora optimista en caídas de densidad, lo que indica que la movilidad tiene éxito ayudando a la entrega de mensajes optimistas. Lo relevante de este resultado es que muestra que en una red de tomar ventaja de la movilidad del nodo puede operar en densidades más bajas mientras se mantiene el mismo retardo promedio.

Carreteras unidireccionales y bidireccionales

La siguiente figura muestra dos conjuntos de retrasos optimistas, medidos en las carreteras unidireccionales y bidireccionales. El retraso en cualquier densidad dada es menor para el tráfico bidireccional, lo que indica que el rápido movimiento relativo de los vehículos en dos direcciones hace una contribución significativa a la reducción de retardo de la entrega de mensajes.



Efecto del número de carriles

La siguiente figura muestra los retrasos optimistas medidos en las carreteras bidireccionales con 1 a 5 carriles. Es evidente que un pequeño número de carriles tienen un efecto perjudicial sobre el rendimiento de la red. Con un solo carril, inevitablemente hay vehículos lentos que acumulan colas de seguidores, y hacen que la distribución de vehículos se convierta en clúster. Un carril adicional crea la posibilidad de que los seguidores en cola puedan cambiar de carril y pasen los carros lentos. Sin embargo, a densidades medias esto puede no ser posible debido a que ambos carriles están ocupados en efecto, la parcela para una carretera de dos carriles exhibe un aumento en la demora para los valores de alta densidad. Con tres o más carriles, hay suficiente libertad de movimientos para evitar la agrupación, lo que lleva a disminuir retrasos.

Conclusión

Se encontró que la movilidad de los nodos de retardo de transmisión de extremo a extremo en carretera si se transmiten mensajes, si se llevaron a cabo en los nodos intermedios hasta que aparecieron caminos de reenvío favorables. La mejora lleva a valores de retardo prácticos en densidades de tráfico más pequeños que era posible incluso para los mensajes reenviados de forma pesimista, con información de enrutamiento ideal. Por lo tanto, la hipótesis inicial es válida.

Referencia:

[*]Zong Da Chen, HT Kung, Dario Vlah, Ad Hoc Relay Wireless Networks over Moving Vehicles on Highways, New York, NY, USA ©2001, http://www.eecs.harvard.edu/~htk/publication/2001-mobihoc-ckv.pdf

*Imágenes sacadas del pdf