Image Compression - Wavelets

For this post, show you how to work on image compression.

Waveletes
To accomplish this task using what are wavelets, which are a type of Fourier transform. The wavelet transform is to compare the signal with certain wavelet functions, which are obtained from the mother wavelet. The comparison allows to obtain the coefficients are interpretable and further manipulation.

PyWavelets
To carry out the compression used pywavelets which is a wave abirto code and serves to transform python. It is necessary to use this module you need to install pywt. To do this we can just download it from the terminal with the following line:

sudo apt-get install python-pywt

Process


To do this work with the Discrete Wavelet Transform, with which we obtain a new representation of the image to be treated.

Within this process the TWD provides a matrix of coefficients, which are the four wavelet coefficients:

1. approximations
2. horizontal coefficients
3. vertical coefficients
4. diagonal coefficients

In the following image shows how the coefficients are obtained:

Haar transform used to treat 2-dimensional images, which we use to get our 4 coefficients.

The process is performed as follows:

1.  Enter imgagen you want to compress
2.  After you get the size in bytes of the image from the original image
3.  We estimate each of the coefficients (approximations, horizontal, vertical and diagonal)
   
   

   	def coeficientes(matrix):#Obtener los coefficientes 2D
   	coeffs=pywt.dwt2(matrix,'haar')
   	cA,(cH,cV,cD)=coeffs#cA=approximacion,cH=Detalle horizontal,cV=Detalle vertical,cD=Detalle diagonal
   	return (cA,cH,cV,cD),coeffs

   view raw coeficientes.py hosted with ❤ by GitHub
4. After obtaining the coefficients, we apply them within a binary filter for so the new images.
   
   

   	def binario(mat):
   	ancho = len(mat)
   	alto = len(mat[0])
   	nuevo = 0
   	foto = Image.new('RGBA',(ancho, alto)) #nueva imagen
   	pixeles = foto.load()
   	for i in range(ancho):
   	for j in range(alto):
   	if mat[i,j]<0:
   	nuevo = 0
   	elif mat[i,j]>255:
   	nuevo = 255
   	else:
   	nuevo = int(mat[i,j])
   	pixeles[i,j] = (nuevo,nuevo,nuevo)
   	return foto

   view raw filtro_bin.py hosted with ❤ by GitHub
5. Also after that calculate the inverse image to apply the compression process.
   
   

   	def inversa(coeffis,escala):
   	inv = pywt.idwt2(coefficientes,'haar')
   	pixeles = escala.load()
   	ancho,alto = escala.size
   	for i in range(ancho):
   	for j in range(alto):
   	nuevo = int (inv[i,j])
   	pixeles[i,j] = (nuevo,nuevo,nuevo)
   	return escala

   view raw inversa.py hosted with ❤ by GitHub

Below will show some of the tests performed with different images.

Test 1:

Approximation coefficient   

Horizontal coefficient

Vertical Coefficient

Diagonal Coefficient

Finally this is the compressed image below shows the change that was from one image to another. (reverse image)

Here attached another test that you make with a different image which contained a little more color, and is slightly heavier than the first.

Test 2:

Approximation coefficient   

Horizontal coefficient

Vertical Coefficient

Diagonal Coefficient

And the reverse image

Conclusions

According to the tests you make think it depends on the weight of the image, so that when compressing it look as similar to the original, another thing I noticed is that it also depends on how well defined this image, because for example in the first test can fully appreciate the detail between one figure and another, while in the second test is different.

Another thing you can do is check if the compression works with images that contain a lot of noise and not lost many details of the original image. Below I made a small test this:

Test 3:

Approximation coefficient   

Horizontal coefficient

Vertical Coefficient

Diagonal Coefficient

And the reverse image:

And we see in this image with more noise, reduced compression almost the weight of the picture and not get upset too.

