OpenCV學習筆記（18）雙目測距與三維重建的OpenCV實現問題集錦（三）立體匹配與視差計算

2023-10-12 00:58
文章标签 opencv 匹配 18 問題 重建 學習 實現 筆記 雙目 測距 三維 集錦 立體 視差 計算

本文主要是介绍OpenCV學習筆記（18）雙目測距與三維重建的OpenCV實現問題集錦（三）立體匹配與視差計算，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

http://blog.csdn.net/chenyusiyuan/article/details/5967291

四、雙目匹配與視差計算

立體匹配主要是通過找出每對圖像間的對應關系，根據三角測量原理，得到視差圖；在獲得了視差信息後，根據投影模型很容易地可以得到原始圖像的深度信息和三維信息。立體匹配技術被普遍認為是立體視覺中最困難也是最關鍵的問題，主要是以下因素的影響：

 

（1） 光學失真和噪聲（亮度、色調、飽和度等失衡）

（2） 平滑表面的鏡面反射

（3） 投影縮減（Foreshortening）

（4） 透視失真（Perspective distortions）

（5） 低紋理（Low texture）

（6） 重復紋理（Repetitive/ambiguous patterns）

（7） 透明物體

（8） 重疊和非連續

 

 

目前立體匹配算法是計算機視覺中的一個難點和熱點，算法很多，但是一般的步驟是：

 

A、匹配代價計算

匹配代價計算是整個立體匹配算法的基礎，實際是對不同視差下進行灰度相似性測量。常見的方法有灰度差的平方SD（squared intensity differences），灰度差的絕對值AD（absolute intensity differences）等。另外，在求原始匹配代價時可以設定一個上限值，來減弱疊加過程中的誤匹配的影響。以AD法求匹配代價為例，可用下式進行計算，其中T為設定的閾值。

圖18

B、 匹配代價疊加

一般來說，全局算法基於原始匹配代價進行後續算法計算。而區域算法則需要通過窗口疊加來增強匹配代價的可靠性，根據原始匹配代價不同，可分為：

圖19

 

C、 視差獲取

對於區域算法來說，在完成匹配代價的疊加以後，視差的獲取就很容易了，只需在一定范圍內選取疊加匹配代價最優的點（SAD和SSD取最小值，NCC取最大值）作為對應匹配點，如勝者為王算法WTA（Winner-take-all）。而全局算法則直接對原始匹配代價進行處理，一般會先給出一個能量評價函數，然後通過不同的優化算法來求得能量的最小值，同時每個點的視差值也就計算出來了。

 

D、視差細化（亞像素級）

大多數立體匹配算法計算出來的視差都是一些離散的特定整數值，可滿足一般應用的精度要求。但在一些精度要求比較高的場合，如精確的三維重構中，就需要在初始視差獲取後采用一些措施對視差進行細化，如匹配代價的曲線擬合、圖像濾波、圖像分割等。

 

有關立體匹配的介紹和常見匹配算法的比較，推薦大家看看Stefano Mattoccia 的講義 Stereo Vision: algorithms and applications，190頁的ppt，講解得非常形象詳盡。

1． opencv2.1和opencv2.0在做stereo vision方面有什麼區別了？

2.1版增強了Stereo Vision方面的功能：

(1) 新增了 SGBM 立體匹配算法（源自Heiko Hirschmuller的《Stereo Processing by Semi-global Matching and Mutual Information》），可以獲得比 BM 算法物體輪廓更清晰的視差圖（但低紋理區域容易出現橫/斜紋路，在 GCstate->fullDP 選項使能時可消減這種異常紋路，但對應區域視差變為0，且運行速度會有所下降），速度比 BM 稍慢， 352*288的幀處理速度大約是 5 幀/秒；

(2) 視差效果：BM < SGBM < GC；處理速度：BM > SGBM > GC ；

(3) BM 算法比2.0版性能有所提升，其狀態參數新增了對左右視圖感興趣區域 ROI 的支持（roi1 和 roi2，由stereoRectify函數產生）；

(4) BM 算法和 GC 算法的核心代碼改動不大，主要是面向多線程運算方面的（由 OpenMP 轉向 Intel TBB）；

