Find the peak of each islands in sparse matrix

I have a sparse matrix that contains several islands of unknown size. I would like to find the highest peak of each islands. Consider this matrix as an example:

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

In this case I would like to get the position of 3 at (3, 2), the position of 4 at (3, 4) and the position of 1 at (5, 4), (5, 5) or (5, 6). Note: I consider 4-connected neighbours.

Until now I came up with the solution that scans each pixel and if it is not zero it starts a flood fill from that pixel. The flood fill paints the pixels to zero keeping track the maximum value visited. This algorithm works well but I was wondering if there are any faster solution?

In my target platform (iOS) I have access to different vector processing frameworks like BLAS, LAPACK, vDSP that provide some functions for fast finding the maximum value in a vector (or matrix). Maybe one could implement a faster solution with the help of these functions?

4

I once had to solve the exact same problem, as part of commercial image processing software. In the end I opted for a scan-line implementation, because it reads the matrix only once.

Basically, you consider a single row of the matrix and keep track of all ‘events’ on this scan line. Events are left and right edges of islands. Note that the same island might have multiple left and right edges on the same scan line. Also note that what seems to be 2 seperate islands on your scan line, might turn out to be the same island later.

You also keep a record of each known island with its highest value.

You start with the top row, initialize the events. And then go down one row at a time, each time revealing one more row of the matrix and updating the events. Next to updating the position of the existing events, you need consider also the following topology-changes:

  1. Start (top) of new land: a new island record, and new left and right edges are inserted in the scan line.
  2. End (bottom) of a piece of land: a left and right event are removed from the scan line.
  3. Top of a lake/sea: An island that splits into 2 seperate peninsulae of the same island (2 new events)
  4. Bottom of a lake/sea: two peninsulae merge into one. If they didn’t already belong to the same island records, then these 2 island records need to be merged.

2

If I understand correctly, it would seem that you’re doing it in the most efficient way. Let me try to summarize your algorithm:

Main:
For each pixel in image:
  If pixel is non-zero:
    Call flood subroutine with pixel.
  End
End

Flood subroutine:
Acquire all neighboring pixels of passed pixel of the same height.
Peak = true
For each pixel 
  If pixel has neighboring pixel with higher height
    Peak = false
    Call flood subroutine with pixel with higher height
  End
End
If Not Peak
  For each pixel
    Set pixel height to 0
  End
Else
  Add peak to list
End

This means that although technically you’re passing every pixel in the image to perform this flooding subroutine, if a lot of the pixels share the same height, you will later hit a lot of 0 height pixels that were set by the subroutine.

You could probably even optimize this a bit to both select all pixels of the same height as well as determine if there are neighboring pixels with higher height in the same algorithm to avoid having to perform that check afterwards.

The only problem with this algorithm is that it may be rather memory heavy, since it uses recursion to hold the pixels with the same color. You could probably improve on this a bit by selecting the neighboring pixels with higher height, setting currently selected pixels to 0 if found, then freeing the resources prior to calling the flood subroutine for each pixel with higher height.

I hope that helps.

4

If I understand your current algorithm correctly it is:

loop through all n values in your matrix looking for non 0 ones in O(n)
for each of island, flood fill over the m non zero elements and set them to 0 in O(m)

given you matrix is sparse i.e. n >> m then this algorithm is going to be O(n) complexity.

We can get better complexity by using a data structure that doesn’t store the 0s. for instance if you added your non 0 data to a dictionary with the key being the index of the data (i,j) then we can still get any data in O(1) and rely on a key not being present meaning the value is 0.

we can then for each non zero element we haven't looked at yet, run the flood fill 
and remove every key we look at from the dictionary in a complexity of O(m).

Now your question doesn’t ask for a lower algorithmic complexity solution but a faster one, is this new algorithm going to help?

Well, it depends:

  • If your matrix is big enough and sparse enough then this should outperform your current implementation. For a smaller matrix you original algorithm may well end up being faster as it could well have smaller constant factors.
  • Can you even change your data structures? (answer here appears to be no)

2

Sounds like a variation of blob coloring. (Google is your FRIEND!)

