Answers.Body: <p>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.</p>
  <p>My PyTorch architecture:</p>
  <pre><code>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
  </code></pre>
  <p>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.</p>
  <p>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.</p>
  <p>The result:</p>
  <ul>
  <li>I test using the bottom-left (0,4,0), and it gives the output (0,3,1)</li>
  <li>I test using the bottom, the second from the left (3,0,0), and it gives the output (2,0,0)</li>
  </ul>
  <p>I think it's surprisingly good, for a very simple model and a very small train set.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-02-16T05:55:23.380Z
Answers.Text: 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](https://codegolf.stackexchange.com/questions/242611/counting-overlapping-objects).
Answers.UserDisplayName: Hans-Peter Stricker
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-02-16T08:34:09.953Z
Answers.Text: 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?
Answers.UserDisplayName: Hans-Peter Stricker
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-02-16T10:32:15.157Z
Answers.Text: 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
Answers.UserDisplayName: malioboro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-02-16T12:13:37.247Z
Answers.Text: Not really. I am testing with $N=30$ and $M=50$. But you are free to choose any numbers you want.
Answers.UserDisplayName: Hans-Peter Stricker
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-02-16T02:20:53.763Z
Answers.LastActivityDate: 2022-02-16T02:20:53.763Z
Answers.UserDisplayName: malioboro
Answers.Body: <p><em>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 &quot;symbols&quot; described below).</em></p>
  <hr />
  <p>I came up with a &quot;classic&quot; 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.</p>
  <p>The algorithm applies pixel-wise some &quot;masks&quot;, and if the mask &quot;fits&quot;, a corresponding &quot;stamp&quot; is printed over the pixel (and some of its surrounding pixels). This happens in an sequential fashion, i.e. order matters.</p>
  <p><strong>Legend:</strong> Gray pixels in masks mean &quot;doesn't matter&quot;, 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.</p>
  <p><strong>Step 1: Detect interior points</strong><br>
  Mask and stamp:<br>
  <a href="https://i.sstatic.net/KQHRY.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/KQHRY.png" alt="enter image description here" /></a></p>
  <p><strong>Step 2: Detect squares</strong><br>
  Mask and stamp:<br>
  <a href="https://i.sstatic.net/CzyHN.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/CzyHN.png" alt="enter image description here" /></a></p>
  <p><strong>Step 3: Detect spikes and corners</strong><br>
  Masks and stamps (to be rotated):<br>
  <a href="https://i.sstatic.net/ynbSI.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/ynbSI.png" alt="enter image description here" /></a><br>
  <a href="https://i.sstatic.net/agJBo.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/agJBo.png" alt="enter image description here" /></a><br>
  Mark objects blue that must be present and cannot me removed.</p>
  <p><strong>Step 4: Mark ambiguous objects and remove unnecessary objects</strong><br>
  Masks and stamps:<br>
  <a href="https://i.sstatic.net/kHP5z.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/kHP5z.png" alt="enter image description here" /></a>  (surrounding pixel may be missing)<br>
  <a href="https://i.sstatic.net/xD9fB.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/xD9fB.png" alt="enter image description here" /></a><br>
  <a href="https://i.sstatic.net/UJz74.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/UJz74.png" alt="enter image description here" /></a><br>
  <a href="https://i.sstatic.net/hTpIS.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/hTpIS.png" alt="enter image description here" /></a></p>
  <p><strong>Step 5: Keep further objects that should not be removed</strong><br>
  Masks and stamps (surrounding pixel may be missing):<br>
  <a href="https://i.sstatic.net/slog1.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/slog1.png" alt="enter image description here" /></a><br>
  <a href="https://i.sstatic.net/WQ3KP.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/WQ3KP.png" alt="enter image description here" /></a><br>
  <a href="https://i.sstatic.net/Yttn1.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/Yttn1.png" alt="enter image description here" /></a><br>
  Successively go through the objects with the most surrounding pixels while repeating step 4 after each application of the rule.</p>
  <p><strong>Step 6: Clean up</strong><br>
  Masks and stamps (to be rotated and reflected):<br>
  <a href="https://i.sstatic.net/ikUlX.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/ikUlX.png" alt="enter image description here" /></a><br>
  <a href="https://i.sstatic.net/2Wclm.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/2Wclm.png" alt="enter image description here" /></a><br>
  Objects may have survived after step 5 and are removed.</p>
  <hr />
  <p>Applying this algorithm I managed to identify the minimal set of objects that is needed to generate a given initial pattern.</p>
  <p><a href="https://i.sstatic.net/aEZFA.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/aEZFA.png" alt="enter image description here" /></a></p>
  <p>Is this algorithm &quot;folklore&quot; or of any – e.g. educational – value?</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-02-17T10:08:38.013Z
