I am assuming that each your images have a location. Try partitioning your space into sections and only do collision to entities within the same sections. Use the bound of image to determine which sections to play entities in.
The present method operates in stages. 1) Test the bounds of the two image rectangles in coordinate space. If passes, 2) scan through each relevant pixel of the relevant pixel subsets. If no conditions are violated, return happy.
No irrelevant pixels are tested presently. Some sort of operation like what SteveSmith said is all I can think would work here. I don't have that sorted yet tho.