计算QR码对齐图案的位置

Question

我需要知道如何计算QR码对齐图案的位置，这些位置在ISO/IEC 18004:2000附录E的表格中有定义。

我不理解它是如何计算的。例如，如果以版本16为例，使用{6,26,50,74}来计算位置，点之间的距离为{20,24,24}。如果点之间的距离{22,24,22}更加均匀分布，为什么不是{6,28,52,74}？

我想知道如何通过程序生成这些位置。

- Danguafer

---

嗯...这是一个Python问题，还是与语言无关？目前它没有任何语言标签，但至少一个Python特定的问题被标记为重复的。接受的答案在这里是用Python编写的，但可能只是巧合。 - John Y

Answer 1

虽然规范提供了一个对齐表，但这是个合理的问题（我自己也遇到了 :-)) - 通过过程生成位置具有其优点（减少打字错误，减小代码占用空间，知道位置的模式/属性）。

我很高兴地报告，确实存在一个过程（而且它甚至相当简单）。规范本身就说明了大部分内容：

[对齐图案] 尽可能均匀地分布在定时图案和符号反面之间，任何不均匀的间隔都将被容纳在定时图案和符号内的第一个对齐图案之间。

也就是说，仅第一个和第二个坐标之间的间隔可能与其余间隔不同。剩下的必须相等。 当然，另一个重要的部分是，为了使AP与定时图案相符，间隔必须是均匀的。 剩下棘手的部分只是正确进行四舍五入罢了。

无论如何-这里是打印对齐位置表格的代码：

def size_for_version(version):
    return 17 + 4 * version

