algorithm - Constrained maximization of the sum of square submatrices -

algorithm - Constrained maximization of the sum of square submatrices -

i have intensity map of image select sub-regions big average value. this, want find sub-regions maximize sum of intensity map pixels covered sub-regions. prevent excessive number of returned sub-regions, penalty applied each additional sub-region returned. additionally, fine if 2 sub-regions overlap, overlap objective value of union of sub-regions.

more formally, suppose have matrix a containing non-negative values dimensions m x n. cover matrix square sub-matrices dimension s x s such sum of values of a covered union of area of squares maximized. each square add together solution, constant penalty p subtracted objective value of solution.

for instance, consider next matrix:

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

with parameters p = -4 , s = 2. optimal solution 2 squares s1 = [1, 2; 1, 2] , s2 = [2, 1; 2, 2] coordinates (2:3,2:3) , (2:3,4:5) respectively (in matlab notation). note in illustration greedy approach of incrementally adding squares maximum value until no squares can added (without decreasing objective value) fails.

one brute forcefulness way of solving check possible combinations using k squares. starting k =1, compute optimal combination k squares, increment k , repeat until objective value stops increasing. expensive.

you can precompute sums of values of (m-s+1)*(n-s+1) possible squares in time o(mn) using integral image.

is there efficient solution this?

the problem np-hard. proven reduction planar minimum vertex cover. proof special case s=3, p=2, , having values 0 or 1 identical proof other question.

as brute forcefulness solution, made more efficient if instead of trying combinations increasing k, add together squares incrementally. when objective value of partial solution plus sum of not-yet-covered values not greater best-so-far objective value, rollback lastly valid combination removing added square(s) , seek other squares. avoid adding squares add together 0 objective value. avoid adding sub-optimal squares: if in illustration op partial solution contains square [1, 2; 1, 2], not add together square [2, 2; 2, 2] because [2, 1; 2, 2] @ to the lowest degree or better. , reorder squares in such way plenty solution, allows terminate farther attempts sooner.

algorithm optimization matrix