In this lesson, we will explore the phenomenon of traversing in two-dimensional (2D) arrays via a certain fixed-size 2-D window.

We will explore both mutually exclusive and inclusive traversals.

Press + to interact

main.cpp

SW.txt

#include <iostream>
#include <fstream>
#include <iomanip>
using namespace std;
#define MaxRows 100
#define MaxCols 100
void load(const char fileName[], int M[][MaxCols], int &Rows, int &Cols, int &wr, int &wc, int &strideR, int &strideC)
{
	ifstream Rdr(fileName);
	Rdr >> Rows >> Cols >> wr >> wc >> strideR >> strideC;
	for (int r = 0; r < Rows; r++)
		for (int c = 0; c < Cols; c++)
			Rdr >> M[r][c];
}
void displayGrid(const char Name[], int M[][MaxCols], int Rows, int Cols)
{
	cout << Name << ": {\n\n";
	for (int r = 0; r < Rows; r++)
	{
		for (int c = 0; c < Cols; c++)
			cout << setw(4) << M[r][c];
		cout << endl;
	}
	cout << "}\n\n";
}
void displayAWindow(int M[][MaxCols], int wsr, int wsc, int wr, int wc)
{
	// Displaying a window anchored at (wsr, wsc) of the size of wrxwc
	cout << "{\n";
	for (int r = 0; r < wr; r++)	// the window is of wr-rows
	{
		cout << "   ";
		for (int c = 0; c < wc; c++)	// the window is of wc-columns
			cout << setw(3) << M[wsr + r][wsc + c] << " ";
		// anchored at (wsc, wsc) hence shifted 
		cout << endl;
	}
	cout << "}";
}
void displayAllWindows(int M[][MaxCols], int Rows, int Cols, int wr, int wc, int strideR = 1, int strideC = 1)
{
	cout << "All the windows of: \t" << wr << " x " << wc << "\nAnd stride of: \t\t" << strideR << " x " << strideC << endl << endl;
	for (int r = 0; 
        r + wr <= Rows;	// one window is of wr size, hence no further stride
		    r += strideR)	// r should be incremented by strideR size
	{
		for (int c = 0; 
            c + wc <= Cols;	// one window is of wc size, hence no further stride
			    c += strideC)	// c should be incremented by strideC size
		{
			cout << "Anchored At:[" << r << "," << c << "]: \n";
			displayAWindow(M, r, c, wr, wc);
			// anchored at[r, c] and of the size wr x wc
			cout << endl << endl;
		}
	}
}
void displayAllWindowsMutuallyExclusively(int M[][MaxCols], int Rows, int Cols, int wr, int wc)
{   // Exercise 1
	cout << "All the mutually exclusive windows of: \t" << wr << " x " << wc  << endl << endl;
	// Write your code here
}
int main()
{
	int M[MaxRows][MaxCols], Rows, Cols, wr, wc, strideR, strideC;
	load("SW.txt", M, Rows, Cols, wr, wc, strideR, strideC);
	displayGrid("\n\nThe Matrix M[][] ", M, Rows, Cols);
	displayAllWindows(M, Rows, Cols, wr, wc, strideR, strideC);
	// displayAllWindowsMutuallyExclusively(M, Rows, Cols, wr, wc);
	// Exercise 1: uncomment above line of displayAllWindowsMutuallyExclusively() call
	// and comment line with displayAllWindows() function call.
	return 0;
}

The load() function reads the data from the file “SW.txt”. It reads the original 2-D array along with its dimensions, required window and stride sizes.

Format of SW.txt

Each line in the “SW.txt” file contains six integers (e.g., on line 1, we have 6, 6, 2, 2, 1, 1) that represent the following respectively:

Array rows
Array columns
Window rows
Window columns
Row-wise stride
Column-wise stride

Inside the load() function, we read these values (lines 11–12) followed by the 2-D array values in lines 13–15. The function ifstream is an input (characters) file stream reader that reads the data from the file “SW.txt” (look at it in the playground to see what this function is loading).

The function displayGrid() displays the 2-D array. The setw() in C++ is used to set the width of the next message to be displayed. For instance, setw(4) means the variable will take 4 minimum number of character spaces.

