1.vector中resize() 和 reserve() 函數(shù)的區(qū)別龙巨？
- reserve 容器預(yù)留空間 ,但并不真正創(chuàng)建對(duì)象，在創(chuàng)建對(duì)象前，不能引用容器內(nèi)元素嫂侍， 因此加入元素后懒鉴，需要push_back() 和 insert()函數(shù)
- resize() 改變?nèi)萜鞔笮∥饪悖⑶覄?chuàng)建對(duì)象魏颓。調(diào)用函數(shù)后叹话，可以直接引用容器內(nèi)對(duì)象。
- reserve()只有一個(gè)參數(shù)相速， 即需要預(yù)留容器的空間
- resize() 兩個(gè)參數(shù)，第一個(gè)容器新的大小抠刺，第二個(gè)是加入容器中的新元素
- 共同點(diǎn)是：都保證了vector中空間（capacity）的大小备恤，但是resize() 會(huì)調(diào)整 size() 的大小
2.說(shuō)一下new/delete 和malloc/free函數(shù)的區(qū)別稿饰？ malloc是庫(kù)函數(shù)嗎？ 還是系統(tǒng)調(diào)用函數(shù)露泊？
-
區(qū)別：
- malloc/free是C/C++語(yǔ)言的標(biāo)準(zhǔn)庫(kù)函數(shù)喉镰，new/delete是C++的運(yùn)算符胶果。它們都可用于申請(qǐng)動(dòng)態(tài)內(nèi)存和釋放內(nèi)存。但是new能夠自動(dòng)分配空間大小，而malloc需要計(jì)算字節(jié)數(shù)颤枪。
- new/delete能進(jìn)行對(duì)對(duì)象進(jìn)行構(gòu)造和析構(gòu)函數(shù)的調(diào)用進(jìn)而對(duì)內(nèi)存進(jìn)行更加詳細(xì)的工作逻锐，而malloc/free不能冒萄。
- new是類(lèi)型安全的忿晕，而malloc不是，比如：
int* p = new float[2]; // 編譯時(shí)指出錯(cuò)誤
int* p = malloc(2*sizeof(float)); // 編譯時(shí)無(wú)法指出錯(cuò)誤
new operator 由兩步構(gòu)成券盅，分別是 operator new 和 construct
- 返回值帮哈。malloc分配失敗時(shí)，返回的是空指針锰镀。new拋出std::bad_alloc異常娘侍。
- new/delete是保留字，不需要頭文件支持泳炉；malloc/free需要頭文件庫(kù)函數(shù)支持憾筏。
- 聯(lián)系：
- 既然new/delete的功能完全覆蓋了malloc/free，為什么C++還保留malloc/free呢花鹅？因?yàn)镃++程序經(jīng)常要調(diào)用C函數(shù)氧腰，而C程序只能用malloc/free管理動(dòng)態(tài)內(nèi)存。如果用free釋放“new創(chuàng)建的動(dòng)態(tài)對(duì)象”刨肃，那么該對(duì)象因無(wú)法執(zhí)行析構(gòu)函數(shù)而可能導(dǎo)致程序出錯(cuò)古拴。如果用delete釋放“malloc申請(qǐng)的動(dòng)態(tài)內(nèi)存”，理論上講程序不會(huì)出錯(cuò)真友，但是該程序的可讀性很差黄痪。所以new/delete，malloc/free必須配對(duì)使用盔然。
4.寫(xiě)一個(gè)插入排序
#include<iostream>
#include<vector>
using namespace std;
void swap(vector<int> &arr, int i, int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
};
void insertsort(vector<int> &arr){
int N = arr.size();
for(int i=1;i<N;++i){
for(int j=i;j>0;--j){
if(arr[j]<arr[j-1]){
swap(arr,j,j-1);
}
}
}
};
int main(){
vector<int> array = {5,3,0,6,1,4};
insertsort(array);
for(int i=0;i<array.size();++i){
std::cout << array[i] <<" ";
}
return 0;
}
5.static 的作用桅打？
- 飾普通變量，修改變量的存儲(chǔ)區(qū)域和生命周期愈案，使變量存儲(chǔ)在靜態(tài)區(qū)挺尾，在 main 函數(shù)運(yùn)行前就分配了空間，如果有初始值就用初始值初始化它刻帚，如果沒(méi)有初始值系統(tǒng)用默認(rèn)值初始化它潦嘶。
- 修飾普通函數(shù)，表明函數(shù)的作用范圍，僅在定義該函數(shù)的文件內(nèi)才能使用掂僵。在多人開(kāi)發(fā)項(xiàng)目時(shí)航厚，為了防止與他人命名空間里的函數(shù)重名，可以將函數(shù)定位為 static锰蓬。
- 修飾成員變量幔睬，修飾成員變量使所有的對(duì)象只保存一個(gè)該變量，而且不需要生成對(duì)象就可以訪問(wèn)該成員芹扭。
- 修飾成員函數(shù)麻顶，修飾成員函數(shù)使得不需要生成對(duì)象就可以訪問(wèn)該函數(shù)，但是在 static 函數(shù)內(nèi)不能訪問(wèn)非靜態(tài)成員舱卡。成員函數(shù)：特點(diǎn)： 區(qū)別與普通成員函數(shù)是辅肾，其沒(méi)有this指針，它不屬于某一個(gè)對(duì)象擁有轮锥，他屬于整個(gè)類(lèi)所有
- 優(yōu)點(diǎn)：由于沒(méi)有this指針的開(kāi)銷(xiāo)矫钓，靜態(tài)成員函數(shù)相比較全局函數(shù)，速度上會(huì)有少許的增長(zhǎng)
6.你了解面向?qū)ο髥幔?/h2>
封裝舍杜，繼承新娜、多態(tài)
封裝是信息隱藏，是指利用抽象數(shù)據(jù)類(lèi)型將數(shù)據(jù)和基于數(shù)據(jù)的操作封裝在一起既绩，使其構(gòu)成一個(gè)不可分割的獨(dú)立實(shí)體概龄，數(shù)據(jù)被保護(hù)在抽象數(shù)據(jù)類(lèi)型的內(nèi)部，盡可能地隱藏內(nèi)部的細(xì)節(jié)饲握，只保留一些對(duì)外接口使之與外部發(fā)生聯(lián)系私杜。系統(tǒng)的其他對(duì)象只能通過(guò)包裹在數(shù)據(jù)外面的已經(jīng)授權(quán)的操作來(lái)與這個(gè)封裝的對(duì)象進(jìn)行交流和交互。也就是說(shuō)用戶是無(wú)需知道對(duì)象內(nèi)部的細(xì)節(jié)互拾，但可以通過(guò)該對(duì)象對(duì)外的提供的接口來(lái)訪問(wèn)該對(duì)象歪今。
對(duì)于封裝而言，一個(gè)對(duì)象它所封裝的是自己的屬性和方法颜矿，所以它是不需要依賴其他對(duì)象就可以完成自己的操作。使用封裝有三大好處：
1嫉晶、良好的封裝能夠減少耦合骑疆。
2、類(lèi)內(nèi)部的結(jié)構(gòu)可以自由修改替废。
3箍铭、可以對(duì)成員進(jìn)行更精確的控制。
4椎镣、隱藏信息诈火，實(shí)現(xiàn)細(xì)節(jié)
7 .你喜歡合肥/上海嗎？
8. 你對(duì)我公司了解嗎状答？宣講會(huì)來(lái)了嗎冷守？
10. 花一分鐘時(shí)間介紹一下自己
11. 實(shí)習(xí)項(xiàng)目介紹一下
12. 如果用三個(gè)標(biāo)簽描述你自己
13刀崖、有什么示例可以證明的這些嗎？
14拍摇、介紹一下讓你感到最開(kāi)心的事情
15亮钦、業(yè)余時(shí)間你做什么？
16充活、一般做什么運(yùn)動(dòng)蜂莉？打什么球？
17混卵、你未來(lái)的職業(yè)規(guī)劃是什么樣的映穗？
18、你期望中的團(tuán)隊(duì)或者工資是怎么樣的幕随？
19男公、按照你的經(jīng)驗(yàn)如果做到一個(gè)團(tuán)隊(duì)協(xié)作？
20合陵、為什么要選擇枢赔。。拥知。踏拜？
21、最后你有什么問(wèn)題要問(wèn)我們嗎低剔？
22. extern?
- 放在變量和函數(shù)前速梗，表明該變量和函數(shù)在別處已有定義，在該行只是聲明襟齿，并沒(méi)有分配內(nèi)存姻锁，此處是為了引用別處已定義好的變量函數(shù)，起到跨越文件使用變量和函數(shù)的作用猜欺，其實(shí)可以直接include相應(yīng)的頭文件來(lái)使用位隶，主要是可以加快編譯速度。
例如开皿，A模塊 extern int a涧黄； A模塊源文件 a =10; B模塊同樣 extern int a； 我們會(huì)發(fā)現(xiàn)B模塊中并沒(méi)有a的內(nèi)存分配赋荆，但同樣也能使用a笋妥，原因在于B模塊會(huì)從A模塊中找到定義。 另外 extern int a = 10 等同于 int a =10; 但是另外一個(gè)文件include該文件時(shí)窄潭，會(huì)造成編譯器發(fā)現(xiàn)有兩個(gè)a 全局變量春宣。 因此我們通常將聲明放在頭文件
- extern c {} ，表明是C語(yǔ)言的接口函數(shù)，由于C和C++對(duì)函數(shù)命名的不一致月帝，C++支持函數(shù)重載躏惋，而C語(yǔ)言不支持，需要C++編譯器編譯的時(shí)候告知編譯器嫁赏，此處調(diào)用的是C中函數(shù)其掂，需要編譯器選擇C語(yǔ)言的編譯規(guī)則來(lái)編譯和鏈接此處的函數(shù)。
23. inline 內(nèi)聯(lián)函數(shù)
特征：
- 相當(dāng)于把內(nèi)聯(lián)函數(shù)里面的內(nèi)容寫(xiě)在調(diào)用內(nèi)聯(lián)函數(shù)處潦蝇；
- 相當(dāng)于不用執(zhí)行進(jìn)入函數(shù)的步驟款熬，直接執(zhí)行函數(shù)體；
- 相當(dāng)于宏攘乒，卻比宏多了類(lèi)型檢查贤牛，真正具有函數(shù)特性；
- 編譯器一般不內(nèi)聯(lián)包含循環(huán)则酝、遞歸殉簸、switch 等復(fù)雜操作的內(nèi)聯(lián)函數(shù)；
- 在類(lèi)聲明中定義的函數(shù)沽讹，除了虛函數(shù)的其他函數(shù)都會(huì)自動(dòng)隱式地當(dāng)成內(nèi)聯(lián)函數(shù)般卑。
24. inline優(yōu)缺點(diǎn)
優(yōu)點(diǎn)
內(nèi)聯(lián)函數(shù)同宏函數(shù)一樣將在被調(diào)用處進(jìn)行代碼展開(kāi)，省去了參數(shù)壓棧爽雄、棧幀開(kāi)辟與回收蝠检，結(jié)果返回等，從而提高程序運(yùn)行速度挚瘟。
內(nèi)聯(lián)函數(shù)相比宏函數(shù)來(lái)說(shuō)叹谁，在代碼展開(kāi)時(shí)，會(huì)做安全檢查或自動(dòng)類(lèi)型轉(zhuǎn)換（同普通函數(shù)）乘盖，而宏定義則不會(huì)焰檩。
在類(lèi)中聲明同時(shí)定義的成員函數(shù)，自動(dòng)轉(zhuǎn)化為內(nèi)聯(lián)函數(shù)订框，因此內(nèi)聯(lián)函數(shù)可以訪問(wèn)類(lèi)的成員變量析苫，宏定義則不能。
內(nèi)聯(lián)函數(shù)在運(yùn)行時(shí)可調(diào)試布蔗，而宏定義不可以藤违。
缺點(diǎn)
代碼膨脹。內(nèi)聯(lián)是以代碼膨脹（復(fù)制）為代價(jià)纵揍，消除函數(shù)調(diào)用帶來(lái)的開(kāi)銷(xiāo)。如果執(zhí)行函數(shù)體內(nèi)代碼的時(shí)間议街，相比于函數(shù)調(diào)用的開(kāi)銷(xiāo)較大泽谨，那么效率的收獲會(huì)很少。另一方面，每一處內(nèi)聯(lián)函數(shù)的調(diào)用都要復(fù)制代碼吧雹，將使程序的總代碼量增大骨杂，消耗更多的內(nèi)存空間。
inline 函數(shù)無(wú)法隨著函數(shù)庫(kù)升級(jí)而升級(jí)雄卷。inline函數(shù)的改變需要重新編譯搓蚪，不像 non-inline 可以直接鏈接。
是否內(nèi)聯(lián)丁鹉，程序員不可控妒潭。內(nèi)聯(lián)函數(shù)只是對(duì)編譯器的建議，是否對(duì)函數(shù)內(nèi)聯(lián)揣钦，決定權(quán)在于編譯器雳灾。
25. 說(shuō)說(shuō)引用，什么時(shí)候用引用好冯凹，什么時(shí)候用指針好谎亩？
答：
使用引用參數(shù)的主要原因有兩個(gè)：
程序員能修改調(diào)用函數(shù)中的數(shù)據(jù)對(duì)象
通過(guò)傳遞引用而不是整個(gè)數(shù)據(jù)–對(duì)象，可以提高程序的運(yùn)行速度
一般的原則：
對(duì)于使用引用的值而不做修改的函數(shù)：
如果數(shù)據(jù)對(duì)象很小宇姚，如內(nèi)置數(shù)據(jù)類(lèi)型或者小型結(jié)構(gòu)匈庭，則按照值傳遞
如果數(shù)據(jù)對(duì)象是數(shù)組，則使用指針（唯一的選擇）浑劳，并且指針聲明為指向const的指針
如果數(shù)據(jù)對(duì)象是較大的結(jié)構(gòu)阱持，則使用const指針或者引用，已提高程序的效率呀洲。這樣可以節(jié)省結(jié)構(gòu)所需的時(shí)間和空間
如果數(shù)據(jù)對(duì)象是類(lèi)對(duì)象紊选，則使用const引用（傳遞類(lèi)對(duì)象參數(shù)的標(biāo)準(zhǔn)方式是按照引用傳遞）
對(duì)于修改函數(shù)中數(shù)據(jù)的函數(shù)：
如果數(shù)據(jù)是內(nèi)置數(shù)據(jù)類(lèi)型，則使用指針
如果數(shù)據(jù)對(duì)象是數(shù)組道逗，則只能使用指針
如果數(shù)據(jù)對(duì)象是結(jié)構(gòu)兵罢，則使用引用或者指針
如果數(shù)據(jù)是類(lèi)對(duì)象，則使用引用
26. 堆/棧的區(qū)別滓窍？
-
管理方式不同：
對(duì)于棧來(lái)講卖词，是由編譯器自動(dòng)管理，無(wú)需我們手工控制吏夯；
對(duì)于堆來(lái)說(shuō)此蜈，申請(qǐng)和釋放工作由程序員控制，容易產(chǎn)生memory leak噪生。
-
空間大小不同：
對(duì)于棧來(lái)講裆赵，一般都是有一定的空間大小的，一般默認(rèn)的椂逅裕空間大小為1M战授，同時(shí)页藻，我們是可以進(jìn)行修改的；
對(duì)于堆來(lái)說(shuō)植兰，在32位系統(tǒng)下份帐，堆內(nèi)存可以達(dá)到4G的空間，從這個(gè)角度來(lái)看堆內(nèi)存幾乎是沒(méi)有什么限制的楣导。
-
能否產(chǎn)生碎片不同：
對(duì)于棧來(lái)講废境，不會(huì)有碎片，因?yàn)闂Ｊ窍冗M(jìn)后出的隊(duì)列筒繁，以至于永遠(yuǎn)都不可能有一個(gè)內(nèi)存塊從棧中間彈出噩凹，在他彈出之前，在他上面的后進(jìn)的棧內(nèi)容已經(jīng)被彈出膝晾；
對(duì)于堆來(lái)說(shuō)栓始，頻繁的new/delete勢(shì)必會(huì)造成內(nèi)存空間的不連續(xù)，從而造成大量的碎片血当，使程序效率降低幻赚。
-
生長(zhǎng)方向不同：
對(duì)于棧來(lái)講，生長(zhǎng)方向是向下的臊旭，是向著內(nèi)存地址減小的方向增長(zhǎng)落恼；
對(duì)于堆來(lái)說(shuō)，生長(zhǎng)方向是向上的离熏，也就是向著內(nèi)存地址增加的方向佳谦。
-
分配方式不同：
對(duì)于棧來(lái)講，棧有2種分配方式：靜態(tài)分配和動(dòng)態(tài)分配滋戳。靜態(tài)分配是編譯器完成的钻蔑，比如局部變量的分配。動(dòng)態(tài)分配由alloc函數(shù)進(jìn)行分配奸鸯，但是棧的動(dòng)態(tài)分配和堆是不同的咪笑，他的動(dòng)態(tài)分配是由編譯器進(jìn)行釋放，無(wú)需我們手工實(shí)現(xiàn)娄涩。
對(duì)于堆來(lái)說(shuō)窗怒，堆都是動(dòng)態(tài)分配的，沒(méi)有靜態(tài)分配的堆蓄拣。
-
分配效率不同：
對(duì)于棧來(lái)講扬虚，棧是機(jī)器系統(tǒng)提供的數(shù)據(jù)結(jié)構(gòu)，計(jì)算機(jī)會(huì)在底層對(duì)棧提供支持：分配專(zhuān)門(mén)的寄存器存放棧的地址球恤，壓棧出棧都有專(zhuān)門(mén)的指令執(zhí)行辜昵，這就決定了棧的效率比較高。
對(duì)于堆來(lái)說(shuō)咽斧，堆則是C/C++函數(shù)庫(kù)提供的路鹰，它的機(jī)制是很復(fù)雜的贷洲。顯然收厨，堆的效率比棧要低得多晋柱。
從這里我們可以看到，堆和棧相比诵叁，由于大量new/delete的使用雁竞，容易造成大量的內(nèi)存碎片；由于沒(méi)有專(zhuān)門(mén)的系統(tǒng)支持拧额，效率很低碑诉；由于可能引發(fā)用戶態(tài)和核心態(tài)的切換，內(nèi)存的申請(qǐng)侥锦，代價(jià)變得更加昂貴进栽。所以棧在程序中是應(yīng)用最廣泛的，就算是函數(shù)的調(diào)用也利用棧去完成解幽，函數(shù)調(diào)用過(guò)程中的參數(shù)唤蔗，返回地址餐弱，EBP和局部變量都采用棧的方式存放。
27. null與nullptr區(qū)別
NULL在C++中就是0唠帝， 這是因?yàn)樵贑++中void* 類(lèi)型是不允許隱式轉(zhuǎn)換成其他類(lèi)型的，所以之前C++中用0來(lái)代表空指針玄柏，但是在重載整形的情況下襟衰，會(huì)出現(xiàn)上述的問(wèn)題。所以粪摘，C++11加入了nullptr瀑晒，可以保證在任何情況下都代表空指針，而不會(huì)出現(xiàn)上述的情況徘意，因此苔悦，建議以后還是都用nullptr替代NULL吧，而NULL就當(dāng)做0使用映砖。
28. STL中map和unordered_map 區(qū)別
需要引入的頭文件不同
map:
#include < map >
unordered_map:
#include < unordered_map >
內(nèi)部實(shí)現(xiàn)機(jī)理不同
map： map內(nèi)部實(shí)現(xiàn)了一個(gè)紅黑樹(shù)（紅黑樹(shù)是非嚴(yán)格平衡二叉搜索樹(shù)间坐，而AVL是嚴(yán)格平衡二叉搜索樹(shù)），紅黑樹(shù)具有自動(dòng)排序的功能邑退，因此map內(nèi)部的所有元素都是有序的竹宋，紅黑樹(shù)的每一個(gè)節(jié)點(diǎn)都代表著map的一個(gè)元素。因此地技，對(duì)于map進(jìn)行的查找蜈七，刪除，添加等一系列的操作都相當(dāng)于是對(duì)紅黑樹(shù)進(jìn)行的操作莫矗。map中的元素是按照二叉搜索樹(shù)（又名二叉查找樹(shù)飒硅、二叉排序樹(shù)砂缩，特點(diǎn)就是左子樹(shù)上所有節(jié)點(diǎn)的鍵值都小于根節(jié)點(diǎn)的鍵值，右子樹(shù)所有節(jié)點(diǎn)的鍵值都大于根節(jié)點(diǎn)的鍵值）存儲(chǔ)的三娩，使用中序遍歷可將鍵值按照從小到大遍歷出來(lái)庵芭。
unordered_map: unordered_map內(nèi)部實(shí)現(xiàn)了一個(gè)哈希表（也叫散列表，通過(guò)把關(guān)鍵碼值映射到Hash表中一個(gè)位置來(lái)訪問(wèn)記錄雀监，查找的時(shí)間復(fù)雜度可達(dá)到O(1)双吆，其在海量數(shù)據(jù)處理中有著廣泛應(yīng)用）。因此会前，其元素的排列順序是無(wú)序的好乐。
優(yōu)缺點(diǎn)以及適用處
map：
1、優(yōu)點(diǎn)：
1）有序性瓦宜，這是map結(jié)構(gòu)最大的優(yōu)點(diǎn)蔚万，其元素的有序性在很多應(yīng)用中都會(huì)簡(jiǎn)化很多的操作
2）紅黑樹(shù)，內(nèi)部實(shí)現(xiàn)一個(gè)紅黑書(shū)使得map的很多操作在lgn的時(shí)間復(fù)雜度下就可以實(shí)現(xiàn)临庇，因此效率非常的高
2反璃、缺點(diǎn)： 空間占用率高，因?yàn)閙ap內(nèi)部實(shí)現(xiàn)了紅黑樹(shù)苔巨，雖然提高了運(yùn)行效率版扩，但是因?yàn)槊恳粋€(gè)節(jié)點(diǎn)都需要額外保存父節(jié)點(diǎn)、孩子節(jié)點(diǎn)和紅/黑性質(zhì)侄泽，使得每一個(gè)節(jié)點(diǎn)都占用大量的空間
3礁芦、適用處：對(duì)于那些有順序要求的問(wèn)題，用map會(huì)更高效一些
unordered_map：
1悼尾、優(yōu)點(diǎn)： 因?yàn)閮?nèi)部實(shí)現(xiàn)了哈希表柿扣，因此其查找速度非常的快
2、缺點(diǎn)： 哈希表的建立比較耗費(fèi)時(shí)間
3闺魏、適用處： 對(duì)于查找問(wèn)題未状，unordered_map會(huì)更加高效一些，因此遇到查找問(wèn)題析桥，常會(huì)考慮一下用unordered_map
29. c++ 中l(wèi)ist, vector, map, set 區(qū)別與用法比較
List封裝了鏈表,Vector封裝了數(shù)組, list和vector得最主要的區(qū)別在于vector使用連續(xù)內(nèi)存存儲(chǔ)的司草，他支持[]運(yùn)算符，而list是以鏈表形式實(shí)現(xiàn)的泡仗，不支持[]埋虹。
Vector對(duì)于隨機(jī)訪問(wèn)的速度很快，但是對(duì)于插入尤其是在頭部插入元素速度很慢娩怎，在尾部插入速度很快搔课。List對(duì)于隨機(jī)訪問(wèn)速度慢得多，因?yàn)榭赡芤闅v整個(gè)鏈表才能做到截亦，但是對(duì)于插入就快的多了爬泥，不需要拷貝和移動(dòng)數(shù)據(jù)柬讨，只需要改變指針的指向就可以了。另外對(duì)于新添加的元素袍啡，Vector有一套算法踩官，而List可以任意加入。
Map,Set屬于標(biāo)準(zhǔn)關(guān)聯(lián)容器葬馋，使用了非常高效的平衡檢索二叉樹(shù)：紅黑樹(shù)卖鲤，他的插入刪除效率比其他序列容器高是因?yàn)椴恍枰鰞?nèi)存拷貝和內(nèi)存移動(dòng)，而直接替換指向節(jié)點(diǎn)的指針即可畴嘶。
Set和Vector的區(qū)別在于Set不包含重復(fù)的數(shù)據(jù)。Set和Map的區(qū)別在于Set只含有Key集晚，而Map有一個(gè)Key和Key所對(duì)應(yīng)的Value兩個(gè)元素窗悯。
Map和Hash_Map的區(qū)別是Hash_Map使用了Hash算法來(lái)加快查找過(guò)程，但是需要更多的內(nèi)存來(lái)存放這些Hash桶元素偷拔，因此可以算得上是采用空間來(lái)?yè)Q取時(shí)間策略蒋院。
vector 向量 相當(dāng)于一個(gè)數(shù)組
在內(nèi)存中分配一塊連續(xù)的內(nèi)存空間進(jìn)行存儲(chǔ)。支持不指定vector大小的存儲(chǔ)莲绰。STL內(nèi)部實(shí)現(xiàn)時(shí)欺旧，首先分配一個(gè)非常大的內(nèi)存空間預(yù)備進(jìn)行存儲(chǔ)，即capacituy（）函數(shù)返回的大小蛤签，當(dāng)超過(guò)此分配的空間時(shí)再整體重新放分配一塊內(nèi)存存儲(chǔ)辞友，這給人以vector可以不指定vector即一個(gè)連續(xù)內(nèi)存的大小的感覺(jué)。通常此默認(rèn)的內(nèi)存分配能完成大部分情況下的存儲(chǔ)震肮。
優(yōu)點(diǎn)：
- (1) 不指定一塊內(nèi)存大小的數(shù)組的連續(xù)存儲(chǔ)称龙，即可以像數(shù)組一樣操作，但可以對(duì)此數(shù)組進(jìn)行動(dòng)態(tài)操作戳晌。通常體現(xiàn)在push_back() pop_back()
- (2) 隨機(jī)訪問(wèn)方便鲫尊，即支持[ ]操作符和vector.at()
- (3) 節(jié)省空間。
缺點(diǎn)：
- (1) 在內(nèi)部進(jìn)行插入刪除操作效率低沦偎。
- (2) 只能在vector的最后進(jìn)行push和pop疫向，不能在vector的頭進(jìn)行push和pop。
- (3) 當(dāng)動(dòng)態(tài)添加的數(shù)據(jù)超過(guò)vector默認(rèn)分配的大小時(shí)要進(jìn)行整體的重新分配豪嚎、拷貝與釋放
list 雙向鏈表
每一個(gè)結(jié)點(diǎn)都包括一個(gè)信息快Info搔驼、一個(gè)前驅(qū)指針Pre、一個(gè)后驅(qū)指針Post疙渣〕着可以不分配必須的內(nèi)存大小方便的進(jìn)行添加和刪除操作。使用的是非連續(xù)的內(nèi)存空間進(jìn)行存儲(chǔ)妄荔。
優(yōu)點(diǎn)：
- (1) 不使用連續(xù)內(nèi)存完成動(dòng)態(tài)操作泼菌。
- (2) 在內(nèi)部方便的進(jìn)行插入和刪除操作
- (3) 可在兩端進(jìn)行push谍肤、pop
缺點(diǎn)：
- (1) 不能進(jìn)行內(nèi)部的隨機(jī)訪問(wèn)，即不支持[ ]操作符和vector.at()
- (2) 相對(duì)于verctor占用內(nèi)存多
deque
雙端隊(duì)列 double-end queue
deque是在功能上合并了vector和list哗伯。
優(yōu)點(diǎn)：
- (1) 隨機(jī)訪問(wèn)方便荒揣，即支持[ ]操作符和vector.at()
- (2) 在內(nèi)部方便的進(jìn)行插入和刪除操作
- (3) 可在兩端進(jìn)行push、pop
缺點(diǎn)：
(1) 占用內(nèi)存多
使用區(qū)別：
- 1 如果你需要高效的隨即存取焊刹，而不在乎插入和刪除的效率系任，使用vector
- 2 如果你需要大量的插入和刪除，而不關(guān)心隨即存取虐块，則應(yīng)使用list
- 3 如果你需要隨即存取俩滥，而且關(guān)心兩端數(shù)據(jù)的插入和刪除，則應(yīng)使用deque
數(shù)據(jù)結(jié)構(gòu)
deque,queue,vector,stack,list
X a(n,t);
a.insert(p,t);
a.insert(p,n,t);
a.erase(p);
a.clear;
a.front();
a.back();
a.push_front(t);
a.push_back(t);
a.pop_front(t);
a.pop_back(t);
a[n];
a.at(t);
30. 繼承的種類(lèi)
31. 線程與進(jìn)程
https://zhuanlan.zhihu.com/p/60375108
進(jìn)程與線程的區(qū)別
進(jìn)程是CPU資源分配的基本單位贺奠，線程是獨(dú)立運(yùn)行和獨(dú)立調(diào)度的基本單位（CPU上真正運(yùn)行的是線程）霜旧。
進(jìn)程擁有自己的資源空間，一個(gè)進(jìn)程包含若干個(gè)線程儡率，線程與CPU資源分配無(wú)關(guān)挂据，多個(gè)線程共享同一進(jìn)程內(nèi)的資源。
線程的調(diào)度與切換比進(jìn)程快很多儿普。
32. 并發(fā)與并行
并發(fā)：
在操作系統(tǒng)中崎逃，某一時(shí)間段，幾個(gè)程序在同一個(gè)CPU上運(yùn)行眉孩，但在任意一個(gè)時(shí)間點(diǎn)上个绍，只有一個(gè)程序在CPU上運(yùn)行。
當(dāng)有多個(gè)線程時(shí)勺像，如果系統(tǒng)只有一個(gè)CPU障贸，那么CPU不可能真正同時(shí)進(jìn)行多個(gè)線程，CPU的運(yùn)行時(shí)間會(huì)被劃分成若干個(gè)時(shí)間段吟宦，每個(gè)時(shí)間段分配給各個(gè)線程去執(zhí)行篮洁，一個(gè)時(shí)間段里某個(gè)線程運(yùn)行時(shí)，其他線程處于掛起狀態(tài)殃姓，這就是并發(fā)袁波。并發(fā)解決了程序排隊(duì)等待的問(wèn)題，如果一個(gè)程序發(fā)生阻塞蜗侈，其他程序仍然可以正常執(zhí)行篷牌。
并行：
當(dāng)操作系統(tǒng)有多個(gè)CPU時(shí)，一個(gè)CPU處理A線程踏幻，另一個(gè)CPU處理B線程枷颊，兩個(gè)線程互相不搶占CPU資源，可以同時(shí)進(jìn)行，這種方式成為并行夭苗。
區(qū)別：
并發(fā)只是在宏觀上給人感覺(jué)有多個(gè)程序在同時(shí)運(yùn)行信卡，但在實(shí)際的單CPU系統(tǒng)中，每一時(shí)刻只有一個(gè)程序在運(yùn)行题造，微觀上這些程序是分時(shí)交替執(zhí)行傍菇。
在多CPU系統(tǒng)中，將這些并發(fā)執(zhí)行的程序分配到不同的CPU上處理界赔，每個(gè)CPU用來(lái)處理一個(gè)程序丢习，這樣多個(gè)程序便可以實(shí)現(xiàn)同時(shí)執(zhí)行。
例子：
你吃飯吃到一半淮悼，電話來(lái)了咐低，你一直到吃完了以后才去接，這就說(shuō)明你不支持并發(fā)也不支持并行敛惊。
你吃飯吃到一半渊鞋，電話來(lái)了，你停了下來(lái)接了電話瞧挤，接完后繼續(xù)吃飯，這說(shuō)明你支持并發(fā)儡湾。
你吃飯吃到一半特恬，電話來(lái)了，你一邊打電話一邊吃飯徐钠，這說(shuō)明你支持并行癌刽。
并發(fā)的關(guān)鍵是你有處理多個(gè)任務(wù)的能力，不一定要同時(shí)尝丐。并行的關(guān)鍵是你有同時(shí)處理多個(gè)任務(wù)的能力显拜。所以我認(rèn)為它們最關(guān)鍵的點(diǎn)就是：是否是『同時(shí)』。
33. 進(jìn)程的三個(gè)狀態(tài)
? 就緒狀態(tài)爹袁，運(yùn)行狀態(tài)远荠，阻塞狀態(tài)
34. 進(jìn)程從執(zhí)行狀態(tài)轉(zhuǎn)換到阻塞狀態(tài)的可能原因是本進(jìn)程：
需要等待其他進(jìn)程的執(zhí)行結(jié)果
執(zhí)行了P操作
35. Kill與kill-9
? kill是Linux下常見(jiàn)的命令。其man手冊(cè)的功能定義如下：
kill – send a signal to a process
明朗了失息，其實(shí)kill就是給某個(gè)進(jìn)程id發(fā)送了一個(gè)信號(hào)譬淳。默認(rèn)發(fā)送的信號(hào)是SIGTERM，而kill -9發(fā)送的信號(hào)是SIGKILL盹兢，即exit邻梆。exit信號(hào)不會(huì)被系統(tǒng)阻塞，所以kill -9能順利殺掉進(jìn)程绎秒。當(dāng)然你也可以使用kill發(fā)送其他信號(hào)給進(jìn)程浦妄。
經(jīng)常使用的killall呢？
killall – kill processes by name 即，通過(guò)指定進(jìn)程名的方式殺死進(jìn)程剂娄。
36. 構(gòu)造函數(shù)為什么不能是虛函數(shù)蠢涝？
虛函數(shù)采用的是虛調(diào)用的辦法，虛調(diào)用是一種可以在只知道部分信息的情況下正常工作的機(jī)制宜咒，特別是 在我們只知道接口而不知道準(zhǔn)確的對(duì)象類(lèi)型的函數(shù)惠赫。 但是，要?jiǎng)?chuàng)建一個(gè)類(lèi)對(duì)象故黑，必須要讓構(gòu)造函數(shù)知道對(duì)象的準(zhǔn)確類(lèi)型儿咱，所以構(gòu)造函數(shù)不能為虛！
37. 析構(gòu)函數(shù)為何常常為虛函數(shù)场晶？
創(chuàng)建一個(gè)對(duì)象時(shí)我們總是要明白指定對(duì)象的類(lèi)型混埠。我們往往通過(guò)基類(lèi)的指針來(lái)銷(xiāo)毀對(duì)象。這時(shí)候假設(shè)析構(gòu)函數(shù)不是虛函數(shù)诗轻，就不能正確識(shí)別對(duì)象類(lèi)型從而不能正確調(diào)用析構(gòu)函數(shù)钳宪。
38. 虛擬內(nèi)存
虛擬內(nèi)存是計(jì)算機(jī)系統(tǒng)內(nèi)存管理的一種技術(shù)。它使得應(yīng)用程序認(rèn)為它擁有連續(xù)可用的內(nèi)存（一個(gè)連續(xù)完整的地址空間）扳炬，而實(shí)際上吏颖，它通常是被分隔成多個(gè)物理內(nèi)存碎片，還有部分暫時(shí)存儲(chǔ)在外部磁盤(pán)存儲(chǔ)器上恨樟，在需要時(shí)進(jìn)行數(shù)據(jù)交換半醉。與沒(méi)有使用虛擬內(nèi)存技術(shù)的系統(tǒng)相比，使用這種技術(shù)的系統(tǒng)使得大型程序的編寫(xiě)變得更容易劝术，對(duì)真正的物理內(nèi)存（例如RAM）的使用也更有效率缩多。
注意：虛擬內(nèi)存不只是“用磁盤(pán)空間來(lái)擴(kuò)展物理內(nèi)存”的意思——這只是擴(kuò)充內(nèi)存級(jí)別以使其包含硬盤(pán)驅(qū)動(dòng)器而已。把內(nèi)存擴(kuò)展到磁盤(pán)只是使用虛擬內(nèi)存技術(shù)的一個(gè)結(jié)果养晋，它的作用也可以通過(guò)覆蓋或者把處于不活動(dòng)狀態(tài)的程序以及它們的數(shù)據(jù)全部交換到磁盤(pán)上等方式來(lái)實(shí)現(xiàn)衬吆。對(duì)虛擬內(nèi)存的定義是基于對(duì)地址空間的重定義的，即把地址空間定義為“連續(xù)的虛擬內(nèi)存地址”绳泉，以借此“欺騙”程序逊抡，使它們以為自己正在使用一大塊的“連續(xù)”地址。
39. 虛擬內(nèi)存提供了三個(gè)重要的能力： 緩存圈纺，內(nèi)存管理秦忿，內(nèi)存保護(hù)
將主存視為一個(gè)存儲(chǔ)在磁盤(pán)上的地址空間的高速緩存，在主存中只保存活動(dòng)區(qū)域蛾娶，并根據(jù)需要在磁盤(pán)和主存之間來(lái)回傳送數(shù)據(jù)
為每個(gè)進(jìn)程提供了一致的地址空間灯谣，簡(jiǎn)化內(nèi)存管理
保護(hù)了每個(gè)進(jìn)程的地址空間不被其他進(jìn)程破壞
40. 那么虛表指針在什么時(shí)候，或者說(shuō)在什么地方初始化呢蛔琅？
答案： 是在構(gòu)造函數(shù)中進(jìn)行虛表的創(chuàng)建和虛表指針的初始化胎许。還記得構(gòu)造函數(shù)的調(diào)用順序嗎，在構(gòu)造子類(lèi)對(duì)象時(shí)，要先調(diào)用父類(lèi)的構(gòu)造函數(shù)辜窑，此時(shí)編譯器只“看到了”父類(lèi)钩述，并不知道后面是否后還有繼承者，它初始化父類(lèi)對(duì)象的虛表指針穆碎，該虛表指針指向父類(lèi)的虛表牙勘。當(dāng)執(zhí)行子類(lèi)的構(gòu)造函數(shù)時(shí)，子類(lèi)對(duì)象的虛表指針被初始化所禀，指向自身的虛表方面。
41. 虛函數(shù)與純虛函數(shù)區(qū)別：
虛函數(shù)和純虛函數(shù)可以定義在同一個(gè)類(lèi)中，含有純虛函數(shù)的類(lèi)被稱為抽象類(lèi)色徘，而只含有虛函數(shù)的類(lèi)不能被稱為抽象類(lèi)恭金。
虛函數(shù)可以被直接使用，也可以被子類(lèi)重載以后以多態(tài)的形式調(diào)用褂策，而純虛函數(shù)必須在子類(lèi)中實(shí)現(xiàn)該函數(shù)才可以使用横腿，因?yàn)榧兲摵瘮?shù)在基類(lèi)只有聲明而沒(méi)有定義。
虛函數(shù)和純虛函數(shù)都可以在子類(lèi)中被重載斤寂，以多態(tài)的形式被調(diào)用耿焊。
虛函數(shù)和純虛函數(shù)通常存在于抽象基類(lèi)之中，被繼承的子類(lèi)重載遍搞，目的是提供一個(gè)統(tǒng)一的接口搀别。
在虛函數(shù)和純虛函數(shù)的定義中不能有static標(biāo)識(shí)符，因?yàn)楸籹tatic修飾的函數(shù)在編譯時(shí)候要求前期綁定,然而虛函數(shù)卻是動(dòng)態(tài)綁定尾抑，而且被兩者修飾的函數(shù)生命周期也不一樣。
虛函數(shù)必須實(shí)現(xiàn)蒂培，如果不實(shí)現(xiàn)再愈，編譯器將報(bào)錯(cuò)。
對(duì)于虛函數(shù)來(lái)說(shuō)护戳，父類(lèi)和子類(lèi)都有各自的版本翎冲。由多態(tài)方式調(diào)用的時(shí)候動(dòng)態(tài)綁定。
實(shí)現(xiàn)了純虛函數(shù)的子類(lèi)媳荒，該純虛函數(shù)在子類(lèi)中就變成了虛函數(shù)抗悍，子類(lèi)的子類(lèi)即孫子類(lèi)可以覆蓋該虛函數(shù)，由多態(tài)方式調(diào)用的時(shí)候動(dòng)態(tài)綁定钳枕。
虛函數(shù)是C++中用于實(shí)現(xiàn)多態(tài)的機(jī)制缴渊。核心理念就是通過(guò)基類(lèi)訪問(wèn)派生類(lèi)定義的函數(shù)。
多態(tài)性指相同對(duì)象收到不同消息或不同對(duì)象收到相同消息時(shí)產(chǎn)生不同的實(shí)現(xiàn)動(dòng)作鱼炒。
如果一個(gè)類(lèi)中含有純虛函數(shù)衔沼，那么任何試圖對(duì)該類(lèi)進(jìn)行實(shí)例化的語(yǔ)句都將導(dǎo)致錯(cuò)誤的產(chǎn)生，因?yàn)槌橄蠡?lèi)(ABC)是不能被直接調(diào)用的。必須被子類(lèi)繼承重載以后指蚁，根據(jù)要求調(diào)用其子類(lèi)的方法菩佑。
42. malloc的原理？brk系統(tǒng)調(diào)用和mmap系統(tǒng)調(diào)用的作用分別是什么凝化？
malloc根據(jù)用戶要求從堆里動(dòng)態(tài)分配內(nèi)存空間稍坯。為減少內(nèi)存碎片降低內(nèi)存開(kāi)銷(xiāo)，采用內(nèi)存池的方式搓劫。 首先分配較大內(nèi)存為堆瞧哟，分為大小不同的內(nèi)存塊進(jìn)行管理。malloc利用隱式鏈表糟把，在分配時(shí)遍歷整個(gè)鏈表绢涡，選擇大小合適的內(nèi)存塊分配。 內(nèi)存分配時(shí)會(huì)調(diào)用brk或mmap系統(tǒng)遣疯，小于128K時(shí)調(diào)用brk在堆中分配雄可，大于128K時(shí)調(diào)用mmap在映射區(qū)分配。
43. 進(jìn)程的缺陷的缠犀，主要體現(xiàn)在兩點(diǎn)上：
進(jìn)程只能在一個(gè)時(shí)間干一件事数苫，如果想同時(shí)干兩件事或多件事，進(jìn)程就無(wú)能為力了辨液。
進(jìn)程在執(zhí)行的過(guò)程中如果阻塞虐急，例如等待輸入，整個(gè)進(jìn)程就會(huì)掛起滔迈，即使進(jìn)程中有些工作不依賴于輸入的數(shù)據(jù)止吁，也將無(wú)法執(zhí)行。
如果這兩個(gè)缺點(diǎn)理解比較困難的話燎悍，舉個(gè)現(xiàn)實(shí)的例子也許你就清楚了：如果把我們上課的過(guò)程看成一個(gè)進(jìn)程的話敬惦，那么我們要做的是耳朵聽(tīng)老師講課，手上還要記筆記谈山，腦子還要思考問(wèn)題俄删，這樣才能高效的完成聽(tīng)課的任務(wù)。而如果只提供進(jìn)程這個(gè)機(jī)制的話奏路，上面這三件事將不能同時(shí)執(zhí)行畴椰，同一時(shí)間只能做一件事，聽(tīng)的時(shí)候就不能記筆記鸽粉，也不能用腦子思考斜脂，這是其一；如果老師在黑板上寫(xiě)演算過(guò)程潜叛，我們開(kāi)始記筆記秽褒，而老師突然有一步推不下去了践付，阻塞住了炊邦，他在那邊思考著涨共，而我們呢测暗，也不能干其他事，即使你想趁此時(shí)思考一下剛才沒(méi)聽(tīng)懂的一個(gè)問(wèn)題都不行蚂踊，這是其二约谈。
44. 線程的優(yōu)點(diǎn)
因?yàn)橐l(fā)，我們發(fā)明了進(jìn)程犁钟，又進(jìn)一步發(fā)明了線程棱诱。
進(jìn)程和線程的并發(fā)層次不同：
進(jìn)程屬于在處理器這一層上提供的抽象；
線程則屬于在進(jìn)程這個(gè)層次上再提供了一層并發(fā)的抽象涝动。如果我們進(jìn)入計(jì)算機(jī)體系結(jié)構(gòu)里迈勋，就會(huì)發(fā)現(xiàn)，流水線提供的也是一種并發(fā)醋粟，不過(guò)是指令級(jí)的并發(fā)靡菇。這樣，流水線米愿、線程厦凤、進(jìn)程就從低到高在三個(gè)層次上提供我們所迫切需要的并發(fā)！
除了提高進(jìn)程的并發(fā)度育苟，線程還有個(gè)好處较鼓，就是可以有效地利用多處理器和多核計(jì)算機(jī)。現(xiàn)在的處理器有個(gè)趨勢(shì)就是朝著多核方向發(fā)展违柏，在沒(méi)有線程之前博烂，多核并不能讓一個(gè)進(jìn)程的執(zhí)行速度提高，原因還是上面所有的兩點(diǎn)限制漱竖。但如果講一個(gè)進(jìn)程分解為若干個(gè)線程脖母，則可以讓不同的線程運(yùn)行在不同的核上，從而提高了進(jìn)程的執(zhí)行速度闲孤。
例如：我們經(jīng)常使用Word進(jìn)行文字排版，實(shí)際上就打開(kāi)了多個(gè)線程烤礁。這些線程一個(gè)負(fù)責(zé)顯示讼积，一個(gè)接受鍵盤(pán)的輸入，一個(gè)進(jìn)行存盤(pán)等等脚仔。這些線程一起運(yùn)行勤众，讓我們感覺(jué)到我們輸入和屏幕顯示同時(shí)發(fā)生，而不是輸入一些字符鲤脏，過(guò)一段時(shí)間才能看到顯示出來(lái)们颜。在我們不經(jīng)意間吕朵，還進(jìn)行了自動(dòng)存盤(pán)操作。這就是線程給我們帶來(lái)的方便之處窥突。
45. 進(jìn)程與線程的區(qū)別
進(jìn)程是具有一定獨(dú)立功能的程序關(guān)于某個(gè)數(shù)據(jù)集合上的一次運(yùn)行活動(dòng),進(jìn)程是系統(tǒng)進(jìn)行資源分配和調(diào)度的一個(gè)獨(dú)立單位努溃。
線程是進(jìn)程的一個(gè)實(shí)體, 是CPU調(diào)度和分派的基本單位,它是比進(jìn)程更小的能獨(dú)立運(yùn)行的基本單位.線程自己基本上不擁有系統(tǒng)資源,只擁有一點(diǎn)在運(yùn)行中必不可少的資源(如程序計(jì)數(shù)器,一組寄存器和棧),但是它可與同屬一個(gè)進(jìn)程的其他的線程共享進(jìn)程所擁有的全部資源。
一個(gè)線程可以創(chuàng)建和撤銷(xiāo)另一個(gè)線程阻问，同一個(gè)進(jìn)程中的多個(gè)線程之間可以并發(fā)執(zhí)行梧税。
進(jìn)程和線程的主要差別在于它們是不同的操作系統(tǒng)資源管理方式。進(jìn)程有獨(dú)立的地址空間称近，一個(gè)進(jìn)程崩潰后第队，在保護(hù)模式下不會(huì)對(duì)其它進(jìn)程產(chǎn)生影響，而線程只是一個(gè)進(jìn)程中的不同執(zhí)行路徑刨秆。線程有自己的堆棧和局部變量凳谦，但線程之間沒(méi)有單獨(dú)的地址空間，一個(gè)線程死掉就等于整個(gè)進(jìn)程死掉衡未，所以多進(jìn)程的程序要比多線程的程序健壯尸执，但在進(jìn)程切換時(shí)，耗費(fèi)資源較大眠屎，效率要差一些剔交。但對(duì)于一些要求同時(shí)進(jìn)行并且又要共享某些變量的并發(fā)操作，只能用線程改衩，不能用進(jìn)程岖常。
46. 一個(gè)由C/C++編譯的程序占用的內(nèi)存分配：
棧區(qū)（stack）：由編譯器自動(dòng)分配釋放，存放函數(shù)的參數(shù)值葫督，局部變量的值等竭鞍。其操作方式類(lèi)似于數(shù)據(jù)結(jié)構(gòu)中的棧。
堆區(qū)（heap）：一般由程序員分配釋放橄镜，若程序員不釋放偎快，程序結(jié)束時(shí)可能由OS（操作系統(tǒng)）回收。注意它與數(shù)據(jù)結(jié)構(gòu)中的堆是兩回事洽胶，分配方式倒是類(lèi)似于鏈表晒夹。
全局區(qū)（靜態(tài)區(qū)）（static）：全局變量和靜態(tài)變量的存儲(chǔ)是放在一塊的，初始化的全局變量和靜態(tài)變量在一塊區(qū)域姊氓，未初始化的全局變量和未初始化的靜態(tài)變量在相鄰的另一塊區(qū)域丐怯。程序結(jié)束后由系統(tǒng)釋放。
文字常量區(qū)：常量字符串就是放在這里的翔横。程序結(jié)束后由系統(tǒng)釋放读跷。
程序代碼區(qū)：存放函數(shù)體的二進(jìn)制代碼。
int a=0; 全局初始化區(qū)
char *p1; 全局未初始化區(qū)
int main()
{
int b; //棧
char s[]="abc"; //棧
char *p2; //棧
char *p3="123456"; //123456/0在常量區(qū)禾唁，p3在棧上效览。
static int c =0无切；//全局（靜態(tài)）初始化區(qū)
p1 = (char *)malloc(10); //分配得來(lái)得10和20字節(jié)的區(qū)域就在堆區(qū)
p2 = (char *)malloc(20);
strcpy(p3,"123456"); //123456/0放在常量區(qū)，編譯器可能會(huì)將它與p3所指向的"123456" 優(yōu)化成一個(gè)地方丐枉。
}
47. NMS 非極大值抑制的原理與C++代碼實(shí)現(xiàn)
? 非極大值抑制：先假設(shè)有6個(gè)候選框哆键，根據(jù)分類(lèi)器類(lèi)別分類(lèi)概率做排序，從小到大分別屬于車(chē)輛的概率分別為A矛洞、B洼哎、C、D沼本、E噩峦、F。
1抽兆、從最大概率矩形框F開(kāi)始识补，分別判斷A~E與F的重疊度IOU是否大于某個(gè)設(shè)定的閾值;
2、假設(shè)B辫红、D與F的重疊度超過(guò)閾值凭涂，那么就扔掉B、D贴妻；并標(biāo)記第一個(gè)矩形框F切油，是我們保留下來(lái)的。
3名惩、從剩下的矩形框A澎胡、C、E中娩鹉，選擇概率最大的E攻谁，然后判斷E與A、C的重疊度弯予，重疊度大于一定的閾值戚宦，那么就扔掉；并標(biāo)記E是我們保留下來(lái)的第二個(gè)矩形框锈嫩。
4受楼、一直重復(fù)這個(gè)過(guò)程，找到所有曾經(jīng)被保留下來(lái)的矩形框呼寸。
*//**升序排列*
bool cmpScore(Bbox lsh, Bbox rsh) {
if (lsh.score < rsh.score)
return true;
else
return false;
}
\8. https://blog.csdn.net/krais_wk/article/details/80938752
48. 單峰函數(shù)求極值
#include<bits/stdc++.h>
using namespace std;
double a,b,c;
inline double f(double x) {
return a*x*x+b*x+c;
}
int main(void)
{
cin>>a>>b>>c;
//形如y=ax^2+by+c的二次函數(shù)
double l=-1e9,r=1e9;
while (l+1e-9<r)
{
double lmid=l+(r-l)/3.0;
//圖像上位于1/3部分的靠左的mid值
double rmid=l+(r-l)/3.0*2.0;
//圖像上位于2/3部分的靠右的mid值
if (f(lmid)<f(rmid)) l=lmid;
else r=rmid;
//求單峰極值
}
cout<<"X="<<l<<'\n';
cout<<"Y="<<f(l);
}
49. Eigen矩陣儲(chǔ)存
數(shù)據(jù)存儲(chǔ)：Matrix創(chuàng)建的矩陣默認(rèn)是按列存儲(chǔ)那槽，Eigen在處理按列存儲(chǔ)的矩陣時(shí)會(huì)更加高效。如果想修改可以在創(chuàng)建矩陣的時(shí)候加入?yún)?shù)等舔，如:
Matrix<int,3, 4, ColMajor> Acolmajor;
Matrix<int,3, 4, RowMajor> Arowmajor;
50. 激光slam與視覺(jué)SLAM的優(yōu)劣
51. SIFT缺點(diǎn)（Scale-invariant feature transform）
SIFT是十分經(jīng)典的算法，但有以下缺點(diǎn)：
實(shí)時(shí)性不高
特征點(diǎn)比較少
對(duì)邊緣光滑的圖像有時(shí)無(wú)能為力
52. SIFT提取策略
-
構(gòu)建尺度空間
這是一個(gè)初始化操作糟趾，尺度空間理論目的是模擬圖像數(shù)據(jù)的多尺度特征慌植。
高斯卷積核是實(shí)現(xiàn)尺度變換的唯一線性核甚牲，于是一幅二維圖像的尺度空間定義為：
其中 G(x,y,σ) 是尺度可變高斯函數(shù)。
（x蝶柿，y）是空間坐標(biāo)丈钙，是尺度坐標(biāo)。σ大小決定圖像的平滑程度交汤，大尺度對(duì)應(yīng)圖像的概貌特征雏赦，小尺度對(duì)應(yīng)圖像的細(xì)節(jié)特征。大的σ值對(duì)應(yīng)粗糙尺度(低分辨率)芙扎，反之星岗，對(duì)應(yīng)精細(xì)尺度(高分辨率)。為了有效的在尺度空間檢測(cè)到穩(wěn)定的關(guān)鍵點(diǎn)戒洼，提出了高斯差分尺度空間（DOG scale-space）俏橘。利用不同尺度的高斯差分核與圖像卷積生成。
圖像金字塔的建立：對(duì)于一幅圖像I,建立其在不同尺度(scale)的圖像圈浇，也成為子八度（octave）寥掐，這是為了scale-invariant，也就是在任何尺度都能夠有對(duì)應(yīng)的特征點(diǎn)磷蜀，第一個(gè)子八度的scale為原圖大小召耘，后面每個(gè)octave為上一個(gè)octave降采樣的結(jié)果，即原圖的1/4（長(zhǎng)寬分別減半）褐隆，構(gòu)成下一個(gè)子八度（高一層金字塔）污它。
-
LoG近似DoG找到關(guān)鍵點(diǎn)<檢測(cè)DOG尺度空間極值點(diǎn)>
為了尋找尺度空間的極值點(diǎn)，每一個(gè)采樣點(diǎn)要和它所有的相鄰點(diǎn)比較妓灌，看其是否比它的圖像域和尺度域的相鄰點(diǎn)大或者小轨蛤。如圖所示，中間的檢測(cè)點(diǎn)和它同尺度的8個(gè)相鄰點(diǎn)和上下相鄰尺度對(duì)應(yīng)的9×2個(gè)點(diǎn)共26個(gè)點(diǎn)比較虫埂，以確保在尺度空間和二維圖像空間都檢測(cè)到極值點(diǎn)祥山。 一個(gè)點(diǎn)如果在DOG尺度空間本層以及上下兩層的26個(gè)領(lǐng)域中是最大或最小值時(shí)，就認(rèn)為該點(diǎn)是圖像在該尺度下的一個(gè)特征點(diǎn),如圖所示掉伏。
使用Laplacian of Gaussian能夠很好地找到找到圖像中的興趣點(diǎn)缝呕，但是需要大量的計(jì)算量，所以使用Difference of Gaussian圖像的極大極小值近似尋找特征點(diǎn).DOG算子計(jì)算簡(jiǎn)單斧散，是尺度歸一化的LoG算子的近似,極值點(diǎn)檢測(cè)用的Non-Maximal Suppression.有關(guān)DOG尋找特征點(diǎn)的介紹及方法詳見(jiàn).
-
除去不好的特征點(diǎn)
這一步本質(zhì)上要去掉DoG局部曲率非常不對(duì)稱的像素供常。
-
給特征點(diǎn)賦值一個(gè)128維方向參數(shù)
上一步中確定了每幅圖中的特征點(diǎn)，現(xiàn)在利用關(guān)鍵點(diǎn)鄰域像素的梯度方向分布特性為每個(gè)關(guān)鍵點(diǎn)指定方向參數(shù)鸡捐，使算子具備旋轉(zhuǎn)不變性栈暇。
為(x,y)處梯度的模值和方向公式。其中L所用的尺度為每個(gè)關(guān)鍵點(diǎn)各自所在的尺度箍镜。至此源祈，圖像的關(guān)鍵點(diǎn)已經(jīng)檢測(cè)完畢煎源，每個(gè)關(guān)鍵點(diǎn)有三個(gè)信息：位置，所處尺度香缺、方向手销，由此可以確定一個(gè)SIFT特征區(qū)域。
梯度直方圖的范圍是0～360度图张，其中每10度一個(gè)柱锋拖，總共36個(gè)柱。隨著距中心點(diǎn)越遠(yuǎn)的領(lǐng)域其對(duì)直方圖的貢獻(xiàn)也響應(yīng)減小.Lowe論文中還提到要使用高斯函數(shù)對(duì)直方圖進(jìn)行平滑祸轮，減少突變的影響兽埃。
在實(shí)際計(jì)算時(shí)，我們?cè)谝躁P(guān)鍵點(diǎn)為中心的鄰域窗口內(nèi)采樣倔撞，并用直方圖統(tǒng)計(jì)鄰域像素的梯度方向讲仰。梯度直方圖的范圍是0～360度，其中每45度一個(gè)柱痪蝇，總共8個(gè)柱, 或者每10度一個(gè)柱鄙陡，總共36個(gè)柱。Lowe論文中還提到要使用高斯函數(shù)對(duì)直方圖進(jìn)行平滑躏啰，減少突變的影響趁矾。直方圖的峰值則代表了該關(guān)鍵點(diǎn)處鄰域梯度的主方向，即作為該關(guān)鍵點(diǎn)的方向给僵。
-
關(guān)鍵點(diǎn)描述子的生成
首先將坐標(biāo)軸旋轉(zhuǎn)為關(guān)鍵點(diǎn)的方向毫捣，以確保旋轉(zhuǎn)不變性。以關(guān)鍵點(diǎn)為中心取8×8的窗口帝际。
圖左部分的中央為當(dāng)前關(guān)鍵點(diǎn)的位置蔓同，每個(gè)小格代表關(guān)鍵點(diǎn)鄰域所在尺度空間的一個(gè)像素，利用公式求得每個(gè)像素的梯度幅值與梯度方向蹲诀，箭頭方向代表該像素的梯度方向斑粱，箭頭長(zhǎng)度代表梯度模值，然后用高斯窗口對(duì)其進(jìn)行加權(quán)運(yùn)算脯爪。
圖中藍(lán)色的圈代表高斯加權(quán)的范圍（越靠近關(guān)鍵點(diǎn)的像素梯度方向信息貢獻(xiàn)越大）则北。然后在每4×4的小塊上計(jì)算8個(gè)方向的梯度方向直方圖，繪制每個(gè)梯度方向的累加值痕慢，即可形成一個(gè)種子點(diǎn)尚揣，如圖右部分示。此圖中一個(gè)關(guān)鍵點(diǎn)由2×2共4個(gè)種子點(diǎn)組成掖举，每個(gè)種子點(diǎn)有8個(gè)方向向量信息快骗。這種鄰域方向性信息聯(lián)合的思想增強(qiáng)了算法抗噪聲的能力，同時(shí)對(duì)于含有定位誤差的特征匹配也提供了較好的容錯(cuò)性。
計(jì)算keypoint周?chē)?6*16的window中每一個(gè)像素的梯度方篮，而且使用高斯下降函數(shù)降低遠(yuǎn)離中心的權(quán)重思灌。
這樣就可以對(duì)每個(gè)feature形成一個(gè)448=128維的描述子，每一維都可以表示4*4個(gè)格子中一個(gè)的scale/orientation. 將這個(gè)向量歸一化之后恭取，就進(jìn)一步去除了光照的影響。
-
根據(jù)SIFT進(jìn)行Match
生成了A熄守、B兩幅圖的描述子蜈垮，（分別是k1128維和k2128維），就將兩圖中各個(gè)scale（所有scale）的描述子進(jìn)行匹配裕照，匹配上128維即可表示兩個(gè)特征點(diǎn)match上了攒发。
實(shí)際計(jì)算過(guò)程中，為了增強(qiáng)匹配的穩(wěn)健性晋南，Lowe建議對(duì)每個(gè)關(guān)鍵點(diǎn)使用4×4共16個(gè)種子點(diǎn)來(lái)描述惠猿，這樣對(duì)于一個(gè)關(guān)鍵點(diǎn)就可以產(chǎn)生128個(gè)數(shù)據(jù)，即最終形成128維的SIFT特征向量负间。此時(shí)SIFT特征向量已經(jīng)去除了尺度變化偶妖、旋轉(zhuǎn)等幾何變形因素的影響，再繼續(xù)將特征向量的長(zhǎng)度歸一化政溃，則可以進(jìn)一步去除光照變化的影響趾访。 當(dāng)兩幅圖像的SIFT特征向量生成后，下一步我們采用關(guān)鍵點(diǎn)特征向量的歐式距離來(lái)作為兩幅圖像中關(guān)鍵點(diǎn)的相似性判定度量董虱。取圖像1中的某個(gè)關(guān)鍵點(diǎn)扼鞋，并找出其與圖像2中歐式距離最近的前兩個(gè)關(guān)鍵點(diǎn)，在這兩個(gè)關(guān)鍵點(diǎn)中愤诱，如果最近的距離除以次近的距離少于某個(gè)比例閾值云头，則接受這一對(duì)匹配點(diǎn)。降低這個(gè)比例閾值淫半，SIFT匹配點(diǎn)數(shù)目會(huì)減少溃槐，但更加穩(wěn)定。為了排除因?yàn)閳D像遮擋和背景混亂而產(chǎn)生的無(wú)匹配關(guān)系的關(guān)鍵點(diǎn),Lowe提出了比較最近鄰距離與次近鄰距離的方法,距離比率ratio小于某個(gè)閾值的認(rèn)為是正確匹配撮慨。因?yàn)閷?duì)于錯(cuò)誤匹配,由于特征空間的高維性,相似的距離可能有大量其他的錯(cuò)誤匹配,從而它的ratio值比較高竿痰。Lowe推薦ratio的閾值為0.8。但作者對(duì)大量任意存在尺度砌溺、旋轉(zhuǎn)和亮度變化的兩幅圖片進(jìn)行匹配影涉，結(jié)果表明ratio取值在0. 4~0. 6之間最佳，小于0. 4的很少有匹配點(diǎn)规伐，大于0. 6的則存在大量錯(cuò)誤匹配點(diǎn)蟹倾。(如果這個(gè)地方你要改進(jìn)，最好給出一個(gè)匹配率和ration之間的關(guān)系圖，這樣才有說(shuō)服力)作者建議ratio的取值原則如下:
ratio=0. 4 對(duì)于準(zhǔn)確度要求高的匹配鲜棠；
ratio=0. 6 對(duì)于匹配點(diǎn)數(shù)目要求比較多的匹配肌厨；
ratio=0. 5 一般情況下。
也可按如下原則:當(dāng)最近鄰距離<200時(shí)ratio=0. 6豁陆，反之ratio=0. 4柑爸。ratio的取值策略能排分錯(cuò)誤匹配點(diǎn)。
當(dāng)兩幅圖像的SIFT特征向量生成后盒音，下一步我們采用關(guān)鍵點(diǎn)特征向量的歐式距離來(lái)作為兩幅圖像中關(guān)鍵點(diǎn)的相似性判定度量表鳍。取圖像1中的某個(gè)關(guān)鍵點(diǎn)，并找出其與圖像2中歐式距離最近的前兩個(gè)關(guān)鍵點(diǎn)祥诽，在這兩個(gè)關(guān)鍵點(diǎn)中譬圣，如果最近的距離除以次近的距離少于某個(gè)比例閾值，則接受這一對(duì)匹配點(diǎn)雄坪。降低這個(gè)比例閾值厘熟，SIFT匹配點(diǎn)數(shù)目會(huì)減少，但更加穩(wěn)定维哈。
53. kd-tree
K-D樹(shù)的構(gòu)造
- 超平面的選擇：采用最大方差法绳姨，計(jì)算出每個(gè)維度上的方差，取最大方差所在維度為垂直于超平面的方向軸（不是作為超平面而是作為方向軸）笨农。因?yàn)榉讲钤酱缶屠拢f(shuō)明數(shù)據(jù)點(diǎn)在該維度上越為分散，從而分割的效果越好谒亦。
- 節(jié)點(diǎn)的選擇：中值選擇法竭宰，在數(shù)據(jù)結(jié)構(gòu)的知識(shí)中已知平衡二叉樹(shù)的平均查詢效率最好，所以在選擇各子樹(shù)根節(jié)點(diǎn)時(shí)應(yīng)該盡量保證分割后的樹(shù)仍然能達(dá)到或接近平衡狀態(tài)份招。將方向軸上的數(shù)據(jù)進(jìn)行排序切揭，取中值點(diǎn)為子樹(shù)根節(jié)點(diǎn)進(jìn)行超平面分割。
- 對(duì)左右子樹(shù)重復(fù)以上過(guò)程锁摔，直至樹(shù)建立完成廓旬。
算法原理
- 向下遍歷：在遍歷KD樹(shù)時(shí)，根據(jù)每個(gè)節(jié)點(diǎn)的方向軸數(shù)據(jù)來(lái)確定遍歷順序谐腰。從根節(jié)點(diǎn)開(kāi)始孕豹，將查找點(diǎn)與根節(jié)點(diǎn)方向軸上的數(shù)據(jù)進(jìn)行比較，小于則進(jìn)入左子樹(shù)查找十气，反之則進(jìn)入右子樹(shù)查找励背。重復(fù)此過(guò)程直到遍歷到葉子節(jié)點(diǎn)。完成向下遍歷操作砸西。
- 向上回溯：顯然叶眉，遍歷得到的點(diǎn)很大可能不是最近點(diǎn)址儒，僅僅是處于同一子空間而已，既無(wú)法保證其距離小于查找點(diǎn)到葉子節(jié)點(diǎn)父節(jié)點(diǎn)的距離衅疙，也無(wú)法保證其距離小于查找點(diǎn)到另一子空間中節(jié)點(diǎn)的距離莲趣。所以要進(jìn)行回溯。首先饱溢，向上回溯到葉子節(jié)點(diǎn)的父節(jié)點(diǎn)喧伞，計(jì)算查找點(diǎn)到該父節(jié)點(diǎn)的距離，若小于之前距離則把該父節(jié)點(diǎn)當(dāng)作最鄰近點(diǎn)绩郎，并更新最短距離絮识。反之則不更新。然后嗽上，以查找點(diǎn)為圓心，到查詢到的鄰近點(diǎn)距離為半徑（此時(shí)可能是葉子節(jié)點(diǎn)也可能是葉子節(jié)點(diǎn)的父節(jié)點(diǎn)）進(jìn)行畫(huà)圓熄攘。觀察是否與葉子節(jié)點(diǎn)的父節(jié)點(diǎn)另一子空間相交兽愤。若相交，則進(jìn)入另一子空間繼續(xù)查詢（重復(fù)遍歷和回溯操作）挪圾。若不相交浅萧，則繼續(xù)回溯并重復(fù)該操作，直至回溯到根節(jié)點(diǎn)方止哲思。
向下遍歷：
1.先從（7,2）查找洼畅，x=7為超平面方向軸，因?yàn)閤=2 < x=7,所以遍歷到左空間中的（5,4）節(jié)點(diǎn)棚赔。
2.在（5帝簇，4）點(diǎn)上查找時(shí)，y = 4為超平面的方向軸靠益，因?yàn)橛捎诓檎尹c(diǎn)為y值為4.5丧肴，4.5>4，因此進(jìn)入右子空間查找到（4,7）胧后。
3.形成搜索路徑<（7,2）芋浮，（5,4），（4,7）>壳快，戎较铩（4,7）為當(dāng)前最近鄰點(diǎn)，計(jì)算其與目標(biāo)查找點(diǎn)的距離為3.202眶痰。
向上回溯：
1.然后回溯到父節(jié)點(diǎn)（5,4）瘤旨，計(jì)算其與查找點(diǎn)之間的距離為3.041。3.041<3.202凛驮，所以最鄰近點(diǎn)更新為（5裆站，4），最短距離更新為3.041。
2.以（2宏胯，4.5）為圓心羽嫡，以3.041為半徑作圓，如圖所示肩袍『伎茫可見(jiàn)該圓和y = 4超平面相交，所以需要進(jìn)入（5,4）左子空間進(jìn)行查找氛赐。此時(shí)需將（2,3）節(jié)點(diǎn)加入搜索路徑中得<（7,2）魂爪，（2,3）>。
3.回溯至（2,3）葉子節(jié)點(diǎn)艰管，（2,3）距離（2,4.5）比（5,4）要近滓侍，所以最近鄰點(diǎn)更新為（2锥累，3）虎囚，最近距離更新為1.5较性。
4.回溯至根節(jié)點(diǎn)（7,2）货抄，以（2,4.5）為圓心1.5為半徑作圓吕粗，并不和x = 7分割超平面相交试读。
5.至此锨咙，搜索路徑回溯完嘶炭。返回最近鄰點(diǎn)（2,3）裂逐，最近距離1.5歹鱼。
54. 深度與視差轉(zhuǎn)換關(guān)系：
depth = (fx * baseline) / disparity
深度方向的測(cè)量誤差與測(cè)量距離的平方成正比，而X/Y方向的誤差與距離成正比卜高。
隨著測(cè)量距離的增加弥姻，深度方向的誤差比X/Y方向更難控制。
55. ORB（Oriented FAST and Rotated BRIEF）優(yōu)點(diǎn)
一定的尺度不變性：利用圖像金子塔實(shí)現(xiàn)掺涛，由于金字塔層數(shù)有限蚁阳，因此只能在一定范圍保證尺度的不變性。
旋轉(zhuǎn)不變性：首先利用灰度質(zhì)心法計(jì)算出特征的方向鸽照，然后計(jì)算旋轉(zhuǎn)后的BRIEF描述子螺捐。
抗噪能力：計(jì)算BRIEF的時(shí)候不是使用一個(gè)點(diǎn)的灰度，而是使用了點(diǎn)周?chē)?×5區(qū)域的灰度矮燎。
應(yīng)該也有一定的光照不變性：因?yàn)镕AST提取的時(shí)候是比較灰度定血，rBRIEF的計(jì)算也是比較灰度。
速度快：使用了FAST角點(diǎn)诞外，BRIEF描述子澜沟，二者均很快。速度是SIFT的100倍峡谊，SURF的10倍茫虽。
56. ORB特征提取的流程
-
提取流程概覽
l 構(gòu)造金字塔
l 提取FAST角點(diǎn)
l 利用灰度質(zhì)心法刊苍，計(jì)算旋轉(zhuǎn)角度
l 計(jì)算旋轉(zhuǎn)后的BRIEF描述子
-
提取FAST角點(diǎn)
2.1 如何分配每一層提取的特征點(diǎn)數(shù)量。
金字塔層數(shù)越高濒析，圖像的面積越小正什，所能提取到的特征數(shù)量就越小『判樱基于這個(gè)原理婴氮，我們可以按照面積將特征點(diǎn)均攤到金字塔每層的圖像上。我們假設(shè)第0層圖像的寬為W盾致，長(zhǎng)為 L 主经，縮放因子s（這里的0<S<1）。那么整個(gè)金字塔總的面積為
2.2 什么是FAST角點(diǎn)庭惜，如何提日肿ぁ？
FAST角點(diǎn)护赊，通過(guò)對(duì)比中心與周?chē)c(diǎn)（半徑為3的圓上的點(diǎn)）灰度的差別鉴腻，即可確定是否為關(guān)鍵點(diǎn)，速度賊快百揭。
具體的步驟為：
像素p ，其灰度為Ip ;
設(shè)置一個(gè)閾值T ,比如Ip的20%蜓席。
以 p為圓心器一，選擇半徑為3的圓上的16個(gè)像素點(diǎn)。
4）如果圓上面有連續(xù)的N個(gè)點(diǎn)的亮度大于閾值 Ip+T或者小于Ip-T厨内，則判定此點(diǎn)為FAST角點(diǎn)祈秕。通常N的取值有FAST-9，F(xiàn)AST-11雏胃，F(xiàn)AST-12最常見(jiàn)请毛。對(duì)于FAST-12有高效的檢測(cè)方法，首先檢測(cè)12點(diǎn)瞭亮、3點(diǎn)方仿、6點(diǎn)和9點(diǎn)鐘的像素（1,5,9,13），如果至少有3個(gè)是成功的统翩，才有可能是角點(diǎn)仙蚜，再去進(jìn)一步的檢測(cè)，否則就直接pass厂汗。
按照上述步驟對(duì)圖像上每個(gè)像素處理一遍委粉，可以獲取大量的FAST角點(diǎn)。那娶桦，F(xiàn)AST角點(diǎn)容易出現(xiàn)扎堆現(xiàn)象贾节，要用非極大值抑制再處理一遍（Non-maximal suppression）汁汗。
-
Oriented FAST，旋轉(zhuǎn)角度計(jì)算
ORB計(jì)算角度也比較簡(jiǎn)單栗涂，首先一個(gè)圓形區(qū)域的灰度質(zhì)心知牌，連接質(zhì)心和圓心形成一個(gè)向量，這個(gè)向量的角度就是角點(diǎn)的角度戴差。圓的半徑取為15送爸，因?yàn)檎麄€(gè)patch一般取的是31×31的。
注意暖释，現(xiàn)在我們已經(jīng)把坐標(biāo)系的圓心設(shè)在了關(guān)鍵點(diǎn)上袭厂，那么灰度質(zhì)心為
-
計(jì)算Rotation-Aware BRIEF， rBRIEF
4.1 BRIEF描述子
BRIEF是一個(gè)二進(jìn)制的描述子球匕，計(jì)算和匹配的速度都很快纹磺。
4.2 Steered BRIEF
BRIEF描述子是沒(méi)有考慮旋轉(zhuǎn)不變性的，Steered BRIEF根據(jù)Oriented FAST計(jì)算出的角度亮曹，把原始的256個(gè)點(diǎn)對(duì)的坐標(biāo)旋轉(zhuǎn)之后橄杨，再取灰度。從而實(shí)現(xiàn)了旋轉(zhuǎn)不變性照卦。
4.3 Rotation-Aware BRIEF
上述過(guò)程雖然解決了旋轉(zhuǎn)問(wèn)題式矫，但是也造成了描述子一些性能的下降。
這個(gè)問(wèn)題的解決是使用了學(xué)習(xí)的方法役耕，利用了大量的數(shù)據(jù)采转，選擇出了效果最好的256個(gè)點(diǎn)對(duì)位置。以后每次提取特征點(diǎn)都使用這256個(gè)位置瞬痘。
4.4 抗噪能力的提高
在計(jì)算BRIEF描述子的時(shí)候故慈，ORB使用的不是每個(gè)點(diǎn)的灰度，而是周?chē)?×5的patch的灰度框全。因此起到了低通濾過(guò)的效果察绷，對(duì)噪聲有更強(qiáng)的魯棒性。
-
ORB-SLAM對(duì)ORB特征的改進(jìn)
ORBSLAM中并沒(méi)有使用OpenCV的實(shí)現(xiàn)津辩，因?yàn)镺penCV的版本提取的ORB特征過(guò)于集中拆撼，會(huì)出現(xiàn)扎堆的現(xiàn)象。這會(huì)降低SLAM的精度喘沿，對(duì)于閉環(huán)來(lái)說(shuō)情萤，也會(huì)降低一幅圖像上的信息量。ORB-SLAM中的實(shí)現(xiàn)提高了特征分布的均勻性摹恨。
最簡(jiǎn)單的一種方法是把圖像劃分成若干小格子筋岛，每個(gè)小格子里面保留質(zhì)量最好的n個(gè)特征點(diǎn)。這種方法看似不錯(cuò)晒哄，實(shí)際上會(huì)有一些問(wèn)題睁宰。當(dāng)有些格子里面能夠提取的數(shù)量不足n個(gè)的時(shí)候（無(wú)紋理區(qū)域）肪获，整幅圖上提取的特征總量就達(dá)不到我們想要的數(shù)量。`
ORB-SLAM中的實(shí)現(xiàn)就解決了這么一個(gè)問(wèn)題柒傻，當(dāng)一個(gè)格子提取不到FAST點(diǎn)的時(shí)候孝赫，自動(dòng)降低閾值。ORB-SLAM主要改進(jìn)了FAST角點(diǎn)提取步驟红符。
對(duì)于金字塔的每一層青柄。
劃分格子，格子的大小為30×30pixels
單獨(dú)對(duì)每個(gè)格子提取FAST角點(diǎn)预侯，如果提取不到點(diǎn)致开，就降低FAST閾值。這樣保證紋理較弱的區(qū)域也能提取到一些FAST角點(diǎn)萎馅。這一步可以提取大量的FAST點(diǎn)双戳。
基于四叉樹(shù)，均勻的選取
個(gè)FAST點(diǎn)糜芳。
上述步驟中飒货，基于四叉樹(shù)的方法有點(diǎn)復(fù)雜，下面分析一下峭竣。
如果圖片的寬度比較寬塘辅，就先把分成左右w/h份。一般的640×480的圖像開(kāi)始的時(shí)候只有一個(gè)node皆撩。
如果node里面的點(diǎn)數(shù)>1扣墩，把每個(gè)node分成四個(gè)node，如果node里面的特征點(diǎn)為空毅访，就不要了，刪掉盘榨。
新分的node的點(diǎn)數(shù)>1喻粹，就再分裂成4個(gè)node。如此草巡，一直分裂守呜。
終止條件為：node的總數(shù)量無(wú)法再進(jìn)行分裂。
然后從每個(gè)node里面選擇一個(gè)質(zhì)量最好的FAST點(diǎn)山憨。
56. 最小二乘法的推導(dǎo)
https://blog.csdn.net/u011026329/article/details/79183114
最小二乘法和梯度下降法有哪些區(qū)別查乒？
迭代法，即在每一步update未知量逐漸逼近解郁竟，可以用于各種各樣的問(wèn)題（包括最小二乘）玛迄，比如求的不是誤差的最小平方和而是最小立方和。
梯度下降是迭代法的一種棚亩，可以用于求解最小二乘問(wèn)題（線性和非線性都可以）蓖议。高斯-牛頓法是另一種經(jīng)常用于求解非線性最小二乘的迭代法（一定程度上可視為標(biāo)準(zhǔn)非線性最小二乘求解方法）虏杰。
還有一種叫做Levenberg-Marquardt的迭代法用于求解非線性最小二乘問(wèn)題，就結(jié)合了梯度下降和高斯-牛頓法勒虾。
然后Levenberg-Marquardt方法的好處就是在于可以調(diào)節(jié):
如果下降太快纺阔，使用較小的λ，使之更接近高斯牛頓法
如果下降太慢修然，使用較大的λ笛钝，使之更接近梯度下降法
57. 深拷貝與淺拷貝
-
在未定義顯示拷貝構(gòu)造函數(shù)的情況下，系統(tǒng)會(huì)調(diào)用默認(rèn)的拷貝函數(shù)——即淺拷貝愕宋，它能夠完成成員的一一復(fù)制玻靡。當(dāng)數(shù)據(jù)成員中沒(méi)有指針時(shí)，淺拷貝是可行的掏婶；但當(dāng)數(shù)據(jù)成員中有指針時(shí)啃奴，如果采用簡(jiǎn)單的淺拷貝，則兩類(lèi)中的兩個(gè)指針將指向同一個(gè)地址雄妥，當(dāng)對(duì)象快結(jié)束時(shí)最蕾，會(huì)調(diào)用兩次析構(gòu)函數(shù)，而導(dǎo)致指針懸掛現(xiàn)象老厌，所以瘟则，此時(shí)，必須采用深拷貝枝秤。
深拷貝與淺拷貝的區(qū)別就在于深拷貝會(huì)在堆內(nèi)存中另外申請(qǐng)空間來(lái)儲(chǔ)存數(shù)據(jù)醋拧，從而也就解決了指針懸掛的問(wèn)題。簡(jiǎn)而言之淀弹，當(dāng)數(shù)據(jù)成員中有指針時(shí)丹壕，必須要用深拷貝。
帶實(shí)例的解釋
默認(rèn)的拷貝構(gòu)造函數(shù)是淺拷貝
淺拷貝就是對(duì)象的數(shù)據(jù)成員之間的簡(jiǎn)單賦值薇溃，如你設(shè)計(jì)了一個(gè)沒(méi)有類(lèi)而沒(méi)有提供它的拷貝構(gòu)造函數(shù)菌赖，當(dāng)用該類(lèi)的一個(gè)對(duì)象去給令一個(gè)對(duì)象賦值時(shí)所執(zhí)行的過(guò)程就是淺拷貝，如：
class A
{
public:
A(int _data) : data(_data){}
A(){}
private:
int data;
};
int main()
{
A a(5), b = a; // 僅僅是數(shù)據(jù)成員之間的賦值
}
這一句b = a;就是淺拷貝沐序，執(zhí)行完這句后b.data = 5;
如果對(duì)象中沒(méi)有其他的資源（如：堆琉用，文件，系統(tǒng)資源等）策幼，則深拷貝和淺拷貝沒(méi)有什么區(qū)別邑时，
但當(dāng)對(duì)象中有這些資源時(shí)，例子：
class A
{
public:
A(int _size) : size(_size)
{
data = new int[size];
} // 假如其中有一段動(dòng)態(tài)分配的內(nèi)存
A(){};
~A()
{
delete [] data;
} // 析構(gòu)時(shí)釋放資源
private:
int* data;
int size;
}
int main()
{
A a(5), b = a; // 注意這一句
}
這里的b = a會(huì)造成未定義行為特姐，因?yàn)轭?lèi)A中的復(fù)制構(gòu)造函數(shù)是編譯器生成的晶丘，所以b = a執(zhí)行的是一個(gè)淺拷貝過(guò)程。我說(shuō)過(guò)淺拷貝是對(duì)象數(shù)據(jù)之間的簡(jiǎn)單賦值唐含，比如：
b.size = a.size;
b.data = a.data; // Oops!
這里b的指針data和a的指針指向了堆上的同一塊內(nèi)存铣口，a和b析構(gòu)時(shí)滤钱，b先把其data指向的動(dòng)態(tài)分配的內(nèi)存釋放了一次，而后a析構(gòu)時(shí)又將這塊已經(jīng)被釋放過(guò)的內(nèi)存再釋放一次脑题。對(duì)同一塊動(dòng)態(tài)內(nèi)存執(zhí)行2次以上釋放的結(jié)果是未定義的件缸，所以這將導(dǎo)致內(nèi)存泄露或程序崩潰。
所以這里就需要深拷貝來(lái)解決這個(gè)問(wèn)題叔遂，深拷貝指的就是當(dāng)拷貝對(duì)象中有對(duì)其他資源（如堆他炊、文件、系統(tǒng)等）的引用時(shí)（引用可以是指針或引用）時(shí)已艰，對(duì)象的另開(kāi)辟一塊新的資源痊末，而不再對(duì)拷貝對(duì)象中有對(duì)其他資源的引用的指針或引用進(jìn)行單純的賦值。如：
class A
{
public:
A(int _size) : size(_size)
{
data = new int[size];
} // 假如其中有一段動(dòng)態(tài)分配的內(nèi)存
A(){};
A(const A& _A) : size(_A.size)
{
data = new int[size];
} // 深拷貝
~A()
{
delete [] data;
} // 析構(gòu)時(shí)釋放資源
private:
int* data;
int size;
}
int main()
{
A a(5), b = a; // 這次就沒(méi)問(wèn)題了
}
總結(jié)：深拷貝和淺拷貝的區(qū)別是在對(duì)象狀態(tài)中包含其它對(duì)象的引用的時(shí)候哩掺，當(dāng)拷貝一個(gè)對(duì)象時(shí)凿叠，如果需要拷貝這個(gè)對(duì)象引用的對(duì)象，則是深拷貝嚼吞，否則是淺拷貝盒件。
59. python中哪些是可變數(shù)據(jù)類(lèi)型，哪些是不可變數(shù)據(jù)類(lèi)型舱禽。 可變數(shù)據(jù)類(lèi)型：列表list和字典dict炒刁；不可變數(shù)據(jù)類(lèi)型：整型int、浮點(diǎn)型float誊稚、字符串型string和元組tuple翔始。
60. python深拷貝和淺拷貝的區(qū)別? python的等號(hào)和copy有什么區(qū)別?
61. 值傳遞，地址傳遞里伯，引用傳遞的聯(lián)系和區(qū)別
62. 快排和堆排的優(yōu)缺點(diǎn)和應(yīng)用場(chǎng)景
63. 實(shí)現(xiàn)歸并排序
#include <iostream>
#include <vector>
using namespace std;
vector<int> merge(const vector<int> &L,const vector<int> &R){
vector<int> res={};
int i=0;
int j=0;
while(i<L.size() and j <R.size()){
if (L[i] <= R[j]){
res.push_back(L[i]);
i++;
}else{
res.push_back(R[j]);
j++;
}
}
while(i<L.size()){
res.push_back(L[i]);
i++;
};
while(j<R.size()){
res.push_back(R[j]);
j++;
};
return res;
}
vector<int> MergeSort(vector<int> &arr){
int l = arr.size();
if(l<2){ return arr;};
int mid = l/2;
vector<int> L={};
vector<int> R={};
L.reserve(mid);
for(int i=0;i<mid;i++){
L.push_back(arr[i]);
}
for(int j=mid;j<l;j++){
R.push_back(arr[j]);
}
L = MergeSort(L);
R = MergeSort(R);
return merge(L,R);
}
int main() {
vector<int> array = {5,3,0,6,1,4},res;
res = MergeSort(array);
cout << "after Merge Sort..." <<endl;
for(auto i:res){
cout << i<<" ";
}
return 0;
}
64. 實(shí)現(xiàn)快速排序
#include <iostream>
#include <vector>
using namespace std;
//This a quickSort Algorithm. The main thought is divide and conquer.
void swap(vector<int> &arr, int i, int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
int partition(vector<int>&arr,int low,int high){ //conquer
int i = low-1;
int pivot = arr[high];
for(int j=low;j<high;j++){
if(arr[j] <= pivot) { //find the number which is smaller than pivot,and we can confirm the true place of pivot(arr[high]).
i++;
swap(arr, i, j);
}
}
swap(arr,i+1,high);
return i+1;
}
void quickSort(vector<int> &arr,int low,int high){
if (low<high){
int pi = partition(arr,low,high);
quickSort(arr,low,pi-1); //divide
quickSort(arr,pi+1,high);
}
}
int main() {
vector<int> arr = {1,2,4,8,12,1,3,9,2,5,7,8,122,654,7654,211};
int n = arr.size();
cout << "before quick sort..." <<endl;
for(auto v: arr){
cout << v <<" ";
};
cout << endl;
quickSort(arr,0,n-1);
cout << "After quick sort..." <<endl;
for(auto v: arr){
cout << v <<" ";
};
return 0;
}
65. C++中sort底層是什么城瞎，是否穩(wěn)定，還有哪些穩(wěn)定排序算法
66. 項(xiàng)目用了哪些多線程技術(shù)疾瓮？
67. 光流算法原理
68. C++編譯過(guò)程
69. C++里面vector脖镀、list、deque的區(qū)別
70. topK要求nlogk
71. C++中什么是左值什么是右值
72. python 元組和列表的區(qū)別
73. python 當(dāng)中的with說(shuō)一下
74. linux基本操作：
l 怎么設(shè)置環(huán)境變量: .bashrc爷贫，然后source一下
l 統(tǒng)計(jì)當(dāng)前文件夾下面.jpg文件的數(shù)量：ls -l | grep '.*.jpg' | wc -l
l 計(jì)算當(dāng)前文件夾的大腥先弧：du -sh
75. 描述一下隨機(jī)森林
76. 隨機(jī)森林主要用于解決什么類(lèi)的問(wèn)題补憾？
77. 實(shí)習(xí)經(jīng)歷中提到了數(shù)據(jù)清洗漫萄，講解一下清洗的工作是怎么做的？
78. 梯度爆炸和梯度消失怎么解決
造成梯度消失和梯度爆炸問(wèn)題是網(wǎng)絡(luò)太深盈匾，網(wǎng)絡(luò)權(quán)值更新不穩(wěn)定造成的腾务，本質(zhì)上是因?yàn)樘荻确聪騻鞑ブ械倪B乘效應(yīng)。另外一個(gè)原因是當(dāng)激活函數(shù)使用 sigmoid 時(shí)削饵，梯度消失問(wèn)題更容易發(fā)生岩瘦，因此可以考慮的解決方法如下：
\1. 壓縮模型層數(shù)
\2. 改用其他的激活函數(shù)如 ReLU
\3. 使用 BN 層
\4. 使用類(lèi)似ResNet的shortcut連接結(jié)構(gòu)
79. C++程序編譯過(guò)程
需要編譯和鏈接
編譯就是把文本形式源代碼翻譯為機(jī)器語(yǔ)言形式的目標(biāo)文件的過(guò)程未巫。
鏈接是把目標(biāo)文件、操作系統(tǒng)的啟動(dòng)代碼和用到的庫(kù)文件進(jìn)行組織启昧，形成最終生成可執(zhí)行代碼的過(guò)程叙凡。
從圖上可以看到，整個(gè)代碼的編譯過(guò)程分為編譯和鏈接兩個(gè)過(guò)程密末，編譯對(duì)應(yīng)圖中的大括號(hào)括起的部分握爷，其余則為鏈接過(guò)程。
-
編譯過(guò)程
編譯過(guò)程又可以分成兩個(gè)階段：編譯和匯編严里。
編譯
編譯是讀取源程序（字符流）新啼，對(duì)之進(jìn)行詞法和語(yǔ)法的分析，將高級(jí)語(yǔ)言指令轉(zhuǎn)換為功能等效的匯編代碼刹碾，源文件的編譯過(guò)程包含兩個(gè)主要階段：
編譯預(yù)處理
讀取c源程序燥撞，對(duì)其中的偽指令（以# 開(kāi)頭的指令）和特殊符號(hào)進(jìn)行處理。
偽指令主要包括以下四個(gè)方面：
-
鏈接過(guò)程
由匯編程序生成的目標(biāo)文件并不能立即就被執(zhí)行迷帜，其中可能還有許多沒(méi)有解決的問(wèn)題物舒。
例如，某個(gè)源文件中的函數(shù)可能引用了另一個(gè)源文件中定義的某個(gè)符號(hào)（如變量或者函數(shù)調(diào)用等）瞬矩；在程序中可能調(diào)用了某個(gè)庫(kù)文件中的函數(shù)茶鉴，等等。所有的這些問(wèn)題景用，都需要經(jīng)鏈接程序的處理方能得以解決涵叮。
鏈接程序的主要工作就是將有關(guān)的目標(biāo)文件彼此相連接，也即將在一個(gè)文件中引用的符號(hào)同該符號(hào)在另外一個(gè)文件中的定義連接起來(lái)伞插，使得所有的這些目標(biāo)文件成為一個(gè)能夠被操作系統(tǒng)裝入執(zhí)行的統(tǒng)一整體割粮。
根據(jù)開(kāi)發(fā)人員指定的同庫(kù)函數(shù)的鏈接方式的不同，鏈接處理可分為兩種：
- 靜態(tài)鏈接
在這種鏈接方式下媚污，函數(shù)的代碼將從其所在的靜態(tài)鏈接庫(kù)中被拷貝到最終的可執(zhí)行程序中舀瓢。這樣該程序在被執(zhí)行時(shí)這些代碼將被裝入到該進(jìn)程的虛擬地址空間中。靜態(tài)鏈接庫(kù)實(shí)際上是一個(gè)目標(biāo)文件的集合耗美，其中的每個(gè)文件含有庫(kù)中的一個(gè)或者一組相關(guān)函數(shù)的代碼京髓。
- 動(dòng)態(tài)鏈接
在此種方式下，函數(shù)的代碼被放到稱作是動(dòng)態(tài)鏈接庫(kù)或共享對(duì)象的某個(gè)目標(biāo)文件中商架。鏈接程序此時(shí)所作的只是在最終的可執(zhí)行程序中記錄下共享對(duì)象的名字以及其它少量的登記信息堰怨。在此可執(zhí)行文件被執(zhí)行時(shí)，動(dòng)態(tài)鏈接庫(kù)的全部?jī)?nèi)容將被映射到運(yùn)行時(shí)相應(yīng)進(jìn)程的虛地址空間蛇摸。動(dòng)態(tài)鏈接程序?qū)⒏鶕?jù)可執(zhí)行程序中記錄的信息找到相應(yīng)的函數(shù)代碼备图。
對(duì)于可執(zhí)行文件中的函數(shù)調(diào)用，可分別采用動(dòng)態(tài)鏈接或靜態(tài)鏈接的方法。使用動(dòng)態(tài)鏈接能夠使最終的可執(zhí)行文件比較短小揽涮，并且當(dāng)共享對(duì)象被多個(gè)進(jìn)程使用時(shí)能節(jié)約一些內(nèi)存抠藕，因?yàn)樵趦?nèi)存中只需要保存一份此共享對(duì)象的代碼。但并不是使用動(dòng)態(tài)鏈接就一定比使用靜態(tài)鏈接要優(yōu)越蒋困。在某些情況下動(dòng)態(tài)鏈接可能帶來(lái)一些性能上損害盾似。
-
GCC的編譯鏈接
我們?cè)趌inux使用的gcc編譯器便是把以上的幾個(gè)過(guò)程進(jìn)行捆綁，使用戶只使用一次命令就把編譯工作完成雪标，這的確方便了編譯工作颜说，但對(duì)于初學(xué)者了解編譯過(guò)程就很不利了，下圖便是gcc代理的編譯過(guò)程：
- 預(yù)編譯
將.c 文件轉(zhuǎn)化成 .i文件
使用的gcc命令是：gcc –E
對(duì)應(yīng)于預(yù)處理命令cpp
- 編譯
將.c/.h文件轉(zhuǎn)換成.s文件
使用的gcc命令是：gcc –S
對(duì)應(yīng)于編譯命令 cc –S
- 匯編
將.s 文件轉(zhuǎn)化成 .o文件
使用的gcc 命令是：gcc –c
對(duì)應(yīng)于匯編命令是 as
- 鏈接
將.o文件轉(zhuǎn)化成可執(zhí)行程序
使用的gcc 命令是： gcc
對(duì)應(yīng)于鏈接命令是 ld
總結(jié)起來(lái)編譯過(guò)程就上面的四個(gè)過(guò)程：預(yù)編譯處理(.c) －－> 編譯汰聋、優(yōu)化程序（.s门粪、.asm）－－> 匯編程序(.obj、.o烹困、.a玄妈、.ko) －－> 鏈接程序（.exe、.elf髓梅、.axf等）拟蜻。
-
總結(jié)
一般情況下，我們只需要知道分成編譯和鏈接兩個(gè)階段枯饿，編譯階段將源程序（*.c) 轉(zhuǎn)換成為目標(biāo)代碼（一般是obj文件酝锅，至于具體過(guò)程就是上面說(shuō)的那些階段），鏈接階段是把源程序轉(zhuǎn)換成的目標(biāo)代碼（obj文件）與你程序里面調(diào)用的庫(kù)函數(shù)對(duì)應(yīng)的代碼連接起來(lái)形成對(duì)應(yīng)的可執(zhí)行文件（exe文件）就可以了奢方，其他的都需要在實(shí)踐中多多體會(huì)才能有更深的理解搔扁。
80. Bundle Adjustment
BA的思想就是根據(jù)視覺(jué)圖像同時(shí)估計(jì)相機(jī)位姿和空間點(diǎn)位置，通過(guò)構(gòu)造相應(yīng)的最小二乘問(wèn)題進(jìn)行優(yōu)化求解蟋字，又由于SLAM問(wèn)題天然適合使用圖優(yōu)化表示稿蹲，因此往往是使用圖優(yōu)化的方式進(jìn)行優(yōu)化求解。甚至我們可以稱BA為帶有相機(jī)位姿和空間點(diǎn)的圖優(yōu)化鹊奖。
81. hessian矩陣為何稀疏
稀疏性指的是H矩陣的稀疏性苛聘，而考慮海塞矩陣由
計(jì)算得到，因此H矩陣的稀疏性直接來(lái)源于雅克比矩陣J忠聚。J矩陣中含有大量的0項(xiàng)设哗，為什么呢？考慮J矩陣是代價(jià)函數(shù)e對(duì)相機(jī)位姿和路標(biāo)點(diǎn)進(jìn)行求導(dǎo)得到的两蟀，而一個(gè)相機(jī)位姿在一個(gè)時(shí)刻看到的路標(biāo)點(diǎn)是少數(shù)有限個(gè)网梢，因此求導(dǎo)后J矩陣含有很多0項(xiàng)，具體一點(diǎn)以代價(jià)函數(shù)的
分量為例垫竞，其對(duì)應(yīng)的J僅有兩個(gè)非0項(xiàng)澎粟，組合之后的J自然非0項(xiàng)也很少，因此H矩陣是非常稀疏的欢瞪。
Hessian矩陣判斷
（1）如果是正定矩陣活烙，則臨界點(diǎn)處是一個(gè)局部極小值
（2）如果是負(fù)定矩陣，則臨界點(diǎn)處是一個(gè)局部極大值
（3）如果是不定矩陣遣鼓，則臨界點(diǎn)處不是極值
實(shí)二次型矩陣為正定二次型的判斷方法
判斷一個(gè)矩陣是否是正定方法 ：
1啸盏、順序主子式：實(shí)對(duì)稱矩陣為正定矩陣的充要條件是的各順序主子式都大于零。
2骑祟、特征值：矩陣的特征值全大于零回懦，矩陣為正定。矩陣的特征值全小于零次企，矩陣為負(fù)定怯晕。否則是不定的。
82. 關(guān)于邊緣化
83. 在滑動(dòng)窗口中的應(yīng)用
84. ORBSLAM中的回環(huán)
? https://zhuanlan.zhihu.com/p/61850005
85. TCP UDP區(qū)別
86. 什么時(shí)候進(jìn)程會(huì)被阻塞
87. DBoW2利用 K叉樹(shù)的好處是什么呢缸棵？主要是加速舟茶。
-
可以加速判斷一個(gè)特征屬于哪個(gè)單詞。如果不使用K叉樹(shù)堵第，就需要與每個(gè)單詞比較（計(jì)算漢明距離）吧凉，共計(jì)需要比較clip_image063.png
次。而使用K叉樹(shù)之后踏志，需要的比較次數(shù)變?yōu)?/p>
clip_image065.png
次阀捅。大大提高了速度。這里利用了K叉樹(shù)的快速查找特性针余。 DBoW中存儲(chǔ)了Direct Index饲鄙，也就每個(gè)節(jié)點(diǎn)存儲(chǔ)有一幅圖像上所有歸屬與該節(jié)點(diǎn)的特征的index。在兩幀進(jìn)行特征匹配的時(shí)候圆雁，只需要針對(duì)每一個(gè)節(jié)點(diǎn)進(jìn)行匹配就好了傍妒，大大縮小了匹配空間，加速了匹配速度摸柄。ORB-SLAM幀間匹配都使用了這個(gè)trick颤练。
-
除此之外，如下圖驱负，DBoW的每個(gè)單詞中還存儲(chǔ)了Inverse index嗦玖，每個(gè)Inverse Index中存儲(chǔ)有所有有此單詞的圖像index，以及對(duì)應(yīng)的權(quán)重：
在進(jìn)行閉環(huán)搜索的時(shí)候跃脊，可以加快搜索過(guò)程的宇挫。具體的，我們只需要找與當(dāng)前關(guān)鍵幀有相同單詞的關(guān)鍵幀就可以了酪术。
88. DBoW2是如何計(jì)算相似分?jǐn)?shù)的器瘪。
在構(gòu)建詞典的時(shí)候翠储，使用了大量的數(shù)據(jù)。在這個(gè)環(huán)境中有的單詞出現(xiàn)的次數(shù)多橡疼，有的單詞出現(xiàn)的少援所。直觀想一下，出現(xiàn)次數(shù)多的單詞其實(shí)對(duì)環(huán)境不具有區(qū)分度欣除，反而出現(xiàn)次數(shù)少的單詞很有區(qū)分性住拭。比如一個(gè)單詞叫做“地磚”，環(huán)境中很多历帚，用這個(gè)單詞來(lái)比較兩幅圖像的話就不能顯著區(qū)分兩個(gè)環(huán)境滔岳。因此，引入一個(gè)TF-IDF（Term Frequency-Inverse Document Frequency）的權(quán)重挽牢，來(lái)降低這種單詞的作用谱煤。
為該單詞出現(xiàn)的次數(shù)，ni為所有單詞的總次數(shù)禽拔。（注：這里說(shuō)的是訓(xùn)練過(guò)程趴俘，詞典構(gòu)建過(guò)程。）明顯的奏赘， ni越大寥闪，權(quán)重越小。
至此詞典就構(gòu)建OK了：一個(gè)K叉樹(shù)磨淌，兩個(gè)index（Inverse index医男，Direct Index）灾馒，一個(gè)權(quán)重（TF-IDF）带到。
下面開(kāi)始使用詞典比較圖像相似度说敏。將一幅圖像A的所有特征轉(zhuǎn)換為詞袋向量，這里不僅僅要考慮單詞有無(wú)的問(wèn)題搪锣，還要考慮單詞的權(quán)重秋忙。A中有的單詞多，有的單詞少构舟。單詞多自然要加大權(quán)重灰追，單詞少自然要減少權(quán)重啦。引入另一個(gè)權(quán)重叫做TF（Term Frequency）
[圖片上傳失敗...(image-7d513a-1596547753169)]
89. ORB-SLAM中的回環(huán)
ORB-SLAM維護(hù)了一個(gè)數(shù)據(jù)庫(kù)狗超，這個(gè)數(shù)據(jù)庫(kù)里面保存了每個(gè)單詞能看到的關(guān)鍵幀弹澎。（inverse index）。每個(gè)關(guān)鍵幀都要從這個(gè)數(shù)據(jù)庫(kù)中檢測(cè)回環(huán)努咐，檢測(cè)完回環(huán)之后苦蒿，每個(gè)關(guān)鍵幀都會(huì)加入到這個(gè)數(shù)據(jù)庫(kù)中。當(dāng)一個(gè)關(guān)鍵幀被刪除之后渗稍，這個(gè)數(shù)據(jù)庫(kù)也會(huì)被同時(shí)更新佩迟。這樣做的好處就是加快回環(huán)搜索的速度团滥，這個(gè)與DBoW的inverse index是相同的思想，只不過(guò)ORB-SLAM自己去維護(hù)了以下而已报强。
2.1 搜索閉環(huán)候選幀
下面進(jìn)入正式的流程灸姊，因?yàn)镺RB-SLAM使用了共視圖，很多操作都可以采用共視圖輔助躺涝。
做了降頻，要求閉環(huán)與閉環(huán)之間至少經(jīng)過(guò)10個(gè)關(guān)鍵幀扼雏。
計(jì)算一個(gè)相對(duì)分?jǐn)?shù)minsocre：計(jì)算當(dāng)前幀與其共視圖中的幀的相似分?jǐn)?shù)坚嗜，取其中最小的那個(gè)作為minsocre。因?yàn)镈BoW計(jì)算出的絕對(duì)分?jǐn)?shù)不具有可比性诗充，取當(dāng)前幀與共視幀之間最小的相似度作為基準(zhǔn)苍蔬，如果大于這個(gè)基準(zhǔn)才有可能是閉環(huán)幀。
-
從上文中說(shuō)的數(shù)據(jù)庫(kù)中查找閉環(huán)候選幀蝴蜓。
因?yàn)閿?shù)據(jù)庫(kù)中維護(hù)了Inverse Index碟绑，所以可以快速找到與當(dāng)前幀有共同單詞的關(guān)鍵幀。其中就會(huì)有一個(gè)關(guān)鍵幀具有的共同單詞數(shù)最大茎匠，為maxcommonwords格仲。根據(jù)這個(gè)設(shè)一個(gè)閾值，mincommons = 0.8 * maxcommonwords诵冒，據(jù)此去掉共同單詞太少的候選關(guān)鍵凯肋。再加上minscore的要求干掉一部分關(guān)鍵幀。再再加上候選幀不能在當(dāng)前幀的共視圖中的條件汽馋，又干掉一部分侮东。之后，把相連的的候選幀歸為一組豹芯，每個(gè)組計(jì)算一個(gè)累加分?jǐn)?shù)悄雅，可以找到一個(gè)最大分?jǐn)?shù)bestAccScore。據(jù)此铁蹈，設(shè)置一個(gè)閾值宽闲，minScoreToRetain = 0.75*bestAccScore。用這個(gè)閾值干掉一部分分組握牧，這樣可以干掉一些孤立的閉環(huán)幀候選幀（孤立的可能都是錯(cuò)誤的閉環(huán)）便锨。剩下的這些分組中的關(guān)鍵幀就是閉環(huán)候選幀啦。
連續(xù)性檢測(cè)∥业現(xiàn)在放案，進(jìn)一步對(duì)候選關(guān)鍵幀進(jìn)行篩選。閉環(huán)不僅僅是單幀對(duì)單幀的匹配矫俺，好的閉環(huán)應(yīng)該是多幀對(duì)多幀的閉環(huán)吱殉。也就是形成連續(xù)閉環(huán)掸冤，如下圖所示。
[圖片上傳失敗...(image-eacd41-1596547753169)]
- 至此可以得到若干的比較可靠的候選關(guān)鍵幀了：mvpEnoughConsistentCandidates友雳。上面那么多的步驟稿湿，都是為了保證準(zhǔn)確率。SLAM中要求閉環(huán)的準(zhǔn)確率達(dá)到100%押赊。
2.2 幾何校驗(yàn)饺藤，sim3
下面，還要進(jìn)行幾何校驗(yàn)流礁。對(duì)每一個(gè)候選幀與當(dāng)前幀計(jì)算Sim3變換涕俗。
l 匹配當(dāng)前幀與閉環(huán)幀之間的特征點(diǎn)，利用DBoW加速一下（Direct Index的應(yīng)用）神帅，匹配太少的候選幀直接就干掉了再姑。
l 計(jì)算一個(gè)Sim3初值。
l 利用Sim3初值將候選關(guān)鍵幀的地圖點(diǎn)再投影到當(dāng)前幀找御，得到更多匹配元镀。
l 然后優(yōu)化Sim3. 第2-4步是在RANSAC框架下做的，只要有一個(gè)幀通過(guò)了測(cè)試霎桅，就跳出去了栖疑。這樣就選出了一個(gè)閉環(huán)幀。
l 把閉環(huán)幀的共視關(guān)鍵幀全部取出來(lái)滔驶，形成了局部地圖蔽挠，把局部地圖點(diǎn)再投到當(dāng)前幀匹配，又形成了更多的匹配瓜浸。檢查一下匹配點(diǎn)的數(shù)量來(lái)確定是否接受此次閉環(huán)澳淑。
l 至此，已經(jīng)找到了一個(gè)閉環(huán)幀插佛，并且計(jì)算出了當(dāng)前幀與閉環(huán)幀之間的Sim3變換杠巡。
2.3 Loop fusion
下面要去做Loop fusion：調(diào)整關(guān)鍵幀位姿，更新共視圖雇寇。
首先氢拥，把當(dāng)前幀和當(dāng)前幀的相鄰幀（共視幀&共視幀的共視幀），根據(jù)前面的Sim3變換對(duì)齊到閉環(huán)幀上锨侯。這樣做的好處是可以迅速把相機(jī)拉回到閉環(huán)位姿嫩海，并且把局部地圖也拉回去了，可以保證定位的連續(xù)性囚痴。
然后叁怪，更新共視圖關(guān)系，把閉環(huán)幀和閉環(huán)幀的共視幀上的地圖點(diǎn)投影到當(dāng)前幀上來(lái)深滚。進(jìn)行地圖點(diǎn)融合奕谭，匹配涣觉，更新共視幀。
上面的步驟其實(shí)就是把當(dāng)前幀的局部地圖和閉環(huán)幀的局部地圖縫合起來(lái)血柳。
2.4 優(yōu)化
接下來(lái)官册，就要開(kāi)始優(yōu)化啦。
首先基于Essential graph優(yōu)化一下难捌，然后再來(lái)一個(gè)全局BA膝宁。
90. Orbslam初始化策略
ORB-SLAM提出一種自動(dòng)初始化流程，能夠根據(jù)場(chǎng)景自動(dòng)的選擇模型（Homography or Fundamental）根吁，當(dāng)初始化質(zhì)量不好的時(shí)候則延遲初始化员淫。
-
初始化流程
Step 0. 選定一個(gè)參考幀，提取ORB特征
選擇標(biāo)準(zhǔn)：提取到的ORB特征數(shù)量足夠多>100個(gè)
Step 1. 匹配當(dāng)前幀與參考幀的ORB特征
當(dāng)前幀提取的特征數(shù)量足夠多>100婴栽，否則回到第0步满粗。
利用DBOW2的詞袋加速特征匹配過(guò)程辈末。
如果匹配點(diǎn)數(shù)太少<100愚争，則回到第0步。
上面的條件通過(guò)之后挤聘，進(jìn)行初始化
Step 2. 同步計(jì)算兩個(gè)模型Homography和Fundamental
[圖片上傳失敗...(image-fc641e-1596547753169)]
? Step 3. 模型選擇：Homography or Fundamental
? 計(jì)算比例：
[圖片上傳失敗...(image-9cc52f-1596547753169)]
如果大于0.45就選擇Homography為模型轰枝，否則就選擇Fundamental為模型。
? Step 4. 計(jì)算位姿和地圖點(diǎn)
? 根據(jù)選擇的模型恢復(fù)出相對(duì)位姿和3D地圖點(diǎn)组去。
? Step 5. Bundle Adjustment.
最后在來(lái)一個(gè)BA鞍陨。
這里有幾個(gè)關(guān)鍵點(diǎn)：1. 如何估計(jì)單應(yīng)矩陣、基礎(chǔ)矩陣从隆。2. 如何從單應(yīng)矩陣和基礎(chǔ)矩陣中分解出旋轉(zhuǎn)R和平移t诚撵。
91. 由F分解R與T
? [圖片上傳失敗...(image-407a9c-1596547753169)] 下面根據(jù)Essential Matrix分解出R和t。我們知道E的成分有一個(gè)反對(duì)稱矩陣S和一個(gè)正交矩陣R键闺，外加一個(gè)scale組成寿烟。
[圖片上傳失敗...(image-918f2e-1596547753169)]
實(shí)際上只有5個(gè)自由度。s可以放到反對(duì)稱矩陣?yán)锩妗?/p>
先給出兩個(gè)矩陣
[圖片上傳失敗...(image-ab1550-1596547753169)]
W為正價(jià)矩陣辛燥，Z為反對(duì)稱矩陣筛武。
對(duì)E進(jìn)行SVD分解為
[圖片上傳失敗...(image-35bb2-1596547753169)]
然后根據(jù)：
點(diǎn)在相機(jī)的前面，重投影誤差足夠小挎塌，恢復(fù)3D點(diǎn)徘六。
根據(jù)恢復(fù)出3D點(diǎn)的多少來(lái)找一個(gè)最優(yōu)解。
如果有多個(gè)最優(yōu)解則放棄這次計(jì)算榴都。
如果只有一個(gè)最優(yōu)解待锈，且恢復(fù)出了足夠的3D點(diǎn)，并且有足夠的視差（這里用的是地圖點(diǎn)指向兩個(gè)幀的夾角）就接收嘴高。
92. 由單應(yīng)矩陣H恢復(fù)出R和t
按照ORB-SLAM的做法炉擅，可以恢復(fù)8個(gè)解辉懒，然后從8個(gè)解中選擇一個(gè)最優(yōu)解。
然后根據(jù)恢復(fù)出的3D點(diǎn)個(gè)數(shù)谍失，視差等信息篩選出最優(yōu)解眶俩，要求
最優(yōu)個(gè)數(shù) > 0.7 次優(yōu)個(gè)數(shù)
最優(yōu)的視差，大于最小要求的視差
最優(yōu)的個(gè)數(shù)快鱼，大于最小設(shè)置的個(gè)數(shù)
最優(yōu)個(gè)數(shù)颠印，大于匹配點(diǎn)個(gè)數(shù)*0.9
93. EPNP算法
https://www.zybuluo.com/snuffles/note/1454799
94. DLT算法
https://zhuanlan.zhihu.com/p/58648937
95. NLS 問(wèn)題之魯棒代價(jià)函數(shù)(robust cost function)處理外點(diǎn)
96. 實(shí)現(xiàn)一個(gè)計(jì)時(shí)類(lèi)，可以用來(lái)為程序運(yùn)行時(shí)間計(jì)時(shí)
#include<iostream>
#include<chrono>
using namespace std;
using namespace std::chrono;
class Timer{
public:
void start(){ _startpoint = high_resolution_clock::now();}
void end(){_stoppoint = high_resolution_clock::now();}
template<typename span>
auto delta() const{return duration_cast<span> (_stoppoint-_startpoint).count();}
private:
time_point<high_resolution_clock> _startpoint;
time_point<high_resolution_clock> _stoppoint;
}
