Abstract: To label connected components in an image fast, this paper presents a very efficient algorithm for labeling connected components in a binary image based on propagating labels of run sets. This algorithm assigns provisional labels only to run sets which are composed of a series of runs connected to each other in adjacent scan rows rather than to each run. This kind of run set is called downward connected branch or DCB for short. A location map table is established at one time to store the location relations between all runs in DCBs, and all label nodes of DCBs are organized in a tree with small size. This enables us to propagate equivalence information in a partial path. Finally, the map table is scanned once to replace all provisional labels with representative labels. The result demonstrates that the speed of the algorithm is faster than existed ones as less equivalence information needs to be processed, fewer operations needs to label runs in DCBs, and the minimum label needs not to be calculated while combining two DCBs. Further more, the algorithm is very simple.