I S E L INSTITUTO SUPERIOR DE ENGENHARIA DE LISBOA Departamento de Engenharia de Electrnica e Telecomunicaes e de Computadores MESTRADO EM ENGENHARIA DE ELECTRNICA E TELECOMUNICAES Codificao de Sinais Multimdia Trabalho Prtico N 1 (RLC e HUFFMAN) Antnio Machado N 11586 Semestre Vero 2012 Trabalho prtico N 1 -CSM Pg. 2 Antnio Machado N 11586 ndice Geral 1Introduo ......................................................................................................................................... 4 2Desenvolvimento.............................................................................................................................. 6 2.1RLC ............................................................................................................................................ 8 2.1.1Codificao RLC ............................................................................................................... 9 2.1.2Descodificao RLC........................................................................................................ 11 2.2HUFFMAN .............................................................................................................................. 13 2.2.1Codificao Huffman ...................................................................................................... 15 2.2.2Descodificao Huffman ................................................................................................. 19 3Resultados ....................................................................................................................................... 21 4Concluses ...................................................................................................................................... 23 5Bibliografia ..................................................................................................................................... 25 6Anexo A .......................................................................................................................................... 26 Trabalho prtico N 1 -CSM Pg. 3 Antnio Machado N 11586 ndice de Figuras Figura 1 Processo de Codificao/Descodificao ............................................................................. 7 Figura 2 Codificao RLC .................................................................................................................... 9 Figura 3 Descodificao RLC ............................................................................................................ 12 Figura 4 Codificao HUFFMAN ...................................................................................................... 15 Figura 5 Codificao HUFFMAN ...................................................................................................... 19 Trabalho prtico N 1 -CSM Pg. 4 Antnio Machado N 11586 1Introduo Noprocessamentodigitaldeimagens,umdosmaioresdesafiosconsisteemreduziragrande quantidade de bytes necessrios para armazenar ou transmitir distncia uma imagem digitalizada. Asoluoconsistenautilizaodetcnicasdecodificaoquetirempartidodascaractersticas estatsticas da imagem, eliminando eficientemente a informao redundante. Ointeressepelastcnicasdecompressodeimagensremontapocadastcnicasanalgicas, actualmente,comapopularidadedossistemasmultimdiaquenecessitamdatecnologiade compresso de imagens parase tornaremviveis, esteinteresse cadavez maior.Como exemplo destasnovasaplicaes,podemoscitaravideoconferncia,oenviodearquivosdevdeovia Internet, a televiso digital de alta definio, etc. O objetivo principal dacodificao de imagens representaruma imagem usando um nmerode bitstopequenoquantopossvel,preservandoonveldequalidadenecessrioparaumadada aplicao.Acodificaodeimagenspossuiduasprincipaisaplicaes:areduodabanda requerida por sistemas de transmisso de imagens digitais (por exemplo em televiso digital, vdeo conferncias,etc.),eareduoderequisitosdearmazenamento(porexemplo,nareduodo espao necessrio para o armazenamento de dados de imagens usadas em vdeos digitais). [1] Algumas aplicaes exigem que o processo de compresso e descompresso seja livre de perdas de informao.Emimagensmdicasporexemplo,sehperdadeinformaopodehaverum comprometimento daprecisododiagnstico,omesmoocorreemaplicaesmilitares,ondeum pequenodetalhe pode conterumagrandequantidade deinformaessobre osrecursosdasoutras foras. Existem tcnicas especficas para a compresso sem perdas de dados de imagens digitais, os quais apresentamcaractersticasmuitoparticulares,comoaaltaredundnciaentrepixeisadjacentes, estas tcnicas exploram principalmente, essa redundncia. Trabalho prtico N 1 -CSM Pg. 5 Antnio Machado N 11586 Neste trabalho foi desenvolvido em MATLAB cdigo para a compresso e descompresso atravs dosalgoritmosconhecidosRLE,eHUFFMAN,tentandoumcompromissoentrecompressoe velocidade. Foi feita uma interface grfica apenas para serem mais simples os testes com diversos ficheirosnoinfluenciandonaperformancedecadaumadasrotinasdecodificao.Ocdigo, encontra-se integralmente reproduzido no Anexo A deste documento. Talcomoteremosoportunidadedeverificar,o MATLABnoaferramentaidealparaefectuar este tipo de compresso, pois o seu sistema de converso entre vrios formatos de variveis no o mais eficaz. Um sistema no didtico teria de ser implementado com algoritmos em linguagens de mais baixo nvel, para ser suficientemente rpido. No entanto dada a facilidade de utilizao, esta a linguagem de simulao mais usada, e serve perfeitamente para efectuar as provas de conceito. Trabalho prtico N 1 -CSM Pg. 6 Antnio Machado N 11586 2Desenvolvimento Osrecursosnecessrios paraarmazenaretransmitirimagenssoimensos,oquetornaatractivaa compressodeimagem,estabaseia-senaremoodeinformaoredundanteexistente.Existem duas categorias de compresso de imagem: Nodestrutiva-possvelreconstruirexactamenteaimagemoriginalantesdetersido efectuada a compresso. Destrutiva - com o processo de compresso so perdidas caractersticas das imagens, o que permite obter graus de compresso mais elevados. Nestetrabalhoserabordadaapenasacategoriadecompresso nodestrutiva,tambm chamada de compresso sem perdas. Sen1en2foremduasrepresentaesdamesmainformao,ograudecompresso(CR)dado por: CR = n1n2 (1.1) A redundncia relativa RD pode ser definida por: R = 1 1CR(1.2) Uma imagem gera um conjunto (L) de mensagens, rk, com k = 1, ..., L, com probabilidades pk,com k = 1,..., L. A informao Ik associada com rk definida como: Ik=-Iog2pk(1.3) A Entropia (H) de uma fonte de informao definida como sendo a informao mdia gerada por esta fonte: [2] Trabalho prtico N 1 -CSM Pg. 7 Antnio Machado N 11586 E = log2pkLk=1(1.4) A Entropia de uma fonte fornece o nmero mnimo de bits necessrios para codificar a informao geradapor estafonte. De acordo como Teorema daCodificao deShannon possvel codificar sem perdas, a informao gerada por uma fonte com entropia de H bits, usando em mdia H+ bits por mensagem, onde > = 0. Paraumadeterminadaimagemcomnbitsporpxel,seapsumprocessodedescorrelaoos dadosobtidosnoforemuniformementedistribudos,aentropiadestesdadosserinferioraosn bits por pxel da imagem original. O processo a seguir na execuo deste compressor/descompressor foi para ambos os mtodos o que se mostra na Figura 1Tabela 1. Figura 1 Processo de Codificao/Descodificao Imagem original do ficheiro lido Compresso RLC HUFFMAN Ficheiro Comprimido Descompresso RLC HUFFMAN Imagem original do ficheiro lido Trabalho prtico N 1 -CSM Pg. 8 Antnio Machado N 11586 2.1RLC ACodificaorun-length uma codificaoporentropia.Parte dosdados daimagempodemser comprimidosatravsdasupressodesequnciasdosmesmosbytes.Estassequnciasso substitudas por um nmero de ocorrncias e um smbolo padro para anotar a repetio. Obviamente, o factor de compresso alcanvel depende dos dados de entrada. Usando uma marca deexclamaocomoflagespecialparaindicaracodificaorun-length,mostra-sedeseguida como um fluxo de dados pode ser comprimido substituindo a sequncia de seis caracteres "H" por "!6H": Dados originais: UHHHHHHIMMG1223 Dados comprimidos: U!6HIMMG1223 Estatcnicanodeveserutilizadaparasequnciasdecaracteresmenoresquetrs,istoporque nenhumacompressoseriaobtidanessecaso.Porexemplo,substituindoasequnciadedois caracteres "M" com o cdigo run-length "!2M" aumentaria o tamanho do cdigo em um byte. Se a flagespecialnoexemploocorrernosdados,eladevesersubstitudaporduasmarcasde exclamao (byte stuffing). [3] Oalgoritmoapresentadoacimapodeserfacilmenteoptimizado;porexemplo,emvezde sequnciassimplesdecaracteres,podem-seusarpadresdediferentescaracteres,quepodem tambmsersubstitudos.Estaextensorequerqueotamanhodasequnciasejacodificado,ou utilizado uma flag especial de fim. Existem diversas variaes da codificao run-length, sendo que nestetrabalhofoiusadaumadelas.Estemtodostrazganhosrelevantessehouvergrandes agrupamentos de smbolosiguais,eas principais aplicaes domtodo, soemimagens binrias, imagens com grandes espaos envolvendo uma s cor e em imagens geradas por computador, onde os dados esto agrupados de forma mais geometricamente definida. Trabalho prtico N 1 -CSM Pg. 9 Antnio Machado N 11586 2.1.1Codificao RLC Nafiguraseguinteapresenta-seumecranretiradodaaplicaodesenvolvidaaquandoda codificao do ficheiro lena.tiff Figura 2 Codificao RLC function btnCod_RLC_Callback(hObject, eventdata, handles) fid = fopen('Imagem.org', 'r'); [x,countOrg]=fread(fid,'uint8'); .. data=rlc_Codificar(x,nbits); .. fid = fopen('Imagem.rlc', 'w'); .. end Nafunoexecutadapelobotodecodificao RLCabre-seoficheiro e envia-se ovector numa linha paraafunodecodificao.Esta devolvetambmumvectorcomacodificao efectuada parase fazer a gravao do ficheiro. Importasalientar que enviada para a funo de codificao tambmumparmetronbits,queserveparaindicarqualquernmerodebitscomoqual pretendemos fazer a codificao. Trabalho prtico N 1 -CSM Pg. 10 Antnio Machado N 11586 Talcomojfoireferidoacima,oalgoritmorelativamentesimpleseocdigodesenvolvidona funoRLC_Codificarestcomentadoporformaaserfacilmentepercebido.Noentantoha salientar que foram efectuadas algumas modificaes para o algoritmo poder efectuar compresses enuncafazerexpansesdoficheiro,etentaramaiorrapidezpossvel,tendoematenoquea linguagem MatLab tem as suas limitaes neste aspecto. feito o clculo do tamanho do vector x a codificar, e alocado o espao para a resposta, para ser mais rpido. tam=size(x,2); comp = zeros(1,tam); Percorre-se todo o vector at ao penltimo byte e faz-se a comparao com o simbolo seguinte para ircalculandoasquantidades,tendocomolimitaoatalquantidadedebitsquedeincio imposemos.for i=1: tam-1 % Percorre at fim do ficheiro-1 if x(i)~=x(i+1) || qt > nMax% Compara o elemento com o seguinte comp(z)=x(i);% Se for diferente coloca o elemento nos z=z+1;% dados codificados (garante que pode ser usado com qq n de bits (2^bits) Umadasoptimizaesefectuadasnocodificadortemavercomaformacomoeleguardaos elementoscodificados.Emvezdeusarahabitualflag,quantidadeesimbolo,usaapenasuma quantidadenegativa.Comosabemospartidaqueestamosalerimagenseossmbolosso numricospositivos,entoaocolocarumvalornegativosabemosqueelerepresentauma quantidade,dispensamosassimaflageconsequentementeotamanhodoficheirocodificado reduzido. if qt>1 % Se j temos quantidades vamos escreve-las nos comp(z)=-qt;% dados codificados, como valores negativos, evitando z=z+1;% mais caracteres no ficheiro. Consegue-se assim obter end % sempre compresso do ficheiro. qt=1; else qt=qt+1; end end Trabalho prtico N 1 -CSM Pg. 11 Antnio Machado N 11586 Seutilizasemosumvalormximofixoparaasquantidadesquecadasimbolosepodiarepetir, poderamos ter um problema de codificao, aqui que o nbits entra, fazendo com que quantidades grandesfiquempartidasemduasrepresentaes.Porexemplo,casoumsmbolosejarepetido 300 vezes consecutivas, e o valor de nbits seja 8, ento a sua codificao passar a ser -255-45. Nunca se fazem codificaes de smbolos se eles se repetirem apenas at duas vezes, escrevendo-os directamentenoficheiro.Nofinalcomopodemosterapenasquantidadesenoumsmbolo isolado,hqueescreveraquantidadeeessesmbolo,juntaroltimosimboloquenunca comparado, e por fim reduzir o tamanho do vector quantidade correcta. if qt>1comp(z)=x(tam-qt+1); % No fim do ciclo pode haver quantidades apenas z=z+qt-1;% h que escrever o simbolo e essa quantidadeend comp(z)=x(tam);% Escrever o ltimo smbolo, este nunca comprimido para ser mais rpido o algoritmo comp=comp(1:z); % Truncar os dados ao tamanho exacto end Destaformapodemosassimgarantirassimqueoficheirocomprimidosempremenorqueo original, ou igual se no houver repeties de caracteres. Tambm a descodificao do ficheiro fica garantida e de uma maneira bastante simples como veremos no subcaptulo seguinte. 2.1.2Descodificao RLC Na Figura 3 observamos o ecran de descodificao do ficheiro PBimage1.bmp, este ficheiro a preto ebrancoapenastemumacompressoelevadssima.NobotoComparaoteracertezaqueos ficheiros originais e descomprimidos, so rigorosamente iguais. if countOrg~=countDes msgbox('Os ficheiros no tm sequer tamanhos iguais.','Comparao de ficheiros','error','modal'); else if isequal(inOrg,inDes) msgbox('Confirma-se a inexistncia de perdas! (ficheiros iguais)!!!','Comparao de ficheiros','none','modal'); else msgbox('Os ficheiros tm o mesmo tamanho mas no so exactamente iguais.','Comparao de ficheiros','error','modal'); Trabalho prtico N 1 -CSM Pg. 12 Antnio Machado N 11586 Figura 3 Descodificao RLC Afunodedescodificaobastantesimples.Percorretodososdadosecadavez queencontra um valor negativo, escreve o simbolo seguinte essa quantidade de vezes. A nica optimizao feita, temavercomoprprioMatLab,eliminandoocicloFOR,esubstituindo-opelavectorizao, porque como se tinha referido, o grande trabalho foi feito na rotina de codificao. for i=1: tam % Percorre os dados comprimidos todos if x(i)>=0 Codigo(z)=x(i);% Se o valor positivo um simbolo z=z+1; else %for j=2:-x(i) % Se o valor negativo, uma quantidade %Codigo(z)=x(i-1); % Tem de se fazer a expanso do simbolo%z=z+1; %end Codigo(z:z-2-x(i))=x(i-1); % Assim mais eficiente no Matlab z=z-1-x(i);% para fazer a expanso end end Codigo=Codigo(1:z-1);% Truncar os dados ao tamanho exacto end Trabalho prtico N 1 -CSM Pg. 13 Antnio Machado N 11586 2.2HUFFMAN Esteumesquemadecodificaocomcdigosdecomprimentovarivelqueobtmomenor nmeromdiodebitsporsmboloquandonoexisteredundnciainter-pixeis.Oalgoritmode Huffman baseia-sena atribuio decdigos decomprimentovarivela cadaum dossmbolos deumaimagem. Agrandeaplicaodeste codificadoracompressode arquivos, e a criptografia de dados. [3] O tipo de compresso da informao est na atribuio dos cdigos mais curtos aos smbolos mais provveis nafonte,conseguindoassim areduodo comprimentomdiodas palavrasdecdigo associadas. Para a codificao, os smbolos so classificados numa rvore em ordem decrescente da suaprobabilidade. Os doissmbolos menos provveis soagrupadosemumpseudosmbolo cujaprobabilidade asoma dasprobabilidadesdossmbolos fundidos.Ossmbolos restantes so pseudosmbolos reclassificados de acordo com sua probabilidade, combinando dois a dois com o menos provvel e adicionando assuas probabilidades numpseudosmbolo novo. Oprocesso tem deserrepetido,atque todaarvoregerada,fiquereduzidaa umnico smbolocom probabilidade igualaum.Pararecuperar ainformaooriginal necessrioconhecero cdigo atribudo a cada carcter bem como o seu comprimento em bits. A ttulo de exemplo para codificar uma informao com os seguintes smbolos: NNBMDSMDANMBMBBMDNSMN Contar o nmero de ocorrncias de cada caractereD (3), S (2), A (1), N (5), B (4), M (6) Ordenar em ordem crescente de probabilidade (1) - S (2) - D (3) - B (4) - N (5) - M (6) So agrupados os dois primeiros ns (rvores) em uma rvore nova, adicionando a sua frequncias e soltando-os se necessrio Trabalho prtico N 1 -CSM Pg. 14 Antnio Machado N 11586 O processo repetido de uma maneira semelhante, at o n raiz conter o nmero total de caracteres O resultado final da construo da rvore ser Para a codificao dos smbolos assignam-se zeros aos ramos do lado esquerdo e uns ao lo lado direito, ficando ento Trabalho prtico N 1 -CSM Pg. 15 Antnio Machado N 11586 Ao reagrupar os cdigos, as palavras assignadas a cada smbolo so: A sequncia a comprimir Guardam-se assim 8 bytes dos 21 originais Calculando os valores de H e L temos: oH= 2.3983 bits/smbolo oL=2. 4286 Os valores de L e H esto prximos, o que indicia uma boa compresso. 2.2.1Codificao Huffman Na Figura 4 apresenta-se o ecran de codificao de uma imagem com o algoritmo de Huffman. Figura 4 Codificao HUFFMAN TalcomoaconteceunacodificaoRLCanteriormenteabordada,aformadefuncionamentoda aplicao a mesma. Trabalho prtico N 1 -CSM Pg. 16 Antnio Machado N 11586 Estealgoritmodescritomuitasvezescomosendoadequadorecursividade,noentantoneste trabalhofoiusado um mtodo no recursivo, que poder no ser mais eficiente,mas certamente mais fcil de entender. De forma genrica, o cdigo de Huffman pode ser representado por uma rvore onde: As folhas so os smbolos do alfabeto. Os ns intermedios so "smbolos de convenincia", introduzidos durante a construo do cdigo. Cada ramo associado com o bit 0 ou com o bit 1.O cdigo associado a cada smbolo a sequncia de bits associadosao caminho, da raiz at a folha. ParalidarcomestarvoreemMatlab,construiu-seumamatrizrepresentadacomNlinhas(N= nmerototaldens)e5colunas. Cada linharepresentaumn,eosignificadodascolunaso seguinte: A primeira coluna contm a probabilidade associada com o n (a probabilidade do smbolo se o n uma folha, ou a soma das probabilidades dos seus filhos, se o n intermdio). A segunda coluna o smbolo (representado por um inteiro positivo tal como no RLC). A terceira coluna contm o bit associado com o ramo que liga o n ao pai. A quarta coluna contm osmbolo associado como pai. Paraonraiz (que no tem pais, esta coluna fica com -1). A quinta coluna a profundidade que a rvore tem. Para ser mais simples identificar no programa desenvolvido, a cada coluna foi dado o nome de uma varivel, j que a legibilidade aumenta drasticamente, e ajudou imenso no debug. O algoritmo, em esboo o seguinte: 1. Inicializaratabelaeaslinhasordenadasemordemcrescentedeprobabilidade. 2. Utilizarasprimeirasduaslinhasdatabela(correspondentesaosdois smbolos menos provveis), e criar um n intermdio que se usa como pai para os dois ns. Trabalho prtico N 1 -CSM Pg. 17 Antnio Machado N 11586 3. Deverse-ia agoraexcluir da rvore os dois ns utilizados e continuarapartir do passo 2,at ao fim. Na verdade, o que feito adicionar 1 probabilidade, e reordenar de novo a tabela, assim, estes ns ficaro no fim da tabela, e continua-se at a probabilidade ser ento maior que um. while (arvore(2,prob) < 1) %Criar a ligao para os dois smbolos menos provveis ao pai entrada = [sum(arvore(1:2,prob)), aux, -1, -1]; entrada = [entrada,max(arvore(1:2, prof))+1]; max_prof = max(max_prof, entrada(prof)); % Soma 1 probilidade para os enviar para baixo a seguir arvore(1:2, prob)= arvore(1:2,prob)+1; % Coloca os bits 0 e 1 em cada lado da arvore arvore(1, bit) = 0; arvore(2, bit) = 1; % O novo n passa a pai dos dois ns actuais arvore(1:2, pai) = aux; aux=aux+1; % Junta o novo n arvore arvore = [entrada ; arvore]; % Reordena a arvore. Os dois ns agora ficam no fundo. arvore = sortrows(arvore, prob); end Ficamosassimcomarvoreconstrudaeocdigoapenasconcatenarosbitsqueforamsendo criados, para isso: Cria-se um vetor de pais. Enquanto ovector de pais estiver vazio,extrai-se o primeiro n na lista dos pais,e encontra-se os dois ns que so filhos do nque acabamos de extrair. Se o n no tem filhos para fora, ento uma folha nada fazer. Se o n tem filhos, tem de se atribuir a cada um os bits associados. Coloca-se os ns na lista de pais. Trabalho prtico N 1 -CSM Pg. 18 Antnio Machado N 11586 while (~isempty(pais)) %Extrai o primeiro pai e remove-o da lista ppa = pais(1);pais(1) = [];% Encontrar as linhas de ns que possuem o n actual como pai idx = find(arvore(:,pai) == ppa); if (~isempty(idx)) % N actual tem filho filho = arvore(idx, simb);% Simbolo do n filho % Criar a string do filho com a do pai e mais 0 ou 1 for n=1:length(filho) s=str(ppa+1, :); livre=find(s==' ', 1 ); s(livre) = num2str(arvore(idx(n),bit)); str(filho(n)+1,:) = s; end pais = [pais ; filho]; end end Para finalizar retiram-se os bits do dicionrio e removem-se os espaos que esto no meio dos bits. dic=str(1:(max_simb+1),:); bits = dic(x+1,:)'; % Retirar os bits do dicionario bits = bits(:)'; % Colocar a matriz num vector apagar = bits == ' '; % Apagar os espaos no meio dos bits bits(apagar)=[]; Trabalho prtico N 1 -CSM Pg. 19 Antnio Machado N 11586 2.2.2Descodificao Huffman Na Figura 5 apresenta-se o ecran de descodificao de uma imagem com o algoritmo de Huffman. Figura 5 Codificao HUFFMAN Tambm aqui como no RLC, a descodificao do ficheiro mais simples do que a codificao. No Matlab fundamental alocar espao para os vectores de trabalho, para que sejam mais rpidos, no entanto nestecaso no se sabe qual otamanho que sevaicriar,assimporopo alocou-se paraa piordassituaes,sabendodeantemoquenuncasevaichegaraestadimenso.Istocriacomo reverso da medalha a utilizao desnecessria de memria. simbolo=0:(size(tabela,1)-1); tab=tabela; simb=simbolo; y=1:size(bits,2);% alocar para a pior das hipteses Para a descodificao o processo simples, percorre todo o ficheiro, e encontra as linhas que tm o bit b. for b=bits ind = find(b == tab(:,1)); % Encontrar as linhas com o bit 'b' Trabalho prtico N 1 -CSM Pg. 20 Antnio Machado N 11586 Dependendo dotamanho dovector de ndices,sabemos se stemos uma linha,e porconseguinte umsmbolo,ouhmaislinhasetemosdecontinuar.Sedefactoumsmbolo,pesquisa-seno dicionrio o smbolo com o cdigo correspondente, e guarda-se. if (length(ind)==1) %y=[y simb(ind)];y(z)= simb(ind); % Como s h uma linha este um simbolo z=z+1; tab=tabela; simb=simbolo; else % Existem mais linhas, continuar com o prximo bit tab=tab(ind, 2:size(tab,2)); simb=simb(ind); end end y=y(1:z-1); end No final imperativo redimensionar os dados ao tamanho correcto, da o contador z. Trabalho prtico N 1 -CSM Pg. 21 Antnio Machado N 11586 3Resultados ParaaelaboraodaTabela1,foramutilizadososficheirosPBimage1.bmp,PBimage1.bmpe lena.tiff.Estesficheirosporteremdadosapretoebrancoeanveisdecinzentorepresentaa generalidadedasamostrasrecomendveis paraestestiposdecompresso.Osvaloresdeentropia foramcalculadoscomafunoseguinte,jquenaalturadodesenvolvimentonotinha conhecimento da funo interna do MATLAB. function data = entropia(x) unico=unique(x); numUnico=length(unico); numX=length(x); Frequencia = zeros(numUnico,1); data = 0; for i = 1:numUnico, Frequencia(i) = sum(x == unico(i)); y = (Frequencia(i)/numX) * log2((Frequencia(i)/numX)); data = data + y; end data=-data;end Deumaformasucinta,afunorecebeumvectorx,aoqualseextraioselementosnicos,e percorrendo ovector,calcula-seafrequncia de cada simbolo. De seguida tambmao percorrero vector,normaliza-se a frequncia de cada simboloevai-se fazendo osomatrio de cada elemento com o logaritmo da probabilidade de acordo com a frmula 1.4. Tabela 1 Quadro resumo de resultados da compresso Ficheiro Entr. (H) Tam. Inicial Tamanho Comprimido Tempo de Compresso Tempo de Descompresso Taxa de Comp. RLCHUFFRLCHUFFRLCHUFFRLCHUFF PBimage1.bmp0.5641550625399565880.01210.24220.3690.459792.1086.986 PBimage2.bmp1.609506258943155720.00300.14090.3981.161582.3369.240 Lena.tiff7.445512621442569472491500.02979.49250.08422.1511.9824.9568 Trabalho prtico N 1 -CSM Pg. 22 Antnio Machado N 11586 Da Tabela 1 podemos verificar algumas informaes interessantes para os ficheiros estudados, com cada uma das codificaes sem perdas usadas. Osficheirosa preto e brancocombaixa entropiasoosmais propciosaserem codificadoscom estetipodecodificador,enquantoosdemaiorvalordeentropia,seromaiscomprimidospelo mtodo de Huffman. OcdigoHuffmandesenvolvidoseforaplicadoaficheirosgrandes,comvriosMBde informao,ficamuitolentoprincipalmentenagravaodoficheiroemdisco,aocontrriodo cdigoRLC,istodeve-seprincipalmenteconversodosbitsquesocaracteres,numcdigo decimalparasergravado emficheiro, porquea construo da rvoreemsi noexcessivamente lenta. Trabalho prtico N 1 -CSM Pg. 23 Antnio Machado N 11586 4Concluses PodemosdizerqueoalgoritmoRLCeficientequandoainformaoacodificarapresentaruma caractersticapeculiarquepossuirsequnciasdepadresrepetidos.Podemosentoaplica-lo satisfatoriamente a imagens, pois estas, na maioria dos casos, apresentam tal caracterstica. Se estas forem a preto e branco ento ainda mais eficiente o algoritmo . Asuagrandesimplicidadedeimplementaooutradascaractersticasarealar,querna codificaoquer na descodificao.Isto particularmenteimportante em sistemas detransmisso em tempo real, onde no pode haver um grande tempo de processamento, e na recepo os sistemas normalmentetmdesersuficientementebaratosenodeixamgrandemargemdemanobrapara implementaes exigentes. Esta implementao fica pois a cargo de uma mquina de estados trivial que se pode implementar facilmente em hardware. O cdigo de Huffman, tem particularidades muito diferentes do RLC, e portanto as suas aplicaes somaisvariadas.Paraalmdeserutilizadoemcompressodeimagenseficheiros,tambm muitasvezesutilizadoparaefectuarcriptografia.Aformacomoumconjuntodecaracteres representado poderia ser usado para enfraquecer um esquema criptogrfico, ao utilizar este tipo de compresso,ocdigopassaaficarmaisdissimulado,criandoumabarreiraadicionalnaquebra criptogrfica. Quandoaplicadocodificao decadasmbolodafonte,individualmente,ocdigodeHuffman forneceomenornmerointeiropossveldeunidadesdeinformao(bits)porsmbolodefonte, mas a compresso por este algoritmo no isenta de problemas, nomeadamente o facto de a tabela de smbolos ter de ser conhecida por ambos os interlocutores, o codificador e o descodificador, ou ento a nica forma de funcionar, ser a incluso dessa tabela no ficheiro comprimido, o que por si s pode criar um ficheiro com tamanho maior que o original. Para alm deste facto temos ainda um outro problema que se prende com a compresso obtida, esta noomximopossvel,jqueaoaplicaromtodoestatsticoaumsmboloeseeletiverpor Trabalho prtico N 1 -CSM Pg. 24 Antnio Machado N 11586 exemplo 90% de probabilidade, o cdigo ptimo seria 0.15 bits, no entanto o mnimo possvel que se pode assignar de 1 bit, portanto estamos a desperdiar 6 vezes a quantidade necessria. Como o cdigo de Huffman usa um nmero inteiro (k) de bits para cada smbolo, isto implica que nunca teremos k menor que 1. Numa imagem com duas cores (1 bit por pixel), como as usadas em fax por exemplo,acompressoficaquaseimpossvel.Asoluoseriaagruparosbitsemconjuntose depois aplicar Huffman, porm isso impede o cdigo de ser um compressor universal. Pelos resultados obtidos na Tabela 1 tambm se consegue provar o dito anteriormente, e podemos tambminferirquequantomaiorovalordeentropiadeumficheiro,maiseficazocdigode Huffman se torna, comparativamente com o RLC. EmcomparaocomoRLC,ocdigodeHuffmanpermitegeralmenteumamaiorcompresso, teoricamentemaisprximadovalordeentropia,exceptonoscasosmencionados,masmais difcil de implementar, mais lento e consome muito mais memria. Tambm dada a forma como foi neste trabalho implementado, o RLC nunca faz expanso de ficheiros, ao contrrio do Huffman. Trabalho prtico N 1 -CSM Pg. 25 Antnio Machado N 11586 5Bibliografia [1] L.Markenzon, Estruturas de Dados e seus algoritmos, Livraria Tcnica e Cientfica, 1994.[2] J. Nascimento, Slides da unidade curricular CSM, ISEL, 2012.[3] D. Salomon, A concise introduction to data compression, Springer, 2008. Trabalho prtico N 1 -CSM Pg. 26 Antnio Machado N 11586 6Anexo A Conjunto de ficheiros em Matlab criados para o trabalho: Ficheiro MAIN.M function varargout = Main(varargin) % MAIN M-file for Main.fig %MAIN, by itself, creates a new MAIN or raises the existing %singleton*. % %H = MAIN returns the handle to a new MAIN or the handle to %the existing singleton*. % %MAIN('CALLBACK',hObject,eventData,handles,...) calls the local %function named CALLBACK in MAIN.M with the given input arguments. % %MAIN('Property','Value',...) creates a new MAIN or raises the %existing singleton*.Starting from the left, property value pairs are %applied to the GUI before Main_OpeningFcn gets called.An %unrecognized property name or invalid value makes property application %stop.All inputs are passed to Main_OpeningFcn via varargin. % %*See GUI Options on GUIDE's Tools menu.Choose "GUI allows only one %instance to run (singleton)". % % See also: GUIDE, GUIDATA, GUIHANDLES % Edit the above text to modify the response to help Main % Last Modified by GUIDE v2.5 23-Apr-2012 15:45:18 % Begin initialization code - DO NOT EDIT gui_Singleton = 1; gui_State = struct('gui_Name', mfilename, ... 'gui_Singleton',gui_Singleton, ... 'gui_OpeningFcn', @Main_OpeningFcn, ... 'gui_OutputFcn',@Main_OutputFcn, ... 'gui_LayoutFcn',[] , ... 'gui_Callback', []); if nargin && ischar(varargin{1}) Trabalho prtico N 1 -CSM Pg. 27 Antnio Machado N 11586 gui_State.gui_Callback = str2func(varargin{1}); end if nargout [varargout{1:nargout}] = gui_mainfcn(gui_State, varargin{:}); else gui_mainfcn(gui_State, varargin{:}); end; end % End initialization code - DO NOT EDIT % --- Executes just before Main is made visible. function Main_OpeningFcn(hObject, eventdata, handles, varargin) handles.output = hObject; guidata(hObject, handles); clc; end % --- Outputs from this function are returned to the command line. function varargout = Main_OutputFcn(hObject, eventdata, handles)varargout{1} = handles.output; end % --- Executes on button press in btnEscImagem. function btnEscImagem_Callback(hObject, eventdata, handles) set(handles.lblTamOrig,'String',' '); set(handles.lblTempoCod,'String',' '); set(handles.lblTamCod,'String',' '); set(handles.lblEntropia,'String',' '); set(handles.lblEficiencia,'String',' '); set(handles.lblTempoDescod,'String',' '); [filename, pathname] = uigetfile({'*.tiff;*.bmp;*.jpg;*.jpeg','Imagens (*.tiff,*.bmp,*.jpg)'; '*.tiff','TIFF (*.tiff)'; ... '*.bmp','BMP (*.bmp)'; ... '*.jpg','JPG (*.jpg *.jpeg)'}, ... 'Escolha a imagem'); if isequal(filename,0) msgbox('Seleco de imagem cancelada.','Imagem','error','modal'); Trabalho prtico N 1 -CSM Pg. 28 Antnio Machado N 11586 else [x, map]=imread(fullfile(pathname, filename)); set(handles.lblImagem,'String',filename); imshow(x,map); [L,C]=size(x); x=reshape(x,1,L*C); fid = fopen('Imagem.org', 'w'); count=fwrite(fid, x, 'uint8'); fclose(fid); set(handles.lblTamOrig,'String',count); ent=entropia(x); set(handles.lblEntropia,'String',ent); end; end % --- Executes on button press in btnCod_RLC. function btnCod_RLC_Callback(hObject, eventdata, handles) fid = fopen('Imagem.org', 'r'); [x,countOrg]=fread(fid,'uint8'); fclose(fid); x=x'; nbits=16;% 16 para ser int16 tinicial = tic; data=rlc_Codificar(x,nbits); tempo = toc(tinicial); set(handles.lblTempoCod,'String',tempo); fid = fopen('Imagem.rlc', 'w'); countCod=fwrite(fid, data, 'int16'); fclose(fid); set(handles.lblTamCod,'String',countCod); eficiencia=(1-countCod/countOrg)*100; set(handles.lblEficiencia,'String',eficiencia); end % --- Executes on button press in btnDec_RLC. function btnDec_RLC_Callback(hObject, eventdata, handles) fid = fopen('Imagem.rlc', 'r'); [x]=fread(fid,'int16'); Trabalho prtico N 1 -CSM Pg. 29 Antnio Machado N 11586 fclose(fid); x=x'; tinicial = tic; data=rlc_Descodificar(x); tempo = toc(tinicial); set(handles.lblTempoDescod,'String',tempo); fid = fopen('Imagem.des', 'w'); fwrite(fid, data, 'uint8'); fclose(fid); end % --- Executes on button press in btnCod_HUF. function btnCod_HUF_Callback(hObject, eventdata, handles) fid = fopen('Imagem.org', 'r'); [x,countOrg]=fread(fid,'uint8'); fclose(fid); tinicial = tic; % Dados para testes rpidos % x=[0 2 22 2 2 66 66 99 165 12 22 22 22 82 127 52 9 44 66 188 243 255]; [bits,dic]=huf_Codificar(x); tempo = toc(tinicial); set(handles.lblTempoCod,'String',tempo); [L,C]=size(dic); [Lz, Cz]=size(bits); bitStuf=rem(Cz,8); for i=1: 8-bitStuf % Fazer o bit Stufing caso seja necessrio bits=[bits '0']; end [Lz, Cz]=size(bits); % TRANSFORMAR EM DECIMAL Y = zeros(1,Cz/8); z=1; for n=1:8:Cz Y(z)=bin2dec(bits(n:n+7));% Cdigo lento!!! mas... alternativaz=z+1;% seria fazer em C endfid = fopen('Imagem.huf', 'w'); countCod=fwrite(fid, L, 'uint16'); % Coloca as linhas e colunas do dicionario countCod=countCod + fwrite(fid, C, 'uint8'); countCod=countCod + fwrite(fid, dic, 'uint8');% Coloca o dicionario Trabalho prtico N 1 -CSM Pg. 30 Antnio Machado N 11586 countCod=countCod + fwrite(fid, 8-bitStuf, 'uint8');% Coloca o bitstufing countCod=countCod + fwrite(fid, Y, 'uint8');% Coloca os dados no ficheiro fclose(fid); ent=entropia(x); set(handles.lblTamCod,'String',countCod); set(handles.lblEntropia,'String',ent); eficiencia=(1-countCod/countOrg)*100; set(handles.lblEficiencia,'String',eficiencia); end % --- Executes on button press in btnDec_HUF. function btnDec_HUF_Callback(hObject, eventdata, handles) fid = fopen('Imagem.huf', 'r'); L=fread(fid,1,'uint16'); C=fread(fid,1,'uint8'); dic=fread(fid,L*C,'uint8=>char'); dic=reshape(dic,L,C); bitStufing=fread(fid,1,'uint8'); [y,countCod]=fread(fid,'uint8'); bits=1:countCod*8; bits =dec2bin(y(1),8); for i=2:countCod bits = [bits dec2bin(y(i),8)];% Cdigo muito lento!!! mas.... end bits=bits(1:countCod*8-bitStufing); fclose(fid); tinicial = tic; bits=huf_Descodificar(bits,dic); tempo = toc(tinicial); set(handles.lblTempoDescod,'String',tempo); fid = fopen('Imagem.des', 'w'); fwrite(fid, bits, 'uint8'); fclose(fid); end % --- Executes on button press in btnCmpFich. function btnCmpFich_Callback(hObject, eventdata, handles) fid = fopen('Imagem.org', 'r'); Trabalho prtico N 1 -CSM Pg. 31 Antnio Machado N 11586 [inOrg,countOrg]=fread(fid,'uint8'); fclose(fid); fid = fopen('Imagem.des', 'r'); [inDes,countDes]=fread(fid,'uint8'); fclose(fid); if countOrg~=countDes msgbox('Os ficheiros no tm sequer tamanhos iguais.','Comparao de ficheiros','error','modal'); else if isequal(inOrg,inDes) msgbox('Confirma-se a inexistncia de perdas! (ficheiros iguais)!!!','Comparao de ficheiros','none','modal'); else msgbox('Os ficheiros tm o mesmo tamanho mas no so exactamente iguais.','Comparao de ficheiros','error','modal'); end; end; end % --- Executes on button press in btnSair. function btnSair_Callback(hObject, eventdata, handles) close all; end Trabalho prtico N 1 -CSM Pg. 32 Antnio Machado N 11586 Ficheiro RLC_CODIFICAR.M function comp = rlc_Codificar(x,bits) tam=size(x,2); % Calcula o tamanho do vector x a codificar comp = zeros(1,tam); % Aloca o espao para a resposta, para ser mais rpido qt=1; z=1; nMax= 2^bits-1; for i=1: tam-1% Percorre at fim do ficheiro-1 if x(i)~=x(i+1) || qt > nMax% Compara o elemento com o seguinte comp(z)=x(i); % Se for diferente coloca o elemento nos z=z+1;% dados codificados (garante que pode ser usado com qq n de bits (2^bits) if qt>1 % Se j temos quantidades vamos escreve-las nos comp(z)=-qt;% dados codificados, como valores negativos, evitando z=z+1;% mais caracteres no ficheiro. Consegue-se assim obter end % sempre compresso do ficheiro. qt=1; else qt=qt+1; end end if qt>1comp(z)=x(tam-qt+1); % No fim do ciclo pode haver quantidades apenas z=z+qt-1;% h que escrever o simbolo e essa quantidadeend comp(z)=x(tam);% Escrever o ltimo smbolo, este nunca comprimido para ser mais rpido o algoritmo comp=comp(1:z);% Truncar os dados ao tamanho exacto end Trabalho prtico N 1 -CSM Pg. 33 Antnio Machado N 11586 Ficheiro RLC_DESCODIFICAR.M function Codigo = rlc_Descodificar(x) tam=size(x,2); % Calcula o tamanho do vector x a codificar z=1; Codigo = zeros(1,2*tam); % Aloca o espao para a resposta, para ser mais rpido for i=1: tam % Percorre os dados comprimidos todos if x(i)>=0 Codigo(z)=x(i);% Se o valor positivo um simbolo z=z+1; else %for j=2:-x(i) % Se o valor negativo, uma quantidade %Codigo(z)=x(i-1); % Tem de se fazer a expanso do simbolo%z=z+1; %end Codigo(z:z-2-x(i))=x(i-1); % Assim mais eficiente no Matlab z=z-1-x(i);% fazer a expanso end end Codigo=Codigo(1:z-1);% Truncar os dados ao tamanho exacto end Ficheiro ENTROPIA.M function data = entropia(x) unico=unique(x); numUnico=length(unico); numX=length(x); Frequencia = zeros(numUnico,1); data = 0; for i = 1:numUnico, Frequencia(i) = sum(x == unico(i)); y = (Frequencia(i)/numX) * log2((Frequencia(i)/numX)); data = data + y; end data=-data;end Trabalho prtico N 1 -CSM Pg. 34 Antnio Machado N 11586 Ficheiro HUF_CODIFICAR.M function [bits, dic] = huf_Codificar(x) freqs=hist(x, 0:(max(x)));% Calcular as frequencias dos simbolos freqs=freqs/length(x);% Normalizar max_simb = max(x);% Simbolo maior alfabeto=0:(length(freqs)-1); % Vector com os smbolos sempre positivos. % Nomes para os campos da arvore, para ser mais facil identificar prob= 1; % Coluna da Probabilidade simb= 2; % Coluna do Simbolo bit = 3; % Coluna do Bit pai = 4; % Coluna da ligao ao Pai prof= 5; % Coluna com a Profundidade % Inicializa a arvore com os 5 campos arvore = [freqs(:), alfabeto(:), zeros(length(alfabeto), 2)-1]; arvore = [arvore zeros(length(alfabeto), 1)]; tmp = freqs ~= 0;% Usar apenas os simbolos com frequncia no nula arvore = arvore(tmp, :); arvore = sortrows(arvore, prob); % Ordenar por probabilidades aux = max_simb+1;%Inteiro associado com o prximo smbolo max_prof = 0; while (arvore(2,prob) < 1) %Criar a ligao para os dois smbolos menos provveis ao pai entrada = [sum(arvore(1:2,prob)), aux, -1, -1]; entrada = [entrada,max(arvore(1:2, prof))+1]; max_prof = max(max_prof, entrada(prof)); % Soma 1 probilidade para os enviar para baixo a seguir arvore(1:2, prob)= arvore(1:2,prob)+1; % Coloca os bits 0 e 1 em cada lado da arvore arvore(1, bit) = 0; arvore(2, bit) = 1; % O novo n passa a pai dos dois ns actuais arvore(1:2, pai) = aux; aux=aux+1; % Junta o novo n arvore arvore = [entrada ; arvore]; % Reordena a arvore. Os dois ns agora ficam no fundo. arvore = sortrows(arvore, prob); end % Alocar na rvore os simbolos Trabalho prtico N 1 -CSM Pg. 35 Antnio Machado N 11586 n_simb = max(arvore(:,simb)+1); str = reshape(blanks(n_simb*max_prof), n_simb, max_prof); vazia = blanks(max_prof); % Encontrar a nova raiz, simbolo com o pai==-1 idx = arvore(:,pai)==-1; raiz = arvore(idx, simb);str(raiz,:) = vazia;pais = raiz; % Inicializar a lista de pais % Enquanto houver pais while (~isempty(pais)) %Extrai o primeiro pai e remove-o da lista ppa = pais(1);pais(1) = [];% Encontrar as linhas de ns que possuem o n actual como pai idx = find(arvore(:,pai) == ppa); if (~isempty(idx)) % N actual tem filho filho = arvore(idx, simb);% Simbolo do n filho % Criar a string do filho com a do pai e mais 0 ou 1 for n=1:length(filho) s=str(ppa+1, :); livre=find(s==' ', 1 ); s(livre) = num2str(arvore(idx(n),bit)); str(filho(n)+1,:) = s; end pais = [pais ; filho]; end end dic=str(1:(max_simb+1),:); bits = dic(x+1,:)'; % Retirar os bits do dicionario bits = bits(:)'; % Colocar a matriz num vector apagar = bits == ' '; % Apagar os espaos no meio dos bits bits(apagar)=[];end Trabalho prtico N 1 -CSM Pg. 36 Antnio Machado N 11586 Ficheiro HUF_DESCODIFICAR.M function y = huf_Descodificar(bits, tabela) simbolo=0:(size(tabela,1)-1); tab=tabela; simb=simbolo; y=1:size(bits,2);% alocar para a pior das hipteses z=1; for b=bits ind = find(b == tab(:,1)); % Encontrar as linhas com o bit 'b' if (length(ind)==1) %y=[y simb(ind)];y(z)= simb(ind); % Como s h uma linha este um simbolo z=z+1; tab=tabela; simb=simbolo; else % Existem mais linhas, continuar com o prximo bit tab=tab(ind, 2:size(tab,2)); simb=simb(ind); end end y=y(1:z-1); end