Image segmentation using SB

[mdshbz]

Dear bqth29,
I want to use the SB in image processing. But I am confused how to format the pixels into Ising problem. Can you help me?

[mdshbz]

I also want to know, have you included these three equations?

[bqth29]

Hi @mdshbz and thank you for your interest in the project!

We indeed included equations 7 and 8 in the code as they are required to perform the evolution of the spins. The only difference with the version you sent is that we use the equations from the most recent papers from Goto et al. that proved to be simpler to model while being more efficient:

• Goto, H., Endo, K., Suzuki, M., Sakai, Y., Kanao, T., Hamakawa, Y., ... & Tatsumura, K. (2021). High-performance combinatorial optimization based on classical mechanics. Science Advances, 7(6), eabe7953.
• Kanao, T., & Goto, H. (2022). Simulated bifurcation assisted by thermal fluctuation. Communications Physics, 5(1), 153.

In this new version, inelastic walls are simulated so the oscillators remain in the [-1, 1] range which makes the cubic term $Kx_i^3$ neglectable with respect to the linear terms (the ones with $x_i$). Thus, the $Kx_i^3$ term vanished.

Besides, the detuning frequency $\Delta$ was set to 1 (as all other variables depend on it, it is equivalent to dividing all equations by $\Delta$).

We end up with the following (simpler) equations:

• $\dot{x_i} = y_i$
• $\dot{y_i} = [p(t) - 1] x_i + \xi_0 \sum J_{i,j} x_j$

If you want to have a look at the code, you can read the symplectic_integrator.py file in the optimizer module which handles the symplectic equations under the hood of the SB algorithm. You can also see the two papers cited above if you want more information about the new version of the equations.

We will come back to you regarding your main question, we just need a bit more reflexion to give you a structured answer. In the meantime, do not hesitate to ask us any other question you may have.

All the best!

[BusyBeaver-42]

Dear bqth29, I want to use the SB in image processing. But I am confused how to format the pixels into Ising problem. Can you help me?

Dear mdshbz,

While it's feasible to utilize SB for image segmentation, it may not be the most suitable tool for this task. If your image comprises $N$ pixels and you intend to segment it into $C$ classes, the Ising problem's dimension would be $CN$, limiting its practical application to smaller images. In this scenario, SB utilizes a $CN \times CN$ matrix. Additionally, prior knowledge of the number of classes present in the image is necessary.

Should you still wish to employ SB for image segmentation, you'll need to establish a similarity measure wherein similar pixels possess a positive similarity value, while dissimilar ones exhibit a negative similarity value. It's essential to note that SB doesn't inherently incorporate spatial structure information from your image, necessitating its inclusion within the similarity measure. This measure need not solely rely on pixel value and position but can also consider the similarity between the surrounding areas of different pixels.

Define the $N \times N$ matrix $\tilde{J}$, where each element $(i,j)$ represents the similarity between pixel $i$ and pixel $j$. Additionally, allocate $C$ spins for each pixel $p$: $s_1^{(p)}, s_2^{(p)}, \ldots, s_C^{(p)}$. A pixel belongs to class $c$ if and only if $s_c^{(p)} = +1$. Construct the block diagonal $CN \times CN$ matrix $J$, comprising $C$ copies of $\tilde{J}$ along its diagonal. Furthermore, select a penalization parameter $\lambda > 0$, sufficiently large to ensure each pixel belongs to exactly one class. This ensures that if the spin vector minimizes the energy, then for every pixel $p$, there exists exactly one $c$ such that $s_c^{(p)} = +1$, with all others being $-1$. The penalty term takes the following form:

$$ \mathit{Penalty}(s) = - \lambda \sum_{p \text{ pixel}} \left( C - 2 + \sum_{c=1}^C s_c^{(p)} \right)^2 $$

Arrange all spins into the following vector:

$$ s = \begin{pmatrix} s_1^{(p_1)} \\ s_1^{(p_2)} \\ \vdots \\ s_1^{(p_N)} \\ s_2^{(p_1)} \\ s_2^{(p_2)} \\ \vdots \\ s_C^{(p_{N - 1})} \\ s_C^{(p_N)} \\ \end{pmatrix} $$

Then, aim to maximize the following quantity:

$$ s^T J s + \mathit{Penalty}(s) $$

Note: When utilizing SB for this problem, you need to input the sum of $J$ and the matrix representing the quadratic form $\mathit{Penalty}$.

Finally, since SB is an approximation algorithm, the output may not be optimal. Consequently, certain pixels may be assigned to more than one class, or conversely, some may remain unassigned. Thus, it's likely that some post-processing will be necessary.

[KunalKranti]

Dear bqth29,
Thanks for your reply.
kindly share your email for the further communication.

[bqth29]

Hi @KunalKranti,

In the interests of transparency of our open source code, we prefer that all discussions are publicly visible in our repository.

This allows everyone to participate in the discussions, and the solutions found remain available for other users who may have a similar question in the future.

Please feel free to open a new discussion if you have a topic you would like to discuss and we will be happy to help.

All the best!