The function displayAWindow() displays a single window, which is called inside the displayAllWindows() function to display all the windows.

By row and column strides (strideR and strideC), we mean the number of rows and columns the sliding window shifts/jumps after each iteration, respectively.

In the code above, the window size is 2x2, stored in wr and wc along with the strideR and strideC as 1x1 (read from the file “SW.txt”). Change these values to 3x3 and then 4x4 and the stride to 2x2 and then 3x3 or any other value of your choice to see how the program displays the possible windows.

eTo do this, write the code in the displayAllWindowsMutuallyExclusively() function. It will be very similar to displayAllWindows(). The only change is that we increment r and c by window rows (wr) and window columns (wc), respectively, instead of incrementing by strideR and strideC (lines 51 and 55).

The sample output should be the following:


The Matrix is: {

   1   0   1   0
   2   0   2   0
   3   0   3   0
   4   0   4   0
}

All the windows of: 2 x 2
And stride of: 	    2 x 2

Anchored At: [0,0]: 
{
	  1   0 
	  2   0 
}

Anchored At: [0,2]: 
{
	  1   0 
	  2   0 
}

Anchored At: [2,0]: 
{
	  3   0 
	  4   0 
}

Anchored At: [2,2]: 
{
	  3   0 
	  4   0 
}

Instruction: Add the displayAllWindowsMutuallyExclusively() function and uncomment the function call from main() and execute the program. The output should have all the mutually exclusive sliding windows.

Exercise 2: Finding the window with the maximum sum

In this exercise, we are going to find the window that has the maximum sum.

Sample Program



The Matrix is: {

   1   0   1   0   1   0
   2   0   2   0   2   0
   3   0   3   0   3   0
   4   0   4   0   4   0
   5   6   5   0   5   0
   6   9   6   0   6   0
}


Max window of 2x2 is: 
{
	  5   6 
	  6   9 
} 
anchored at [4,0] and has the sum of 26

The windowSum() function computes the sum of a window.

To find and maintain the maximum sum from all windows, we have created the findMaxWindow() function.

Like finding the maximum from an array, we assume the first window to have the maximum sum in Max. We then find the sum of all the windows one by one in WinSum and update Max if the WinSum is greater than Max.

Instruction: Write the code in the playground below and complete this function.

In the function findMaxWindow(), we are receiving mwr and mwc as references, and this function’s responsibility is to assign the anchor position of the maximum window in these two variables. Along with that, the function must also return the maximum sum value.

Look at the animations to understand how your program should calculate the maximum sum window.

Press + to interact

Exercise 3: Cancer Detection

You are given a black-and-white image of a skin cancer sample, stored in a matrix data of dimensions $M \times N$ – meaning $M$ rows and $N$ columns The matrix data consists of only 0s and 1s where:

0 represents a black pixel.
1 represents a white pixel.

The task is to find the largest square window that contains at least 70% of black pixels, which constitutes a cancerous portion. This window will be identified by its starting index and the size that your function needs to return.

Note: Keep in mind that there can be more than one window with at least 70% black pixels; however, you have to find the one with the maximum size (and for the largest fixed $K$ , if there are multiple windows that qualify for cancerous regions, then return the one that has the maximum cancer cells and the one that appears first).

Constraint: Window size $K \times K \le M \times N$ , where $K \ge 2$ .

Functions

The following specifies the functions you need to implement and briefly explains their purpose.

The `countBlackPixels()` function

The countBlackPixels() function computes the number of black pixels for a given window.

Signature

int countBlackPixels(int data[][MaxCols], int sr, int sc, int k);

Parameters

int data[][MaxCols]: This is the matrix that contains the image pixels.
int sr: This is the starting row of the window.
int sc: This is the starting column of the window.
int k: This is the window size.

The `isCancerousRegion()` function

The isCancerousRegion() function determines whether the number of black pixels of the specified window size constitutes a cancerous region (meaning, whether the window contains at least 70% black pixels).

Signature

bool isCancerousRegion(int K, int zeroCount);

Parameters

int K: This represents the window size.
int zeroCount: This specifies the number of black pixels.

The `searchCancerRegion()` function

