Image Representation Using Graph Models
Digital images can be interpreted not only as arrays of intensity or color values, but also as structured graphs. In this formulation, the spatial organization of pixels is encoded through vertices, edges, neighborhoods, and optional edge weights. This graph-based perspective provides a rigorous mathematical foundation for image analysis, segmentation, region growing, boundary extraction, connectivity analysis, and many other computational imaging tasks.
First Stage — Pixel-to-Vertex Mapping
A two-dimensional image I of size M × N can be represented as a graph G = (V, E). Each pixel location (i, j) is mapped to a vertex vᵢ,ⱼ ∈ V. The image is therefore transformed from a rectangular grid of samples into a discrete topological structure whose nodes preserve the spatial layout of the original image.
Second Stage — Neighborhood and Edge Construction
Edges are defined between neighboring pixels according to a selected connectivity model. In a 4-connected grid, each pixel is connected to its horizontal and vertical neighbors. In an 8-connected grid, diagonal neighbors are also included. Edge weights may encode photometric or geometric relations, such as intensity difference, color distance, gradient magnitude, spatial proximity, or local texture similarity.
Third Stage — Graph-Based Image Analysis
Once the image has been represented as a graph, image-processing operations can be formulated as graph problems. Connected components, shortest paths, minimum spanning trees, cuts, random walks, and traversal procedures can all be applied to the image domain. This allows local pixel relations and global image structure to be analyzed within one unified mathematical framework.
Fourth Stage — Breadth-First Search as Region Expansion
Breadth-First Search (BFS) can then be used as a graph-traversal mechanism for image exploration. Starting from a seed pixel v₀, BFS visits vertices level by level using a first-in/first-out queue. When combined with a similarity criterion, such as |I(v) − I(v₀)| < τ, the traversal expands through accepted neighboring pixels and produces a connected segmented region.