En la seguidilla de las ideas que estoy dando a conocer, esta es otra de ellas. En los siguientes párrafos, les dejo a continuación la idea.
Específicamente, pentominós, los que podrían ofrecer una buena alternativa para representar formas, basándose en la morfología matemática.
Esta idea nace como una alternativa a la compresión utilizando las matrices Sudoku, discutida en el artículo Compresión de Datos Utilizando Matrices Sudoku -- estos problemas me estaban causando demasiados cortocircuitos cerebrales; por eso consideré esta idea, como una nueva vía.
La idea principal es implementar un algoritmo cuya entrada sea un flujo de bits, y cuya salida sea otro con ciertas propiedades que a continuación explico.
Internamente, el algoritmo va tomando de a m bits en m bits, conformando matrices binarias de nxn que llamaremos matriz T. A partir de T, se busca «encajar» poliominós donde existan conjuntos de bits encendidos (i.e. unos), generando un conjunto de poliominós utilizados que llamaremos P. De esta manera, sólo se necesitará codificar no toda la matriz, sino sólo el conjunto P.
Es necesario mencionar que en T pueden surgir tres situaciones. La primera es que en T existan mayor cantidad de unos que de ceros. En este caso, la cantidad de poliominós necesarios para cubrir la superficie de T será grande. Una solución simple, es invertir los bits de T. La segunda situación, es que ocurra lo contrario a la primera. En este caso, no es necesario hacer algo. Finalmente, la tercera situación es que vengan tantos unos como ceros en igual cantidad.
Los problemas que surgen de esta propuesta son los siguientes:
- Se necesita encontrar la combinación óptima de poliominós p en P sobre T, tal que ||P|| sea el mínimo en U, donde U es el universo de conjuntos de poliominós.
- Se requiere encontrar una representación óptima para p.
¿Alguna idea?
