The fastest algorithm for splitting image into footprint and nodata values

Question

I have a random satellite image that can be divided into 2 classes:

1) no data values (all pixel values are equal and randomly vary from image to image)

2) footprint (all pixel values are random)

A sum of all the values of no data and footprint gives a bounding box.

What is the fastest algorithm for dividing a random satellite image into these 2 classes?

UPDATE:

Are no data value-areas always at the border of the image?

No data value could not be inside of the footprint and it may be absent.

Are no data-values always black?

No, it's value may vary from picture to picture. But always equal each other inside one image.

Does this no data value-color appear within the footprint?

Most of the images are grayscale and may be in 16, 8-bit data formats. But i need general algorithm. Case specific algorithm is not what i want.

UPDATE 2:

My current approach is:

1) Take every pixel values that lay on the bounding box boarder

2) Take most frequent value and set it as nodata

3) Reclassify image into 2 classes with values: NoData value - nodata class, 1 - footprint class

4) Convert rasters pixels with value 1 into vector format

For big images it take more than 5 minutes to get vector boarders of footprint.

Answer 1

A simple way for you would be to multiply the pixel intensities. From the images you uploaded, the no data values are esentially of 0 intensity. Instead of going for complex methods, simply multiply the image intensities by 1000.

I used OpenCV and could segment out the regions in under 4 lines of code. Here's an example -