0
$\begingroup$

Imagine a grayscale image, $M$.

We know that somewhere within $M$ is a dark spot $S$ with brightness values of $0$.

Can we find the borders of $S$ using block matrix multiplication, such that the result of each block matrix multiplication is a probability that it contains $S$?

Example

$M = \begin{bmatrix} . \space . \space 0 \space . \space . \space . \space . \space . \space . \space . \space . \space . \space \\ 0 \space 0 \space 0 \space 0 \space . \space . \space . \space . \space . \space . \space . \space . \space \\ . \space 0 \space 0 \space . \space . \space . \space . \space 0 \space . \space . \space . \space . \space \\ . \space . \space . \space . \space . \space . \space . \space . \space . \space 0 \space . \space . \space \\ . \space . \space . \space . \space . \space . \space 0 \space . \space 0 \space . \space 0 \space . \space \end{bmatrix} $

$B= \text{ matrix made of blocks}$

$MB = \begin{bmatrix} \sim 1 \space \sim 0 \\ \sim 0 \space \sim 0 \end{bmatrix} \text{ if there were 4 blocks} $

Note

If there's another good way to efficiently identify where $S$ is, I'll accept that answer too.

$\endgroup$
7
  • $\begingroup$ What do you mean by probability? You did not mention any randomness in your problem statement. $\endgroup$ Commented Dec 10, 2024 at 17:32
  • $\begingroup$ @JairTaylor I mean probability that the block in question contains a dark spot. I did mention randomness; I wrote "Example". That means that M is not necessarily as described, it's just a sample matrix of grayscale values. The spot can be anywhere. Its placement is random. Of course, you can replace a probability metric with another metric of your own design that has the same function, such that dark spots bias the metric in an identifiable way. $\endgroup$ Commented Dec 10, 2024 at 18:36
  • $\begingroup$ This is still not very clear. You say "a" dark spot which would mean a single dark spot, but there are many 0-values in your matrix - are those all dark spots? Or what is the definition of dark spot? And what values do the dots represent? And what precisely is the intended probability distribution over these matrices - or, what random process generates them? $\endgroup$ Commented Dec 10, 2024 at 20:12
  • $\begingroup$ Also, if $M$ is random, then $MB$ is random as well so it doesn't make sense to speak of $MB$ representing probabilities - probabilities are usually not themselves random. There should just be a single, constant matrix that gives the probabilities. $\endgroup$ Commented Dec 10, 2024 at 20:15
  • $\begingroup$ @JairTaylor Yes, the other 0 values are there on purpose, because the other values outside of the single dark spot can take any value, including 0. The other 0 values demonstrate that there will be other 0 values which are "somewhat" (purposely non-specific terminology) less contiguous than the spot. The other values can not be said to follow any specific noise distribution. As a real image, you can't make any valid assumptions about the things outside of the dark spot. All you can say is that there is a contiguous group of dark pixels, which is randomly placed somewhere inside the image. $\endgroup$ Commented Dec 10, 2024 at 21:06

1 Answer 1

Reset to default
1
$\begingroup$

One option I thought of:

  1. replace all zeros with $i$
  2. normalize each column
  3. take the dot product of each column with the $i$ vector, $[i \space i \space i ...]$. The real part of the dot products are now a measure of how many zeros this column had.
  4. average the dot products

The result should now be a metric of how many zeros the matrix had.

$\endgroup$
6
  • 1
    $\begingroup$ This is just the average over columns of the average number of zeroes in each column. The gymnastics with $i$ are completely unnecessary. $\endgroup$ Commented Dec 11, 2024 at 0:14
  • $\begingroup$ @NicholasTodoroff it's my understanding that from a computational perspective, it's much faster to use a matrix multiplication because it's parallelizable. GPU are more optimized for that operation than executing if (zero)...then (add) operations when scrolling through a matrix. $\endgroup$ Commented Dec 11, 2024 at 19:30
  • 1
    $\begingroup$ (1) You can just parallize by column, matrix multiplication is irrelevant. (2) You're doing lots of useless calculations because you throw away the imaginary part. (3) All you did was move the conditional to the step where you replace $0$ with $i$, and if you're visiting every zero like this anyway why not just count them? (4) This conversion to complex values is a change of the data type help by your matrix, which will require (unecessarily) copying the entire matrix. $\endgroup$ Commented Dec 11, 2024 at 22:17
  • $\begingroup$ 1) I don't understand. 2) But it's still a procedure that doesn't require a conditional. 3) You don't exactly use a conditional to replace 0 with i. It's more like adding i/(x^x), where x is the value of the entry. Then any 0 is just i and any non zero is basically still itself. 4) That's anyways necessary, because image data types are RGBA, so when you're inserting those (reduced, not RGBA) values into a normal matrix, you can just put it in a complex matrix instead of a normal one. I will say though, that when I benchmarked this approach, it was 1/4th as fast as manually converting. $\endgroup$ Commented Dec 11, 2024 at 22:28
  • $\begingroup$ "'It's more like adding i/(x^x)" But then nonzero entries in the matrix have a nonzero imaginary component, and your calculation isn't doing what you want? Anyway, if you haven't tried the straightforward method, you should; my understanding is that tiny branching like this is a non-issue in CUDA, and anyway compilers are always more sophisticated than you than. Premature optimization is the root of all evil. $\endgroup$ Commented Dec 12, 2024 at 0:56

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.