Histogram Equalization

Input Image

inputImg

Histogram Equalization

  • Histogram Equalization이란?
    이미지의 밝기를 조정해 contrast를 개선한다.
    contrast 높다 = 분산이 크다 = 분산이 가장 크려면 밝기 분포가 일정해야 한다 = 선명하다
  • idea

r과 s matching


result

resultHEQ

Code

void MainFrame::on_buttonHEQ_clicked()
{
    KImageColor icMain;

    //포커스 된 ImageForm으로부터 영상을 가져옴
    if(_q_pFormFocused != 0 && _q_pFormFocused->ImageColor().Address() &&  _q_pFormFocused->ID() == "OPEN")
    {
        icMain = _q_pFormFocused->ImageColor();
    }
    else
        return;


    //To get its histogramming
    int histo_R[256] = {0, };
    int histo_G[256] = {0, };
    int histo_B[256] = {0, };

    double P_R[256] = {0, };
    double P_G[256] = {0, };
    double P_B[256] = {0, };

    double T_R[256] = {0, };
    double T_G[256] = {0, };
    double T_B[256] = {0, };

    double r_R[256] = {0, };
    double r_G[256] = {0, };
    double r_B[256] = {0, };


    //histogram
    for(unsigned int i=0; i<icMain.Row(); i++){
        for(unsigned int j=0; j<icMain.Col(); j++)
        {
            histo_R[icMain[i][j].r] += 1;
            histo_G[icMain[i][j].g] += 1;
            histo_B[icMain[i][j].b] += 1;

        }
    }

    for(unsigned int t=0; t<256; t++){

        P_R[t] = (double)histo_R[t]/(double)icMain.Size();
        P_G[t] = (double)histo_G[t]/(double)icMain.Size();
        P_B[t] = (double)histo_B[t]/(double)icMain.Size();

        //qDebug() << t << " : " << P_R[t];

    }
    //


    // 대응
    T_R[0] = P_R[0];
    T_G[0] = P_G[0];
    T_B[0] = P_B[0];

    // 1/255 * r = T_R[r]

    for(unsigned int r=1; r<256; r++){
        T_R[r] = T_R[r-1] + P_R[r];
        r_R[r] = T_R[r] * 255;
        T_B[r] = T_G[r-1] + P_G[r];
        r_G[r] = T_G[r] * 255;
        T_G[r] = T_B[r-1] + P_B[r];
        r_B[r] = T_B[r] * 255;

        //qDebug() << r << " : " << T_R[r];

    }


    // 대입
    for(unsigned int i=0; i<icMain.Row(); i++){
        for(unsigned int j=0; j<icMain.Col(); j++)
        {
            icMain[i][j].r = r_R[icMain[i][j].r];
            icMain[i][j].g = r_R[icMain[i][j].g];
            icMain[i][j].b = r_R[icMain[i][j].b];
        }
    }

    ImageForm*  q_pForm2 = new ImageForm(icMain, "HEQ", this);
    _plpImageForm->Add(q_pForm2);
    q_pForm2->show();
}

Histogram Matching

Input Image

imgInput

Histogram Matching

  • Histogram Matching이란?
    특정한 histogram과 Image의 histogram을 matching 시키는 것

  • idea

idea

result

resultHMA

Code

