import cv2
import numpy as np
import matplotlib.pyplot as plt
import os
import sys
from itertools import combinations
import threading
from queue import Queue
import tkinter as tk
from tkinter import filedialog, messagebox
from PIL import Image, ImageTk
import networkx as nx

# ==========================
# PuzzlePiece Class Definition
# ==========================

class PuzzlePiece:
    def __init__(self, image, contour, bbox, index):
        self.image = image  # Image of the puzzle piece
        self.contour = contour  # Contour of the puzzle piece
        self.bbox = bbox  # Bounding box (x, y, w, h)
        self.index = index  # Unique identifier
        self.keypoints = None  # SIFT keypoints
        self.descriptors = None  # SIFT descriptors
        self.features_computed = False  # Flag indicating feature computation
        self.orientation = None  # Orientation angle
        self.position = None  # (x, y) position in the reconstructed puzzle

    def compute_features(self, detector):
        """Compute SIFT keypoints and descriptors."""
        gray = cv2.cvtColor(self.image, cv2.COLOR_BGR2GRAY)
        self.keypoints, self.descriptors = detector.detectAndCompute(gray, None)
        self.features_computed = True

    def rotate_image(self, angle):
        """Rotate the puzzle piece image by a given angle."""
        (h, w) = self.image.shape[:2]
        center = (w // 2, h // 2)
        M = cv2.getRotationMatrix2D(center, angle, 1.0)
        rotated = cv2.warpAffine(self.image, M, (w, h), flags=cv2.INTER_LINEAR, borderMode=cv2.BORDER_REFLECT)
        self.image = rotated
        # Update contour after rotation
        rotated_gray = cv2.cvtColor(rotated, cv2.COLOR_BGR2GRAY)
        _, thresh = cv2.threshold(rotated_gray, 0, 255, cv2.THRESH_BINARY + cv2.THRESH_OTSU)
        contours, _ = cv2.findContours(thresh, cv2.RETR_EXTERNAL, cv2.CHAIN_APPROX_SIMPLE)
        if contours:
            self.contour = max(contours, key=cv2.contourArea)
            self.bbox = cv2.boundingRect(self.contour)

# ==========================
# Feature Computation with Multithreading
# ==========================

def compute_piece_features(pieces, detector, thread_count=4):
    """
    Compute SIFT features for all puzzle pieces using multithreading.
    """
    def worker():
        while True:
            piece = q.get()
            if piece is None:
                break
            piece.compute_features(detector)
            q.task_done()

    q = Queue()
    threads = []
    for _ in range(thread_count):
        t = threading.Thread(target=worker)
        t.start()
        threads.append(t)

    for piece in pieces:
        q.put(piece)

    q.join()

    for _ in range(thread_count):
        q.put(None)
    for t in threads:
        t.join()

# ==========================
# Feature Matching
# ==========================

def match_features_between_pieces(pieces, matcher, ratio_threshold=0.75):
    """
    Match SIFT features between all pairs of puzzle pieces.
    Returns a dictionary with (i, j) as keys and list of good matches as values.
    """
    matches_dict = {}
    for (piece1, piece2) in combinations(pieces, 2):
        if piece1.descriptors is None or piece2.descriptors is None:
            continue
        matches = matcher.knnMatch(piece1.descriptors, piece2.descriptors, k=2)
        good_matches = []
        for m, n in matches:
            if m.distance < ratio_threshold * n.distance:
                good_matches.append(m)
        if len(good_matches) > 10:  # Minimum number of good matches
            matches_dict[(piece1.index, piece2.index)] = good_matches
    print(f"Total matched pairs: {len(matches_dict)}")
    return matches_dict

# ==========================
# Homography Calculation
# ==========================

def calculate_homographies(pieces, matches_dict, ransac_thresh=5.0):
    """
    For each matched pair, calculate homography using RANSAC.
    Returns a list of connections with homographies.
    """
    connections = []
    for (i, j), matches in matches_dict.items():
        piece1 = pieces[i]
        piece2 = pieces[j]
        src_pts = np.float32([piece1.keypoints[m.queryIdx].pt for m in matches]).reshape(-1, 1, 2)
        dst_pts = np.float32([piece2.keypoints[m.trainIdx].pt for m in matches]).reshape(-1, 1, 2)
        M, mask = cv2.findHomography(src_pts, dst_pts, cv2.RANSAC, ransac_thresh)
        if M is not None:
            inliers = mask.sum()
            if inliers > 10:  # Threshold for good homography
                connections.append({
                    'p1': i,
                    'p2': j,
                    'homography': M,
                    'inliers': inliers
                })
    print(f"Total valid homographies: {len(connections)}")
    return connections

# ==========================
# Graph Construction and MST
# ==========================

def build_graph(pieces, connections):
    """
    Build a graph where nodes are puzzle pieces and edges are connections based on homography.
    Edge weights are inversely proportional to the number of inliers.
    """
    G = nx.Graph()
    for piece in pieces:
        G.add_node(piece.index)
    for conn in connections:
        weight = 1.0 / conn['inliers']  # Higher inliers => lower weight
        G.add_edge(conn['p1'], conn['p2'], weight=weight, homography=conn['homography'])
    return G

def compute_mst(G):
    """
    Compute the Minimal Spanning Tree (MST) of the graph.
    """
    mst = nx.minimum_spanning_tree(G, weight='weight')
    print(f"MST has {mst.number_of_edges()} connections.")
    return mst

# ==========================
# Puzzle Assembly
# ==========================

def assemble_puzzle(pieces, mst):
    """
    Assemble the puzzle based on the MST connections.
    Returns the reconstructed image.
    """
    # Initialize position for the first piece
    first_piece_index = list(mst.nodes())[0]
    first_piece = pieces[first_piece_index]
    first_piece.position = np.array([0, 0])

    # BFS to traverse MST and set positions
    visited = set()
    queue = []
    queue.append(first_piece_index)
    visited.add(first_piece_index)

    while queue:
        current = queue.pop(0)
        current_piece = pieces[current]
        for neighbor in mst.neighbors(current):
            if neighbor in visited:
                continue
            # Get homography from current to neighbor
            H = mst[current][neighbor]['homography']
            # Compute neighbor's position using homography
            # Transform the top-left corner of neighbor's piece to current's coordinate
            neighbor_piece = pieces[neighbor]
            h, w = neighbor_piece.image.shape[:2]
            pts = np.float32([[0, 0]]).reshape(-1, 1, 2)
            transformed_pts = cv2.perspectiveTransform(pts, H)[0][0]
            neighbor_piece.position = current_piece.position + transformed_pts
            visited.add(neighbor)
            queue.append(neighbor)

    # Determine canvas size
    positions = [piece.position for piece in pieces if piece.position is not None]
    if not positions:
        print("No positions assigned to pieces.")
        return None
    positions = np.array(positions)
    min_x, min_y = int(np.min(positions[:, 0])), int(np.min(positions[:, 1]))
    max_x = int(np.max(positions[:, 0]) + max([piece.image.shape[1] for piece in pieces]))
    max_y = int(np.max(positions[:, 1]) + max([piece.image.shape[0] for piece in pieces]))

    # Translate positions to positive coordinates
    for piece in pieces:
        if piece.position is not None:
            piece.position -= [min_x, min_y]

    canvas_width = max_x - min_x
    canvas_height = max_y - min_y

    # Create a white canvas
    reconstructed = np.ones((canvas_height, canvas_width, 3), dtype=np.uint8) * 255

    # Place each piece on the canvas
    for piece in pieces:
        if piece.position is None:
            continue
        x, y = piece.position
        x = int(x)
        y = int(y)
        h, w = piece.image.shape[:2]
        if y + h > canvas_height or x + w > canvas_width:
            print(f"Piece {piece.index} exceeds canvas boundaries. Skipping placement.")
            continue
        roi = reconstructed[y:y+h, x:x+w]
        # Create mask
        gray = cv2.cvtColor(piece.image, cv2.COLOR_BGR2GRAY)
        _, mask = cv2.threshold(gray, 1, 255, cv2.THRESH_BINARY)
        mask_inv = cv2.bitwise_not(mask)
        # Black-out the area of the piece in ROI
        bg = cv2.bitwise_and(roi, roi, mask=mask_inv)
        # Take only region of the piece
        fg = cv2.bitwise_and(piece.image, piece.image, mask=mask)
        # Add the piece to the ROI
        dst = cv2.add(bg, fg)
        reconstructed[y:y+h, x:x+w] = dst

    return reconstructed

# ==========================
# GUI for User Interaction and Adjustments
# ==========================

class PuzzleGUI:
    def __init__(self, master, reconstructed_image, pieces):
        self.master = master
        self.master.title("Puzzle Assembly - Manual Adjustments")
        self.pieces = pieces
        self.selected_piece = None
        self.offset_x = 0
        self.offset_y = 0

        # Convert image for Tkinter
        self.image = cv2.cvtColor(reconstructed_image, cv2.COLOR_BGR2RGB)
        self.photo = ImageTk.PhotoImage(Image.fromarray(self.image))

        # Create Canvas
        self.canvas = tk.Canvas(master, width=self.image.shape[1], height=self.image.shape[0], bg='white')
        self.canvas.pack()
        self.canvas_image = self.canvas.create_image(0, 0, anchor='nw', image=self.photo)

        # Bind events
        self.canvas.bind("<ButtonPress-1>", self.on_press)
        self.canvas.bind("<B1-Motion>", self.on_move)
        self.canvas.bind("<ButtonRelease-1>", self.on_release)

        # Dictionary to hold images for pieces
        self.piece_images = {}
        for piece in self.pieces:
            if piece.position is not None:
                self.piece_images[piece.index] = ImageTk.PhotoImage(Image.fromarray(cv2.cvtColor(piece.image, cv2.COLOR_BGR2RGB)))
                self.canvas.create_image(piece.position[0], piece.position[1], anchor='nw', image=self.piece_images[piece.index], tags=str(piece.index))

        self.canvas.tag_bind("current", "<ButtonPress-1>", self.on_press)
        self.canvas.tag_bind("current", "<B1-Motion>", self.on_move)
        self.canvas.tag_bind("current", "<ButtonRelease-1>", self.on_release)

    def on_press(self, event):
        # Record the piece selected
        self.selected_piece = None
        clicked_tags = self.canvas.gettags(self.canvas.find_closest(event.x, event.y))
        if not clicked_tags:
            return
        tag = clicked_tags[0]
        try:
            piece_index = int(tag)
            self.selected_piece = self.pieces[piece_index]
            self.offset_x = self.selected_piece.position[0] - event.x
            self.offset_y = self.selected_piece.position[1] - event.y
        except:
            pass

    def on_move(self, event):
        if self.selected_piece:
            # Update piece position
            new_x = event.x + self.offset_x
            new_y = event.y + self.offset_y
            self.selected_piece.position = np.array([new_x, new_y])
            # Move the image on the canvas
            self.canvas.coords(str(self.selected_piece.index), new_x, new_y)
            self.redraw()

    def on_release(self, event):
        self.selected_piece = None

    def redraw(self):
        # Create a white canvas
        new_image = np.ones_like(self.image) * 255

        # Place all pieces
        for piece in self.pieces:
            if piece.position is not None:
                x, y = piece.position
                x = int(x)
                y = int(y)
                w, h = piece.image.shape[1], piece.image.shape[0]
                if y + h > new_image.shape[0] or x + w > new_image.shape[1]:
                    continue
                # Overlay the piece
                piece_img_rgb = cv2.cvtColor(piece.image, cv2.COLOR_BGR2RGB)
                new_image[y:y+h, x:x+w] = piece_img_rgb

        # Update the image on the canvas
        self.image = new_image
        self.photo = ImageTk.PhotoImage(Image.fromarray(self.image))
        self.canvas.delete(self.canvas_image)
        self.canvas_image = self.canvas.create_image(0, 0, anchor='nw', image=self.photo)

# ==========================
# Main Function
# ==========================

def main():
    # === Step 1: Select Image via GUI ===
    root = tk.Tk()
    root.withdraw()  # Hide the root window
    image_path = filedialog.askopenfilename(title="Select Puzzle Image",
                                            filetypes=[("Image Files", "*.jpg *.jpeg *.png *.bmp")])
    if not image_path:
        messagebox.showinfo("No File Selected", "No image file was selected. Exiting.")
        return

    # === Step 2: Load and Preprocess Image ===
    print("Loading and preprocessing image...")
    original, thresh = load_and_preprocess(image_path)
    cv2.imwrite('preprocessed_threshold.png', thresh)  # Save thresholded image for debugging

    # === Step 3: Detect Puzzle Pieces ===
    print("Detecting puzzle pieces...")
    contours = find_puzzle_pieces(thresh, min_area=5000)
    if not contours:
        messagebox.showinfo("No Pieces Found", "No puzzle pieces were detected in the image.")
        return

    # === Step 4: Extract Pieces ===
    print("Extracting puzzle pieces...")
    pieces = []
    for idx, cnt in enumerate(contours):
        piece_img, bbox = extract_piece(original, cnt)
        piece = PuzzlePiece(piece_img, cnt, bbox, idx)
        pieces.append(piece)

    # === Step 5: Compute Features ===
    print("Computing features for each piece...")
    sift = cv2.SIFT_create()
    compute_piece_features(pieces, sift)
    print("Feature computation completed.")

    # === Step 6: Feature Matching ===
    print("Matching features between pieces...")
    bf = cv2.BFMatcher()
    matches_dict = match_features_between_pieces(pieces, bf)
    if not matches_dict:
        messagebox.showinfo("No Matches Found", "No sufficient feature matches were found between pieces.")
        return

    # === Step 7: Homography Calculation ===
    print("Calculating homographies...")
    connections = calculate_homographies(pieces, matches_dict)
    if not connections:
        messagebox.showinfo("Homography Failure", "Homography computation failed for all piece pairs.")
        return

    # === Step 8: Graph Construction and MST ===
    print("Constructing graph and computing MST...")
    G = build_graph(pieces, connections)
    mst = compute_mst(G)
    if mst.number_of_edges() == 0:
        messagebox.showinfo("MST Failure", "Minimal Spanning Tree could not be computed.")
        return

    # === Step 9: Assemble Puzzle ===
    print("Assembling the puzzle...")
    reconstructed = assemble_puzzle(pieces, mst)
    if reconstructed is None:
        messagebox.showinfo("Assembly Failed", "The puzzle could not be assembled automatically.")
        return
    print("Puzzle assembly completed.")

    # === Step 10: Save Reconstructed Image ===
    save_option = messagebox.askyesno("Save Result", "Do you want to save the reconstructed puzzle image?")
    if save_option:
        save_path = filedialog.asksaveasfilename(defaultextension=".png",
                                                 filetypes=[("PNG Files", "*.png"), ("JPEG Files", "*.jpg"), ("All Files", "*.*")],
                                                 title="Save Reconstructed Puzzle As")
        if save_path:
            cv2.imwrite(save_path, cv2.cvtColor(reconstructed, cv2.COLOR_BGR2RGB))
            messagebox.showinfo("Saved", f"Reconstructed puzzle saved at {save_path}")

    # === Step 11: Launch GUI for Manual Adjustments ===
    print("Launching GUI for manual adjustments...")
    gui_root = tk.Tk()
    gui = PuzzleGUI(gui_root, reconstructed, pieces)
    gui_root.mainloop()

# ==========================
# Image Loading and Preprocessing
# ==========================

def load_and_preprocess(image_path):
    """
    Load the image, convert to grayscale, blur, and threshold to obtain binary image.
    """
    # Load image
    image = cv2.imread(image_path)
    if image is None:
        print(f"Error: Image at path '{image_path}' could not be loaded.")
        exit()
    original = image.copy()

    # Convert to grayscale
    gray = cv2.cvtColor(image, cv2.COLOR_BGR2GRAY)

    # Apply Gaussian Blur to reduce noise
    blurred = cv2.GaussianBlur(gray, (5, 5), 0)

    # Apply binary thresholding
    _, thresh = cv2.threshold(blurred, 0, 255, cv2.THRESH_BINARY_INV + cv2.THRESH_OTSU)

    return original, thresh

# ==========================
# Detecting Puzzle Pieces
# ==========================

def find_puzzle_pieces(thresh, min_area=5000):
    """
    Find contours in the thresholded image and filter them based on area.
    """
    contours, _ = cv2.findContours(thresh, cv2.RETR_EXTERNAL, cv2.CHAIN_APPROX_SIMPLE)
    pieces = []
    for cnt in contours:
        area = cv2.contourArea(cnt)
        if area > min_area:
            pieces.append(cnt)
    print(f"Detected {len(pieces)} puzzle pieces.")
    return pieces

# ==========================
# Extracting Puzzle Pieces
# ==========================

def extract_piece(image, contour):
    """
    Extract the puzzle piece from the image using the contour.
    """
    x, y, w, h = cv2.boundingRect(contour)
    piece_image = image[y:y+h, x:x+w]
    return piece_image, (x, y, w, h)

# ==========================
# Execute the Script
# ==========================

if __name__ == "__main__":
    main()



just remeber this script