Fast method to access random image pixels and at most once

Question

I'm learning OpenCV (C++) and as a simple practice, I designed a simple effect which makes some of image pixels black or white. I want each pixel to be edited at most once; so I added address of all pixels to a vector. But it made my code very slow; specially for large images or high amounts of effect. Here is my code:

void effect1(Mat& img, float amount)    // 100 ≥ amount ≥ 0
{
    vector<uchar*> addresses;
    int channels = img.channels();
    uchar* lastAddress = img.ptr<uchar>(0) + img.total() * channels;
    for (uchar* i = img.ptr<uchar>(0); i < lastAddress; i += channels) addresses.push_back(i);   //Fast Enough
    size_t count = img.total() * amount / 100 / 2;
    for (size_t i = 0; i < count; i++)
    {
        size_t addressIndex = xor128() % addresses.size();   //Fast Enough, xor128() is a fast random number generator
        for (size_t j = 0; j < channels; j++)
        {
            *(addresses[addressIndex] + j) = 255;
        }   //Fast Enough
        addresses.erase(addresses.begin() + addressIndex);    // MAKES CODE EXTREMELY SLOW
    }
    for (size_t i = 0; i < count; i++)
    {
        size_t addressIndex = xor128() % addresses.size();   //Fast Enough, xor128() is a fast random number generator
        for (size_t j = 0; j < channels; j++)
        {
            *(addresses[addressIndex] + j) = 0;
        }   //Fast Enough
        addresses.erase(addresses.begin() + addressIndex);    // MAKES CODE EXTREMELY SLOW
    }
}

I think rearranging vector items after erasing an item is what makes my code slow (if I remove addresses.erase, code will run fast).

Is there any fast method to select each random item from a collection (or a number range) at most once?

Also: I'm pretty sure such effect already exists. Does anyone know the name of it?

Answer 1

I also post a simpler code:

void saltAndPepper(Mat& img, float amount)
{
    vector<size_t> pixels(img.total());    // size_t = unsigned long long
    uchar channels = img.channels();
    iota(pixels.begin(), pixels.end(), 0);    // Fill vector with 0, 1, 2, ...
    shuffle(pixels.begin(), pixels.end(), mt19937(time(nullptr)));    // Shuffle the vector
    size_t count = img.total() * amount / 100 / 2;
    for (size_t i = 0; i < count; i++)
    {
        for (size_t j = 0; j < channels; j++)    // Set all pixel channels (e.g. Grayscale with 1 channel or BGR with 3 channels) to 255
        {
            *(img.ptr<uchar>(0) + (pixels[i] * channels) + j) = 255;
        }
    }
    for (size_t i = count; i < count*2; i++)
    {
        for (size_t j = 0; j < channels; j++)    // Set all pixel channels (e.g. Grayscale with 1 channel or BGR with 3 channels) to 0
        {
            *(img.ptr<uchar>(0) + (pixels[i] * channels) + j) = 0;
        }
    }
}

Answer 2

This answer assumes you have a random bit generator function, since std::random_shuffle requires that. I don't know how xor128 works, so I'll use the functionality of the <random> library.

If we have a population of N items, and we want to select groups of size j and k randomly from that population with no overlap, we can write down the index of each item on a card, shuffle the deck, draw j cards, and then draw k cards. Everything left over is discarded. We can achieve this with the <random> library. Answer pending on how to incorporate a custom PRNG like you implemented with xor128.

This assumes that random_device won't work on your system (many compilers implement it in a way that it will always return the same sequence) so we seed the random generator with current time like the good old fashioned srand our mother used to make.

Untested since I don't know how to use OpenCV. Anyone with a lick of experience with that please edit as appropriate.

#include <ctime>     // for std::time
#include <numeric>   // for std::iota
#include <random>
#include <vector>

void effect1(Mat& img, float amount, std::mt19937 g)    // 0.0 ≥ amount ≥ 1.00
{
    std::vector<cv::Size> ind(img.total());
    std::iota(ind.begin(), ind.end(), 0);   // fills with 0, 1, 2, ...
    std::random_shuffle(ind.begin(), ind.end(), g);
    cv::Size count = img.total() * amount;

    auto white = get_white<Mat>();  // template function to return this matrix' concept of white
                                    // could easily replace with cv::Vec3d(255,255,255) 
                                    // if all your matrices are 3 channel?
    auto black = get_black<Mat>();  // same but... opposite

    auto end = ind.begin() + count;
    for (auto it = ind.begin(), it != end; ++it)
    {
        img.at(*it) = white;
    }
    end = (ind.begin() + 2 * count) > ind.end() ?
               ind.end() : 
               ind.begin() + 2 * count;
    for (auto it = ind.begin() + count; it != end; ++it)
    {
        img.at(*it) = black;
    }
}

int main()
{
    std::mt19937 g(std::time(nullptr)); // you normally see this seeded with random_device
                                        // but that's broken on some implementations
                                        // adjust as necessary for your needs
    cv::Mat mat = ... // make your cv objects

    effect1(mat, 0.1, g);

    // display it here

}

Another approach

Instead of shuffling indices and drawing cards from a deck, assume each pixel has a random probability of switching to white, switching to black, or staying the same. If your amount is 0.4, then select a random number between 0.0 and 1.0, any result between 0.0 and 0.4 flips the pixel black, and betwen 0.4 and 0.8 flips it white, otherwise it stays the same.

General algorithm:

given probability of flipping -> f
for each pixel in image -> p:
    get next random float([0.0, 1.0)) -> r
    if r < f
        then p <- BLACK
    else if r < 2*f
        then p <- WHITE

You won't get the same number of white/black pixels each time, but that's randomness! We're generating a random number for each pixel anyway for the shuffling algorithm. This has the same complexity unless I'm mistaken.

Answer 3

Also: I'm pretty sure such effect already exists. Does anyone know the name of it?

The effect you're describing is called salt and pepper noise. There is no direct implementation in OpenCV that I know of though.

I think rearranging vector items after erasing an item is what makes my code slow (if I remove addresses.erase, code will run fast).

Im not sure why you add your pixels to a vector in your code, it would make much more sense and also be much more performant to directly work on the Mat object and change the pixel value directly. You could use OpenCVs inbuild Mat.at() function to directly change the pixel values to either 0 or 255.

I would create a single loop which generates random indexes in the range of your image dimension and manipulate the image pixels directly. That way you are in O(n) for your noise addition. You could also just search for "OpenCV" and "salt and pepper noise", I am sure there already are a lot of really performant implementations.