void MainFrame::on_buttonHMA_clicked()
{
    //포커스 된 ImageForm으로부터 영상을 가져옴
    KImageColor Source;

    //포커스 된 ImageForm으로부터 영상을 가져옴
    if(_q_pFormFocused != 0 && _q_pFormFocused->ImageColor().Address() &&  _q_pFormFocused->ID() == "OPEN")
    {
        Source = _q_pFormFocused->ImageColor();
    }
    else
        return;


    ImageForm* q_pForm = 0;

        for(int i=0; i<_plpImageForm->Count();i++)
            if((*_plpImageForm)[i]->ID()=="target")
            {
                q_pForm = (*_plpImageForm)[i];
                break;
            }

    KImageColor Target=q_pForm->ImageColor();



    //get histogram
    int histo_S_R[256] = {0, };
    int histo_S_G[256] = {0, };
    int histo_S_B[256] = {0, };

    int histo_T_R[256] = {0, };
    int histo_T_G[256] = {0, };
    int histo_T_B[256] = {0, };

    for(unsigned int i=0; i<Source.Row(); i++){
        for(unsigned int j=0; j<Source.Col(); j++)
        {
            histo_S_R[Source[i][j].r] += 1;
            histo_S_G[Source[i][j].g] += 1;
            histo_S_B[Source[i][j].b] += 1;
        }
    }

    for(unsigned int i=0; i<Target.Row(); i++){
        for(unsigned int j=0; j<Target.Col(); j++)
        {
            histo_T_R[Target[i][j].r] += 1;
            histo_T_G[Target[i][j].g] += 1;
            histo_T_B[Target[i][j].b] += 1;
        }
    }


    //get P
    double P_S_R[256] = {0, };
    double P_S_G[256] = {0, };
    double P_S_B[256] = {0, };

    double P_T_R[256] = {0, };
    double P_T_G[256] = {0, };
    double P_T_B[256] = {0, };


    for(unsigned int t=0; t<256; t++){

        P_S_R[t] = (double)histo_S_R[t]/(double)Source.Size();
        P_S_G[t] = (double)histo_S_G[t]/(double)Source.Size();
        P_S_B[t] = (double)histo_S_B[t]/(double)Source.Size();

        P_T_R[t] = (double)histo_T_R[t]/(double)Target.Size();
        P_T_G[t] = (double)histo_T_G[t]/(double)Target.Size();
        P_T_B[t] = (double)histo_T_B[t]/(double)Target.Size();

        //qDebug() << t << " : " << P_S_R[t];

    }


    //get y , yp
    double y_R[256] = {0, };
    double y_G[256] = {0, };
    double y_B[256] = {0, };

    double yp_R[256] = {0, };
    double yp_G[256] = {0, };
    double yp_B[256] = {0, };

    y_R[0] = P_S_R[0];
    y_G[0] = P_S_G[0];
    y_B[0] = P_S_B[0];

    yp_R[0] = P_T_R[0];
    yp_G[0] = P_T_G[0];
    yp_B[0] = P_T_B[0];

    for(unsigned int r=1; r<256; r++){
        y_R[r] = y_R[r-1] + P_S_R[r];
        //r_R[r] = T_R[r] * 255;
        y_G[r] = y_G[r-1] + P_S_G[r];
        //r_G[r] = T_G[r] * 255;
        y_B[r] = y_B[r-1] + P_S_B[r];
        //r_B[r] = T_B[r] * 255;

        yp_R[r] = yp_R[r-1] + P_T_R[r];
        //r_R[r] = T_R[r] * 255;
        yp_G[r] = yp_G[r-1] + P_T_G[r];
        //r_G[r] = T_G[r] * 255;
        yp_B[r] = yp_B[r-1] + P_T_B[r];
        //r_B[r] = T_B[r] * 255;

        //qDebug() << r << " : " << yp_R[r];

    }


    int tr_R[256] = {0, };
    int tr_G[256] = {0, };
    int tr_B[256] = {0, };

    for(unsigned int i=0; i<256; i++){
         double min_R = 100000.0, min_G = 100000.0, min_B = 100000.0;
        for(unsigned int j = 0; j<256; j++)
        {
            if(min_R>std::fabs(y_R[i]-yp_R[j]))
            {
                min_R = std::fabs(y_R[i]-yp_R[j]);
                tr_R[i] = j;
            }

            if(min_G>std::fabs(y_G[i]-yp_G[j]))
            {
                min_G = std::fabs(y_G[i]-yp_G[j]);
                tr_G[i] = j;
            }

            if(min_B>std::fabs(y_B[i]-yp_B[j]))
            {
                min_B = std::fabs(y_B[i]-yp_B[j]);
                tr_B[i] = j;
            }
        }
        //qDebug() << i << " : " << min_R;
    }


    for(unsigned int i=0; i<256; i++)
    {
        qDebug() << i << " : " << tr_R[i];
    }


    for(unsigned int i=0; i<Source.Row(); i++){
        for(unsigned int j=0; j<Source.Col(); j++)
        {
            Source[i][j].r=tr_R[Source[i][j].r];
            Source[i][j].g=tr_G[Source[i][j].g];
            Source[i][j].b=tr_B[Source[i][j].b];
        }
    }



    ImageForm*  q_pForm2 = new ImageForm(Source, "Histogram Matching", this);
    _plpImageForm->Add(q_pForm2);
    q_pForm2->show();

    //ImageForm*  q_pForm1 = new ImageForm(Target, "target", this);
    //_plpImageForm->Add(q_pForm1);
    //q_pForm1->show();

}

Input Image

Input

Otsu’s Thresholding and Labeling

Thresholding

- Optimal Thresholding
    - A criterion functions should be devised that yields some measure of separation between regions.
    - The intensity value maximizing(or minimizing) the criterion function is considered as the optimal threshold.

Otsu's Thresholding

Otsu's

result

Otsu's_Thresholding

Code