(5) cvFindStereoCorrespondenceBM 函數的disparity參數的數據格式新增了 CV_32F 的支持，這種格式的數據給出實際視差，而 2.0 版只支持 CV_16S，需要除以 16.0 才能得到實際的視差數值。

 

 

2． 用於立體匹配的圖像可以是彩色的嗎？

在OpenCV2.1中，BM和GC算法只能對8位灰度圖像計算視差，SGBM算法則可以處理24位（8bits*3）彩色圖像。所以在讀入圖像時，應該根據采用的算法來處理圖像：

 

int color_mode = alg == STEREO_SGBM ? 1 : 0;
//
// 載入圖像
cvGrabFrame( lfCam );
cvGrabFrame( riCam );
frame1 = cvRetrieveFrame( lfCam );
frame2 = cvRetrieveFrame( riCam );
if(frame1.empty()) break;
resize(frame1, img1, img_size, 0, 0);
resize(frame2, img2, img_size, 0, 0);
// 選擇彩色或灰度格式作為雙目匹配的處理圖像
if (!color_mode && cn>1)
{
cvtColor(img1, img1gray, CV_BGR2GRAY);
cvtColor(img2, img2gray, CV_BGR2GRAY);
img1p = img1gray;
img2p = img2gray;
}
else
{
img1p = img1;
img2p = img2;
}

 

 

3． 怎樣獲取與原圖像有效像素區域相同的視差圖？

在OpenCV2.0及以前的版本中，所獲取的視差圖總是在左側和右側有明顯的黑色區域，這些區域沒有有效的視差數據。視差圖有效像素區域與視差窗口（ndisp，一般取正值且能被16整除）和最小視差值（mindisp，一般取0或負值）相關，視差窗口越大，視差圖左側的黑色區域越大，最小視差值越小，視差圖右側的黑色區域越大。其原因是為了保證參考圖像（一般是左視圖）的像素點能在目標圖像（右視圖）中按照設定的視差匹配窗口匹配對應點，OpenCV 只從參考圖像的第 (ndisp - 1 + mindisp) 列開始向右計算視差，第 0列到第 (ndisp - 1 + mindisp) 列的區域視差統一設置為 (mindisp - 1) *16；視差計算到第 width + mindisp列時停止，余下的右側區域視差值也統一設置為 (mindisp - 1) *16。  

00177 static const int DISPARITY_SHIFT = 4;
…
00411     int ndisp = state->numberOfDisparities;
00412     int mindisp = state->minDisparity;
00413     int lofs = MAX(ndisp - 1 + mindisp, 0);
00414     int rofs = -MIN(ndisp - 1 + mindisp, 0);
00415     int width = left->cols, height = left->rows;
00416     int width1 = width - rofs - ndisp + 1;
…
00420     short FILTERED = (short)((mindisp - 1) << DISPARITY_SHIFT);
…
00466     // initialize the left and right borders of the disparity map
00467     for( y = 0; y < height; y++ )
00468     {
00469         for( x = 0; x < lofs; x++ )
00470             dptr[y*dstep + x] = FILTERED;
00471         for( x = lofs + width1; x < width; x++ )
00472             dptr[y*dstep + x] = FILTERED;
00473     }
00474     dptr += lofs;
00475
00476     for( x = 0; x < width1; x++, dptr++ )…

 

這樣的設置很明顯是不符合實際應用的需求的，它相當於把攝像頭的視場范圍縮窄了。因此，OpenCV2.1 做了明顯的改進，不再要求左右視圖和視差圖的大小（size）一致，允許對視差圖進行左右邊界延拓，這樣，雖然計算視差時還是按上面的代碼思路來處理左右邊界，但是視差圖的邊界得到延拓後，有效視差的范圍就能夠與對應視圖完全對應。具體的實現代碼范例如下：

 

//
// 對左右視圖的左邊進行邊界延拓，以獲取與原始視圖相同大小的有效視差區域
copyMakeBorder(img1r, img1b, 0, 0, m_nMaxDisp, 0, IPL_BORDER_REPLICATE);
copyMakeBorder(img2r, img2b, 0, 0, m_nMaxDisp, 0, IPL_BORDER_REPLICATE);//
// 計算視差
if( alg == STEREO_BM )
{bm(img1b, img2b, dispb);// 截取與原始畫面對應的視差區域（舍去加寬的部分）displf = dispb.colRange(m_nMaxDisp, img1b.cols);	
}
else if(alg == STEREO_SGBM)
{sgbm(img1b, img2b, dispb);displf = dispb.colRange(m_nMaxDisp, img1b.cols);
}

 

