Vol.21 No.4 吴斌等：图像数据库的智能检索 ·397 取和按准则的特征提取（如熵方法、K-L变换、 特征向量是它的下层子节点所组成类别的族 最佳鉴别变换等)” 心， 在研究中，我们利用“积分投影”方法提取 按照定义2，可以确定聚类树上所有非叶子 人脸图像的特征点侧.但因各特征点是彼此弧立 节点的类特征向量，从而保证树上每一个节点 的，不能形象、直观地表征人脸，所以采用点间 都有一个特征向量或类特征向量，这样聚类树 的某种组合构成人脸的特征向量.共选择15个 就成为一棵便于检索的检索树了. 点间的距离或夹角作为人脸特征向量的各个分 在我们的实验中，检索树是用Lisp语言编 量.这些点的选择原则是：分量数目尽可能少： 写的，可按如下2种定义来表示检索树， 各分量间的相关性小：各分量的方差Y大，而对 定义3检索树上每个节点对应着Lisp语 应的噪声方差σ2小，使品质因素6=(2-σ)1σ高. 言中的一个原子，每个原子的性质表中增加3 项性质：①性质Vector项，其值为用表表示的对 3建立检索树 应节点的特征向量或类特征向量：②性质Suc- 图像库中的每幅图像都有其相应的特征向 cessor项，其值为该节点的子节点对应的原子组 成的表.若此项性质为空L,则表明此节点为 量，对它们应用聚类分析的方法进行聚类分析， 将图像库按树形结构重新组织，以建立起适合 叶子节点（对应着图像）：③性质Precedence项， 其值为父辈节点对应的原子，当该项值为NL 于智能检索的检索树. 时，说明此原子对应的节点为根节点. 聚类算法选用具有一定启发性的最大最小 (MAXMIN)距离算法例.MAXMIN算法是以欧氏 定义4检索树用一张嵌套表来表示，其定 义如下：①若检索树为空，则用空表NL表示； 距离为基础的一个启发式聚类算法，它实质上 分为两大步骤：寻找聚类中心和将模式样本按 ②若检索树只有一个节点L,则用表(L)表示：③ 对检索树上任意一个节点N,其子节点设为S, 最近距离分到最近的聚类中心 S,S,则可表示为： 设共有n个图像特征向量S,S,…,S,经过 (N.(S)S)S)) 一次聚类分析后，得到m,个子类，其中第i个聚 其中N,或为根节点，或为另一棵更大检索树上 类类别中含N,个特征向量，三N=m:再应用聚 的子类节点，S,S,S,是同一父辈节点的兄弟节 类方法对这个m,个子类进行聚类分析，得到m: 点，它们可能是叶子节点，也可能是另外子树的 个子类(>m>m),其中第j个类别中含有Ng个 父辈节点，其表示如①，②，③所定义的形式. 子类，三N=m.如此聚类下去，直到只得到一 这2种方式各有优缺点.前者结构简单，操 个子类，即产生根节点R,形成一棵如图1所示 作方便，但当检索树非常庞大时，占有较多存贮 的聚类树为止.该树上的叶子节点为S2(p=1,2, 空间：而后者的结构紧凑，节省存储空间，但在 …,),是各图像的特征向量，对应着图像库中的 检索树较大时，由于嵌套层次较多，给操作带来 各图像. 麻烦，运算时间长.我们选用后一种方式，即用 定义1聚类树上各非叶子节点，称为子类 嵌套表表示检索树， 节点，它们的特征向量称为类特征向量 定义2聚类树第k层上的某子类节点的类 R 图1聚类树一 一 吴斌 等 图像数 据 库 的智 能检 索 一 取 和 按准 则 的特 征提 取 如嫡 方 法 、 一 变换 、 最 佳 鉴别 变换等 「一 〕 在研 究 中 ， 我们 利用 “ 积 分 投 影 ” 方 法 提取 人脸 图像的特征 点‘ 但 因各特征 点是 彼 此 弧立 的 ， 不 能形 象 、 直 观 地表 征 人 脸 ， 所 以采 用 点 间 的某种组 合 构成 人脸 的特 征 向量 共选择 巧 个 点 间的距 离或夹 角作 为人脸特征 向量 的各个分 量 这 些 点 的选择 原 则 是 分 量 数 目尽 可 能少 各分 量 间 的相 关 性小 各分 量 的方 差尹大 ， 而 对 应 的噪声方差了 小 ， 使品质 因素 占 尹一 护 扩 高 建立检索树 图像库中的每幅 图像都有 其相应 的特 征 向 量 ， 对它们 应用聚类分析的方法进行聚类分析 ， 将 图像库按 树形 结构重 新组 织 ， 以建立起 适合 于 智 能检索的检索树 聚类算法选用具有一 定启发性 的最大最 小 呵 距离算法 叭 算法是 以欧 氏 距 离为基础 的一个启发式聚 类算法 ， 它 实质上 分 为 两 大步骤 寻 找聚类 中心和 将模式样 本 按 最 近距离分到最近 的聚 类 中心 设共有 个 图像特征 向量 ， 凡 ， … ， 凡 ， 经 过 一 次聚类分析后 ， 得 到 ，个子 类 ， 其 中第 个 聚 类类 别 中含 凡 ‘个特 征 向量 ， 蓦凡产 ” 再 应用聚 类方法对 这个 ， 个子类进行 聚类分析 ， 得 到 狡 个子类 ， 其 中第 个类别 中含 有 个 子类 ， 全 一 如 此聚 类 下 去 ， 直 到 只 得 到一 个子类 ， 即产生根节 点 ， 形 成 一 棵如 图 所 示 的聚 类树为止 该树上 的叶子 节 点为 凡勿 ，， … ， ， 是各 图像的特征 向量 ， 对应着 图像库 中的 各 图像 定 义 聚类树上 各 非叶子 节 点 ， 称 为 子 类 节 点 ， 它们 的特征 向量称为类特 征 向量 定义 聚类树第 层 上 的某子 类节 点 的类 特 征 向量 是 它 的 下 层 子 节 点 所 组 成 类 别 的族 心 按照 定义 ， 可 以确 定聚类树上 所有 非 叶子 节 点的类特 征 向量 ， 从而 保证树上 每一 个 节 点 都 有 一 个 特 征 向量或 类特征 向量 ， 这 样聚 类树 就 成为一 棵便于 检索 的检索树 了 在 我 们 的实验 中 ， 检索树是 用 语 言编 写 的 ， 可 按 如 下 种 定 义 来表 示检 索树 定义 检索树上 每个节 点对应 着 语 言 中的一 个 原子 ， 每个 原子 的性质表 中增 加 项 性 质 ①性 质 项 ， 其值 为用 表表 示 的对 应 节 点 的特 征 向量 或 类特 征 向量 ②性质 项 ， 其值 为该 节 点 的子 节 点对 应 的原子 组 成 的表 若 此项性质 为 空 ， 则表 明此 节 点为 叶 子节 点 对 应着 图像 ③性质 项 ， 其值 为父 辈节 点对 应 的原 子 当该项值 为 时 ， 说 明此 原子 对 应 的节 点为根 节 点 定义 检 索树用 一 张 嵌套表来表 示 ， 其 定 义 如下 ①若检索树为 空 ， 则用 空表 表示 ②若检索树 只 有一 个 节 点 ， 则 用表 表 示 ③ 对 检索树上 任意一 个节 点凡 ，， 其子节 点设为 ，， 又 ， 凡 ， 则可 表示 为 凡 ， 凡 其 中凡 ，或 为根节 点 ， 或为另一 棵更 大检索树上 的子 类节 点 ， ， 及 ， 凡 是 同一 父 辈节 点 的兄 弟节 点 ， 它们 可 能是 叶子 节 点 ， 也 可 能是另外 子 树 的 父 辈节 点 ， 其表示 如① ， ② ， ③所 定义 的形 式 这 种方式各 有优缺点 前 者 结构 简单 ， 操 作方便 ， 但 当检索树非常庞 大时 ， 占有 较 多存贮 空 间 而 后 者 的结构紧凑 ， 节 省存储 空 间 ， 但 在 检索树较 大 时 ， 由于 嵌套层 次较 多 ， 给 操 作带 来 麻烦 ， 运算 时 间长 我们 选 用 后 一 种方 式 ， 即用 嵌套表 表 示检 索树 从 ， 川 一 凡 。 又 ， 凡 凡 凡 凡 图 聚类树