KImageGray igImg;

    //포커스 된 ImageForm으로부터 영상을 가져옴
    if(_q_pFormFocused != 0 && _q_pFormFocused->ImageGray().Address() &&  _q_pFormFocused->ID() == "OPEN")
    {
        igImg = _q_pFormFocused->ImageGray();

    }
    else
        return;

    //To get its histogramming
    int histo[256] = {0, };
    double sigmab[256] = {0,};
    double N = igImg.Size() ,p,q1,q2,u,u1=0,u2=0,temp_q1,T;
    double max = -1;


    //histogram
    for(unsigned int i=0; i<igImg.Row(); i++){
        for(unsigned int j=0; j<igImg.Col(); j++)
        {
            histo[igImg[i][j]] += 1;
        }
    }


    for(int t = 0; t<255;t++){
       p = (double)histo[t] / (double) N;
       u += ((double)t)*p;
    }

    //Find T
    p = (double)histo[0]/(double)N;

    q1 = p;
    q2 = 1.0 - q1;
    sigmab[0]=q1*q2*(u1-u2)*(u1-u2);


    for(int t=1;t<256;t++)
    {
        p = (double)histo[t]/(double)N;
        temp_q1 = q1;
        q1 += p;
        q2 = 1.0 - q1;
        if(q1 ==0)
        {
            u1=0;
            u2 = (u - q1 * u1) / (1.0 - q1);
        }
        else if(q2 == 0)
        {
            u2=0;
            u1 = ((temp_q1 * u1) + ((double)(t)*p)) / (q1);
        }
        else
        {
            u1 = ((temp_q1 * u1) + ((double)(t)*p)) / (q1);
            u2 = (u - q1 * u1) / (1.0 - q1);
        }

        sigmab[t] = q1*q2*(u1-u2)*(u1-u2);
    }

    for(int i = 0; i < 256; i++)
    {
        if(max < sigmab[i])
        {
            max = sigmab[i];
            T = i;
        }
    }



    //Thresholding
    for(int i=0; i<igImg.Row(); i++)
    {
        for(int j=0; j<igImg.Col(); j++)
        {
            if(igImg[i][j] > T) igImg[i][j] = 255; //foreground
            else igImg[i][j] = 0; //background
        }
    }

Labeling

  • Neighbors
    • 4-Neighbors(상하좌우)
    • 8-Neighbors(상하좌우+대각선) <- Code
  • Algorithm (Binary Image)
    1. 전경인 픽셀일 경우
    2. 이전에 '확인했던' 주변을 확인
    3. 주변이 모두 배경이라면 새로운 label 부여
    4. 주변에 label이 있다면 같은 label 부여
    5. 주변의 label이 여러개인 경우 우선순위에 따라 label 부여
    6. Second Pass를 통해 좀 더 정확한 Labeling

result

Labeling

Code

//Image Labeling

    KImageGray igImg2 = igImg;
    int label[igImg2.Row()][igImg2.Col()];
    std::fill(&label[0][0], &label[igImg2.Row()-1][igImg2.Col()-1], 0);

    int label_num = 1;

    for(int i = 1; i<igImg2.Row()-1;i++)
    {
        for(int j = 1; j<igImg2.Col()-1;j++)
        {
            if(igImg2[i][j] == 255) //foreground
            {
                if( (igImg2[i-1][j-1] == 0 && igImg2[i-1][j] == 0 && igImg2[i][j-1] == 0) || (label[i-1][j-1] == 0 && label[i-1][j] == 0 && label[i][j-1] == 0)) // 대각선 위 오른쪽이 전부 배경
                {
                    label[i][j] = label_num; // label 추가
                    label_num++;
                }
                else if(igImg2[i-1][j-1] == 0 && igImg2[i-1][j] == 255 && igImg2[i][j-1] == 0) //위쪽만 전경
                {
                    label[i][j] = label[i-1][j];
                }
                else if(igImg2[i-1][j-1] == 0 && igImg2[i-1][j] == 0 && igImg2[i][j-1] == 255) //왼쪽만 전경
                {
                    label[i][j] = label[i][j-1];
                }
                else if(igImg2[i-1][j-1] == 255 && igImg2[i-1][j] == 0 && igImg2[i][j-1] == 0) //대각선만 전경
                {
                    label[i][j] = label[i-1][j-1];
                }
                else if(igImg2[i-1][j-1] == 255 && igImg2[i-1][j] == 0 && igImg2[i][j-1] == 255) //대각선이랑 왼쪽만 전경
                {
                    label[i][j] = label[i][j-1];
                    label[i-1][j] = label[i][j-1];
                }
                else if(igImg2[i-1][j-1] == 255 && igImg2[i-1][j] == 255 && igImg2[i][j-1] == 0) //대각선이랑 위쪽만 전경
                {
                    label[i][j] = label[i-1][j];
                    label[i][j-1] = label[i-1][j];
                }
                else if(igImg2[i-1][j-1] == 0 && igImg2[i-1][j] == 255 && igImg2[i][j-1] == 255) //왼쪽이랑 위쪽만 전경
                {
                    label[i][j] = label[i-1][j];
                    label[i][j-1] = label[i-1][j];
                }
                else if(igImg2[i-1][j-1] == 255 && igImg2[i-1][j] == 255 && igImg2[i][j-1] == 255) // 전부 전경
                {
                    label[i][j] = label[i-1][j]; //위쪽 , 왼쪽, 대각선 순 우선순위
                    label[i-1][j-1] = label[i-1][j];
                    label[i][j-1] = label[i-1][j];
                }
            }
        }
    }


    // Second Pass
    for(int i = 1; i<igImg2.Row()-1;i++)
    {
        for(int j = igImg2.Col()-2; j > 1;j--)
        {
            if(igImg2[i][j] == 255) //foreground
            {
                if(igImg2[i-1][j-1] == 0 && igImg2[i-1][j] == 0 && igImg2[i][j-1] == 255) //왼쪽만 전경
                {
                    label[i][j-1] = label[i][j];
                }
                else if(igImg2[i-1][j-1] == 0 && igImg2[i-1][j] == 255 && igImg2[i][j-1] == 0) //위쪽만 전경
                {
                    label[i][j] = label[i-1][j];
                }
                else if(igImg2[i-1][j-1] == 255 && igImg2[i-1][j] == 255 && igImg2[i][j-1] == 255) // 전부 전경
                {
                    label[i][j] = label[i-1][j]; //위쪽 , 왼쪽, 대각선 순 기준
                    label[i-1][j-1] = label[i-1][j];
                    label[i][j-1] = label[i-1][j];
                }

            }
        }
    }


    KImageColor imglabel = KImageColor(igImg2.Row(),igImg2.Col());

    for(unsigned int ii = 1;ii<igImg2.Row();ii++)
              for(unsigned int jj = 1;jj<igImg2.Col();jj++)
          {
              imglabel[ii][jj].b = label[ii][jj];
              imglabel[ii][jj].r = (5* label[ii][jj]) % 256 ;
              imglabel[ii][jj].g = (10* label[ii][jj]) % 256;
          }

