You could use actual bounding shapes instead of per-pixel collision data (you incorrectly called it a "bounds box"). This greatly simplifies the computational requirements.
You can use a single primitive shape in most cases, e.g. an AABB (axis-aligned bounding box), circle, etc.
If you need (actually need, not just think you need with no analysis) more complex shapes, you can achieve those in several ways. The first is to allow multiple primitive shapes. A table side-view for instance can be represented by three AABBs: one for the top and one for each pair of legs. A tree is an AABB with a circle at the top. etc.
The second option is to use a polygon shape. Generally this will be a convex hull as the math is considerably simpler for convex hulls than for arbitrary polygons. Again you can use multiple shapes (potentially all convex hulls or a combination with other primitive shapes) to represent more intricate objects that cannot be accurately represented by one. A human character may have separate polygons for each limb apart from its head and torso, for instance.
Typically you really, really don't need per-pixel collision, especially if you support convex hulls. You can represent any object with a set of convex hulls. The results will be faster and easier and allow more things to be done with them (such as determining depth of overlap and so on).