Air carrier Captain reported releasing the brakes before the pushback crew had disconnected headset. Pushback crew communicated to Captain who stopped aircraft movement.

Narrative

During pushback; everything was normal up until the initial taxi. After pushback was complete; the pushback crew told me to set the parking brake and then cleared us to start the engines. We complied with his instructions and set the brakes. We then started the engines uneventfully. I knew that once I received the command to set the parking brake that the ground crew would be disconnecting the tow bar. Several minutes had passed and I had not heard back from the ground crew. I thought that I had cleared him to disconnect his headset since I had not heard back from him. There was no ground crew person or equipment in sight either in front of the airplane or to either side. There was also no one in front of us with wands in hand signaling 'stop' like we are used to seeing in ZZZ. So; because I had not heard from nor seen anyone; I asked for the flaps to be placed to the takeoff position. I then performed a control check and asked for the after start checklist. Once complete; I asked for my first officer to get the ATC taxi clearance. Once received; I turned on the taxi light then released the brakes. The airplane moved slightly forward a few inches when I heard the ground crew say; 'flight deck' on the interphone. I immediately stopped the airplane and set the parking brake. Due to non-normal pushback communications; I did not know that the ground crew was still on headset although the towbar was disconnected. I told the ground crew that I did not know that he was still on headset. I then cleared him to disconnect his headset and that I would look for his salute. He complied with those instructions. We then asked for and received taxi instructions with no further issues.