Space-efficient algorithms in computer algebra and image processing applications

计算机代数和图像处理应用中的空间高效算法

• 批准号: 288300-2012
• 负责人: Cheng, HowardChiHo
• 金额: $ 1.24万
• 依托单位: University of Lethbridge
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2017
• 资助国家: 加拿大
• 起止时间: 2017-01-01 至 2018-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=634878
• 关键词: Space; efficient; algorithms; computer; algebra

We propose to study problems in a number of areas including computer algebra, image set compression, and mathematical document analysis. Our main focus is on techniques for efficiently reducing the space requirement for both the execution of algorithms and the storage of data.In many important problems in computer algebra, the sizes of the input and the final desired results are relatively small, but intermediate results may grow significantly in many algorithms. Our goal is to develop algorithms that are not only space efficient, but also take memory management in the underlying system into account. We expect that more practical algorithms will be developed as a result.In image set compression, compressing each image individually does not exploit the redundancy that exists between images. We plan to examine techniques to compress a set of images as well as the problem of dynamic updates to image set. We particularly focus on satellite and medical images in which substantial redundancy among images is known to exist.Many mathematical documents are available in digital form only as scanned digital images. We intend to build a system that analyzes these images and store them in a structured form for use by other tools. Of particular interests are recognizing and utilizing abstract concepts in mathematics such as matrix structures (e.g. Toeplitz, Hankel, etc.) and algorithm descriptions. Such a system can be used to build a digital library of mathematical knowledge to be stored efficiently and used by other computer algebra systems.

我们建议研究一些领域的问题，包括计算机代数、图像集压缩和数学文档分析。在计算机代数的许多重要问题中，输入的大小和最终期望结果的大小相对较小，但在许多算法中，中间结果可能会显著增加。我们的目标是开发不仅节省空间，而且考虑到底层系统中的内存管理的算法。在图像集压缩中，单独压缩每一幅图像并不会利用图像之间存在的冗余。我们计划研究压缩图像集的技术以及图像集的动态更新问题。我们特别关注卫星和医学图像，其中图像之间存在大量冗余。许多数学文献只能以扫描的数字图像的形式提供。我们打算建立一个系统来分析这些图像，并以结构化的形式存储它们，以供其他工具使用。特别感兴趣的是识别和利用数学中的抽象概念，如矩阵结构(如Toeplitz、Hankel等)。和算法描述。这样的系统可以用来建立数学知识的数字图书馆，以便有效地存储并被其他计算机代数系统使用。