Mostrando entradas con la etiqueta Teoria de la Información y Métodos de Codificación. Mostrar todas las entradas
Mostrando entradas con la etiqueta Teoria de la Información y Métodos de Codificación. Mostrar todas las entradas

miércoles, 29 de mayo de 2013

Assignment 6. Image Compression

For this week, we were assigned to implement a transform of compression image. In this oportunitty I apply the wavlets for compress the image and show the results.

Repositoty: https://gist.github.com/vane90/5670878

Pywavelets : 
I used pywavelets its a free open source wavelet transform software in python, it is very easy to use if I worked with 2D Forward and Inverse Discrete Wavelet Transform  but it includes, many other features you can look for more information about this library in the page official.

Instalation
The first thing we need to do in order to work with this tool is to install the Pack needed to be imported to our python script.


The pywt is an module needed to be able to work with the program that will show. It can be installed by using the next line code on any linux terminal


Why does the compression of images?
To compress images, we can reduce the redundancy, or the frequency of the image data in order to be able to store or transmit data in an efficient way.

Wavelet analysis can often compress or delete noise without appreciable degradation.

For this it can considere two methods of data compression and are classified into:
  • Lossless: it is the compression without loss of information
  • Lossy: it is the compression with loss of information.
Transformed Wavelet: 
This transform is efficient for local analysis of non-stationary signals quick transitoriness and, like the Fourier transfor with window, maps the signal into a representation. The temporary aspect of the signal is preserved.
 
The Wavelets, bases of the transformed Wavelet functions, are generated from a basic Wavelet function, through translations and dilations. These functions allow to reconstruct the original signal through the transformed Wavelet inverse in any case. 

Wavelet analysis is to decompose a signal into mobile scaled versions of the original wavelet ("mother"). The comparison allows to obtain coefficients that are susceptible of interpretation and subsequent manipulation. 
 
Descomposition wavelet:
In this case I use the transform of discrete wavelets (DWT): it will be used this transformed for a new representation of the image, more appropriate for the compression process. 
 
We choose a wavelet to work with it and we apply it, this will generate a array of coefficients, known as wavelet coefficients which are four: 

  • csA: Approximation Coefficient
  • csH:horizontal Coefficient
  • csV: vertical Coefficient
  • csD: diagonal Coefficient


We can then apply each of the coefficients to create new images that will show each detail contained in each coefficient.


This are the process for the compression to the image:


Step 1: This procces Convert the imagen to grey scale
First apply gray scale that already has been handled previously, this consists of adding the value of r, g and b of each pixel and take your average, finally is assigned the same value to each r, g, b). 




Step 2. Subsequently generated an array of the image to grayscale (in the new image became smaller, here the array is created for full-size image width by height):
 


Step3. Then we call the function coefficients, where we apply the function of the DWT (Discrete Wavelet transformed).

Use the dwt2 () function to apply this transform for 2 dimensions, it requires 2 parameters to work:
pywt.dwt2 (data, wavelet)

Data: Array with the information of the pixels.

Wavelet: We choose a wavelet in this case "haar".



Step4. Create an image for each coefficient. A first test print the array that returned coefficients are made and saw that numbers returning negative and greater than 255.

I need to apply a filter because the generating arrays from the coefficients contain negative numbers and numbers that pass 255 so this cant be included on and image, what we do is to create a filter any negative value will be 0 and any value that pass 255 will be 255 any other value will remain the same, after fixing the array we apply it to a new image generating the coefficient images.

Step5. The images are created

Approximation Coefficient


horizontal Coefficient
 vertical Coefficient


Diagonal Coefficient


6.Compressed Image


 
Compression level

Differences of what was the capacity of the compressed image to the original (image in grayscale) reduction:

Test 2: 

 Approximation Coefficient

 Horizontal
 Vertical
 Diagonal
Compress: 
 
Reference:

Filip Wasilewski, "PyWavelets - Discrete Wavelet Transform in Python", 31 de Agosto de 2012. [Accessed:  27 de Mayo de 2013], in http://www.pybytes.com/pywavelets/