Answers.Text: This is not an answer, but a clarification or addendum to the question, better to write on it.
Answers.UserDisplayName: pasaba por aqui
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-02-17T10:11:29.700Z
Answers.Text: @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.)
Answers.UserDisplayName: Hans-Peter Stricker
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-02-17T10:13:11.010Z
Answers.Text: "it's not completely in the language of neural networks": it has absolutely no relation with a NN.
Answers.UserDisplayName: pasaba por aqui
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-02-17T10:18:25.843Z
Answers.Text: @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.
Answers.UserDisplayName: Hans-Peter Stricker
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-02-17T10:22:30.837Z
Answers.Text: @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.)
Answers.UserDisplayName: Hans-Peter Stricker
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-02-17T13:58:01.443Z
Answers.Text: To the unknown down-voter: Please give me hint why you downvoted.
Answers.UserDisplayName: Hans-Peter Stricker
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-02-16T14:34:51.140Z
Answers.LastActivityDate: 2022-02-18T08:50:34.860Z
Answers.LastEditDate: 2022-02-18T08:50:34.860Z
Answers.UserDisplayName: Hans-Peter Stricker
Body: <p>Consider the following task to be solved by a neural network: Given a <span class="math-container">$N\times N$</span> pixel grid with up to <span class="math-container">$M$</span> objects drawn on it, either squares (9 pixels) or diamonds (5 pixels):</p>
  <p><a href="https://i.sstatic.net/stm2o.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/stm2o.png" alt="3x3 grid of black squares (&quot;squares&quot;)" /></a>square
     <a href="https://i.sstatic.net/lUjYS.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/lUjYS.png" alt="3x3 grid with black squares forming a plus symbol (&quot;diamonds&quot;)" /></a>diamond</p>
  <p>The objects may overlap. The task is to give the <strong>minimal</strong> possible <strong>numbers of objects per shape</strong> that can be &quot;seen&quot; and distinguished in the picture and tell how many squares, how many diamonds, and how many objects with unknown shape there are.</p>
  <p>Here are some examples with <span class="math-container">$N = 7$</span> and <span class="math-container">$M=5$</span> with their intended numbers (<span class="math-container">$n_\square, n_\Diamond, n_?$</span>). The examples with <span class="math-container">$n_? = 1$</span> 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).</p>
  <p><a href="https://i.sstatic.net/HVIY0.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/HVIY0.png" alt="list of test cases containing 12 different grid configurations" /></a></p>
  <p>I wonder if this task can be solved for general <span class="math-container">$N$</span> and <span class="math-container">$M$</span> by simple multi-layer networks of standard neurons (e.g. McCulloch-Pitts cells) and how to design and train them.</p>
  <p>I further wonder if it could be a standard exercise in an introductory course in neural networks to &quot;hand-draw&quot; a neural network that solves the task (by giving explicit weights). If so I'm happy to see a standard solution (full-blown).</p>
  <p>This exercise could foster explainability and understandability of networks, I guess.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-02-15T09:45:35.720Z
