Use disjoint-set/union-find for connected components, instead of breadth-first search:

https://bugfix-66.com/5c92ae4bfe4b19be55b1f8136d7f844b630fa8...

Above is the most efficient known disjoint-set algorithm: Martin Rem's union-find.

Pretty sure the most efficient algorithm (it's linear) is to scan through the image in raster order but when you find a component you follow all the way around its border. I implemented it years ago. Can't remember the name though.