Here attached the code you use.

	import pywt
	from PIL import Image
	import numpy
	import os
	import Gnuplot
	from time import *
	def matriz(foto):
	ancho,alto=foto.size
	pixeles=foto.load()
	matrix=numpy.empty((ancho,alto))
	for i in range(ancho):
	for j in range(alto):
	(r,g,b)=foto.getpixel((i,j))
	matrix[i,j]=r
	return matrix
	def coeficientes(matrix):#Obtener los coefficientes
	coeffs=pywt.dwt2(matrix,'haar')
	cA,(cH,cV,cD)=coeffs
	return (cA,cH,cV,cD),coeffs
	def binario(mat,c,to,ti):
	ancho=len(mat)
	alto=len(mat[0])
	nuevo=0
	foto=Image.new('RGB',(ancho,alto))
	pixeles=foto.load()
	for i in range(ancho):
	for j in range(alto):
	if mat[i,j]<0:
	nuevo=0
	elif mat[i,j]>255:
	nuevo=255
	else:
	nuevo=int(mat[i,j])
	pixeles[i,j]=(nuevo,nuevo,nuevo)
	foto.save('coefficiente'+str(c)+'.jpg')
	def inversa(coefficientes,escala):
	inv=pywt.idwt2(coefficientes,'haar')
	pixeles=escala.load()
	ancho,alto=escala.size
	for i in range(ancho):
	for j in range(alto):
	nuevo=int(inv[i,j])
	pixeles[i,j]=(nuevo,nuevo,nuevo)
	return escala
	def main():
	img=str(raw_input('Nombre de imagen: '))#cargar imagen
	foto=Image.open(img)
	ancho,alto=foto.size
	f=os.stat(img)
	print f
	ti=time()
	tamano_original=f.st_size
	matrix=matriz(foto)
	coe,coeff=coeficientes(matrix)
	nueva_imagen(coe,tamano_original)
	foto=inversa(coeff,foto)
	foto.save('Inversa.jpg')
	f=os.stat('Inversa.jpg')
	tamano=f.st_size
	porcentaje=(tamano*100)/float(tamano_original)
	print "Resultado de imagen"
	print "Tamano Imagen original:"+str(tamano_original)+"bytes"
	print "Tamano con compression:"+str(tamano)+"bytes"
	print "Porcentaje de compression:"+str(100-porcentaje)+"%"
	print "Tiempo de compression: "+str(tt)+"segundos"
	print "-------------------------------------------"
	main()

view raw wavelets.py hosted with ❤ by GitHub

References

• http://en.wikipedia.org/wiki/Haar_wavelet
• http://www.pybytes.com/pywavelets/
• https://en.wikipedia.org/wiki/Wavelet_transform

Extra Points - Bioinformatics

Identifying DNA and protein patterns with statistically significant alignments of multiple sequences

Autors: Gerald Z. Hertz and Gary D. Stormo

This paper talks about what is expected to occur in DNA sequences.

It shows an example where you can expect a protein can bind two DNA sequences related. This pattern is identified by a pattern containing shared by a group of related sequences, and are also identified during the process of alignment of the sequences in order to maximize a sequence.

The objective of the model is to summarize the alignment for the set of sequences can be described in a more concise. The simplest method is the consensus sequence, which contains the most highly concervadas letters in each position of the alignment.  However, some letters may occur more frequently than others.

The interest of this study is focused on the sequences that are related by common function. Therefore, we use a matrix model Which does not include phylogenetic information.

One of the simplest types is the alignment matrix, which lists the number of occurrences of each letter in each position of alignment, for example Figure 1a. Another type of matrix, is the matrix of weights, which uses the weights used to mark a test sequence to measure how close the word sequence matches the pattern described by the matrix. (Fig. 1b)

Arrays can also describe more complex patterns containing gaps. However, in this work only interested in sequences that can be aligned without incersiones and deletions.

A good alignment is assumed to be one Whose alignment matrix is rarely expected to Occur by chance. A standard statistic for scoring the relative likelihood of an alignment matrix is the log-likelihood ratio. We compare alignments using a variant of the log-likelihood ratio we call information content and determine alignments from functionally related, unaligned sequences using a greedy algorithm.

