0
$\begingroup$

Consider the following task to be solved by a neural network: Given a $N\times N$ pixel grid with up to $M$ objects drawn on it, either squares (9 pixels) or diamonds (5 pixels):

3x3 grid of black squares ("squares")square    3x3 grid with black squares forming a plus symbol ("diamonds")diamond

The objects may overlap. The task is to give the minimal possible numbers of objects per shape that can be "seen" and distinguished in the picture and tell how many squares, how many diamonds, and how many objects with unknown shape there are.

Here are some examples with $N = 7$ and $M=5$ with their intended numbers ($n_\square, n_\Diamond, n_?$). The examples with $n_? = 1$ are those with pixels that may either come from a square or a diamond (highlighted in black, but not bearing any information that may be used).

list of test cases containing 12 different grid configurations

I wonder if this task can be solved for general $N$ and $M$ by simple multi-layer networks of standard neurons (e.g. McCulloch-Pitts cells) and how to design and train them.

I further wonder if it could be a standard exercise in an introductory course in neural networks to "hand-draw" a neural network that solves the task (by giving explicit weights). If so I'm happy to see a standard solution (full-blown).

This exercise could foster explainability and understandability of networks, I guess.

Improve this question
$\endgroup$
9
  • $\begingroup$ Can you put your specific question in the title? "Counting overlapping objects" is not specific and it's not a question. $\endgroup$
    – nbro
    Commented Feb 15, 2022 at 9:45
  • $\begingroup$ I do not understand your examples. In the first one, there are 5 possible rectangles and 9 diamonds. Why (4,0,1) ? $\endgroup$
    – pasaba por aqui
    Commented Feb 15, 2022 at 10:36
  • $\begingroup$ @pasabaporaqui: I'm looking for the minimal possible numbers. You can create the example with minimally 4 squares and 1 square-or-diamond. $\endgroup$
    – Hans-Peter Stricker
    Commented Feb 15, 2022 at 12:57
  • 1
    $\begingroup$ @nbro: I changed the title. $\endgroup$
    – Hans-Peter Stricker
    Commented Feb 15, 2022 at 12:58
  • 1
    $\begingroup$ Analyzing the algorithm: your steps 1 and 2 are a morphological erosion. Remainder is the login to obtain a minimal set. From the point of view of AI, a erosion could be considered a preprocess stage before a NN. Remainders rules could be inferred by a very intelligent system, not an usual NN. In conclusion, to your question: no, this is not standard exercise in an introductory course in neural networks. $\endgroup$
    – pasaba por aqui
    Commented Feb 17, 2022 at 10:09

2 Answers 2

Reset to default
1
$\begingroup$

I'm not sure if you are looking for this. But I just tried to create a simple neural network without a hidden layer and activation function, and (surprisingly) it works pretty well.

My PyTorch architecture:

class Net2(nn.Module):
   
    def __init__(self, N):
        super(Net2, self).__init__()
        self.out = nn.Linear(49, 3)
    
    def forward(self, x):
        x = x.reshape(x.shape[0], -1)
        x = self.out(x)
        return x

The input image is represented as a binary matrix. And then, I try to flatten the input and feed it to get three output neurons.

I train the model in 500 epochs optimized using SGD. I use your image samples as a train set, except the bottom left (0,4,0) and its right side (3,0,0). I also add five other samples that represent more the diamond shape combination (as in the train set, only three images with the significant diamond shape). So in total I only using 15 images in samples.

The result:

  • I test using the bottom-left (0,4,0), and it gives the output (0,3,1)
  • I test using the bottom, the second from the left (3,0,0), and it gives the output (2,0,0)