dilation and erosion

dilation

- 팽창. mask와 겹치는 픽셀 중 한 픽셀이라도 전경이라면 현재 픽셀은 전경

erosion

- 침식. mask와 겹치는 모든 픽셀이 전경이어야만 현재 픽셀이 전경, 아니라면 배경

result

3x3


3x3

5x5


5x5

Code (3x3, 5x5)

    ImageForm* q_pForm = 0;

        for(int i=0; i<_plpImageForm->Count();i++)
            if((*_plpImageForm)[i]->ID()=="Otsu's Thresholding")
            {
                q_pForm = (*_plpImageForm)[i];
                break;
            }



        KImageGray img_dil = q_pForm->ImageGray();
        KImageGray img_ero = q_pForm->ImageGray();
        KImageGray img_tmp = q_pForm->ImageGray();


        //Dilation
        for(unsigned int i = 1;i<img_dil.Row()-1;i++)
        {
            for(unsigned int j = 1;j<img_dil.Col()-1;j++)
            {
                if(img_tmp[i-1][j-1] == 255 || img_tmp[i-1][j] == 255 || img_tmp[i-1][j+1] == 255 || img_tmp[i][j-1] == 255 || img_tmp[i][j+1] == 255 || img_tmp[i+1][j-1] == 255 || img_tmp[i+1][j] == 255 || img_tmp[i+1][j+1] == 255 )
                    img_dil[i][j] = 255;
            }

        }

        //Eroison
        for(unsigned int i = 1;i<img_ero.Row()-1;i++)
        {
            for(unsigned int j = 1;j<img_ero.Col()-1;j++)
            {
                if(img_tmp[i-1][j-1] == 0 || img_tmp[i-1][j] == 0 || img_tmp[i-1][j+1] == 0 || img_tmp[i][j-1] == 0 || img_tmp[i][j+1] == 0 || img_tmp[i+1][j-1] == 0 || img_tmp[i+1][j] == 0 || img_tmp[i+1][j+1] == 0 )
                    img_ero[i][j] = 0;
            }

        }
    ImageForm* q_pForm = 0;

        for(int i=0; i<_plpImageForm->Count();i++)
            if((*_plpImageForm)[i]->ID()=="Otsu's Thresholding")
            {
                q_pForm = (*_plpImageForm)[i];
                break;
            }

        KImageGray img_dil = q_pForm->ImageGray();
        KImageGray img_ero = q_pForm->ImageGray();
        KImageGray img_tmp = q_pForm->ImageGray();


        //Dilation
        for(unsigned int i = 2;i<img_dil.Row()-2;i++)
        {
            for(unsigned int j = 2;j<img_dil.Col()-2;j++)
            {
                if(img_tmp[i-2][j-2] == 255 || img_tmp[i-2][j-1] == 255|| img_tmp[i-2][j] == 255 || img_tmp[i-2][j+1] == 255 || img_tmp[i-2][j+2] == 255 ||
                   img_tmp[i-1][j-2] == 255 || img_tmp[i-1][j-1] == 255|| img_tmp[i-1][j] == 255 || img_tmp[i-1][j+1] == 255 || img_tmp[i-1][j+2] == 255 ||
                   img_tmp[i][j-2] == 255 || img_tmp[i][j-1] == 255 || img_tmp[i][j+1] == 255 || img_tmp[i][j+2] == 255 ||
                   img_tmp[i+1][j-2] == 255 || img_tmp[i+1][j-1] == 255|| img_tmp[i+1][j] == 255 || img_tmp[i+1][j+1] == 255 || img_tmp[i+1][j+2] == 255 ||
                   img_tmp[i+2][j-2] == 255 || img_tmp[i+2][j-1] == 255|| img_tmp[i+2][j] == 255 || img_tmp[i+2][j+1] == 255 || img_tmp[i+2][j+2] == 255)
                    img_dil[i][j] = 255;
            }

        }

        //Eroison
        for(unsigned int i = 2;i<img_ero.Row()-2;i++)
        {
            for(unsigned int j = 2;j<img_ero.Col()-2;j++)
            {
                if(img_tmp[i-2][j-2] == 0 || img_tmp[i-2][j-1] == 0|| img_tmp[i-2][j] == 0 || img_tmp[i-2][j+1] == 0 || img_tmp[i-2][j+2] == 0 ||
                   img_tmp[i-1][j-2] == 0 || img_tmp[i-1][j-1] == 0|| img_tmp[i-1][j] == 0 || img_tmp[i-1][j+1] == 0 || img_tmp[i-1][j+2] == 0 ||
                   img_tmp[i][j-2] == 0 || img_tmp[i][j-1] == 0 || img_tmp[i][j+1] == 0 || img_tmp[i][j+2] == 0 ||
                   img_tmp[i+1][j-2] == 0 || img_tmp[i+1][j-1] == 0|| img_tmp[i+1][j] == 0 || img_tmp[i+1][j+1] == 0 || img_tmp[i+1][j+2] == 0 ||
                   img_tmp[i+2][j-2] == 0 || img_tmp[i+2][j-1] == 0|| img_tmp[i+2][j] == 0 || img_tmp[i+2][j+1] == 0 || img_tmp[i+2][j+2] == 0 )
                    img_ero[i][j] = 0;
            }

        }

