Sokumenzu / 侧视图生成器背后的算法

Question

我发现了一个有趣的网站，可以生成给定输入文本的“旋转字谜”，名为Sokumenzu / Side View Generator，它会生成以下动画结果：

我非常想了解它背后的算法。我尝试查看是否有任何公开的JavaScript可以帮助我理解，但它是一团混乱的混淆，而且我的语言掌握程度不够牢固，无法确定真正的工作是否在服务器端完成。

我大致了解了如何构建类似系统的轮廓，但它会有自己的缺点（如果真正的方法是硬编码，则可能有小优势）：

预计算

Define an nxnxn cube composed of equally sized sub-cubes
Each sub-cube may either contain a sphere or not
Create a virtual camera orthogonal to one of the cube's faces a fixed distance away
For each of the possible states of the cube:
    Cast rays from the camera and build up an nxn matrix of which cells appear occupied from the camera's point of view.
    Input this matrix into a neural network / other recognizer which has been pre-trained on the latin alphabet.
    If the recognizer matches a character: 
        Add the state which triggered recognition to a hashtable indexed on the character it recognized. 
        Handle collisions (there should be many) by keeping the highest confidence recognition
For every key in the hashtable
    Rotate the corresponding state in fixed increments recognizing characters as before
    If a character other than the current key is recognized:
        Add that character and the amount of rotation performed to a tuple in a list.
    Store each of these lists in the hashtable indexed on the current key.

查询

Generate all of the permutations achieved by substituting each of the characters linked in the list associated with input character at that position.
Find the first dictionary word in the list of permutations
Visualize using the rotation information stored for each character

显然，这不是使用的相同算法，因为它是基于逐个字符处理的。我想你可以采用类似的方法按单词进行处理，将整个卷的面部作为文本识别器的输入，但我相信他们可能已经做了更简单、更聪明和更高效的事情。

这个可怕的想法的一个优点是，通过重新训练识别器，您可以支持其他字符集。

有人知道这实际上是如何工作的吗？

- DuncanACoulter

Answer 1

我认为这比那要简单得多。

对于每一对字母（它们是2D对象），您可以尝试找到一个3D对象，根据从0°角或90°角看到的情况，将其投影到其中之一。

在3D网格上找到一组3D点，使其根据投影分别显示为给定的两组2D点，看起来像是离散层析成像问题，您可以在维基百科上阅读相关信息：https://en.wikipedia.org/wiki/Discrete_tomography 请注意，您可以逐行处理3D形状，并实际上仅解决2D实例。

完成预处理并且有了字母图形后，如果存在一个3D形状，可以从不同的角度产生这两个字母，则我怀疑算法的工作方式如下：

计算原单词的字母集。然后，探索所有可以通过将输入的一个字母更改为与之相关联的字母而拥有的字母集。当您找到一个可以组成单词的字母集时，请停止。（可能有一个预先计算的字典，它在单词和字母集之间进行匹配）

如果需要将3D形状投影到单词的不同部分（也就是说，您需要具有在单词的位置2或4中投影的形状，具体取决于它是原始单词还是另一个单词，例如D（u）ncan - Une（v）en），则计算适当的置换矩阵。像这样为您的名字：

DU__________

______uv____

__nn________

____ce______

________ae__

__________nn

（每对字母的第一个字母是向左投影的字母，第二个字母是向下投影的字母）

它是从置换矩阵计算出来的：

100000

000100

010000

001000

000010

000001

以及字母的匹配。（D-U，c-e ...）。

- A.N.

---

感谢您向我介绍离散断层成像和置换矩阵。 - DuncanACoulter

Answer 2

链接的演示似乎适用于预先计算或甚至手工制作的字母对。A.N.已经指出了如何重新排列字母对。请注意，Sokumenzu有时无法生成另一个单词，例如使用“Lydia”。它然后将该单词映射到自身。当找不到与给定大小写匹配的内容时，它还会尝试全大写版本。

如果您想要更通用的解决方案，可以组合具有相同高度的任意位图，前提是每个至少在第一个位图中具有一个像素的行也在第二个位图中具有像素。(因此，您不能在一个面上放置“i”，在另一个面上放置“l”，因为在“i”的点和柄之间的行中将有一个像素。)

您可以独立创建立方体的层。您的目标是拥有至少一个像素，可以投影到两个位图的每个像素。

创建每个位图填充像素的位置列表。如果其中一个列表为空，则没有解决方案。从较长的列表中创建成对，以便使用所有像素，并且每个来自较短列表的像素至少使用一次。

根据你想要实现的自顶向下外观，你可以使用不同的算法。如果你想创建一个对角线，可以使用Bresenham算法。你也可以通过随机分配对来创建散乱的外观，只要至少使用每个像素一次。

举个例子：

                · · · · · · · · · ·
                · · ● · · · · · ○ ○    #
                · · · · · · · · · ·
                · ● · ○ · · ○ · ● ·    #
                · ○ ○ ● · · ● · · ●    #

                  # # #     #   # #

无论是圆盘还是圆形都会产生哈希图案，但从上面看，圆形看起来更整洁，可能在透视方面也更有效。

- M Oehm