This site is being phased out.
Difference between revisions of "Graph representation of topology of color images"
imported>WikiSysop |
(No difference)
|
Latest revision as of 19:56, 30 October 2012
Start at Graph representation of topology of gray scale images and Color images.
Contents
What is the topology of a color image?
The RGB color space is $$C = \{ (r, g, b) : 0 ≤ r, g, b ≤ 255 \}.$$ There is a natural partial order on $C$: $$r ≤ r’, g ≤ g’, b ≤ b’ \Rightarrow (r, g, b) ≤ (r’, g’, b’).$$
If only one of the three primary color is changing, the topology is the same as that of the corresponding gray scale image:
Then we recognize objects as darker areas surrounded by lighter background. Similarly, all three colors may be changing producing the same effect of a dark object on a light background. The rule applies to more general situations.
To make this specific, suppose we have a color image as a function $J:[0,N] \times [0,M] → C$, where $C$ is the RGB color space.
If we have any function $P:C → [0,255]$, then the composition $PJ:[0,N] \times [0,M] → [0,255]$ is a gray scale image. Suppose also that $P$ is increasing with respect to the partial order: $$r≤r', g≤g', b≤b' \Rightarrow P(r,g,b)≤P(r',g',b').$$ What this means is that the darker/lighter relationship between pixels is preserved under $P$ but some of it may disappear. In other words, the gray scale of $PJ$ is becoming darker as the color of $J$ is becoming darker.
Two things follow:
- Every darker area surrounded by a lighter background in the gray scale image $PJ$ appears as a darker area surrounded by a lighter background in the original image $J$, for any $P$.
- Every darker area surrounded by a lighter background in image $J$ appears as a darker area surrounded by a lighter background in the gray scale image $PJ$, for some $P$.
Therefore, in order to capture the topology of $J$ one needs to capture the topologies of all possible gray scale images $PJ$, without double counting.
A similar analysis will lead to an even simpler conclusion that in order to capture the topology of $J$ one needs to captures the topologies of all of its possible binarizations (via thresholding), without double counting.
Topology graph of a color image
The nodes of the topology graph are the objects and holes in the thresholded image and there is an arrow from node $A$ to node $B$ if:
- object $B$ has hole $A$, provided $A$ and $B$ correspond to consecutive colors.
- object $B$ has hole $A$, provided $A$ and $B$ correspond to the same color.
- And vice versa.
Each of these slices is the topology graph of the gray scale image obtained from the color image by fixing a value of, say, green and blue and letting red vary. The end result is a box filled with graphs connected with its neighbors.
How to build the topology graph
All pixels in the image are ordered according to the partial order.
- Following this order, each pixel is processed:
- add its vertices, unless those are already present as parts of other pixels;
- add its edges, unless those are already present as parts of other pixels;
- add the face of the pixel.
- At every step, the graph is given a new node and arrows that connect the nodes in order to represent the merging and the splitting of the cycles:
- adding a new vertex creates a new component;
- adding a new edge may connect two components, or create, or split a hole;
- adding the face to the hole eliminates the hole.
For how, see Adding pixels.
Complete analysis
- Same as for gray scale but based on the partial order above
- Threshold the image to create $256 \times 256 \times 256$ binary images.
- Collect all objects and holes in the topology graph, as above.
- Filter noise out if necessary.
- Choose the tips, etc to give the "binary" topology of the image.