Find the Grid of Region Average in Java
In this tutorial, we are going to find the grid of region average in Java. A grayscale image represented by a 0-indexed m x n grid image is presented to us; each image[i][j] represents a pixel whose intensity falls between the interval [0..255]. Additionally, a non-negative integer threshold is provided. An area is a 3 × 3 subgrid in which the absolute difference in intensity between any two neighboring pixels is less than or equal to the threshold. A pixel can belong to more than one region, but every pixel inside a region is a part of that region. A 3x3 rectangle that defines each pixel's neighborhood is centered around every pixel in the image. If the neighboring pixels in this 3x3 zone meet a certain set of criteria, we have to find the average value of all the pixels in the region for every pixel in the image. If |a - c| + |b - d| == 1, then two pixels, image[a][b] and image[c][d], are said to be adjacent.
Examples:
Example 1:
Input: image = [[2, 3, 3, 4], [4, 5, 5, 6], [6, 7, 7, 8]], threshold = 2
Output: [[5, 5, 5, 5], [5, 5, 5, 5], [5, 5, 5, 5]]
Explanation: Two sections can be seen in this image: one has intensity values of 2 and 3, and the other has values of 4, 5, 6, 7, and 8. For the first region, the average intensity is (2 + 3) / 2 = 2.5, which is rounded to 3. (4 + 5 + 6 + 7 + 8) / 5 = 6, which is already an integer, is the average intensity of the second zone. The average intensities of the two regions are rounded to the closest integer. Each pixel in the result therefore belongs to either the first region, the second region, or both, and so has an intensity of 5.
Example 2:
Input: image = [[1, 1, 1, 1], [2, 2, 2, 2], [3, 3, 3, 3] and threshold = 1
Output: [[2, 2, 2, 2], [2, 2, 2, 2], [2, 2, 2, 2]
Explanation: There are two sections in this picture: one with an intensity value of 1, and the other with values of 2 and 3. In the first zone, the average intensity is 1, and in the second, it is (2 + 3) / 2 = 2.5, rounded to 2. Since each pixel is a part of either the first region, the second region, or both, every pixel in the result has an intensity of 2.
Naïve approach:
The simplistic method simply computes every pixel and every pixel that it is adjacent to by brute force, resulting in an O(n * m * 9) time complexity, where n is the number of rows and m is the number of columns in the input image. The method is less effective than the optimized method included in the given code, which makes use of the 3x3 areas' structure to minimize the number of calculations.
Filename: GridOfRegion.java
public class GridOfRegion { public int[][] calculateRegionAverages(int[][] image, int threshold) { int numRows = image.length; int numColumns = image[0].length; int[][] regionAverages = new int[numRows - 2][numColumns - 2]; // Grid for storing averages by region for (int j = 0; j + 2 < numRows; ++j) { for (int k = 0; k + 2 < numColumns; ++k) { boolean isRegion = true; int sum = 0; int count = 0; // Repeat over all of the pixels in the 3x3 area. for (int m = 0; m < 3; ++m) { for (int n = 0; n < 3; ++n) { int diffX = Math.abs(image[j + m][k + n] - image[j][k]); int diffY = Math.abs(image[j + m][k + n] - image[j + 2][k + 2]); isRegion &= (diffX <= threshold) && (diffY <= threshold); if (isRegion) { sum += image[j + m][k + n]; count++; } } } // Determine the average if the region satisfies the threshold requirement. if (isRegion) { regionAverages[j][k] = sum / count; } else { regionAverages[j][k] = -1; // Declare that this area is not meeting the threshold. } } } return regionAverages; } public static void main(String[] args) { // Given sample example image int[][] image = { {1, 2, 3, 4, 5}, {5, 2, 5, 4, 5}, {2, 2, 3, 4, 5}, {4, 4, 3, 4, 5}, {6, 6, 3, 4, 5} }; int threshold = 2; GridOfRegion gridregion = new GridOfRegion(); int[][] regionAverages = gridregion.calculateRegionAverages(image, threshold); for (int j = 0; j < regionAverages.length; j++) { for (int k = 0; k < regionAverages[0].length; k++) { System.out.print(regionAverages[j][k] + " "); } System.out.println(); } } }
Output:
-1 -1 4 -1 -1 4 -1 -1 4
Time complexity: The time complexity of the program is O(n * m).
Space complexity: The space complexity of the program is O(n * m).
Approach: Iterative Region-Based Average
Step 1: Iterate over each pixel in the input image using nested loops. It considers each pixel as the center of a 3x3 region and processes it accordingly.
Step 2: Check whether the surrounding 3x3 region meets a certain condition (isRegion method). The condition involves comparing the pixel values of neighboring pixels with the central pixel's value and checking if they are within a specified threshold.
Step 3: Calculate the sum of pixel values within that region (getSubgridSummethod), if the condition for the 3x3 region is met.
Step 4: Maintain two additional 2D arrays (sums and counts) to accumulate the sums of pixel values and the counts of pixels in each region.
Step 5: Calculate the average value for each pixel based on the accumulated sums and counts after processing all regions.
Filename: RegionAveraging.java
public class RegionAveraging { public int[][] calculateRegionOfGrid(int[][] image, int threshold) { final int numRows = image.length; final int numColumns = image[0].length; int[][] sums = new int[numRows][ numColumns]; int[][] counts = new int[numRows][ numColumns]; for (int j = 0; j < numRows - 2; ++j) for (int k = 0; k < numColumns - 2; ++k) if (isRegion(image, j, k, threshold)) { final int subgridSum = getSubgridSum(image, j, k); for (int a = j; a < j + 3; ++a) for (int b = k; b < k + 3; ++b) { sums[a][b] += subgridSum / 9; counts[a][b] += 1; } } for (int j = 0; j < numRows; ++j) for (int k = 0; k < numColumns; ++k) if (counts[j][k] > 0) image[j][k] = sums[j][k] / counts[j][k]; return image; } private boolean isRegion(int[][] image, int j, int k, int threshold) { for (int a = j; a < j + 3; ++a) for (int b = k; b < k + 3; ++b) { if (a > j && Math.abs(image[a][b] - image[a - 1][b]) > threshold) return false; if (b > k && Math.abs(image[a][b] - image[a][b - 1]) > threshold) return false; } return true; } private int getSubgridSum(int[][] image, int j, int k) { int subgridSum = 0; for (int a = j; a < j + 3; ++a) for (int b = k; b < k + 3; ++b) subgridSum += image[a][b]; return subgridSum; } public static void main(String[] args) { // Given input example image int[][] image = { {1, 2, 3, 4, 5}, {5, 2, 5, 4, 5}, {2, 2, 3, 4, 5}, {4, 4, 3, 4, 5}, {6, 6, 3, 4, 5} }; int threshold = 2; RegionAveraging regionaveraging = new RegionAveraging(); int[][] result = regionaveraging.calculateRegionOfGrid(image, threshold); // Print the result grid for (int[] row : result) { for (int value: row) { System.out.print(value + " "); } System.out.println(); } } }
Output:
1 2 4 4 4 5 2 4 4 4 2 2 4 4 4 4 4 4 4 4 6 6 4 4 4
Time complexity: The time complexity of the program is O(mn).
Space complexity: The space complexity of the program is O(nm).