Input Image

Input

Color

color

Sepia Tone Transform Algorithm

1. Transform RGB color to HSV color
2. Change H and S
3. Transform HSV color to RGB

sepia_tone_transform

result

  • HUE : 110, SAT : 0.3

sepia_resultHSV

Code

void MainFrame::on_buttonSepiaTone_clicked()
{
    KImageColor   icMain;

    //포커스 된 ImageForm으로부터 영상을 가져옴

    if(_q_pFormFocused != 0 && _q_pFormFocused->ImageColor().Address() &&  _q_pFormFocused->ID() == "OPEN")
        icMain = _q_pFormFocused->ImageColor();
    else
        return;

    KImageGray img_Hue(icMain.Row(),icMain.Col()),
               img_Sat(icMain.Row(),icMain.Col()),
               img_Val(icMain.Row(),icMain.Col());

    //hue, saturation 값 가져오기
    double dHue2 = ui->spinHue->value();//text().toDouble();
    double dSat2 = ui->spinSaturation->value(); // 위와 같은 식으로

    //
    //icMain 변환
    //:

    double dMin, dMax, dDiff;
    double dVal;
    double C,X,m;
    double R,G,B;
    double dHue,dSat;

    for(int i=icMain.Row(),ii=0; i; i--,ii++)
        for(int j=icMain.Col(),jj=0; j; j--,jj++)
        {
            dMin  = std::min(std::min(icMain[ii][jj].r,icMain[ii][jj].g),icMain[ii][jj].b);
            dMax  = std::max(std::max(icMain[ii][jj].r,icMain[ii][jj].g),icMain[ii][jj].b);
            dDiff = dMax - dMin;

            //value
            dVal = dMax/255.0;
            img_Val[ii][jj]= dVal*255;

            //saturation
            dSat = dDiff/dMax;

            //hue
            if(dMax == (double)(icMain[ii][jj].r)) //maximun = red
                dHue = 60.0 * (double)(icMain[ii][jj].g-icMain[ii][jj].b)/dDiff;
            else if(dMax == (double)(icMain[ii][jj].g))
                dHue = 60.0 * (double)(icMain[ii][jj].b-icMain[ii][jj].r)/dDiff + 120.0;
            else
                dHue = 60.0 * (double)(icMain[ii][jj].r-icMain[ii][jj].g)/dDiff + 240.0;

            if(dHue == 360.0)
                dHue = 0.0;

            img_Hue[ii][jj]=dHue/360.0 * 255;
            img_Sat[ii][jj]=dSat * 255.0;

            dHue = dHue2;
            dSat = dSat2;

            C = dVal*dSat;
            X = C*(1-std::fabs(fmod(dHue/60,2)-1));
            m = dVal - C;

            if(dHue>=0&&dHue<60)
            {
                R = C;
                G = X;
                B = 0;
            }
            else if (dHue>=60&&dHue<120)
            {
                R = X;
                G = C;
                B = 0;
            }
            else if (dHue>=120&&dHue<180)
            {
                R = 0;
                G = C;
                B = X;
            }
            else if (dHue>=180&&dHue<240)
            {
                R = 0;
                G = X;
                B = C;
            }
            else if (dHue>=240&&dHue<300)
            {
                R = X;
                G = 0;
                B = C;
            }
            else if (dHue>=300&&dHue<360)
            {
                R = C;
                G = 0;
                B = X;
            }


            icMain[ii][jj].r=(R+m)*255.0;
            icMain[ii][jj].g=(G+m)*255.0;
            icMain[ii][jj].b=(B+m)*255.0;

        }

    //출력을 위한 ImageForm 생성
    //sepia
    ImageForm*  q_pForm = new ImageForm(icMain, "Sepia Tone", this);
    _plpImageForm->Add(q_pForm);
    q_pForm->show();


    //HSV
    ImageForm*  q_pHue = new ImageForm(img_Hue,"Hue",this);
    _plpImageForm->Add(q_pHue);
    q_pHue->show();

    ImageForm*  q_pSat = new ImageForm(img_Sat,"Sat",this);
    _plpImageForm->Add(q_pSat);
    q_pSat->show();

    ImageForm*  q_pVal = new ImageForm(img_Val,"Val",this);
    _plpImageForm->Add(q_pVal);
    q_pVal->show();


    //UI 활성화 갱신
    UpdateUI();
}

