How to solve such a system of nonlinear equations?

My specific problem is: on a fixed (320*320) size image, there are 2 known object-detection boundingboxes, shown in green in the figure, The problem is that only the width and height (W and H) of another object-detection boundingbox(red color) are known, how to determine the x and y of the red object-detection boundingbox so that its intersection with all other green object-detection boundingboxes is 0 (All IOU=0)?

The object-detection boundingboxes is represented by four elements [x, y, w, h], respectively representing the x coordinate, y coordinate, rectangle width and height of the upper left corner of the image.

In the following example, the solution set of the coordinate range of the upper left corner of the red object-detection boundingbox should be {0<x<20,150<y<220}, but the program cannot solve it，and I tried to solve my problem in 2 ways, but I still can't get my answer. Why?

-------------------------------------------------------------------------------------------------------------------------------------------------------------------

我的具体问题是：在一副固定（320*320）大小尺寸的图像上，有2个已知的目标检测框，在图中用绿色显示，问题是仅已知另外一个检测框的宽和高（W和H)情况下,如何确定该红色检测框的x,y，使得其与其他所有绿色检测框的交并比都为0？

检测框用[x,y,w,h]四个元素表示，分别表示图像左上角x坐标，y坐标，矩形宽和高。

在以下示例中，红色检测框的左上角点坐标范围解集应该为 {0<x<20,150<y<220}，但程序无法解出，我尝试2种方法求解，但程序无法得到我的答案，请问为什么？

%% 
% The first method is to solve inequalities.  The problem is that I don't know how to list the desired equations.（第一种方法，解不等式求解，出现问题是不知道如何列出想要的等式）
objectROIs = [50,50,100,100;
   80,80,200,230];
image = zeros(320,320,3,'uint8');
image = insertObjectAnnotation(image,'rectangle',objectROIs,'object','Color','green');
imshow(image)
W = 60;
H = 100;

% solve eqns
syms x y
eqn1 = x>0;
eqn2 = y>0;
eqn3 = x<320-W;
eqn4 = y<320-H;
eqn5 = sum(bboxOverlapRatio([x,y,W,H],objectROIs),'all')==0; % error!!!
f = @(x,y)bboxOverlapRatio([x,y,W,H],objectROIs);

% 红色检测框的左上角点坐标范围解集应该为 {0<x<20,150<y<220}，但程序无法解出
eqns = [eqn1,eqn2,eqn3,eqn4,eqn5];
S = solve(eqns,[x,y],'ReturnConditions',true)


%% The second method, the optimization solution fails, exitflag has no solution（第二种方法，优化求解失败，exitflag无解）
W = 60;
H = 100;
fun = @(x)sum(bboxOverlapRatio([x(1),x(2),W,H],objectROIs),'all');
lb = [0,0];
ub = [320-W,320-H];
A = [];
b = [];
Aeq = [];
beq = [];
% nonlcon = @mycon(x,W,H,objectROIs);
x0 = (lb + ub)/2;
options = optimoptions('fmincon','Display','iter','Algorithm','interior-point');
[x,fval,exitflag] = fmincon(fun,x0,A,b,Aeq,beq,lb,ub,@(x)mycon(x,W,H,objectROIs),options)

ious = bboxOverlapRatio([round(x),W,H],objectROIs)
image = insertObjectAnnotation(image,'rectangle',[round(x),W,H],'insert','Color','red');
imshow(image)

-----------------------------------------------------method1 error!-----------------------------------------------

Error using bboxOverlapRatio

The value of 'bboxA' is invalid. Expected input to be one of these types:

uint8, int8, uint16, int16, uint32, int32, single, double

Instead its type was sym.

Error in bboxOverlapRatio>validateAndParseInputs (line 195)

parser.parse(bboxA,bboxB,varargin{:});

Error in bboxOverlapRatio>iParseInputs (line 94)

[bboxA, bboxB, ratioType] = validateAndParseInputs(bboxA, bboxB, varargin{:});

Error in bboxOverlapRatio (line 55)

[bboxA, bboxB, ratioType, isUsingCodeGeneration] = iParseInputs(bboxA,bboxB,varargin{:});

Error in TEST (line 17)

eqn5 = sum(bboxOverlapRatio([x,y,W,H],objectROIs),'all')==0;

------------------------------------------------------------method2, No feasible solution! ？？？ ----------------------------------------------------------------------------------

Converged to an infeasible point.

fmincon stopped because the size of the current step is less than

the value of the step size tolerance but constraints are not

satisfied to within the value of the constraint tolerance.

<stopping criteria details>

x =

150.0000 110.3551

fval =

0.1304

exitflag =

-2

ious =

0 0.1304

function [c,ceq] = mycon(x,W,H,objROIs)
c = [];     % Compute nonlinear inequalities at x.
ceq = sum(bboxOverlapRatio([round(x),W,H],objROIs),'all');   % Compute nonlinear equalities at x.

Answer 1

[Mohit Kumar]

Hi,

I think this might be a better approach to your problem :

img=zeros(320,320); % create a 320x320 zeros matrix to represent your image

To represent two known boxes, populate that region with ones.

img(r1:r1+w1,c1:c1+h1)=ones(w1,h1);
img(r2:r2+w2,c2:c2+h2)=ones(w2,h2);

% (r1,c1) is the position of the top left corner of the first green box
% (r2,c2) is the position of the top left corner of the first green b

Now, your problem reduces to finding a zeros matrix of size (w,h), where w and h represent the dimensions of your red box.

To do this, have a look on how to find a submatrix within another matrix. Some links for this :

https://in.mathworks.com/matlabcentral/answers/395258-most-efficent-way-of-finding-submatrices-of-a-matrix

https://matlabtricks.com/post-28/find-the-biggest-empty-box-example-of-two-dimensional-convolution

[cui,xingxing]

Thank you very much for the link you provided. According to 2D convolution, my problem can be solved ingeniously. The idea of conv2 function is to traverse row by column to find the result of convolution, but I get all feasible numerical solutions.

%% The problem is simplified as follows
objectROIs = [50,50,100,100;
   80,80,200,230];
image = zeros(320,320,'single');
image(50:50+100,50:50+100)=1;
image(80:80+200,80:80+230)=1;
imshow(image)

W = 60; % Fixed width pixel
H = 100;% Fixed height pixel

%% 2D convolution can get all numerical solutions
kernal = ones(H,W,'single');
out = conv2(image,kernal,'valid');
[row,col] = find(out==0);

%% show result
for i = 1:length(row)
    RGB = insertShape(image,'Rectangle',[col(i),row(i),W,H],'Color','red');
    imshow(RGB);
    pause(0.01);
end

If I want to get an analytical solution ? For example, I solved it by solving the inequality above? I think it should be able to solve the above optimization problem in a mathematical sense. Conv2() seems to me to be a brute force solution method (but the underlying optimization convolution speed is very fast).

[Mohit Kumar]

Hm, I am not able to think of methods to solve it analytically.

However, I do feel that a closed form analytical solution may not be possible here.. I'm not well versed in this topic though.

Your method of using inequalities fails because the bboxOverlapRatio is not meant to work with symbolic variables. I'm not quite sure I understand why the optimisation method fails.