On the non-optimality of four color coding of image partitions
Research output: Contribution to conference › Paper › Research › peer-review
Standard
On the non-optimality of four color coding of image partitions. / Agarwal, Sameer; Belongie, Serge.
2002. II/677-II/680 Paper presented at International Conference on Image Processing (ICIP'02), Rochester, NY, United States.Research output: Contribution to conference › Paper › Research › peer-review
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - CONF
T1 - On the non-optimality of four color coding of image partitions
AU - Agarwal, Sameer
AU - Belongie, Serge
PY - 2002
Y1 - 2002
N2 - Recent interest in region based image coding has given rise to graph coloring based partition encoding methods. These methods are based on the four color theorem for planar graphs, and assume that a coloring for a graph with the minimum possible number of colors will result in the most compressible representation. In this paper we show that this assumption is wrong. We show that there exist graphs with chromatic number k that can be colored with k + 1 colors resulting in bitmaps representing image partitions which are more compressible than the corresponding bitmaps generated using any k coloring of the same graph. We conclude with some conjectures on optimal coloring of weighted graphs.
AB - Recent interest in region based image coding has given rise to graph coloring based partition encoding methods. These methods are based on the four color theorem for planar graphs, and assume that a coloring for a graph with the minimum possible number of colors will result in the most compressible representation. In this paper we show that this assumption is wrong. We show that there exist graphs with chromatic number k that can be colored with k + 1 colors resulting in bitmaps representing image partitions which are more compressible than the corresponding bitmaps generated using any k coloring of the same graph. We conclude with some conjectures on optimal coloring of weighted graphs.
UR - http://www.scopus.com/inward/record.url?scp=18844469431&partnerID=8YFLogxK
M3 - Paper
AN - SCOPUS:18844469431
SP - II/677-II/680
T2 - International Conference on Image Processing (ICIP'02)
Y2 - 22 September 2002 through 25 September 2002
ER -
ID: 302056823