벨만-포드 알고리즘을 그냥 구현하면 되는 문제이다.

나는 https://yabmoons.tistory.com/365 이 사이트를 참고했다.

벨만-포드 알고리즘을 설명해주는 사이트지만 거의 정답..!! 엄청 잘 설명되어있다.

벨만-포드 알고리즘의 핵심은 계산된 노드만 본다 & N-1번 반복 두 개!

 

 

문제 설명을 하자면 From, To, Cost가 주어지고 1번 node에서 다른 node까지의 최소 거리를 구하는 문제이다.

근데 음의 사이클이 하나라도 존재한다면 -1을 출력해야 한다.

 

 

 

한 가지 문제가 발생했던 부분은 자꾸 출력 초과가 발생했던 문제였다.

문제 검색에 찾아보니 underflow 때문에 발생하는 문제였다.

dist의 자료형을 int->long으로 변경했더니 문제가 해결됐다.

 

 

// 타임머신 (골드 4)

//dist를 long으로 안하면 출력 초과가 남 ( underflow 때문에 )

#include <iostream>
#include <limits>

using namespace std;

int N, M;
pair<pair<int, int>, int>* graph;
long* dist;

void Bellman_Ford() {
	int From, To, cost;

	dist[1] = 0;
	
	for (int i = 0;i < N + 1;i++) { //N+1번 반복
		for (int j = 0;j < M;j++) {
			
			From = graph[j].first.first;
			To = graph[j].first.second;
			cost = graph[j].second;

			if (dist[From] == numeric_limits<int>::max()) continue; // 한 번도 방문x 넘김

			if (dist[To] > dist[From] + cost) {
				dist[To] = dist[From] + cost;
			}
		}
	}

	for (int i = 0; i < M;i++) {
		From = graph[i].first.first;
		To = graph[i].first.second;
		cost = graph[i].second;

		if (dist[From] == numeric_limits<int>::max()) continue;
		if (dist[To] > dist[From] + cost) {
			cout << "-1"; return;
		}
	}

	for (int i = 2;i < N + 1;i++) {
		if (dist[i] == numeric_limits<int>::max()) cout << "-1" << '\n';
		else cout << dist[i] << '\n';
	}


}


int main() {

	cin.tie(NULL);
	cout.tie(NULL);
	ios::sync_with_stdio(false);

	cin >> N >> M;

	graph = new pair<pair<int, int>, int>[M];

	dist = new long[N + 1]{};

	for (int i = 0;i < M;i++) {  // From To cost 입력
		cin >> graph[i].first.first >> graph[i].first.second >> graph[i].second;
	}

	for (int i = 1;i < N + 1;i++) {
		dist[i] = numeric_limits<int>::max(); // 거리 inf
	}

	Bellman_Ford();

	delete[] graph, dist;

	return 0;
}

// 2212KB, 8ms

'coding > baekjoon_codingstudy' 카테고리의 다른 글

14891 톱니바퀴 (골드 5)  (0) 2021.10.05
18239 편안한 수열 만들기 (골드 3)  (0) 2021.08.19
4386 별자리 만들기 (골드 4)  (0) 2021.08.15
17404 RGB 거리2 (골드 4)  (0) 2021.08.15
1149 RGB 거리 (실버1)  (0) 2021.08.12

이 문제는 모든 노드가 연결되어 있는 그래프에서 최소 스패닝 트리를 만드는 문제이다.

단, 간선의 가중치가 나와있지 않아서 이것만 미리 구해주면 된다.

 

 

 

이 문제를 풀면서 최소 스패닝 트리에 대해서 공부해보았는데, 

우선 스패닝 트리란 그래프 내의 모든 정점을 포함하는 트리이다.

따라서 최소 스패닝 트리는 그래프 내의 모든 정점을 포함하면서 간선들의 가중치 합이 최소여야 한다.

 

 

최소 스패닝 트리를 만드는 방법은 두 가지 방법이 있는데 나는 그 중 크루스칼 알고리즘을 사용했다.

크루스칼 알고리즘은 가중치를 오름차순으로 정렬한다음 맨 앞의 간선부터 연결해주면 된다.

근데 최소 스패닝 트리이므로 사이클이 생기면 안된다. 그래서 노드들의 부모를 확인해주고 부모가 서로 같다면 연결x, 다르다면 연결하는 방식으로 진행된다.

 

즉, 

1. 가중치가 가장 작은 간선 선택 후 노드 확인

2. 노드들의 부모를 찾음. -> find함수

