指紋排序

對(duì)活體指紋 提取多枚或十枚進(jìn)行采集、分析和預(yù)存，利用了組合數(shù)學(xué)的排列組合方式，通過“先后、位置、數(shù)量”組合為所需的項(xiàng)目識(shí)別數(shù)據(jù)，比對(duì)使用時(shí)輸入的項(xiàng)目識(shí)別數(shù)據(jù)準(zhǔn)確地鑒別出個(gè)人身份、賬戶。

指紋在我國銀行業(yè)務(wù)中的應(yīng)用 不用帶錢包、不刷銀行卡、不用手機(jī)掃碼，只要手指在終端上按幾下，就可以實(shí)現(xiàn)金融功能，運(yùn)用指紋排序的新型指紋銀行，比較以前的指紋銀行 安全度增加了3個(gè)數(shù)量級(jí)。同時(shí)，可以用于指紋防盜門、ATM存取款、手機(jī)支付、銀行柜面使用、指紋認(rèn)證各類應(yīng)用等。其本身即帶有100億種排列組合，識(shí)別基數(shù)大，理論接近于識(shí)別無限個(gè)人身份，安全性極高。即使被惡意盜取全部指紋，但由于輸入項(xiàng)目識(shí)別數(shù)據(jù)不對(duì)，依舊無法盜取存款、無法欺騙防盜門等。

所謂指紋排序，就是指依靠組合數(shù)學(xué)中的排列組合概念，從多枚至十枚手指指紋中取出隨機(jī)幾枚指紋進(jìn)行排列組合的一種排序方式。

每個(gè)人的指紋排序理論上自帶100億種密碼，幾乎無法破解。且組合的項(xiàng)目識(shí)別數(shù)據(jù)，可以輕松識(shí)別上百億人的不同特征，輕松滿足對(duì)于識(shí)別基數(shù)大的需求。對(duì)比人臉識(shí)別數(shù)據(jù)分析 ，掃臉識(shí)別 是1個(gè)識(shí)別數(shù)據(jù)，指紋排序是10個(gè)識(shí)別數(shù)據(jù)的排列組合。指紋識(shí)別 的主要難點(diǎn)在于，識(shí)別精度的設(shè)置。精度設(shè)置高，指紋識(shí)別要求高，不易于識(shí)別。精度設(shè)置低，對(duì)于識(shí)別基數(shù)大，相似識(shí)別數(shù)據(jù)太多，很難精準(zhǔn)識(shí)別。

二叉排序樹(Binary Sort Tree：BST)

1、二叉排序樹的定義

二叉排序樹(Binary Sort Tree)又稱二叉查找(搜索)樹(Binary Search Tree)。其定義為：二叉排序樹或者是空樹，或者是滿足如下性質(zhì)的二叉樹：

①若它的左子樹非空，則左子樹上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值；

②若它的右子樹非空，則右子樹上所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值；

③左、右子樹本身又各是一棵二叉排序樹。

上述性質(zhì)簡(jiǎn)稱二叉排序樹性質(zhì)(BST性質(zhì))，故二叉排序樹實(shí)際上是滿足BST性質(zhì)的二叉樹。

2、二叉排序樹的特點(diǎn)

由BST性質(zhì)可得：

（1） 二叉排序樹中任一結(jié)點(diǎn)x，其左(右)子樹中任一結(jié)點(diǎn)y(若存在)的關(guān)鍵字必小(大)于x的關(guān)鍵字。

（2） 二叉排序樹中，各結(jié)點(diǎn)關(guān)鍵字是惟一的。

注意：

實(shí)際應(yīng)用中，不能保證被查找的數(shù)據(jù)集中各元素的關(guān)鍵字互不相同，所以可將二叉排序樹定義中BST性質(zhì)(1)里的"小于"改為"小于等于"，或?qū)ST性質(zhì)(2)里的"大于"改為"大于等于"，甚至可同時(shí)修改這兩個(gè)性質(zhì)。