TEORÍA DE WAVELETS, [Accessed: May 28th, 2013]
http://catarina.udlap.mx/u_dl_a/tales/documentos/lem/hernandez_d_m/capitulo2.pdf

Wavelet, [Accessed: May 27th,2013]
http://elisa.dyndns-web.com/~elisa/teaching/comp/vision/wavelet.pdf







Extra Point: Article of Bioinformatics

For this assignment we were asked to make a summary of an article related bioinformatics.

Article: 
An algorithm for constraint-based structural template matching: application to 3D templates with statistical analysis
Autors:
 Jonathan A. Barker∗,† and Janet M. Thornton


Introduction

This paper mentions about the diferents algorithms and methods based in  structural templates, that we can be use  in 3D templates.  Mention that in the biology exist diferent structures templates and function, the structural templates consist of atoms in a specific geometric conformation provide a powerful tool for studying the relation ship between protein structure and funcition. 

A small structural template,  for an active site typically consists of around ten functional atoms in a specific geometric shape. Usually there are no restrictions on the type of atom and, sometimes, sequential relations, exist methods for template searching constrain template syntax and semantics by their design. The real functional properties of a protein without doubt should be represented more easily by a good structure in 3D instead of just a sequence of 1D.

Several tools have been developed expressly for the purpose of seeking well-defined structural templates. For best results here is introduces Jess, a fast and flexible algorithm for searching protein structures for small groups of atoms under arbitrary constraints on geometry and chemistry.  

An alghoritm is the suite with SPASM and RIGOR allows a greater general coincidence of centroid Cα and positions. On the other hand JESS requires substantial pre-calculation and storage and also imposes more stringent limitations in the semantics of the template.

An other term, spoke about the best algorithm implement for  structural templates it is  the design of JESS (JESS is not an acronym, but that is so called in honor of his TESS predecessor, the T replaced by the first initial of the author of Jess) that they were guided by the following requirements:

1. Generality: JESS must be capable of processing a template that consists of arbitrary restrictions on physical, sequential and geometric properties. 
2. Compatibility: A large number of JESS and templates have been derived from SPASM and refined within our group. It would be desirable for JESS to be able to process these templates in order to extend their definitions to a later date. 
3. Standardization: In general, the templates have a wide variety specificity and selectivity.
4. Modularity: The internal design of JESS must be modular enough to allow the modification of the template syntax without significant re-encoding.

Mentions that the normalization is essentially a post-processing. In the case of the templates of JESS, the candidate sites are scored using RMSD after a optimal rigid overlap with the atoms in the template.

Algorithm 
The most important algorithm mention  is JESS, that describe the process of templates, geometric constraints are constructed by measuring pairwise distances between the atoms and allowing distance mismatches up to a maximum supplied as a parameter, it is consist: 


  • The atoms of T are thought of as variables t1,...,tn , the ordering being unimportant but held fixed throughout the computation. 
  • The task facing Jess is to find all possible assignments{t1←m1,...,tn←mn} of atoms in M to the template variables which simultaneously satisfy all the constraints in C. 
  • Problems such as this fall within the domain of constraint logic programming 

Define a partial solution as a set of assignments {t1←m1,...,tk←mk}with k≤n for which all constraints in C involving t1,...,tk alone are satisfied. . The basic method of solution is inductive; we assume a partial solution and attempt to extend it by fixing the assignment of one more variable.

Then we can construct all complete solutions to the problem using the next pseudocode: 


The core of Jess is a combination of a trace constraint solver and a comprehensive index of the query molecule. The constraint solver works in cooperation with a compiled template separately to find solutions in the system of constraints in an efficient manner.


Methods for Statical analysis

For work in a sigle template the statistical analysis is at least, in this case the results are directly comparable, but if we want to compare the results obtained with several templates, we have to take into account that have different specifications and the normalization of the results of different templates. 

As usual we constructed a non-redundant structure reference population R, and analyzes the distribution of the results obtained when R is polled with each of the templates.

