Take the 2-minute tour ×

This is part of image processing algorithm where more optimization is expected. We have a large sparse matrix consisting of 0's and 1's. In this sparse matrix there are one or more dense region of 1's. Lets say the whole matrix represents an image and 0 represent non-video areas and 1 represents video areas. Basically All nearby 1's should be grouped together to find out the more approximate video region. So drawing a boundary around all 1's will give exact video areas in a image.

enter image description here

As shown in the above matrix of 0's and 1's. There are 4 dense areas of 1's. We have tried a naive approach which is of more time complexity and further improvements expected.

The approach we tried is converting all 0's in a block size of 3*3 or 2*2 if the number of 1's in the block are above a certain threshold value. But even this approach doesnt give us the exact boundary of video blocks.

So looking for a better algorithm which is good in both time and space complexity. Actually this calculation need to be done in real time so algorithm must have a very less time complexity. It would be great if we can achieve in O(n) linear time.

share|improve this question
It is nice of you to post your homework assignment, but what have you done on it? –  user85109 Jan 19 '13 at 14:16
It is not a homework kind of thing. What I am looking for is nothing but an approach. Implementation I can do. I tried sweep line algorithm suggested by Philips and It worked properly after some editing. thanks @philips –  vicky Jan 27 '13 at 13:23
add comment

1 Answer

up vote 1 down vote accepted

The usual approach here is to apply a sweep line algorithm.

Basically, it works as follows: Look at each column. If it consists of all zeros, move on to the next column. If it contains 1's, save the smallest and largest vertical positions (they are likely candidates for rectangle coordinates). As you move the sweep line further, adjust your candidates accordingly. If you have found candidates and reach a line consisting of all zeros, your coordinate candidates are the actual coordinates of the rectangle.

You may as well (or additionally) sweep vertically and examine rows instead of columns.

Depending on the properties of your matrix (or your task), there are a lot of different possible solutions. Consider the following matrix:

1 1 1
1 1 1
1 1 1

How many rectangles does it contain? 1? 9? 4?

In your example, the two touching rectangles may as well be regarded as part of one larger rectangle.

Some advice: state your problem more clearly.

share|improve this answer
In the above scenario whole matrix represents our desktop screen areas. Where 1 represents areas where some animation or video is being rendered and 0 represents all other areas. All the 0's in between 1's are actually animation or video only but not temporarily due to less motion. So by detecting all 0's inside 1's we can ensure those temporarily areas as animation or video. That's why we need to detect the bounding rectangles. –  vicky Jan 21 '13 at 9:19
Yes Philip in the matrix you shown it will consider that as 1. –  vicky Jan 27 '13 at 13:24
add comment

Your Answer