（3） 按中序遍歷該樹所得到的中序序列是一個(gè)遞增有序序列。

【例】下圖所示的兩棵樹均是二叉排序樹，它們的中序序列均為有序序列：2，3，4，5，7，8。

3、二叉排序樹的存儲(chǔ)結(jié)構(gòu)

typedef int KeyType； //假定關(guān)鍵字類型為整數(shù)

typedef struct node { //結(jié)點(diǎn)類型

KeyType key； //關(guān)鍵字項(xiàng)

InfoType otherinfo； //其它數(shù)據(jù)域，InfoType視應(yīng)用情況而定，下面不處理它

struct node *lchild，*rchild，*parent； //左右孩子指針

} BSTNode；

typedef BSTNode *BSTree； //BSTree是二叉排序樹的類型

二叉排序樹的基本操作（pascal）：

1.中序遍歷所有元素

procedure tree_walk(x:longint);

begin

if x<>0 then

begin

tree_walk(left[x]);

write(key[x]);

tree_walk(right[x]);

end;

2.查找給定的元素

function tree_search(x,k:longint):longint;

begin

if (x=0) or (k=key[x]) then exit(x);

if k

end;

非遞歸版本

function tree_search(x,k:longint):longint;

begin

while (x<>0) and (k<>key[x]) do

begin

if k

end;

exit(x);

end;

3.查找最小元素

function tree_minimum(x:longint):longint;

begin

while left[x]<>0 do

x:=left[x]；

exit(x);

end;

查找最大元素

function tree_maximum(x:longint):longint;

begin

while right[x]<>0 do

x:=right[x];

exit(x);

end;

4. 求后繼

function tree_successor(x:longint):longint;

var

y:longint;

begin

if right[x]<>0 then exit(tree_minimum(right[x]));//若右子樹不空，則返回右子樹中的最小值

y:=p[x];//若右子樹為空，則后繼y為x的最低祖先節(jié)點(diǎn)，且y的左兒子也是x的祖先

while (y<>0) and (x=right[y]) do

begin

x:=y;

y:=p[y];

end;

exit(y);//注意，若y為0，則x無后繼

end;

//注意，函數(shù)返回值為節(jié)點(diǎn)編號(hào)，并不是節(jié)點(diǎn)本身的值

5.插入

procedure tree_insert(z:longint);//注意z為節(jié)點(diǎn)編號(hào)，并非樹中的值

var

x,y:longint;

begin

y:=0;

x:=root;

while x<>0 do//查找z的父節(jié)點(diǎn)，y記錄

begin

y:=x;

if key[z]

end;

p[x]:=y;

if y=0 then root:=z//若z為根節(jié)點(diǎn)

else begin

if key[z]

end;

end;

6.刪除

刪除操作是最麻煩的，分3種情況：

（1）若z無子樹，則就刪除z節(jié)點(diǎn)，更新p[z]的值為空

（2）若z有一個(gè)子樹，刪除z節(jié)點(diǎn)，更新p[z]的值為z的兒子節(jié)點(diǎn)，更新left[p[z]] 或 right[p[z]]

（3）若z有兩棵子樹，先找到z的后繼y（后繼節(jié)點(diǎn)無左子樹，可證），刪除y節(jié)點(diǎn)，更新p[y]與left[p[y]] 或 right[p[y]],最后用節(jié)點(diǎn)y的數(shù)據(jù)覆蓋z節(jié)點(diǎn)

procedure tree_delete(z:longint);

var

x,y:longint;

begin

if (left[z]=0) or (right[z]=0) then y:=z

else y:=tree_successor(z);

if left[y]<>0 then x:=left[y]

else x:=right[y];

if x<>0 then p[x]:=p[y];

if p[y]=0 then root:=x

else begin

if y=left[p[y]] then left[p[y]]:=x

else right[p[y]]:=x;

end;

if z<>y then key[z]:=key[y];

end;

7.查找數(shù)中第k大元素