The searchCancerRegion() function utilizes the countBlackPixels() and isCancerousRegion() functions to find the largest region with black pixels greater than 70% of the pixels in that region.

Signature

void searchCancerRegion(int data[][MaxCols], int &cr, int &cc, int &k)

Parameters

int data[][MaxCols]: This is the matrix that contains the image pixels.
int &cr: This should contain the starting row of the cancerous region found.
int &cc: This should contain the starting column of the cancerous region found.
int &k: This should contain the window size of the cancerous region found.

Press + to interact

main.cpp

cancer.txt

#include <iostream>
#include <fstream>
#include <iomanip>
using namespace std;
#define MaxRows 100
#define MaxCols 100
void loadImageMap(const char fName[], int Map[][MaxCols], int &rows, int &cols)
{
    ifstream Rdr(fName);
    Rdr>>rows>>cols;
    for(int r=0; r<rows; r++)
    {
        for(int c=0; c<cols; c++)
        {
            Rdr>>Map[r][c];
        }
    }
}
void displayMap(int Map[][MaxCols], int rows, int cols)
{
    for(int r=0; r<rows; r++)
    {
        for(int c=0; c<cols; c++)
        {
            cout <<Map[r][c] << " ";
        }
        cout << endl;
    }
}
void displayWindowMap(int Map[][MaxCols], int rows, int cols, int cr, int cc, int cK)
{
    for(int r=0; r<rows; r++)
    {
        for(int c=0; c<cols; c++)
        {
            if (r >= cr && c >= cc && r < cr + cK && c < cc + cK)
                cout <<Map[r][c] << " ";
            else
                cout << "* ";
        }
        cout << endl;
    }
}
bool isCancerousRegion(int K, int zeroCount)
{
    // Write your implementation here
}
int countBlackPixels(int data[][MaxCols], int sr, int sc, int k)
{
	// Write your implementation here
}
void searchCancerRegion(int data[][MaxCols], int rows, int cols, int &cr, int &cc, int &cK)
{
    // Write your implementation here
}
int main()
{
	int imageMap[MaxRows][MaxCols], rows, cols;
    int cr, cc, cK;
    loadImageMap("cancer.txt",imageMap, rows, cols);
    displayMap(imageMap, rows, cols);
    searchCancerRegion(imageMap, rows, cols, cr, cc, cK);
    if(cK==-1)
    {
        cout << "\nCancer not found...!\n";
    }
    else
    {
        cout << "\nCancer found....!\n";
        cout << "Size: "<< cK<<"x"<<cK<<"\t at: ("<<cr <<","<< cc << ")" <<endl;
        displayWindowMap(imageMap, rows, cols, cr, cc, cK); // Prints the map with only the window pixels highlighted
    }
	
	return 0;
}

Getting Started

Computing in the Real World

Introduction to C++ (Table Printing)

GNU Debugger Tutorial

Memory, Operations and Control Structure

Divide, Conquer, and Rule

Iteration, Reusability and Extensibility

Introduction to Arrays

Problem Solving With Arrays

Multi-dimensional Arrays

Sliding Window

Conclusion

Search via Sliding Window in 2-D Array

Sliding window traversal

Implementation

Exercise 1: Displaying all mutually exclusive windows in a 2-D array

Exercise 2: Finding the window with the maximum sum

Exercise 3: Cancer Detection

Functions

The `countBlackPixels()` function

The `isCancerousRegion()` function

The `searchCancerRegion()` function

Getting Started

Computing in the Real World

Introduction to C++ (Table Printing)

GNU Debugger Tutorial

Memory, Operations and Control Structure

Divide, Conquer, and Rule

Iteration, Reusability and Extensibility

Introduction to Arrays

Problem Solving With Arrays

Multi-dimensional Arrays

Sliding Window

Conclusion

Search via Sliding Window in 2-D Array

Sliding window traversal

Implementation

Exercise 1: Displaying all mutually exclusive windows in a 2-D array

Exercise 2: Finding the window with the maximum sum

Exercise 3: Cancer Detection

Functions

The countBlackPixels() function

The isCancerousRegion() function

The searchCancerRegion() function

The `countBlackPixels()` function

The `isCancerousRegion()` function

The `searchCancerRegion()` function