def alignment_coord_list(version):
    if version == 1:
        return []
    divs = 2 + version // 7
    size = size_for_version(version)
    total_dist = size - 7 - 6
    divisor = 2 * (divs - 1)
    # Step must be even, for alignment patterns to agree with timing patterns
    step = (total_dist + divisor // 2 + 1) // divisor * 2 # Get the rounding right
    coords = [6]
    for i in range(divs - 2, -1, -1): # divs-2 down to 0, inclusive
        coords.append(size - 7 - i * step)
    return coords

for version in range(1, 40 + 1): # 1 to 40 inclusive
    print("V%d: %s" % (version, alignment_coord_list(version)))

- eriksoe

---

现在已经很晚了，但我也有同样的问题，想知道如何计算对齐图案的位置。你的算法是错误的，特别是V36位置是不正确的。它应该是[6, 24, 50, 76, 102, 128, 154]，而你的代码得到的是[6, 34, 58, 82, 106, 130, 154]。你是怎么得出你的算法的？ - user1002430

V39也是错误的。正确的序列是[6, 26, 54, 82, 110, 138, 166]。你的代码得到的是[6, 36, 62, 88, 114, 140, 166]。 - user1002430

Answer 2

这是一个Python解决方案，基本上相当于由@jgosar发布的C#解决方案，只是它纠正了与thonky.com table版本32偏离的问题（其他解决方案报告倒数第二个位置的值为110，而链接的表格显示为112）：

def get_alignment_positions(version):
    positions = []
    if version > 1:
        n_patterns = version // 7 + 2
        first_pos = 6
        positions.append(first_pos)
        matrix_width = 17 + 4 * version
        last_pos = matrix_width - 1 - first_pos
        second_last_pos = (
            (first_pos + last_pos * (n_patterns - 2)  # Interpolate end points to get point
            + (n_patterns - 1) // 2)                  # Round to nearest int by adding half
                                                      # of divisor before division
            // (n_patterns - 1)                       # Floor-divide by number of intervals
                                                      # to complete interpolation
            ) & -2                                    # Round down to even integer
        pos_step = last_pos - second_last_pos
        second_pos = last_pos - (n_patterns - 2) * pos_step
        positions.extend(range(second_pos, last_pos + 1, pos_step))
    return positions

更正包括首先将倒数第二个位置四舍五入到最近的整数，然后向下取整到最近的偶数（而不是直接向下取整到最近的偶数）。

免责声明：像@jgosar一样，我不知道thonky.com表格是否正确（我不会购买规范来找出）。我只是通过将表格粘贴到上述函数的适当包装器中进行验证，以使我的解决方案与该表在其当前版本中匹配。

- Ovaflo

Answer 3

最高评分回答的一些评论表明它不是100％准确的，所以我也贡献了我的解决方案。

我的解决方案是用C#编写的。将其翻译为您选择的语言应该很容易。

private static int[] getAlignmentCoords(int version)
    {
        if (version <= 1)
        {
            return new int[0];
        }

        int num = (version / 7) + 2;//number of coordinates to return
        int[] result = new int[num];

        result[0] = 6;

        if (num == 1)
        {
            return result;
        }

        result[num - 1] = 4 * version + 10;

        if (num == 2)
        {
            return result;
        }

        result[num - 2] = 2 * ((result[0] + result[num - 1] * (num - 2)) / ((num - 1) * 2)); //leave these brackets alone, because of integer division they ensure you get a number that's divisible by 2

        if (num == 3)
        {
            return result;
        }

        int step = result[num - 1] - result[num - 2];

        for (int i = num - 3; i > 0; i--)
        {
            result[i] = result[i + 1] - step;
        }

        return result;
    }

我得到的值与此处显示的相同：http://www.thonky.com/qr-code-tutorial/alignment-pattern-locations/ 总结一下，第一个坐标始终为6。

最后一个坐标始终比图像大小小7。图像大小计算公式为4*version+17，因此最后一个坐标为4*version+10。

如果坐标精确地平均分布，则倒数第二个坐标位置为(first_coordinate+(num-2) * last_coordinate)/(num-1)，其中num是所有坐标的数量。 但是，这些坐标并不是均匀分布的，因此必须将此位置减少到偶数。

其余每个坐标与下一个坐标之间的距离与最后两个坐标之间的距离相同。

免责声明：我没有阅读任何文档，只编写了一些代码，生成了一个与我链接表格中的序列相同的数字序列。

- jgosar

---

此解决方案现在与版本32的链接表不一致。该解决方案为result[num - 2]提供了坐标110，而链接表显示为112。至少有一个生成器和一个扫描仪似乎与链接表一致（该链接表似乎是在本答案撰写几个月后更新的）。 - Ovaflo

Answer 4

抱歉我的英语不好。 我希望这可以帮助你，不要回复晚了。 首先，标准忘记了一个重要的事情，即左上角被定义为(0,0)。 {6, 26, 50, 74}表示对齐点的行坐标和列坐标，我不知道他们为什么这样做，也许是为了节省空间。但我们将所有值组合在一起，例如：

{ 6, 26, 50, 74 }

"and we get:"

{ 6 , 6  } ---> ( the x coordinate is 6, and the y is 6, from top/left )
{ 6 , 26 }
{ 6 , 50 }
{ 6 , 74 }
{ 26, 26 }
{ 26, 50 }
{ 26, 74 }
{ 50, 50 }
{ 50, 74 }
{ 74, 74 }

这些点是对齐图案中心的实际坐标。

提示：如果一个位置有位置检测图案，我们会忽略输出对齐，比如位置(6, 6)。

我之前也有这个问题，但现在我解决了，所以我希望你也能解决它。

祝好运~

- Samlv9

Answer 5

从@ericsoe的回答开始，注意到它对v36和v39不正确（感谢@Ana的指出），我开发了一个返回正确序列的函数。请原谅JavaScript（尽管很容易翻译成其他语言）：

function getAlignmentCoordinates(version) {
  if (version === 1) {
    return [];
  }
  const intervals = Math.floor(version / 7) + 1;
  const distance = 4 * version + 4; // between first and last alignment pattern
  const step = Math.ceil(distance / intervals / 2) * 2; // To get the next even number
  return [6].concat(Array.from(
    { length: intervals },
    (_, index) => distance + 6 - (intervals - 1 - index) * step)
  );
}

- MaxArt

---

我已经使用苹果的CoreImage QR码生成器进行了检查，除了v32（step应为26而不是28），它似乎与其对齐模式匹配。 OP链接的表格还声明了{6,34,60,86,112,138}。 对于v32，distance / intervals == 26.4，这是唯一一个小数部分<0.5的偶数，因此我猜正确的过程是先四舍五入到最近的整数（不是ceil()），然后再取下一个最大的偶数。 - YourMJK

Answer 6

看起来大多数答案对于所有版本（特别是v32、v36和v39）都不正确，或者非常复杂。
基于@MaxArt的绝妙解决方案（它为v32生成了错误的坐标），这里有一个C函数，它可以计算出所有版本的正确坐标：

#include <math.h>

int getAlignmentCoordinates(int version, int *coordinates) {
    if (version <= 1) return 0;
    int intervals = (version / 7) + 1;  // Number of gaps between alignment patterns
    int distance = 4 * version + 4;  // Distance between first and last alignment pattern
    int step = lround((double)distance / (double)intervals);  // Round equal spacing to nearest integer
    step += step & 0b1;  // Round step to next even number
    coordinates[0] = 6;  // First coordinate is always 6 (can't be calculated with step)
    for (int i = 1; i <= intervals; i++) {
        coordinates[i] = 6 + distance - step * (intervals - i);  // Start right/bottom and go left/up by step*k
    }
    return intervals+1;
}

关键是先将除法四舍五入到最近的整数（而不是向上），然后再将其四舍五入到下一个最大的偶数。

下面的C程序使用此函数生成与OP链接的{{link1：ISO / IEC 18004:2000附录E表}}和{{link2：thonky.com上找到的（更新后的）列表}}中相同的值：

#include <stdio.h>

void main() {
    for (int version = 2; version <= 40; version++) {
        int coordinates[7];
        int n = getAlignmentCoordinates(version, coordinates);
        printf("%d:", version);
        for (int i = 0; i < n; i++) {
            printf(" %d", coordinates[i]);
        }
        printf("\n");
    }
}

- YourMJK

Answer 7

我不知道这是否是一个有用的问题。它只是这样，如果它是{22,24,22}，那么也没有太大关系。你为什么要问呢？ 我猜测间距应该是4个模块的倍数。

- Sean Owen

---

我提出这个问题是为了确保我生成的QR码符合标准。如果我无法理解该表背后的逻辑，我将无法生成版本高于40的QR码。并且，请让我明确一点...当你说“它就是这样，如果是{22,24,22}也没有什么关系”时，你是想说({20,24,24})是标准，我不能改变它，还是说即使是{22,24,22}，读者也能正确理解QR码？感谢您的回复。您的QR码阅读器非常棒。 - Danguafer

而且，我不明白你的猜测。你所说的“4的倍数模块”是什么意思？ - Danguafer

所以你想要构建一种符合标准的实现，而且你有了完全定义正确行为的标准。你为什么要想着做些不同的事情呢？不要这样做。标准是 {6,26,50,74}，所以当然要这样做。不存在版本 > 40 的 QR 码。我的观察是距离 {20,24,24} 是 4 的倍数，而 {22,24,22} 不是。 - Sean Owen