Search code examples
iosmatrixdepth-first-searchbreadth-first-search

How to convert irregular connected regions in a 2D matrix into rectangles in iOS?

I have a 513*513 matrix, which indicate the result of person segmentation.

Now I wanna convert irregular connect regions into rectangles.

It looks like the image below:

1

My code is:

func findConnectedRegion(matrix: [[Int]]) -> [[(Int, Int)]] {
        var result: [[(Int, Int)]] = []
        //    var visited: Set<(Int, Int)> = []
        var visited: Set<String> = []
        let numRows = matrix.count
        let numCols = matrix[0].count
        
        for i in 0..< numRows {
            for j in 0..< numCols {
                let position = (i, j)
                self.str = String(i)+"-"+String(j)
                if matrix[i][j] == 15 && !visited.contains(self.str) {
                    var region: [(Int, Int)] = []
                    dfs(matrix: matrix, rows: numRows,cols: numCols,position: position, visited: &visited, region: &region)
                    result.append(region)
                }
            }
        }
        
        return result
    }
    
    func dfs(matrix: [[Int]],rows:Int,cols:Int,position: (Int, Int), visited: inout Set<String>, region: inout [(Int, Int)]) {
//        let numRows = matrix.count
//        let numCols = matrix[0].count
        
        let numRows = rows
        let numCols = cols
        
        let (row, col) = position
        self.str = String(position.0)+"-"+String(position.1)
        
        // Check if the current position is within bounds and is part of the region
        guard row >= 0, row < numRows, col >= 0, col < numCols, matrix[row][col] == 15, !visited.contains(self.str) else {
            return
        }
        
        visited.insert(self.str)
        region.append(position)
        
        // Explore neighbors in all four directions
        dfs(matrix: matrix,rows: numRows,cols: numCols, position: (row - 1, col), visited: &visited, region: &region)  // Up
        dfs(matrix: matrix, rows: numRows,cols: numCols,position: (row + 1, col), visited: &visited, region: &region)  // Down
        dfs(matrix: matrix, rows: numRows,cols: numCols,position: (row, col - 1), visited: &visited, region: &region)  // Left
        dfs(matrix: matrix, rows: numRows,cols: numCols,position: (row, col + 1), visited: &visited, region: &region)  // Right
    }

But it always has an error like Thread 1: EXC_BAD_ACCESS (code=2, address=0xxxxxxx) 2

It looks like a stack overflow error, but I'm not sure. And how can I to solve this?

The arrayFile is here: https://gofile.io/d/Ijmok8

And convert it to array by:

if let data = try? Data(contentsOf: filePath, options: .mappedIfSafe), 
let array = try? JSONSerialization.jsonObject(with: data, options: .mutableLeaves) {
                            
                        }

What I wanna do is make the irregular connected regions by 15 become rectangles.

Then draw the image by:

