A Genus Bound for Digital Image Boundaries
Lowell Abrams, Donniell E. Fishkind · SIAM Journal on Discrete Mathematics · 2005
Shattuck and Leahy [IEEE Trans. Med. Imag., 20 (2001), pp. 1167--1177] conjectured---and Abrams, Fishkind, and Priebe [IEEE Trans. Med. Imag., 21 (2002), pp. 1564--1566], [IEEE Trans. Med. Imag., 23 (2004), pp. 655--657] proved---that the boundary of a digital image is topologically equivalent to a sphere if and only if certain related foreground and background graphs are both trees. In this article we extend this result by proving upper and lower bounds on digital image boundary genus in terms of the foreground and background graphs, and we show that these bounds are best possible. Our results have current application to topology correction in medical imaging.