c++ - ACM 画像圧縮アルゴリズム C++

Question

私は C++ を上達させようとしてきたので、プログラミング コンテスト用に設計された問題を解決してきました。私はこの問題を数日前に始めましたが、一生解決することはできません。アルゴリズムとその修正方法について助けが必要です。これが問題です: ACM 画像圧縮の問題

MY CODE: 以下で説明します。

#include "Compress.h"
using namespace std;

Compress::Compress(){
    size = 0, threshold = 0, nRows=0, nCols=0;
    // Enter in a file name
    cout << "Welcome. Please type in the name of the file to read the numbers.\n";
    cin >> readFileName;

    inFile.open(readFileName.c_str());
    if(!inFile.is_open()) {
        cout << "Failed to open the file! Press Enter to exit..." << endl;
        exit(1);
    }

    //Finding the array size and threshold
    inFile >> size >> threshold;

    nRows = size;
    nCols = size;
    topright = size;
    bottomleft = size;

    //Let's make the array
    // creating the columns
    compressArray = new int* [nCols];

    // creating the rows
    for (int r = 0; r < nRows; r++){
        compressArray[r] = new int[nRows];
    }

    // FIll the array
    for (int i = 0; i < nRows; i++){
        for (int j = 0; j < nCols; j++){
            inFile >> compressArray[i][j];
        }
    }

    inFile.close();

    // Show before editing.
    print();
    work(0, nRows, 0, nCols);

}
Compress::~Compress(){
    for (int i = 0; i < nRows; i ++){
        delete compressArray[i];
    }
    delete [] compressArray;
}


void Compress::work(int start_x, int end_x, int start_y, int end_y){
    int nb_blacks = 0;
    int nb_whites = 0;
    int total_blocks = 0;
    int majority = 0;
    int percent = 0;

     cout << start_x << end_x << start_y << end_y << "\n------\n";

    for(int i = start_x; i < end_x; i++){
        for(int j = start_y; j < end_y; j++){
            if(compressArray[i][j] == 1){
                nb_blacks++;
            }
        }
    }

    total_blocks = ((end_x - start_x) * (end_y - start_y));
    nb_whites = total_blocks - nb_blacks;

    // give the max back
    majority = max(nb_blacks, nb_whites);
    // find the percent of the highest amount of colored blocks.
    percent = ((majority*100)/total_blocks);

    cout << "\n----\nPercent: " << percent << " Threshold: " << threshold  << endl;



    // majority/total_blocks is determining the percent of the greater
    // color in the box. We are comparing it to the threshold percent.
    if (percent >= threshold){
        for(int i = start_x; i < end_x; i++){
            for(int j = start_y; j < end_y; j++){
                if(nb_blacks > nb_whites) compressArray[i][j] = 1;
                else compressArray[i][j] = 0;
            }
        }
    }
    else {
            topright = topright/2;
            bottomleft = bottomleft/2;

            work(start_x, (end_x/2), (topright), end_y);
            work(start_x, (end_x/2), start_y, (end_y/2));
            work((bottomleft), end_x, start_y, (end_y/2));
            work((bottomleft), end_x, (topright), end_y);

    }

}

void Compress::print(){
    for (int r = 0; r < nRows; r++){
        for (int c = 0; c < nCols; c++){
            cout << compressArray[r][c];
        }
        cout << endl;
    }
}

したがって、私のプログラムが行うことは、画像内の黒い四角の数 (1) を数えることです。次に、それを白い四角 (0) の数と比較します。どちらが大きいかは、画像内の正方形の数に基づいてパーセントに変換されます。それをしきい値と比較します。しきい値がパーセントよりも小さい場合... 画像全体が多数色になりました。

しきい値が高い場合... 再帰的な 4 つの部分に分割してズームインします。右上から始まり、左上、左下、右下の順に進みます。

私のプログラムは、正しく 4 つの部分に分割されるため、4 x 4 の正方形で動作します。ただし、8 x 8 の正方形では... 4 つ未満の部分に分割する必要がある場合は、すべてが台無しになります。

なぜこれを行うのか知っています。再帰関数をズームするアルゴリズムが間違っています。正方形が 8 x 8 の場合...パラメータは次のようになります

0, 8, 0, 8 = 正方形全体を見ている

0、4、4、8 = 右上

4 x 4 0、2、6、8 を使用したコーナー = 最小の右上を見る

2 x 2 の 2 乗。

必要なものを取得する数学関数がわかりません。これを 8 x 8 の正方形に修正する方法がわかりません。私のコードを修正することさえ可能ですか? それとも、別の方法を考え出す必要がありますか? もしそうなら、どのように？

ありがとうございました

Answer 1

修正しました！数学関数はただの苦痛でした。

ヘッダー機能

#include<cstdlib>
#include<iostream>
#include<string>
#include<fstream>


using namespace std;

class Compress{
    public:
        Compress();
        ~Compress();
        void input();
        void work(int start_x, int end_x, int start_y, int end_y);
        void print();

    private:
        int size;
        int threshold;
        int** compressArray;
        int nRows, nCols;

        string readFileName;
        ifstream inFile;
};

CPPファイル

#include "Compress.h"
using namespace std;