4． cvFindStereoCorrespondenceBM的輸出結果好像不是以像素點為單位的視差？

「@scyscyao：在OpenCV2.0中，BM函數得出的結果是以16位符號數的形式的存儲的，出於精度需要，所有的視差在輸出時都擴大了16倍(2^4)。其具體代碼表示如下：

dptr[y*dstep] = (short)(((ndisp - mind - 1 + mindisp)*256 + (d != 0 ? (p-n)*128/d : 0) + 15) >> 4);

可以看到，原始視差在左移8位(256)並且加上一個修正值之後又右移了4位，最終的結果就是左移4位。

因此，在實際求距離時，cvReprojectTo3D出來的X/W,Y/W,Z/W都要乘以16 (也就是W除以16)，才能得到正確的三維坐標信息。」

 

在OpenCV2.1中，BM算法可以用 CV_16S 或者 CV_32F 的方式輸出視差數據，使用32位float格式可以得到真實的視差值，而CV_16S 格式得到的視差矩陣則需要 除以16 才能得到正確的視差。另外，OpenCV2.1另外兩種立體匹配算法 SGBM 和 GC 只支持 CV_16S 格式的 disparity 矩陣。

 

 

5． 如何設置BM、SGBM和GC算法的狀態參數？

（1）StereoBMState

// 預處理濾波參數

  • preFilterType：預處理濾波器的類型，主要是用於降低亮度失真（photometric distortions）、消除噪聲和增強紋理等, 有兩種可選類型：CV_STEREO_BM_NORMALIZED_RESPONSE（歸一化響應） 或者CV_STEREO_BM_XSOBEL（水平方向Sobel算子，默認類型）, 該參數為 int 型；
  • preFilterSize：預處理濾波器窗口大小，容許范圍是[5,255]，一般應該在 5x5..21x21 之間，參數必須為奇數值, int 型
  • preFilterCap：預處理濾波器的截斷值，預處理的輸出值僅保留[-preFilterCap, preFilterCap]范圍內的值，參數范圍：1 - 31（文檔中是31，但代碼中是 63）, int

// SAD 參數

  • SADWindowSize：SAD窗口大小，容許范圍是[5,255]，一般應該在 5x5 至 21x21 之間，參數必須是奇數，int 型
  • minDisparity：最小視差，默認值為 0, 可以是負值，int 型
  • numberOfDisparities：視差窗口，即最大視差值與最小視差值之差, 窗口大小必須是 16 的整數倍，int 型

// 後處理參數

  • textureThreshold：低紋理區域的判斷閾值。如果當前SAD窗口內所有鄰居像素點的x導數絕對值之和小於指定閾值，則該窗口對應的像素點的視差值為 0（That is, if the sum of absolute values of x-derivatives computed over SADWindowSize by SADWindowSize pixel neighborhood is smaller than the parameter, no disparity is computed at the pixel），該參數不能為負值，int 型
  • uniquenessRatio：視差唯一性百分比， 視差窗口范圍內最低代價是次低代價的(1 + uniquenessRatio/100)倍時，最低代價對應的視差值才是該像素點的視差，否則該像素點的視差為 0 （the minimum margin in percents between the best (minimum) cost function value and the second best value to accept the computed disparity, that is, accept the computed disparity d^ only if SAD(d) >= SAD(d^) x (1 + uniquenessRatio/100.) for any d != d*+/-1 within the search range ），該參數不能為負值，一般5-15左右的值比較合適，int 型
  • speckleWindowSize：檢查視差連通區域變化度的窗口大小, 值為 0 時取消 speckle 檢查，int 型
  • speckleRange：視差變化閾值，當窗口內視差變化大於閾值時，該窗口內的視差清零，int 型

