I have spent the past week coding an app that should take an image, which is divided into x rows and y cols, shuffled around, and put it back into its original state without any info about the original image. I’ve checked over the internet and I couldn’t find any good way of solving this. Most people here talk about jigsaw puzzles only, which is a lot easier to do due to having the edge shape as well to work with.

I have ran into a problem where I can’t thing of a good algorithm to do this properly. At first I tried to use genetic algorithm to solve it, however, that also requires a very great algorithm and I didn’t like how it was always taking differently long and always produced different results (which is most likely my fault due to the algorithm for giving fitness values being not exactly great). Anyways, I remade the app to not use genetic algorithm and just use normal code to give each piece some fitness values to fitting with another piece and trying to build an image from there.

Example of such scrambled image is here: Scrambled image

What I am doing now for the algorithm is using edge detection on the pieces and then taking the pieces with the least amount of “edge” in it. However, this is not perfect and therefore the algoritm has a success rate of around 20% only.

Therefore, could I maybe get any other ideas of what algorithm to do or how to improve it?

Here is the main part of the code getting the fitness initially

def get_piece_fitness(self):  # checks how likely each piece is to be next to each other

        for piece_one in self.image_pieces:
            Helper.get_certain_loading(current_progress=piece_one.index + 1, final_num=len(self.image_pieces),
                                       description="Getting fitness values of piece edges: ")
            right_edge_fit_likelihood = []
            left_edge_fit_likelihood = []
            top_edge_fit_likelihood = []
            bottom_edge_fit_likelihood = []
            for piece_two in self.image_pieces:
                if piece_two != piece_one:  # check whether the pieces aren't the same piece

                    # concatenating horizontally on both sides at once to save on computing power
                    horizontal_edge_fit = np.concatenate(
                        [piece_two.gray_piece, piece_one.gray_piece, piece_two.gray_piece], axis=1)
                    horizontal_edge_likelihood = self.get_edge_fitness(horizontal_edge_fit, is_horizontal=True)

                    left_edge_fit_likelihood.append((piece_two, horizontal_edge_likelihood[0]))

                    right_edge_fit_likelihood.append((piece_two, horizontal_edge_likelihood[1]))

                    vertical_edge_fit = np.concatenate(
                        [piece_two.gray_piece, piece_one.gray_piece, piece_two.gray_piece])
                    vertical_edge_likelihood = self.get_edge_fitness(vertical_edge_fit, is_horizontal=False)

                    top_edge_fit_likelihood.append((piece_two, vertical_edge_likelihood[0]))

                    bottom_edge_fit_likelihood.append((piece_two, vertical_edge_likelihood[1]))

            piece_one.left_edge_candidates = left_edge_fit_likelihood
            piece_one.right_edge_candidates = right_edge_fit_likelihood
            piece_one.bottom_edge_candidates = bottom_edge_fit_likelihood
            piece_one.top_edge_candidates = top_edge_fit_likelihood

    def get_edge_fitness(self, image: np.ndarray, is_horizontal: bool) -> tuple[float, float]:
        image_blur = cv.GaussianBlur(image, (5, 5), 0)  # image blur
        edges = cv.Canny(image=image_blur, threshold1=30, threshold2=self.contrast)  # Canny Edge Detection

        if is_horizontal:
            edges_width = edges.shape[1]
            left_edge = np.array(edges[:, (edges_width // 3) - 1: (edges_width // 3)])
            right_edge = np.array(edges[:, (edges_width // 3) * 2 - 1: (edges_width // 3) * 2])

            left_edge_length = left_edge.size
            right_edge_length = right_edge.size

            left_edge_likelihood = np.sum(left_edge) / left_edge_length
            right_edge_likelihood = np.sum(right_edge) / right_edge_length

            return left_edge_likelihood, right_edge_likelihood
        else:
            edges_height = edges.shape[0]
            top_edge = np.array(edges[(edges_height // 3) - 1:(edges_height // 3)])
            bottom_edge = np.array(edges[(edges_height // 3) * 2 - 1:(edges_height // 3) * 2])

            top_edge_length = top_edge.size
            bottom_edge_length = bottom_edge.size

            top_edge_likelihood = np.sum(top_edge) / top_edge_length
            bottom_edge_likelihood = np.sum(bottom_edge) / bottom_edge_length

            return top_edge_likelihood, bottom_edge_likelihood