You’re going to make a list of blobs, initially empty. Scan for a nonzero value. When you find one, do 4-way-connectivity to find the blob pixels, and call the “color” the highest value. When you run out of 4-way-connected pixels, restart your scan to find a new blob.

I believe this is an example of Disjoints Sets where
Island: Set
Peak: Great Number of the set (or “Set’s parent”)

I would go with “Disjoint Sets Forest” where each sets keeps a pointer to the “peak” of the island.

https://en.wikipedia.org/wiki/Disjoint-set_data_structure

Give it a try. Good luck.

Trang chủ Giới thiệu Sinh nhật bé trai Sinh nhật bé gái Tổ chức sự kiện Biểu diễn giải trí Dịch vụ khác Trang trí tiệc cưới Tổ chức khai trương Tư vấn dịch vụ Thư viện ảnh Tin tức - sự kiện Liên hệ Chú hề sinh nhật Trang trí YEAR END PARTY công ty Trang trí tất niên cuối năm Trang trí tất niên xu hướng mới nhất Trang trí sinh nhật bé trai Hải Đăng Trang trí sinh nhật bé Khánh Vân Trang trí sinh nhật Bích Ngân Trang trí sinh nhật bé Thanh Trang Thuê ông già Noel phát quà Biểu diễn xiếc khỉ Xiếc quay đĩa Dịch vụ tổ chức sự kiện 5 sao Thông tin về chúng tôi Dịch vụ sinh nhật bé trai Dịch vụ sinh nhật bé gái Sự kiện trọn gói Các tiết mục giải trí Dịch vụ bổ trợ Tiệc cưới sang trọng Dịch vụ khai trương Tư vấn tổ chức sự kiện Hình ảnh sự kiện Cập nhật tin tức Liên hệ ngay Thuê chú hề chuyên nghiệp Tiệc tất niên cho công ty Trang trí tiệc cuối năm Tiệc tất niên độc đáo Sinh nhật bé Hải Đăng Sinh nhật đáng yêu bé Khánh Vân Sinh nhật sang trọng Bích Ngân Tiệc sinh nhật bé Thanh Trang Dịch vụ ông già Noel Xiếc thú vui nhộn Biểu diễn xiếc quay đĩa Dịch vụ tổ chức tiệc uy tín Khám phá dịch vụ của chúng tôi Tiệc sinh nhật cho bé trai Trang trí tiệc cho bé gái Gói sự kiện chuyên nghiệp Chương trình giải trí hấp dẫn Dịch vụ hỗ trợ sự kiện Trang trí tiệc cưới đẹp Khởi đầu thành công với khai trương Chuyên gia tư vấn sự kiện Xem ảnh các sự kiện đẹp Tin mới về sự kiện Kết nối với đội ngũ chuyên gia Chú hề vui nhộn cho tiệc sinh nhật Ý tưởng tiệc cuối năm Tất niên độc đáo Trang trí tiệc hiện đại Tổ chức sinh nhật cho Hải Đăng Sinh nhật độc quyền Khánh Vân Phong cách tiệc Bích Ngân Trang trí tiệc bé Thanh Trang Thuê dịch vụ ông già Noel chuyên nghiệp Xem xiếc khỉ đặc sắc Xiếc quay đĩa thú vị
Trang chủ Giới thiệu Sinh nhật bé trai Sinh nhật bé gái Tổ chức sự kiện Biểu diễn giải trí Dịch vụ khác Trang trí tiệc cưới Tổ chức khai trương Tư vấn dịch vụ Thư viện ảnh Tin tức - sự kiện Liên hệ Chú hề sinh nhật Trang trí YEAR END PARTY công ty Trang trí tất niên cuối năm Trang trí tất niên xu hướng mới nhất Trang trí sinh nhật bé trai Hải Đăng Trang trí sinh nhật bé Khánh Vân Trang trí sinh nhật Bích Ngân Trang trí sinh nhật bé Thanh Trang Thuê ông già Noel phát quà Biểu diễn xiếc khỉ Xiếc quay đĩa
Thiết kế website Thiết kế website Thiết kế website Cách kháng tài khoản quảng cáo Mua bán Fanpage Facebook Dịch vụ SEO Tổ chức sinh nhật