java - 大二进制图像数据集上的系数相关-性能低下

我正在尝试通过计算从图像中提取的字符与我预先存储在数据库中的每个字符之间的系数相关性来构建OCR。我的实现基于Java，并且在应用程序开始时将预存储的字符加载到ArrayList中，即

ArrayList<byte []> storedCharacters, extractedCharacters;
storedCharacters = load_all_characters_from_database();
extractedCharacters = extract_characters_from_image();

// Calculate the coefficent between every extracted character
// and every character in database.
double maxCorr = -1;
for(byte [] extractedCharacter : extractedCharacters)
  for(byte [] storedCharacter : storedCharactes)
  {
     corr = findCorrelation(extractedCharacter, storedCharacter)
     if (corr > maxCorr)
       maxCorr = corr;
  }
...
...
public double findCorrelation(byte [] extractedCharacter, byte [] storedCharacter)
{
  double mag1, mag2, corr = 0;
  for(int i=0; i < extractedCharacter.length; i++)
  {
     mag1 += extractedCharacter[i] * extractedCharacter[i];
     mag2 += storedCharacter[i] * storedCharacter[i];
     corr += extractedCharacter[i] * storedCharacter[i];
  } // for
  corr /= Math.sqrt(mag1*mag2);
  return corr;
}

每个图像的提取字符数约为100-150，但是数据库中存储了15600个二进制字符。使用Intel i5 CPU，检查每个提取的字符与每个存储的字符之间的系数相关性会对性能产生影响，因为完成每个图像大约需要15-20秒才能完成。
有没有一种方法可以提高该程序的速度，或者建议构建此程序的另一条途径带来相似的结果。（通过将每个字符与如此大的数据集进行比较所产生的结果是相当不错的）。

先感谢您

更新1

public static void run() {
    ArrayList<byte []> storedCharacters, extractedCharacters;
    storedCharacters = load_all_characters_from_database();
    extractedCharacters = extract_characters_from_image();

    // Calculate the coefficent between every extracted character
    // and every character in database.
    computeNorms(charComps, extractedCharacters);
    double maxCorr = -1;
    for(byte [] extractedCharacter : extractedCharacters)
      for(byte [] storedCharacter : storedCharactes)
      {
         corr = findCorrelation(extractedCharacter, storedCharacter)
         if (corr > maxCorr)
           maxCorr = corr;
      }
    }
}
private static double[] storedNorms;
private static double[] extractedNorms;

// Correlation  between to binary images
public static double findCorrelation(byte[] arr1, byte[] arr2, int strCharIndex, int extCharNo){
         final int dotProduct = dotProduct(arr1, arr2);
         final double corr = dotProduct * storedNorms[strCharIndex] * extractedNorms[extCharNo];
         return corr;
}

public static void computeNorms(ArrayList<byte[]> storedCharacters, ArrayList<byte[]> extractedCharacters) {
          storedNorms = computeInvNorms(storedCharacters);
          extractedNorms = computeInvNorms(extractedCharacters);
}

private static double[] computeInvNorms(List<byte []> a) {
         final double[] result = new double[a.size()];

         for (int i=0; i < result.length; ++i)
            result[i] = 1 / Math.sqrt(dotProduct(a.get(i), a.get(i)));
         return result;
}

private static int dotProduct(byte[] arr1, byte[] arr2) {
         int dotProduct = 0;
         for(int i = 0; i< arr1.length; i++)
            dotProduct += arr1[i] * arr2[i];

         return dotProduct;
}

最佳答案

如今，很难找到具有单核的CPU（即使在移动设备中也是如此）。由于任务已很好地分开，因此您仅需执行几行即可完成。所以我会去做，尽管收益有限。

如果您真的是说cross-correlation，那么像DFT或DCT这样的转换可能会有所帮助。他们肯定可以处理大图像，但是对于您的12x16，我不确定。

也许您是说dot product吗？也许您应该告诉我们？

请注意，您实际上并不需要计算相关性，大多数情况下，您只需要找出相关性是否大于阈值即可：

corr = findCorrelation(extractedCharacter, storedCharacter)
..... more code to check if this is the best match ......

这可能会导致是否进行某些优化，具体取决于图像的外观。

还请注意，如此question of mine所示，简单的低级优化可以为您提供近4的系数。也许您真的应该告诉我们您在做什么？

更新1

我猜是由于循环中三个乘积的计算，有足够的指令级并行性，因此不需要像my above question中那样手动展开循环。

但是，我看到这三个乘积的计算时间为100 * 15600，而其中只有一个依赖于extractedCharacter和storedCharacter。所以你可以计算

100 + 15600 + 100 * 15600

点产品代替

 3 * 100 * 15600

这样，您可能很容易获得三倍的系数。

或不。在此步骤之后，将在相关步骤中计算出一个总和，并且上面链接的问题适用。其解决方案（手动展开）也是如此。

系数5.2

虽然byte[]非常紧凑，但计算涉及将它们扩展为int，这会花费一些时间，如我的benchmark所示。在计算所有相关性之前将byte[]转换为int[]可以节省时间。更好的是利用可以预先进行storedCharacters转换的事实。

手动展开两次会有所帮助，但展开更多则没有帮助。

关于java - 大二进制图像数据集上的系数相关-性能低下，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/23647687/