Suppose we are given an r x s matrix M that contains only O's and 1's....

   

Transcribed Image Text:

Suppose we are given an r x s matrix M that contains only O's and 1's. It is a bitmap of an image. The O's represent the background while the 1's indicate the presence of an object. The 1's that are adjacent horizontally or vertically are part of the same object. We want to know how many objects appear in the bitmap. For example, the matrix on the left indicates that there are three objects while the matrix on the right indicates there are two objects in the image. [00000] 101 10 0 1 1 0 0 [1 0 0 0 0] 100 10 1 1 1 0 0 1 0 0 0 0 1 0 0 0 0 Given M, our goal is to design a graph-based algorithm that returns the number of objects detected by M. Suppose we are given an r x s matrix M that contains only O's and 1's. It is a bitmap of an image. The O's represent the background while the 1's indicate the presence of an object. The 1's that are adjacent horizontally or vertically are part of the same object. We want to know how many objects appear in the bitmap. For example, the matrix on the left indicates that there are three objects while the matrix on the right indicates there are two objects in the image. [00000] 101 10 0 1 1 0 0 [1 0 0 0 0] 100 10 1 1 1 0 0 1 0 0 0 0 1 0 0 0 0 Given M, our goal is to design a graph-based algorithm that returns the number of objects detected by M.