Bose, P.; Dujmovi¿, V.; Hurtado, F.; Morin, P.
Computer vision and image understanding
Vol. 113, num. 10, p. 1027-1038
DOI: 10.1016/j.cviu.2007.06.003
Data de publicació: 2009-10
Article en revista
A binary image $\emph{I}$ is $B_a$, $W_b$-connected, where $\emph{a,b}$ ∊ {4,8}, if its foreground is $\emph{a}$-connected and its background is $\emph{b}$-connected. We consider a local modification of a $B_a$, $W_b$-connected image $\emph{I}$ in which a black pixel can be interchanged with an adjacent white pixel provided that this preserves the connectivity of both the foreground and the background of $\emph{I}$. We have shown that for any ($\emph{a,b}$) ∊ {(4,8),(8,4),(8,8)}, any two $B_a$, $W_b$-connected images $\emph{I}$ and $\emph{J}$ each with n black pixels differ by a sequence of $\theta(n^2)$ interchanges. We have also shown that any two $B_4$, $W_4$-connected images $\emph{I}$ and $\emph{J}$ each with n black pixels differ by a sequence of O($n^4$) interchanges.