需要對(duì)每個(gè)節(jié)點(diǎn)新開一個(gè)域v[x]，記錄該節(jié)點(diǎn)的有多少子節(jié)點(diǎn)，

查找時(shí)分三種情況：

（1）k=v[left[x]] 1 則當(dāng)前x節(jié)點(diǎn)為所求

（2）k<=v[left[x]] 則在左子樹中繼續(xù)查找

（3）k>v[left[x]] 1 則在右子樹中繼續(xù)查找,k更新為k-left[x]-1;

function find(x,k:longint):longint;

begin

if v[left[x]] 1=k then exit(key[k])

else if v[left[x]]>=k then exit(find(left[x],k))

else exit(find(right[x],k-v[left[x]]-1));

end;

指紋識(shí)別指紋模式

指紋是人類手指末端由凹凸的皮膚所形成的紋路，在人類出生之前指紋就已經(jīng)形成并且隨著個(gè)體的成長(zhǎng)指紋的形狀不會(huì)發(fā)生改變，只是明顯程度的變化，而且每個(gè)人的指紋都是不同的，在眾多細(xì)節(jié)描述 中能進(jìn)行良好的區(qū)分，指紋紋路有三種基本的形狀：斗型（whorl）、 弓型（arch）和箕型（loop）。在指紋中有許多特征點(diǎn)，特征點(diǎn)提供了指紋唯一性的確認(rèn)信息，這是進(jìn)行指紋識(shí)別的基礎(chǔ)，分為總體特征和局部特征，總體特征又包括了核心點(diǎn)（位于指紋紋路的漸進(jìn)中心）、 三角點(diǎn)（位于從核心點(diǎn)開始的第一個(gè)分叉點(diǎn)或者斷點(diǎn)，或者兩條紋路會(huì)聚處、孤立點(diǎn)、折轉(zhuǎn)處，或者指向這些奇異點(diǎn)）、紋數(shù)（指紋紋路的數(shù)量）；局部特征是指紋的細(xì)節(jié)特征，在特征點(diǎn)處的方向、曲率、 節(jié)點(diǎn)的位置，這都是區(qū)分不同指紋的重要指標(biāo)。

指紋識(shí)別指紋特征

特征點(diǎn)

指紋，英文名稱為fingerprint，兩枚指紋經(jīng)常會(huì)具有相同的總體特征，但它們的細(xì)節(jié)特征，卻不可能完全相同。指紋紋路并不是連續(xù)的、平滑筆直的，而是經(jīng)常出現(xiàn)中斷、分叉或轉(zhuǎn)折。這些斷點(diǎn)、分叉點(diǎn)和轉(zhuǎn)折點(diǎn)就稱為"特征點(diǎn)"。

特征點(diǎn)提供了指紋唯一性的確認(rèn)信息，其中最典型的是終結(jié)點(diǎn)和分叉點(diǎn)，其他還包括分歧點(diǎn)、孤立點(diǎn)、環(huán)點(diǎn)、短紋等。特征點(diǎn)的參數(shù)包括方向（節(jié)點(diǎn)可以朝著一定的方向）、曲率（描述紋路方向改變的速度）、位置（節(jié)點(diǎn)的位置通過x/y坐標(biāo)來描述，可以是絕對(duì)的，也可以是相對(duì)于三角點(diǎn)或特征點(diǎn)的）。

總體特征

總體特征是指那些用人眼直接就可以觀察到的特征。包括紋形、模式區(qū)、核心點(diǎn)、三角點(diǎn)和紋數(shù)等。

紋形，指紋專家在長(zhǎng)期實(shí)踐的基礎(chǔ)上，根據(jù)脊線的走向與分布情況一般將指紋分為三大類——環(huán)型（loop，又稱斗形）、弓形（arch）、螺旋形（whorl）。

模式區(qū)即指紋上包括了總體特征的區(qū)域，從此區(qū)域就能夠分辨出指紋是屬于哪一種類型的。有的指紋識(shí)別算法只使用模式區(qū)的數(shù)據(jù)，有的則使用所取得的完整指紋。

