Performance issues when clustering pixels by color

Question

EDIT: Giving up the lists and working with 2D arrays for both the pixels and clusters, as suggested by Cris Luengo, has solved the problem. The solution now runs in 10 sec what used to take 15 mins with the same input.

So I am trying to create a list of objects that represent the clusters of pixels in an image which contain adjacent pixels of same color (four-point neighborhood). My approach was to process the list of pixels and check which neighbors (and consecutively neighbors of their neighbors) have the same color.

I tried to avoid processing the same pixel twice by removing them from the outer list of pixels that will still be processed. However, my code still runs very slowly, even for small pictures. After trying different approaches, I still cannot make it fast enough (not waiting an eternity per run).

So I ask for advice on how to improve the below code in order make it quicker:

from Color_Cluster import Color_Cluster

class Color_Cluster_Processor:
    def get_three_biggest_color_clusters(self, image, filepath):
        self._pixels = []
        self._visited = []
        self._clusters = []
        self._image = image
        for h in range(image.height):
            for w in range(image.width):
                self._pixels.append((w,h))
        
        while self._pixels:
            pixel = self._pixels.pop(0)
            if pixel not in self._visited:
                current_color = image.getpixel(pixel)
                cluster = Color_Cluster(current_color)
                self._process_pixel(pixel, current_color, cluster)
                self._clusters.append(cluster)

        return []

    def _process_pixel(self, pixel, current_color, cluster):
        neighbors = []
        print(pixel)
        self._visited.append(pixel)
        cluster.add_pixel(pixel)
        self._enqueue_neighbors(pixel, current_color, neighbors)
        
        while neighbors:
            pixel = neighbors.pop(0)
            print(pixel)
            self._visited.append(pixel)
            self._pixels.remove(pixel)
            self._enqueue_neighbors(pixel, current_color, neighbors)

    def _enqueue_neighbors(self, pixel, current_color, neighbors):
        left = (pixel[0]-1, pixel[1])
        if left[0] >= 0:
            if self._is_valid_neighbor(left, current_color, neighbors):
                neighbors.append(left)
        up = (pixel[0], pixel[1]-1)
        if up[1] >= 0:
            if self._is_valid_neighbor(up, current_color, neighbors):
                neighbors.append(up)
        right = (pixel[0]+1, pixel[1])
        if right[0] < self._image.width:
            if self._is_valid_neighbor(right, current_color, neighbors):
                neighbors.append(right)
        down = (pixel[0], pixel[1]+1)
        if down[1] < self._image.height:
            if self._is_valid_neighbor(down, current_color, neighbors):
                neighbors.append(down)

    def _is_valid_neighbor(self, pixel, color, neighbors):
        if pixel not in self._visited and pixel not in neighbors and self._is_color_match(pixel, color):
            return True

    def _is_color_match(self, pixel, color):
        if self._image.getpixel(pixel) == color:
            return True