ACM圖像壓縮算法C++

Question

我一直在試圖獲得在C++更好的，所以我一直在解決設計的編程競賽的問題。我幾天前開始這個問題，並且無法爲我的生活解決它。我需要一些關於我的算法的幫助，以及如何解決它。這就是問題所在：ACM Image Compression problem

我的代碼：我下面解釋。

#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的方形，因爲把它分成四個部分正確。然而，隨着8×8平方...如果它需要被分解成小於四個部分，一切都打亂了。

我知道爲什麼它這樣做。我的放大遞歸函數的算法是錯誤的。如果正方形是一個8×8 ...參數會像

0，8,0，8 =看着整個廣場

0,4，4,8 =頂部右

利用角球4×4 0，2，6，8 =看着最小的頂部的2由2

我只是不知道數學右

方功能會得到我所需要的。我不知道如何解決這個8×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

首先，你的閱讀程序存在一些問題：

第二陣列創建循環是錯誤的，應該使用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常規：

你要找的公式是不是火箭科學，就來看看下面的圖片中：

就partitionate一樣，位圖，使各自的調用來work每一個部門（看不到的top/bottom使用 - right/left v ariables想到這裏）

你的算法是遞歸的一個，但沒有最初的情況下，讓你的算法執行下去，你應該檢查是否有遞歸調用之前start和end之間的差爲0。

有另一個警告，但是你首先應該繼續

IMO之前修復這些了，你解決這個問題的想法是好的，只需要一點點打磨

希望這有助於！

PS：是一個很好的（如果不是最好的之一）的做法，申請一般的軟件開發OOP的基本面（如類），但對於編程競賽考慮時間因素和的軟件複雜性開發出來的解決方案並不差，但考慮到在很多情況下它可能會導致你浪費時間並增加一些不必要的複雜性