核心點(diǎn)位于指紋紋路的漸進(jìn)中心，它在讀取指紋和比對(duì)指紋時(shí)作為參考點(diǎn)。許多算法是基于核心點(diǎn)的，即只能處理和識(shí)別具有核心點(diǎn)的指紋。

三角點(diǎn)位于從核心點(diǎn)開始的第一個(gè)分叉點(diǎn)或者斷點(diǎn)，或者兩條紋路會(huì)聚處、孤立點(diǎn)、折轉(zhuǎn)處，或者指向這些奇異點(diǎn)。三角點(diǎn)提供了指紋紋路的計(jì)數(shù)跟蹤的開始之處。

紋數(shù)，即模式區(qū)內(nèi)指紋紋路的數(shù)量。在計(jì)算指紋的紋路時(shí)，一般先連接核心點(diǎn)和三角點(diǎn)，這條連線與指紋紋路相交的數(shù)量即可認(rèn)為是指紋的紋數(shù)。

局部特征

局部特征指紋節(jié)點(diǎn)的特征。指紋的紋路并不是連續(xù)、平滑筆直的，經(jīng)常會(huì)出現(xiàn)分叉、折

轉(zhuǎn)或中斷。這些交叉點(diǎn)、折轉(zhuǎn)點(diǎn)或斷點(diǎn)稱為"特征點(diǎn)"，它們提供了指紋唯一性的確認(rèn)信

息。特征點(diǎn)的主要參數(shù)包括：

方向：相對(duì)于核心點(diǎn)，特征點(diǎn)所處的方向。

曲率：紋路方向改變的速度。

位置：節(jié)點(diǎn)的位置坐標(biāo)，通過x/y坐標(biāo)來描述。它可以是絕對(duì)坐標(biāo)，也可以是與三角點(diǎn)（或特征點(diǎn)）的相對(duì)坐標(biāo)。

（1）使用Gantt圖進(jìn)行生產(chǎn)作業(yè)排序，Gantt圖是作業(yè)排序中最常用的一種工具，最早由Henry L.Gantt于1917年提

出。這種方法是基于作業(yè)排序的目的，將活動(dòng)與時(shí)間聯(lián)系起來，它有兩種基本形式：作業(yè)進(jìn)度圖和機(jī)器圖。作業(yè)進(jìn)度圖表示一項(xiàng)工作的計(jì)劃開始日期、計(jì)劃完成日期以及現(xiàn)在的進(jìn)度。

（2）一臺(tái)設(shè)備加工多個(gè)加工對(duì)象時(shí)，為使任務(wù)總流程時(shí)間最短，即總等待時(shí)間最短，保證盡可能多的對(duì)象早日加工出來，加速資金周轉(zhuǎn)，應(yīng)該根據(jù)最短加工時(shí)間規(guī)則對(duì)加工對(duì)象排序。

（3）兩臺(tái)設(shè)備加工多個(gè)加工對(duì)象時(shí)，加工順序不同，總加工周期和等待時(shí)間都有很大差別。根據(jù)最優(yōu)化原理，加工對(duì)象在兩臺(tái)設(shè)備上加工的順序不同時(shí)的排序不是最優(yōu)方案。換句話說，最優(yōu)排序方案只能在兩臺(tái)設(shè)備加工順序相同的排序方案中尋找。為保證總加工周期最短，可按照以下方法進(jìn)行排序：

1、計(jì)算加工對(duì)象在兩臺(tái)設(shè)備的加工時(shí)間中的最小值。

2、若最小值屬于第一臺(tái)設(shè)備，則將該加工對(duì)象排在第一位；若隸屬于第二臺(tái)設(shè)備，則將該加工對(duì)象排在最后一位。

3、對(duì)剩余的加工對(duì)象重復(fù)上述步驟，直至全部加工對(duì)象的順序全都能夠決定為止。