Reference population
  • SCOP  and CATH, for example, provide lists of representatives at various levels of structural similarity. However structural classification takes place mostly at the domain level. 
  • For each of the structures classified in CATH we recorded domain composition at the H-level (homology)including multiplicity.
  • Thus, each structure is assigned a label in the form of a multi-set of domain codes. 

Fitting model distributions
In the same structure was used 186 enzyme active site templates, we probed the reference population described above. The results were collected on a per-template basis. Was used the Marquardt–Levenberg (ML) algorithm to fit normal distributions to cumulative frequency data and the Kolmogorov–Smirnoff test to assess the results. 

----------------------------------------------------------------------------------------------------------------------------------
Personal Conclusion 
The 3D templates are very important within the bioinformatics, because it helps in the prediction or calculation of the 3D structures of different proteins, in medicine for the design of drugs and biotechnology (in the design of new enzymes). 

In my opinion one of the major challenges of the structural bioinformatics is to provide good reliable statistical data for the measures of the structural similarity.


Reference to: 
Available at: http://bioinformatics.oxfordjournals.org/content/19/13/1644.full.pdf [Accessed in 28 May 2013]


jueves, 9 de mayo de 2013

Code Block

This week we are assigned to make a way to check if a string or text or text string is transmitted correctly.

The idea is to use HAMMING BLOCK CODES.

The hamming code allows us to find errors in a text received by a string of 4 bits (7x4). This indicates that it will be a string of four bits that represent something as numbers or letters and is accompanied with 3 digits its parity bits.



Hamming algorithm (7X4) can correct any single bit error, but when there are errors in more than one bit, the transmitted word is confused with another with a single bit error being corrected, but incorrectly, ie that the word is not correct other than the original, and the final message is wrong without knowing it. 

The key to the Hamming Code is the use of extra parity bits to allow the identification of a single error. Create the code word as follows:
  1. Mark all bit positions that are powers of two as parity bits. (positions 1, 2, 4, 8, 16, 32, 64, etc.)
  2. All other bit positions are for the data to be encoded. (positions 3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 17, etc.)
  3. Each parity bit calculates the parity for some of the bits in the code word. The position of the parity bit determines the sequence of bits that it alternately checks and skips.
    Position 1: check 1 bit, skip 1 bit, check 1 bit, skip 1 bit, etc. (1,3,5,7,9,11,13,15,...)
    Position 2: check 2 bits, skip 2 bits, check 2 bits, skip 2 bits, etc. (2,3,6,7,10,11,14,15,...)
    Position 4: check 4 bits, skip 4 bits, check 4 bits, skip 4 bits, etc. (4,5,6,7,12,13,14,15,20,21,22,23,...)
    Position 8: check 8 bits, skip 8 bits, check 8 bits, skip 8 bits, etc. (8-15,24-31,40-47,...)
    Position 16: check 16 bits, skip 16 bits, check 16 bits, skip 16 bits, etc. (16-31,48-63,80-95,...)
    Position 32: check 32 bits, skip 32 bits, check 32 bits, skip 32 bits, etc. (32-63,96-127,160-191,...)
    etc.
  4. Set a parity bit to 1 if the total number of ones in the positions it checks is odd. Set a parity bit to 0 if the total number of ones in the positions it checks is even.


Bibliografía
http://users.cs.fiu.edu/~downeyt/cop3402/hamming.html


 

jueves, 25 de abril de 2013

Tarea #4. Método adatpativo

For this week we ask you to make a coding algorithm based adaptive Huffman coding.

Try to modify my above code to make it adaptive only manage to finish a bit to read me the frequency of characters within a compressed textro something that was not yet finished.


Remembering some algorithm process:



1. We look for the frequency of unique characters in the text above.
2. Each of the characters is created as a tree and add them to a list, each tree has its associated symbol and frequency number.

3. The ordered from lowest to highest according to the frequencies.
4. From the above it will select the first two trees from the list and will form a new tree with them, before the tree will delete the two trees in the list. The root of the new tree will be the sum of the frequencies of the roots of the two trees to be joined and the trees will now child nodes of this. 
5. We add to the list the new tree created by ordering from low to high 
6. Already having obtained the tree end we have to begin to explore it in order to get the binary code of each of the characters, as we know is a binary tree that has the following tags that link one node to another.