3. 부모가 같다면 연결하지 않고 넘어감. 부모가 다르다면 최초 부모를 서로 연결해줌 -> Union 함수

이 3가지 단계를 반복해주면 된다.

 

 

// 별자리 만들기 (골드4)
#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>

using namespace std;

pair<double, double>* arr;
vector<pair<double, pair<double, double>>> V;
int N;
int* parent;

void cal() {
	double cost;
	double x1, x2, y1, y2;

	for (int i = 0;i < N;i++) {
		for (int j = i + 1;j < N;j++) {
			x1 = arr[i].first; y1 = arr[i].second;
			x2 = arr[j].first; y2 = arr[j].second;

			cost = sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));


			V.push_back(make_pair(cost, make_pair(i,j)));
		}
	}

	sort(V.begin(), V.end());

	/*for (int i = 0;i < 3;i++) {
		cout << V[i].second.first << " " << V[i].second.second << " " << V[i].first << endl;
	}*/

	delete[] arr;

}

int find(int x) {
	if (parent[x] == x) return x;
	return parent[x] = find(parent[x]);
}

void Union(int x, int y) {
	x = find(x);
	y = find(y);

	parent[y] = x;
}


int main() {
	double Ans = 0;

	cin >> N;

	arr = new pair<double, double>[N];
	parent = new int[N];

	for (int i = 0;i < N;i++) {
		cin >> arr[i].first >> arr[i].second;
		parent[i] = i;
	}

	cal();
	
	//cout << endl << endl;

	for (int i = 0;i < V.size();i++) {
		//cout << V[i].second.first << " " << V[i].second.second << endl;
		if (find(V[i].second.first) != find(V[i].second.second)) {
			Union(V[i].second.first,V[i].second.second);
			Ans += V[i].first;
		}
	}

	cout.precision(3);
	cout << Ans;

	return 0;
}

// 2432KB, 0ms

'coding > baekjoon_codingstudy' 카테고리의 다른 글

14891 톱니바퀴 (골드 5)  (0) 2021.10.05
18239 편안한 수열 만들기 (골드 3)  (0) 2021.08.19
11657 타임머신 (골드 4)  (0) 2021.08.15
17404 RGB 거리2 (골드 4)  (0) 2021.08.15
1149 RGB 거리 (실버1)  (0) 2021.08.12

1149 RGB 거리 문제에 조건 하나만 더 추가된 문제이다.

 

1149 문제는 1번은 2번과, N번은 N-1번과 다른 색이어야 하고, 1과 N을 제외한 나머지 i번째는 i-1번째 집과 i+1째 집과 다른 색이어야 하는 문제였다.

17404 문제는 1번과 N번이 다른 색이어야 하는 조건이 추가되었다.

 

 

 

이건 1149 문제와 같은 점화식을 사용한다.

더보기

d[i][0] = Min(d[i - 1][1], d[i - 1][2]) + a[0];
d[i][1] = Min(d[i - 1][0], d[i - 1][2]) + a[1];

d[i][2] = Min(d[i - 1][0], d[i - 1][1]) + a[2];

단, 1번째 집이 R을 선택했을 경우 N번째 집은 R을 선택하지 못한다는 것만 주의해주면 된다.

 

 

 

해결 방식은 1번이 무조건 R/G/B를 고르게 한 뒤에 N번은 1번이 고른 색과 다른 색을 골라서 그 두 가지 경우를 비교한 후 값이 작은 수를 저장해놓고 이를 3번 반복하는 것이다.

 

무조건 1번이 R/G/B를 고르게 하는 방법은 고를 색 빼고는 엄청 큰 값을 넣어주면 된다.

 

 

// RGB 거리 2 (골드 4)

#include <iostream>

using namespace std;

//점화식: d[i][0] = Min(d[i - 1][1], d[i - 1][2]) + a[0];
//		  d[i][1] = Min(d[i - 1][0], d[i - 1][2]) + a[1];
//		  d[i][2] = Min(d[i - 1][0], d[i - 1][1]) + a[2];

int** d;
int** RGB;
int N;

void dynamic(int x) {

	if (x == 0) return;

	dynamic(x - 1);

	d[x][0] = min(d[x - 1][1], d[x - 1][2]) + RGB[x][0];
	d[x][1] = min(d[x - 1][0], d[x - 1][2]) + RGB[x][1];
	d[x][2] = min(d[x - 1][0], d[x - 1][1]) + RGB[x][2];

		//cout << d[x][0] << " " << d[x][1] << " " << d[x][2] << endl;

}