// OpenCV2.1 新增的狀態參數

  • roi1, roi2：左右視圖的有效像素區域，一般由雙目校正階段的 cvStereoRectify 函數傳遞，也可以自行設定。一旦在狀態參數中設定了 roi1 和 roi2，OpenCV 會通過cvGetValidDisparityROI 函數計算出視差圖的有效區域，在有效區域外的視差值將被清零。
  • disp12MaxDiff：左視差圖（直接計算得出）和右視差圖（通過cvValidateDisparity計算得出）之間的最大容許差異。超過該閾值的視差值將被清零。該參數默認為 -1，即不執行左右視差檢查。int 型。注意在程序調試階段最好保持該值為 -1，以便查看不同視差窗口生成的視差效果。具體請參見《使用OpenGL動態顯示雙目視覺三維重構效果示例》一文中的討論。

在上述參數中，對視差生成效果影響較大的主要參數是 SADWindowSize、numberOfDisparities 和 uniquenessRatio 三個，一般只需對這三個參數進行調整，其余參數按默認設置即可。

在OpenCV2.1中，BM算法有C和C++ 兩種實現模塊。

 

（2）StereoSGBMState

SGBM算法的狀態參數大部分與BM算法的一致，下面只解釋不同的部分：

  • SADWindowSize：SAD窗口大小，容許范圍是[1,11]，一般應該在 3x3 至 11x11 之間，參數必須是奇數，int 型
  • P1, P2：控制視差變化平滑性的參數。P1、P2的值越大，視差越平滑。P1是相鄰像素點視差增/減 1 時的懲罰系數；P2是相鄰像素點視差變化值大於1時的懲罰系數。P2必須大於P1。OpenCV2.1提供的例程stereo_match.cpp 給出了 P1 和 P2 比較合適的數值。
  • fullDP：布爾值，當設置為 TRUE 時，運行雙通道動態編程算法（full-scale 2-pass dynamic programming algorithm），會佔用O(W*H*numDisparities)個字節，對於高分辨率圖像將佔用較大的內存空間。一般設置為 FALSE。

注意OpenCV2.1的SGBM算法是用C++ 語言編寫的，沒有C實現模塊。與H. Hirschmuller提出的原算法相比，主要有如下變化：

  1. 算法默認運行單通道DP算法，只用了5個方向，而fullDP使能時則使用8個方向（可能需要佔用大量內存）。
  2. 算法在計算匹配代價函數時，采用塊匹配方法而非像素匹配（不過SADWindowSize=1時就等於像素匹配了）。
  3. 匹配代價的計算采用BT算法（"Depth Discontinuities by Pixel-to-Pixel Stereo" by S. Birchfield and C. Tomasi），並沒有實現基於互熵信息的匹配代價計算。
  4. 增加了一些BM算法中的預處理和後處理程序。

（3）StereoGCState

GC算法的狀態參數只有兩個：numberOfDisparities 和 maxIters ，並且只能通過cvCreateStereoGCState 在創建算法狀態結構體時一次性確定，不能在循環中更新狀態信息。GC算法並不是一種實時算法，但可以得到物體輪廓清晰准確的視差圖，適用於靜態環境物體的深度重構。

注意GC算法只能在C語言模式下運行，並且不能對視差圖進行預先的邊界延拓，左右視圖和左右視差矩陣的大小必須一致。

 

 

6． 如何實現視差圖的偽彩色顯示？

首先要將16位符號整形的視差矩陣轉換為8位無符號整形矩陣，然後按照一定的變換關系進行偽彩色處理。我的實現代碼如下： 

 

// 轉換為 CV_8U 格式，彩色顯示
dispLfcv = displf, dispRicv = dispri, disp8cv = disp8;
if (alg == STEREO_GC)
{cvNormalize( &dispLfcv, &disp8cv, 0, 256, CV_MINMAX );
} 
else
{displf.convertTo(disp8, CV_8U, 255/(m_nMaxDisp*16.));
}
F_Gray2Color(&disp8cv, vdispRGB);

 

 

灰度圖轉偽彩色圖的代碼，主要功能是使灰度圖中 亮度越高的像素點，在偽彩色圖中對應的點越趨向於 紅色；亮度越低，則對應的偽彩色越趨向於 藍色；總體上按照灰度值高低，由紅漸變至藍，中間色為綠色。其對應關系如下圖所示：

 

圖20

 

 

