You wouldn't upscale, you'd fill 16x16 blocks in original image iterating over downscaled image and if the block wasn't all the same color you'd process it normally. In fact you don't need to flood fill in downscaled image, just do edge detection.