工程学院电气学院工程和计算机科学SI 2120程序设计范式相似图像搜索综合任务
(24%)2024年冬季最多两名学生一组的项目
第1部分将于2月16日23:59之前到期
第2部分将于3月8日23:59之前到期
第3部分和第4部分将于4月22日23:59之前到期延迟分配政策：每延迟一天减10%。例如：一个项目周五晚上到期，但周一上午发放：-30%
问题描述
如今，图像以疯狂的速度被创造和积累。拥有强大的
能够分析这些图像并促进搜索、分类和发现的计算机工具感兴趣的图像。在这个项目中，你被要求编程一个简单的方法来搜索类似的图像。所谓相似的图像，我们指的是在内容方面彼此相似的图像以及它们的视觉外观、颜色和纹理（例如，显示日落的图像）。您的程序将处理彩色数字图像。然后我们来解释一下这些图像是如何构造的。A.数字图像被划分为矩形网格，其中每个元素都是一个像素（“图片元素”）。这网格包含一定数量的列和行，定义图像的分辨率（例如
手机可能会产生分辨率为4032x3024像素的图像）。像素包含颜色与图像中的对应位置相关联的信息。如果您的图像是灰度（a“黑白”图像），每个像素的值将在0到255之间（此8位表示为最常见的），0为黑色，255为白色，其他值表示不同的色调灰色。在彩色图像的情况下，每个像素包含三个值（三个通道），对应于三原色：红、绿、蓝（RGB）。这三个值分别表示红色、绿色和蓝色的量，和产生所需颜色所需的蓝色。例如，颜色255:红色、255:绿色、0:蓝色将生成浅黄色，而50:红色、0:绿色、0:蓝色将生成暗红色与像素相关联的通常由包含这三个值的向量[R，G，B]表示通道（例如，用于浅黄色的[255255，0]）。由于每种颜色可以取0到255之间的值三个通道的组合产生256 x 256 x 256种不同的颜色（即超过1600万种）。CSI 2120第2页
_________________________________________________________________________________________________我们正在寻找类似的图片。所以，让我们假设具有相似颜色的图像应该具有相似的颜色所容纳之物这是一个简单化的假设，并不总是正确的，但通常会产生可接受的结果，尽管不完美的结果。这是我们将在这个项目中验证的内容。因此，有必要计算图像的直方图并比较这些直方图。
直方图只是图像中包含的颜色的计数。它包括计算有多少像素具有颜色[0，0，0]，有多少像素具有颜色[0]，0，1]，依此类推。然而，这意味着对所有1600万种可能的颜色的像素进行计数，这是昂贵的并且不是很精确。它是因此建议减少色彩空间。这可以通过简单地减少
可能的值，例如，通过每个通道从8位值到3位值，产生一种颜色只有8 x 8 x 8的空间=512种可能的颜色。在这种情况下，简单的位右移8–3=5个位置减少了空间。直方图将只有512个条目，每个可能的颜色都有一个bin。到比较具有不同分辨率（不同像素数）的图像，有必要对
直方图，即，将每个条目除以像素总数（从而通过将
直方图，我们将获得1.0）。
直方图比较
如前所述，将通过比较图像的直方图来对图像进行比较。这可以使用对于直方图H1和H2，可以如下计算直方图交集：
如果两个直方图相同，则该总和将给出等于1.0的值。相反，如果两个图像没有共同的颜色，则它们的直方图交集将等于0.0。因此相似的是两幅图像，它们的直方图交集越接近1.0。
搜索相似图像
您将被要求使用颜色直方图交集来查找与查询图像相似的图像。一将提供图像数据集用于搜索。搜索K个最相似图像的算法使用减少到D比特的颜色空间的查询图像I如下：
1.计算I的缩减颜色直方图
a.通过对每个通道R、G、B应用（8-D）右位移位来减少像素值。i.R'=R>>（8-D）
ii。G'=G>>（8-D）
iii.B'=B>>（8-D）
b.直方图H中的仓数为N=2D*3
c.计算每种颜色的多少像素包含在I中，以获得直方图H直方图H是N个元素的阵列。
CSI 2120第3页
_________________________________________________________________________________________________i.可以计算与颜色[R'，G'，B']相对应的直方图仓的索引如（R'<<（2*D））+（G'<<D）+B）
d.归一化H，使其所有bin的值总和为1.0
2.将H与图像集中所有预先计算的直方图进行比较。
a.此比较是使用直方图交集进行的
b.返回距离最接近1.0的K个图像
编程
你必须在不同的范式下编写程序来解决这个问题的不同版本。你将收到每种语言的具体说明。
每个程序将标记如下：
程序产生正确的结果【3分】
遵守编程模式【2分】
编程质量（结构、组织等）[1分]
您的所有文件都必须包含一个标题，显示学生ID和小组成员的姓名。所有文件都必须以zip文件的形式提交。
CSI 2120第4页
_________________________________________________________________________________________________数据集
您可以访问图像数据集。图像以jpg格式提供。的直方图该数据集中的每个图像都已被计算（每个通道3位）并保存在文本文件中。我们还为您提供了16个查询图像。您必须找到与每个查询最相似的5个图像图像。查询图像以jpg和ppm格式提供，您可以使用其中一种。CSI 2120第5页
_________________________________________________________________________________________________1.面向对象部分（Java）[6%的期末成绩]
由于此解决方案必须遵循面向对象的范例，因此您的程序必须由一组类。具体而言，它必须包括以下列出的类别。
除了解决方案的源代码之外，您还必须提交一个包含UML的文档所有类的图表（显示属性、关联和方法）。不要使用静态方法，除了主要功能之外。本文档还必须引用用于构建解决方案的所有参考资料。相似性搜索类
o包含主要方法
必须指定图像文件名，即图像数据集目录
java相似性搜索q01.jpg imageDatasets2_15_20 您可以假设图像数据集的直方图是预先计算好的
但是，必须计算查询图像的直方图
你可以假设搜索是在3位减色图像上完成的，但
你的程序尽可能通用（没有深度值的硬编码，除非在
主要方法）。
程序必须打印与查询图像最相似的5个图像的名称
ColorImage类，包括
o从文件创建图像的构造函数
public ColorImage（字符串文件名） 您可以从jpg或ppm格式读取图像（只需选择一种格式）您可以使用JMF Java API读取jpg图像ppm格式只是一个列出RGB值的文本文件
图像的像素值存储在您选择的阵列表示中
（在提交的文件中说明）
o以下图像属性（以及相应的getter方法）
int宽度
int高度
int depth（每个像素的位数）
o一个getPixel方法，返回中第i列第j行像素的3通道值三元阵列的形式
public int[3]getPixel（int i，int j）o一种reduceColor方法，将颜色空间缩减为d位表示 public void reduceColor（int d）CSI 2120第6页
_________________________________________________________________________________________________ColorHistogram类，包括
o为d位图像构建ColorHistogram实例的构造函数 公共颜色直方图（int d）
o从文本文件构造ColorHistogram的构造函数 公共颜色直方图（字符串文件名）
o将图像与直方图实例关联的setImage方法
public void setImage（ColorImage图像）o返回图像归一化直方图的getHistogram方法 公共双[]getHistogram（）
o一种比较方法，返回两个直方图之间的交集
公共双比较（颜色直方图历史记录）
o将直方图保存到文本文件中的保存
public void ColorHistogram（字符串文件名）o加上您认为必要
2.功能编程部分（方案）【您最终成绩的6%】
对于综合任务的这一部分，我们要求您执行图像相似性搜索算法遵循函数范式。请参阅一般问题描述部分以了解
算法步骤。
这些要求与面向对象零件的要求相同，只是这次您不必
生成查询图像的直方图。您可以使用已生成的直方图文件使用Java程序。
您必须创建以下函数才能启动程序：
（类似搜索查询历史记录文件名imageDatasetDirectory）此函数应将5个最相似图像的名称返回到查询图像。你显然会必须创建其他功能。请记住，在功能范式下，创建
几个短函数比几个长函数好。
在包含scheme函数文件和列出函数的文档的zip文件中提交您的项目以及为每个查询图像获得的输出。本文件还必须引用所有您可能已用于构建解决方案的引用。
您的所有Scheme函数都必须有一个描述函数功能的头，输入参数以及输出。
不允许使用终止于的函数！（例如set！函数），并且您不能使用迭代循环，请使用递归。
CSI 2120第8页
_________________________________________________________________________________________________3.并行编程部分（Go）【期末成绩的6%】
对于综合课业的并发部分，我们要求您对图像相似性进行编程使用多线程的搜索算法。为了使其计算成本更高，您的程序将每次执行查询时都必须计算所有直方图（来自查询和数据库图像）。您的go程序使用以下参数执行：
>go运行similaritySearch queryImageFilename imageDatasetDirectory注：哦。Args提供对命令行参数的访问。
读取jpeg图像
幸运的是，如果您查看有关映像包的Go文档，https://pkg.go.dev/image你将找到一个示例来显示如何计算图像的直方图。这并不完全是你想要的必须这样做，但这是一个很好的起点。提供了该示例的略微修改的版本；它有直方图Go函数的签名。
类型Histo结构{
名称字符串
H[]int
}
func computeHistogram（imagePath字符串，depth int）（Histo，error）此函数计算指定jpeg图像的直方图，并将其减少为位数由深度参数给出。起始代码相对容易理解，需要注意的一点是Go中图像的像素值存储在uint32中，您必须将每个通道的位右移8位置以获得正确的范围（0到255）。检查提供的代码，它只显示RGB值图像的。
您还需要一个函数来计算图像文件名切片的直方图。
func computeHistograms（imagePath[]字符串，depth int\hChan-chan<-Histo）
当计算直方图时，它被发送到给定的通道。
CSI 2120第9页
_________________________________________________________________________________________________主要功能
您的主要功能必须执行以下操作：
1.创建直方图通道；
2.获取数据集目录中所有图像文件名的列表；
3.将该列表拆分为K个切片，并将每个切片发送到go函数computeHistograms；4.在一个单独的线程中，打开查询图像并计算其直方图5.读取直方图的通道
a.当收到直方图时，将其与查询直方图进行比较
b.根据相似性结果，维护5张最相似图像的列表
6.处理完所有图像后，打印5个最相似图像的列表。
7.关闭所有通道，并确保在程序终止之前停止所有线程。实验
为了确定并发算法的最佳配置，我们要求您执行
以下实验，并报告每个案例的执行时间：
K=1
K=2
K=4
K=16
K=64
K=256
K=1048
创建一个显示运行时间与线程数量的关系图（使用所有线程的平均运行时间查询）。在估计运行时间时，不要忘记不要将文本打印到控制台，这会大大降低了程序的速度。还要指定您的操作系统和规格
处理器（包括核的数量）。你也可以将自己的经历添加到其他配置。请记住，您的程序必须计算所有直方图（来自查询和数据集图像），不使用预先计算的直方图文本文件。
除了源代码外，您还必须提交一份显示实验结果的文档。CSI 2120第10页
_________________________________________________________________________________________________4.逻辑编程部分（Prolog）【期末成绩的6%】对于综合任务的最后一部分，您必须执行图像相似性搜索遵循逻辑编程范式的算法。请参阅一般问题描述部分
用于算法步骤。
这些要求与其他部分的要求相同，只是这次不必生成
图像的直方图。您可以将直方图文本文件用于查询图像和数据集图像所提供的。
您必须创建以下谓词来解决此问题，如下所示：
- similarity_search（'q00.jpg.txt'，S）。S=[（'2144.jpg.txt'，0.8799533333334），（'1998.jpg.txt'，0.86362），（'3538.jpg.txt'，0.79226），（'33920.jpg.txt'，0.77334），（'4923.jpg.txt'，0.76828）]。（请注意，显示的解决方案不正确，仅用于演示解决方案的格式）。我们为您提供了一个入门项目，其中包括所需的大多数谓词。尤其是读直方图文件并返回列表将非常有用。
- read_hist_file（'q00.jpg.txt'，H）。H=[2715,22,0,0,0,0,0,10,2,2|…]。生成目录中文本文件列表的方法也很有用。
- 数据集（D），目录文本文件（D，L）。
D='C:\\Users\\Documents\\imageDataset2_15_20\\'，L=“1000.jpg.txt”，“1001.jpg.txt”、“1003.jpg.txt”和“1004.jpg.txt”，“1005.jpg.txt'，”1006.jpg.txt'“，”1007.jpg.txt''“，”1008.jpg.txt''，'1009.jpg.txt'|…]。
请注意数据集目录路径是如何通过谓词dataset/1提供的。CSI 2120第11页
_________________________________________________________________________________________________最后，我们还为您提供了执行高级算法的谓词。
similarity_search（QueryFile，DatasetDirectory，DatasetFiles，最佳）：-read_hist_file（QueryFile、QueryHisto），1.
compare_histograms（QueryHisto、DatasetDirectory、，数据集文件，分数），%2。
排序（2，@>，分数，排序），%3。
take（排序，5，最佳）。%4.
如您所见，此谓词首先读取查询图像的直方图文件（read_hist_file/2）。那就好了将此直方图与直方图文件列表（compare_histograms/4）中的所有直方图进行比较生成（HistogramFilename，Score）对的列表。下一步对获得的列表进行排序（排序/4）其中前5对被提取（take/3）。
仔细阅读这个Prolog文件并实现缺失的谓词。
在包含评论良好的Prolog谓词的zip文件中提交您的项目；所有的Prolog谓词必须有一个简短的头，描述谓词的作用及其参数。还包括示出针对每个查询图像获得的输出的文档。
CSI 2120第12页
_________________________________________________________________________________________________规则
你可以两人一组完成这项任务，学习团队合作
对这个问题进行思考和头脑风暴，并与你的伴侣一起编程。任何相似之处在你的程序之间到其他组被认为是剽窃。是的，如果你不喜欢团队合作，你可以单独完成。不要使用任何来自互联网的代码或程序，因为这也被认为是剽窃。请参阅以下链接中的大学剽窃政策。
https://www2.uottawa.ca/about-us/provost重要提示：如果您的TA发现您的代码来自
chatGPT，您将立即收到此项目所有部分的0。
我们为检测剽窃而采取的措施
已指示助教向教授报告任何抄袭嫌疑
他们在标记课业时会发现。
如果在任何部分或整个课业中发现抄袭，教授将采取
适当的措施。回想一下，复制一个解决方案并让其他人使用同样糟糕复制您的解决方案。