In this paper, we present an efficient method for calculating the P value of an information-content score. In our case, the P value is the probability of obtaining an information content greater than or equal to the observed value, given the number of sequences in the alignment and its width. This method combines numerical calculations with a technique from large-deviation statistics.

Information content of an alignment matrix

In our comparison of alignment matrices, we assume that the letters of a sequence are independent and identically distributed. Thus, the a priori probability of a sequence of letters is the product of the a priori probability of the individual letters. The a priori probability of the individual letters might be the overall frequency of the letters within all sequences of an organism.

Given the assumption that the distribution of letters is independent and identically distributed, the probability of an alignment matrix is determined by the multinomial distribution:

where i refers to the rows of the matrix (e.g. the bases A, C, G, T for a DNA alignment), j refers to the columns of the matrix (i.e. the positions of the letters within the alignment pattern), A is the total number of letters in the sequence alphabet (four for DNA and 20 for protein), L is the total number of columns in the matrix (six in Figure 1), pi is the a priori probability of letter i, ni, j is the occurrence of letter i at position j, and N is the total number of sequences in the alignment (four in Figure 1).


The most commonly used measures for scoring the divergence from the a priori probabilities of a set of letters are the χ2 statistic and the log-likeli-hood ratio. In our work, we use statistics based on the log-li-
kelihood ratio rather than the more ad hoc χ2 statistic. The standard log-likelihood ratio statistic is

When motivated by information theory, this formula is called the Kullback–Leibler information (Kullback and Leibler, 1951) or relative entropy. When derived from large-deviation principles, it is called the large-deviation rate function (Bucklew, 1990). 

The P value of an information content

We ultimately wish to calculate the P value of the statistic, i.e. the probability of observing an alignment having the observed information content or greater, given the width of the alignment and the number of sequences in the alignment. Thus, the null model for the alignment matrix is that the distribution of letters in each alignment column is an independent multinomial distribution [formula (1)].


Under the above assumptions, when the information content is small and the number of sequences is large, 2NIseq tends to a χ2 distribution with L(A – 1) degrees of freedom since –NIseq is a log-likelihood ratio (discussed in many introductory statistics books). Unfortunately, our conditions generally involve very large scores and frequently few sequences; thus, the χ2 distribution tends to give poor probability estimates.

However, we are able to obtain very accurate estimates of the P value using a technique from large-deviation statistics.

A large-deviation technique for approximating P value



Applying the large-deviation technique to multiple sequence alignments

To apply the techniques described above, we need to be able to calculate efficiently the moment-generating function M(θ) and its first two derivatives M′(θ) and M′′(θ) for the statistic of interest. In this subsection, we describe these calculations for the statistic NIseq, where N is the total number of sequences in the alignment and Iseq is the information content statistic defined in formula (2).

Since we restrict ourselves to simple alignment models in which each column is independent, the moment-generating function only needs to be calculated for a single column since the overall moment-generating function is only dependent on Mc , the moment-generating function for an individual column, and L, the width of the alignment:

By the definition in equation (3), the moment-generating function for NIseq for an individual column is:

where ni is the occurrence of letter i. The outer summation is taken over all combinations of the ni summing to N. The total number of such combinations is (N + A – 1)!/N!/(A – 1)!, i.e. O(N A – 1).
A brute force calculation for M(θ) involving all these combinations is not too bad for a DNA alignment
where A = 4, but is unacceptable for proteins where there are 20 letters in the amino acid alphabet. Therefore, we use the following dynamic programming algorithm, whose complexity is only O[(A – 2)N 2] in time and O(N) in space.


Approximating the P value numerically

In this section, we describe an alternative method for approximating the P values of NIseq. This method creates a table of P values for the statistic after it has been transformed into integer values. The statistic NIseq is transformed into an integer value I′ after multiplying NIseq by some factor α:

in which the ‘int’ function rounds a real number to its closest integer. α is chosen so that the maximum ( I Ȁmax ) and minimum ( I Ȁmin ) values of I′ differ by some desired amount. The greater the difference between I Ȁmax and I Ȁmin , the more accurate the estimation of the P value.


Algorithms for determining the alignment having the optimum information content

Our ultimate goal is to apply our models and statistics for sequence alignments to identify optimal alignments and determine consensus patterns describing functional relationships.

The goal of all these algorithms is to determine a sequence alignment that maximizes a log-likelihood statistic. In this section, we describe the current version of our greedy algorithm.

Here, we describe two related alignment algorithms that are order independent. The first algorithm,  requires the user to specify the width of the pattern being sought based on previous biochemical knowledge. The second algorithm determines the width of the alignment, but requires that the user adjust a bias that is subtracted from the information content so that the average score is negative.

Fig. 2. An example of the algorithm for finding sequence alignments of a fixed width, assuming each sequence contributes exactly once to the final alignment. Alignments of width 4 are being sought from the three single-stranded DNA sequences listed at the top. Each base has an a priori probability of 25%.

The user specifies the width of the alignment

The user first designates the maximum number of alignments that can be saved (e.g. 100 or 1000). Typically, less alignments are ultimately saved because some will be identical. Besides the width, there are various constraints the user can impose.

The user specifies a standard deviation bias

A similar algorithm in which the user does not explicitly specify the width of the alignment. A property of the information content is that it is always non-negative. However, for this local alignment algorithm to work, we need the score to be negative on average so that an interesting alignment can appear as a region of positive information. 

Fig. 3. The ratio of the P value calculated by the large-deviation (LD) method to the P value determined numerically (NUM) for various values

of NIseq. The horizontal axis is the numerically determined P value, which is assumed to be accurate. The vertical axis is the ratio.

Results

The accuracy of the P value approximations

The large-deviation method for determining the P value was compared to the numerical method. As expected, because the estimate of Pγ () is based on the Central Limit Theorem, the accuracy of the large-deviation method increases as the width of the alignment increases.

Information content and related statistics have proven their usefulness for identifying and analyzing sequence alignments (Schneider et al., 1986; Berg and von Hippel, 1987; Stormo and Hartzell, 1989; Hertz et al., 1990; Lawrence and Reilly, 1990; Lawrence et al., 1993).

However, a major deficiency has been the lack of an accurate measure of the P value of a particular information content. In this paper, we use large-deviation statistics and an efficient algorithm for determining the moment-generating function to estimate the P value of an information content accurately. The large-deviation approach is also applicable to the scores of weight matrices.

 

My Contribution

My contribution to this work, is that I think you could apply a bit more testing and check if it really is feasible to apply to sequences that have a wide or a long too big.

To understand a little more about the analyzes that are performed below left a direct link where they can find the full paper, plus graphs containing more tests.

PAPER: Identifying DNA and protein patterns with statistically significant alignments of multiple sequences

References

Hertz, G. and Stormo, G. (1999) Identifying DNA and protein patterns with statistically significant alignments of multiple sequences. February 22, p.15.

Lab #14 Reflexionando...?

Mi trabajo en el proyecto...

Bueno, puedo decir que desde un inicio, comencé aportando ideas para lo que seria el proyecto, algo que pues usualmente no me sucede.. xD

Durante la organización y evaluaciones del proyecto me hubiera gustado que existiera mas comunicación entre todos para realizar mejor las pruebas de usabilidad y demás cosas que se realizaron.

Nuestro trabajo como equipo..

En esta parte creo que nos falto un poco mas de organización y planificación de las cosas, porque? pues porque al momento de hacer el proyecto se nos presentaron varios problemas que, ya por cuestiones de tiempo no pudimos solucionar de la mejor manera y creo que pues si lo hubiéramos organizado y planificado mejor  nos hubiera dado mas tiempos para poder resolver adecuadamente los problemas que aparecían durante la construcción del prototipo y esas cosas.