void F_Gray2Color(CvMat* gray_mat, CvMat* color_mat)
{if(color_mat)cvZero(color_mat);int stype = CV_MAT_TYPE(gray_mat->type), dtype = CV_MAT_TYPE(color_mat->type);int rows = gray_mat->rows, cols = gray_mat->cols;// 判斷輸入的灰度圖和輸出的偽彩色圖是否大小相同、格式是否符合要求if (CV_ARE_SIZES_EQ(gray_mat, color_mat) && stype == CV_8UC1 && dtype == CV_8UC3){CvMat* red = cvCreateMat(gray_mat->rows, gray_mat->cols, CV_8U);CvMat* green = cvCreateMat(gray_mat->rows, gray_mat->cols, CV_8U);CvMat* blue = cvCreateMat(gray_mat->rows, gray_mat->cols, CV_8U);CvMat* mask = cvCreateMat(gray_mat->rows, gray_mat->cols, CV_8U);// 計算各彩色通道的像素值cvSubRS(gray_mat, cvScalar(255), blue);	// blue(I) = 255 - gray(I)cvCopy(gray_mat, red);			// red(I) = gray(I)cvCopy(gray_mat, green);			// green(I) = gray(I),if gray(I) < 128cvCmpS(green, 128, mask, CV_CMP_GE );	// green(I) = 255 - gray(I), if gray(I) >= 128cvSubRS(green, cvScalar(255), green, mask);cvConvertScale(green, green, 2.0, 0.0);// 合成偽彩色圖cvMerge(blue, green, red, NULL, color_mat);cvReleaseMat( &red );cvReleaseMat( &green );cvReleaseMat( &blue );cvReleaseMat( &mask );}
}

 

7． 如何將視差數據保存為 txt 數據文件以便在 Matlab 中讀取分析？

由於OpenCV本身只支持 xml、yml 的數據文件讀寫功能，並且其xml文件與構建網頁數據所用的xml文件格式不一致，在Matlab中無法讀取。我們可以通過以下方式將視差數據保存為txt文件，再導入到Matlab中。 

 

