Please use this identifier to cite or link to this item: http://hdl.handle.net/10348/215
Title: Estudo da Utilização de Recorrência de Padrões Multiescala na Codificação de Documentos
Authors: Francisco, Nelson Carreira
Advisor: Reis, Manuel José Cabral dos Santos
Faria, Sérgio Manuel Maciel de
Keywords: Codificação de imagens
Compressão de documentos compostos
Correspondência de padrões
Multidimensional Multiscale Parser
Issue Date: 2008
Abstract: A crescente utilização do suporte digital como meio de comunicação e publicação de documentos escritos, tem contribuído para o aumento da necessidade de desenvolver algoritmos de compressão eficientes para este tipo dados. O presente trabalho baseia-se na aplicação do algoritmo MMP (Multidimensional Multiscale Parser) a um codificador de documentos digitalizados. Os resultados promissores anteriormente obtidos apontam no sentido deste poder constituir uma alternativa viável a outros algoritmos existentes, como sejam o DjVu ou o JPEG2000- Part6. O algoritmo MMP foi originalmente proposto como sendo uma técnica de compressão com perdas, para sinais multi-dimensionais. Utiliza um dicionário adaptativo de vectores de dimensão variável, para aproximar blocos também eles de tamanho variável do sinal de entrada. Estes elementos do dicionário resultam de concatenações sucessivas de blocos de dados previamente processados. O recurso a transformações de escala possibilita a adequação da dimensão dos elementos do dicionário ás dos blocos da imagem original. O MMP demonstrou anteriormente ser uma alternativa variável para compressão de documentos digitalizados, dada a sua versatilidade, que assenta na ausência de pressupostos em relação ás características da imagem a codificar, e no paradigma de codificação utilizado. Ao contrário do que acontece com os algoritmos de codificação baseados em transformadas, não se assume que as imagens a comprimir sejam de natureza passa-baixo, facto que se revela numa falsa consideração no caso das imagens de texto. Consequentemente, o MMP ultrapassa consideravelmente o desempenho destes algoritmos, quando aplicado a imagens de texto. Porém, isso não acontece quando o MMP é utilizado para codificar imagens suaves, o que motivou a introdução de um novo esquema de segmentação, apresentado no presente trabalho, mais flexível, e que permitiu obter ganhos consideráveis em relação ao anteriormente utilizado. Uma optimização especificamente orientada para imagens de texto permitiu igualmente um aumento de desempenho do MMP para este tipo de sinal de entrada, apresentando ainda uma clara vantagem associada á redução da complexidade computacional do algoritmo.
The increasing use of the digital support as a communication and publishing media for written documents is contributing to the need of efficient coding Algorithms for this specific type of data. The presented work is focused in the use of the Multidimensional Multiscale Parser (MMP) algorithm for a digital scanned document encoder. Our promising results allow us to consider it as a true alternative to the existing algorithms, like DjVu and JPEG2000-Part6. The MMP algorithm was originally proposed as a multidimensional lossy signal compression method, and uses a multiscale adaptive dictionary of vectors to approximate variable-length input vectors, that result from parsing an original input block of data. Using scale transformations allow the matching of each dictionary element with the original blocks, that may have different sizes. MMP has already proven to be a reliable option for scanned document coding, due to its universal character, build upon the absence of assumptions about the input images' characteristics, and the compression paradigm used. In opposition to transform-based algorithms, MMP do not assume that the input images have a low-pass nature, which is a false consideration for text documents. Consequently, MMP is able to considerably outperform transform-based state of-the-art compression algorithms, when applied to non-smooth images. However, this is not true for natural images, motivating the introduction of a new segmentation scheme, presented in this work, that is more flexible and that allowed a significative performance gain, in relation to its antecessor. A specifically oriented optimization for text-images, additionally allowed an increase of the MMP's performance, while reducing its computacional complexity.
Description: Dissertação de Mestrado em Engenharia Electrotécnica e de Computadores
URI: http://hdl.handle.net/10348/215
Document Type: Master Thesis
Appears in Collections:OLD - Dissertações de Mestrado

Files in This Item:
File Description SizeFormat 
msc_ncfrancisco.pdf
  Restricted Access
1,81 MBAdobe PDFView/Open Request a copy


FacebookTwitterDeliciousLinkedInDiggGoogle BookmarksMySpace
Formato BibTex mendeley Endnote Logotipo do DeGóis Logotipo do Orcid 

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.