I think it's surprisingly good, for a very simple model and a very small train set.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks. I'm definitely also looking for trained solutions like yours, but mainly to compare them with a manually designed solution. Looking at your trained network: do you understand what it does and can describe it explicitly in the form of some rules? In case you want to train your network with other input, you can create training data with a imple script that I gave in another question. $\endgroup$
    – Hans-Peter Stricker
    Commented Feb 16, 2022 at 5:55
  • $\begingroup$ Please note, that $N$ and $M$ are supposed to be arbitrary and not restricted to $N=7$ and $M=5$ (as in my examples). What happens when your network has an input layer of size $30\times 30 = 900$ and up to $M= 50$ objects may be present? How many training images and how many epochs would your network need then? $\endgroup$
    – Hans-Peter Stricker
    Commented Feb 16, 2022 at 8:34
  • $\begingroup$ ah I see... I think it'll be more challenging as neural network tend to use fixed-size input. Are there any constrains for $N$ and $M$? like the upper bound $\endgroup$
    – malioboro
    Commented Feb 16, 2022 at 10:32
  • $\begingroup$ Not really. I am testing with $N=30$ and $M=50$. But you are free to choose any numbers you want. $\endgroup$
    – Hans-Peter Stricker
    Commented Feb 16, 2022 at 12:13
0
$\begingroup$

The following is only a partial answer, but I claim that it is possible to make the algorithm into a fully specified neural network with at least seven layers (one input layer and six layers for each of the "symbols" described below).

I came up with a "classic" algorithm that solves the problem (as far as I can see almost perfectly) and is apparently inspired by neural networks. Nevertheless I can hardly imagine a genuinely different algorithm.

The algorithm applies pixel-wise some "masks", and if the mask "fits", a corresponding "stamp" is printed over the pixel (and some of its surrounding pixels). This happens in an sequential fashion, i.e. order matters.

Legend: Gray pixels in masks mean "doesn't matter", gray pixels in stamps are not printed. Gray circles in stamps mean that symbols are not overwritten, only the background of the pixel is overwritten.

Step 1: Detect interior points
Mask and stamp:
enter image description here

Step 2: Detect squares
Mask and stamp:
enter image description here

Step 3: Detect spikes and corners
Masks and stamps (to be rotated):
enter image description here
enter image description here
Mark objects blue that must be present and cannot me removed.

Step 4: Mark ambiguous objects and remove unnecessary objects
Masks and stamps:
enter image description here (surrounding pixel may be missing)
enter image description here
enter image description here
enter image description here

Step 5: Keep further objects that should not be removed
Masks and stamps (surrounding pixel may be missing):
enter image description here
enter image description here
enter image description here
Successively go through the objects with the most surrounding pixels while repeating step 4 after each application of the rule.

Step 6: Clean up
Masks and stamps (to be rotated and reflected):
enter image description here
enter image description here
Objects may have survived after step 5 and are removed.

Applying this algorithm I managed to identify the minimal set of objects that is needed to generate a given initial pattern.

enter image description here

Is this algorithm "folklore" or of any – e.g. educational – value?

Improve this answer
$\endgroup$
6
  • $\begingroup$ This is not an answer, but a clarification or addendum to the question, better to write on it. $\endgroup$
    – pasaba por aqui
    Commented Feb 17, 2022 at 10:08
  • $\begingroup$ @pasabaporaqui: I think, it's better here as an answer. First, it would blow up the question, and second it is a (partial) answer to the explicit question for a full-blown standard solution. (Only partial because it's not completely in the language of neural networks.) $\endgroup$
    – Hans-Peter Stricker
    Commented Feb 17, 2022 at 10:11
  • $\begingroup$ "it's not completely in the language of neural networks": it has absolutely no relation with a NN. $\endgroup$
    – pasaba por aqui
    Commented Feb 17, 2022 at 10:13
  • $\begingroup$ @pasabaporaqui: The relations maybe are not obvious but they exist: We have edge/interior and shape detectors working very much like neuronal detectors, and information is only processed locally. $\endgroup$
    – Hans-Peter Stricker
    Commented Feb 17, 2022 at 10:18
  • $\begingroup$ @pasabaporaqui: I claim that I could mimick the algorithm by a hand-drafted multi-layered and possibly recursive network of McCulloch-Pitts cells. (My intuition tells me.) $\endgroup$
    – Hans-Peter Stricker
    Commented Feb 17, 2022 at 10:22

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .