6

我有下表存储有关图像的数据：

images
 - id (int)
 - sample_1_1 (int)
 - sample_1_2 (int)
 - sample_1_3 (int)
 - sample_2_1 (int)
 - sample_2_2 (int)
 - sample_2_3 (int)
 - ... # Up until sample_25_3

任务是计算收集到的数据之间的距离。目前，我正在使用一个 75 维（没错，3 * 25 = 75）欧几里德距离计算作为存储过程编程到数据库中：

CREATE DEFINER=`root`@`localhost`
FUNCTION `distanceBetween`(compareId INT, toId INT) RETURNS double
    READS SQL DATA
    DETERMINISTIC
BEGIN
 DECLARE distance DOUBLE;
SELECT euclidDistance(
 i1.sample_1_1, i1.sample_1_2, i1.sample_1_3,
 i2.sample_1_1, i2.sample_1_2, i2.sample_1_3,
 ...
 ) INTO distance
FROM images i1, (SELECT * FROM images WHERE id = toId) i2
WHERE i1.id = compareId;
RETURN distance;
END

用另一个子程序计算 2 75-dim 之间的实际距离。载体：

CREATE DEFINER=`root`@`localhost`
    FUNCTION `euclidDistance`(
 img1_sample1_1 INT, img1_sample1_2 INT, img1_sample1_3 INT,
 img2_sample1_1 INT, img2_sample1_2 INT, img2_sample1_3 INT,
 ...
 ) RETURNS double
RETURN SQRT(
   quadDiff(img1_sample1_1, img2_sample1_1)
 + quadDiff(img1_sample1_2, img2_sample1_2)
 + quadDiff(img1_sample1_3, img2_sample1_3)
 + ...
)

还有另一个子程序来计算两个值之间的平方差：

CREATE DEFINER=`root`@`localhost`
FUNCTION `quadDiff`(var1 INT, var2 INT) RETURNS int(11)
RETURN POW(var1 - var2, 2)

函数本身非常好，并返回在数学和逻辑上都正确的确定性结果。

当我想获得与给定图像“最接近”的图像时，问题就出现了——这意味着与任何给定图像距离最短的图像。为此，我使用另一个过程：

CREATE DEFINER=`root`@`localhost`
PROCEDURE `getSimilarImages`(imageId INT, `limit` INT)
BEGIN
    SELECT i2.id, i2.filename, distanceBetween(i1.id, i2.id) distance
    FROM images i1, (SELECT * FROM images WHERE id != imageId AND duplicateImageId IS NULL) i2
    WHERE i1.id = imageId
    ORDER BY distance
    LIMIT 10;
END

该数据库目前包含大约 30.000 张图像。这意味着 aCALL getSimilarImages(123, 10);大约需要12秒才能完成。这对于任何应用程序来说都太长了，无论是基于 Web 的还是基于应用程序的。

所以，我想加快速度。我有哪些选择？您是否看到任何优化图像比较或计算距离过程的潜力？

我考虑过缓存过程的结果，但我不知道该怎么做。我还可以在添加新图像后立即将每张图像与其他图像进行比较，但这会使添加图像的过程非常漫长，这也是不可接受的。

如果有帮助，我可以提供有关系统设置的更多信息，但我感谢您提供的任何指示。目前的情况并不好，我真的需要做点什么，因为图像数据库只会随着系统启动的每一个小时而增长。

4

3 回答 3

4

正如您所发现的，您的 ORDER BY distance(a,b) 操作正在计算全部 75 维距离，不出所料，这需要很长时间。它必须计算整个批次，以便执行 ORDER 操作。哎哟。

这是一个关于欧几里得距离的观察，可能会对您有所帮助：边界框是一个有用的近似值。当您使用 GetSimilarImages 时，您能否仅包含与您正在使用的 imageId 的特定阈值距离内的图像？

假设您只关心radimageId 距离内的图像。然后你可以像这样修改你的 GetSimilarImages 查询。

PROCEDURE `getSimilarImages`(imageId INT, `limit` INT, rad INT)
BEGIN
    SELECT i2.id, i2.filename, distanceBetween(i1.id, i2.id) distance
    FROM images i1, 
    (SELECT * FROM images WHERE id != imageId AND duplicateImageId IS NULL) i2
    WHERE i1.id = imageId
      AND i1.img_sample_1_1 BETWEEN i2.img_sample_1_1 - rad
                                AND i2.img_sample_1_1 + rad
      AND i1.img_sample_1_2 BETWEEN i2.img_sample_1_2 - rad
                                AND i2.img_sample_1_2 + rad
      AND i1.img_sample_1_3 BETWEEN i2.img_sample_1_3 - rad
                                AND i2.img_sample_1_3 + rad
    ORDER BY distance
    LIMIT 10;
END

在此示例代码中，我任意选择了 75 个维度中的前三个用于边界框包含代码（三个BETWEEN子句）。为了使这种优化起作用，您需要至少在一些用于边界框包含的维度上创建索引。

选择三个维度或选择任何特定维度并没有什么特别之处。如果您从数据中知道某些尺寸可以更好地区分图像，那么您可以选择这些尺寸。您可以根据需要选择尽可能多的尺寸。但是，当然有索引开销。

于 2012-08-03T11:16:11.920 回答
1

编写 UDF C 函数或调用调用 GPU 函数的本机 C 函数。

于 2012-08-03T12:52:02.053 回答
0

此案例的优化提示：

在列上添加索引id，duplicateImageId最好使用clustured index.

尽量避免在大表上进行多次选择images。

您可以通过在函数内部调用函数时减少函数调用的数量来略微提高性能。所有这些函数调用都需要在内存堆栈中维护，这会消耗硬件资源。

每次更改代码以进行优化后的性能基准。

CREATE PROCEDURE getSimilarImages(imageId INT unsigned, limit INT unsigned)
BEGIN
    SELECT i2.id, i2.filename, euclidDistance(
 i1.sample_1_1, i1.sample_1_2, i1.sample_1_3,
 i2.sample_1_1, i2.sample_1_2, i2.sample_1_3,
 ...
 ) AS distance
    FROM images i1, (SELECT id, filename 
                     FROM images 
                     WHERE id <> imageId AND 
                           duplicateImageId IS NULL
                    ) i2
    WHERE i1.id = imageId
    ORDER BY distance
    LIMIT 10;
END;

CREATE FUNCTION euclidDistance(
 img1_sample1_1 INT, img1_sample1_2 INT, img1_sample1_3 INT,
 img2_sample1_1 INT, img2_sample1_2 INT, img2_sample1_3 INT,
 ...
 ) RETURNS double
RETURN SQRT(
   POW(img1_sample1_1 - img2_sample1_1, 2)
 + POW(img1_sample1_2 - img2_sample1_2, 2)
 + POW(img1_sample1_3 - img2_sample1_3, 2)
 + ...
);

希望这可以帮助。

于 2012-08-03T09:56:35.563 回答