Comments.Text: Can you put your specific question in the title? "Counting overlapping objects" is not specific and it's not a question.
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-02-15T10:36:14.343Z
Comments.Text: I do not understand your examples. In the first one, there are 5 possible rectangles and 9 diamonds. Why (4,0,1) ?
Comments.UserDisplayName: pasaba por aqui
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-02-15T12:57:38.980Z
Comments.Text: @pasabaporaqui: I'm looking for the **minimal** possible numbers. You can create the example with minimally 4 squares and 1 square-or-diamond.
Comments.UserDisplayName: Hans-Peter Stricker
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-02-15T12:58:22.843Z
Comments.Text: @nbro: I changed the title.
Comments.UserDisplayName: Hans-Peter Stricker
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-02-15T19:52:10.970Z
Comments.Text: Have you found a classic algorithm that solves the problem?
Comments.UserDisplayName: pasaba por aqui
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-02-15T21:15:38.620Z
Comments.Text: @pasabaporaqui: No, but I am working on one. Do you know one?
Comments.UserDisplayName: Hans-Peter Stricker
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-02-16T14:35:26.437Z
Comments.Text: @pasabaporaqui: I describe a "classic" algorithm in my answer.
Comments.UserDisplayName: Hans-Peter Stricker
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-02-17T10:09:39.453Z
Comments.Text: 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.
Comments.UserDisplayName: pasaba por aqui
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-02-17T10:12:41.767Z
Comments.Text: @pasabaporaqui: Thanks for declaring me a "very intelligent system";-)
Comments.UserDisplayName: Hans-Peter Stricker
Tags: <neural-networks><object-detection><deep-neural-networks><pattern-recognition><explainable-ai>
Title: How to count overlapping objects with neural networks
UserDisplayName: Hans-Peter Stricker
ThreadText: # How to count overlapping objects with neural networks
  
  (Asked by: username_0 on 2022-02-14)
  
  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")](https://i.sstatic.net/stm2o.png)](https://i.sstatic.net/stm2o.png)square
     [![3x3 grid with black squares forming a plus symbol ("diamonds")](https://i.sstatic.net/lUjYS.png)](https://i.sstatic.net/lUjYS.png)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](https://i.sstatic.net/HVIY0.png)](https://i.sstatic.net/HVIY0.png)
  
  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.
  
  **Tags:** neural-networks, object-detection, deep-neural-networks, pattern-recognition, explainable-ai
  
  > **Comments:**
  > **username_1**: Can you put your specific question in the title? "Counting overlapping objects" is not specific and it's not a question.  
  > **username_2**: I do not understand your examples. In the first one, there are 5 possible rectangles and 9 diamonds. Why (4,0,1) ?  
  > **username_0**: @username_2: I'm looking for the **minimal** possible numbers. You can create the example with minimally 4 squares and 1 square-or-diamond.  
  > **username_0**: @username_1: I changed the title.  
  > **username_2**: Have you found a classic algorithm that solves the problem?  
  > **username_0**: @username_2: No, but I am working on one. Do you know one?  
  > **username_0**: @username_2: I describe a "classic" algorithm in my answer.  
  > **username_2**: 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.  
  > **username_0**: @username_2: Thanks for declaring me a "very intelligent system";-)  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_3 on 2022-02-16. Score: 1
  
  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.
  
  > **Comments:**
  > **username_0**: 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](https://codegolf.stackexchange.com/questions/242611/counting-overlapping-objects).  
  > **username_0**: 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?  
  > **username_3**: 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  
  > **username_0**: Not really. I am testing with $N=30$ and $M=50$. But you are free to choose any numbers you want.  
  
  ---
  
  ### Answer by username_0 on 2022-02-16. Score: 0
  
  *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](https://i.sstatic.net/KQHRY.png)](https://i.sstatic.net/KQHRY.png)
  
  **Step 2: Detect squares**  
  Mask and stamp:  
  [![enter image description here](https://i.sstatic.net/CzyHN.png)](https://i.sstatic.net/CzyHN.png)
  
  **Step 3: Detect spikes and corners**  
  Masks and stamps (to be rotated):  
  [![enter image description here](https://i.sstatic.net/ynbSI.png)](https://i.sstatic.net/ynbSI.png)  
  [![enter image description here](https://i.sstatic.net/agJBo.png)](https://i.sstatic.net/agJBo.png)  
  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](https://i.sstatic.net/kHP5z.png)](https://i.sstatic.net/kHP5z.png) (surrounding pixel may be missing)  
  [![enter image description here](https://i.sstatic.net/xD9fB.png)](https://i.sstatic.net/xD9fB.png)  
  [![enter image description here](https://i.sstatic.net/UJz74.png)](https://i.sstatic.net/UJz74.png)  
  [![enter image description here](https://i.sstatic.net/hTpIS.png)](https://i.sstatic.net/hTpIS.png)
  
  **Step 5: Keep further objects that should not be removed**  
  Masks and stamps (surrounding pixel may be missing):  
  [![enter image description here](https://i.sstatic.net/slog1.png)](https://i.sstatic.net/slog1.png)  
  [![enter image description here](https://i.sstatic.net/WQ3KP.png)](https://i.sstatic.net/WQ3KP.png)  
  [![enter image description here](https://i.sstatic.net/Yttn1.png)](https://i.sstatic.net/Yttn1.png)  
  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](https://i.sstatic.net/ikUlX.png)](https://i.sstatic.net/ikUlX.png)  
  [![enter image description here](https://i.sstatic.net/2Wclm.png)](https://i.sstatic.net/2Wclm.png)  
  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](https://i.sstatic.net/aEZFA.png)](https://i.sstatic.net/aEZFA.png)
  
  Is this algorithm "folklore" or of any – e.g. educational – value?
  
  > **Comments:**
  > **username_2**: This is not an answer, but a clarification or addendum to the question, better to write on it.  
  > **username_0**: @username_2: 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.)  
  > **username_2**: "it's not completely in the language of neural networks": it has absolutely no relation with a NN.  
  > **username_0**: @username_2: 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.  
  > **username_0**: @username_2: 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.)  
  > **username_0**: To the unknown down-voter: Please give me hint why you downvoted.  
  
  ---
  
  