func drawImage(array: [[Int]], completion: @escaping (UIImage?) -> Void) {
        let m = array.count
        let n = array[0].count
        let size = CGSize(width: m, height: n)
        

        DispatchQueue.global(qos: .userInitiated).async {
            let renderer = UIGraphicsImageRenderer(size: size)
            

            let image = renderer.image { (context) in

                let cgContext = context.cgContext
                
                let black = UIColor.black
                let white = UIColor.white

                for j in 0..<n {
                    for i in 0..<m {
                        let value = array[i][j]
                        let rect = CGRect(x: i, y: j, width: 1, height: 1)
                        if value == 15 {
                            
                            cgContext.setFillColor(black.cgColor)
                            cgContext.fill(rect)
                            
                        } else {
                            cgContext.setFillColor(white.cgColor)
                            cgContext.fill(rect)
                        }
                        
                    }
                }
            }
            
            DispatchQueue.main.async {
                completion(image)
            }
            
            
        }

The result is not same as the top-right image, it's OK if it show rectangle(s).

Thanks

Solution

  • Likely, yes, you're hitting a memory error due to the huge Set of String...

    I made a few edits to your code to use a Set<CGPoint> instead and no longer get the crash (also added a little code to draw rects around the shapes):

    // we want to use a Set of CGPoint
//  so we need to make it Hashable
extension CGPoint : Hashable {
    public func hash(into hasher: inout Hasher) {
        hasher.combine(x)
        hasher.combine(y)
    }
}

class MatrixVC: UIViewController {
    
    let imgView = UIImageView()
    
    override func viewDidLoad() {
        super.viewDidLoad()
        
        view.backgroundColor = .systemYellow
        
        imgView.translatesAutoresizingMaskIntoConstraints = false
        view.addSubview(imgView)
        let g = view.safeAreaLayoutGuide
        NSLayoutConstraint.activate([
            imgView.topAnchor.constraint(equalTo: g.topAnchor, constant: 20.0),
            imgView.leadingAnchor.constraint(equalTo: g.leadingAnchor, constant: 20.0),
            imgView.trailingAnchor.constraint(equalTo: g.trailingAnchor, constant: -20.0),
        ])
        
        guard let filePath = Bundle.main.url(forResource: "arrayFile", withExtension: "json") else { fatalError() }
        
        if let data = try? Data(contentsOf: filePath, options: .mappedIfSafe),
           let array = try? JSONSerialization.jsonObject(with: data, options: .mutableLeaves),
           let a = array as? [[Int]]
        {
            let t = findConnectedRegion(matrix: a)
            
            var rects: [CGRect] = []
            
            for i in 0..<t.count {
                let mnx = t[i].min(by: { $0.0 < $1.0 }) ?? (0, 0)
                let mxx = t[i].max(by: { $0.0 < $1.0 }) ?? (0, 0)
                let mny = t[i].min(by: { $0.1 < $1.1 }) ?? (0, 0)
                let mxy = t[i].max(by: { $0.1 < $1.1 }) ?? (0, 0)
                
                let r: CGRect = .init(x: mnx.0, y: mny.1, width: mxx.0 - mnx.0, height: mxy.1 - mny.1)
                rects.append(r)
            }
            
            drawImage(array: a, rects: rects, completion: { img in
                guard let img = img else { fatalError() }
                self.imgView.heightAnchor.constraint(equalTo: self.imgView.widthAnchor, multiplier: img.size.height / img.size.width).isActive = true
                self.imgView.image = img
            })

        }
    }
    
    func drawImage(array: [[Int]], rects: [CGRect], completion: @escaping (UIImage?) -> Void) {
        let m = array.count
        let n = array[0].count
        let size = CGSize(width: m, height: n)
        
        DispatchQueue.global(qos: .userInitiated).async {
            let renderer = UIGraphicsImageRenderer(size: size)
            
            let rectColors: [UIColor] = [
                .systemRed, .systemGreen, .systemBlue
            ]
            
            let image = renderer.image { (context) in
                let cgContext = context.cgContext
                
                let black = UIColor.black
                let white = UIColor.white
                
                for j in 0..<n {
                    for i in 0..<m {
                        let value = array[i][j]
                        let rect = CGRect(x: i, y: j, width: 1, height: 1)
                        if value == 15 {
                            
                            cgContext.setFillColor(black.cgColor)
                            cgContext.fill(rect)
                            
                        } else {
                            cgContext.setFillColor(white.cgColor)
                            cgContext.fill(rect)
                        }
                        
                    }
                }
                
                for i in 0..<rects.count {
                    cgContext.setStrokeColor(rectColors[i % rectColors.count].cgColor)
                    cgContext.stroke(rects[i])
                }
                
            }
            
            DispatchQueue.main.async {
                completion(image)
            }
            
            
        }
    }
    
    var curPoint: CGPoint = .zero
    
    func findConnectedRegion(matrix: [[Int]]) -> [[(Int, Int)]] {
        var result: [[(Int, Int)]] = []
        var visitedPoints: Set<CGPoint> = []
        let numRows = matrix.count
        let numCols = matrix[0].count
        
        for i in 0..<numRows {
            for j in 0..<numCols {
                let position = (i, j)
                self.curPoint = .init(x: i, y: j)
                if matrix[i][j] == 15 && !visitedPoints.contains(self.curPoint) {
                    var region: [(Int, Int)] = []
                    dfsP(matrix: matrix, rows: numRows,cols: numCols,position: position, visited: &visitedPoints, region: &region)
                    result.append(region)
                }
            }
        }
        return result
    }
    
    func dfsP(matrix: [[Int]],rows:Int,cols:Int,position: (Int, Int), visited: inout Set<CGPoint>, region: inout [(Int, Int)]) {
        let numRows = rows
        let numCols = cols
        
        let (row, col) = position
        self.curPoint = .init(x: position.0, y: position.1)
        
        // Check if the current position is within bounds and is part of the region
        guard row >= 0, row < numRows, col >= 0, col < numCols, matrix[row][col] == 15, !visited.contains(self.curPoint) else {
            return
        }
        
        visited.insert(self.curPoint)
        region.append(position)
        
        // Explore neighbors in all four directions
        dfsP(matrix: matrix,rows: numRows,cols: numCols, position: (row - 1, col), visited: &visited, region: &region)  // Up
        dfsP(matrix: matrix, rows: numRows,cols: numCols,position: (row + 1, col), visited: &visited, region: &region)  // Down
        dfsP(matrix: matrix, rows: numRows,cols: numCols,position: (row, col - 1), visited: &visited, region: &region)  // Left
        dfsP(matrix: matrix, rows: numRows,cols: numCols,position: (row, col + 1), visited: &visited, region: &region)  // Right
    }
    
}

    Result:

    enter image description here

    I used your json file... don't know if this would run into problems again if you had a larger array - I'll leave that up to you to test.

    As a side note, you may want to look into VNDetectContoursRequest with the Vision framework.