?談論 OpenCV學習筆記（三）人臉檢測的代碼分析 


 
        
        一、預備知識：
        1、動態內存存儲及操作函數
        CvMemStorage
        typedef struct CvMemStorage
        {
            struct CvMemBlock* bottom;/* first allocated block */
            struct CvMemBlock* top; /* the current memory block - top of the 
        stack */
            struct CvMemStorage* parent; /* borrows new blocks from */
            int block_size; /* block size */
            int free_space; /* free space in the top block (in bytes) */
        } CvMemStorage;
        內存存儲器是一個可用來存儲諸如序列，輪廓，圖形,子劃分等動態增長數據結構的底層結構。它是由一系列以同等大小的內存塊構成，呈列表型 
        ---bottom 域指的是列首，top 域指的是當前指向的塊但未必是列尾.在bottom和top之間所有的塊(包括bottom, 
        不包括top）被完全占據了空間；在 top和列尾之間所有的塊（包括塊尾，不包括top)則是空的；而top塊本身則被占據了部分空間 -- 
        free_space 指的是top塊剩余的空字節數。新分配的內存緩沖區（或顯示的通過 cvMemStorageAlloc 函數分配，或隱示的通過 
        cvSeqPush, 
        cvGraphAddEdge等高級函數分配）總是起始于當前塊（即top塊)的剩余那部分，如果剩余那部分能滿足要求（夠分配的大小）。分配后，free_space 
        就減少了新分配的那部分內存大小，外加一些用來保存適當列型的附加大小。當top塊的剩余空間無法滿足被分配的塊（緩沖區）大小時，top塊的下一個存儲塊被置為當前塊（新的top塊） 
        --  free_space 
        被置為先前分配的整個塊的大小。如果已經不存在空的存儲塊（即：top塊已是列尾），則必須再分配一個新的塊（或從parent那繼承,見 
        cvCreateChildMemStorage)并將該塊加到列尾上去。于是，存儲器（memory storage)就如同棧（Stack)那樣, 
        bottom指向棧底，(top, free_space)對指向棧頂。棧頂可通過 cvSaveMemStoragePos保存，通過 
        cvRestoreMemStoragePos 恢復指向， 通過 cvClearStorage 重置。
        CvMemBlock
        內存存儲塊結構
        typedef struct CvMemBlock
        {
            struct CvMemBlock* prev;
            struct CvMemBlock* next;
        } CvMemBlock;
        CvMemBlock 代表一個單獨的內存存儲塊結構。 內存存儲塊中的實際數據存儲在 header塊 之后(即：存在一個頭指針 head 指向的塊 
        header ，該塊不存儲數據）,于是，內存塊的第 i 個字節可以通過表達式 ((char*)(mem_block_ptr+1))[i] 
        獲得。然而，通常沒必要直接去獲得存儲結構的域。
        CvMemStoragePos
        內存存儲塊地址
        typedef struct CvMemStoragePos
        {
            CvMemBlock* top;
            int free_space;
        } CvMemStoragePos;
        該結構（如以下所說）保存棧頂的地址，棧頂可以通過 cvSaveMemStoragePos 保存，也可以通過 
        cvRestoreMemStoragePos 恢復。
        ________________________________________
        cvCreateMemStorage
        創建內存塊
        CvMemStorage* cvCreateMemStorage( int block_size=0 );
         block_size：存儲塊的大小以字節表示。如果大小是 0 byte, 則將該塊設置成默認值  當前默認大小為64k.
        函數 cvCreateMemStorage 創建一內存塊并返回指向塊首的指針。起初，存儲塊是空的。頭部（即：header)的所有域值都為 
        0，除了 block_size 外.
        ________________________________________
        cvCreateChildMemStorage
        創建子內存塊
        CvMemStorage* cvCreateChildMemStorage( CvMemStorage* parent );
        parent    父內存塊
        函數 cvCreateChildMemStorage 
        創建一類似于普通內存塊的子內存塊，除了內存分配/釋放機制不同外。當一個子存儲塊需要一個新的塊加入時，它就試圖從parent 
        那得到這樣一個塊。如果 parent 中 還未被占據空間的那些塊中的第一個塊是可獲得的，就獲取第一個塊（依此類推），再將該塊從 parent  
        那里去除。如果不存在這樣的塊，則 parent 要么分配一個，要么從它自己 parent (即：parent 的 parent) 
        那借個過來。換句話說，完全有可能形成一個鏈或更為復雜的結構，其中的內存存儲塊互為 child/ parent 
        關系（父子關系）。當子存儲結構被釋放或清除，它就把所有的塊還給各自的 parent. 在其他方面，子存儲結構同普通存儲結構一樣。
        子存儲結構在下列情況中是非常有用的。想象一下，如果用戶需要處理存儲在某個塊中的動態數據，再將處理的結果存放在該塊中。在使用了最簡單的方法處理后，臨時數據作為輸入和輸出數據被存放在了同一個存儲塊中，于是該存儲塊看上去就類似下面處理后的樣子： 
        Dynamic data processing without using child storage. 
        結果，在存儲塊中，出現了垃圾（臨時數據）。然而，如果在開始處理數據前就先建立一個子存儲塊，將臨時數據寫入子存儲塊中并在最后釋放子存儲塊，那么最終在 
        源/目的存儲塊 （source / destination storage) 中就不會出現垃圾, 
        于是該存儲塊看上去應該是如下形式：Dynamic data processing using a child storage.
        cvReleaseMemStorage
        釋放內存塊
        void cvReleaseMemStorage( CvMemStorage** storage );
        storage: 指向被釋放了的存儲塊的指針
        函數 cvReleaseMemStorage 釋放所有的存儲（內存）塊 或者 將它們返回給各自的 parent（如果需要的話）。 接下來再釋放 
        header塊（即：釋放頭指針 head 指向的塊 = free(head)）并清除指向該塊的指針（即：head = NULL)。在釋放作為 
        parent 的塊之前，先清除各自的 child 塊。
        cvClearMemStorage
        清空內存存儲塊
        void cvClearMemStorage( CvMemStorage* storage );
        storage:存儲存儲塊
        函數 cvClearMemStorage 將存儲塊的 top 
        置到存儲塊的頭部（注：清空存儲塊中的存儲內容）。該函數并不釋放內存（僅清空內存）。假使該內存塊有一個父內存塊（即：存在一內存塊與其有父子關系），則函數就將所有的塊返回給其 
        parent.
        cvMemStorageAlloc
        在存儲塊中分配以內存緩沖區
        void* cvMemStorageAlloc( CvMemStorage* storage, size_t size );
        storage：內存塊. 
        size：緩沖區的大小.
        函數 cvMemStorageAlloc 
        在存儲塊中分配一內存緩沖區。該緩沖區的大小不能超過內存塊的大小，否則就會導致運行時錯誤。緩沖區的地址被調整為CV_STRUCT_ALIGN 字節 
        （當前為 sizeof(double)). 
        cvMemStorageAllocString
        在存儲塊中分配一文本字符串
        typedef struct CvString
        {
            int len;
            char* ptr;
        }
        CvString;
        CvString cvMemStorageAllocString( CvMemStorage* storage, const char* 
        ptr, int len=-1 );
        storage：存儲塊
        ptr：字符串
        len：字符串的長度（不計算'\0'）。如果參數為負數，函數就計算該字符串的長度。
        函數 cvMemStorageAlloString 
        在存儲塊中創建了一字符串的拷貝。它返回一結構，該結構包含字符串的長度（該長度或通過用戶傳遞，或通過計算得到）和指向被拷貝了的字符串的指針。
        cvSaveMemStoragePos
        保存內存塊的位置（地址）
        void cvSaveMemStoragePos( const CvMemStorage* storage, CvMemStoragePos* 
        pos );
        storage：內存塊. 
        pos：內存塊頂部位置。
        函數 cvSaveMemStoragePos 將存儲塊的當前位置保存到參數 pos 中。 函數 cvRestoreMemStoragePos 
        可進一步獲取該位置（地址）。
        cvRestoreMemStoragePos
        恢復內存存儲塊的位置
        void cvRestoreMemStoragePos( CvMemStorage* storage, CvMemStoragePos* pos 
        );
        storage：內存塊. 
        pos：新的存儲塊的位置
        函數 cvRestoreMemStoragePos 通過參數 pos 恢復內存塊的位置。該函數和函數 cvClearMemStorage 
        是釋放被占用內存塊的唯一方法。注意：沒有什么方法可去釋放存儲塊中被占用的部分內存。
        2、分類器結構及操作函數：
        CvHaarFeature
        #define CV_HAAR_FEATURE_MAX  3
        typedef struct CvHaarFeature
        {
            int  tilted;  
            struct
            {
                CvRect r;
                float weight;
        } rect[CV_HAAR_FEATURE_MAX]; 
         
        }
        CvHaarFeature;
        一個 harr 特征由 2－3 個具有相應權重的矩形組成
        titled ：/* 0 means up-right feature, 1 means 45--rotated feature */
        rect[CV_HAAR_FEATURE_MAX];  /* 2-3 rectangles with weights of opposite 
        signs and       with absolute values inversely proportional to the areas 
        of the rectangles. if rect[2].weight !=0, then  the feature consists of 
        3 rectangles, otherwise it consists of 2 */
        CvHaarClassifier
        typedef struct CvHaarClassifier
        {
            int count;  
            CvHaarFeature* haar_feature;
            float* threshold;
            int* left;
            int* right;
            float* alpha;
        }
        CvHaarClassifier;
        /* a single tree classifier (stump in the simplest case) that returns 
        the response for the feature   at the particular image location (i.e. 
        pixel sum over subrectangles of the window) and gives out a value 
        depending on the responce */
        int count;  /* number of nodes in the decision tree */
         /* these are "parallel" arrays. Every index i corresponds to a node of 
        the decision tree (root has 0-th index).
        left[i] - index of the left child (or negated index if the left child is 
        a leaf)
        right[i] - index of the right child (or negated index if the right child 
        is a leaf)
        threshold[i] - branch threshold. if feature responce is <= threshold, 
        left branch                      is chosen, otherwise right branch is 
        chosed.
        alpha[i] - output value correponding to the leaf. */
        CvHaarStageClassifier
        typedef struct CvHaarStageClassifier
        {
            int  count;  /* number of classifiers in the battery */
            float threshold; /* threshold for the boosted classifier */
            CvHaarClassifier* classifier; /* array of classifiers */
            /* these fields are used for organizing trees of stage classifiers,
               rather than just stright cascades */
            int next;
            int child;
            int parent;
        }
        CvHaarStageClassifier;

        /* a boosted battery of classifiers(=stage classifier): the stage 
        classifier returns 1 if the sum of the classifiers' responces is greater 
        than threshold and 0 otherwise */
        int  count;  /* number of classifiers in the battery */
        float threshold; /* threshold for the boosted classifier */
        CvHaarClassifier* classifier; /* array of classifiers */
        /* these fields are used for organizing trees of stage classifiers, 
        rather than just stright cascades */
        CvHaarClassifierCascade
        typedef struct CvHidHaarClassifierCascade CvHidHaarClassifierCascade;
        typedef struct CvHaarClassifierCascade
        {
            int  flags; 
            int  count;