How do I identify clusters of the same values in a binary matrix?

Question

After doing spectral analysis on a recorded dial tone using Fourier transform and some data cleanup I ended up with a binary matrix that looks like this (red is 0, yellow is 1). Each pixel represents a single point in the matrix.

The X axis is time, and the Y axis is a sound frequency (not really relevant for the problem). What I'm trying to do is identify which two frequencies are currently playing at any given point in time. I've tried to cleanup the data as much as possible, which is why the matrix is binary and most of the clusters are separated from eachother.

What I need to do is figure out the clusters at each point where the frequencies change, and figure out their compound value vertically, as shows this image

It feels that there should be a well-known solution to this kind of problem, especially for a binary matrix like this, but I just can't think of a simple algorithm that would provably work. I don't really want to just eye-ball the solution.

Simply put, I need to somehow group all of these yellow square-ish clusters into a single point, or something like that. A solution using R would be preferred, but I'll accept a general algorithm/approach as well.

Answer 1

I wouldn't threshold this to a binary matrix, because this throws away information.

One way to approach this would be as a dynamic program. Divide frequency into a finite number of bins, and divide time into a finite number of bins. For each time, you need to pick two frequencies in a way that minimizes a penalty function. I would make the penalty function have two components:

1) One component measures how good the frequency choice is for a given instant. Take the average of all intensities outside the chosen frequencies, and take the average of the two intensities for the chosen frequencies. Now sum the square of the differences between the intensity of each frequency and the average it contributes to.

2) Another component is a penalty if the chosen frequencies for the current instant are not the same as the chosen frequencies for the previous timestep.

Now run a dynamic program to find the assignment of frequencies which minimizes the total of the two penalty functions. The relative size of the two contributions will have to be a tuneable parameter.

This approach doesn't make use of the fact that the frequencies change at regular times, so perhaps there is a better way, especially if you know what those times are.