A pesar de que nos falto esto, como quiera nos guiamos en lo que inicialmente se había acordado, alomejor no fue lo mejor y lo que realmente necesitamos fue ir revisando las tareas o metas que ya teníamos y planear algunas nuevas y fue algo que no hicimos.

Mejore o empeore?

Bueno en lo personal, creo que mejore un poco mi forma de trabajar ya que desde un principio me fije la idea que quería lograr. Con esto se me hizo mas fácil ubicar los materiales con tiempo, y respecto a esto no tuvimos dificultades. 

Aunque aun me falta mas organización y planificación  ya que en ocasiones le dedicaba mas tiempo a algo simple que salia rápido  en lugar de dedicarle mas tiempo a las cosas que tal ves importaban mas. Otro punto fue que no planifique bien mis otras clases, y pues si me afecto un poco.


Conclusión

Bueno pues espero tomar en cuenta muchos de los tips que los compañeros expusieron en las presentaciones de sus proyectos, creo que me ayudarían mucho a tener una mejor organización  y esto no solo aplicaría para mi si no que también para mis próximos trabajos en equipo.

Lab #13 - Retro-alimentacion Proyectos Finales

Proyecto: Seguri-Lap           Equipo: (Ave, Pedro,Jona, Obed)

Este proyecto es una buena idea, me parece que la manera en que la presentaron esta bien, aunque como ellos mismos lo mencionan les falto un poco mas de organización y comunicación como equipo. Esto es muy importante ya que alomejor si hubieran tenido mas comunicación se hubieran agregado mas cosas al proyecto y hacerlo mejor.



Proyecto: Car NxP                Equipo: (Juan, Abraham, Davidd, Rafa)

Este proyecto me parece que esta bien presentado, aunque hubiera estado mejor ver un poco mas de integración en lo que fue en si el proyecto para poder apreciar que era lo que se buscaba. Importante hacer un demo.
También que traten de tomar en cuenta para algún proyecto futuro, los tips que explicaron dentro de su presentación, creo que esto les ayudaría mejor a solucionar los problemas que se les presentaron.

Proyecto: Despertador Inteligente     Equipo: (Roberto,Cecy, Ramon)

En este proyecto se tuvo una buena presentacion y una buena demostracion, solo que me hubiera gustado ver que se tuvieran algunos tipos diferentes de tonos de alarma segun el tipo de persona. 

Proyecto: Casa Segura           Equipo: (rene,ivan, Raul)

Este proyecto en general es una buena idea, y que se puede decir que tiene futuro, pero falto algo mas de organización  Ademas de que creo que se debieron informar un poco mas en como poder armar un prototipo simple de lo que querían.

Proyecto: Garage Inteligente     Equipo: (Emmanuel, Victor, Carmen, Max)

Me pareció buena idea eso de solo simular el garage a mi parecer esta mejor eso que no presentar nada.

Proyecto: Auto Inteligente      Equipo:(Roberto,Sergio, Cris, Alex)

Creo que para este equipo al igual que los anteriores les falto un poco mas de organización  y plantear bien las ideas y las fechas de lo que se iba a hacer, creo que no necesariamente necesitaban hacer un demo en tamaño real, ya que pudieron haber utilizado algún carro de juguete o algo que se le pareciera.

Proyecto: Localizador             Equipo:(Omar,Isaias,Saul)

Yo creo que para este proyecto hubiera sido mejor mostrar un poquito mas de información de lo que se realizo, ademas de que creo que deberían mejorar su presentación del demo en vivo, a mi parecer quedo un poco al aire.

Proyecto: Oficina Inteligente            Equipo: (Triana,Osvaldo,Esteban)

Por lo que vi en la presentación de este equipo, creo que cada integrante trabajo bien pero de manera individual, cosa que tal vez les afecto un poco, creo que si esta bien el trabajo individual pero el trabajo en equipo también es importante y pues el hecho esta en los resultados que obtuvieron y lo que les falto implementar.


Conclusión General

