The invention relates to a method for automatic detection and tracking of one or multiple objects of interest in a video sequence comprising several successive frames (1) captured with a moving camera, comprising:—segmenting (32) each frame into regions depending on color and producing a segmented image (1′);—deducing (34) from each segmented image (1′) a region adjacency graph (11) comprising nodes and edges, wherein each node defines a region and each edge links two nodes of adjacent regions; wherein the region adjacency graphs (11) form a set of region adjacency graphs;—extracting (36) from the set of region adjacency graphs frequent spatio-temporal patterns (13);—determining (38) degrees of dissimilarity between the trajectories of the extracted frequent spatio-temporal patterns (13) between successive frames (1); and—clustering (39) the frequent spatio-temporal patterns (13) to produce at least one cluster (25, 26, 27) corresponding to one object of interest among said one or multiple objects of interest according to the determined degrees of dissimilarity of the trajectories.