4
\$\begingroup\$

I'm trying to write a function in python that detects a pixel signature in an image. The pixel signature is a small image of a maximum of 16 pixels of different rectangular shapes, e.g. 1x3 pixels, 2x4 pixels, or 4x4 pixels. The image in which we want to detect the signature is between 800x600 and 1920x1080 in resolution. The function should take the RGB NumPy arrays of the image and the signature as input and return an array of tuples with the coordinates where the signature was detected in the image.

I have written a function that accomplishes this by first detecting the first pixel of the signature in the image and then checking whether the neighboring pixels match the rest of the signature. The problem however is, that this function is quite slow. In the implementation below, it takes about 0.014s per call for an 800x600 image. Considering, that I want to check for about 300 different signatures in an image, the whole process takes around 4 seconds. Ideally, I would be looking for a faster solution.

def signature_locations_in_image(signature, image):

    res_x = image.shape[1]
    res_y = image.shape[0]
    sig_size_x = signature.shape[1]
    sig_size_y = signature.shape[0]

    # first we find all the pixels in the image that match the first pixel of the signature
    indices = np.where(np.all(image == signature[0, 0, :], axis=-1))
    coords = [x for x in zip(indices[0], indices[1])]
    found = []
    # for the matches we got in the first step, we then check if the rest of the signature matches
    for c in coords:
        c_x = c[1]
        c_y = c[0]
        match = False
        if c_x + sig_size_x <= res_x and c_y + sig_size_y <= res_y:
            match = True
            for x in range(0, sig_size_x):
                for y in range(0, sig_size_y):
                    if not np.all(image[c_y + y, c_x + x, :] == signature[y, x, :]):
                        match = False
        if match:
            found.append((c_x, c_y))

    return found 

EDIT: an example

For testing, one can take any png image and create a signature from any 1x3, 1x4, 2x2, 2x3, 2x4, 3x4, or 4x4 pixel area within that image. The images can be loaded in the right format with:

from PIL import Image
img = Image.open("img.png")
img = np.array(img)[:, :, :3]

sig = Image.open("sig.png")
sig = np.array(sig)[:, :, :3]

coords = signature_locations_in_image(signature=sig, image=img)
print(coords)

Here is an example image: example image

and an example signature (small dot next to the end of this line, it's only 1x4 pixels and barely visible): example signature

The signature in this case only appears in the letter E, hence it is detected 3 times in the image at the coordinates:

[(632, 66), (147, 84), (364, 300)]
\$\endgroup\$
4
  • 1
    \$\begingroup\$ Can you offer an example png? \$\endgroup\$
    – Reinderien
    Jan 5, 2023 at 13:19
  • \$\begingroup\$ I edited the question to include example image and signature \$\endgroup\$
    – Nik
    Jan 5, 2023 at 13:37
  • \$\begingroup\$ Are the image and signatures always binary? Or are you comparing gray-values, or even RGB values? For the binary case there is a very elegant and efficient solution. \$\endgroup\$ Feb 8, 2023 at 2:37
  • \$\begingroup\$ In my case, they are RGB values \$\endgroup\$
    – Nik
    Feb 8, 2023 at 6:22

1 Answer 1

2
\$\begingroup\$

The standard answer to this sort of question is you need to profile it first to make sure it's clear what's actually slow. If, for example, your coords = [... line is taking a fraction of a percent of your runtime, there's no real point in paying it any attention. Instead you should focus on the bits which are expensive. For a problem like this with an isolated chunk of code to focus on, my favourite profiler is line_profiler. You point it at your function of interest and run the program. At the end, it prints out that function, line by line, with annotations saying how often each line was hit and how much time each consumed. I recommend that you try that.

I haven't done any profiling of your code, so the rest of my answer is at best educated guesswork.

The first thing that I notice about your code is that you have access to numpy, but aren't making very much use of it. To be clear, your initial np.where call is very sensible, and I'm sure that's saving you a lot of time compared to running the same loop over every possible pixel. I'm guessing (sorry!) that the next thing which would benefit from speeding up is that repeated nested loop. Because raw Python is so much slower than numpy, the first thing I'd look for is a way to get numpy to do entire loops in one call. For example, you could use slicing (image[c_y : c_y + sig_size_y , c_x : c_x + sig_size_x]) to get the whole subsection of the image. Then you could do something like [numpy.array_equal][2] to compare the subsection with the signature.

The other thing which may help is doing a little bit more preprocessing before you get to the big coords loop, to exclude some of the false positives ahead of time. The notion is that the top left corner of the signature may be a common value. Finding the right filter can seem like a bit of a dark art, and it very much depends on the nature of your problem. One simple option would be to use a different pixel from your signature, perhaps looking up a histogram to see which is rarest. A second option would be to transform the image, such as adding up all the pixels in the signature-sized box around each pixel, and then looking for those pixels where this sum corresponds to the sum of the signature. A third particularly elegant option (which I don't think numpy supports, but scikit.image does) would be to do a convolution of the image and the signature. Whatever you pick, so long as it takes less time to preprocess the image ahead of your search than you save in not having so many false starts, you'll be in luck.

Anyway, like I said a lot of this is guesswork. Grab a profiler, see which bits are expensive, and focus there. Probably "Find how Numpy would do it" won't steer you too far wrong.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.