0
$\begingroup$

The Situation
I am an electronics engineer and on a volunteer team that have built a prototype eye that has 200*200 sensors that are mapped to the optic nerve, the connection to the optic nerve is random (organic connection is grown) so I need to have the patient draw what they see, I am trying to limit the number of drawings (difficult for a blind person) the patient has to do to get the relationship between the artificial eye output and the correct perception of the image.

The Problem
Given a input image/matrix and an viewable/readable output matrix, what is an algorithm to automatically identify the encoding with the least number of iterations.

enter image description here

By changing the input one pixel at a time and then examining the output, the relationship can be discovered, this is, however, very inefficient.

Improve this question
$\endgroup$
3
  • $\begingroup$ The answer to the question is "yes, there is such an algorithm". Hint: given the above example, you can do it with 6 queries. $\endgroup$
    – poncho
    Sep 6, 2014 at 0:16
  • 2
    $\begingroup$ @AnthonyKeane: this isn't a C writing service. I would suggest instead that you think about the problem; if you were given a 2x2 array, how can you do it with 2 queries? Then, if you were given a 4x4 array, how can you do it with 4 queries? If you can answer those two questions, generalizing it to nxn arrays should be easy. $\endgroup$
    – poncho
    Sep 8, 2014 at 12:38
  • 1
    $\begingroup$ How do you represent the "encoding"? Is this to calibrate the software with some known images? If arbitrary mappings are allowed, it's unlikely that one letter is enough to learn it. $\endgroup$
    – Raphael
    Sep 10, 2014 at 12:58

1 Answer 1

Reset to default
3
$\begingroup$

Number the pixels from $0$ to $n^2-1$. Then create $\lceil \log_2n^2\rceil$ many pictures. In the $i$-th picture all pixels are black, if the $i$-th bit in their number is $1$, white otherwise.

Note: If you have $2^k$ colors available, you can choose the color for each pixel based on $k$ successive bits of the number. This will reduce the number of images by a factor of $k$.

Improve this answer
$\endgroup$
4
  • $\begingroup$ huh - how does apply in code? $\endgroup$
    – Anthony Keane
    Sep 11, 2014 at 8:11
  • $\begingroup$ @AnthonyKeane I don't mean to be rude, but I doubt you will find someone on here to write the code for you. You mention this is a volunteer team. Check with a local university and see if they will send out an email to their computer science, EE, and computer engineering students to see if anyone wants to volunteer their time to write the code for you. $\endgroup$
    – mikeazo
    Sep 11, 2014 at 16:23
  • $\begingroup$ @mikeazo so it appears $\endgroup$
    – Anthony Keane
    Sep 13, 2014 at 9:30
  • $\begingroup$ Unfortunately this approach won't work since a human almost certainly won't be able to draw pixel correct 200x200 images. $\endgroup$
    – CodesInChaos
    Sep 17, 2014 at 15:45

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.