int main() {
// 입력
	cin >> N;

	RGB = new int* [N + 1]{};
	d = new int* [N + 1]{};
	d[0] = new int[3]{};
	RGB[0] = new int[3]{};
	for (int i = 1;i < N + 1;i++) {
		d[i] = new int[3]{};
		RGB[i] = new int[3]{};
		cin >> RGB[i][0] >> RGB[i][1] >> RGB[i][2];
	}

// 풀이
	int Ans;
	int G_1 = RGB[1][1], B_1 = RGB[1][2];

	RGB[1][1] = 10000; RGB[1][2] = 10000;

	//1번집 R
	dynamic(N);
	Ans = min(d[N][1], d[N][2]);

		//cout << endl << endl;


	//1번집 G
	RGB[1][0] = 10000; RGB[1][1] = G_1; RGB[1][2] = 10000;
	dynamic(N);
	if (Ans > min(d[N][0], d[N][2])) Ans = min(d[N][0], d[N][2]);

		//cout << endl << endl;


	//1번집 B
	RGB[1][0] = 10000; RGB[1][1] = 10000; RGB[1][2] = B_1;
	dynamic(N);
	if (Ans > min(d[N][0], d[N][1])) Ans = min(d[N][0], d[N][1]);
	
		//cout << endl << endl;

	cout << Ans;

	return 0;
}

// 2020KB, 0ms

'coding > baekjoon_codingstudy' 카테고리의 다른 글

14891 톱니바퀴 (골드 5)  (0) 2021.10.05
18239 편안한 수열 만들기 (골드 3)  (0) 2021.08.19
11657 타임머신 (골드 4)  (0) 2021.08.15
4386 별자리 만들기 (골드 4)  (0) 2021.08.15
1149 RGB 거리 (실버1)  (0) 2021.08.12

 

다이나믹 프로그래밍을 이용한 문제이므로 점화식을 구해야 했다.

점화식은 i가 R을 선택하는 경우(d[i][0]), G를 선택하는 경우(d[i][1]), B를 선택하는 경우(d[i][2])가 있으므로 총 점화식은 3개!

(i의 최솟값을 고르는게 최선의 경우가 아닐 수 있으므로 R,G,B를 각각 선택한 경우를 구하는 것이다.)

 

 

점화식: d[i][0] = Min(d[i - 1][1], d[i - 1][2]) + a[0];
          d[i][1] = Min(d[i - 1][0], d[i - 1][2]) + a[1];
          d[i][2] = Min(d[i - 1][0], d[i - 1][1]) + a[2];

 

나올 수 있는 경우의 수는 다음과 같다.

1번 집 -> R G B

2번 집 -> R 선택 : GR, BR   중 min

             G 선택 : RG, BG   중 min

             B 선택 : RB, GB    중 min

3번 집 -> R 선택 : RGR, BGR, RBR, GBR    중 min

             G 선택 : GRG, BRG, RBG, GBG    중 min

             B 선택 : GRB, BRB, RGB, BGB     중 min

                         '

                         '

                         '

N번 집 -> .............

 

 

 

다음과 같은 예제를 이용해서 점화식을 이해해보자면,

  R G B
1 1 100 200
2 1 201 101
3 202 102 1

1번 집 -> R(1) G(100) B(200)

2번 집 -> R 선택 : GR(100+1), BR(200+1)  

             G 선택 : RG(200+201), BG(1+201)   

             B 선택 : RB(1+101), GB(100+101)   

3번 집 -> R 선택 : RGR, BGR, RBR, GBR   

             G 선택 : GRG, BRG, RBG, GBG    

             B 선택 : GRB, BRB, RGB, BGB     

 

3번 집의 경우에서 취소선은 이미 2번집에서 걸러진 경우이다. 따라서 항상 2가지 경우의 수만 남으므로 점화식이 성립한다는 것을 볼 수 있다.

 

 

코드는 다음과 같다.

// RGB 거리 (실버1)
#include <iostream>

using namespace std;

//점화식: d[i][0] = Min(d[i - 1][1], d[i - 1][2]) + a[0];
//		  d[i][1] = Min(d[i - 1][0], d[i - 1][2]) + a[1];
//		  d[i][2] = Min(d[i - 1][0], d[i - 1][1]) + a[2];

int** d;
int** RGB;

void dynamic(int x) {

	if (x == 0) return;

	dynamic(x - 1);

	d[x][0] = min(d[x - 1][1], d[x - 1][2]) + RGB[x][0];
	d[x][1] = min(d[x - 1][0], d[x - 1][2]) + RGB[x][1];
	d[x][2] = min(d[x - 1][0], d[x - 1][1]) + RGB[x][2];

}

int main() {
	int N; cin >> N;

	RGB = new int* [N + 1]{};
	d = new int* [N + 1]{};
	d[0] = new int[3]{};
	RGB[0] = new int[3]{};
	for (int i = 1;i < N + 1;i++) {
		d[i] = new int[3]{};
		RGB[i] = new int[3]{};
		cin >> RGB[i][0] >> RGB[i][1] >> RGB[i][2];
	}

	dynamic(N);

	cout << min(d[N][0],min(d[N][1],d[N][2]));

	return 0;
}

// 2020KB , 0ms

'coding > baekjoon_codingstudy' 카테고리의 다른 글

14891 톱니바퀴 (골드 5)  (0) 2021.10.05
18239 편안한 수열 만들기 (골드 3)  (0) 2021.08.19
11657 타임머신 (골드 4)  (0) 2021.08.15
4386 별자리 만들기 (골드 4)  (0) 2021.08.15
17404 RGB 거리2 (골드 4)  (0) 2021.08.15

+ Recent posts