关于图片的去重拼接

没找到有效的编程解决方法，不过找到了使用一款叫 mathematica 的软件实现的方法，解决这个问题的关键其实是找出重叠区域。

链接中探讨的方法主要有两种：

• Longest Common Subsequence Positions：这个概念很容易理解，但是如果对比整张图片运算量很大，似乎不适合小程序；
• 第一张图片和第二张图片各取出一部分，然后计算各像素各通道的差值，最后拿到最大的 100 个差值并求和，在重叠区这个求和值会突然变小：distance[align_] := Total@TakeLargest[Abs[Flatten[id1[[-align ;;]] - id2[[;; align]]]], 100]；

我写的微信小程序“拼长图”也支持去重拼接手机截图，但实现方法和上面两种都不一样，我用 pixelMatch 逐行比较两张图片在同一位置的两个像素，如果某一行相同或不同，则可以视为进入重叠区域或离开重叠区域，如果连续多行都一样，则找到了重叠临界线。

链接探讨的两种方法运算量都较高，但准确性应该比我的好。

2022/12/09 补充：odiff 是类似 pixelMatch 的工具，但速度比 pixelMatch 快很多。

2024/0726 补充：有人提到可以试试 pHash，js 代码参考 imagehash-web、js-image-similarity。我试了一下，发现并不能准确找到重叠区域，以下是在小程序计算 pHash 的代码。也可以用 jimp 计算。

const cosCache = {} as Record<string, any>;

let c1: any;
let c2: any;

Page({
  onLoad: async function () {
    const p1 = new Promise((resolve) => {
      this.createSelectorQuery()
        .select("#canvas_1")
        .fields({ node: true, size: true })
        .exec((res) => {
          const canvas = res[0].node;
          canvas.width = 32;
          canvas.height = 32;
          const ctx = canvas.getContext("2d");
          resolve({ canvas, ctx });
        });
    });
    const p2 = new Promise((resolve) => {
      this.createSelectorQuery()
        .select("#canvas_2")
        .fields({ node: true, size: true })
        .exec((res) => {
          const canvas = res[0].node;
          canvas.width = 32;
          canvas.height = 32;
          const ctx = canvas.getContext("2d");
          resolve({ canvas, ctx });
        });
    });
    [c1, c2] = await Promise.all([p1, p2]);
    const duplicatedLine = await this.getLastDuplicatedLineTop();
    console.log(duplicatedLine);
  },

  //获取两张截屏顶部重叠区域的最后一行
  getLastDuplicatedLineTop: async function () {
    const image1 = "./images/screenshot1.png";
    const image2 = "./images/screenshot2.png";
    const [imageInfo1, imageInfo2] = await Promise.all([
      wx.getImageInfo({ src: image1 }),
      wx.getImageInfo({ src: image2 }),
    ]);
    const max = Math.min(imageInfo1.height, imageInfo2.height);
    for (let x = 1; x < max; x = x + 300) {
      const diff = await this.compareImage(image1, 0, x, image2, 0, x);
      if (diff > 5) {
        for (let y = x - 300; y < x; y = y + 100) {
          const diff = await this.compareImage(image1, 0, y, image2, 0, y);
          if (diff > 5) {
            for (let z = y - 100; z < y; z = z + 50) {
              const diff = await this.compareImage(image1, 0, z, image2, 0, z);
              if (diff > 5) {
                for (let s = z - 50; s < z; s = s + 5) {
                  const diff = await this.compareImage(
                    image1,
                    0,
                    s,
                    image2,
                    0,
                    s
                  );
                  if (diff > 5) {
                    for (let a = s - 5; a < s; a = a + 1) {
                      const diff = await this.compareImage(
                        image1,
                        0,
                        a,
                        image2,
                        0,
                        a
                      );
                      if (diff > 5) {
                        return a - 1;
                      }
                    }
                    break;
                  }
                }
                break;
              }
            }
            break;
          }
        }
        break;
      }
    }
  },

  compareImage: async function (
    image1: string,
    sy1: number,
    sh1: number,
    image2: string,
    sy2: number,
    sh2: number
  ) {
    const p1 = this.getImageData("#canvas_1", image1, sy1, sh1);
    const p2 = this.getImageData("#canvas_2", image2, sy2, sh2);
    const [imageData1, imageData2] = await Promise.all([p1, p2]);
    const pHash1 = this.getHashFromImagedata(imageData1);
    const pHash2 = this.getHashFromImagedata(imageData2);
    const diff = this.hammingDistance(pHash1, pHash2);
    return diff;
  },

  getImageData: async function (
    canvasId: string,
    imagePath: string,
    sy: number,
    sh: number
  ) {
    return new Promise((resolve) => {
      const { canvas, ctx } = canvasId === "#canvas_1" ? c1 : c2;
      const image = canvas.createImage();
      image.onload = async () => {
        const sx = 0;
        const sw = image.width;
        const dx = 0;
        const dy = 0;
        const dw = canvas.width;
        const dh = canvas.height;
        ctx.drawImage(image, sx, sy, sw, sh, dx, dy, dw, dh);
        const data = ctx.getImageData(dx, dy, dw, dh);
        resolve(data);
      };
      image.src = imagePath;
    });
  },

  getHashFromImagedata: function (data: ImageData) {
    const pixels = this.grayScaleConverter(data.data);
    const dctOut = this.dctTransform(pixels);
    const size = 8;
    const imageSize = 32;
    const dctLowFreq = new Float64Array(size * size);
    const sorted = new Float64Array(size * size);
    let ptrLow = 0;
    let ptr = 0;
    for (let i = 0; i < size; i++) {
      for (let j = 0; j < size; j++) {
        dctLowFreq[ptrLow] = dctOut[ptr];
        sorted[ptrLow] = dctOut[ptr];
        ptrLow += 1;
        ptr += 1;
      }
      ptr += imageSize - size;
    }
    const med = this.median(sorted);
    const hash = new Uint8ClampedArray(size * size);
    for (let i = 0; i < hash.length; ++i) {
      hash[i] = dctLowFreq[i] > med ? 1 : 0;
    }
    return hash;
  },

  hammingDistance: function (
    hashOne: Uint8ClampedArray,
    hashTwo: Uint8ClampedArray
  ) {
    if (hashOne.length !== hashTwo.length) {
      throw new Error(
        "Cannot compare two ImageHash instances of different sizes"
      );
    }

    let distance = 0;
    for (let i = 0; i < hashTwo.length; i++) {
      if (hashTwo[i] !== hashOne[i]) {
        distance += 1;
      }
    }

    return distance;
  },

  toHexString: function (binArray: Uint8ClampedArray) {
    let str = "";
    for (let i = 0; i < binArray.length; i += 8) {
      const c =
        binArray[i] |
        (binArray[i + 1] << 1) |
        (binArray[i + 2] << 2) |
        (binArray[i + 3] << 3) |
        (binArray[i + 4] << 4) |
        (binArray[i + 5] << 5) |
        (binArray[i + 6] << 6) |
        (binArray[i + 7] << 7);
      str += c.toString(16).padStart(2, "0");
    }
    return str;
  },

  fromHexString: function (s: string) {
    if (s.length % 2 !== 0) {
      throw Error("hex string length must be a multiple of 2");
    }
    const arr = new Uint8ClampedArray(s.length * 4);

    for (let i = 0; i < s.length; i += 2) {
      const c = Number.parseInt(s.slice(i, i + 2), 16);

      if (Number.isNaN(c)) {
        throw Error("Invalid hex string");
      }

      arr[i * 4] = c & 0x01;
      arr[i * 4 + 1] = (c & 0x02) >> 1;
      arr[i * 4 + 2] = (c & 0x04) >> 2;
      arr[i * 4 + 3] = (c & 0x08) >> 3;
      arr[i * 4 + 4] = (c & 0x10) >> 4;
      arr[i * 4 + 5] = (c & 0x20) >> 5;
      arr[i * 4 + 6] = (c & 0x40) >> 6;
      arr[i * 4 + 7] = (c & 0x80) >> 7;
    }

    return arr;
  },

  median: function (values: Float64Array) {
    values.sort((a, b) => a - b);
    return values[Math.floor(values.length / 2)];
  },

  grayScaleConverter: function (imgData: ImageData) {
    const arr = new Uint8ClampedArray(imgData.length / 4);
    for (let i = 0; i < imgData.length; i += 4) {
      arr[i >> 2] = Math.round(
        (imgData[i] * 299) / 1000 +
          (imgData[i + 1] * 587) / 1000 +
          (imgData[i + 2] * 114) / 1000
      );
    }
    return arr;
  },

  dctTransform: function (matrix: Uint8ClampedArray) {
    const L = Math.round(Math.sqrt(matrix.length));

    const cos = this.precomputeCos(L);
    const dct = new Array(L * L);

    let _u, _v, sum;

    for (let u = 0; u < L; u++) {
      for (let v = 0; v < L; v++) {
        sum = 0;

        _u = u << 8;
        _v = v << 8;

        for (let x = 0; x < L; x++) {
          for (let y = 0; y < L; y++) {
            sum += matrix[x * L + y] * cos[_u + x] * cos[_v + y];
          }
        }

        dct[u * L + v] = sum;
      }
    }

    return dct;
  },

  precomputeCos: function (L: number) {
    if (L in cosCache) {
      return cosCache[L];
    }

    const piOver2L = Math.PI / (2 * L);

    const cos = {} as Record<string, any>;

    for (let u = 0; u < L; u++) {
      const uTimesPiOver2L = u * piOver2L;
      for (let x = 0; x < L; x++) {
        cos[(u << 8) + x] = Math.cos((2 * x + 1) * uTimesPiOver2L);
      }
    }

    cosCache[L] = cos;

    return cos;
  },
});