Codigo




The idea to make a little adaptive was possible to continue updating the tree and updates during ordering property is maintained, for example, nodes (internal and leaves) were ordered according to increasing their weights.

When it is necessary to exchange the farthest node with a certain weight is exchange with the node whose weight is increased.

Be tree could be seen differently when exchanging nodes and perform better compression level and still have the same efficiency.


But the program didn't work :(



jueves, 11 de abril de 2013

Assignment 3. Text compression


For this assignment is necesary implement the tree-based Huffman coding for Unicode strings. 

This algorithm consists in the creation of a binary tree in which each of  the leaves contain a character string to compress with the frequency whit which it is repeated in the character string. 

Based on the assignment of codes to different bit length of each character composing a text string. If short codes are assigned to the characters that appear more often, you get a greater understanding of the text string.

Process
  I give the input character string, in this case use the next line of text for example:

Laptop nueva

1. Characters ordered from lowest to highest according to the number of times they are repeated.



2. We create a new tree root that contain the character with their respective number of frequency in the chain and insert the tree in a tree list.


3. Each of the characters as a tree is created and added to a list, each tree has its associated symbol and frequency number.

 
 4. From the above it will select the first two trees from the list and will form a new tree with them:

5. The root of the new tree will be the sum of the frequencies of the roots of two trees to be joined and tree are now child nodes 


6. It adds to the list the new tree created by ordering from lowest to highest

  
7.  It gets to select two trees from the list and will form a new tree with them, before the tree realiar delete the two trees of the list, until a single tree in the list. 



Not operate properly but here is some code that would make these processes. 




Continued...

Link
Huffman

jueves, 28 de febrero de 2013

Resumen. Suffix Tree

Reference to  "Algorithms on Strings, Trees, and Sequences" by Dan Gusfield.

Introduction

The string of lenght  m can be generated into m sufflix can be stored

  •  created this structure requieres time O(m)

  • for a parttner requieres tiimeO(n)
These two properties make the suffix tree an appealing structure for a diverse range of bioinformatics applications including: multiple genome alignment (Michael Hohl et al., 2002)

Biological Application

Genome Alignament

 Reference this book "Algorithms on Strings, Trees, and Sequences" by Dan Gusfield.

 At a least two programs based Suffix trees are available for whole gnome alignament. 

MUMmer and MGA both use common subsequences as anchors for the alignment. While they both use the same data structure:

MUMmer extracts Maximal Unique Matches (MUMs)  sequences that occur exactly once in each genome, sorts these sequences to find the longest set of MUMs occurring in the same order in both sequences, and uses this set of sequences to anchor the multiple alignment. 

For this the gaps between anchors are filled using the Needleman Wunsch dynamic programming alignment algorithm.  MUMmer is restricted to comparing two genomes.

The function

MGA computes the longest non-overlapping sequence of Maximal Multiple Exact Matches (multiMEMs) and uses these to guide the multiple alignment. A MEM is defined as a (K+1)-tuple (l, p_0, p_1, ... p_k-1) such that l indicates the length of the MEM, and p_i indicates the start coordinate of the exact match in genome i. A maximal MEM cannot be extended to the left or the right and is referred to as a multiMEM. Gaps are shortened by recursively extracting multiMEM sequences, and finally filled using ClustalW - a progressive/iterative multiple alignment method.

Bibliografia

Link1

jueves, 21 de febrero de 2013

Tarea2. Metodos de Codificación

Se realizo una simulación utilizando los métodos de búsqueda para palabras utilice el algoritmo de boyer-moore es el unico implementado.

Este algoritmo analiza la cadena de derecha a izquierda esto es eliminando el ultimo elemento del patrón de palabras después de esto se invierte este patrón y se van insertando todos los elementos que no esten en el patrón referente a la cadena de texto.

Y como resultado no obtuve nada porque aun no esta terminado :(

Código