Creo que a la mayoría de los equipos, (incluido el mio)  les hizo falta mucha organización y planificación  ademas de una buena integración de cada uno de los integrantes del equipo. Otro punto importante es que hubiera estado bonito que mínimo cada equipo trajera una simulación de lo que era su proyecto.

Lab #12

Plan de negocios

Licencia Inteligente

Descripción del articulo:

Este articulo es similar a las licencias comunes solo que contara con un dispositivo, que permitirá identificar al conductor y registrar las faltas que el conductor realiza durante un determinado tiempo. Al momento de acumular cierta cantidad de faltas la licencia informara de manera electronicamente que el usuario necesita hacerse cargo de las faltas que cometió o informar si es necesario renovar el permiso para conducir.

Finalidad:

La finalidad de este producto es minimizar las irregularidades que se cometen al haber faltas al manejar. Ademas de que este sea no solo una licencia, si no que también sirva como manera de identificar la persona que conduce el auto ya sea en carreteras de paga, etc..

Mercadeo:

El producto a vender sera mas que nada la tarjeta (licencia). 

Clientes:

La idea de este producto es que sea utilizado en las ciudades donde existe un amplio manejo vehicular, para tener un mejor control y evitar que se cometan irregularidades dentro del sistema.

Desarrollo y Producción:

Para desarrollar este producto sera necesario las siguientes herramientas:

• Chip RFID
• Algún lector de la tarjeta
• Tarjeta 

En cuanto a software se refiere es necesario desarrollar una base de datos para almacenar los datos de cada conductor ademas de que también tendrá un registro para las faltas que este cometa.

Distribución:

La manera de distribuir este articulo seria al momento de tramitar la licencia para conducir, principalmente se tratara de que este articulo sea hecho de un material que sea de fácil manejo para el usuario. Y que en caso de robo o perdida poder reemplazarlo.

Proyecciones Financieras:

A continuación se mostrara una estimación de los posibles gastos y recaudaciones.

Se tiene estimado que el precio en que se dará esta licencia al publico sera similar al que alctualmente se cobra al momento de realizar este tramite.

Proyecto Final

Lab #11

Sugerencias de Privacidad

Auto Inteligente

Para este proyecto me parece que es importante que revisen bien la forma de conexión para que realmente aseguren al usuario que sus datos/información esta protegida.

Seguridad de Computadora

En este proyecto no se manejan muchos datos, aquí lo importante es cuidar la identidad del usuario ya que como se manejan imágenes de los rostros, es importante que se tenga una buena seguridad en cuanto al lugar donde se almacenaran estos datos, ya que actualmente se da mucho el robo de identidad. 

Oficina Personalizada

Para este proyecto la manera en que marcan la seguridad queda a mi parecer un poco al aire, ya que se me haría un poco mas seguro de que si se le entrega una llave de acceso a cada usuario, estos tengan un tipo de registro único para que solo sea de ellos y no se pueda transferir y así evitar el robo o perdida de información.

Localizador

En cuanto a este equipo se refiere yo creo que explicaron bien que es lo que se busca hacer para proteger los datos que se utilizan dentro de su proyecto. Y también seria buena idea manejar algún tipo de aviso de privacidad para el usuario.

Cama Inteligente

En este equipo también se tiene bien planteada la manera en que se manejara la seguridad  lo único es que también se le avise al usuario sobre estas políticas de privacidad y que revisen si todo esto esta funcionando de la mejor manera y no hay escapes de información.

Garage Inteligente

Para este equipo mi recomendación seria que revisen bien el registro de datos que se tendrá y ver que tan seguro es ya que es posible que en cualquier momento cualquier persona ajena tome el control y pueda entrar por el garage esto implicaría muchos riesgos.

Casa Inteligente

En este proyecto a mi parecer creo que es necesario fijar antes que nada que datos son los que se manejaran y revisar si es muy necesario implementar algún método de seguridad, para proteger al usuario. Yo creo que este proyecto implicaría el manejo de mucha seguridad ya que esta enfocado a una casa habitación lo que lo hace que el usuario quiera estar seguro en todo momento.

Car NXP