An improved algorithm for gray image representation using non-symmetry and anti-packing model with triangles and rectangles

Abstract

Although the triangle non-symmetry and anti-packing model (TNAM) representation for gray images is an effective image representation method, there is still much space left for optimization. In this paper, inspired by the optimization idea of the packing problem, we proposed an improved algorithm for gray image representation using the non-symmetry and anti-packing model with triangles and rectangles (NAMTR). By comparing the representation algorithm of the NAMTR with those of the TNAM and the popular linear quadtree, theoretical and experimental results presented in this paper show that the former can greatly reduce the number of sub-patterns or nodes and simultaneously save the data storage much more effectively than the latter, and therefore it is a better method to represent gray images. Representation method of the NAMTR, as envisaged in this paper, shows a very strong promise, and it is valuable for further theoretical research and potential business foreground, such as reducing storage space, increasing transmission speed and improving pattern match efficiency.

References

1. Chen C B, He D H . Heuristic method for solvingtriangle packing problem. Journal of ZhejiangUniversity, 2005, 6(6): 565–570. doi:10.1631/jzus.2005.A0565
2. Krivelevich M . Ona conjecture of Tuza about packing and covering of triangles. Discrete Mathematics, 1995, 142(1): 281–286. doi:10.1016/0012-365X(93)00228-W
3. Chen C B, He D H, Hang W Q . An approximation algorithm for solving the problem ofpacking unit equilateral triangles in a square. Chinese Journal of Computers, 2003, 26(2): 212–220 (in Chinese)
4. Wu Y L, Huang W Q, Lau S C, et al.. An effective quasi-human based heuristic forsolving the rectangle packing problem. European Journal of Operational Research, 2002, 141(2): 341–358. doi:10.1016/S0377-2217(02)00129-7
5. Chen M, Huang W Q . A two-level search algorithmfor 2D rectangular packing problem. Computersand Industrial Engineering, 2007, 53(1): 123–136. doi:10.1016/j.cie.2007.04.007
6. Huang W Q, Li Y, Akeb H, et al.. Greedy algorithms for packing unequal circlesinto a rectangular container. Journal ofthe Operational Research Society, 2005, 56(5): 539–548. doi:10.1057/palgrave.jors.2601836
7. Klinger A . Datastructure and pattern recognition. In: Proceedings of International Joint Conference on Pattern Recognition(IJCPR), Washington, D.C., USA, 1973, 497–498
8. Gargantini I . Aneffective way to represent quadtrees. Communicationsof the ACM, 1982, 25(12): 905–910. doi:10.1145/358728.358741
9. Wang C L, Wu S C, Chang Y K . quadtree and statistical model-based lossless binaryimage compression method. Imaging ScienceJournal, 2005, 53(2): 95–103. doi:10.1179/136821905X43927
10. Laszlo M, Mukherjee S . A genetic algorithm usinghyper-quadtrees for low-dimensional k-means clustering. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2006, 28(4): 533–543. doi:10.1109/TPAMI.2006.66
11. Zheng Y P, Chen C B . A color image representationmethod based on non-symmetry and anti-packing model. Journal of Software, 2007, 18 (11): 2932–2941 (in Chinese). doi: 10.1360/jos182932
12. Chen C B, Hu W J, Wan L . Direct non-symmetry and anti-packing pattern representationmodel of medical images. In: Proceedingsof the 1st International Conference on Bioinformatics and BiomedicalEngineering, Wuhan, China, 2007, 1011–1018
13. Zheng Y P, Chen C B, Sarem M . A novel algorithm for triangle non-symmetry and anti-packingpattern representation model of gray images. In: Proceedings of the 3rd International Conference on Intelligent Computing,Lecture Note in Computer Science, Vol 4681, Qingdao, China, 2007, 832–841