随着“Internet”的飞速发展，产生并累积了大量的图像数据，如果没有很好的方法处理这些海量数据，其中有用的信息就会被淹没。因此，如何有效地表示图像、高效的检索图像成为一个有意义的课题。本文围绕基于图理论的图像描述与检索展开讨论，在介绍基于内容的图像检索(Content-Based Image Retrieval，CBIR)的基础上，针对传统的使用图像颜色、纹理和形状等特征的CBIR对结构化信息描述不足的缺点，提出使用基于图描述的图像检索。并阐明本研究的立足点：使用基于图理论的图像描述与检索作为传统CBIR检索的补充，以提高检索效率。为了使用图理论来优化基于内容的图像检索，首先必须寻找有效的图像图描述方法。本文详细阐述了基于图像特征点的Delaunay图的描述方法，并通过图谱特征的图像分类实验来验证这种图像描述方法的有效性。对于内容较为简单的图像，提出了基于轮廓的加权图描述方法。该方法利用仿射傅立叶变换重构的离散轮廓点来构成加权图，使用这种图可以在较小的数据规模情况下较好的保持图像的形状结构。而骨架作为有效的描述图像形状的手段，在很多方面取得了成功的应用，结合骨架和图描述的优势，本文提出了基于骨架的图描述方法。该方法是建立在水平集理论和散度空间的骨架提取算法之上的。不论是基于轮廓的图描述方法还是基于骨架的图描述方法，都只能描述简单的单一轮廓图像，为了突破这一限制，本文提出基于了轮廓和骨架统一框架的分层图描述方法。该方法在不同层采用不同规模的图描述，使形状比较可以在不同层进行。虽然有了图像的图描述，但是如何衡量两图之间距离一直是一个困难的问题。本文引入了衡量图与图之间距离的一种思路：先把图序列化成串，利用串与串间的相似度量方法来比较图与图的距离。基于这种思路，提出了基于谱系数夹角的图的序列化方法和基于随机图理论的图的序列化方法。谱系数夹角作为图的谱特征用于图的序列化，利用图的特征向量获取序列化的起点，然后按照谱系数夹角的排序来完成序列化过程；基于随机图理论的图的序列化方法利用随机图中层次类覆盖捕获图理论，把序列化过程看成是个随机过程，根据其概率模型来完成序列化过程。对于序列化后的图，本文提出使用动态时间规整算法来刻画序列化图之间距离，并给出了动态时间规整描述图距离的概率模型及其算法框架。使用图描述图像的方法把图像库的检索转换成图库的检索，图库的特殊性使得图库的高维索引成为必须考虑的问题。本文详细阐述了基于混合模型和矢量量化的图库索引方法，提出了基于模型自动选择聚类的图库索引方法和基于t-混合模型的图库索引方法。基于模型自动选择聚类的图库索引方法利用改进的主分量优先的EM算法-CEM~2(Component-wise EM)来估计图库的分布模型。由于该方法可以在未知图库精确类别数的情况下进行索引，因而比起传统的基于高斯混合模型的索引方法更实用；考虑到实际图库可能比较复杂，而基于高斯混合模型的索引方法对于图库中类别分布极不均匀的场合的索引效率会显著下降。为此，本文提出基于t-混合模型和独立成分分析的索引方法。由于t-混合模型具有抗野值性能强的特性，使该索引方法具有较强的稳定性。传统的基于内容的图像检索方法，返回的结果集只考虑与查询图像在特征域的相似性，而不考虑结果集内部图像之间的关系。本文研究了在扩大的结果集上寻求既与查询图像相似，结果集本身分布又比较紧密的子集作为检索的结果。提出了基于关系图谱特征的图像检索方法，该方法在初始结果集上构造关系图，利用该关系图的图谱特征来寻找满足条件的顶点子集，其对应的结果作为检索的结果。实验证明该方法可以在不显著增加检索复杂度的前提下提高检索的精度。