I need to make a pattern detection code, with the following conditions:
Given an image (square matrix) A[N,N], if point P(X,Y) is the center of a star, the following condition will be satisfied:
(1) A[X][j]=255, for all 0<=j<N (The values in the Xth row are all 255)
(2) A[i][Y]=255, for all 0<=i<N (The values in the Yth column are all 255)
(3)
A[X i][Y i]=255, for all -N<=i<N if 0<=(X i)<N and 0<=(Y i)<N
A[X i][Y-i]=255, for all -N<=i<N if 0<=(X i)<N and 0<=(Y-i)<N
(The values of two diagonals from the centers are all 255)
I would like to know a way to effectively solve this problem quickly.
What I have tried:
The way that my program works is as follows:
- receive the input matrix
- create an empty copy 2d matrix
- scan for full row values whilst scanning. -> add the value of a the detected row into the copy
- scan for full column values-> add the value of a the detected col into the copy
- scan for full diagonal values -> same as above
- scan for full anti-diagonal values. -> same as above
- iterate through the copy matrix, and the center of a star will be found with a point which has been intersected 4 times.
With simple testcases, my code works, but it fails in the online judge, and also have time limit issues.
Full code down here:
#include<stdio.h>
int constellation[2048][2048];
int copy[2048][2048]={};
int main()
{
int a,size;
int totalrow=0, totalcol=0;
scanf("%d", &a);
scanf("%d", &size);
for(int i=0; i<a; i ){
for(int row=0; row<size; row ){
for(int col=0; col<size; col ){
scanf("%d", &constellation[row][col]);
constellation[row][col]=(constellation[row][col]== 255)?1:0;
totalrow =constellation[row][col];
}
if(totalrow==size)
{
for(int col = 0; col<size; col )
copy[row][col] =1;
}
totalrow=0;
}
for(int row=0; row<size; row ){
for(int col=0; col<size; col )
totalcol =constellation[col][row];
if(totalcol==size)
for(int x=0; x<size; x )
copy[x][row] =1;
totalcol=0;
}
int totaldiagonal=0, i=0, j=0;
for(int k=0; k<=size-1; k )
{
i=k;
j=0;
while(i>=0)
{
totaldiagonal =constellation[i][j];
i-=1;
j =1;
}
//printf("j=%d\n", j);
if(totaldiagonal==j && totaldiagonal!=0){
i=k;
j=0;
while(i>=0){
copy[i][j] =1;
i-=1;
j =1;
}
}
totaldiagonal=0;
}
totaldiagonal=0;
//checking for the same diagonal, but the patterns changed, need new for loop.
for(int k=1; k<=size-1; k ){
i=size-1;
j=k;
while(j<=size-1)
{
totaldiagonal =constellation[i][j];
i-=1;
j =1;
}
//printf("i=%d\n", size-i);
//printf("total diagonal=%d\n", totaldiagonal);
if(totaldiagonal== size-i-1){
i=size-1;
j=k;
//printf("masuk\n");
while(j<=size-1){
copy[i][j] =1;
i-=1;
j =1;
}
}
totaldiagonal=0;
}
//-----------------------------------------------------------------------------------------------
int max=0;
for(int j=0; j<size ;j )
{
max=0;
int i=size-1;
int y=j;
while(y>=0)
{
max ;
totaldiagonal =constellation[i][y];
i--;
y--;
}
if(max==totaldiagonal){
//printf("inside\n");
int i=size-1;
int y=j;
while(y>=0)
{
//printf("coordinates: x=%d, y=%d\n", i,y);
//printf("data: %d", constellation[i][y]);
copy[i][y] =1;
i--;
y-=1;
}
}
totaldiagonal=0;
//printf("repeat\n");
}
for(int k=size-1; k>=0; k--)
{
max=0;
i = k-1;
j = size-1;
while(i>=0)
{
max ;
totaldiagonal =constellation[i][j];
i--;
j--;
}
if(totaldiagonal==max)
{
i=k-1;
j=size-1;
while(i>=0)
{
copy[i][j] =1;
i--;
j--;
}
}
totaldiagonal=0;
}
int counter=0;
/*
for(int i=0; i<size; i ){
for(int j=0; j<size; j ){
printf("%d ", constellation[i][j]);
}
printf("\n");
}
printf("\n");
*/
for(int i=0; i<size; i ){
for(int j=0; j<size; j ){
if(copy[i][j]>=4 && i>0 && i<size-1 && j>0 && j<size-1) counter ;
//i have checked whether the edges could be or not be a center of star, but still no difference
//printf("%d ", copy[i][j]);
}
//printf("\n");
}
printf("%d\n", counter);
}
return 0;
}
CodePudding user response：
My first thought:
Create 8 arrays of bits (or a single array of 8-bit numbers), with the same size as the image.
Each array corresponds to one of the directions. A bit in the array should be true if there is a white line (in the specific direction) from the corresponding pixel to the edge of the image.
In other words,
arr1[i][j]should be true ifinput[i][j]is white andarr1[i-1][j]is true (offset is different for each array).If all 8 arrays have
trueelements in the same location, this location is a star.To fill the arrays according to this rule, you do two passes over the input image. The second pass should be in reverse.
The first pass can fill 4 of the 8 arrays (which ones should be self-evident: it only makes sense to examine neighbors that were already traversed).
The second pass can fill the 4 remaining arrays.
The second pass can also check if thet current pixel is a star (if all 8 arrays have
trueelements in the same location), and increment a counter if it's the case.
In pseudocode, the first pass could look like this:
for y = 0..n-1
for x = 0..n-1
if input[x][y] == 255
if arr1[x-1][y]
arr1[x][y] = true
if arr2[x-1][y-1]
arr2[x][y] = true
if arr3[x][y-1]
arr3[x][y] = true
if arr4[x 1][y-1]
arr4[x][y] = true
You also need special handling for the image borders, to avoid accessing `arr??` out of bounds.
The second pass would be exactly the same, except you should be iterating in reverse, and should be filling the other 4 arrays.
CodePudding user response：
I would first go for a simpler problem. Consider that stars only have horizontal and vertical lines going through them. To find out which horizontal and vertical lines are completely white, just count the number of white pixels in each of them, and at the end compare the count with the width and height of the image. This is very cheap if you do it while reading the input:
int rowsums[size] = {0};
int colsums[size] = {0};
for (int row=0; row<size; row ) {
for (int col=0; col<size; col ) {
int value;
scanf("%d", &value);
rowsums[row] = value;
colsums[col] = value;
}
}
Note that we no longer need the two-dimensional arrays, we just have two one-dimensional arrays to store information about the image.
Now you can get the positions of the stars by checking for each pixel if it's in a full row or full column:
for (int row=0; row<size; row ) {
if (rowsums[row] != size * 255)
continue;
for (int col=0; col<size; col ) {
if (colsums[col] != size * 255)
continue;
printf("Star at %d, %d\n", row, col);
}
}
That second pass is still O(N²). However, if you first scan rowsums and colsums and create new arrays that only hold the row and column indices of those rows and columns that are fully white, you reduce the problem to O(N number_of_stars). If you only need to count, then it's just O(N), since you just need to multiply the number of fully white rows with the number of fully white columns to get the number of stars.
Now try to expand this approach to build the sum of pixel values of all the possible diagonals.