void saveDisp(const char* filename, const Mat& mat)		
{FILE* fp = fopen(filename, "wt");fprintf(fp, "%02d/n", mat.rows);fprintf(fp, "%02d/n", mat.cols);for(int y = 0; y < mat.rows; y++){for(int x = 0; x < mat.cols; x++){short disp = mat.at<short>(y, x); // 這裡視差矩陣是CV_16S 格式的，故用 short 類型讀取fprintf(fp, "%d/n", disp); // 若視差矩陣是 CV_32F 格式，則用 float 類型讀取}}fclose(fp);
}

 

相應的Matlab代碼為：

  

function img = txt2img(filename)
data = importdata(filename);
r = data(1);    % 行數
c = data(2);    % 列數
disp = data(3:end); % 視差
vmin = min(disp);
vmax = max(disp);
disp = reshape(disp, [c,r])'; % 將列向量形式的 disp 重構為 矩陣形式
%  OpenCV 是行掃描存儲圖像，Matlab 是列掃描存儲圖像
%  故對 disp 的重新排列是首先變成 c 行 r 列的矩陣，然後再轉置回 r 行 c 列
img = uint8( 255 * ( disp - vmin ) / ( vmax - vmin ) );
mesh(disp);
set(gca,'YDir','reverse');  % 通過 mesh 方式繪圖時，需倒置 Y 軸方向
axis tight; % 使坐標軸顯示范圍與數據范圍相貼合，去除空白顯示區

 

顯示效果如下：

 

圖21

 

 

 

 

（待續……）


这篇关于OpenCV學習筆記（18）雙目測距與三維重建的OpenCV實現問題集錦（三）立體匹配與視差計算的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/192086。

相关文章

使用opencv优化图片（画面变清晰）

使用opencv优化图片（画面变清晰）

文章目录 需求影响照片清晰度的因素 实现降噪测试代码 锐化空间锐化Unsharp Masking频率域锐化对比测试 对比度增强常用算法对比测试 需求 对图像进行优化，使其看起来更清晰，同时保持尺寸不变，通常涉及到图像处理技术如锐化、降噪、对比度增强等 影响照片清晰度的因素 影响照片清晰度的因素有很多，主要可以从以下几个方面来分析 1. 拍摄设备 相机传感器：相机传
阅读更多...
【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯，先赞后看哦~🎈🎈 🏆 作者简介：景天科技苑 🏆《头衔》：大厂架构师，华为云开发者社区专家博主，阿里云开发者社区专家博主，CSDN全栈领域优质创作者，掘金优秀博主，51CTO博客专家等。 🏆《博客》：Python全栈，前后端开发，小程序开发，人工智能，js逆向，App逆向，网络系统安全，数据分析，Django，fastapi
阅读更多...
hdu 3065 AC自动机 匹配串编号以及出现次数

hdu 3065 AC自动机 匹配串编号以及出现次数

题意： 仍旧是天朝语题。 Input 第一行，一个整数N（1<=N<=1000），表示病毒特征码的个数。 接下来N行，每行表示一个病毒特征码，特征码字符串长度在1—50之间，并且只包含“英文大写字符”。任意两个病毒特征码，不会完全相同。 在这之后一行，表示“万恶之源”网站源码，源码字符串长度在2000000之内。字符串中字符都是ASCII码可见字符（不包括回车）。
阅读更多...
二分最大匹配总结

二分最大匹配总结

HDU 2444  黑白染色 ，二分图判定 const int maxn = 208 ;vector<int> g[maxn] ;int n ;bool vis[maxn] ;int match[maxn] ;;int color[maxn] ;int setcolor(int u , int c){color[u] = c ;for(vector<int>::iter
阅读更多...
opencv 滚动条

opencv 滚动条

参数介绍:createTrackbar( trackbarname , "hello" , &alpha_slider ,alpha_max ,  on_trackbar )  ;在标签中显示的文字（提示滑动条的用途） TrackbarName创建的滑动条要放置窗体的名字 “hello”滑动条的取值范围从 0 到 alpha_max (最小值只能为 zero).滑动后的值存放在
阅读更多...
android-opencv-jni

android-opencv-jni

//------------------start opencv--------------------@Override public void onResume(){ super.onResume(); //通过OpenCV引擎服务加载并初始化OpenCV类库，所谓OpenCV引擎服务即是 //OpenCV_2.4.3.2_Manager_2.4_*.apk程序包，存
阅读更多...
POJ 3057 最大二分匹配+bfs + 二分

POJ 3057 最大二分匹配+bfs + 二分

SampleInput35 5XXDXXX...XD...XX...DXXXXX5 12XXXXXXXXXXXXX..........DX.XXXXXXXXXXX..........XXXXXXXXXXXXX5 5XDXXXX.X.DXX.XXD.X.XXXXDXSampleOutput321impossible
阅读更多...
OpenCV结构分析与形状描述符（11）椭圆拟合函数fitEllipse()的使用

OpenCV结构分析与形状描述符（11）椭圆拟合函数fitEllipse()的使用

操作系统：ubuntu22.04 OpenCV版本：OpenCV4.9 IDE:Visual Studio Code 编程语言：C++11 算法描述 围绕一组2D点拟合一个椭圆。 该函数计算出一个椭圆，该椭圆在最小二乘意义上最好地拟合一组2D点。它返回一个内切椭圆的旋转矩形。使用了由[90]描述的第一个算法。开发者应该注意，由于数据点靠近包含的 Mat 元素的边界，返回的椭圆/旋转矩形数据
阅读更多...
OmniGlue论文详解（特征匹配）

OmniGlue论文详解（特征匹配）

OmniGlue论文详解（特征匹配） 摘要1. 引言2. 相关工作2.1. 广义局部特征匹配2.2. 稀疏可学习匹配2.3. 半稠密可学习匹配2.4. 与其他图像表示匹配 3. OmniGlue3.1. 模型概述3.2. OmniGlue 细节3.2.1. 特征提取3.2.2. 利用DINOv2构建图形。3.2.3. 信息传播与新的指导3.2.4. 匹配层和损失函数3.2.5. 与Super
阅读更多...
二分图的最大匹配——《啊哈！算法》

二分图的最大匹配——《啊哈！算法》

二分图 如果一个图的所有顶点可以被分为X和Y两个集合，并且所有边的两个顶点恰好一个属于X，另外一个属于Y，即每个集合内的顶点没有边相连，那么此图就是二分图。 二分图在任务调度、工作安排等方面有较多的应用。 判断二分图：首先将任意一个顶点着红色，然后将其相邻的顶点着蓝色，如果按照这样的着色方法可以将全部顶点着色的话，并且相邻的顶点着色不同，那么该图就是二分图。 java
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2