Graph-Based Object Tracking in Linear Complexity Time
This concept presents a contour-based tracking algorithm for moving objects in video sequences. Instead of representing an object only by its interior region or by a bounding box, the method focuses on the evolution of the object’s contour and on the geometric structure induced by the segmentation of consecutive frames.
First Stage — Contour Decomposition Using the RAG
The input frame is segmented into adjacent regions, from which a region adjacency graph RAG = (V, E) is constructed. The object contour is then decomposed into meaningful subcurves according to the boundaries represented by the RAG. This converts the contour into a structured set of local curve elements rather than a single undifferentiated boundary.
Second Stage — Important Junctions
Each connection between two neighboring contour subcurves is defined as an important junction. These junctions serve as stable geometric anchors for tracking. Instead of tracking every contour point independently, the algorithm estimates the motion of these junctions across consecutive frames using the graph structure induced by segmentation.
Third Stage — Motion Search on the Consecutive RAG
In the next frame, the motion of each junction is estimated through a search represented by the edges of the consecutive-frame RAG. The RAG is transformed into a weighted and directed graph, allowing possible contour transitions to be evaluated according to edge costs, geometric consistency, and the expected motion of the object boundary.
Fourth Stage — k-Shortest Candidate Contours
Each pair of matched junctions may be connected by several possible edge paths. These paths are treated as candidate representations of the tracked contour and are obtained by a k-shortest paths algorithm. The final tracked contour is constructed by matching the object edges against the candidate path set and selecting the most consistent contour configuration.