import cv2
import numpy as np
import os
import sys
from itertools import combinations
import threading
from queue import Queue, Empty
import tkinter as tk
from tkinter import filedialog, messagebox, ttk
from PIL import Image, ImageTk
import networkx as nx
import logging

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
self.rotation = 0 # Rotation angle applied to the piece


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
    self.rotation = (self.rotation + angle) % 360
    # 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(q, progress_q):
while True:
piece = q.get()
if piece is None:
break
piece.compute_features(detector)
progress_q.put(piece.index)
q.task_done()


q = Queue()
progress_q = Queue()
threads = []
for _ in range(thread_count):
    t = threading.Thread(target=worker, args=(q, progress_q))
    t.daemon = True  # Daemonize thread
    t.start()
    threads.append(t)

for piece in pieces:
    q.put(piece)

# Collect progress
while True:
    try:
        piece_index = progress_q.get(timeout=1)
        yield piece_index
        progress_q.task_done()
    except Empty:
        if q.empty():
            break

# Stop workers
for _ in range(thread_count):
    q.put(None)
for t in threads:
    t.join()
==========================
Feature Matching and Homography Calculation
==========================
def match_features_between_pieces(pieces, matcher, ratio_threshold=0.75, min_matches=10):
"""
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 = {}
total_pairs = len(list(combinations(pieces, 2)))
processed = 0


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 = [m for m, n in matches if m.distance < ratio_threshold * n.distance]
    if len(good_matches) > min_matches:
        matches_dict[(piece1.index, piece2.index)] = good_matches
    processed += 1
    if processed % 100 == 0:
        logging.info(f"Matched {processed}/{total_pairs} pairs.")

logging.info(f"Total matched pairs: {len(matches_dict)}")
return matches_dict
def calculate_homographies(pieces, matches_dict, ransac_thresh=5.0, min_inliers=10):
"""
For each matched pair, calculate homography using RANSAC.
Returns a list of connections with homographies.
"""
connections = []
total_matches = len(matches_dict)
processed = 0


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 > min_inliers:
            connections.append({
                'p1': i,
                'p2': j,
                'homography': M,
                'inliers': inliers
            })
    processed += 1
    if processed % 100 == 0:
        logging.info(f"Calculated homographies for {processed}/{total_matches} matched pairs.")

logging.info(f"Total valid homographies: {len(connections)}")
return connections
==========================
Graph Construction and MST Calculation
==========================
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')
logging.info(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
        edge_data = mst.get_edge_data(current, neighbor)
        H = edge_data['homography']
        # Transform the top-left corner of neighbor's piece to current's coordinate
        pts = np.float32([[0, 0]]).reshape(-1, 1, 2)
        transformed_pts = cv2.perspectiveTransform(pts, H)[0][0]
        neighbor_piece = pieces[neighbor]
        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:
    logging.error("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:
        logging.warning(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):
self.master = master
self.master.title("Advanced Puzzle Assembly Application")
self.master.geometry("1200x800")
self.pieces = []
self.reconstructed_image = None
self.mst = None
self.original_image = None
self.threshold_image = None


    # Queues for thread-safe GUI updates
    self.log_queue = Queue()
    self.progress_queue = Queue()

    # Setup logging
    logging.basicConfig(level=logging.INFO)
    self.logger = logging.getLogger('PuzzleAssembly')

    # Create UI components
    self.create_widgets()

    # Start a periodic GUI update
    self.master.after(100, self.process_queue)

def create_widgets(self):
    # Frame for controls
    control_frame = ttk.Frame(self.master, width=300)
    control_frame.pack(side=tk.LEFT, fill=tk.Y, padx=10, pady=10)

    # Button to load image
    load_button = ttk.Button(control_frame, text="Load Puzzle Image", command=self.load_image)
    load_button.pack(pady=5, fill=tk.X)

    # Progress bar
    self.progress = ttk.Progressbar(control_frame, orient='horizontal', mode='determinate')
    self.progress.pack(pady=5, fill=tk.X)

    # Log window
    log_label = ttk.Label(control_frame, text="Process Log:")
    log_label.pack(pady=5)
    self.log_text = tk.Text(control_frame, height=20, state='disabled')
    self.log_text.pack(pady=5, fill=tk.BOTH, expand=True)

    # Save button
    save_button = ttk.Button(control_frame, text="Save Reconstructed Image", command=self.save_image)
    save_button.pack(pady=5, fill=tk.X)
    save_button.config(state='disabled')
    self.save_button = save_button

    # Frame for displaying images
    display_frame = ttk.Frame(self.master)
    display_frame.pack(side=tk.RIGHT, fill=tk.BOTH, expand=True, padx=10, pady=10)

    # Canvas to display the reconstructed image
    self.canvas = tk.Canvas(display_frame, bg='grey')
    self.canvas.pack(fill=tk.BOTH, expand=True)

def load_image(self):
    image_path = filedialog.askopenfilename(title="Select Puzzle Image",
                                            filetypes=[("Image Files", "*.jpg *.jpeg *.png *.bmp")])
    if not image_path:
        self.log("No image selected.")
        return
    self.log(f"Loading image: {image_path}")
    self.original, self.threshold = load_and_preprocess(image_path)
    self.original_image = self.original.copy()
    self.threshold_image = self.threshold.copy()
    self.display_image(self.threshold, title="Thresholded Image")
    self.log("Image loaded and preprocessed.")

    # Enable saving after processing
    self.save_button.config(state='disabled')

    # Proceed with processing in a separate thread to keep GUI responsive
    processing_thread = threading.Thread(target=self.process_image, args=(self.original, self.threshold), daemon=True)
    processing_thread.start()

def process_image(self, original, thresh):
    try:
        # Detect puzzle pieces
        self.log("Detecting puzzle pieces...")
        contours = find_puzzle_pieces(thresh, min_area=5000)
        if not contours:
            self.log("No puzzle pieces detected.")
            messagebox.showinfo("No Pieces Found", "No puzzle pieces were detected in the image.")
            return
        self.log(f"Detected {len(contours)} puzzle pieces.")

        # Extract pieces
        self.log("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)
        self.pieces = pieces
        self.log("Puzzle pieces extracted.")

        # Compute features with progress
        self.log("Computing SIFT features for each piece...")
        sift = cv2.SIFT_create()
        feature_gen = compute_piece_features(pieces, sift, thread_count=4)
        total_pieces = len(pieces)
        for _ in feature_gen:
            self.progress_queue.put(1)  # Increment progress
            # Optional: Update progress based on completed pieces
            # self.progress['value'] += (1 / total_pieces) * 100

        self.log("Feature computation completed.")

        # Match features
        self.log("Matching features between pieces...")
        bf = cv2.BFMatcher()
        matches_dict = match_features_between_pieces(pieces, bf, ratio_threshold=0.75, min_matches=10)
        if not matches_dict:
            self.log("No sufficient feature matches found.")
            messagebox.showinfo("No Matches Found", "No sufficient feature matches were found between pieces.")
            return
        self.log(f"Total matched pairs: {len(matches_dict)}")

        # Calculate homographies
        self.log("Calculating homographies...")
        connections = calculate_homographies(pieces, matches_dict, ransac_thresh=5.0, min_inliers=10)
        if not connections:
            self.log("Homography computation failed for all piece pairs.")
            messagebox.showinfo("Homography Failure", "Homography computation failed for all piece pairs.")
            return
        self.log(f"Total valid homographies: {len(connections)}")

        # Build graph and compute MST
        self.log("Constructing graph and computing Minimum Spanning Tree (MST)...")
        G = build_graph(pieces, connections)
        mst = compute_mst(G)
        if mst.number_of_edges() == 0:
            self.log("Minimal Spanning Tree could not be computed.")
            messagebox.showinfo("MST Failure", "Minimal Spanning Tree could not be computed.")
            return
        self.mst = mst
        self.log(f"MST has {mst.number_of_edges()} connections.")

        # Assemble puzzle
        self.log("Assembling the puzzle...")
        reconstructed = assemble_puzzle(pieces, mst)
        if reconstructed is None:
            self.log("The puzzle could not be assembled automatically.")
            messagebox.showinfo("Assembly Failed", "The puzzle could not be assembled automatically.")
            return
        self.reconstructed_image = reconstructed
        self.display_image(reconstructed, title="Reconstructed Puzzle")
        self.log("Puzzle assembly completed.")

        # Enable saving after successful assembly
        self.save_button.config(state='normal')

    except Exception as e:
        self.log(f"An error occurred: {e}")
        messagebox.showerror("Error", f"An error occurred: {e}")

def process_queue(self):
    try:
        while True:
            msg = self.log_queue.get_nowait()
            self.append_log(msg)
            self.log_queue.task_done()
    except Empty:
        pass

    try:
        while True:
            update = self.progress_queue.get_nowait()
            self.progress['value'] += update
            self.progress_queue.task_done()
    except Empty:
        pass

    self.master.after(100, self.process_queue)  # Check again after 100ms

def append_log(self, message):
    self.log_text.config(state='normal')
    self.log_text.insert(tk.END, f"{message}\n")
    self.log_text.see(tk.END)
    self.log_text.config(state='disabled')

def display_image(self, image, title="Image"):
    # Convert image to PhotoImage
    if len(image.shape) == 2:
        image_rgb = cv2.cvtColor(image, cv2.COLOR_GRAY2RGB)
    else:
        image_rgb = cv2.cvtColor(image, cv2.COLOR_BGR2RGB)
    img_pil = Image.fromarray(image_rgb)
    # Resize image to fit the canvas while maintaining aspect ratio
    canvas_width = self.canvas.winfo_width()
    canvas_height = self.canvas.winfo_height()
    if canvas_width < 10 or canvas_height < 10:
        # Initial size before the window is rendered
        canvas_width = 800
        canvas_height = 800
    img_pil.thumbnail((canvas_width, canvas_height), Image.LANCZOS)
    self.photo = ImageTk.PhotoImage(img_pil)
    self.canvas.delete("all")  # Clear previous images
    self.canvas.create_image(0, 0, anchor='nw', image=self.photo)
    self.canvas.config(scrollregion=self.canvas.bbox(tk.ALL))
    self.canvas.update()

def save_image(self):
    if self.reconstructed_image is None:
        messagebox.showinfo("No Image", "There is no reconstructed image to save.")
        return
    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(self.reconstructed_image, cv2.COLOR_BGR2RGB))
        self.log(f"Reconstructed puzzle saved at {save_path}")
        messagebox.showinfo("Saved", f"Reconstructed puzzle saved at {save_path}")

def log(self, message):
    self.log_queue.put(message)
    # Additionally, print to console for debugging
    print(message)
==========================
Utility Functions
==========================
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:
logging.error(f"Error: Image at path '{image_path}' could not be loaded.")
sys.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
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)
logging.info(f"Detected {len(pieces)} puzzle pieces.")
return 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)

==========================
Main Function
==========================
def main():
root = tk.Tk()
app = PuzzleGUI(root)
root.mainloop()

if name == "main":
main()




improve the code step by step