Compress::Compress(){
    size = 0, threshold = 0, nRows=0, nCols=0;
    // Enter in a file name
    cout << "Welcome. Please type in the name of the file to read the numbers.\n";
    cin >> readFileName;

    // Open the file.
    inFile.open(readFileName.c_str());
    if(!inFile.is_open()) {
        cout << "Failed to open the file! Press Enter to exit..." << endl;
        exit(1);
    }

    //Finding the array size and threshold
    inFile >> size;

    nRows = size;
    nCols = size;

    // Enter a threshold.
    cout << "Enter the desired threshold between 50-100: ";
    cin >> threshold;

    // Keep asking for the desired threshold until it is given.
    while (threshold < 50 || threshold > 100){
        cout << "\nIncorrect Threshold.\n";
        cout << "Enter the desired threshold between 50-100: ";
        cin >> threshold;
    }


    //Let's make the array
    // creating the columns
    compressArray = new int* [nCols];

    // creating the rows
    for (int r = 0; r < nRows; r++){
        compressArray[r] = new int[nCols];
    }

    // FIll the array
    for (int i = 0; i < nRows; i++){
        for (int j = 0; j < nCols; j++){
            inFile >> compressArray[i][j];
        }
    }

    inFile.close();

    // Show before editing.
    print();
    work(0, nRows, 0, nCols);

}
Compress::~Compress(){
    for (int i = 0; i < nRows; i ++){
        delete compressArray[i];
    }
    delete [] compressArray;
}


void Compress::work(int start_x, int end_x, int start_y, int end_y){
    int Size = end_y - start_y; // Finding the midpoints.
    int nb_blacks = 0;
    int nb_whites = 0;
    int total_blocks = 0;
    int majority = 0;
    int percent = 0;

//    Testing everything.

//    cout << "\nx1, y1: " << start_x << "," << start_y << " x2,y2: " << end_x << "," << end_y << endl;
//    for (int r = start_x; r < end_x; r++){
//        for (int c = start_y; c < end_y; c++){
//            cout << compressArray[r][c];
//        }
//        cout << endl;
//    }

    // Initial case. If 1, break and start returning results
    if (end_x <= start_x || end_y <= start_y){
        return;
    }

   //  Keep breaking it down until it reaches 1.
    else {
        // Count the Number of Black pieces
        for(int i = start_x; i < end_x; i++){
            for(int j = start_y; j < end_y; j++){
                if(compressArray[i][j] == 1){
                    nb_blacks++;
                }
            }
        }

        // Find the total and number of white pieces.
        total_blocks = ((end_x - start_x) * (end_y - start_y));
        nb_whites = total_blocks - nb_blacks;

        // give the max back
        majority = max(nb_blacks, nb_whites);
        // find the percent of the highest amount of colored blocks.
        percent = ((majority*100)/total_blocks);

//        cout << "Percent: " << percent << " Threshold: " << threshold  << "\n-----\n";


        // majority/total_blocks is determining the percent of the greater
        // color in the box. We are comparing it to the threshold percent.
        if (percent >= threshold){
            for(int i = start_x; i < end_x; i++){
                for(int j = start_y; j < end_y; j++){
                    if(nb_blacks > nb_whites) compressArray[i][j] = 1;
                    else compressArray[i][j] = 0;
                }
            }
        }

        // Keep breaking down until we reach the initial case.
        else {
            work((end_x - (Size/2)), (end_x), (start_y), (start_y + (Size/2)));
            work(start_x, (start_x + (Size/2)), (start_y), (start_y + (Size/2)));
            work((start_x), (start_x + (Size/2)), (end_y - (Size/2)), end_y);
            work((end_x - (Size/2)), end_x, (end_y - (Size/2)), end_y);
//
//            work((start_x), (mid_x), (mid_y), end_y);
//            work(start_x, (mid_x ), (start_y), (mid_y));
//            work((mid_x), end_x, start_y, (mid_y));
//            work((mid_x), end_x, (mid_y), end_y);
        }
    }
}

void Compress::print(){

    // Print the function
    cout << "\nImage: " << threshold << "%\n";
    for (int r = 0; r < nRows; r++){
        for (int c = 0; c < nCols; c++){
            cout << compressArray[r][c];
        }
        cout << endl;
    }
}

Answer 2

まず第一に、あなたの読書習慣にはいくつかの問題があります。

2 番目の配列作成ループは間違っています。nCols代わりにループの制限として使用する必要がありnRowsます。

// creating the rows
for (int r = 0; r < nCols; r++){
    // Remember you're creating the "row"s for every column
    compressArray[r] = new int[nRows];
}

問題の列挙に基づいて、入力形式にはビットマップ ピクセル間にスペースが含まれていないため、データの行を読み取ってから、行を反復処理して個々の文字を抽出する必要があります。

// FIll the array
for (int i = 0; i < nRows; i++){
    // You should #include <string> for this to work
    string line;
    inFile >> line;
    for (int j = 0; j < nCols; j++) 
        compressArray[i][j] = line[j] - '0';
}

work読み取りが完了したら、ルーチンにいくつかの改善を追加できます。

あなたが探している式はロケット科学ではありません。次の画像を見てください。

そのようにビットマップを分割し、すべてのセクターに対してそれぞれの呼び出しを行うだけです（ここで考えた-変数workの使用は見られません）top/bottomright/left

あなたのアルゴリズムは再帰的なものですが、初期ケースがないため、アルゴリズムは無期限に実行されます。再帰呼び出しの前にstartとの差が 0 であるかどうかを確認する必要があります。end

別の警告がありますが、続行する前にまずこれらを修正する必要があります

IMO、この問題を解決するためのあなたのアイデアは良いですが、少し磨く必要があります

お役に立てれば！

PS: 一般的なソフトウェア開発に OOP の基礎 (クラスなど) を適用するのは、(ベストではないにしても) 本当に良い方法ですが、プログラミング コンテストでは、開発されたソリューションの時間要因とソフトウェアの複雑さを考慮することは悪くありません。ただし、多くの場合、時間を無駄にし、不要な複雑さを追加する可能性があることを考慮してください。